Если вы знаете длину строки и применяете к ней хеш SHA1, можете ли вы ее хешировать?

Question

Просто интересно, если знать, что оригинальная длина строки означает, что вам лучше использовать шифрование SHA1.

Answer 1

Нет, не в общем случае: хеш-функция не является функцией шифрования и не предназначена для обратимости.

Обычно невозможно наверняка восстановить исходный хеш. Это связано с тем, что размер домена хеш-функции превышает диапазон функции. Для SHA-1 домен не ограничен, но диапазон составляет 160 бит.

Это означает, что по принципу Pigeonhole , несколько значений в домене сопоставляются с тем же значением в диапазоне. Когда такие два значения отображаются на один и тот же хеш, это называется коллизия хешей .

Однако, для определенного ограниченного набора входов (где область входов намного меньше , чем диапазон хеш-функции), тогда, если обнаружено столкновение хеша Например, с помощью поиска методом грубой силы , может быть «приемлемым», предполагая, что входная информация, вызывающая хэш, была исходным значением. Вышеописанный процесс фактически является прообразом атаки . Обратите внимание, что этот подход очень быстро становится невозможным, , как показано внизу. (Есть, вероятно, несколько хороших математических формул, которые могут определить «приемлемые» с точки зрения вероятности коллизии для данного размера домена, но я не настолько подкован.)

Единственный способ узнать, что это был вход only , который сопоставлен с хэшем, однако, это выполнить исчерпывающий поиск по всем значениям в диапазоне - такие как все строки с заданной длиной - и убедитесь, что это был единственный такой ввод, который привел к данному хэш-значению.

Обратите внимание, однако, что ни в коем случае процесс хеширования не является "обращенным". Даже без действующего принципа голубиных дырок, SHA-1 и другие криптографические хеш-функции специально предназначены для невозможности обратного , то есть они "односторонние" хеш-функции. Есть несколько продвинутых техник, которые можно использовать для уменьшения диапазона различных хэшей; их лучше оставить докторам наук или людям, специализирующимся на криптографическом анализе: -)

Удачного кодирования.

---

Для развлечения попробуйте создать прообраз грубой силы на строке из 3 символов. Предполагая, что допустимы только английские буквы (A-Z, a-z) и цифры (0-9), в этом случае есть комбинации «только» 62 ³ (238,328). Затем примерьте строку из 4 символов (62 ⁴ = 14 776 336 комбинаций) ... 5 символов (62 ⁵ = 916 132 832 комбинаций) ... 6 символов (62 ⁶ = 56 800 235 584 комбинации) ...

Обратите внимание, насколько больше домен для каждого дополнительного символа: этот подход быстро становится непрактичным (или «неосуществимым»), и хэш-функция выигрывает: -)

Одним из способов взлома паролей для ускорения атак прообразом является использование радужных таблиц (которые могут охватывать только небольшой набор всех значений в домене, на который они рассчитаны), который именно поэтому пароли, использующие хеширование (SHA-1 или иное), всегда должны иметь большое случайное число .

Answer 2

Я отправил это как ответ на другой вопрос, но я думаю, что это применимо здесь:

---

SHA1 - алгоритм хеширования. Хеширование является односторонним, что означает, что вы не можете восстановить входные данные с выхода.

Эта картинка демонстрирует, что такое хеширование, несколько:

Как видите, и John Smith, и Sandra Dee сопоставлены с 02. Это означает, что вы не можете восстановить , имя которого было хешировано, только 02.

Хеширование используется в основном по этому принципу:

Если hash(A) == hash(B), то есть действительно хороший шанс, что A == B. Хеширование отображает большие наборы данных (например, всю базу данных) в крошечный вывод, например, в 10-символьную строку. Если вы перемещаете базу данных и хеш-значения как входных, так и выходных данных совпадают, то вы можете быть уверены, что база данных не повреждена. Это намного быстрее, чем сравнивать обе базы данных побайтно.

Это видно на картинке. Длинные имена отображаются на двузначные числа.

---

Чтобы адаптироваться к вашему вопросу, если вы используете брутфорс-поиск, для строки заданной длины (скажем, длины l) вам придется хешировать до (dictionary size)^l различных хешей.

Если словарь состоит только из буквенно-цифровых символов, чувствительных к регистру, то у вас есть (10 + 26 + 26)^l = 62^l хэшей для хеширования. Я не уверен, сколько FLOPS требуется для создания одного хэша (так как это зависит от длины хэша). Давайте будем супер-нереалистичными и скажем, что для выполнения одного хэша требуется 10 FLOP.

Для 12-символьного пароля это 62^12 ~ 10^21. Это 10,000 секунды вычислений на самом быстром на сегодняшний день суперкомпьютере .

Умножьте это на несколько тысяч, и вы увидите, что это невозможно, если я немного увеличу размер словаря или увеличу пароль.

Answer 3

Теоретически, предположим, что строка также была известна только из символов ASCII и имеет размер n.

В ASCII 95 символов, не считая элементов управления. Предположим, что элементы управления не использовались.

Возможно 95ⁿ таких строк.

Есть 1.461501 × 10⁴⁸ возможных значений SHA-1 (дать или взять) и просто n = 25, есть 2.7739 × 10⁴⁹ возможных строк только для ASCII без элементов управления, что будет означать гарантированные коллизии (некоторые такие строки тот же SHA-1).

Итак, нам нужно добраться до n = 25, когда это становится невозможным даже при бесконечных ресурсах и времени.

И помните, до сих пор я сознательно облегчал это с помощью своего правила только для ASCII. Современный текст в реальном мире не следует этому.

Конечно, только подмножество таких строк могло бы быть чем-то реальным (если одна говорит «привет, меня зовут Джон», а другая говорит «fsdfw09r12esaf», то это, вероятно, первая). Тем не менее, до сих пор я предполагал бесконечное время и вычислительную мощность. Если мы хотим решить это до того, как наступит конец вселенной, мы не можем этого допустить.

Конечно, характер атаки также важен. В некоторых случаях я хочу найти исходный текст, в то время как в других я буду доволен тарабарщиной с тем же хешем (если я могу ввести его в систему, ожидая пароль).

Правда, ответ - нет.

Answer 4

Хеш-функциями являются односторонняя функция. Для данного размера есть много строк, которые могли бы создать этот хэш.

Теперь, если вы знаете, что размер ввода фиксирован достаточно мал, скажем, 10 байтов, и вы знаете, что каждый байт может иметь только определенные значения (например, A-Za-z0-9 ASCII), тогда вы можете используйте эту информацию для предварительного вычисления всех возможных хэшей и определения, какой простой текст создает хеш, который у вас есть. Эта техника является основой для Радужных столов .

Answer 5

Если бы это было возможно, SHA1 сейчас не был бы таким безопасным.Это ? Так что нет, вы не можете, если у вас нет значительной вычислительной мощности [2 ^ 80 операций] .В этом случае вам также не нужно знать длину.

Одним из основных свойств хорошей криптографической хеш-функции , из которой SHA1 оказывается одна, является

it is infeasible to generate a message that has a given hash