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

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


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


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


 
На страницу: 1, 2 След.
Комментарии
— SATtva (15/07/2008 15:17)   профиль/связь   <#>
комментариев: 11558   документов: 1036   редакций: 4118
У нас цвет отпечатка, если не изменяет мне память, строится по последним 12ти цифрам

Так и есть.
— unknown (15/07/2008 15:35, исправлен 15/07/2008 16:25)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Я дал абсолютно строгую формулу без приближений, и для её вывода мне не понадобилось ничего кроме определения вероятности и теоремы умножения/сложения вероятностей, сиречь элементарного вводного курса тервера.

...и даже без теоремы Бернулли и геометрического распределения?
— Гость (15/07/2008 20:00)   <#>
...и даже без теоремы Бернулли и геометрического распределения?

А где оно там? Даже таких умных слов не знаю.
— unknown (16/07/2008 09:22, исправлен 16/07/2008 09:26)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Пусть вероятность успеха в одном испытании = p, а неудачи соотв. q=p-1. Это всего навсего и есть распределение Бернулли.

Чем больше испытаний n, то отклонения реальной частоты успеха от идеального значения, описываемого величиной p в событиях всё меньше. (Такая самоочевидная на первый взгляд вещь и называется теоремой Бернулли)

Если p=1/n, то логично предположить, что после n испытаний, вероятность Pr того, что хотя бы в одном из них случиться p, будет очень близка к единице. Что и является следствием теоремы Бернулли.

Но Pr всё-таки не будет строго равно 1 даже после n испытаний. Всегда существует небольшая вероятность того, что во всех испытаниях выпадет только q.

Pr стремится к единице, если n стремится к бесконечности.
В этом смысл геометрического распределения.

Но этот хвост не особо существенен. Округлённо можно считать, что Pr=n – число шагов примерно равно p-1.

А если нужно посчитать, сколько нужно сделать испытаний n, чтобы достичь заданной вероятности Pr (скажем 70%), чтобы произошло хоть одно q?

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

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

Но в криптографии точными расчётами не заморачиваются, всё сокращают ещё решительнее, поэтому считают, что на подбор заданного прообраза размером 2n, именно 2n работы и потребуется.
— Гость (16/07/2008 14:43)   <#>
[offtop]
Спасибо за разъяснения.

Никогда не понимал любви народа называть простейшие формулы, непосредственно следующие из аксиом/определений, собственными именами. Ещё один классический пример – "формула Муавра". Ппц. Курс стандартного тервера не учил и не сдавал – всё в рамках общих познаний, но приходилось сдавать стохастические процессы (обощение тервера на случай величин, принимающих значения из непрерывного набора и функций). Там аккуратная теория уже на биномах, естественно, не строится, а вводится так называемая "аксиоматика Колмогорова", алгебра событий и т.д. и т.п., в общем, про это есть и в вики (секция Measure-theoretic probability theory). В модных выражениях, если не путаюсь, вероятность – это что-то типа счётно-аддитивной меры, определённой на борелевской сигма-алгебре событий (биномы неравно курят в сторонке). И плотность распределния P, к которой все так привыкли, существует далеко не всегда. Ессно, в криптографии приходится работать только с дискретными распределениями (в меру моих знаний).
[/offtop]
На страницу: 1, 2 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3