Атака на хэши (часть3 или парадокс "Дней рождений")

[intro]

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

[Немного теории]

Хэш-функцией называется односторонняя (необратимая) функция, предназначенная для получения отпечатка файла, блока данных, строки пароля.
Требования к хэш-функциям
Пусть хэш-код h создается функцией Н:
h = H (M)
Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.
Рассмотрим необходимые требования, которым должна соответствовать хэш-функция для того, чтобы она могла использоваться в качестве аутентификатора сообщения, т.е. с очень большой степенью вероятности, близкой к 1 мы могли идентифицировать сообщение по его слепку:
1. Хэш-функция Н должна применяться к блоку данных любой длины.
2. Хэш-функция Н создает выход фиксированной длины. (часто кратна нескольким байтам, измеряется в битах)
3. Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М.
4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h.
5. Для любого данного х вычислительно невозможно найти y x, что H (y) = H (x).
6. Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x).
Хэш-функция, которая удовлетворяет первым пяти свойствам, называется простой или слабой хэш-функцией. Если кроме того выполняется шестое свойство, то такая функция называется сильной хэш-функцией. Шестое свойство защищает против класса атак, известных как атака "день рождения".
Что такое коллизия я рассписывать не буду, а напомню кратко: это ситуация, кода для хэш-функции H и входных данных a и b выполняется равенство h(a)=h(b), т.е. проще говоря, в случае хэширования разных паролей их хэши совпадают.
Какова вероятность такого совпадения? Многие скажут, что зависит от разрядности хэша и назовут сходу, например 1/2^64 для хэша 64bit (MySQL-Хэш) или 1/2^256 для (MD5-Хэш) что не совсем верно! Потому как неясно, каким образом сформированы исходные данные, подаваемые на вход хэш-функции.


Парадокс дней рождения — утверждение, что если дана группа из 23 или более человек, то вероятность того, что хотя бы у двух из них дни рождения (число и месяц) совпадут, превышает 50 %. Для группы из 60 или более человек вероятность совпадения дней рождения хотя бы у двух её членов составляет более 99 %, хотя 100 % она достигает, когда в группе не менее 366 человек (с учётом високосных лет — 367). Такое утверждение может показаться противоречащим здравому смыслу, так как вероятность одному родиться в определённый день года довольно мала, а вероятность того, что двое родились в конкретный день — ещё меньше, но является верным в соответствии с теорией вероятностей. Таким образом, оно не является парадоксом в строгом научном смысле — логического противоречия в нём нет, а парадокс заключается лишь в различиях между интуитивным восприятием ситуации человеком и результатами математического расчёта.

[Парадокс дней рождения с точки зрения здравого смысла]

Один из способов понять на интуитивном уровне, почему в группе из 23 человек вероятность совпадения дней рождения у двух человек столь высока, состоит в осознании следующего факта: поскольку рассматривается вероятность совпадения дней рождения у любых двух человек в группе, то эта вероятность определяется количеством пар людей, которые можно составить из 23 человек. Так как порядок людей в парах не имеет значения, то общее число таких пар равно числу сочетаний из 23 по 2, то есть 23*22/2 = 253 пары. Посмотрев на это число, легко понять, что при рассмотрении 253 пар людей вероятность совпадения дней рождения хотя бы у одной пары будет достаточно высокой.
Ключевым моментом здесь является то, что утверждение парадокса дней рождения говорит именно о совпадении дней рождения у каких-либо двух членов группы. Одно из распространённых заблуждений состоит в том, что этот случай путают с другим — похожим, на первый взгляд, — случаем, когда из группы выбирается один человек и оценивается вероятность того, что у кого-либо из других членов группы день рождения совпадёт с днем рождения выбранного человека. В последнем случае вероятность совпадения значительно ниже.
Более подробно, а также формулы расчёта можно посмотреть тут: http://ru.wikipedia.org/wiki/Парадокс_дней_рождения

[Пример расчёта вероятности]

