бит

56 бит

Теоретический расчет затрат на проведение атак методом тотального перебора на криптографические ключи разной длины всегда существенно отличается от того, с чем криптоаналитики сталкиваются на практике при покупке или разработке суперкомпьютеров для ведения такого рода атак. Объясняется это тем, что одни сделанные допущения оказываются весьма далеки от реальности, в то время как другие факторы просто не принимаются во внимание. В данном случае Диффи, Винер и другие посчитали, что при создании специализированного суперкомпьютера для атаки методом тотального перебора будут использоваться заказные микросхемы ценой не более 10 долл. По оценкам АНБ, такие микросхемы стоят, как правило, в 100 раз дороже. У АНБ вызвало сомнение и допущение о том, что вне зависимости от алгоритма шифрования, лишь длина ключа определяет сложность криптоаналитической атаки. Кроме того, при составлении таблицы не были учтены затраты на научно-исследовательские и опытно-конструкторские работы, которые для первого экземпляра суперкомпьютера обычно составляют не менее 10 млн долл. Не были также приняты во внимание расходы на приобретение компьютерной памяти.

Из сказанного можно сделать весьма важный вывод. Если кто-то очень захочет узнать использованный вами ключ, ему нужно всего лишь потратить достаточное количество денег. Поэтому определяющей является стоимость зашифрованной вами информации. Если цена ей в базарный день — около 2 долл., вряд ли кто-то решится потратить 1 млн, чтобы ее заполучить. Но если прибыль от прочтения вашей шифровки составляет 100 млн долл.. — берегитесь! Единственным утешением может послужить тот факт, что с течением времени любая информация очень быстро устаревает и теряет свою ценность.

Биотехнология

Предположим такую ситуацию: с использованием генной инженерии удалось вывести особую породу травоядных динозавров. Их нарекли "криптозаврами", поскольку они состоят из клеток, которые могут проверять криптографические ключи. Шифрованный и соответствующий открытый теки передаются в клетки криптозавра с помощью магнитооптических средин. Найденный ключ выводится специальными клетками, способными перемещаться в пределах тела криптозавра. Поскольку динозавр в среднем состоит из 2 14 клеток, то при условии, что каждая из них успевает проверить 1 миллион ключей в секунду, на поиск 64-битного ключа уйдет не более 1 с.

Для этой же цели можно использовать клетки морских водорослей. Например, на площади в 500 км2 и на глубине в 1 м их можно разместить в количестве 1023. Если каждая из них будет обрабатывать 1 млн ключей в секунду. то 128-битный ключ будет вскрыт менее чем за сотню лет. Шифрованный и открытый тексты передаются водорослям с помощью спутника, а сигналом о нахождении искомого ключа служит изменение окраски водорослей вокруг клетки, отыскавшей этот ключ. За советами по разведению морских водорослей криптоаналитики могут обратиться на биологический факультет ближайшего университета.

Длина открытого ключа

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

Конечно, разложение большого числа на множители — задача трудная. Однако сразу возникает резонный вопрос, насколько трудная. К несчастью для криптографов, сложность ее решения уменьшается. И что еще хуже, эта сложность падает значительно более быстрыми темпами, чем ожидалось ранее. Например, в середине 70-х годов считалось, что для разложения на множители числа из 125 цифр потребуются десятки квадрильонов лет. А всего два десятилетия спустя с помощью компьютеров, подключенных к сети Internet удалось разложить на множители число из 129 цифр. Этот прорыв стал возможен благодаря тому, что за прошедшие 20 лет были не только предложены новые, более быстрые, методы разложения на множители больших чисел, но и возросла производительность используемых компьютеров.

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

А почему, спрашивается, не взять 10000-битный ключ 9 Ведь тогда отпадут все вопросы, связанные со стойкостью асимметричного алгоритма шифрования с открытым ключом, основанном на разложении большого числа па множители. Но дело в том, что обеспечение достаточной стойкости шифра не является единственной заботой криптографа. Имеются дополнительные соображения, влияющие на выбор длины ключа, и среди них — вопросы. связанные с практической реализуемостью алгоритма шифрования при выбранной длине ключа.

