книги / Практическая криптография

13.6 Шифрование

263

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

Предположим, через некоторое время злоумышленнику Е стал известен ключ К (возможно, из-за сбоя какого-нибудь другого компонента системы). Приведет ли это к утечке информации о закрытом ключе пользователя А? Нет. Ключ К — это результат функции хэширования, а злоумышленник не может получить какую-либо информацию о входных данных функции хэ­ ширования на основе ее выходных данных. Следовательно, даже если зло­ умышленнику Е удастся особым образом подобрать шифрованный текст с, полученный им ключ К не предоставит никакой информации об г. Закры­ тый ключ пользователя А применялся только для вычисления г, поэтому злоумышленнику Е снова ничего не удастся узнать о закрытом ключе поль­ зователя А.

Это одно из преимуществ применения функции хэширования в функ­ ции D BCRYPT R A N D O M K E Y W ITHRSA. Предположим, что последняя возвра­ щала бы лишь значение с^е mod п. В этом случае данная функция могла бы быть использована злоумышленником для осуществления всевозможных атак. Предположим, что другая часть системы имеет слабое место, в резуль­ тате чего злоумышленник Е может узнать наименее значимый бит выходных данных. В этом случае злоумышленник может отослать пользователю А спе­ циально подобранные значения С1,С2,сз,... и получить наименее значимые биты значений с^ е, с^е, с^е, .... Полученные результаты будут обладать все­ ми видами алгебраических свойств. Вполне вероятно, что злоумышленник Е сможет извлечь из подобной ситуации что-нибудь полезное. Функция хэши­ рования ft, примененная в D E CR YPT RANDOM K EYW ITHRSA, полностью раз­ рушает математическую структуру. Знание одного бита значения К не предо­ ставит злоумышленнику Е практически никакой информации о с1^. Более того, даже знание всего значения К не принесет слишком большой пользы, так как функция хэширования не является обратимой. Таким образом, при­ менение функции хэширования делает алгоритм RSA более безопасным по отношению к сбоям остальных компонентов системы.

Описанное поведение, помимо всего прочего, является также причиной того, почему мы не проверяем, попадает ли значение г, вычисленное по за­ данному с, в интервал 0 ,..., 2* - 1. Если бы мы реализовали подобную про­

264	Глава 13. Алгоритм RSA

верку, то должны были бы обрабатывать ошибки в случае их возникновения. Поскольку поведение системы при обработке ошибок всегда отличается от по­ ведения в нормальной ситуации, вполне вероятно, что злоумышленник смо­ жет обнаружить факт возникновения ошибки. В результате у него появится функция, которая раскрывает информацию о закрытом ключе: злоумыш­ ленник Е может выбрать любое с и проверить, выполняется ли отношение с1/6mod п < 2к. Злоумышленник Е не может проверить данное свойство без помощи пользователя А, но зачем же лишний раз помогать злоумышлен­ нику, если этого можно избежать? Отказавшись от проверки условия, мы в худшем случае получим лишь бессмысленные выходные данные, а это мо­ жет произойти и при наличии проверки, поскольку с может быть повреждено таким образом, что г все равно будет попадать в нужный диапазон3*.

Небольшое замечание: существует огромная разница между раскрытием информации о случайной паре (с, с1/6) и вычислением с1//е для с, выбранного кем-то другим. Генерировать пары вида (с, с1/6) может каждый. Для этого достаточно выбрать случайное г, вычислить пару (ге,г) и затем обозначить с := ге. Ничего секретного в таких парах нет. Но, если пользователь А будет так добр, что подсчитает значение с1/6 для с, полученного от злоумышлен­ ника, последний сможет выбирать значения с некоторым специальным об­ разом, что было невозможно для случайных пар (с, с1/ 6), сгенерированных самим злоумышленником. Отсюда вывод: не следует лишний раз помогать злоумышленнику.

13.7 Подписи

Реализовать схему цифровых подписей несколько сложнее. Проблема со­ стоит в том, что сообщение тп, которое мы хотим подписать, имеет довольно четкую структуру. Допускать, чтобы эта структура перешла на числа, для которых подсчитываются корни RSA, нежелательно. Поэтому структуру со­ общения необходимо уничтожить.

Первый шаг к уничтожению структуры состоит в хэшировании сообще­ ния. Таким образом, вместо сообщения произвольной длины т будем ра­ ботать со значением фиксированной длины h(m), где h — функция хэши­ рования. Если мы используем функцию SHAd-256, то получим 256-битовый результат. Но значение п намного больше, поэтому мы не можем применять h(m) непосредственно.

