Еще более действенной является атака с помощью избранного открытого текста (chosen-plain text attack). При такой атаке криптоаналитик имеет возможность выбрать сообщение, которое после этого зашифровывают. Затем он получает зашифрованное сообщение и восстанавливает ключ. Атаки этого рода срабатывали против немецких шифров: союзники сознательно допускали утечку определенной информации для того, чтобы получить зашифрованный текст, или провоцировали сообщения о событиях в городах с уникальными названиями, служащие особенно хорошими шпаргалками. Эти атаки хорошо срабатывают и против некоторых систем, использующих смарт-карты, в результате чего злоумышленники получают возможность помещать на карту нужную им информацию.
Все эти атаки объединяет то, что аналитикам известны детали алгоритма. (Единственным исключением, которое мне известно, сегодня является японский код PURPLE.) Это не просто ученый ярлык, а очень хороший механизм. Если в программах будут использовать какой-то алгоритм, то его «раскрутят» и в обратную сторону. Среди секретных когда-то алгоритмов, которые уже «раскрутили» – RC4, все алгоритмы шифрования цифровой сотовой связи, DVD– и DIVX-алгоритмы шифрования видеоизображений и алгоритм Firewire. Захватят и расшифруют даже алгоритмы, глубоко запрятанные в военном оборудовании. Примерами могут служить «Энигма» во Второй мировой войне[21] или почти все алгоритмы НАТО и Варшавского договора во времена холодной войны. (Мы их не знаем, но весьма компетентные военные занимались их расшифровкой.) Полезно предполагать, что врагу известны подробности вашего алгоритма, потому что в конечном итоге они все равно станут ему известны. Август Керхкофф первым сформулировал это положение в 1883 году: «В алгоритме нет никакой тайны, вся тайна в ключе».
Распознавание открытого текста
В разговоре об атаках всегда возникает один вопрос: как криптоаналитик распознает открытый текст? Ответ прост: его легко узнать, потому что он выглядит как открытый текст. Это сообщение на английском языке или файл компьютерного приложения, изображение в формате JPEG или база данных в каком-нибудь приемлемом формате. Когда вы смотрите на расшифрованный файл, он похож на что-нибудь вам известное. Когда вы смотрите на зашифрованный файл или файл, расшифрованный с применением неправильного ключа, он выглядит как полная тарабарщина. Человек или компьютер могут понимать эту разницу.
В 1940-х годах Клод Шеннон ввел понятие расстояния уникальности (unicitydistance). Среди прочего, расстояние уникальности измеряет количество необходимого зашифрованного текста, позволяющее однозначно воспроизвести открытый текст. Это значение зависит и от свойств открытого текста, и от длины ключа, характерной для такого алгоритма шифрования.
Например, алгоритм RC4 зашифровывает данные в байтах. Представьте себе одну единственную букву в ASCII-кодировке в качестве открытого текста. На 26 букв приходится 256 возможных вариантов кодирования. Любой случайный ключ, если использовать его для расшифровки этого текста (буквы), с вероятностью 26/256 даст верный открытый текст. У аналитика нет никакого средства, позволяющего отличить ошибочный открытый текст от правильного.
Представьте теперь сообщение электронной почты размером 1 Кбайт. Аналитик пытается применять случайные ключи, и в конечном счете возникает открытый текст, который выглядит как сообщение электронной почты: слова, фразы, предложения, грамматика. Вероятность того, что это неправильный открытый текст, бесконечно мала.
Для стандартного англоязычного сообщения расстояние уникальности равно К/6,8, где К – это длина ключа в битах. (6,8 – степень естественной избыточности английского языка. Для других открытых текстов она будет больше или меньше, но незначительно.) Для ASCII-кода, применяемого согласно стандарту DES, расстояние уникальности составляет 8,2 байт. Для 128-битового шифра это примерно 19 байт. Таким образом, для англоязычных сообщений, длина которых превышает 19 байт, расшифрованный текст, похожий на английский, с большой вероятностью будет истинным открытым текстом. Почти такое же значение расстояния единственности имеют файлы электронных таблиц, текстовых процессоров и баз данных. (На самом деле оно может быть намного меньше, потому что форматы файлов предполагают стандартное начало файла.) Для сжатых файлов расстояние уникальности могло бы быть в два-три раза больше (но опять-таки, стандартное начало может его существенно снизить).
Отсюда мораль: «Распознать открытый текст просто, и для этого не требуется большого количества информации».
Коды аутентификации сообщений
Коды аутентификации сообщений (Message authentication codes или MACs) – это следующий базисный элемент, о котором мы поговорим. Они не обеспечивают секретность, но гарантируют аутентификацию и целостность. Они дают уверенность, что сообщение пришло именно от того человека, который обозначен как автор (это аутентификация), и что сообщение по пути не изменилось (а это целостность).
Вы можете рассматривать MAC как защищающую от вскрытия оболочку сообщения. Кто угодно может прочесть сообщение – оболочка не обеспечивает секретность. Но кто-то, кто знает ключ MAC, может удостовериться, что сообщение не было изменено. Конкретнее, MAC – это номер, который прикреплен к цифровому сообщению.
Для MAC применяют секретные ключи совместного использования, типа симметричных алгоритмов шифрования. Сначала Алиса договаривается о ключе с Бобом. Затем, когда она хочет послать Бобу сообщение, она вычисляет MAC сообщения (применяя секретный ключ) и присваивает его сообщению. У каждого сообщения есть уникальный MAC для любого возможного ключа.
Когда Боб получает сообщение, он вычисляет его MAC (опять-таки используя все тот же совместный ключ) и сравнивает его с тем значением MAC, которое прислала Алиса. Если они совпадают, то он может быть уверен в двух вещах: сообщение действительно пришло от Алисы (или от кого-то, кто знает секрет общего ключа) – потому что только применяя этот ключ, можно вычислить MAC, и это сообщение цельное и не измененное – так как MAC можно вычислить только по полному и точному сообщению. Если бы Ева (помните нашу перехватчицу?) прослушивала связь, она смогла бы прочитать сообщение. Однако если бы она попыталась изменить текст сообщения или MAC, то вычисленный Бобом MAC не был бы равен тому значению, которое он получил. Еве пришлось бы изменить сообщение, а затем изменить MAC, чтобы он был правильным для нового сообщения, но она не могла бы этого сделать, так как не знает ключа. Банки используют такую простую систему аутентификации уже несколько десятилетий.
Алиса может прибегнуть к той же уловке, чтобы установить подлинность информации, содержащейся в базе данных. Добавляя информацию в базу данных, она вычисляет MAC и хранит его вместе с информацией. Когда она извлекает информацию, то снова вычисляет MAC и сравнивает его с тем значением, которое хранилось в базе данных. Если они совпадают, то она приобретает уверенность, что никто не изменил информацию.
MAC постоянно используются в Интернете. Их применяют, например, в протоколе IPsec, чтобы гарантировать, что IP-пакеты не были изменены в промежутке между отправлением и прибытием на место назначения. Их используют во всевозможных протоколах межбанковских переводов для установления подлинности сообщений. Большинство MAC сконструированы с применением симметричных алгоритмов или односторонних хэш-функций. Например, в СВС-МАС применяется симметричный алгоритм, а в НМАС и NMAC – хэш-функции.
Односторонние хэш-функции
Односторонние (однонаправленные) хэш-функции напоминают цифровые отпечатки пальцев: небольшие фрагменты данных, которые могут служить для идентификации достаточно больших цифровых объектов. Это общедоступные функции, у них нет никаких секретных ключей.
Они названы односторонними из-за своей математической природы. Любой может вычислить одностороннее хэш-значение чего угодно (например, текста этой книги). Однако если имеется хэш-значение этой книги, исходя из вычислений невозможно создать другую книгу с таким же значением хэш-функции или получить подлинный текст книги.
Хэш-функция также может обеспечивать аутентификацию и целостность. Если бы вы загрузили эту книгу из Интернета, у вас не было бы никакого способа узнать, написал все это я или кто-то другой все же частично изменил мои слова. Однако, если бы я дал вам в руки хэш-значение для этой книги (типичный 20-байтовый код), вы смогли бы сравнить расчетный результат с тем значением, которое дал я. Если они совпадают, то это моя книга, без изменений.
Хэш-функции широко применяются в криптографии и компьютерной безопасности. Они используются почти во всех протоколах Интернета, чтобы обрабатывать ключи, связывать последовательность событий или аутентифицировать события. Они также важны для алгоритмов цифровой подписи (подробнее об этом – позднее). Они, возможно, – наиболее полезный инструмент в коллекции шифровальщика.
