Почему шифры стойкие. I. Теоретико-информационная стойкость

Архив

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

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

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

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

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

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

Инженеры Секции безопасности телеграфной связи AT&T, где с 1914 года работал Вернам, и сами это прекрасно знали - прекрасно видели, как шесть одновременно передаваемых сообщений отчетливо разделяются на экране осциллографа. И не удивлялись тому, что клиенты, особенно солидные компании, все чаще пользуются кодовыми книгами.

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

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

Довольно быстро Вернам разработал устройство, включаемое в цепь между клавиатурой и приемопередатчиком телетайпа: принцип, который он назвал... правильно, on-line encipherment, то есть "шифрование онлайн". Впервые в практике электросвязи шифрование и расшифровка были полностью автоматизированы.

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

В 1918 году коллега Вернама инженер Лаймэн Морхауз (Lyman F. Morehouse) предложил использовать для шифрования "вторичный" ключ, генерируемый с помощью двух первичных разной длины также побитным XOR. Два трехметровых кольцевых ключа длиной 1000 и 999 символов дали бы неповторяющуюся последовательность в 999000 символов. К этому времени Секция секретности уже тесно сотрудничала с заинтересовавшимися военными, одним из которых был Джозеф Моборн (Joseph O. Mauborgne). Моборну удалось найти способ успешной атаки на шифр Морхауза, что было нетривиальным результатом (много позднее, став главой сигнальной разведки США, Моборн неоднократно подтверждал свою криптаналитическую квалификацию).

Самое длинное кольцо в мире

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

Вот и все. Дальше - история "триумфального шествия" шифра Вернама. Постепенно он начал применяться везде, где требовалась сверхсекретная коммуникация. Первыми его взяли на вооружение правительства Германии и СССР. Немцы ввели в практику заранее подготовленные ключевые блокноты с отрывными листами, которые, по использовании, можно было сразу уничтожить. Отсюда - второе название шифра Вернама: "одноразовый ключевой блокнот".

Шифр Вернама для 8-битных символов procedure VernamCharwiseEncipher ( n : integer, var plaintext, key, ciphertext : array [1..n] of char); {посимвольное шифрование массива n символов plaintext ключом key; результат возвращается в ciphertext} var i : integer; begin for i := 1 to n do ciphertext[i] := chr((ord(plaintext[i])+ord(key[i])) mod 28) end; procedure VernamCharwiseDecipher ( n : integer, var plaintext, key, ciphertext : array [1..n] of bit); {посимвольная расшифровка массива n символов ciphertext ключом key; результат возвращается в plaintext} var i : integer; begin for i := 1 to n do plainext[i] := chr((ord(ciphertext[i])-ord(key[i])) mod 28) end; Побитный "одноразовый блокнот" procedure VernamBitwiseEncipher(n : integer, var plaintext, key, ciphertext : array [1..n] of bit); {побитное шифрование массива n бит plaintext ключом key; результат возвращается в ciphertext} var i : integer; begin for i := 1 to n do ciphertext[i] := plaintext[i] Е key[i] end; procedure VernamBitwiseDecipher(n : integer, var plaintext, key, ciphertext : array [1..n] of bit); {побитная расшифровка массива n бит ciphertext ключом key; результат возвращается в plaintext} begin {процедура расшифровки совпадает с процедурой шифрования} VernamBitwiseEncipher(n, ciphertext, key, plaintext) end;

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

В отношении же абсолютной стойкости придуманного им шифра, как ни парадоксально это может нам сегодня показаться, сам Вернам чувствовал себя не вполне спокойно. По крайней мере, пари о расшифровке, предложенное им и его коллегой Бэнкрофтом Герарди (Bancroft Gherardi) своим партнерам (включая прославившегося впоследствии криптаналитика Уильяма Фридмана, William Frederick Friedman) в 1918 году, так и не было отозвано.

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

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

Имя это, конечно же, - Клод Шеннон. Спустя четыре десятка лет после пионерских разработок Вернама им были опубликованы две знаменитые работы, итожащие исследования времен Второй мировой войны: "Математическая теория связи"  [2] и "Коммуникационная теория секретных систем"  [3]. В "Математической теории..." Шеннон ввел количественную меру информации как величины, обратной энтропии. В "Коммуникационной теории..." ему удалось также ввести количественную меру секретности.

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

Шеннон доказал теорему (в "Теории связи..." она имеет номер 6), согласно которой необходимым и достаточным условием совершенной секретности является равенство полной вероятности всех ключей, продуцирующих шифровку E из открытого сообщения Mi, полной вероятности всех ключей, продуцирующих ту же самую шифровку из другого открытого сообщения Mj для любых E, i, j. Далее, Шеннон показал, что шифр Вернама соответствует этому условию.

