id: Гость   вход   регистрация
текущее время 18:36 28/03/2024
Автор темы: Гость, тема открыта 13/07/2008 22:27 Печать
Категории: криптография, инфобезопасность, шифрование с открытым ключом, защита email, атаки, полный перебор, человек посередине
https://www.pgpru.com/Форум/Криптография/ФальсификацияАвторизацииВPGPПосредствомПоддельныхКлючей
создать
просмотр
ссылки

Фальсификация авторизации в PGP посредством поддельных ключей


Возникла идея следующей атаки на протокол (возможно, она уже хорошо известна, но ранее об этом на pgpru не читал). Допустим, что Ева обладает большими вычислительными мощностями (наподобие NSA). Ева может изменить способ генерации PGP-ключей на своей машине, делая их не обязательно случаными, чтобы увеличить скорость их генерации. Задача Евы состоит в том, чтобы подделать несколько последних цифр в отпечатке ключа. В предположении, что никаких слабостей в хэш-функции, выдающей отпечаток ключа, нет, легко посчитать эффективное количество ключей, которое нужно сгенерить, чтобы с существенной вероятностью получить коллизию последних цифр с истиным ключом. Согласно моим оценкам, если каждый ключ генерируется за секунду, в среднем за 136 лет удастся получить коллизию по последним 8ми цифрам (8ми значному uid'у). С учётом имеющихся знаний о вычислительных мощностях современных суперкомпьютеров, сколько понадобится времени на генерацию подобного фэйкового ключа? И аналогичный вопрос про коллизию 16тизанчного uid'а. Понятно, то подобная задача может быть и распараллелена. Даже если не рассматривать это как серьёзную атаку, сам способ загадить серверы ключей коллизионными и фэйковыми забавен, причём по моим оценкам будет не просто определить, случаен ли конкретный ключ, или генерился фэйковым алгоритмом (если в распоряжении только насколько подобных ключей).


P. S.: идея не моя, но решил дать объяву. Сильно не пинайте :)
В свете подобной атаки можно поставить вопрос о подделке цветного отпечатка ключа как здесь в комментариях (собственно, насколько это просто при такой атаке?).


 
На страницу: 1, 2 След.
Комментарии
— sentaus (14/07/2008 09:43)   профиль/связь   <#>
комментариев: 1060   документов: 16   редакций: 32
Судя по текущему состоянию серверов ключей кто-то уже пытался :)
Хотя, возможно, это просто совпадения.

Здесь есть некоторая статистика по таким ключам, не знаю, насколько она полна.
http://keyserver.kjsl.com/~jha.....uplicate_keyids.html

А мера защиты против этого только одна – проверять полный отпечаток, когда подписывайте ключи и не игнорировать предупреждения программы о неверных ключах.

Цветовой идентификатор не задумывался для однозначной идентификации. Это скорее "рюшечка", учитывающая некоторые особенности психологии человека.
— SATtva (14/07/2008 09:44)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Вот по этим причинам ID ключей — это лишь средство указания, а для аутентификации всегда должен использоваться только полный отпечаток. Коллизии ID бывают и случайными просто из-за ограниченного пространства значений. (Некоторые серверы ключей ведут такую статистику. Последний раз, когда я смотрел, было зарегистрировано несколько десятков, в числе которых было даже несколько тройных коллизий. А ещё есть поддельный ключ Фила Циммермана: с его именем, с его ID, но весь отпечаток, конечно, не настоящий; группа CKT так в своё время демонстрировала опасность ID.) Короче, коллизии ID не входят в модель угрозы PGP. Об этом можете прочитать даже во "Введении в криптографию".

Методика поиска частичных коллизий хэш-значений используется в протоколе hashcash. Поскольку это вычислительно затратная операция, клиент предъявляет подсчитанный токен hashcash серверу, а тот предоставляет ему запрошенные ресурсы (скажем, отправляет письмо адресату), ведь проверить правильность токена сервер может за одну операцию. Hashcash обеспечивает защиту от DoS-атак.