Чтобы оценить длину открытого ключа, будем измерять доступную криптоаналитику вычислительную мощь в так называемых мопс-годах, т. е. количеством операций, которые компьютер, способный работать со скоростью 1 миллион операций в секунду, выполняет за год. Допустим, что хакер имеет доступ к компьютерным ресурсам общей вычислительной мощью 10000 мопс-лет, крупная корпорация — 107 мопс-лет, правительство — 109 мопс-лет. Это вполне реальные цифры, если учесть, что при реализации упомянутого выше проекта разложения числа из 129 цифр его участники задействовали всего 0,03% вычислительной мощи Internet, и чтобы добиться этого, им не потребовалось принимать какие-либо экстраординарные меры или выходить за рамки закона.

Предположим еще, что вычислительная мощь возрастает в 10 раз каждые 5 лет, а метод, который используется для разложения больших чисел на множители, позволяет это делать с трудоемкостью, указанной в табл. 6.3.

Длина секретного ключа

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

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

Подсчитать сложность атаки методом тотального перебора достаточно просто. Если ключ имеет длину 64 бита, то суперкомпьютер, который может опробовать 1 млн ключей за 1 с, потратит более 5 тыс. лет на проверку всех возможных ключей. При увеличении длины ключа до 12cS бит, этому же суперкомпьютеру понадобится 10 25 лет, чтобы перебрать все ключи. Вселенная существует всего-навсего 10'° лет, поэтому можно сказать, что 10- — это достаточно большой запас надежности для тех, кто пользуется 128-5ишымп ключами.

Однако прежде чем броситься спешно изобретать криптосистему с длиной ключа в 4 Кбайт, следует вспомнить о сделанном выше предположении, а именно: используемый алгоритм шифрования идеален в том смысле, что вскрыть его можно только методом тотального перебора. Убедиться в этом на практике бывает не так просто, как может показаться на первый взгляд. Криптография требует утонченности и терпения. Новые сверхсложные криптосистемы при более внимательном рассмотрении зачастую оказываются очень нестойкими. А внесение даже крошечных изменений в стойкий криптографический алгоритм может существенно понизить его стойкость. Поэтому надо пользоваться только проверенными шифрами, которые известны уже в течение многих лет, и не бояться проявлять болезненную подозрительность по отношению к новейшим алгоритмам шифрования, вне зависимости от заявлений их авторов об абсолютной надежности этих алгоритмов.

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

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

Генерация ключей

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

Генерация случайных и псевдослучайных последовательностей

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

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

Криптографические ключи

Глава 6. Криптографические ключи

Длина секретного ключа Однонаправленные функции Длина открытого ключа Работа с ключами Генерация случайных и псевдослучайных последовательностей Генерация ключей Нелинейные ключевые пространства Передача ключей Проверка подлинности ключей Контроль за использованием ключей Обновление ключей Хранение ключей Запасные ключи Скомпрометированные ключи Продолжительность использования ключа Уничтожение ключей

Хранение ключей

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

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

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

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

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

Какой длины должен быть ключ

Криптоаналитическая атака против алгоритма шифрования обычно своим острием бывает направлена в самое уязвимое место этого алгоритма. Например, для организации шифрованной связи часто используются криптографические алгоритмы как с секретным, так и с открытым ключом. Такая криптосистема называется гибридной. Стойкость каждого из алгоритмов, входящих в состав гибридной криптосистемы, должна быть достаточной, чтобы успешно противостоять вскрытию. Например, глупо применять симметричный алгоритм с ключом длиной 128 бит совместно с асимметричным алгоритмом, в котором длина ключа составляет всего 386 бит. И наоборот, не имеет смысла задействовать симметричный алгоритм с ключом длиной 56 бит вместе с асимметричным алгоритмом с ключом /шиной 1024 бита.

В табл. 6.5 перечисляются пары длин ключей для симметричного и асимметричного криптографического алгоритма, при которых стойкость обоих алгоритмов против криптоаналитической атаки методом тотального перебора приблизительно одинакова. Из данных, приведенных в табл. 6.5, например, следует, что если используется симметричный алгоритм со 112-битным ключом, то вместе с ним должен применяться асимметричный алгоритм с 1792-битным ключом. Однако на практике ключ для асимметричного алгоритма шифрования обычно выбирают несколько более стойким, чем для симметричного, поскольку с помощью первого защищаются значительно большие объемы информации и на более продолжительный срок.