3Введеиие каких бы то ии было ограничений на г не решает проблему бессмыслен­ ных выходных данных. Злоумышленник Б всегда может использовать открытый ключ пользователя А и измененную функцию E N C R Y P T R A N D O M K E Y W I T H R S A , чтобы отсылать пользователю А бессмысленные ключи в зашифрованном виде.

13.7 Подписи

265

Самое простое решение — использовать псевдослучайное отображение, которое будет “растягивать” h(m), отображая его на случайное число s из диапазона 0 ,..., та — 1. Затем подпись сообщения тпбудет вычисляться как s1/6(modта). Отображение h(m) на число по модулю та выполнить доволь­ но сложно (см. раздел 10.8). В нашем случае можно упростить проблему, отображая h(m) на случайный элемент из диапазона 0,..., 2к — 1, где к — наибольшее число, такое, что 2к < та. Числа из диапазона 0,..., 2к- 1генери­ ровать гораздо проще, поскольку для этого достаточно сгенерировать лишь к случайных бит. В нашем конкретном случае подобное решение можно ис­ пользовать без опаски, однако не применяйте его повсеместно. Существует множество ситуаций, в которых подобное упрощение разрушит безопасность всей системы.

Мы будем использовать генератор псевдослучайных чисел Fortuna, опи­ санный в главе 10, “Генерация случайных чисел”. Многие разработчики ис­ пользуют функцию хэширования Л, чтобы построить небольшой генератор случайных чисел, предназначенный специально для этой цели, но у нас уже есть хороший генератор. Кроме того, нам все равно понадобится генератор псевдослучайных чисел, чтобы выбирать простые числа для генерации клю­ чей RSA.

Для реализации схемы цифровых подписей понадобятся три функции: од­ на, чтобы отобразить сообщение т на s, вторая, чтобы подписать сообщение, и третья, чтобы проверить подпись.

ф ун к ц и я M SG T O RSAN UM BER

в х о д : та Открытый ключ RSA, модуль, по которому выполняются вычисления.

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

вы х о д : s Число по модулю та.

Создадим новый генератор псевдослучайных чисел.

Q<- IN IT IA LIZE G E N E R A TO R ()

Обновим начальное число генератора с помощью хэш-кода сообщения.

R ESEED(£?, SHAd - 256(m))

Вычислим k.

