id: Гость   вход   регистрация
текущее время 01:25 24/11/2017
Владелец: unknown (создано 30/09/2008 15:23), редакция от 07/03/2015 18:26 (автор: unknown) Печать
Категории: криптография, алгоритмы, протоколы, сайт проекта, статьи, разное, сообщество, личности
https://www.pgpru.com/Библиотека/Статьи/КоблитцМатематикиКриптографы
создать
просмотр
редакции
ссылки

О непростых взаимоотношениях между математикой и криптографией


Опубликовано в "Заметках американского математического общества",
том.54 N8 сентябрь 2007 года
© Нил Коблиц, профессор математики университета Вашингтона в Сиэттле
для Notices of the American Mathematical Society
Перевод © 2008 unknown

В течении первых шести сотен лет – до изобретения криптографии с открытым ключом в 1970-х годах математика, применяемая в криптографии не представляла особого интереса. Лишь в двадцатом веке криптографы уже понемногу использовали какие-либо концепции из последних областей математики. Правда математики, глядя на работы тех лет, могли найти оправдание печально известному замечанию Пола Холмса: "Прикладная математика – это плохая математика".


Были некоторые исключения. В 1940-х годах Алан Тюринг, отец современной компьютерной науки работал в широких областях криптографии и в частности показал как, используя сложные статистические техники взламывать коды; и Клод Шеннон, отец теории информации, разработавший фундамент криптологии.


В тоже самое время G.H. Hardy написал в "Математической апологии", что "и Гаусс и менее выдающиеся математики могут быть оправданы в своей радости по поводу того, что есть одна наука [теория чисел], и при любом раскладе и это в их распоряжении, особая удалённость которой от повседневной человеческой активности должна удерживать её в состоянии чистоты и благородства". Во времена Харди большинство приложений математики были военными и будучи пацифистом он радовался тому, что теория чисел изучается не для практического использования, а только из-за присущей ей эстетической привлекательности.


Этот образ теории чисел как "чистой и благородной" получил сильный удар в 1977, когда трое учёных в области компьютерных наук из Массачусетского института технологий – Рон Райвист, Ади Шамир и Лен Адлеман изобрели радикально новую криптографическую систему.
Статья Мартина Гарднера в Scientific American описывала идею RSA, раскрывая её важность и вызвала внезапный подъём популярного интереса и к криптографии и к теории чисел.


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


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


Райвист, Шамир и Адлеман изобрели хитроумный, но одновременно простой способ создать одностороннюю функцию с лазейкой, используя элементарную теорию чисел. Их конструкция основана на умножении двух простых чисел p и q для получения составного числа N = pq. Предполагается, что это односторонний процесс в свете того, что факторизация N для получения p и q очень сложная задача.


Таким образом безопасность RSA криптографии целиком основана на предположении о сложности факторизации больших целых чисел. По этой причине изобретение RSA дало огромный стимул к изучению методов факторизации целых чисел, а также методов генерации очень больших случайных простых чисел. Во времена ранних 1980-х математическая криптография была сфокусирована большей частью на этой области, к примеру Карл Померанц разработал улучшенные техники решета для исчисления индексов в алгоритмах факторизации и детерминистское близковременное доказательство простоты Адлемана-Померанца-Рамли в значениях сумм Якоби.


В несколько другом направлении Дон Копперсмит придумал алгоритм, способный найти дискретный логарифм в мультипликативной группе F_2n за время exp (n1/3+e ), который оказался намного быстрее, чем ранние методы исчисления индексов. Это также имело значение для криптографии, Поскольку Эль-Гамаль предложил альтернативу RSA-шифрованию, основанную на предположении о сложности инвертирования функции x -> gx (где значение g фиксировано) в конечном поле.