Кстати, любопытства ради проверил, сколько ориентировочно времени займёт "выплавление" токена hashcash по 64 битам (как 8-значный ID) — получилось более 400.000 лет. :-) Это, конечно, среднестатистический ПК, а не суперкомпьютер, но даже если у последнего уйдёт 136 лет (без поправки на закон Мура и достижения вычислительной техники), чтобы подделать ID, который всё равно не выполняет аутентификацию, получается какое-то бесцельное расходование средств.
— unknown (14/07/2008 10:17, исправлен 14/07/2008 10:20)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Уже делали такое когда-то. Из-за ошибки в реализации, можно было действительно генерировать ключи по порядку, не случайно. Кто-то при этом получал ключи вида 0xDEADBEAF и т.д.

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

А так, да, идея давно витает в воздухе и обсуждалась где-то.

Для 8-байтного отпечатка – 264 секундных шагов = (264)/(60*60*24*365) = 584942417355 лет на подбор прообраза к заданному ключу.

Или 264/2 шагов на подбор произвольной коллизии = (232)/(60*60*24*365) = 136 лет, так и есть.

Но что даёт произвольная коллизия злоумышленнику? На серверах ключей есть какие-то 8-байтные "коллизии" отпечатков, но получены они модификацией самого ключа и ни на что не влияют. Кажется эти ключи дефектные. Фактически – это один и тот же ключ, у которого меняли поля так, что он воспринимается как разные, но с одним отпечатком.

При такой производительности брутфорса "зафлудить" серверы ключей невозможно, особенно при том что там ключ хранится в базе по полному отпечатку, ну выведется два ключа на один короткий обрезок хэша, но это сразу вызовет подозрение. К тому же сразу подозрение на то, что это ключ того, кто его таким образом и сгенерил.

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

У нас упоминалась работа, в которой рассмотрены слабости протокола хранения публичных OpenPGP ключей. И к сожалению зафлудить серверы можно гораздо более простыми и менее ресурсоёмкими методами. Через них можно даже под видом ключей mp3-файлы распространять, превратив их в полную помойку. И ещё какие-то тоже забавные способы были.
— SATtva (14/07/2008 10:44)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Но подробности бага, насколько работоспособны были полученные ключи, требовались ли какие-то условиях, чтобы их кому-то подсунуть, сейчас не вспомнить, так как давно пофиксили.

В формате ключей v3 значение ID бралось не от младших байтов отпечатка (который суть хэш-значение материала ключа), как у v4, а напрямую от младших битов n. Так что подбором изначальных p и q можно было тривиально получить нужный ID. Более того, даже отпечаток (с некоторыми оговорками) можно было подделать. Ничто из этого на работоспособности ключа не сказывалось.
— Гость (14/07/2008 11:20)   <#>
А мера защиты против этого только одна – проверять полный отпечаток

Вопрос был более конкретным: насколько легко подделать такой ключ спецслужбам, обладающим большими мощностями? Это я прикинул от балды что секунда на ключ, реально же это будет намного быстрее. Но чтобы сказать точно насколько быстрее, нужно знать, насколько быстрее совокупные выч. мощности, находящиеся в распоряжении спецслужб, по ср. с персональным ПК. Эти данные известны, но я их не знаю. Подсказать можете?

Чтоб было более наглядно: допустим, что у злоумышленника есть в распоряжении бот-сеть из 100 тысяч машин. Пусть можно генерировать фэйковый ключ за секунду. Тогда на подделку 8мизначного ида (в итоге получится не дефектный а вполне себе нормальный ключ) понадобится время порядка 12 часов. Так что атака не настолько далека от реальности... Я не зря спросил про "имеющиеся в распоряжении NSA мощности".

Это скорее "рюшечка", учитывающая некоторые особенности психологии человека.