ГИЛБЕРТ ВЕРНАМ Американский инженер Гилберт Вернам (Gilbert S. Vernam) родился в 1890 году. Он окончил Массачусетский колледж (где был президентом Ассоциации беспроволочной связи) и в 1914 году поступил на работу в AT&T в отдел телеграфной связи. Вскоре его приглашают в специальную секцию, занятую вопросами секретности телеграфной связи. Там в 1917 году Вернам изобретает первое автоматическое шифровально-дешифровальное устройство, а в следующем году, после консультаций с коллегами из отрасли и военных ведомств, предлагает прием "бесконечного ключа" - то, что мы сегодня и называем "шифром Вернама", или "одноразовым блокнотом". Через три с лишним десятка лет Клод Шеннон строго докажет абсолютную теоретико-информационную стойкость шифра Вернама. Вернам - ярчайший пример замечательного типа "инженера-предпринимателя" Прогрессивной эпохи - был, видимо, морально сломлен Великой депрессией и последовавшим рузвельтовским ползучим социализмом. После блестящей карьеры в AT&T и Международной лаборатории коммуникации (криптологического подразделения IT&TC), в начале тридцатых годов он оказался практически не у дел. В тридцатые он работает в Postal Telegraph Cable Co. (позднее слившейся с Western Union) и получает множество патентов на серьезные усовершенствования в области телеграфии. Но "печати гения", начинавшего когда-то, по воспоминаниям сослуживцев, рабочий день с вопроса: "А что мы изобретем сегодня?" - уже нет. К криптологическим идеям Вернама очень чутко отнеслись в Германии (использование "одноразовых блокнотов" - модификации шифра Вернама - введено в практику немецких дипломатов между 1921-м и 1923 гг.) и Советском Союзе, но не в США, хотя в Америке система Вернама освещалась во многих публикациях. Исправлять ошибку взялись только с началом Второй мировой войны, когда американские военные достали из-под сукна его статьи... но и тогда к самому Вернаму по какой-то причине не обратились, хотя он, работая инженером в Western Union, был занят совершенствованием телеграфной сети военно-воздушных сил США. В 1960 году человек, автоматизировавший криптографию и изобретший нераскрываемый шифр, умер, всеми забытый, от болезни Паркинсона.

Строим реализацию

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

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

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

Запись алгоритма двух вариантов шифра Вернама в паскалеобразном синтаксисе дана во врезках (в приложении к наиболее часто используемым сегодня байтовым и битовым потокам; Вернам оригинально работал с 5-битным кодом Бода - предшественником ASCII).

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

- уникальный номер ключа (в качестве такового можно, например, использовать первые n бит ключа - с вероятностью неуникальности 2-n);

- смещение в "длинной ленте", задающее подключ, форматом в [log2l]+1, где l - длина ключа;

- само сообщение, зашифрованное этим подключом.

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

Абсолютная конфиденциальность содержания сообщений при таком протоколе действительно гарантирована, пока ключевые диски остаются в тайне  [4].

Но означает ли это надежность протокола в целом? - Смотря какая "надежность" вам нужна.

КЛОД ШЕННОН Американскому ученому Клоду Шеннону (Claude Elwood Shannon) принадлежит особое место в истории прикладной математики, кибернетики, информатики и криптологии. Шеннон родился в 1916 году. После того как Шеннон получил степень магистра наук по электронике и математики в Университете Мичигана, он продолжает изучать математику в Массачусетском технологическом институте, где в 1940 году, защитив диссертацию на тему "Алгебра теоретической генетики", получает диплом доктора философии по математике. Идеи диссертации довольно неожиданно находят применение в теории релейно-контактных схем. После года работы в Институте перспективных исследований в Принстоне Шеннон идет работать в Bell Telephone Labs. В Принстоне и Bell Labs. Шеннон занят исследованиями, относящимися к области, которая впоследствии будет названа кибернетикой: он строит динамически устойчивые модели, в частности, велосипед, сохраняющий равновесие без велосипедиста, и мечтает построить такой же моноцикл. Последнее ему не удается (рассказывают, что зато Шеннон сам научился ездить на одноколесном средстве передвижения не хуже заправского циркача), и он строит электрическую мышь, находящую выход из лабиринта, - неизменную героиню всех книг по кибернетике. Во время Второй мировой войны Bell Labs. была привлечена к работам по обеспечению защиты американских военных коммуникаций. Шеннон работает в группе, занятой изучением криптоаналитических приемов, и к 1944 году создает коммуникационную теорию систем секретности. К концу сороковых ее основы были изложены в двух статьях, опубликованных в Bell Systems Technical Journal. После войны Шеннон - широко признанный как один из "отцов" кибернетики и вычислительной техники - продолжает работу в Bell Labs. (до 1972 года) и преподает в MTI (с 1957 года до своей почетной отставки в 1978 году). Лауреат многочисленных научных наград. Библиография Шеннона, включающая 127 работ, доступна на www.research.att.com/~njas/doc/shannonbib.html. Одна из двух великих работ Шеннона - A Mathematical Theory of Communication (1948 год) - также доступна онлайн: http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html. В 1993 году усилиями Нила Слоуна (Neil J. A Sloane) и Арона Уайнера (Aaron D. Wyner), работавших тогда в Bell Labs. издан девятисотстраничный сборник трудов Шеннона: Claude Shannon, Collected Papers, Piscataway: 1993.