Для примера я возьму колличество тех, кто был на момент написания статьи на Ачате из зарегистрированных, и так:
Кто онлайн?
Сейчас посетителей: 926 (87 пользователей и 839 гостей)
Расчитаем вероятность того, что у любой пары из 87 человек Дни рождения совпадают и примем, что дни рождения распределены равномерно, то есть нет високосных лет, близнецов на форуме, рождаемость не зависит от дня недели, времени года и других факторов. В действительности, конечно это далеко не так.
Число возможных Дней рождения равно колличеству дней в году, это 365. Берём наугад одного человека и запоминаем его день рождения, затем берём наугад второго человека, при этом вероятность того, что у него день рождения не совпадёт с днем рождения первого человека, равна 1 — 1/365, затем возьмём третьего человека, при этом вероятность того, что его день рождения не совпадёт с днями рождения первых двух, равна 1 — 2/365. Рассуждая по аналогии, мы дойдём до последнего 87 человека, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна 1 — 86/365~0,764.Перемножив все эти вероятности, мы получаем вероятность события, что все 87 ачатовцев имеют разные Дни рождения, она равна 365!/(365^87*278!) (! - факториал). Тогда вероятность того, что хотя бы у двух человек из 87 дни рождения совпадут, равна p(87)=1-365!/(365^87*278!)
Более упрощённая общая и апроксимированная формула решения задачи для колличества участников 365 (при кол. участников >365 вероятность события равна 1) имеет вид: p(n)~1-e^(-n^2/768) (где е — математическая константа, основание натурального логарифма ~ 2.71828)
Получаем p(87)=1-е^(-87^2/768)=1-e^(-7569/768)=1-e^(-9,85546875)=1-2.71828^(-9,85546875)=1-1/2.71828^9,85546875=1-1/8103,035=1-0,000123411=0,999876589
То есть с вероятностью 99,9876589% мы можем утверждать, что из 87 человек присутсвующих на ачате найдётся хоть одна пара таких, у кого День рождения совпадают! А при n=23 вероятность совпадения равна примерно 50.7 %.
Интересно будет сравнить вероятность p (n) с вероятностью события, что в группе из 87 человек у кого-либо день рождения совпадет с днём рождения некоторого заранее выбранного человека. Эта вероятность равна
q(87)=1-((365-1)/365)^87=1-0,7876~0,21234 (~21%) что не многим лучше одного из 5 шансов. Для того, чтобы вероятность совпадения дня рождения с заданным человеком превысила 50 %, число людей в группе должно быть не менее 253. Это число заметно больше, чем половина дней в году (365/2 = 182.5); так происходит из-за того, что у остальных членов группы дни рождения так же могут совпасть между собой, и это уменьшит вероятность совпадения одного из них с днём рождения конкретного человека. К чему я веду спросите Вы? Да дело в том, что парадокс Дней рождений может быть использован в так и называемой «атаке дня рождения» (birthday attack) на криптографические хэш-функции.

[Атака "Дня рождения"]

