Длина секретного ключа
Надежность симметричной криптосистемы зависит от стойкости используемого криптографического алгоритма и от длины секретного ключа. Допустим, что сам алгоритм идеален — вскрыть его можно только путем опробования всех возможных ключей. Этот вид криптоаналитической атаки называется методом тотального перебора. Чтобы применить данный метол, криптоаналитику понадобится немного шифртекста и соответствующий открытый текст. Например, в случае блочного шифра ему достаточно получить в свое распоряжение по одному блоку шифрованного и соответствующего открытого текста. Сделать это не так уж и трудно.
Криптоаналитик может заранее узнать содержание сообщения, а затем перехватить его при передаче в зашифрованном виде. По некоторым признакам он также может догадаться, что посланное сообщение представляет собой не что иное, как текстовый файл, подготовленный с помощью распространенного редактора, компьютерное изображение в стандартном формате, каталог файловой подсистемы или базу данных. Для криптоаналитика важно то, что в каждом из этих случаев в открытом тексте перехваченного шифрсообщения известны несколько байтов, которых ему хватит, чтобы предпринять атаку со знанием открытого текста.
Подсчитать сложность атаки методом тотального перебора достаточно просто. Если ключ имеет длину 64 бита, то суперкомпьютер, который может опробовать 1 млн ключей за 1 с, потратит более 5 тыс. лет на проверку всех возможных ключей. При увеличении длины ключа до 12cS бит, этому же суперкомпьютеру понадобится 10 25 лет, чтобы перебрать все ключи. Вселенная существует всего-навсего 10'° лет, поэтому можно сказать, что 10- — это достаточно большой запас надежности для тех, кто пользуется 128-5ишымп ключами.
Однако прежде чем броситься спешно изобретать криптосистему с длиной ключа в 4 Кбайт, следует вспомнить о сделанном выше предположении, а именно: используемый алгоритм шифрования идеален в том смысле, что вскрыть его можно только методом тотального перебора. Убедиться в этом на практике бывает не так просто, как может показаться на первый взгляд. Криптография требует утонченности и терпения. Новые сверхсложные криптосистемы при более внимательном рассмотрении зачастую оказываются очень нестойкими. А внесение даже крошечных изменений в стойкий криптографический алгоритм может существенно понизить его стойкость. Поэтому надо пользоваться только проверенными шифрами, которые известны уже в течение многих лет, и не бояться проявлять болезненную подозрительность по отношению к новейшим алгоритмам шифрования, вне зависимости от заявлений их авторов об абсолютной надежности этих алгоритмов.
Важно также не забывать о правиле Керкхоффа: стойкость алгоритма шифрования должна определяться ключом, а не деталями самого алгоритма. Чтобы быть уверенным в стойкости используемого шифра, недостаточно проанализировать его при условии, что противник досконально знаком с алгоритмом шифрования. Нужно еще и рассмотреть атаку на этот алгоритм, при которой враг может получить любое количество шифрованного и соответствующего открытого текста. Более того, для повышения надежности следует предположить, что криптоаналитик имеет возможность организовать атаку с выбранным открытым текстом произвольной длины.
К счастью, в реальной жизни большинство людей, интересующихся содержанием ваших шифрованных файлов, не обладают квалификацией высококлассных специалистов и вычислительными ресурсами, которые имеются в распоряжении правительств мировых супердержав. Последние же вряд ли будут тратить время и деньги, чтобы прочесть ваше пылкое сугубо личное послание. Однако, если вы планируете свергнуть "антинародное правительство", вам необходимо всерьез задуматься о стойкости применяемого алгоритма шифрования.
Сложность и стоимость атаки методом тотального перебора
Атака методом тотального перебора, как правило, представляет собой разновидность атаки со знанием открытого текста. Если предположить, что атака методом тотального перебора является наиболее эффективной среди возможных атак на используемый вами симметричный алгоритм шифрования. то ключ должен быть достаточно длинным, чтобы успешно отразить эту атаку. Насколько длинным?
Среди параметров, которые необходимо принимать во внимание при рассмотрении атаки методом тотального перебора, прежде всего, надо упомянуть об общем количестве проверяемых ключей и о времени, затрачиваемом противником на проверку одного ключа. Количество ключей для конкретною алгоритма обычно фиксировано. Например, 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).
Таблица 6.1. Стоимость и вычислительная сложность атаки методом тотального перебора
| Кто атакует | Бюджет | Сложность атаки | Стойкий ключ | |
| 40 бит | 56 бит | |||
| Хакер | 1000 долл. | 1 неделя | Никогда | 45 бит |
| Малый бизнес | 10 тыс. долл. | 12 мин. | 556 дней | 64 бита |
| Крупная компания | 10 млн долл. | 0.005 с | 6 мин | 70 бит |
| Федеральное агентство | 300 млн долл. | 0.0002 с | 12с | 75 бит |
К приведенным в табл. 6.1 цифрам следует относиться с осторожностью. Теоретический расчет затрат на проведение атак методом тотального перебора на криптографические ключи разной длины всегда существенно отличается от того, с чем криптоаналитики сталкиваются на практике при покупке или разработке суперкомпьютеров для ведения такого рода атак. Объясняется это тем, что одни сделанные допущения оказываются весьма далеки от реальности, в то время как другие факторы просто не принимаются во внимание. В данном случае Диффи, Винер и другие посчитали, что при создании специализированного суперкомпьютера для атаки методом тотального перебора будут использоваться заказные микросхемы ценой не более 10 долл. По оценкам АНБ, такие микросхемы стоят, как правило, в 100 раз дороже. У АНБ вызвало сомнение и допущение о том, что вне зависимости от алгоритма шифрования, лишь длина ключа определяет сложность криптоаналитической атаки. Кроме того, при составлении таблицы не были учтены затраты на научно-исследовательские и опытно-конструкторские работы, которые для первого экземпляра суперкомпьютера обычно составляют не менее 10 млн долл. Не были также приняты во внимание расходы на приобретение компьютерной памяти.
Из сказанного можно сделать весьма важный вывод. Если кто-то очень захочет узнать использованный вами ключ, ему нужно всего лишь потратить достаточное количество денег. Поэтому определяющей является стоимость зашифрованной вами информации. Если цена ей в базарный день — около 2 долл., вряд ли кто-то решится потратить 1 млн, чтобы ее заполучить. Но если прибыль от прочтения вашей шифровки составляет 100 млн долл.. — берегитесь! Единственным утешением может послужить тот факт, что с течением времени любая информация очень быстро устаревает и теряет свою ценность.
Программная атака
Без специализированного компьютерного оборудования, ведущего параллельный поиск ключей, атака методом тотального перебора имеет значительно меньше шансов на успех. Однако если вы не припасли лишний миллион долларов, который можно потратить на изготовление такого оборудования, есть другой, более дешевый, способ попытаться вскрыть интересующий вас ключ.
В мире имеется огромное количество компьютеров (по оценкам экспертов, в 1996 г. их число достигло 200 млн), которые, чтобы не простаивать, могли бы опробовать ключи. Эксперимент, проведенный в начале 1997 г., показал, что таким способом за две недели можно вскрыть 48-битный ключ. И хотя этот ключ был найден методом тотального перебора после проверки чуть более половины всех возможных ключей, полученный результат впечатляет, поскольку в ходе атаки одновременно использовались не более 5 тысяч компьютеров из существующих 200 миллионов, а в общей сложности в атаке оказались задействованными лишь 7 тысяч компьютеров.
Основное препятствие на пути к использованию миллионов вычислительных устройств, разбросанных по всему миру, заключается в невозможности сделать так, чтобы их владельцы приняли участие в атаке. Можно, конечно, вежливо попросить каждого из них об услуге, но во-первых, на это уйдет уйма времени, а во-вторых, ответом в большинстве случаев будет, скорее всего, твердое "нет". Можно попытаться тайком проникнуть на чужие компьютеры через сеть, но на это понадобится еще больше времени, да вдобавок вас могут арестовать.
Более разумным представляется создание компьютерного вируса, который вместо того, чтобы стирать файлы с жесткого диска и выдавать на дисплей % глупые сообщения, незаметно для владельца компьютера будет перебирать возможные ключи. Проведенные исследования показывают, что в распоряжении вируса будет от 70 до 90% процессорного времени зараженного им компьютера. После вскрытия ключа вирус может породить новый вирус, содержащий информацию о найденном ключе, и отправить его странствовать по компьютерной сети до тех пор, пока он не доберется до своего хозяина.
При более тонком подходе вирус, обнаруживший ключ, выдаст на экран компьютера информацию вида:
В ВАШЕМ КОМПЬЮТЕРЕ ОБНАРУЖЕНА СЕРЬЕЗНАЯ ОШИБКА!
ПОЖАЛУЙСТА, ПОЗВОНИТЕ ПО ТЕЛЕФОНУ (095)123-45-67
И ЗАЧИТАЙТЕ ОПЕРАТОРУ СЛЕДУЮЩЕЕ 48-БИТОВОЕ ЧИСЛО:
хххххххх ххххххх ххххххх ххххххх ххххххх ххххххх
ПЕРВОМУ, КТО СООБЩИТ ОБ ЭТОЙ ОШИБКЕ, ГАРАНТИРОВАНО
ВОЗНАГРАЖДЕНИЕ В РАЗМЕРЕ 100 (СТА) ДОЛЛАРОВ.
Если вирусу удастся заразить 10 млн компьютеров, каждый из которых станет проверять хотя бы 1 тыс. ключей в секунду, то 56-битный ключ будет найден менее чем через 3 месяца. Дополнительно придется раскошелиться на подкуп производителей антивирусных программ, однако к компьютерной криптографии, о которой сейчас идет речь, эта проблема никакого отношения не имеет.
"Китайская лотерея"
Допустим, что для атаки методом тотального перебора во всякий без исключения китайский радиоприемник и телевизор встраивается специальная микросхема, проверяющая 1 млн ключей в секунду. Каждая из них автоматически перебирает свое подмножество ключей после получения из эфира фрагментов шифрованного и соответствующего открытого текста. Как только правительство Китая пожелает вскрыть какой-нибудь ключ, оно принимает постановление, которое обязывает всех владельцев телевизоров и радиоприемников включить свои аппараты в определенное время, чтобы они могли принять пару фрагментов текста и приступить к перебору ключей.
За найденный ключ полагается значительный приз. Благодаря этому радиоприемники и телевизоры со встроенными микросхемами хорошо раскупаются, а вскрытые ключи своевременно доводятся до сведения китайского правительства. Если учесть, что у каждого из десяти китайцев есть радиоприемник или телевизор, то получится, что на вскрытие 64-битного ключа китайскому правительству потребуется самое большее 43 часа. В табл. 6.2 приведена сложность вскрытия 64-битного ключа с помощью "китайской лотереи" при ее проведении в Китае, а также в США, Ираке и Израиле.
Таблица 6.2. Сложность вскрытия 64-битного ключа с помощью "китайской лотереи"
| Страна | Численность населения | Количество телевизоров и радиоприемников | Сложность вскрытия 64-битового ключа с помощью "китайской лотереи" |
| Китай
|
1 190 431 000 | 257 000 000 | 43 часа |
| США | 260 714 000 | 739 000 000 | 6,9 часов |
| Ирак | 19 890 000 | 4 730 000 | 44 дня |
| Израиль | 5 051 000 | 3 640 000 | 58 дней |
Биотехнология
Предположим такую ситуацию: с использованием генной инженерии удалось вывести особую породу травоядных динозавров. Их нарекли "криптозаврами", поскольку они состоят из клеток, которые могут проверять криптографические ключи. Шифрованный и соответствующий открытый теки передаются в клетки криптозавра с помощью магнитооптических средин. Найденный ключ выводится специальными клетками, способными перемещаться в пределах тела криптозавра. Поскольку динозавр в среднем состоит из 2 14 клеток, то при условии, что каждая из них успевает проверить 1 миллион ключей в секунду, на поиск 64-битного ключа уйдет не более 1 с.
Для этой же цели можно использовать клетки морских водорослей. Например, на площади в 500 км2 и на глубине в 1 м их можно разместить в количестве 1023. Если каждая из них будет обрабатывать 1 млн ключей в секунду. то 128-битный ключ будет вскрыт менее чем за сотню лет. Шифрованный и открытый тексты передаются водорослям с помощью спутника, а сигналом о нахождении искомого ключа служит изменение окраски водорослей вокруг клетки, отыскавшей этот ключ. За советами по разведению морских водорослей криптоаналитики могут обратиться на биологический факультет ближайшего университета.
Термодинамические ограничения
Из второго закона термодинамики следует, что для записи одного бита информации путем соответствующего изменения состояния среды требуется не менее kT эрг энергии, где k— постоянная Больцмана и Т— температура системы. Учитывая, что температура Вселенной составляет 3,2° по Кельвину, для изменения одного бита информации компьютеру понадобится не менее 4,4 10 -16 эрг энергии. Уменьшение температуры среды ниже уровня температуры Вселенной потребует дополнительных затрат энергии и поэтому не имеет особого смысла.
За год вся энергия, излучаемая Солнцем, составляет 1,21 10- 41 эрг. Ее хватит, чтобы произвести 2,7 1056 записей одного бита информации, что эквивалентно прогону 187-битного счетчика через все возможные состояния. Если наше довольно "прохладное" Солнце заменить сверхновой звездой, то счет-£ чик можно сделать 219-битным.
Сказанное означает, что атака методом тотального перебора против криптосистемы с 256-битным ключом энергетически неосуществима до тех пор, пока компьютеры являются объектами материального мира и их функционирование подчиняется его законам, в частности — второму закону термодинамики.