|
|
Компьютеры - Структура МерклаДамгарда - Алгоритмы, реализующие структуру Меркла-Дамгарда23 января 2011
Оглавление: 1. Структура МерклаДамгарда 2. Алгоритмы, реализующие структуру Меркла-Дамгарда 3. Пример дополнения сообщения 4. Wide pipe construction
- Message-Digest algorithm 5
- SHA-1, SHA-2, SHA-3
Характеристики безопасности
Популярность структуры Меркла-Дамгарда обусловлена тем, что, как было доказано, если односторонняя функция сжатия f устойчива к коллизиям, то и хеш-функция, построенная на ее основе, будет также устойчива к коллизиям. Эта структура имеет несколько нежелательных свойств:
- Дополнение до необходимой длины когда атакующий найдет хотя бы одну коллизию, он очень легко может найти другие.
- Нахождение второго сообщения, дающего такой-же хеш для длинных сообщений всегда намного более эффективны, чем перебор. Атака для сообщения из 2 блоков может быть выполнена за время k x 2 + 2. Важно, что сложность атаки находится между 2 и 2 когда сообщения длинные. Когда длина сообщения становится меньше, сложность приближается к 2.
- Множественные коллизии могут быть найдены лишь незначительно большими усилиями, чем коллизии.
- Атаки дополнением сообщения: При данном хеше H неизвестного входного сообщения X, легко найти значение H||Y), где pad функция дополнения . Это значит, что возможно найти хеши входных сообщений, связанных с X, даже когда X остается неизвестным. Random oracle не имеет такой возможности, и это может привести к простым атакам даже на схемы, безопасность которых была доказана для модели атак random oracle.
Просмотров: 3381
|