k <-	(_log2та]
x «-	P SE U D O R A N D O M DA TA (C?, |7:/8"|)

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

266 Глава 13. Алгоритм RSA

s <— х mod 2к return 5

ф ункция SIGNW ITH RSA

вход:	(n, d)	Закрытый ключ RSA для е = 3.
	тп	Сообщение, которое должно быть подписано,
выход:	а	Подпись сообщения тп.

s <- MsGToRSANuMBER(n,m) а <— s1/*5mod п

return а

Буква о- (сигма) часто применяется для обозначения цифровой подписи, поскольку это греческий эквивалент английской буквы s (signature — под­ пись). Как вычислить sl/e mod п по заданному закрытому ключу, было опи­ сано ранее.

ф ункция V E RIFYRSASIGNATURE

вход: (п, е)	Открытый ключ RSA для е = 3.
7п	Сообщение, которое было подписано,
сг	Подпись сообщения тп.

з «- MsGToRSANuMBER(n,m) assert s = i7е mod п

Разумеется, в реальных приложениях необходимо предпринимать опреде­ ленные меры, если проверка подписи покажет, что та не является подлинной. В этом примере мы просто вставили утверждение assert, чтобы указать на то, что выполнение каких-либо нормальных действий должно быть прерва­ но. Ошибка подписи должна обрабатываться так же, как и всякая другая ошибка в криптографических протоколах: это верный признак того, что си­ стема находится под нападением. Не посылайте никаких ответов (разве что без этого никак не обойтись) и уничтожьте все данные, с которыми работае­ те. Чем больше информации будет отослано, тем больше сведений появится у злоумышленника.

Аргументы в пользу безопасности цифровых подписей RSA аналогичны тем, что были высказаны относительно шифрования RSA. Если мы попро­ сим пользователя А подписать ряд сообщений m i,m 2, ... ,771*, то получим пары вида (s, s1/6), однако значения з в них будут случайными. Если функ­ ция хэширования безопасна, мы можем лишь подобрать h{m) методом проб и ошибок. Генератор случайных чисел — это тоже случайное отображение. Каждый может создавать пары (s,sl/e) для случайных значений з, поэтому даже наличие такой информации не поможет злоумышленнику фальсифи­ цировать подпись. С другой стороны, для любого конкретного сообщения тп

13.7 Подписи

267

вычислить соответствующую пару (5,sl/e) может только тот, кто знает за­ крытый ключ, так как на основе h(m) вычисляется s, а затем s[/e. Последняя операция требует знания закрытого ключа. Таким образом, каждый, кто про­ верит подпись и обнаружит, что она подлинна, будет знать, что ее должен был сгенерировать именно пользователь А.

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

Глава 14

Введение в криптографические протоколы

Криптографические протоколы описывают обмен сообщениями между двумя или несколькими участниками. Мы уже встречались с простым крип­ тографическим протоколом в главе 12, “Алгоритм Диффи-Хеллмана”.

Протоколы — это, пожалуй, наиболее сложная часть криптографии. Ос­ новная проблема реализации протоколов состоит в том, что разработчики протоколов не могут контролировать их применение. До сих пор мы раз­ рабатывали систему и имели полную власть над поведением ее компонентов. Теперь же, взаимодействуя с другими участниками, мы не сможем контроли­ ровать их поведение. Наш собеседник имеет другой набор интересов и вполне может отклониться от правил, чтобы получить для себя бблыыую выгоду. По­ этому, разрабатывая протоколы, приходится исходить из предположения, что мы имеем дело с врагом.

14.1Роли

Обычно протоколы описывают взаимодействие между пользователем А и пользователем Б или, скажем, между покупателем и продавцом. При этом названия наподобие “пользователь А”, “пользователь Б”, “покупатель” или “продавец” не обозначают конкретного человека или организацию. Они опре­ деляют роль этого человека в протоколе. Если мистер Смит захочет пооб­ щаться с мистером Джонсом, он может запустить протокол согласования ключей. При этом мистер Смит может исполнять роль пользователя А, а ми­ стер Джонс — пользователя Б, затем они могут поменяться ролями. Следует

14.2 Доверие

269

помнить, что одна и та же сущность может исполнять любую роль1. Это особенно важно при проведении анализа безопасности протокола. Мы уже рассматривали возможность осуществления атаки посредника на протокол DH. В атаке такого типа злоумышленник Е исполняет роль как пользовате­ ля А, так и пользователя Б. (Разумеется, “злоумышленник Е” — это всего лишь еще одна роль.)

14.2 Доверие

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

Существует несколько источников доверия.

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

•Репутация. В нашем обществе очень важно иметь “доброе имя". Поэто­ му все его представители — от отдельно взятого человека до крупной компании — ревностно защищают свою репутацию. Зачастую угроза широкой огласки каких-то неблаговидных поступков стимулирует их вести себя должным образом.

•Закон. Цивилизованные страны обладают хорошо развитой правовой инфраструктурой, которая поддерживает возбуждение судебных исков и наказание людей, ведущих себя неправильно. Это вынуждает нас ве­ сти себя в соответствии с законом.

•У гроза ф изической расправы. Еще одним стимулом правильного поведения является страх перед физической расправой, которой может

*В протоколах с тремя или более участниками одни и тот же человек может исполнять несколько ролей одновременно.

270	Глава 14. Введение в криптографические протоколы

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

•Взаимно-гарантированное уничтожение (m utually assured de­ struction — M A D ). Это термин времен “холодной войны”. В более мягких формах он означает угрозу нанести вред и себе, и второй сто­ роне. Если вы обманете своего лучшего друга, он может разорвать с ва­ ми отношения, что причинит боль вам обоим. Довольно часто в ситу­ ации взаимно-гарантированного уничтожения оказываются две компа­ нии, которые возбуждают встречные иски о нарушении патентов.

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

Довольно трудно вызвать доверие у противоположной стороны, общаясь по Internet. Предположим, пользователь А живет за пределами США и под­ ключается к Web-узлу ACME, у которого практически нет оснований до­ верять пользователю А; из всех механизмов доверия остается только этика. Предпринять какие-либо законные меры в отношении частных лиц, живущих за рубежом, практически невозможно и к тому же непозволительно дорого. Мы не можем навредить их репутации, угрожать им или даже поставить в ситуацию взаимно-гарантированного уничтожения.

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

Практически все компании, занимающиеся распространением товаров по телефону, почте или Internet, следуют этому правилу, требуя от покупателя, чтобы товар был оплачен прежде, чем будет доставлен к месту назначения.

14.3 Стимул

271

Понятие доверия нельзя рассматривать в черно-белых тонах: либо дове­ рять, либо не доверять. Мы доверяем разным людям в той или иной степени. Мы можем доверить хорошему знакомому на хранение 100 долларов, но ни­ как не лотерейный билет, который только что сорвал джек-пот в пять мил­ лионов. Мы доверяем банку свои деньги, но сохраняем квитанции и копии аннулированных чеков, так как не полностью доверяем администрации этого банка. Вопрос: “Вы доверяете ему?” не закончен. Он должен звучать так: “Вы доверяете ему в вопросе ХТ\

14.2.1Риск

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

Работая с криптографическими протоколами, гораздо легче думать в тер­ минах доверия, а не рисков. Тем не менее нехватка доверия — это не что иное, как риск, а последний иногда можно обрабатывать с помощью стандартных методов управления рисками, таких, как страхование. Разрабатывая прото­ колы, мы говорим о доверии. Не забывайте, однако, что бизнесмены думают и говорят в терминах рисков. Чтобы общаться с этими людьми, вам придется перестраиваться с одной точки зрения на другую.

14.3Стимул

Еще одним фундаментальным компонентом анализа криптографических протоколов является система стимулов. Каковы цели различных участников общения? Чего они хотят достигнуть? Даже в реальной жизни анализ систе­ мы стимулов позволяет сделать глубокомысленные заключения.

Каждую неделю в прессе то и дело появляются громкие заявления напо­ добие: “Последние исследования показали, что...”. Читая подобные статьи, мы сразу же задаемся вопросом: а кто оплатил эти исследования? Исследо­ вания, результаты которых свидетельствуют в пользу лица, оплатившего их, всегда подозрительны. Здесь действует несколько факторов. Во-первых, ис­ следователи знают, что хочет услышать их заказчик, и понимают, что могут получить повторный контракт, если предоставят “хорошие” результаты, а по­ тому автоматически теряют объективность. Во-вторых, заказчик исследова­ ний не собирается публиковать отрицательные отчеты, а публикация только положительных результатов приводит к еще большей потере объективности. Табачные компании не раз публиковали “научные” статьи о том, что никотин

272	Глава 14. Введение в криптографические протоколы

не вызывает привыкания. Компания Microsoft оплачивает исследования, ко­ торые “доказывают”, что открытое программное обеспечение плохое. Никогда не доверяйте исследованиям, которые свидетельствуют в пользу компании, оплатившей их.

Авторы этой книги хорошо знакомы с подобным давлением. За долгое время работы в качестве консультантов мы многократно выполняли оцен­ ку безопасности систем для коммерческих заказчиков. Мы были безжалост­ ны — большинство предоставленных нам продуктов оказывались довольно плохи — и редко давали положительные отзывы. Это отнюдь не добавля­ ло нам популярности среди заказчиков. Один из них даже позвонил Брюсу и сообщил: “Остановите работу и вышлите мне счет. Я нашел человека, кото­ рый пишет хорошие отчеты за меньшую плату”. Догадываетесь, что в данном случае скрывалось за словом “хорошие”? Единственная причина, по которой мы могли позволить себе оставаться объективными, была в том, что у нас всегда хватало работы. Если заказов мало, а исследователю нужно кормить семью, трудно устоять перед искушением наперекор собственным амбициям говорить то, что хотят от него услышать.

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

Заплатив руководящему составу компании в фондовых опционах, вы пре­ доставите им следующую систему стимулов: увеличьте цены на акции на сле­ дующие три года, и вы сорвете большой куш; уменьшите цены, и вам покажут пальцем на дверь с утешительным призом в качестве солидного выходного пособия. Этот стимул напоминает уговор: “Если выпадет орел, я выиграю много, а если решка, я выиграю немного, но все равно выиграю”; поэтому догадайтесь, как поступает большинство менеджеров? Они выбирают крат­ косрочную стратегию с высокой степенью риска. Если у менеджеров появится возможность удвоить поставленную на кон сумму, они обязательно восполь­ зуются этой возможностью, поскольку всегда получают выигрыш и никогда не платят в случае проигрыша. Если они смогут на несколько лет взвинтить цены на акции с помощью бухгалтерских штучек, то обязательно это сде­ лают, потому что всегда смогут собрать сливки и испариться, прежде чем их изобличат. Некоторым игрокам не везет, но платят по счетам все равно другие.