Я, как автор идеи, понимаю :) Однако вопрос был не в том имеет ли смысл это делать, а насколько легко подделать отпечаток... Думается, что для визуального совпадения достаточно не полного совпадения последних цифр отпечатка (12 последних цифр достаточно подделать для тождественного воспроизведения цветов).

Последний раз, когда я смотрел, было зарегистрировано несколько десятков, в числе которых было даже несколько тройных коллизий.

Тупой вопрос, что сервер ключей выдаст на команду

если происходит коллизия по ID. Насколько большие коллизии (как много послених цифр совпадает) сейчас известны на практике? Есть ли коллизии по 16тизначному ID'у? Я не имею в виду "дефектные ключи" – вопрос о тех, к которым в паре известен закрытый ключ.
— unknown (14/07/2008 12:30)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
136 машино-лет это для коллизии – получаем два ключа с одинаковым отпечатком, но случайным.

А для подбора к конкретному ключу – 584942417355 машино-лет. Ну даже если их будет 100000, что с того?
— SATtva (14/07/2008 13:09)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
Но чтобы сказать точно насколько быстрее, нужно знать, насколько быстрее совокупные выч. мощности, находящиеся в распоряжении спецслужб, по ср. с персональным ПК. Эти данные известны, но я их не знаю.

Те, кому они известны, всё равно ничего не расскажут.

Тупой вопрос, что сервер ключей выдаст на команду
gpg --keyserver keyserver.domain --recv-keys 0xXXXXXXXX
если происходит коллизия по ID.

Скачает все ключи с указанным ID. (Серверы ключей, кстати, не поддерживают поиск по 16-значному ID и отпечатку, так что от неоднозначности всё равно не удастся избавиться.) А дальше что? Так или иначе, Вы должны связаться с владельцем ключа для аутентификации отпечатка или проверить доверенные подписи. Что в итоге даст подделка ID сверх того, что мы уже знаем? В любом случае, это дороже, чем MITM на проводе между Вашим ПК и сервером ключей.
— Гость (14/07/2008 21:35)   <#>
Те, кому они известны, всё равно ничего не расскажут.

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

А дальше что? Так или иначе, Вы должны связаться с владельцем ключа для аутентификации отпечатка

Прекрасно понимаю, но мой вопрос из области "любознательности" о теоретически возможных достижениях при подоборе коллизий.

136 машино-лет это для коллизии – получаем два ключа с одинаковым отпечатком, но случайным.

На слабеньком ПК (не забываем). А вообще, для такого дела можно собрать и спецхардваре, которое будет куда побыстрее...

А для подбора к конкретному ключу – 584942417355 машино-лет. Ну даже если их будет 100000, что с того?


Для 8-байтного отпечатка – 264 секундных шагов = (2^64)/(60*60*24*365) = 584942417355 лет на подбор прообраза к заданному ключу.