Применя так называемый "парадокс дня рождения" к слабым-хэш функциям формулируется следующая задача:
Предположим, количество выходных значений хэш-функции Н равно n. Каким должно быть число k, чтобы для конкретного значения X и значений Y1, …, Yk вероятность того, что хотя бы для одного Yi выполнялось равенство
H (X) = H (Y) была бы больше 0,5?
Для одного Y вероятность того, что H (X) = H (Y), равна 1/n. что и мы всегда отвечаем говоря про стойкость 64, 128,160 и тд. -битных алгоритмов. т.е. соответсвенно 1/2^64, 1/2^128? 1/2^160.
Соответственно, вероятность того, что H(X)!=H(Y), равна 1 - 1/n
Если создать k значений, то вероятность того, что ни для одного из них не будет совпадений, равна произведению вероятностей, соответствующих одному значению, т.е. (1 - 1/n)k. Следовательно, вероятность, по крайней мере, одного совпадения равна 1 - (1 - 1/n)^k. Разложив в биноминальный ряд Ньютона и затем апроксимируя его мы придём к упрощённой формуле P=1 - (1 - k/n) = k/n, мы задавались вероятностью P=50%, отсюда k = n/2.
Таким образом, мы выяснили, что для m-битового хэш-кода достаточно выбрать 2^(m-1) сообщений, чтобы вероятность совпадения хэш-кодов была больше 0,5.
На практике это означает следующее, возьмём к примеру слабую хэш-функцию MySQL(64bit) всё множество её значений 2^64=18446744073709551616 вариантов. Чтоб найти совпадение с исходным паролем с вероятностью 50% нам требуется подать на вход 2^63=2^64/2=18446744073709551616/2=9223372036854775808 случайных паролей, т.е. ровно половину.
В контесте с революцией в вычисленяих на основе технологии CUDA, примем среднюю скорость вычислений одного хеша 8 000 000 000 000 п/c. на GF8600GT получим время 1152921сек.~320часов.~13 дней. Что это означает? Это означает что мы можем не искать исходный пароль, последовательно подавая на вход пароли, генерируемые простым брутфорсом (последовательно) а подавать случайное значение пароля из широкого диапазона > чем число возможных хэшей и в 50% через 13 дней непрерывного брута мы получаем хэш, который совпадёт с хэшем от исходного пароля (а может это будет и оригинальный пароль).

[Поиск коллизий]

Теперь рассмотрим следующую задачу: обозначим P (n, k) вероятность того, что в множестве из k элементов, каждый из которых может принимать n значений, есть хотя бы два с одинаковыми значениями. Чему должно быть равно k, чтобы P (n, k) была бы больше 0,5?
Число различных способов выбора элементов таким образом, чтобы при этом не было дублей, равно n(n-1) … (n-k+1)n!/(n-k)!
Всего возможных способов выбора элементов равно n^k
Вероятность того, что дублей нет, равна n!/(n-k)!n^k
Вероятность того, что есть дубли, соответственно равна 1-n!/(n-k)!n^k
Пропускаю математические выкладки, представленные тут http://www.intuit.ru/department/security/networksec/8/2.html
и приведу конечный результат: Если хэш-код имеет длину m бит, т.е. принимает 2^m значений, то k = v2m = 2^(m/2)
Подобный результат называется "парадоксом дня рождения", потому что в соответствии с приведенными выше рассуждениями для того, чтобы вероятность совпадения дней рождения у двух человек была больше 0,5, в группе должно быть всего 23 человека. Этот результат кажется удивительным, возможно, потому, что для каждого отдельного человека в группе вероятность того, что с его днем рождения совпадет день рождения кого-то другого в группе, достаточно мала.
Что это означает на практике? Снова для примера возьмём слабую хэш-функцию mySQL(64bit), в этом случае m=64, подставим значение в формулу и получаем k=2^(64/2)=2^32=4294967296
Что это означает? именно столько потребуется подать случайных паролей на вход, чтобы с вероятностью выше 50% получить совпадение хэшей от любой одной пары паролей, т.е получить с вероятностью 50% ситуацию называемой коллизия. Прикрутим скорость перебора программ на основе CUDA и получаем, что подавая на вход случайные пароли первую коллизию (а значит пару паролей, от которых хэш одинаков) мы найдём с вероятностью 50% уже на 4 294 967 296/8 000 000 000 000=0,000536870912сек.! Для сравнения посчитаем тоже самое для более стойкого алгоритма md5(128bit) учитывая более медленную скорость генерации хэшей от паролей получим следующее:
k=2^(128/2)=2^64=18446744073709551616, требуемых случайных паролей, скорость перебора 500 000 000 пасс/сек. время нахождения первой коллизии с вероятностью 50% 36893488147,5сек~10248191часов.~427008 дней~1169лет. Срок не приемлемый конечно для одного компа даже с поддержкой CUDA. Идём дальше, допустим поиск коллизии по данному алгоритму осуществляют независимо всё те же 87 ачатовцев, у пары из которых с вероятностью 99,9876589% совпадают дни рождения. Тогда вероятность того что один не нашёл коллизию за 1169лет составляет 1/2 (50%). Что не нашли двое 1/2*1/2=1/4=0,25 (25%), что не нашли трое 1/8=0,125 (12,5%) и т.д что не нашёл не один 1/2^87=6,4623485355705287099328804067966e-27, тогда вероятность того, что коллизию найдёт хоть один составит 0,99999999999999999999999999353765 (обратное событие, почти 100%)
Да, многие скажут, срок брута нериемлем, мы не долгожители и редко кто доживёт до 80 лет, неговоря о бруте такое колличество времени ))). Но есть один момент, можно сократить время поиска коллизии, допустим на месяц, уменьшив вероятность наступления данного события для одного участника. И задаться некоторым временем успешного нахождения коллизии хотя бы одним участником. Решаем задачку:
Исходные данные:
Колличество участников 87 человек.
Пусть время независимого поиска одной коллизии каждым участником 1 месяц = 30 дней = 720 часов = 2592000 сек. Задаёмся той же скоростью 500 млн. пасс/сек. для программ с поддержкой CUDA.
Считаем сколько требуется подать на вход функции хэширования случайных паролей (скорость умножаем на время) = 500 000 000 пасс/сек*2592000сек=1 296 000 000 000 000 паролей (столько же хэшей) сможет сгенерировать каждый участник за это время.
Спрашивается какова вероятность того, что хотя бы у одного участника из 87 наступит событие коллизия хэш-функции?
Формула подсчёта события, что один участник (независимо от остальных) найдёт коллизию вот:
P (n, k) > 1 - e^(-k(k-1)/n)
где n - всё множество значений хэш-функции. (2^128=3,4028236692093846346337460743177e+38)
k - число случайных паролей, подаваемых на вход. (1 296 000 000 000 000)
е - константа ~ 2.71828
Эту задачку я оставляю Вам на домашнее задание.

