uzluga.ru
добавить свой файл


Хэш функции

  • Нестеров Антон


План доклада

  • Что это такое

  • Зачем оно надо

  • Примеры



Hash-функция

  • Пример не из криптографии – Хранение словаря



Коллизии

  • Пример не из криптографии – Хранение словаря



Практическое использование

  • Банкомат

  • Цифровая подпись

    • Быстро вычислимые
    • Не обратимые
    • Зная M сложно вычислить N такое, что H(M)=H(N)
    • Кроме того, сложно найти такие P и Q, что H(P)=H(Q)
  • Авторизация клиент-сервер



Пример взлома



Нахождение коллизий



Требования к функции

  • Актуальный размер кэша

    • Для 16 байтогого кэша (128 бит) 264 различных документов
    • Secure Hash Standard 160 бит 264
    • Специальный метод для удлиннения хэш-значений
    • Отсутствие коллизий осмысленных строк


Немного примеров из истории

  • Snefru Ральф Меркл

  • N-hash 1990

  • MD4, MD5 Рон Ривест

  • SHA

  • RIPE-MD

  • HAVAL

  • ГОСТ Р 34.11.94

  • Использование блочных шифров





Взломы и попытки взломов

  • Некоторые алгоритмы были вломаны

    • Найдены алгоритмы нахождения коллизий
  • Некоторые почти взломаны

    • Найдены алгоритмы нахождения
      • предколлизий
      • коллизий за меньшее время
      • коллизий в укороченных версиях
        • Атака на 7 из 10 уровней AES
        • Антуан Жу – работа о мульти хэш-функциях


MAC

  • Message authentication code

    • Хэш функция зависит от ключа
    • Можно менять ключ для дополнительной проверки
    • В качестве МАС можно использовать обычный хэш
      • H(K,H(K,M))
      • H(K,p,H,M)
    • Сложно подобрать ключ
    • Вычислить значение хэша для другого ключа


Определения

  • Определение hash-функции

    • Функция H
    • Или семейство
    • Пользуясь предыдущим примером:
      • D строчки русских букв
      • R число от 0 до 20000


Определения

  • Обратная функция

  • Коллизия



Нахождение коллизий

  • Три типа устойчивости

    • CR2-KK
      • Collision free, collision resistant
    • CR1-KK
      • Universal one-way
    • CR0
      • Universal


Три вида атак на нахождение коллизий

  • CR2-KK

    • Найти коллизии для конкретной функции
  • CR1-KK

  • СК0

    • Найти коллизию для семейства функций


Литература