Вот грамотеи! Unknown, вам – кол и разжаловать в рядовые!
Итак, осваиваем теорию вероятностей.
Предполагая, что генерить ключи с упорядоченными хэшами нельзя, у нас есть корзинка с бесконечным числом шарикоф, у каждого из которых свой хэш. Допустим, мы хотим получить коллизию последних 8ми знаков отпечатка. Всего существует 16^8 разных видов отпечатков, у которых последние 8 цифр различны. Так как вероятность выбора любого из них равновероятна, вероятность опустив руку в корзинку вытянуть коллизию за один раз есть 1/их_количество, то есть 16^{-8}. Вероятность не получить коллизию за одно вытягивание равна 1-16^{-8}. Допустим, что мы вытягиваем шарики с хэшами n раз, тогда вероятности не вытянуть на каждом шаге коллизию с заданными 8мизначным идом равны, а события независимы. Вероятность одновременного осуществления независимых событий равна произведению вероятностей. Итак, вероятность не полчить коллизию за n вытягиваний равна (1-16^{-8})^n. Значит, вероятность получить коллизию за n шагов равна 1 - (1-16^{-8})^n. Зададимся характерной вероятностью, типа 70%. Сколько раз нужно вытянуть шарики с хэшем чтобы получить вероятность коллизии в 70%? Ответ – решение уравнения: 1 - (1-16^{-8})^n = 0.7. Итак, ответ равен n = ln(0.3)/ln(1-16^{-8})=5.2e+09. Аналогично, для другой вероятности P и коллизии с последними N цифрами имеем формулу: n = ln(1-P)/ln(1-16^{-N}). Для больших чисел N возникают проблемы с расчётом по этой формуле, потому можновоспользоваться приближением 1/ln(1-x) =-1/x (вспоминаем курс матана). Таким образом, очень хорошим приближением является n = -ln(1-P)/16^{-N}. В частности, для вероятности в 70% и коллизии в последних 12 и 16 цифрах отпечатка получаем, соответственно: 3.39e+14 и 2.22e+19. Ну и для коллизии всего отпечатка такая же вероятность есть 1.76e+48. Очевидно, что изменение P мало на что влияет при таких порядках. Чтобы оценить выч. возможности, существующие в мире, нужно скинуть хотя бы порядков 9 от числа нужных шагов.

Если ключи генерятся на каком-нить ПК, каждый за секунду, то для подбора 8мицифровой коллизии понадобится порядка -log(.3)/16^(-8)/3600/24/365=164 года (а не 584942417355 машино-лет, unknown!). Этот же параметр для 12значного, 16тизначного и всего отпечатка даёт, соответственно, 10 миллионов лет, 700 миллиардов лет и 5.6e+40 лет. После скидывания 9ти порядков при переходе к мировым вычмощностям получаем, что для подбора коллизии 8ми знаков нужно 5 секунд, для 12ти знаков – 4 суток, а для 16ти знаков – 700 лет и для всего отпечатка – 5.6e+31 лет. Закон Мура, ессно, не учитывался. Ввиду полученных оценок сверки 16тизначного id'а вполне достаточно вопреки тому что выше писал SATtva. В общем, тема вычисления коллизий уже поднималась на форуме.