Количество мопс-лет для разложения на множители

Количество мопс-лет для разложения на множители

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

Контроль за использованием ключей

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

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

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

Криптографически надежные псевдослучайные последовательности

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

Нелинейные ключевые пространства

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

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

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

Например, блочный алгоритм шифрования с длиной блока 64 бита и длиной ключа 128 бит может использовать "составной" ключ из 192 бит. Тогда вероятность случайно использовать стойкий ключ будет достаточно мала — всего 2 -64 .

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

Обновление ключей

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

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

Однонаправленные функции

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

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

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

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

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

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

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

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

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

Пароль

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

Пароль следует выбирать достаточно длинным, чтобы полученный в результате его преобразования ключ был случайным. Из теории информации известно, что в предложении на английском языке каждая буква содержит примерно 1,3 бита информации. Тогда, чтобы получить 64-бтный ключ, пароль должен состоять примерно из 49 букв, что соответствует английской фразе из 10 слов.

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

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

Передача ключей

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

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

Упоминавшийся выше американский стандарт ANSI X9.17 определяет две разновидности ключей. Ключи шифрования данных используются для зашифрования сообщений, отправляемых по каналам связи. Ключи шифрования ключей применяются для зашифрования других ключей, которые предназначены для передачи получателям этих шифрованных сообщении. Ключи шифрования ключей передаются по каналам связи, исключающим подслушивание. Например, с помощью курьеров. Однако, поскольку делать это приходится значительно реже, чем посылать ключи шифрования данных, такой способ передачи ключей абонентам сети связи вполне пригоден для использования на практике.

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

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

С ростом количества абонентов сети связи применять подход, рекомендуемый стандартом ANSI X9.17, становится все трудней и трудней. Если n человек захотят обмениваться шифрованными сообщениями, общее число переданных ими ключей составит п(п-1)/2. При n =1000 потребуется почти 500 тыс. пересылок ключей между абонентами, что может вылиться в серьезную проблему. В этом случае лучше производить рассылку ключей из единого центра (назовем его центром распределения ключей, сокращенно — ЦРК).

Плохие ключи

Когда отправитель сам выбирает ключ, с помощью которого он шифрует свои сообщения, его выбор обычно оставляет желать лучшего. Например, Петр Сергеевич Иванов скорее предпочтет использовать в качестве ключа Ivanov, чем &7)g\*. И вовсе не потому, что он принципиально не желает соблюдать элементарные правила безопасности. Просто свою фамилию Иванов помнит гораздо лучше, чем абракадабру из шести произвольно взятых символов. Однако тогда сохранить свою переписку в тайне ему не поможет и самый стон кий алгоритм шифрования в мире, особенно если используемые Ивановым ключи всегда совпадают с именами его ближайших родственников и записывает он эти ключи на клочках бумаги, которые наклеивает на компьютер. В ходе хорошо организованной атаки методом тотального перебора квалифицированный криптоанатитик не будет опробовать все ключи последовательно, один за другим. Он сначала проверит те из них, которые хоть что-то значат для Иванова. Такая разновидность атаки методом тотального перебора наливается товарной атакой, поскольку в ходе нее противник использует словарь наиболее вероятных ключей. В этот словарь обычно входят:

Имя, фамилия, отчество, инициалы, год рождения и другая личная информация, имеющая отношение к данному человеку. Например, при словарной атаке против Петра Сергеевича Иванова в первую очередь следует проверить PSI, PSIPSI, PIVANOV, Pivanov, psivanov, peteri, pete I, IvanovP, peterivanov, Peter-Ivanov и т. д. Словарная база данных, составленная из имен людей, героев мультфильмов и мифических животных, ругательств, чисел (как цифрами, так и прописью), названий художественных фильмов, научно-фантастических романов, астероидов, планет и цветов радуги, общепринятых сокращении и т. д. В общей сложности для одного конкретного человека такая база данных насчитывает более 60 тыс. словарных единиц. Слова, которые получены путем внесения различных изменений в словарную базу данных, составленную на предыдущем этапе. Сюда относятся обратный порядок написания слова, замена в нем латинских буки о, l, z, s на цифры 0 , 1, 2 и 5 соответственно, использование слова во множественном числе и т. д. Это даст дополнительно еще около миллиона словарных единиц для опробования в качестве возможного ключа к шифру. Слова, полученные с помощью замены строчных букв на заглавные. Такой замене в принципе может подвергаться любое число букв. Например. вместе со словом Ivanov будут проверяться слова iVanov, ivAnov, ivaNov, ivanOv, ivanoV, IVanov, IvAnov, IvaNov, IvanOv, IvanoV и т. д. Однако. вычислительная мощь современных компьютеров позволяет проверять только одно-, двух- и трехбуквенные замены строчных букв на заглавные. Слова на различных иностранных языках. Хотя компьютерные пользователи в основном работают с англоязычными операционными системами (DOS, UNIX, Windows и другими), существуют локализованные версии распространенных операционных систем, в которых допускается использование другого языка. Это означает, в качестве ключа на вход программы шифрования может быть подана любая фраза на родном языке ее пользователя. Следует также учитывать, что ключ может быть транслитерирован с любого языка (например, с русского или китайского) на английский и затем в таком виде введен в программу шифрования. Пары слов. Поскольку количество вероятных пар слов, из которых может состоять криптографический ключ, слишком велико, на практике криптоаналитики обычно ограничиваются словами из трех и четырех букв.

По-настоящему случайные последовательности

Последовательность называется no-настоящему случайной, если ее нельзя воспроизвести. Это означает, что если запустить генератор по-настоящему случайных последовательностей дважды при одном и том же входе, то на его выходе получатся разные случайные последовательности. Основная трудность состоит в том, чтобы суметь отличить случайную последовательность от неслучайной. Если несколько раз зашифровать строку символов с помощью криптографического алгоритма, соответствующего ГОСТ 28147-89, то получится последовательность, очень напоминающая по-настоящему случайную. Чтобы доказать ее неслучайность, другого способа, кроме аренды АНБ соответствующих вычислительных мощностей и программы вскрытия. не существует. Однако вряд ли ваше предложение об аренде будет воспринято там всерьез.

Продолжительность использования ключа

Любой ключ должен использоваться в течение ограниченного периода времени. Тому есть несколько причин:

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

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

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

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

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

Программная атака

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

В мире имеется огромное количество компьютеров (по оценкам экспертов, в 1996 г. их число достигло 200 млн), которые, чтобы не простаивать, могли бы опробовать ключи. Эксперимент, проведенный в начале 1997 г., показал, что таким способом за две недели можно вскрыть 48-битный ключ. И хотя этот ключ был найден методом тотального перебора после проверки чуть более половины всех возможных ключей, полученный результат впечатляет, поскольку в ходе атаки одновременно использовались не более 5 тысяч компьютеров из существующих 200 миллионов, а в общей сложности в атаке оказались задействованными лишь 7 тысяч компьютеров.

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

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

При более тонком подходе вирус, обнаруживший ключ, выдаст на экран компьютера информацию вида:

В ВАШЕМ КОМПЬЮТЕРЕ ОБНАРУЖЕНА СЕРЬЕЗНАЯ ОШИБКА!

ПОЖАЛУЙСТА, ПОЗВОНИТЕ ПО ТЕЛЕФОНУ (095)123-45-67

И ЗАЧИТАЙТЕ ОПЕРАТОРУ СЛЕДУЮЩЕЕ 48-БИТОВОЕ ЧИСЛО:

хххххххх ххххххх ххххххх ххххххх ххххххх ххххххх

ПЕРВОМУ, КТО СООБЩИТ ОБ ЭТОЙ ОШИБКЕ, ГАРАНТИРОВАНО

ВОЗНАГРАЖДЕНИЕ В РАЗМЕРЕ 100 (СТА) ДОЛЛАРОВ.

Если вирусу удастся заразить 10 млн компьютеров, каждый из которых станет проверять хотя бы 1 тыс. ключей в секунду, то 56-битный ключ будет найден менее чем через 3 месяца. Дополнительно придется раскошелиться на подкуп производителей антивирусных программ, однако к компьютерной криптографии, о которой сейчас идет речь, эта проблема никакого отношения не имеет.

Проверка подлинности ключей

