Страница:
Все эти атаки объединяет то, что аналитикам известны детали алгоритма. (Единственным исключением, которое мне известно, сегодня является японский код PURPLE.) Это не просто ученый ярлык, а очень хороший механизм. Если в программах будут использовать какой-то алгоритм, то его «раскрутят» и в обратную сторону. Среди секретных когда-то алгоритмов, которые уже «раскрутили» – RC4, все алгоритмы шифрования цифровой сотовой связи, DVD– и DIVX-алгоритмы шифрования видеоизображений и алгоритм Firewire. Захватят и расшифруют даже алгоритмы, глубоко запрятанные в военном оборудовании. Примерами могут служить «Энигма» во Второй мировой войне[21] или почти все алгоритмы НАТО и Варшавского договора во времена холодной войны. (Мы их не знаем, но весьма компетентные военные занимались их расшифровкой.) Полезно предполагать, что врагу известны подробности вашего алгоритма, потому что в конечном итоге они все равно станут ему известны. Август Керхкофф первым сформулировал это положение в 1883 году: «В алгоритме нет никакой тайны, вся тайна в ключе».
В 1940-х годах Клод Шеннон ввел понятие расстояния уникальности (unicitydistance). Среди прочего, расстояние уникальности измеряет количество необходимого зашифрованного текста, позволяющее однозначно воспроизвести открытый текст. Это значение зависит и от свойств открытого текста, и от длины ключа, характерной для такого алгоритма шифрования.
Например, алгоритм RC4 зашифровывает данные в байтах. Представьте себе одну единственную букву в ASCII-кодировке в качестве открытого текста. На 26 букв приходится 256 возможных вариантов кодирования. Любой случайный ключ, если использовать его для расшифровки этого текста (буквы), с вероятностью 26/256 даст верный открытый текст. У аналитика нет никакого средства, позволяющего отличить ошибочный открытый текст от правильного.
Представьте теперь сообщение электронной почты размером 1 Кбайт. Аналитик пытается применять случайные ключи, и в конечном счете возникает открытый текст, который выглядит как сообщение электронной почты: слова, фразы, предложения, грамматика. Вероятность того, что это неправильный открытый текст, бесконечно мала.
Для стандартного англоязычного сообщения расстояние уникальности равно К/6,8, где К – это длина ключа в битах. (6,8 – степень естественной избыточности английского языка. Для других открытых текстов она будет больше или меньше, но незначительно.) Для ASCII-кода, применяемого согласно стандарту DES, расстояние уникальности составляет 8,2 байт. Для 128-битового шифра это примерно 19 байт. Таким образом, для англоязычных сообщений, длина которых превышает 19 байт, расшифрованный текст, похожий на английский, с большой вероятностью будет истинным открытым текстом. Почти такое же значение расстояния единственности имеют файлы электронных таблиц, текстовых процессоров и баз данных. (На самом деле оно может быть намного меньше, потому что форматы файлов предполагают стандартное начало файла.) Для сжатых файлов расстояние уникальности могло бы быть в два-три раза больше (но опять-таки, стандартное начало может его существенно снизить).
Отсюда мораль: «Распознать открытый текст просто, и для этого не требуется большого количества информации».
Вы можете рассматривать MAC как защищающую от вскрытия оболочку сообщения. Кто угодно может прочесть сообщение – оболочка не обеспечивает секретность. Но кто-то, кто знает ключ MAC, может удостовериться, что сообщение не было изменено. Конкретнее, MAC – это номер, который прикреплен к цифровому сообщению.
Для MAC применяют секретные ключи совместного использования, типа симметричных алгоритмов шифрования. Сначала Алиса договаривается о ключе с Бобом. Затем, когда она хочет послать Бобу сообщение, она вычисляет MAC сообщения (применяя секретный ключ) и присваивает его сообщению. У каждого сообщения есть уникальный MAC для любого возможного ключа.
Когда Боб получает сообщение, он вычисляет его MAC (опять-таки используя все тот же совместный ключ) и сравнивает его с тем значением MAC, которое прислала Алиса. Если они совпадают, то он может быть уверен в двух вещах: сообщение действительно пришло от Алисы (или от кого-то, кто знает секрет общего ключа) – потому что только применяя этот ключ, можно вычислить MAC, и это сообщение цельное и не измененное – так как MAC можно вычислить только по полному и точному сообщению. Если бы Ева (помните нашу перехватчицу?) прослушивала связь, она смогла бы прочитать сообщение. Однако если бы она попыталась изменить текст сообщения или MAC, то вычисленный Бобом MAC не был бы равен тому значению, которое он получил. Еве пришлось бы изменить сообщение, а затем изменить MAC, чтобы он был правильным для нового сообщения, но она не могла бы этого сделать, так как не знает ключа. Банки используют такую простую систему аутентификации уже несколько десятилетий.
Алиса может прибегнуть к той же уловке, чтобы установить подлинность информации, содержащейся в базе данных. Добавляя информацию в базу данных, она вычисляет MAC и хранит его вместе с информацией. Когда она извлекает информацию, то снова вычисляет MAC и сравнивает его с тем значением, которое хранилось в базе данных. Если они совпадают, то она приобретает уверенность, что никто не изменил информацию.
MAC постоянно используются в Интернете. Их применяют, например, в протоколе IPsec, чтобы гарантировать, что IP-пакеты не были изменены в промежутке между отправлением и прибытием на место назначения. Их используют во всевозможных протоколах межбанковских переводов для установления подлинности сообщений. Большинство MAC сконструированы с применением симметричных алгоритмов или односторонних хэш-функций. Например, в СВС-МАС применяется симметричный алгоритм, а в НМАС и NMAC – хэш-функции.
Они названы односторонними из-за своей математической природы. Любой может вычислить одностороннее хэш-значение чего угодно (например, текста этой книги). Однако если имеется хэш-значение этой книги, исходя из вычислений невозможно создать другую книгу с таким же значением хэш-функции или получить подлинный текст книги.
Хэш-функция также может обеспечивать аутентификацию и целостность. Если бы вы загрузили эту книгу из Интернета, у вас не было бы никакого способа узнать, написал все это я или кто-то другой все же частично изменил мои слова. Однако, если бы я дал вам в руки хэш-значение для этой книги (типичный 20-байтовый код), вы смогли бы сравнить расчетный результат с тем значением, которое дал я. Если они совпадают, то это моя книга, без изменений.
Хэш-функции широко применяются в криптографии и компьютерной безопасности. Они используются почти во всех протоколах Интернета, чтобы обрабатывать ключи, связывать последовательность событий или аутентифицировать события. Они также важны для алгоритмов цифровой подписи (подробнее об этом – позднее). Они, возможно, – наиболее полезный инструмент в коллекции шифровальщика.
В настоящее время используется целый набор односторонних хэш-функций. Стандарт на хэш-функцию SHA-1 принят правительством США. Для алгоритма безопасности хэширования (Secure Hash Algorithm) есть акронимы, и они приведены в соответствующем стандарте (Secure Hash Standard, SHS). RIPEMD-160 – это европейский алгоритм. MD4 выходит из употребления (хотя вы все еще можете его неожиданно встретить), a MD5 демонстрирует существенные недостатки, и его больше не используют для создания чего-либо нового.
Звучит нелепо? Это кажется невозможным. Если бы вы спросили шифровальщиков со всего света в 1975 году, все они сказали бы, что это невозможно. Так что можете себе представить всеобщее изумление, когда в 1976 году Витфилд Диффи и Мартин Хеллман объяснили, как это сделать. Или удивление британской разведки, когда Джеймс Эллис, Клиффорд Кок и М. Д. Уильямсон осуществили то же самое на несколько лет раньше.
Основная идея в том, чтобы использовать математическую функцию, которую просто вычислять в одном направлении и тяжело – в другом. Одна из таких функций – разложение целых чисел на множители. Если даны два числа, их легко перемножить и найти произведение. Но если дано только произведение, практически невозможно разложить число на множители и определить исходные числа. Как раз такого плана математику можно применять для создания шифрования с открытым ключом: в нее входят арифметические операции над абсолютными значениями чисел, возведение в степень и большие многоразрядные (до нескольких тысяч битов) исходные числа. Сегодня существует добрые полдюжины алгоритмов с названиями вроде RSA, Эль-Гамаль и алгоритм эллиптических кривых. (Алгоритмы, в основе которых лежит так называемая «задача о ранце», конкурировали с ними на ранних стадиях, но по прошествии 20 лет их так или иначе взломали.) Математика для каждого алгоритма своя, но концептуально они все одинаковы.
Вместо единственного ключа совместного пользования у Алисы и Боба есть два ключа: один для шифрования, а другой для расшифровки. Ключи различны, и невозможно, зная один ключ, вычислить другой. То есть если у вас есть ключ для шифрования, вы не сумеете найти ключ для расшифровки.
Вот в этом-то и есть самое интересное. Боб может создать пару таких ключей. Он может взять и обнародовать ключ для шифрования. Он может послать его друзьям, опубликовать на своем веб-сайте или поместить в телефонной книге. Алиса может найти этот ключ. Она может с его помощью зашифровать сообщение для Боба. Затем она может послать ему сообщение. Боб, используя свой ключ расшифровки (который он предусмотрительно не размещал на веб-сайте), сможет расшифровать и прочитать послание Алисы. Заметим, что Алисе не приходится встречаться с Бобом в какой-нибудь темной аллее и договариваться об общем секрете. Бобу даже не обязательно знать Алису. И, как ни странно, даже Алисе не обязательно знать Боба. Если Алиса сможет найти ключ, который Боб обнародовал, она сможет послать ему тайное сообщение, которое никто, кроме Боба, не сможет прочитать. Такое постоянно происходит с пользователями PGP; один из их ключей находится на каком-либо сервере, и тогда совершенно посторонний человек может отправить им зашифрованные сообщения. Даже если вы что-то смыслите в математике, это не менее удивительно.
Детали этого процесса содержат в себе целую кучу хитростей. Например, я не рассказал, как Боб создал открытый и закрытый ключи и как он сделал свой личный ключ секретным. (Он не может его помнить – ведь ключ состоит из более чем тысячи случайных цифр.) И я пропущу здесь рассказ о невероятно сложной задаче – как Алиса узнает, что она получила именно ключ Боба, а не какой-то старый, или неправильный, или ключ какого-либо злоумышленника. Мы вернемся к этому позднее.
А сейчас я хочу обратить ваше внимание на то, что никто не применяет шифрование с открытым ключом для кодирования сообщений. Все операционные системы используют гибридные технологии, в которых задействованы оба типа криптографии. Причина интереса к этому подходу в его эффективности. На самом деле, когда Алиса хочет послать сообщение Бобу, она зашифровывает сообщение при помощи симметричного алгоритма, используя произвольный ключ, который создает «из воздуха» (так называемый сеансовый ключ). Она зашифровывает этот произвольный ключ при помощи открытого ключа Боба, а затем отправляет вместе зашифрованный ключ и зашифрованное сообщение для Боба. Когда Боб их получает, он производит обратную операцию. При помощи личного ключа он расшифровывает произвольный симметричный ключ, а затем использует его для расшифровки сообщения.
Это может показаться сверхъестественным, но все совершенно нормально. Повторюсь, никто не использует криптографию с открытым ключом непосредственно для шифрования сообщений. Все применяют гибридные технологии. Так устроены все программы, обеспечивающие безопасность электронной почты, – PGP, РЕМ, S/MIME и любые другие. Так обеспечивается защита сообщений Веб, TCP/IP, телефонной связи и всего остального.
Как и шифрование с открытым ключом, цифровые подписи используют пару ключей: открытый и закрытый. Вы также не можете установить по одному ключу другой. Но в этом случае ключи меняются местами.
У Алисы есть открытый текст сообщения. Применяя свой закрытый ключ, она сообщение зашифровывает. Поскольку это ее личный ключ, то только им можно зашифровать сообщение абсолютно тем же способом. Таким образом, зашифрованное сообщение становится Алисиной подписью на сообщении. Открытый ключ Алисы общедоступен. Кто угодно способен достать этот ключ и расшифровать сообщение, удостоверившись таким образом, что его подписала (то есть зашифровала) Алиса. Подпись является функцией сообщения, поэтому она уникальна для сообщений: злостный фальсификатор не может снять подпись Алисы с одного документа и поместить ее на другой. Подпись – это функция личного ключа Алисы, то есть она уникальна для нее.
Конечно, реальные системы более сложны. Так же как Алиса не зашифровывает сами сообщения при помощи алгоритмов шифрования с открытым ключом (она зашифровывает только ключ сообщения), она и не подписывает непосредственно сообщение. Вместо этого она вычисляет одностороннюю хэш-функцию сообщения и затем ее подписывает. Опять же, подписывание хэш-значения на несколько порядков быстрее, и надо иметь в виду, что существует математическая проблема защиты при подписывании сообщений напрямую.
Таким образом, большинство алгоритмов цифровых подписей на самом деле не зашифровывают подписанные сообщения. Идея та же, но математическое исполнение отличается. Для того чтобы создать подпись, Алиса производит некоторые вычисления исходя из сообщения и своего личного ключа. Эта подпись прикрепляется к сообщению. Боб проделывает другие вычисления, основываясь на сообщении, подписи и открытом ключе Алисы, чтобы проверить подпись. Ева, которая не знает личного ключа Алисы, может проверить подпись, но не может подделать сообщение или полноценную подпись.
В настоящее время применяются несколько алгоритмов цифровой подписи. Наиболее популярен RSA. Алгоритм цифровой подписи американского правительства (Digital Signature Algorithm, DSA), который применяют в стандарте цифровой подписи (Digital Signature Standard, DSS), также используется часто. Вы можете иногда встретить алгоритм Эль-Гамаль. А еще существуют алгоритмы подписей, в основе которых лежит криптография эллиптических кривых; они похожи на все прочие, но в некоторых ситуациях работают эффективнее.
Хотя алгоритмы цифровой подписи с открытым ключом похожи на MAC, они лучше в одном важном нюансе. Используя MAC, Алиса и Боб применяют совместный секретный ключ для аутентификации сообщений. Если Алиса получит сообщение и проверит его, она будет знать, что сообщение пришло от Боба.
Но она не сможет доказать это правосудию. В чем можно его убедить – это в том, что письмо пришло или от Боба, или от Алисы: как-никак оба они знали ключ MAC. При помощи MAC можно убедить получателя, что письмо поступило от отправителя, но MAC нельзя использовать для убеждения третьей стороны. Цифровые подписи позволяют уверить третью сторону, решающую проблему отказа от подписи: Алиса не может отправить Бобу письмо, а позднее утверждать, что никогда его не посылала.
К несчастью, действительность такова, что все, что касается подписей, является черным или белым, как это предполагает математика. Законы о цифровых подписях существуют в законодательстве многих стран, но меня беспокоит, что они не жизнеспособны. Цифровые подписи не являются аналогом автографа (собственноручной подписи). Я расскажу об этом подробнее в главе 15.
В зависимости от того, с кем вы разговариваете, генерация случайных чисел выглядит или тривиальной, или невозможной. Теоретически это невозможно. Джон фон Нейман, отец вычислительной техники, сказал: «Любой, кто считает, что существуют арифметические методы получения случайных цифр, безусловно, грешит». Он имел в виду, что невозможно получить что-то случайное в полном смысле слова на выходе такого детерминированного зверя, как компьютер. Это правда, но, к счастью, кое-что сделать мы можем. От генератора случайных чисел нам необходимо не то, чтобы числа были действительно случайными, а чтобы их невозможно было предсказать и воспроизвести. Если у нас будут выполнены эти два условия, мы сможем достичь безопасности.
С другой стороны, если мы нарушаем эти два условия, безопасности нет. В 1994 году в казино Монреаля установили компьютерный генератор случайных чисел для лотерей. Один наблюдательный игрок, проводивший в казино очень много времени, заметил, что выигрышные номера были каждый день одни и те же. Он успешно сорвал три Джек-Пота подряд и получил 600 000 долларов. (Как следует позаламывав руки, поскрежетав зубами и расследовав все, казино заплатило выигрыш.)
Существует несколько обширных классов генераторов случайных чисел. В основе некоторых из них лежат физические процессы, которые можно считать довольно случайными. Агентство национальной безопасности любит использовать в своей аппаратуре для создания случайных чисел электрические шумы диодов. Другие возможности – счетчик Гейгера или приемники радиопомех. Одна система в Интернете использует цифровой фотоаппарат, направленный на несколько стробоскопов. В других системах применяется турбулентность воздуха в дисководах или момент поступления сетевых пакетов.
Некоторые генераторы случайных чисел отслеживают случайные движения пользователя. Программа может попросить пользователя набрать на клавиатуре большую строку произвольных символов; она может задействовать последовательность символов или даже время между нажатиями клавиш для создания случайных чисел. Другая программа запросто способна потребовать у пользователя туда-сюда подвигать мышью или похрюкать в микрофон.
Некоторые генераторы случайных чисел применяют эту введенную информацию без изменений. В других она служит затравкой (начальным числом) для математических генераторов случайных чисел. Этот прием работает лучше, если системе требуется случайных чисел больше, чем их обеспечивает ввод информации.
Какого бы происхождения ни была случайность, генератор создаст ряд случайных битов. Затем их можно использовать как криптографические ключи и для всего остального, что нужно системе.
Начнем с самого начала. Криптографический ключ – это секретное число, которое делает криптографический алгоритм уникальным для тех, кто совместно пользуется этим ключом. Если Алиса и Боб договорились об общем ключе, то при помощи алгоритма они могут тайно пообщаться. Если Ева-перехватчица не знает ключа, ей придется исследовать и ломать алгоритм.
Одна очевидная вещь, которую можно сделать, – это перепробовать все возможные ключи. Это так называемая атака «в лоб», или лобовая атака. Если длина ключа n битов, то существует 2^n всевозможных комбинаций ключей. При длине ключа в 40 бит, придется перебрать около триллиона вариантов ключей. Такая задача покажется ужасно скучной для Евы, но компьютеры неутомимы. Они лучше всех решают ужасно скучные задачи. В среднем компьютеру пришлось бы испробовать половину ключей, прежде чем он найдет правильный, то есть компьютер, который мог бы проверять миллиард ключей в секунду, потратил бы на поиски правильного 40-битового ключа примерно 18 минут. В 1998 году Electronic Frontier Foundation создала машину, которая могла атакой «в лоб» ломать DES-алгоритм. Эта машина, названная DES Deep Crack, проверяла 90 миллиардов ключей в секунду; она могла найти 56-битовый ключ DES в среднем за 4,5 дня. В 1999 году распределенный интернет-проект подбора ключей для взлома DES, distributed net (включающий в себя Deep Crack), был способен проверить 250 миллиардов ключей в секунду.
Все схемы таких взломов «в лоб» линейны: вдвое большее количество ключей потребует вдвое больше компьютерного времени. Но сложность такого взлома зависит от длины ключей экспоненциально: добавим один бит к длине ключа, и взлом «в лоб» станет в два раза сложнее. Добавим два бита – в четыре раза. Десять битов – в тысячу раз сложнее.
Сила атак «в лоб» в том, что они работают против любого алгоритма. Поскольку эта атака не касается внутренней математики алгоритма, ей все равно, что же там внутри. Одни алгоритмы могут быть быстрее других, и поэтому атака «в лоб» проходит быстрее, но длина ключа легко это перевешивает. Достаточно просто сравнить длины ключей различных алгоритмов, чтобы выяснить, какие из них более уязвимы для лобовой атаки.
В 1996 году группа шифровальщиков (включающая и меня) исследовала различные технологии, которые можно использовать для создания дешифрующих машин, действующих по принципу лобовой атаки, и пришла к выводу, что 90-битовый ключ сможет обеспечивать безопасность до 2016 года. Ключ Triple-DES состоит из 112 бит, а наиболее современные алгоритмы имеют по меньшей мере 128-битовые ключи. (Улучшенный стандарт шифрования (AES) правительства США поддерживает длины ключей 128,192 и 256 бит.) Даже машине, работающей в миллиард раз быстрее Deep Crack, потребовался бы миллион лет, чтобы перебрать 2^112 ключей и восстановить открытый текст; еще более, чем в тысячу раз, возрастает время при переходе к 128-битовому ключу. Он будет обеспечивать безопасность в течение тысячелетия.
Распознавание открытого текста
В разговоре об атаках всегда возникает один вопрос: как криптоаналитик распознает открытый текст? Ответ прост: его легко узнать, потому что он выглядит как открытый текст. Это сообщение на английском языке или файл компьютерного приложения, изображение в формате 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-байтовый код), вы смогли бы сравнить расчетный результат с тем значением, которое дал я. Если они совпадают, то это моя книга, без изменений.
Хэш-функции широко применяются в криптографии и компьютерной безопасности. Они используются почти во всех протоколах Интернета, чтобы обрабатывать ключи, связывать последовательность событий или аутентифицировать события. Они также важны для алгоритмов цифровой подписи (подробнее об этом – позднее). Они, возможно, – наиболее полезный инструмент в коллекции шифровальщика.
В настоящее время используется целый набор односторонних хэш-функций. Стандарт на хэш-функцию SHA-1 принят правительством США. Для алгоритма безопасности хэширования (Secure Hash Algorithm) есть акронимы, и они приведены в соответствующем стандарте (Secure Hash Standard, SHS). RIPEMD-160 – это европейский алгоритм. MD4 выходит из употребления (хотя вы все еще можете его неожиданно встретить), a MD5 демонстрирует существенные недостатки, и его больше не используют для создания чего-либо нового.
Шифрование открытым ключом
Помните проблему распределения ключей, о которой я упоминал в разговоре о симметричном шифровании? Как два человека могут убедиться, что у них один и тот же ключ и что они могут пользоваться алгоритмом симметричного шифрования или функцией MAC? Шифрование открытым ключом (или асимметричное шифрование) решает эту проблему. Оно позволяет вам посылать секретное сообщение людям, которых вы никогда раньше не встречали и с которыми вы не договаривались о секретном ключе. Оно допускает возможность двум людям обмениваться данными у всех на виду и в результате этого обмена получить секретные данные, которые не сможет получить кто-то, подслушивавший переговоры. Говоря в терминах физического мира, такое шифрование позволяет вам и вашему приятелю прокричать друг другу числа в кафе, битком набитом математиками, – так что, когда вы закончите, вы и ваш приятель получите одно и то же число, и никто, кроме вас двоих, совсем ничего не поймет.Звучит нелепо? Это кажется невозможным. Если бы вы спросили шифровальщиков со всего света в 1975 году, все они сказали бы, что это невозможно. Так что можете себе представить всеобщее изумление, когда в 1976 году Витфилд Диффи и Мартин Хеллман объяснили, как это сделать. Или удивление британской разведки, когда Джеймс Эллис, Клиффорд Кок и М. Д. Уильямсон осуществили то же самое на несколько лет раньше.
Основная идея в том, чтобы использовать математическую функцию, которую просто вычислять в одном направлении и тяжело – в другом. Одна из таких функций – разложение целых чисел на множители. Если даны два числа, их легко перемножить и найти произведение. Но если дано только произведение, практически невозможно разложить число на множители и определить исходные числа. Как раз такого плана математику можно применять для создания шифрования с открытым ключом: в нее входят арифметические операции над абсолютными значениями чисел, возведение в степень и большие многоразрядные (до нескольких тысяч битов) исходные числа. Сегодня существует добрые полдюжины алгоритмов с названиями вроде RSA, Эль-Гамаль и алгоритм эллиптических кривых. (Алгоритмы, в основе которых лежит так называемая «задача о ранце», конкурировали с ними на ранних стадиях, но по прошествии 20 лет их так или иначе взломали.) Математика для каждого алгоритма своя, но концептуально они все одинаковы.
Вместо единственного ключа совместного пользования у Алисы и Боба есть два ключа: один для шифрования, а другой для расшифровки. Ключи различны, и невозможно, зная один ключ, вычислить другой. То есть если у вас есть ключ для шифрования, вы не сумеете найти ключ для расшифровки.
Вот в этом-то и есть самое интересное. Боб может создать пару таких ключей. Он может взять и обнародовать ключ для шифрования. Он может послать его друзьям, опубликовать на своем веб-сайте или поместить в телефонной книге. Алиса может найти этот ключ. Она может с его помощью зашифровать сообщение для Боба. Затем она может послать ему сообщение. Боб, используя свой ключ расшифровки (который он предусмотрительно не размещал на веб-сайте), сможет расшифровать и прочитать послание Алисы. Заметим, что Алисе не приходится встречаться с Бобом в какой-нибудь темной аллее и договариваться об общем секрете. Бобу даже не обязательно знать Алису. И, как ни странно, даже Алисе не обязательно знать Боба. Если Алиса сможет найти ключ, который Боб обнародовал, она сможет послать ему тайное сообщение, которое никто, кроме Боба, не сможет прочитать. Такое постоянно происходит с пользователями PGP; один из их ключей находится на каком-либо сервере, и тогда совершенно посторонний человек может отправить им зашифрованные сообщения. Даже если вы что-то смыслите в математике, это не менее удивительно.
Детали этого процесса содержат в себе целую кучу хитростей. Например, я не рассказал, как Боб создал открытый и закрытый ключи и как он сделал свой личный ключ секретным. (Он не может его помнить – ведь ключ состоит из более чем тысячи случайных цифр.) И я пропущу здесь рассказ о невероятно сложной задаче – как Алиса узнает, что она получила именно ключ Боба, а не какой-то старый, или неправильный, или ключ какого-либо злоумышленника. Мы вернемся к этому позднее.
А сейчас я хочу обратить ваше внимание на то, что никто не применяет шифрование с открытым ключом для кодирования сообщений. Все операционные системы используют гибридные технологии, в которых задействованы оба типа криптографии. Причина интереса к этому подходу в его эффективности. На самом деле, когда Алиса хочет послать сообщение Бобу, она зашифровывает сообщение при помощи симметричного алгоритма, используя произвольный ключ, который создает «из воздуха» (так называемый сеансовый ключ). Она зашифровывает этот произвольный ключ при помощи открытого ключа Боба, а затем отправляет вместе зашифрованный ключ и зашифрованное сообщение для Боба. Когда Боб их получает, он производит обратную операцию. При помощи личного ключа он расшифровывает произвольный симметричный ключ, а затем использует его для расшифровки сообщения.
Это может показаться сверхъестественным, но все совершенно нормально. Повторюсь, никто не использует криптографию с открытым ключом непосредственно для шифрования сообщений. Все применяют гибридные технологии. Так устроены все программы, обеспечивающие безопасность электронной почты, – PGP, РЕМ, S/MIME и любые другие. Так обеспечивается защита сообщений Веб, TCP/IP, телефонной связи и всего остального.
Схемы цифровой подписи
Шифрование с открытым ключом – вещь довольно удивительная, но цифровые подписи (сигнатуры) – еще более интересный и важный инструмент. Цифровые подписи обеспечивают тот же уровень аутентификации сообщений, что и MAC. А в современном бизнесе аутентификация намного важнее секретности,Как и шифрование с открытым ключом, цифровые подписи используют пару ключей: открытый и закрытый. Вы также не можете установить по одному ключу другой. Но в этом случае ключи меняются местами.
У Алисы есть открытый текст сообщения. Применяя свой закрытый ключ, она сообщение зашифровывает. Поскольку это ее личный ключ, то только им можно зашифровать сообщение абсолютно тем же способом. Таким образом, зашифрованное сообщение становится Алисиной подписью на сообщении. Открытый ключ Алисы общедоступен. Кто угодно способен достать этот ключ и расшифровать сообщение, удостоверившись таким образом, что его подписала (то есть зашифровала) Алиса. Подпись является функцией сообщения, поэтому она уникальна для сообщений: злостный фальсификатор не может снять подпись Алисы с одного документа и поместить ее на другой. Подпись – это функция личного ключа Алисы, то есть она уникальна для нее.
Конечно, реальные системы более сложны. Так же как Алиса не зашифровывает сами сообщения при помощи алгоритмов шифрования с открытым ключом (она зашифровывает только ключ сообщения), она и не подписывает непосредственно сообщение. Вместо этого она вычисляет одностороннюю хэш-функцию сообщения и затем ее подписывает. Опять же, подписывание хэш-значения на несколько порядков быстрее, и надо иметь в виду, что существует математическая проблема защиты при подписывании сообщений напрямую.
Таким образом, большинство алгоритмов цифровых подписей на самом деле не зашифровывают подписанные сообщения. Идея та же, но математическое исполнение отличается. Для того чтобы создать подпись, Алиса производит некоторые вычисления исходя из сообщения и своего личного ключа. Эта подпись прикрепляется к сообщению. Боб проделывает другие вычисления, основываясь на сообщении, подписи и открытом ключе Алисы, чтобы проверить подпись. Ева, которая не знает личного ключа Алисы, может проверить подпись, но не может подделать сообщение или полноценную подпись.
В настоящее время применяются несколько алгоритмов цифровой подписи. Наиболее популярен RSA. Алгоритм цифровой подписи американского правительства (Digital Signature Algorithm, DSA), который применяют в стандарте цифровой подписи (Digital Signature Standard, DSS), также используется часто. Вы можете иногда встретить алгоритм Эль-Гамаль. А еще существуют алгоритмы подписей, в основе которых лежит криптография эллиптических кривых; они похожи на все прочие, но в некоторых ситуациях работают эффективнее.
Хотя алгоритмы цифровой подписи с открытым ключом похожи на MAC, они лучше в одном важном нюансе. Используя MAC, Алиса и Боб применяют совместный секретный ключ для аутентификации сообщений. Если Алиса получит сообщение и проверит его, она будет знать, что сообщение пришло от Боба.
Но она не сможет доказать это правосудию. В чем можно его убедить – это в том, что письмо пришло или от Боба, или от Алисы: как-никак оба они знали ключ MAC. При помощи MAC можно убедить получателя, что письмо поступило от отправителя, но MAC нельзя использовать для убеждения третьей стороны. Цифровые подписи позволяют уверить третью сторону, решающую проблему отказа от подписи: Алиса не может отправить Бобу письмо, а позднее утверждать, что никогда его не посылала.
К несчастью, действительность такова, что все, что касается подписей, является черным или белым, как это предполагает математика. Законы о цифровых подписях существуют в законодательстве многих стран, но меня беспокоит, что они не жизнеспособны. Цифровые подписи не являются аналогом автографа (собственноручной подписи). Я расскажу об этом подробнее в главе 15.
Генераторы случайных чисел
Случайные числа – это простой элемент криптографии, о котором меньше всего говорят, но он важен не менее, чем остальные. Почти всем системам компьютерной безопасности, в которых применяется криптография, необходимы случайные числа – для ключей, уникальных чисел в протоколах и т. п. – и безопасность таких систем часто зависит от произвольности ее случайных чисел. Если генератор случайных чисел ненадежен, вся система выходит из строя.В зависимости от того, с кем вы разговариваете, генерация случайных чисел выглядит или тривиальной, или невозможной. Теоретически это невозможно. Джон фон Нейман, отец вычислительной техники, сказал: «Любой, кто считает, что существуют арифметические методы получения случайных цифр, безусловно, грешит». Он имел в виду, что невозможно получить что-то случайное в полном смысле слова на выходе такого детерминированного зверя, как компьютер. Это правда, но, к счастью, кое-что сделать мы можем. От генератора случайных чисел нам необходимо не то, чтобы числа были действительно случайными, а чтобы их невозможно было предсказать и воспроизвести. Если у нас будут выполнены эти два условия, мы сможем достичь безопасности.
С другой стороны, если мы нарушаем эти два условия, безопасности нет. В 1994 году в казино Монреаля установили компьютерный генератор случайных чисел для лотерей. Один наблюдательный игрок, проводивший в казино очень много времени, заметил, что выигрышные номера были каждый день одни и те же. Он успешно сорвал три Джек-Пота подряд и получил 600 000 долларов. (Как следует позаламывав руки, поскрежетав зубами и расследовав все, казино заплатило выигрыш.)
Существует несколько обширных классов генераторов случайных чисел. В основе некоторых из них лежат физические процессы, которые можно считать довольно случайными. Агентство национальной безопасности любит использовать в своей аппаратуре для создания случайных чисел электрические шумы диодов. Другие возможности – счетчик Гейгера или приемники радиопомех. Одна система в Интернете использует цифровой фотоаппарат, направленный на несколько стробоскопов. В других системах применяется турбулентность воздуха в дисководах или момент поступления сетевых пакетов.
Некоторые генераторы случайных чисел отслеживают случайные движения пользователя. Программа может попросить пользователя набрать на клавиатуре большую строку произвольных символов; она может задействовать последовательность символов или даже время между нажатиями клавиш для создания случайных чисел. Другая программа запросто способна потребовать у пользователя туда-сюда подвигать мышью или похрюкать в микрофон.
Некоторые генераторы случайных чисел применяют эту введенную информацию без изменений. В других она служит затравкой (начальным числом) для математических генераторов случайных чисел. Этот прием работает лучше, если системе требуется случайных чисел больше, чем их обеспечивает ввод информации.
Какого бы происхождения ни была случайность, генератор создаст ряд случайных битов. Затем их можно использовать как криптографические ключи и для всего остального, что нужно системе.
Длина ключей
Один из простейших критериев сравнения криптографических алгоритмов – длина ключа. Пресса любит обращать на нее внимание, поскольку ее легко считать и сравнивать. Как и в большинстве случаев, когда речь идет о безопасности, реальность более сложна. Короткий ключ плох, но длинный ключ не будет хорошим автоматически. Почему это так, я расскажу в следующей главе, а сейчас лучше разъяснить понятие длины ключа и его важность.Начнем с самого начала. Криптографический ключ – это секретное число, которое делает криптографический алгоритм уникальным для тех, кто совместно пользуется этим ключом. Если Алиса и Боб договорились об общем ключе, то при помощи алгоритма они могут тайно пообщаться. Если Ева-перехватчица не знает ключа, ей придется исследовать и ломать алгоритм.
Одна очевидная вещь, которую можно сделать, – это перепробовать все возможные ключи. Это так называемая атака «в лоб», или лобовая атака. Если длина ключа n битов, то существует 2^n всевозможных комбинаций ключей. При длине ключа в 40 бит, придется перебрать около триллиона вариантов ключей. Такая задача покажется ужасно скучной для Евы, но компьютеры неутомимы. Они лучше всех решают ужасно скучные задачи. В среднем компьютеру пришлось бы испробовать половину ключей, прежде чем он найдет правильный, то есть компьютер, который мог бы проверять миллиард ключей в секунду, потратил бы на поиски правильного 40-битового ключа примерно 18 минут. В 1998 году Electronic Frontier Foundation создала машину, которая могла атакой «в лоб» ломать DES-алгоритм. Эта машина, названная DES Deep Crack, проверяла 90 миллиардов ключей в секунду; она могла найти 56-битовый ключ DES в среднем за 4,5 дня. В 1999 году распределенный интернет-проект подбора ключей для взлома DES, distributed net (включающий в себя Deep Crack), был способен проверить 250 миллиардов ключей в секунду.
Все схемы таких взломов «в лоб» линейны: вдвое большее количество ключей потребует вдвое больше компьютерного времени. Но сложность такого взлома зависит от длины ключей экспоненциально: добавим один бит к длине ключа, и взлом «в лоб» станет в два раза сложнее. Добавим два бита – в четыре раза. Десять битов – в тысячу раз сложнее.
Сила атак «в лоб» в том, что они работают против любого алгоритма. Поскольку эта атака не касается внутренней математики алгоритма, ей все равно, что же там внутри. Одни алгоритмы могут быть быстрее других, и поэтому атака «в лоб» проходит быстрее, но длина ключа легко это перевешивает. Достаточно просто сравнить длины ключей различных алгоритмов, чтобы выяснить, какие из них более уязвимы для лобовой атаки.
В 1996 году группа шифровальщиков (включающая и меня) исследовала различные технологии, которые можно использовать для создания дешифрующих машин, действующих по принципу лобовой атаки, и пришла к выводу, что 90-битовый ключ сможет обеспечивать безопасность до 2016 года. Ключ Triple-DES состоит из 112 бит, а наиболее современные алгоритмы имеют по меньшей мере 128-битовые ключи. (Улучшенный стандарт шифрования (AES) правительства США поддерживает длины ключей 128,192 и 256 бит.) Даже машине, работающей в миллиард раз быстрее Deep Crack, потребовался бы миллион лет, чтобы перебрать 2^112 ключей и восстановить открытый текст; еще более, чем в тысячу раз, возрастает время при переходе к 128-битовому ключу. Он будет обеспечивать безопасность в течение тысячелетия.