PS: думал за меня посчитают – так пришлось всё самому считать :(( Пол дня угрохал :(
PPS: unknown'а – на пересдачу.
— Гость (14/07/2008 21:42)   <#>
Вдогонку: ещё раз подчёркиваю, что в предыдущем посте вычислялось время подбора коллизии как раз к заданному (заранее известному) ключу по последним цифрам его отпечатка, а не просто вероятность появления случайных коллизий в нагенерённых ключах.
— Гость (14/07/2008 21:50)   <#>
Что касается практического применения коллизии, возможно, есть автоматизированные решения на основе PGP, которые проверяют 8мизначный ID а не весь отпечаток...
— Гость (15/07/2008 01:43)   <#>
В принципе, у unknown'а тот же ответ, за исключением что log в виде фактора, т.е. для оценки сгодится.
— unknown (15/07/2008 09:19, исправлен 15/07/2008 12:55)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Ну выводили вы более точную формулу именно для "парадокса дней рождения", которую округлённо считают как 2(n/2).

А для "first preimage" и "second preimage" считают как 2(n), ну или 2(n-1), не принципиально.

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

There are three important attacks on hashes:

    • A "collision attack" allows an attacker to find two messages M1 and M2 that have the same hash value in fewer than 2^(L/2) attempts.
    • A "first-preimage attack" allows an attacker who knows a desired hash value to find a message that results in that value in fewer than 2^L attempts.
    • A "second-preimage attack" allows an attacker who has a desired message M1 to find another message M2 that has the same hash value in fewer than 2^L attempts.

The difference between a collision attack and either of the two preimage attacks is crucial. At the time of this writing, there are no practical preimage attacks, meaning that if your use of hashes is only susceptible to preimage attacks, even MD5

Для урезанных хэшей сохраняются все соотношения.

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

1) Если есть положительные числа m >= n, то:

mn = m(m-1)(m-2)...(m-n+1)

2) Для тех же чисел существует число Стирлинга второго рода:



означающее число способов, которыми можно разместить множество m объектов по n непустым множествам.

В проблеме классического размещения в урне есть m шаров, пронумерованных от 1 до m.
Предположим, что из урны вытаскивается n шаров по одному за раз, но с возвратом, а их номера записываются.

Вероятность того, что по крайней мере t различных шаров будут вытащены равна:



Из проблемы размещения вытекает как частный случай парадокс дней рождения.

Из урны также тащат шары. Но вероятность того, что шар с одинаковым номером вытащится повторно равна:



Поскольку мы имеем дело с большими числами и медленными алгоритмами, то считать действительно неудобно. Для ассимптотических приближений, чтобы упрощать несущественные части функции придумали понятие "О"-большое.

Если n='O'(m0.5) и m->к бесконечности, то



Это сколько раз придётся тащить пока не будет совпадения. Округлённо – просто корень квадратный.

Ну кроме законов биномиальной арифметики, надо приводить то как с O-большим принято обращаться, но принцип ясен.

Отсюда выводится парадокс дней рождения P2(365,23)=0.5 – у по крайней мере двух из двадцати трёх человек в одной комнате велика вероятность совпадения дня рождения. По тому же принципц считается сколько работы надо проделать и для нахождения случайной коллизии в хэш функциях для любой заданной вероятности.


А пересдавать мне уже к счастью ничего не надо. Можете считать, что я сижу на пенсии и подрабатываю в библиотеке ;-)
— Гость (15/07/2008 12:07)   <#>
Ну выводили вы более точную формулу именно для "парадокса дней рождения"

Я думал, что термин "парадок дней рождения" используется как раз для характеристики произвольных коллизий в наборе а никак не для вероятности отлова коллизии для заданного значения.

Можете считать, что я сижу на пенсии и подрабатываю в библиотеке ;-)

Пасёте документы с двумя буквами?! О_О))
— unknown (15/07/2008 12:24, исправлен 15/07/2008 12:52)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Я думал, что термин "парадок дней рождения" используется как раз для характеристики произвольных коллизий в наборе

Правильно. Так и есть. "Непроизвольных коллизий" не бывает. Бывают прообразы. для их нахождения и придётся проделать полную работу, а не корень квадратный.

Всего существует 16^8 разных видов отпечатков, у которых последние 8 цифр различны.

Да, я почему-то подумал и написал о 8-ми байтах, глянув на строки, которые постоянно красуются в форуме и подумал о подделке на 8 байтов с цветом ;-)

Тогда всего-то 4-байта: 0x 4B d1 2C 40

2(4*8) = 232 на всю работу по подгонке ключа.

и 216 на произвольные коллизии. Это конечно меняет дело.

Это в принципе мало.
— Гость (15/07/2008 14:36)   <#>
Вообще-то раз считаются дискретные величины то и делать это надо через биномиальные коэффициенты

Я подумаю над вышими вычислениями, но у вас сложно всё (я про бритву Оккама). Я дал абсолютно строгую формулу без приближений, и для её вывода мне не понадобилось ничего кроме определения вероятности и теоремы умножения/сложения вероятностей, сиречь элементарного вводного курса тервера. Задача о парадоксе дней рождения, хоть и тоже относится к коллизиям, изначально мною в топике вообще не поднималась, так что в итоге всё смешалось в доме Облонских.

"Непроизвольных коллизий" не бывает. Бывают прообразы.

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

Тогда всего-то 4-байта: 0x 4B d1 2C 40

У нас цвет отпечатка, если не изменяет мне память, строится по последним 12ти цифрам, а не 8ми: RRGGBBRRGGBB.
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3