Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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

Криптостойкость криптографических хэш-функций

На криптографические хэш-функции возможны следующие атаки:

1. Нахождение прообраза М по заданному значению НМ= h(М).

Такая атака особенно опасна для систем аутентификации, использующих хэш-образы паролей и секретных ключей;

2. Нахождение второго прообраза М’ по заданному прообразу М, для которого выполняется условие h(M) = h(M’).

Эта атака может быть использована для фальсификации сообщения при контроле целостности с использованием хэш-функции (Пример).

3. Нахождение коллизии,т.е. двух прообразов М и М’,, для которых выполнялось бы условие h(M) = h(M’).

Эта атака может быть использована для фальсификации сообщения, подписанного цифровой подписью (Пример).

При использовании вероятностной атаки для нахождения прообраза (второго прообраза) вероятность нахождения второго прообраза (вероятность успеха атаки навязывания) Рн можно оценить по формуле

Рн = 1/2LА

Так как хэш-функция не содержит секретных параметров, то наряду с вероятностной атакой возможны и детерминированные.

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

1. Атака “грубой силой” может быть использована при нахождения прообраза по заданному хэш-образу. Суть атаки заключается в последовательном или случайном переборе входных сообщений и сравнения полученного хэш-образа с заданным. Сложность такой атаки оценивается 2L-1 операций вычисления хэш-образа, где L - длина хэш-образа в битах.

Обоснование.

Криптоаналитик формирует некоторое число произвольных сообщений М12, …, Мк, вычислят их хэш-образы НМ1, НМ2, …, НМк и сравнивает их значения с заданным НМ1. Атака окажется успешной, если будет найдена хотя бы одна коллизия. Вероятность нахождения второго прообраза (вероятность успеха атаки навязывания) РК можно оценить по формуле

РК = 1- (1- 1/2LА)К

где

К - число вычисленных хэш-образов;

LА = || НМ || - длина хэш-образа.

Сложность атаки навязывания (количество испытаний К, при котором РК =0.5)

К > 2LА-1.

Пример – см. Таблицу 3.1.

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

Рн ≈ еxp(–n1n2/2LА )

В частности, при = = 2 0.5 L

сложность атаки К (число вычислений хэш-образа)

К=2LА/2+1,

а вероятность нахождения коллизии

РК ≈ 1 – 1/e ≈ 0.63

Так как на современном уровне минимальная сложность атаки должна быть не меньше, чем 2128 , то длина хэш-образа L для обеспечения стойкости к атаке нахождения коллизии методом «дня рождения» должна быть не менее 256 бит, т.е. в два раза больше, чем для обеспечения стойкости к атаке нахождения второго прообраза.

* Парадоксе “дня рождения”

· Парадокс “дня рождения” является стандартной статистической проблемой.

· А) Сколько человек должно собраться, чтобы с вероятностью равной 0.5 хотя бы у одного из них был общий с Вами день рождения? Ответ: 183

· В) Сколько человек должно собраться, чтобы с вероятностью равной 0.5 хотя бы у двоих из них был общий день рождения? Ответ: 23

 

Таблица 3.1 Характеристики криптостойкости хэш-функций

Длина хэш-образа LА, бит Нахождение второго прообраза  
Вероятностная атака   Рн   Детерминированная атака (Рн =0.5) Время (MIPS-лет) Детерминированная атака (Рн =0.5) Время (MIPS-лет)
  1,08 × 10–19 3×105 1,19 часа
  5,88 × 10–39 5,4 × 1024 6×105
  1,73 × 10–77 1,8 × 1063 1,1 × 1025
  1,49 × 10–154 2,1 × 10140 3,7 × 1063

 

Одна MIPS (Million Instruction Per Second) машина хэширует миллион сообщений в секунду. При таких условиях число хэш-образов, вычисленных одной MIPS машиной за один год составляет 3.15×1013.

<== предыдущая лекция | следующая лекция ==>
Требования к криптографической хэш-функции | Архитектура хэш-функций
Поделиться с друзьями:


Дата добавления: 2013-12-13; Просмотров: 438; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.