В 1984 году Хэндрик Ленстра распространил одностраничное описание нового метода, основаного на эллиптических кривых, который он разработал для факторизации больших чисел. Интеллектуальный и элегантный алгоритм был настолько прост, что я понял его с одностраничного описания, несмотря на то что анализ времени его выполнения занимал значительно больше страниц. Это был первый раз когда эллиптические кривые были использованы в криптографии и когда я читал страницу, которую мне прислал Ленстра, я внезапно почуствовал, что он поднял математическое совершенство криптографии на новый, более высокий уровень.


Вскоре после того, как я провёл один семестр в Советском Союзе, где никто не работал в открытую в области криптографии, я продолжал думать об этой теме и вскоре мне пришла в голову мысль, что эллиптические кривые возможно использовать совершенно иным способом, в отличие от применённого Ленстра, а именно сконструировать системы, основанные на трудностях проблемы нахождения дискретного логарифма на эллиптических кривых. Поскольку я никого не знал в Советском Союзе с кем я мог бы поговорить об этом, я написал письмо Эндрю Одлыжко тогда ещё в Bell Labs, описывающее мою идею использования групп эллиптичесих кривых для построения криптосистемы. Одлыжко был одним из немногих математиков, кто в то время имел серьёзные работы и в теоретических и в практических областях. В наши дни это не так необычно, когда соединяются чистая и прикладная математика, но в середине 1980-х Одлыжко был уникален в своём роде среди математиков, которых я знал лично.


Электронной почты тогда не существовало и письма между СССР и США ходили по нескольку недель в одну сторону. Так что прошёл месяц, пока я получил ответ от Одлыжко. Он сказал, что моя идея криптографии нового типа хороша и фактически в тоже самое время Виктор Миллер из IBM предложил почти тоже самое. Притягательность криптографии на эллиптических кривых (ECC) была в том, что проблема дискретного логарифма на эллиптических кривых казалась (и до сих пор кажется спустя двадцать два года) значительно более трудной проблемой, чем целочисленная факторизация.


Сперва ни Виктор, ни я не предвидели коммерческой важности ECC, мы скорее думали о ней как о замечательной теоретической конструкции. Глядя в прошлое, кажется удивительным, не то что у меня не было и мысли в коммерциализации этой идеи, а то что Виктор Миллер, работавший в IBM не думал в практическом смысле. Он даже не применил патентование, несмотря на то, что политикой IBM строго предписывается патентовать все изобретения своих сотрудников, которые только возможно, даже на самых слабых основаниях. Так вопрос о превращении ECC в коммерческий продукт остался в ожидании того, пока другие люди им не заинтересуются.


После того как я вернулся в США, я стал присутствовать на конференциях по криптографии. Наиболее значительной являлась встреча на ежегодной конференции Crypto, проходящей каждый август в Санта-Барбаре (Калифорния). В восьмидесятые я находил атмосферу Crypto освежающей и стимулирующей. Это была истинно мультидициплинарная встреча, с людьми из индустрии, правительства и академических кругов в пределах от математики и компьютерной науки до инженерного дела и бизнеса.


Существовал элемент "запретного плода" в первое десятилетие конференций Crypto. В начале восьмидесятых Агенство Национальной Безопасности (NSA) предпринимало серьёзные (но безуспешные) попытки ограничить открытые исследования в области криптографии. Поэтому основание конференции Crypto в 1981 году само по себе было вызовом.


Тональность встреч была наполнена духом свободы, отражавшим красочные и эксцентричные качества личностей некоторых из основателей и ранних исследователей в криптографии с открытым ключом. Одним из таких людей был Вит Диффи, блестящий, выдающийся и непредсказуемый либертарианец, который в 1976 году в соавторстве с Мартином Хэллманом опубликовал самую знаменитую работу в области криптографии. Диффи открыл традицию так называемых "rump session", где неформальные, непочтительные и часто юмористические презентации были нормой. Была одна реплика, после которой Диффи наложил некоторые ограничения на то, что непозволительно делать докладчикам (пустые банки из под пива бросать разрешалось, но только не полные).


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