Стойкость и надежность



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

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

"Анализ активности", или "анализ трафика" (traffic analysis), упомянутый Суворовым в качестве одного из мощнейших средств современной разведки, неспецифичен для конкретных шифров. Разработчики упускают из виду возможность этого типа атак раз за разом. Буквально три месяца назад я экспертировал архитектуру клиент-банковской системы, разработанной в одном из российских кредитно-финансовых учреждений. Достаточно простая система позволяет клиенту выполнять, в сущности, две операции: запрашивать выписку со счета и инициировать перевод средств.

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

Мелочь? - В большинстве случаев - да, однако системному архитектору, когда я указал ему на эту "щелку", показалось разумным пересмотреть спецификации и предусмотреть защиту против этого конкретного вида анализа активности  [5].

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

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

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

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

Если криптаналитик союзников знал, что сообщение нацистского агента начинается с приветствия "Heil Hitler", и "поймал" шифровку, начинающуюся с подстроки "DGTYIBWPJA", он без труда мог вычислить соответствующий кусок "одноразового блокнота": "wclnbtdefj". Это ничего бы ему не дало для расшифровки остальной части сообщения, однако он бы мог сыграть с агентом злую шутку, модифицировав этот фрагмент шифровки, например, так: "DCYTIBWPJA"  [6].

Современные криптографические алгоритмы обычно исключают "глубинную атаку" (и класс схожих атак) с помощью особых приемов, о которых - в другой раз. Однако уязвимой к ней оказалась такая сравнительно недавняя разработка Агентства национальной безопасности США, как симметричный шифр Skipjack.

Это выяснилось после рассекречивания и публикации алгоритма. Skipjack не только является американским армейским стандартом, использующимся для шифрования информации уровней "конфиденциально" и "секретно", но и был предложен в середине девяностых (в составе позорного проекта Clipper) в качестве стандартного средства обеспечения конфиденциальности коммерческой информации. Он вшит в "защищенные" телефоны и в карту Fortezza, продаваемую связанными с АНБ коммерческими поставщиками под видом шифровального устройства "гарантированной стойкости".

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

---

1 (обратно к тексту) - Практически сразу кем-то из коллег Вернама была предложена модификация устройства, использующего вместо побитного посимвольное сложение по модулю 25, то есть 32 (в телеграфном коде Бода для представления символа используется 5 бит); из-за технической сложности оно не было в ту пору реализовано.
В теории чисел суммой (разностью) по модулю n (пишется a+b (mod n)) называют остаток при делении суммы (разности) на n. От определения операции mod в большинстве систем программирования модулярная арифметика отличается тем, что разность меньшего и большего числа по положительному модулю - положительное число. Например, истинно 2-3 . 6 (mod 7) (читается: разность 2 и 3 по модулю 7 конгруэнтна 6), в то время, как на C истинно (2-3)%7==-1.
По модулю 24 вы считаете, например, когда определяете, во сколько приходит поезд, отправляющийся в 19:00 и находящийся в пути 35 часов: 19+35 . 6 (mod 24), то есть поезд прибудет в 6:00. В модулярной арифметике, как и во всяком порядочном исчислении, действуют правила коммутативности, ассоциативности и дистрибутивности, известные из курса арифметики начальной школы.
Модулярная арифметика - очень интенсивно используемый в криптологии (и в информатике) раздел теории чисел.

2 (обратно к тексту) - Claude E. Shannon, A Mathematical Theory of Communication // Bell System Tech. J., v.27, n.4 (1948), pp. 379-423, 623-656.

3 (обратно к тексту) - Claude E. Shannon, Communication Theory of Secrecy Systems // Bell System Tech. J., v.28, n.4 (1949), pp. 656-717.

4 (обратно к тексту) - Шпионы, применявшие ключ в виде бумажного "блокнота", пользуются тем преимуществом, что уже использованный фрагмент блокнота можно уничтожить, и захват оставшейся части не скомпрометирует уже переданные сообщения. Зато у шпионов жизнь тяжелее. Стримерная лента дает в этом плане фору компакт-диску (внимание: для полного уничтожения данных затирать ленту надо много раз и по особому паттерну), но стримерные приводы не так распространены, как CD, поэтому, если у вашего знакомого стоит дома стример, сообщите в ФСБ: он, вероятно, шпион!

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

6 (обратно к тексту) - Пример заимствован из недавней лекции, прочитанной в Кембридже выдающимся британским криптографом Россом Андерсоном (Ross Anderson); в нем использован вариант одноразового блокнота с использованием латинских букв одного регистра и сложения по модулю 26. Расшифруйте "злую шутку" Андерсона сами, если хотите.