[Как использовать атаку "Парадокс дня рождения"?]

Вообщем-то обычно требуется восстановить по извесному хэшу изначальный пароль, а не найти любую пару паролей, у которых один и тот же хэш, поэтому в лоб применение атаки "Дня рождения" нам ничего не даёт, мы так же должны перебрать 2^127 вариантов паролей, чтоб с 50% вероятности найти совпадающий с оригинальным хэш. Но не менее, возможны различного рода атаки, основанные на "парадоксе дня рождения". Возможна следующая стратегия:
1. Атакующий создает 2^(m/2) вариантов случайных паролей, далее подготавливает такое же количество паролей, каждое из которых является поддельным и предназначено для замены исходного пароля.
2. Два набора паролей сравниваются в поисках пары, имеющих одинаковый хэш-код. Вероятность успеха в соответствии с "парадоксом дня рождения" больше, чем 0.5. Если соответствующая пара не найдена, то создаются дополнительные исходные и поддельные пароли до тех пор, пока не будет найдена пара.
3. Атакующий предлагает отправителю один вариант пароля для генерации хэша (оттиска,подписи). Эта же подпись (хэш) может быть затем присоединена к поддельному варианту для передачи получателю. Так как оба варианта имеют один и тот же хэш-код, будет создана одинаковая подпись. Атакующий будет уверен в успехе, даже не зная ключа шифрования (первого варианта сообщения, пароля и т.д.).

[Практика применения атаки "Парадокс дня рождения"]

- в разработке...
Что потребуется:
1) Генератор случайных паролей.
2) Место хранения сгенерированных пар пароль:хэш
3) Производительная видеокарта с поддержкой CUDA.
4) Программа, поддерживающая генерацию MySQL-хэшей (64 bit)
Задачи:
1) Найти коллизию(и) от любой случайной пары пасс(i):пасс(j)
2) Найти коллизию, т.е. по известному пасс1, найти пасс2, чтобы MySQL(пасс1)= MySQL(пасс2)

Заключение: используемые материалы по теме:
http://ru.wikipedia.org/wiki/Парадокс_дней_рождения
Парадокс "дней рождений" и стойкость PGP
http://www.intuit.ru/department/security/networksec/8/1.html