Как Иванову убедиться в том, что полученные им ключи были действительно переданы Петровым, а не противником, который притворился Петровым? Если Петров отдает ключи Иванову с глазу на глаз, то сделать это довольно легко. Однако если Петров присылает ключи с курьером, то Иванову придется положиться на честность курьера. А если полученные Ивановым ключи зашифрованы с помощью ключа шифрования ключей, ему остается лишь надеяться, что этот ключ имеется только у Петрова. Наконец, если рассылку ключей производит ЦРК, Иванов должен убедиться в надежности процедур рассылки, которые приняты в ЦРК.

Если противник полностью контролирует все каналы связи, которыми пользуется Иванов, он может заставить поверить Иванова во что угодно. Противник может прислать ему фальшивый ключ шифрования ключей якобы от Петрова и затем передавать Иванову поддельные ключи шифрования данных, зашифрованные на этом ключе. Противник будет в состоянии обзавестись собственным ЦРК и слать Иванову ключи от имени подлинного ЦРК. И ничего не подозревающий Иванов станет шифровать свои сообщения с помощью ключей, известных противнику.

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

Эти рассуждения наивны. На практике установить тотальный контроль нал чьими бы то ни было линиями связи невозможно. Действительно. Иванов не в силах убедиться наверняка, что переданный ему ключ не был подменен всемогущим противником. Однако, чтобы его контроль был действительно тотальным, такому противнику придется прибегнуть к средствам, которые в реальном мире ему вряд ли будут доступны.

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

Нередко бывает, что Иванов желает убедиться: переданный ему ключ не только является подлинным, но и не был искажен при передаче. Ведь в результате Иванов может оказаться не в состоянии прочесть многие мегабайты шифр-текста. Если соответствующий открытый текст был ASCII-файлом, то можно проверить ключ, попытавшись расшифровать с его помощью шифртекст, и получив абракадабру вместо осмысленного текста, сделать вывод о том, что ключ был передан с искажениями. Если открытый текст является достаточно случайным, можно прибегнуть к другим методам проверки ключа.

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

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

Псевдослучайные последовательности

Самое лучшее, на что способен компьютер, — это сгенерировать псевдослучайную последовательность, которая хотя и выглядит случайной, но, на самом деле, таковой не является. Период псевдослучайной последовательности должен быть достаточно большим, чтобы ее подпоследовательность требуемой длины была апериодичной, т. е. имела период, совпадающий с ее длиной. Например, если нужна строка из миллиона случайных бит, то для ее порождения не стоит использовать генератор последовательностей, которые повторяются через каждые 65536 бит.

Псевдослучайная битовая последовательность должна, по возможности, не отличаться от по-настоящему случайной. Необходимо, чтобы в ней число единиц примерно совпадало с числом нулей, а половина всех "полосок" (подряд идущих идентичных компонентов последовательности) имела длину I. одна четвертая — длину 2, одна восьмая — длину 4 и т. д. Кроме только что перечисленных, существует еще ряд общепринятых тестов, которые позволяют проверить, действительно ли данная последовательность является псевдослучайной.

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

"Китайская лотерея"

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

За найденный ключ полагается значительный приз. Благодаря этому радиоприемники и телевизоры со встроенными микросхемами хорошо раскупаются, а вскрытые ключи своевременно доводятся до сведения китайского правительства. Если учесть, что у каждого из десяти китайцев есть радиоприемник или телевизор, то получится, что на вскрытие 64-битного ключа китайскому правительству потребуется самое большее 43 часа. В табл. 6.2 приведена сложность вскрытия 64-битного ключа с помощью "китайской лотереи" при ее проведении в Китае, а также в США, Ираке и Израиле.

Работа с ключами

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

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

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

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

Потратить 10 млн долл. на разработку и изготовление специализированного криптоаналитического суперкомпьютера? Ну уж нет! Лучше за 1000 долл. подкупить шифровальщика, который будет регулярно передавать ключи к шифру. А если бюджет позволяет, то за миллион долларов можно накупим, этих ключей на много-много лет вперед. Американский военнослужащий Джон Уокер, к примеру, годами снабжал советскую разведку ключами к шифрам ВМС США, что позволило КГБ прочесть огромное количество американских шифровок. Ну а за несколько миллионов долларов доставим, где-то ключи, чтобы потом с их помощью читать шифрованные сообщения, нет нужды и вовсе. За такие огромные деньги лучше сразу приобрести oi-крытые тексты этих сообщений. Например, всего 2 млн долларов понадобилось советской разведке, чтобы купить высокопоставленного сотрудника американской контрразведки Олдрича Эймса вместе с женой.