На Crypto я встретил Скотта Вэнстоуна, математика из университета Ватерлоо, который вёл мультидисциплинарную группу, занимавшуюся реализацией улучшенных алгоритмов для арифметики конечных полей. С таким опытом они были очень хорошо подготовлены для работы над ECC. Вэнстоун и двое других профессоров из Ватерлоо, один в области математики, другой – инженерного дела, основали компанию, называемую сейчас Certicom Corporation, для разработок и маркетинга ECC.


Эллиптические кривые – не единственный вид кривых, которые могут быть использованы в криптографии. В 1989 году я предложил использовать якобиановские группы гиперэллиптических кривых. В последние годы множество исследований, особенно в Германии, было посвящено криптосистемам на гиперэллиптических кривых.


Ранним сентябрём 1998 года после получения академического отпуска от университета Ватерлоо, я получил письмо от Джо Сильвермана, математика из университета Брауна, который написал замечательную книгу – диплом-двухтомник по эллиптическим кривым. В его сообщении был описан алгоритм, позволявший решить проблему дискретного логарифма в эллиптических кривых, другими словами, взламывать эллиптическую криптографию.


Сильверман назвал свой алгоритм "xedni calculus", от обратного прочтения слова "index". Его основная идея заключалась в том чтобы выполнить те же шаги, что и в алгоритме исчисления индексов, но в обратном порядке.


Причина, по которой Сильверман считал свой алгоритм эффективным основана на глубоких и сложных связях, называемых гипотезой Бёрча и Швиннертона-Дайера. Ирония заключалась в том, что в книге, озаглавленной "Алгебраические аспекты криптографии", которую я опубликовал лишь несколькими месяцами ранее, я включил дискуссию по поводу этой гипотезы в раздел "культурный бэкграунд". Мой тон был извиняющимся для читателей, которые потратили своё время на математику, которая несмотря на большой теоретический интерес, весьма маловероятно, как я утверждал, могла бы быть применима к криптографии. Затем в течении года я интенсивно узучал атаку Сильвермана на ECC, которая основана в точности на идее, заключённой в этой гипотезе. Это показывает как неблагоразумно предсказывать какие виды математики никогда не будут использованы в криптографии.


Скотт Вэнстоун и другие из Цертикома были крайне обеспокоены по поводу алгоритма Джо Сильвермана, поскольку ECC-скептики и конкуренты, особенно люди из RSA company могли бы представить это как аргумент против использования эллиптических кривых.


Первые несколько месяцев моего годового академического отпуска были посвящены тщательному исследованию алгоритма Сильвермана. В октябре я нашёл теоретический аргумент, используя концепцию "высоты" точек, который показывал, что для очень-очень больших групп эллиптических кривых xedni-приближение будет крайне неэффективно. Тем не менее, с такой генеральной линией аргументации я не мог определить размер для которого алгоритм становится непрактичным. Это оставляло почву для предположений о том, что хотя и с малой вероятностью, алгоритм не будет совсем бессилен против кривых, размер которых укладывается в диапазон, используемый в криптографии.


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


В целях ответа на критический вопрос об эффективности xedni для практического диапазона эллиптических кривых, я работал с мультидисциплинарной группой молодых математиков и учёных в области компьютерных наук из центра прикладных криптографических исследований Ватерлоо, особенно с Эдлин Теск, Андреасом Штейном и Майклом Якобсом. Мы были на постоянной связи с Джо Сильверманом, который давал нам подсказки по поводу того, как быстро тестировать его алгоритм. В итоге после достаточного количества вычислений в середине декабря, Сильверман согласился, что алгоритм непрактичен. Фактически – это даже преуменьшение, алгоритм вероятно медленнее, чем казалась проблема нахождения дискретного логарифма в эллиптических кривых.


Тем не менее, это было элегантной идеей и изучение xedni было стимулирующим проектом. Предпринятая Сильверманом атака на криптографию эллиптических кривых проиллюстрировало возрастающую роль в использовании арифметической алгебраической геометрии в криптографии с открытым ключом.


