Фальсификация авторизации в PGP посредством поддельных ключей
Возникла идея следующей атаки на протокол (возможно, она уже хорошо известна, но ранее об этом на pgpru не читал). Допустим, что Ева обладает большими вычислительными мощностями (наподобие NSA). Ева может изменить способ генерации PGP-ключей на своей машине, делая их не обязательно случаными, чтобы увеличить скорость их генерации. Задача Евы состоит в том, чтобы подделать несколько последних цифр в отпечатке ключа. В предположении, что никаких слабостей в хэш-функции, выдающей отпечаток ключа, нет, легко посчитать эффективное количество ключей, которое нужно сгенерить, чтобы с существенной вероятностью получить коллизию последних цифр с истиным ключом. Согласно моим оценкам, если каждый ключ генерируется за секунду, в среднем за 136 лет удастся получить коллизию по последним 8ми цифрам (8ми значному uid'у). С учётом имеющихся знаний о вычислительных мощностях современных суперкомпьютеров, сколько понадобится времени на генерацию подобного фэйкового ключа? И аналогичный вопрос про коллизию 16тизанчного uid'а. Понятно, то подобная задача может быть и распараллелена. Даже если не рассматривать это как серьёзную атаку, сам способ загадить серверы ключей коллизионными и фэйковыми забавен, причём по моим оценкам будет не просто определить, случаен ли конкретный ключ, или генерился фэйковым алгоритмом (если в распоряжении только насколько подобных ключей).
P. S.: идея не моя, но решил дать объяву. Сильно не пинайте :)
В свете подобной атаки можно поставить вопрос о подделке цветного отпечатка ключа как здесь в комментариях (собственно, насколько это просто при такой атаке?).
комментариев: 11558 документов: 1036 редакций: 4118
Так и есть.
комментариев: 9796 документов: 488 редакций: 5664
...и даже без теоремы Бернулли и геометрического распределения?
А где оно там? Даже таких умных слов не знаю.
комментариев: 9796 документов: 488 редакций: 5664
Чем больше испытаний 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 работы и потребуется.
Спасибо за разъяснения.
Никогда не понимал любви народа называть простейшие формулы, непосредственно следующие из аксиом/определений, собственными именами. Ещё один классический пример – "формула Муавра". Ппц. Курс стандартного тервера не учил и не сдавал – всё в рамках общих познаний, но приходилось сдавать стохастические процессы (обощение тервера на случай величин, принимающих значения из непрерывного набора и функций). Там аккуратная теория уже на биномах, естественно, не строится, а вводится так называемая "аксиоматика Колмогорова", алгебра событий и т.д. и т.п., в общем, про это есть и в вики (секция Measure-theoretic probability theory). В модных выражениях, если не путаюсь, вероятность – это что-то типа счётно-аддитивной меры, определённой на борелевской сигма-алгебре событий (биномы неравно курят в сторонке). И плотность распределния P, к которой все так привыкли, существует далеко не всегда. Ессно, в криптографии приходится работать только с дискретными распределениями (в меру моих знаний).
[/offtop]