Ну а если из бюджета не удается выкроить нужную сумму на подкуй, то можно воспользоваться другими методами. Человек слаб: его можно напоить, усыпить или просто оглушить тяжелым предметом, чтобы выкраси, криптографические ключи. Его можно также соблазнить. Морские пехотинцы, охранявшие американское посольство в Москве, по просьбе своих русских любовниц пропускали в шифровальный отсек посольства сотрудников КГБ — на "экскурсию".

Это значит, что криптографические ключи нуждаются в такой же защите. как и сами данные, которые шифруются с их помощью. К сожалению, во многих коммерческих средствах шифрования часто считается достаточным провозгласить об использовании DES-алгоритма или другого достаточно стойкого шифра, а о генерации и хранении ключей к ним не говорить ни слова. Например, программа DiskLock (версия 2.1) для персонального компьютера Macintosh позволяет шифровать файлы по DES-алгоритму. Однако ключ, использованный этой программой для зашифрования, она сохраняет на носителе информации вместе с файлом. Зная, где лежит ключ, его можно оттуда извлечь и затем без особых хлопот прочесть с помощью этого ключа содержимое зашифрованного файла. В данном случае совершенно неважно. что сам алгоритм шифрования достаточно надежен. Имеет значение только то, что его реализация абсолютно никуда не годится.

Скомпрометированные ключи

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

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

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

Сложность и стоимость атаки методом тотального перебора

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

Среди параметров, которые необходимо принимать во внимание при рассмотрении атаки методом тотального перебора, прежде всего, надо упомянуть об общем количестве проверяемых ключей и о времени, затрачиваемом противником на проверку одного ключа. Количество ключей для конкретною алгоритма обычно фиксировано. Например, DES-алгоритм использует 56-битный ключ. Это означает, что его ключевое пространство содержит 2 56 ключей.

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

При решении вопроса о достаточной длине ключа в качестве алгоритма шифрования чаще всего рассматривается DES-алгоритм. В 1977 г. американские криптологи У. Диффи (W.Diffie) и М. Хеллман (M.Hellman) заявили, что при существующем уровне развития компьютерной технологии можно построить специализированный суперкомпьютер для вскрытия ключей DES-алгоритма методом тотального перебора. Имея в своем составе 1 млн микросхем, каждая из которых способна проверять 1 млн ключей в секунду, этот суперкомпьютер перебрал бы все 2 56 ключей за 20 час.

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

В 1993 г. американский криптолог М. Винер (M.Wiener) спроектировал суперкомпьютер для атаки на DES-атгоритм методом тотального перебора. Рассуждения Винера верны не только для DES-алгоритма, но и практически для любого другого алгоритма шифрования. Суперкомпьютер, разработанный Винером, состоит из специализированных микросхем, плат и стоек. По мнению Винера, для того чтобы гарантировать вскрытие 56-битного ключа за 7 час, на изготовление такого суперкомпьютера потребуется не более 1 млн долларов. По закону Мура, вычислительная мощь компьютеров улавливается каждые полтора года. Поэтому к 2001 г. стоимость суперкомпьютера, придуманного Винером, уменьшится в 10 раз и составит всего-навсего 100 тыс. долларов. Это означает, что уже сейчас крупные компании и "крутые" криминальные структуры могут вскрывать 56-битные ключи. Для военных криптоаналитиков в большинстве индустриально развитых стран доступны 64-битные ключи.

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

Случайные ключи

Хороший ключ представляет собой случайный битовый вектор. К примеру. если его длина составляет 56 бит, то это значит, что в процессе его генерации с одинаковой вероятностью может получиться любой из 2 56 возможных ключей. Источником случайных ключей обычно служит либо природный случайный генератор (хорошей аналогией такого генератора является маленький ребенок, который только что научился ходить, — временные интервалы между его падениями абсолютно случайны). Кроме того, источником случайного ключа может быть криптографически надежный генератор псевдослучайных битовых последовательностей. Лучше, чтобы процесс генерации ключей был автоматизирован. Если под рукой нет компьютера для запуска программы, реализующей псевдослучайный генератор, или ваш ребенок давно уже вышел из младенческого возраста, можно бросать монетку или игральную кость.

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

