Может ли хеш SHA-1 содержать все нули?

Question

Есть ли какие-либо входные данные, которые SHA-1 будет вычислять для шестнадцатеричного значения из шестидесяти нулей, т.е.

Answer 1

Да, это просто невероятно. То есть один на 2 ^ 160 или 0,00000000000000000000000000000000000000000000006842277657836021%.

Answer 2

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

В зависимости от вашей ситуации (если ваша логика может справиться с обработкой пустой строки как особого случая, чтобы запретить ее ввод), вы можете использовать хэш SHA1 ('da39a3ee5e6b4b0d3255bfef95601890afd80709') пустой строки. Также возможно использование хеша для любой строки, не входящей в ваш входной домен, такой как sha1 ('a'), если ваш ввод имеет только числовой формат в качестве инварианта. Если входные данные предварительно обработаны для добавления какого-либо обычного оформления, то будет работать и хеш чего-либо без оформления (например, sha1 ('abc'), если ваши входные данные, такие как 'foo', украшены кавычками к чему-то вроде '' foo '' ).

Answer 3

Я так не думаю.

Нет простого способа показать, почему это невозможно. Если бы это было так, то это было бы основой алгоритма поиска столкновений.

Более длительный анализ:

Предварительная обработка гарантирует, что на входе всегда есть хотя бы один 1 бит.

Цикл по w[i] оставит исходный поток в покое, поэтому на входе есть хотя бы один 1 бит (слова от 0 до 15). Даже при продуманном дизайне битовых комбинаций, по крайней мере, некоторые значения от 0 до 15 должны быть ненулевыми, поскольку цикл не влияет на них.

Примечание: leftrotate является круглым, поэтому 1 бит не будет потерян.

В основном цикле легко увидеть, что коэффициент k никогда не равен нулю, поэтому temp не может быть нулем, поскольку все операнды в правой части равны нулю (k никогда не равен ).

Это оставляет нас с вопросом, можете ли вы создать битовый шаблон, для которого (a leftrotate 5) + f + e + k + w[i] возвращает 0, переполнив сумму. Для этого нам нужно найти значения для w[i] такие, что w[i] = 0 - ((a leftrotate 5) + f + e + k)

Это возможно для первых 16 значений w[i], поскольку вы имеете полный контроль над ними. Но слова с 16 по 79 снова создаются с помощью xor первых 16 значений.

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

По сути, алгоритм был выбран таким образом, что вы можете создавать отдельные слова 0, выбирая шаблоны ввода, но эти эффекты нейтрализуются путем xor ввода шаблонов ввода для создания 64 других входов.

Просто пример: чтобы сделать temp 0, у нас есть

a = h0 = 0x67452301
f = (b and c) or ((not b) and d)
  = (h1 and h2) or ((not h1) and h3)
  = (0xEFCDAB89 & 0x98BADCFE) | (~0x98BADCFE & 0x10325476)
  = 0x98badcfe
e = 0xC3D2E1F0
k = 0x5A827999

, что дает нам w[0] = 0x9fb498b3 и т. Д. Затем это значение используется в словах 16, 19, 22, 24-25, 27-28, 30-79.

Слово 1, аналогично, используется в словах 1, 17, 20, 23, 25-26, 28-29, 31-79.

Как видите, много совпадений. Если вы вычислите входное значение, которое даст вам результат 0, это значение повлияет, наконец, на 32 других входных значения.

Answer 4

Пост Аарона неверен. Он зацикливается на внутренностях вычисления SHA1, игнорируя то, что происходит в конце функции раунда.

В частности, см. Псевдокод из Википедии . В конце раунда выполняются следующие вычисления:

h0 = h0 + a
h1 = h1 + b 
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e

Таким образом, вывод всех 0 может произойти, если h0 == -a, h1 == -b, h2 == -c, h3 == -d и h4 == -e войдут в этот последний раздел, где вычисления являются модом 2 ^ 32.

Чтобы ответить на ваш вопрос: никто не знает, существует ли вход, который выдает все нулевые выходные данные, но криптографы ожидают , что они основаны на простом аргументе, предоставленном daf.

Answer 5

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

Answer 6

Вопреки всем ответам здесь, ответ просто нет.

Хеш-значение всегда содержит биты, установленные в 1.

Answer 7

Вопреки всем текущим ответам, этого никто не знает. Существует большая разница между оценкой вероятности и доказательством.

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

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

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

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

[Я закончил с этим сайтом ... Мой первый ответ здесь, я попытался написать хороший ответ, но все, что я вижу, - это кучка придурков, которые ошибаются и даже не могут объяснить причину, почему они делают это. Ваше сообщество действительно разочаровало меня. Я все еще буду использовать этот сайт, но только пассивно]