В 1990 году другой пример большого усовершенствования математических методов криптографии – это предложенный Джерардом Фреем метод спуска Вейля для поиска дискретных логарифмов эллиптических кривых. Субэкспоненциальные алгоритмы для дискретных логарифмов в гиперэллиптических кривых высшего порядка уже были ранее предложены Адлеманом и Хуангом и идея Фрея состояла в том, чтобы перенести проблему дискретного логарифма с эллиптической кривой на гиперэллиптическую кривую высшего порядка. Предложение Фрея изучали Galbraith, Gaudry, Hess, Menezes, Smart, Teske и другие и было показано, что данный алгоритм может быть наиболее быстрым, но лишь в малом числе случаев.


Прогресс также происходил в отыскании очень быстрых методов подсчёта числа точек в случайно сгенерированных эллиптических кривых. Первый шаг в этом направлении был сделан Шуфом, который использовал деление многочленов. Впоследствии были созданы лучшие алгоритмы, основанные на модулярных формах и p-адических техниках.


Одним из признаков объема количества исследований посвящённых эллиптическим кривым в последнии годы является являются ежегодные конференции ECC (которых на данный момент прошло уже 12, см. http://www.cacr.math.uwaterloo.ca).


Совершенно новый вид криптографии на эллиптических кривых стал создаваться около 2000 года в соответствии с идеями Antoine Joux, Dan Boneh, Matt Franklin. Он возник из того, что парные отображения Вейля и Тэйта на эллиптических кривых, которые ранее были невозможны (или неэффективны) замечательно подошли для личностной криптографии (где открытым ключом может быть например e-mail адрес) и сверхкоротких цифровых подписей. Криптография на парных отображениях стала активной областью исследований; в июле 2007 года в Японии состоялась первая из серии конференций, посвящённая этопу типу криптографии.


Несмотря на эти удивительные примеры применения математики в криптографии, есть и обратная сторона, фактически две обратные стороны. Они являются предметом рассмотрения оставшейся части статьи.


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


В конце 1980-х NSA (АНБ) осознало, что оно пошло по неверному пути, пытаясь враждовать с математическим сообществом в прежние годы и агенство хотело поправить отношения. В академических кругах лучший способ укрепить свои позиции – это давать деньги. Таким путём они пришли к системе грантов, которая стала главным источником финансирования в некоторых областях, таких как теория чисел.


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


В начале 1990 года я получил предложение от АНБ по финансированию конференции, посвящённой модулям Дринфелда. Конференция выглядела хорошей идеей и моя рецензия была в целом позитивной. Однако тон части предложения насторожил меня. В разделе "Эффект конференции на конкурентоспособность американских математиков" автор допустил разделение области исследований между американскими и "неамериканскими" математиками, аргументируя это тем, что это повысит конкурентоспособность первых.


Я прокомментировал:


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

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


В то самое время как математики пытаются запрыгнуть в убегающий вагон крипто, криптографы открыли мощь, которую аура математики несомненно имеет в ситуациях конкуренции. Они начали доказывать математические теоремы, которые бы доказывали безопасность их систем; с помощью такой идеи можно убеждать непосвящённых, что система 100% безопасна. Это вторая "тёмная сторона" взаимоотношений между математикой и криптографией, когда каждая из двух групп ищет способы эксплуатировать статус другой группы в своих интересах. Перед подробным рассмотрением такого использования (или злоупотребления) математики более детальным образом, я хотел бы прокомментировать противоречие между исследовательскими культурами в математике и криптографии.


В 1996 году я был председателем программного комитета конференции Crypto. Для тех, кто является специалистом по математике это стрессовая ситуация. Около двух третей представленных работ были доставлены курьерской почтой за 48 часов до окончательного срока. Многие видимо были написаны наспех и были полны опечаток. Один автор прислал мне только нечётные страницы. Некоторые нарушили правило анонимности (политику двойных рецензий вслепую). Некоторые нарушили правила, которые им были присланы. И в большинстве случаев работы были малооригинальны: там были малозначительные улучшения по сравнению с тем что автор уже публиковал год назад или это была незначительная модификация чьей-то другой работы.


В некоторых случаях ситуация становилась ещё более плохой при отправке работ в электронном виде. Альфред Менезис, глава программного комитета Crypto 2007 сказал мне, что из 197 представленых работ, 103 пришли за двенадцать часов до окончания срока, а 35 пришли в самый последний час.


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


Математические кафедры обычно верят, что:


Гипотеза. Для развития математики лучше, чтобы кто-либо публиковал одну выдающуюся работу за n лет, чем n почти ничего нестоящих работ за один год.


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


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


В течении предыдущих лет я и Альфред Менезис написали серию статей с критикой подраздела криптографии, называемого доказуемая безопасность (см. filehttp://eprint.iacr.org/2004/152.pdf, filehttp://eprint.iacr.org/2006/229.pdf, http://eprint.iacr.org/2006/230.pdf). Несмотря на большое количество просмотров и в целом положительную оценку, не все приветствовали нашу работу в этом направлении. Многие специалисты по теоретической криптографии были возмущены нашим вторжением в их область.


В 1980-х казалось, что все криптографы рады видеть приток математики. Двадцать лет спустя появляется впечатления, что некоторые из них хотят чтобы мы убирались обратно.


Идея "доказуемой безопасности" состоит в том. чтобы дать строгое математическое доказательство, которое даёт условные гарантии безопасности криптографического протокола. Оно условно, так как имеет типичную форму "наш протокол защищён против атаки X, что обеспечивается тем, что проблема Y вычислительно сложна".


Здесь слово "протокол" означает специфическую последовательность шагов, которую люди осуществляют в конкретном криптографическом приложении. С первых лет криптографии с открытым ключом двух пользователей системы "A" и "B" именовали "Алиса" и "Боб". Так что описание протокола может идти так: "Алиса посылает Бобу..., затем Боб отвечает в виде, затем Алиса шлёт ответ в виде..." и так далее.


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


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


Изучение литературы по доказуемой безопасности для математиков, таких как Менезис и я, нелегко по многим причинам. Наиболее очевидно, что теоремы доказуемой безопасности подходят только к атакам определённого вида и ничего не говорят о более изощрённых атаках, которые могут быть не включены в теорему. Более того, результат условен в строгом смысле. В отличие от математиков, где условные теоремы обычно означают что-то вроде "Допустим что гипотеза Римана верна..." (что в большинстве случаев означает, что несомненно так и есть), в криптографии условность имеет вид "допустим, что никто не смог найти улучшенный алгоритм для решения определённой математической проблемы" – и это на уровне чьих-то догадок. История не связана с последним типом допущений. Например, в конце 1980-хх, начале 1990-хх разработка метода решета числового поля для факторизации модулей числа N в RSA драматическим образом снизила время исполнения алгоритма исчисления индексов с exp((log N)1/2+e) до exp((log N)1/3+e).


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


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


В 1994 году два ведущих специалиста в области доказуемой безопасности Михир Бэллэр и Филип Рогуэй предложили основанный на RSA метод шифрования, названный OAEP ("O" означает "оптимальный" – самое злоупотребляемое слово в нашем гиперболизированном мире хай-тека). Они придерживались взгляда, что доказательство безопасности должно быть достаточно детализировано так чтобы можно было дать конкретные гарантии для определённых длин ключей и выбора параметров. Отчасти из-за того, что OAEP сопровождался доказательством безопасности, он был принят в качестве нового стандарта для Visa и MasterCard. Однако всё обернулось так, что выявилось ошибочность доказательства, что спустя семь лет раскрыл Виктор Шоуп. Это вызвало скандал и заставило многих людей задуматься о контроле качества работ по доказуемой безопасности.


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


Во многих отношениях более поразительный чем OAEP был случай недавнего ажиотажа вокруг "улучшенного" протокола согласования ключей, созданного Уго Кравчиком. В феврале 2005 года Кравчик, работающий в IBM и являющийся ведущим исследователем в области доказуемой безопасности прислал работу на Crypto 2005, в которой утверждал, что нашёл уязвимости в Менезис-Кью-Вэйнстоун (MQV) системе согласования ключей. Он заменил эту систему на модифицированную версию (HMQV), про которую он утверждал, что она более эффективна и доказуемо безопасна. Если его утверждения были правильны, то это бы вызвало большое замешательство не только для Менезиса и его соавторов, но и АНБ, которое лицензировало MQV от Цертикома и эксперты которого тщательного его изучили.


Кравчик не послал свою работу Менезису или другим создателям MQV перед представлением, что является стандартной практикой в научном мире. Что мне кажется ещё более скандальным, так это то, что никто из программного комитета Crypto 2005 также не сделал этого. Очевидно, что они гнались за скорейшим принятием работы только после поверхностного прочтения. Когда Менезис получил копию работы, уже после того как она была принята программным комитетом, он тотчас же сказал, что так называемые уязвимости в протоколе MQV, которые Кравчик перечислил в своей работе, основывались на неверном толковании или на ничтожных теоретических моментах, не имеющих практической ценности.


Более важно то, что Менезис нашёл аргументы данной работы ошибочными. Кравчик утверждал, что модифицированная система согласования ключей увеличит свою эффективность без проведения дополнительной проверки безопасности (называемой "валидацией публичного ключа"), которая была добавлена в MQV для предотвращения известных атак. У него было "доказательство" безопасности, которое дало ему уверенность в этом. Но Менезис быстро нашёл, что несомненно HMQV уступает протоколу MQV перед теми же самыми атаками, которые возможны на MQV, если в него не включить дополнительную проверку безопасности. После того как стало ясно, что некоторые выводы теорем Кравчика были ошибочны, Менезис стал читать "доказательство" внимательнее, пока не нашёл вопиющий изъян в аргументации.


И Кравчик, и референты из программного комитета были загипнотизированы "доказательством", так что они пошли против здравого смысла. Каждый кто работает в криптографии должен очень внимательно подумать перед отбрасыванием проверочных шагов, предназначенных для предотвращения проблем с безопасностью. Конечно кто-то с опытом и экспертными навыками Кравчика мог бы никогда и не допустить такой оплошности, если бы он не был слишком самоуверен в своих "доказательствах" безопасности. Также как и многие другие гиперболизированные идеи – противорадиационные укрытия в 1950-х, противоракетная защита в 1980-х – "доказательства" безопасности криптографических протоколов часто дают фальшивую уверенность, ослепляющую людей перед реальной опасностью.


В нашей первой работе по поводу доказуемой безопасности, Менезис и я критиковали терминологию:


Есть два неудачных смысла слова "доказательство", которые пришли из математики и делают это слово нежелательным в дискуссиях по поводу безопасности криптографических систем. Первое – это идея о 100% верности. Большинство людей не работающих в соответствующей специальности думают что "теорема", которая "доказана" – это нечто такое, что должно быть принято без вопросов.
Второй смысл – это запутанная, технически очень сложная последовательность шагов. С психологической и социологической точки зрения "доказательство теоремы" имеет устрашающий смысл: это что-то такое, что кроме элиты из узких специалистов никто не может понять в деталях, чтобы высказать сомнения. Таким образом, "доказательство", это нечто такое о чём неспециалисту лучше вообще не думать и читать об этом не нужно.
Слово "аргумент", которое мы здесь предпочитаем, имеет совершенно другие смысловые значения. Аргумент – это что-то, что может быть широко воспринято. И также серьёзный убедительный аргумент не обязан быть 100% определяющим. В противоположность "доказательству теоремы" – "аргумент, подтверждающий утверждение" внушает нечто, что для любого достаточно образованного человека оставляет возможность для понимания и возникновения вопросов.

Менезис и я также исследовали некоторые менее значительные проблемы интерпретации результатов доказуемой безопасности. Даже если доказальство корректно, оно часто маскирует очень большую "ширину зазора". Это значит, что редукционистский аргумент, описывающий атаку на протокол должен быть повторён миллионы раз для решения трудной вычислительной задачи. В этом случае практические гарантии, которых он достигает очень непрочные. Менезис нашёл некоторые экстремальные примеры из таких "плохо подогнанных" проблем в нескольких очень известных работах по генераторам случайных чисел. Из одной работы следовало что если вы аккуратно следуете аргументам авторов с рекоммендованными параметрами безопасности, то всё что они доказали, так это то, что атакующему потребуется 10-40 наносекунд для взлома системы. Это меньше времени за которое свет успевает пройти 1 микрон.


Вот что стало происходить, когда стали делать рекоммендации по выбору параметров на основе ассимптотических теорем. Эта теорема гласит, что если N стремится к бесконечности, вы можете безопасно генерировать O(log log N) псевдослучайных бит, каждый раз когда вы выполняете извлечение корня квадратного по модулю составного числа N. ("Безопасно" означает в данном случае, грубо говоря то, что никто не сможет различить последовательность, генерируемую алгоритмом от истинно случайных чисел за разумное время исполнения алгоритма). Тем не менее, как я отмечал по поводу дискуссии о методе исчисления индексов Джо Сильвермана, это ошибочное использование асимптотических результатов для практических гарантий безопасности. Точнее, есть необходимость провести детальный анализ с использованием реалистичных диапазонов параметров. Это часто намного трудее (и так было для xedni), провести этот конкретный анализ, вместо того чтобы доказать асимптотическую теорему и иногда прийти к выводам, на которые мы не надеялись.
В случае генератора псевдослучайных чисел анализ (если подразумевается что log2 (log2 N) битов извлекаются на каждой итерации, как рекомендовано) приведёт к абсурдно низкому значению времени, которое потребуется атакующему, чтобы успешно атаковать генератор.


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


Член редакционной колегии, который критиковал нашу статью был Одед Голдрейх из института Вейцмана, который является ведущим учёным Израиля в области компьютерных наук и высшем именем (некоторые сказали бы the top-name) в теоретической криптографии.
Когда он не смог воспрепятствовать принятию нашей статьи в журнал "Криптология" он разместил на сервере электронных публикаций по криптографии 12-страничное эссе, озаглавленное "О постмодернистской криптографии". в котором набрасывался на нас с философских позиций (см. http://eprint.iacr.org/2006/461 ). Он обвинял меня и Менезиса в "постмодернизме" и "реакционности", поскольку наш критицизм доказуемой безопасности "играет на руку оппонентам прогресса".


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


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


В действительности, то что произошло с Моделью Случайного Оракула, напоминает нам библейскую историю о Бронзовом Змее, которая воспроизведена ниже. (см. Numbers (21:4-8) и 2 Kings (18:4). В течении скитаний народа израилева по пустыне их вождь и пророк Моисей получил указание от Господа по созданию "огненного змея", как символа исцеляющего людей от укуса змия-искусителя (который был ранее послан Господом как наказание за некий первородный грех). Спустя несколько веков бронзовый змей, сотворённый Моисеем, стал объектом идолопоклонства. Это привело к тому, что праведный царь Иезикииль (сын Ахаза) дал указ разбить бронзового змея на куски. Подчеркнём, что царский указ состоял в том, чтобы разрушить объект, созданный по прямой инструкции Господа, поскольку этот объект стал фетишем. Более того, этот объект перестал служить целям, ради которых он был создан. Эта история иллюстрирует процесс, который происходит, когда божественная вещь становится фетишем и что происходит в таком случае... Ради истинного порядка вещей для нас было бы хорошо разрушить Модель Случайного Оракула.

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


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


Но больше чем я испытывал беспокойство от обвинений Голдрейха и остальных, я ободрён тем, что по крайней мере они показали, что люди обратили внимание.


Криптография более волнительнаяя вещь, чем просто академическая область исследований. Однажды я слышал докладчика из АНБ, который жаловался на университетских исследователей, которые бесцеремонно продвигают непротестированные криптосистемы. Он отметил, что если в реальном мире ваша криптография потерпит крах, вы потеряете миллионы долларов или ваш секретный агент будет убит. В академических кругах, если вы напишете о криптосистеме и спустя несколько месяцев найдёте способ её взлома, у вас будет две новые работы, которые вы сможете добавить в своё резюме!


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

fileОткрытое письмо редактору заметок американского математического общества


Уго Кравчик. Исследовательский центр IBM T.J. Watson.
2 сентября 2007 года.

Уважаемый редактор!


После прочтения статьи Нила Коблица в последнем номере "Заметок AMS", я считаю необходым ответить на некоторые неверные и вводящие в заблуждение комментарии, сделанные Коблицем в данной статье. Это включает в себя вопиющие попытки дискредитировать целую область криптографии, основанной на теории сложности, в особенности её важный вклад, который она привносит в практику криптографии. Эта статья также содержит персональный выпад против моей работы и моего поведения, особенно в отношении разработки и анализа HMQV протокола, который я не могу проигнорировать.


Что касается фактов, правдивая история HMQV протокола представляет собой грандиозный пример пользы и уместности теоретической криптографии в реальном мире, в полной оппозиции к тезисам Коблица и именно на этом я хочу сфокусировать свои комментарии по поводу работы над HMQV.


Основой этой работы послужил анализ, проведённый мной в 2004 году с помощью формальных инструментов, разработанных в предыдущие годы, протокола Менезиса-Кью-Вэйнстоуна (MQV), одной из самых эффективных схем согласования ключей в литературе и широко задокументированной в криптографических стандартах. Результаты моего анализа состояли из двух частей. Во первых протокол MQV, будучи основанным на некоторых удивительных идеях, не мог быть доказуемо безопасным в используемой мной формальной модели. Более того, эти аналитические уязвимости выливались в актуальные недостатки безопасности протокола (некоторые из которых были известны до моей работы). Во вторых, и это вклад моей работы, я модифицировал протокол MQV в новый протокол, называемый HMQV, который сохранял исключительную производительность оригинального протокола, но теперь имел чётко определённый набор правил безопасности полностью охватываемых формальным анализом.


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


В своей попытке объявить мои результаты ошибочными (и вместе с этим в более широком подходе "доказуемую безопасность"), Коблиц утверждает, что если результаты моей работы и последующее преимущество HMQV над MQV правильны, это должно было вызвать большое замешательство авторов MQV и даже АНБ, лицензировавшего протокол. Действительно, результаты были и есть правильные (с поправками, данными Менезисом, которые не меняют результаты и значение работы существенным образом) и здесь нет места для недовольства. В противоположность этому, MQV протокол – это замечательная и значительная часть работы.


Это естественно, и потребовалось 10 лет (MQV был создан в 1995), чтобы улучшить наше понимание разработки и анализа протоколов, особенно в таких молодых и живых областях как наша. Протокол HMQV использует все идеи и интуицию, которые являются базисом MQV, но интерпретирует и оптимизирует его на передовом уровне знаний 2005 года. Это совершенно новый тип фундаментального понимания, достигаемый за счёт "доказуемой безопасности", которую Коблиц так неистово отрицает.


В небольшом объёме этого письма невозможно изложить технические подробности, для того чтобы подтвердить вышеприведённые мнения ясным и конкретным образом. Интересующихся читателей я предлагают свериться с моей работой, которая была размещена после публикации на http://eprint.iacr.org/2005/176. Я не модифицировал работу после её оригинальной публикации, но я добавил предисловие, отсылающее к изъяну в одном доказательстве, отмеченном Альфредом Менезисом. В результате необходимы поправки только к некоторым вариантам протокола, но это не меняет никаким значительным образом ни результаты, ни значение работы, ни по отношению к её доказательной силе, ни по отношению к значительному практическому преимуществу HMQV.


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


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


 
Много комментариев (18) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3