В чем уникальность SHA?

Я пытаюсь понять уникальность SHA простыми словами. Например, предположим, что во всем мире есть только сообщения с максимальной длиной 4 бита (binery). Количество возможных сообщений разной длины равно

  • 2 для однобитной длины
  • 2^2 для двойной длины бит
  • 2^3 для 3-битной длины
  • 2^4 для 4-битной длины

это будет 2 + 4 + 8 + 16 = 30 (31, если мы рассмотрим пустое сообщение 2 ^ 0 = 1)

Давайте рассмотрим SHA3 (например) с выходной длиной 3 бита (binery), поэтому максимально возможное количество дайджестов равно 8. Как дайджест может быть уникальным, если нам нужно сопоставить 30 сообщений с 8, или почему трудно найти дайджест коллизия для 2 уникальных сообщений


security crc cryptography hash sha
person Ravi J    schedule 15.02.2020    source источник
comment
Вы слышали голубятню? Что тесно связано с хэш-функциями и их защитой от коллизий.   -  person kelalaka    schedule 15.02.2020
comment
Вы забыли, что 2^0=1, возможно и пустое сообщение. Так что это 31 сообщение, а не 30.   -  person Maarten Bodewes    schedule 16.02.2020
comment
Этот вопрос на самом деле не о программировании, но я не уверен, что он будет хорошо принят в криптографии из-за неправильного представления о том, что SHA3 имеет 3-битный вывод.   -  person Maarten Bodewes    schedule 16.02.2020
comment
Я считаю, что Pigeon-hole доказывает обратное, например, в моем вопросе в соответствии с теорией peigionhole должно произойти столкновение после 8 уникальных дайджестов. Я что-то упустил здесь?   -  person Ravi J    schedule 17.02.2020
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что речь идет не о программировании, а о криптографии (где кросс-пост был закрыт как обман этот вопрос)   -  person Maarten Bodewes    schedule 17.02.2020

Ответы (3)


arrow_upward
1
arrow_downward

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

Криптографическая хеш-функция имеет три важных свойства (которые делают ее криптографическим хэшем по сравнению с обычным хэшем):

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

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

person Gabor Lengyel    schedule 15.02.2020
comment
@kelalaka Разве я сказал иначе? :) (Редактировать: вы имеете в виду фразу, чтобы найти ввод? Вы действительно правы - я исправляю это, потому что это не очень хороший способ выразить это, спасибо) - person Gabor Lengyel; 15.02.2020
comment
Формальные определения лучше написаны П. Рогавеем, написанным здесь, на SO, поскольку принятый ответ был неверным и никогда не исправлялся. Обычно мы не отвечаем на вопросы по криптографии, не связанные с программированием. - person kelalaka; 15.02.2020
comment
Этот ответ требует вычислений, подобных здесь. Как я уже отмечал в ответ на вопрос, ОП необходимо узнать о принципе сортировки, который вы могли бы рассмотреть. - person kelalaka; 16.02.2020
comment
Мой вопрос больше о том, как гарантируется свойство сильного сопротивления столкновениям? только ли большая длина выходного хэша делает вычислительно невозможным поиск коллизии? - person Ravi J; 17.02.2020

arrow_upward
0
arrow_downward

«SHA3 с длиной дайджеста 3 бита»

Я думаю, что этот вопрос основан на одном недоразумении. SHA-3 — это семейство хэшей, которое имеет тот же размер выходного бита, что и SHA-2. SHA-2 имеет битовые размеры 224, 256, 384 или 512 для SHA-224, SHA-256, SHA-384 и SHA-512 соответственно.

Конечно, SHA-2 уже использует эти идентификаторы, поэтому SHA-3 будет иметь SHA3-224, SHA3-256, SHA3-384 и SHA3-512. Было несколько предложений использовать другую аббревиатуру, но они не увенчались успехом.

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

person Community    schedule 16.02.2020
comment
Конечно, все станет странно, как только мы доберемся до семейства хэшей SHA-160, но я думаю, что мы можем принять решение о новой аббревиатуре тогда. На самом деле я думаю, что человечество к тому времени вымерло, но это другой вопрос. - person Maarten Bodewes; 16.02.2020
comment
В качестве примера я привел SHA с 3-битным выходом, я думаю, что это не ясно выражено в вопросе. уточню так же - person Ravi J; 17.02.2020

arrow_upward
-1
arrow_downward

Любой вариант SHA3 будет иметь дайджесты длиной более 100 бит. Терминология, вероятно, смутила вас, потому что SHA256 имеет 256 бит, а SHA3 считается третьим поколением алгоритмов SHA (и НЕ имеет 3-битной длины).

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

person mtrycz    schedule 15.02.2020
comment
Было бы большим заблуждением сказать, что нетрудно найти коллизию для любой правильной криптографической хеш-функции. В том-то и дело, что его действительно трудно найти. Логически не сложно, конечно, потому что вам нужно только пройти через большое количество входных данных. Но практически невозможно, потому что их просто слишком много. - person Gabor Lengyel; 15.02.2020
comment
Я ясно дал понять, что это отнимает много времени, но дело в том, что найти значимое столкновение — это уже другой уровень сложности. - person mtrycz; 15.02.2020
comment
Нет, это не просто отнимает время. Это практически невозможно, потому что требуемое количество времени действительно очень велико. Для хороших криптохэшей никогда не было обнаружено коллизий. - person Gabor Lengyel; 15.02.2020
comment
На самом деле это зависит от сложности хэша. Первоначальный вопрос начался с 3-битных дайджестов, поэтому в его контексте это имеет смысл. Я хочу подчеркнуть, что найти прообраз, который имеет смысл в данном контексте, гораздо важнее и гораздо сложнее, чем просто найти случайное столкновение. - person mtrycz; 15.02.2020
comment
Пока вы продолжаете утверждать, что в SHA-3 нетрудно найти коллизию без серьезного прорыва, этот ответ ложен и останется ложным. Престижность за обнаружение проблемы в первом разделе, но этот второй раздел необходимо заменить. - person Maarten Bodewes; 16.02.2020