Во всех алгоритмах шифрования имеются так называемые нестойкие ключи. Это означает, что некоторые из ключей к шифру являются менее надежными, чем остальные. Поэтому при генерации ключей нужно автоматически проверять их на стойкость и генерировать новые вместо тех, которые эту проверку не прошли. К примеру, в DES-алгоритме имеются всего 24 нестойких ключа из общего количества 2 56 , и следовательно вероятность наткнуться на нестойкий ключ пренебрежимо мала. Кроме того, откуда криптоаналитику знать, что для зашифрования конкретного сообщения или файла был применен именно нестойкий ключ? А сознательный отказ от использования нестойких ключей дает противнику дополнительную информацию о вашей криптосистеме, что нежелательно. С другой стороны, проверка ключей на нестойкость достаточно проста, чтобы ею пренебрегать.

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

Пользоваться случайными ключами не всегда удобно. Иногда ключ требуется сохранить в памяти, а запомнить 36f9 67аЗ f9cb d931 человеку не так-то просто. В этом случае для генерации можно использовать некое правило, которое будет очевидно для вас, но недоступно для постороннего. Два варианта такого правила:

Составьте ключ из нескольких слов, разделенных знаками препинания. Например, очень просто и надолго запоминаются ключи типа Yankee'Go home. Используйте в качестве ключа сочетание букв, которые представляют собой акроним более длинного слова. К примеру, броское название немецкого вина Liebenfraumilch позволяет путем отбрасывания гласных букв и добавления восклицательного знака сгенерировать ключ Lbnfrmlch!.

Сокращенные ключевые пространства

Длина ключа в DES-алгоритме составляет 56 бит. В принципе, в качестве ключа может быть использован любой 56-битный вектор. На практике это правило часто не соблюдается. Например, широко распространенная программа шифрования файлов Norton Discreet, входящая в пакет Norton Utilities (версии 8.0 или более младшей версии), который предназначен для работы в операционной системе DOS, предлагает пользователю программную реализацию DES-алгоритма. Однако при вводе ключа разрешается подавать на вход программы только те символы, старший бит представления которых в коде ASCII равен нулю. Более того, пятый бит в каждом байте введенного ключа является отрицанием шестого бита, и в нем игнорируется младший бит. Это означает, что мощность ключевого пространства сокращается до каких-то жалких 2 40 ключей. Таким образом из-за плохой процедуры генерации ключей программа Norton Discreet реализует алгоритм шифрования, ослабленный в десятки тысяч раз по сравнению с настоящим DES-алгоритмом.

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

в получении большого количества ключей

Стандарт ANSI X9.17

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

Пусть функция Е K (Р) осуществляет шифрование Р по DES-алгоритму на заранее заготовленном ключе К, который используется только для генерации секретных ключей. Пусть далее V 0 является начальным 64-битным значением, которое держится в тайне от противника, а Т i представляет собой отметку времени, когда был сгенерирован i-й ключ. Тогда очередной случайный ключ R i вычисляется с помощью преобразования:

R i = Е К (Е К (Т i ) Å V i )

Чтобы получить очередное значение V i , надо вычислить

V i = Е К (Е К (Т i ) Å R i )

Термодинамические ограничения

Из второго закона термодинамики следует, что для записи одного бита информации путем соответствующего изменения состояния среды требуется не менее kT эрг энергии, где k— постоянная Больцмана и Т— температура системы. Учитывая, что температура Вселенной составляет 3,2° по Кельвину, для изменения одного бита информации компьютеру понадобится не менее 4,4 10 -16 эрг энергии. Уменьшение температуры среды ниже уровня температуры Вселенной потребует дополнительных затрат энергии и поэтому не имеет особого смысла.

За год вся энергия, излучаемая Солнцем, составляет 1,21 10- 41 эрг. Ее хватит, чтобы произвести 2,7 1056 записей одного бита информации, что эквивалентно прогону 187-битного счетчика через все возможные состояния. Если наше довольно "прохладное" Солнце заменить сверхновой звездой, то счет-£ чик можно сделать 219-битным.

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

Уничтожение ключей

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

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

Запасные ключи

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

у Абрама Ключмана, первого заместителя

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

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

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