Хэш функции

• 1 слайд

  Хэш функции
  Нестеров Антон
  

• 2 слайд

  План доклада
  Что это такое
  Зачем оно надо
  Примеры
  
  

• 3 слайд

  Hash-функция
  Пример не из криптографии – Хранение словаря
  Слово
  0 12080 20000
  hash
  12080
  Word
  

• 4 слайд

  Коллизии
  Пример не из криптографии – Хранение словаря
  Слово
  0 12080 20000
  hash
  12080
  Word
  Зебра
  hash
  

• 5 слайд

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

• 6 слайд

  Пример взлома
  Контракт 1
  Контракт 2
  232
  232
  

• 7 слайд

  Нахождение коллизий
  Метод дней рождений
  Сколько человек должно быть в комнате, чтобы вероятность того, что найдется человек родившийса с вами в один день была равна 0.5 ???
  
  Сколько человек должно быть в комнате, чтобы вероятность того, чтобы нашлась пара людей, родившихся в один день была 0.5 ???
  
  
  

• 8 слайд

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

• 9 слайд

  Немного примеров из истории
  Snefru Ральф Меркл
  N-hash 1990
  MD4, MD5 Рон Ривест
  SHA
  RIPE-MD
  HAVAL
  ГОСТ Р 34.11.94
  Использование блочных шифров
  

• 10 слайд

• 11 слайд

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

• 12 слайд

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

• 13 слайд

  Определения
  Определение hash-функции
  Функция H
  
  
  Или семейство
  
  
  Пользуясь предыдущим примером:
  D строчки русских букв
  R число от 0 до 20000
  
  H: K ×D → R.
  HK: D → R
  

• 14 слайд

  Определения
  Обратная функция
  
  
  Коллизия
  
  
  
  HK−1 (y) = { x  D : HK(x) = y }
  
  HK(x1) =
  HK(x2)
  

• 15 слайд

  Нахождение коллизий
  Три типа устойчивости
  CR2-KK
  Collision free, collision resistant
  CR1-KK
  Universal one-way
  CR0
  Universal
  
  
  

• 16 слайд

  Три вида атак на нахождение коллизий
  CR2-KK
  Найти коллизии для конкретной функции
  CR1-KK
  Подобрать пару к заданному значению, образующую коллизию для конкретгой функции.
  СК0
  Найти коллизию для семейства функций
  

• 17 слайд

  Литература
  Брюс Шнайер - Прикладная криптография
  FAQ по криптографии faqs.org.ru
  Mihir Bellare, Phillip Rogaway - Introduction to Modern Cryptography
  www.CyberSecurity.ru
  www.openbsd.org/ru/crypto.html
  www.cryptography.ru
  Shafi Goldwasser, Mihir Bellare - Lecture Notes on Cryptography