Интернет магазин китайских планшетных компьютеров



Компьютеры - N-Hash - Безопасность хеш-функций

27 апреля 2011


Оглавление:
1. N-Hash
2. Использование
3. Особенности N-Hash
4. Цели N-Hash
5. Алгоритм
6. Безопасность хеш-функций
7. Итоги



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

Для того, чтобы хеш-функция была безопасной, необходимо, чтобы выполнялись условия:

  • При изменениях в тексте сообщения M должен меняться и хеш-код сообщения;

Иначе человек, который вводит свои логин и пароль для входа в Википедию, мог бы попасть на страницу другого участника.

  • Невозможность нахождения сообщения M по известному хеш-коду h из h = H;

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

  • Задача нахождения сообщений M1 и M2, таких что их хеш-коды равны h1 = h2 должна быть очень трудоёмкой.

Иначе, можно было бы найти два пароля с одинаковыми хеш-кодами.

N-Hash не является безопасной функцией, так как для нее не выполнено последнее условие.

Криптоанализ N-Hash

В настоящее время N-Hash считается небезопасной функцией. На данном рисунке указаны все безопасные однонаправленные функции на данный момент согласно стандарту ISO/IEC 10118:

NHash safe.png

Из алгоритмов, построенных как и N-Hash на основе блочных шифров, безопасными считаются только MDC-2 и MDC-4.

Для N-Hash характерна следующая проблема:

  • Так как длина хеш-кода равна длине блока алгоритма шифрования, то алгоритм нестоек перед атакой методом «дней рождения».

Атаки на хеш-функции

Hash attack.png

На данном рисунке приведена классификация атак на все алгоритмы хеширования в целом.

Атаки, зависящие от алгоритма, являются атаками, основанными на свойствах конкретного алгоритма.

Например, N-Hash успешно атакуют с помощью дифференциального метода, атакой с фиксированной точкой и встречей посередине.

Атаки, не зависящие от алгоритма, можно применить к любой функции хеширования, однако это не исключает того, что для некоторых алгоритмов они очень трудоёмки из-за большого объёма информации или быстродействия кода.

Действенные атаки на N-Hash

  • метод «грубой силы»
  • встреча посередине
  • метод «дня рождения»
  • дифференциальный метод
  • атака с фиксированной точкой
Атаки, базирующиеся на уязвимости алгоритма
Дифференциальный метод

Ден Бур предложил способ построения коллизии для однораундовой схемы N-Hash.

Бихам и Шамир успешно применили метод дифференциального криптоанализа для компрометации 6-раундовой схемы N-Hash. Предложенный ими способ построения коллизии срабатывает для любого значения N кратного трём и при этом для N ≤ 12 он оказывается эффективнее подхода, основанного на парадоксе дней рождения.

Для 12-раундовой схемы сложность построения коллизий предложенным методом оценивается величиной 256 операций.

Атаки, не зависящие от алгоритма

Увеличение длины хеш-кода и секретного ключа усложнит работу криптоаналитика. Можно попытаться сделать вычисления слишком трудоёмкими для персонального компьютера и требующими больших ресурсов. Тогда криптоаналитику надо будет или искать суперкомпьютер, или написать вирус, который на основе распараллеливания процесса взлома хеш-функции будет использовать сразу несколько персональных компьютеров для решения проблемы.

Также действенны такие методы защиты хеш-функции:

  • использование контрольных сумм на разных этапах хеширования;
  • проверка на достоверность информации;
  • внедрение в сообщение информации типа salt.


Просмотров: 3680


<<< Message authentication algorithm
PJW-32 >>>