Взлом криптоалгоритмов: мифы и реалии
АрхивВ последнее время мы часто слышим о реальном применении криптографии в компьютерных системах и не только
В последнее время мы часто слышим о реальном применении криптографии в компьютерных системах и не только (даже стандарт сотовой связи GSM предусматривает защиту разговора абонентов при помощи методов симметричной криптографии). Криптография здорово продвинулась за последнее столетие. Придумано много алгоритмов: RSA, DES, алгоритмы на основе схемы Эль Гамаля, эллиптических кривых… Но!
Если есть замок, но нет ключа, дверь можно взломать. Шифр также можно попробовать взломать. Кроме перебора всех возможных вариантов существуют другие способы. Взлом есть взлом. Вернее, взлом всегда «есть» (присутствует). От него не уйти. Да и уходить не надо — зачастую он является отправной точкой прогресса в науке и технике. Взлом полезно анализировать хотя бы для того, чтобы понять, насколько сильна защита. Кроме того, знание истории атак и дыр, а также понимание причин, по которым они имели место, является одним из необходимых условий разработки защищенных систем.
Последнее десятилетие характеризуется резким увеличением числа открытых работ по всем вопросам криптологии, а криптоанализ становится одной из наиболее активно развивающихся областей исследований. Многие криптосистемы, стойкость которых не вызывала особых сомнений, оказались успешно раскрытыми. При этом разработан большой арсенал математических методов, представляющих прямой интерес для криптоаналитика.
Взлом криптографических алгоритмов: анализ
В принципе, любой алгоритм, основанный на ключе, может быть вскрыт «в лоб» — перебором всех ключей. Понятно, что требуемая вычислительная мощность в этом случае возрастает экспоненциально при увеличении длины ключа. Можно ли решить задачу такого рода на домашнем ПК? Утверждается, что если длина ключа — 32 бита, то можно (потребуется около 109 шагов), а если немного больше — потребуются распределенные вычисления.
На сегодняшний день работники крупной компании с большими вычислительными мощностями и/или пользователи глобальной сети совместными усилиями могут методом перебора вскрыть ключ максимальной длиной 64–80 бит. По оценкам, взлом шифра со 128-битным ключом займет не менее 1020 лет. Впрочем, оценки такого рода весьма поверхностны. Так, вскрытие 64-битного ключа (симметричного алгоритма RC5-64) потребовало сравнительно меньших временных затрат, чем предполагалось. Распределенное на несколько сотен тысяч машин сложное математическое задание позволило «взломать» ключ за пять лет против предполагавшихся ста лет.
А как обстоят с этим дела у нас? Вспомним удачный отечественный ГОСТ 28147-89 — это симметричная блочная криптосистема, немного напоминающая известный алгоритм DES (только по сходной структуре итераций, шаг шифрования у него совсем другой). Ключ у него «всего» 256 бит. Учтите, что это 256 случайных бит. Так что для прямой атаки на ключ придется перебрать все 2256 ключей (это куда «круче», чем в случае RSA-1024), что физически не реализуемо: при минимальном энергопотреблении взламывающего вычислителя (оно определяется исходя из квантовой теории) оказывается, что для обеспечения энергией такого вычислителя необходимо рвануть сверхновую.
Однако длина ключа — это еще не полная гарантия защиты. Некоторые шифры можно вскрыть и не перебирая всех возможных комбинаций, а применяя специальный алгоритм (например, с полиномиальной сложностью). Для некоторых «опасных» алгоритмов нет гарантированной оценки нижней грани числа операций, необходимых для вскрытия, и поэтому существует вероятность, что будет придуман некий алгоритм, который позволит достаточно быстро дешифровать сообщения.
Здесь уместно отметить один неудачный отечественный опыт, в результате которого был придуман более простой алгоритм вскрытия шифра, чем ожидалось. В 1994 году был принят первый отечественный стандарт в области электронной цифровой подписи (ЭЦП) — ГОСТ Р34.10-94 «Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма». Он определяет процедуры работы с ЭЦП на основе схемы Эль Гамаля. Невозможность подделки подписи основана на сложности решения задачи дискретного логарифмирования в поле из р элементов. Однако математика не стоит на месте, и недавно был изобретен так называемый метод решета числового поля. С его помощью можно «взломать» ЭЦП, сформированную по схеме Эль Гамаля, по крайней мере в случае 512-битного модуля р.
Думаю, теперь вы понимаете, почему некоторые разработчики предпочитают использовать, казалось бы, уходящие в прошлое методы симметричного шифрования. Они боятся, что сделают ставку на некоторый надежный, по их мнению, асимметричный алгоритм, а математики через некоторое время придумают новый метод и вскроют его (алгоритм). С этой точки зрения симметричные алгоритмы, вероятно, более прогнозируемы (но отнюдь не более надежны). Надо ли говорить, что классические методы шифрования и изучены гораздо больше, а их надежность обоснована неизмеримо лучше, чем надежность методов «современной криптографии».
Средства и способы взлома шифров
Суперкомпьютеры
Чтобы понять, насколько современные суперкомпьютеры мощны для решения задач криптоанализа, часто проводят такой эксперимент. Допустим, рассматриваемые алгоритмы шифрования идеальны, то есть оптимальным методом их взлома будет прямой перебор всех возможных ключей. Очевидно, в этом случае стойкость криптосистем будет определяться длиной ключа. Предположим, что генерация ключа компьютером происходит за один такт его работы, а операция дешифрования — мгновенно. Определив отношение количества ключей к быстродействию компьютера, мы получим нижнюю оценку сложности дешифрования сообщения для идеального алгоритма. Результаты этих расчетов приведены в табл. 1 (полный анализ вычислительных мощностей суперкомпьютеров: www.ssl.stu.neva.ru/psw/crypto/ Pudov21.html). Средним временем расшифровки сообщения следует считать половину приведенного в таблице времени (в скобках).
Из таблицы видно, что даже самые мощные суперкомпьютеры затратят на взлом 70-битного ключа больше десяти лет (при условии идеальности алгоритма и его реализации в смысле наличия «дыр»). И что же получается, 70-битный ключ на 100% защитит всех от взлома? Нет, конечно. Во-первых, производительность суперкомпьютеров неуклонно растет (тут еще можно строить какие-то прогнозы и предусмотреть защиту), а во-вторых, существуют другие способы и средства атак на криптосистемы (здесь с прогнозами сложнее).
Распределенные вычисления
В последнее время, в связи с развитием сетей (в частности, Интернета), стало возможно эффективно использовать метод «грубой силы» (перебора) путем распараллеливания операций. Реализуется такой подход, как правило, следующим образом. Где-то в Интернете устанавливается сервер, с которого любой желающий может загрузить программу, выполняющую расшифрование тестового сообщения путем перебора ключей. Программа обычно поставляется как в виде исходных текстов, так и скомпилированной для наиболее распространенных операционных систем. После запуска программа устанавливает соединение с сервером, получает от него набор ключей для перебора и после окончания работы возвращает результат.
Программа может работать в фоновом режиме, в качестве скринсейвера или активироваться по ночам. Она может заниматься не только «вскрытием» шифров, но и, например, подбором двух текстов, имеющих одинаковое значение хэш-функции, вычисленной указанным алгоритмом.
Метод «распределенного взлома» зачастую используют некоммерческие организации для выяснения криптостойкости алгоритмов (см., например, www. distributed.net). Описанный способ, опирающийся исключительно на энтузиазм участников, уже дал потрясающие результаты. Давайте, к примеру, рассмотрим алгоритм RSA.
В настоящее время RSA активно реализуется как в виде самостоятельных криптографических продуктов, так и в качестве встроенных средств в популярных приложениях. Нам же он будет интересен с точки зрения возможности его вскрытия. Некто Шроппель (Rich Schroeppel) исследовал трудоемкость разложения на множители произведения простых чисел различной длины (на этом, собственно, и основан алгоритм RSA). И вот что получилось (см. табл. 2).
Если верить Шроппелю, ключ длиной 800 бит (при симметричной реализации надо полагать) практически не раскрываем на существующих вычислительных мощностях. И в ближайшем будущем вскрытие такого ключа не прогнозируется.
Что касается традиционного асимметричного алгоритма RSA, то в последние десять лет то и дело появляются слухи о его «вскрытии». Вспомним, что в 2001 году филиппинская газета «Manila Bulletin» сообщила: «Взломан алгоритм шифрования RSA. Филиппинский математик-энтузиаст Лео де Велез разработал новый метод декодирования алгоритма шифрования RSA, основанный всего лишь на трех простых формулах».
Лично мне представляется, что взлом RSA — это решение сложной математической проблемы и нахождение (альтернативного) потайного входа стало бы великим математическим открытием, которое заставило бы полпланеты переделывать свои криптосистемы защиты данных, настраивая их на другие алгоритмы/ключи и т. д.
Также появляются сведения о раскрытии шифра для определенной длины ключа. Например, в конце 1995 года удалось практически реализовать раскрытие шифра RSA для 500-значного ключа. Для этого с помощью Интеpнета было задействовано 1600 компьютеров. Здесь также имеет смысл говорить о длительности вычислений — ведь за три-пять лет (практическое время взлома) зачастую информация устаревает. Сами авторы RSA рекомендуют использовать следующие размеры модуля n:
- 768 бит — для частных лиц;
- 1024 бит — для коммерческой информации;
- 2048 бит — для особо секретной информации.
Хочу обратить внимание читателя на запись в табл. 2: «Требует существенных изменений в технологии». О ней-то мы сейчас и поговорим.
Квантовый компьютер IBM
В августе 2000 года корпорация IBM объявила о разработке первого в мире квантового компьютера. Экспериментальная модель, построенная на пяти атомах, продемонстрировала потенциал систем такого рода, решая определенные задачи со скоростью, значительно превышающей быстродействие обычных компьютеров. Что получится, если количество работающих атомов увеличить до тысячи? А до миллиона? Как признался руководитель группы ученых из IBM, Стэнфордского университета и Университета Калгари Исаак Чуанг (Isaac Chuang), квантовый компьютер можно использовать, в частности, и для взлома криптографических шифров.
Команда Чуанга применяет экспериментальный квантовый компьютер для решения традиционных математических задач, встречающихся в криптографии: поиска периода функции. Квантовый компьютер способен решить любую задачу этого типа за один шаг, в то время как обычному потребовалось бы множество циклов. В отличие от обычного компьютера, который при решении криптографических задач выполняет последовательные сложения нескольких чисел, квантовая машина, используя спин электрона или частиц атомного ядра, может складывать числа одновременно. При определенных типах вычислений, таких как криптографические алгоритмы, квантовый компьютер, состоящий из нескольких сотен атомов, сможет выполнять миллиарды операций единовременно.
Даже боязно как-то становится за криптографию, не правда ли? Пока не ясно, когда можно будет построить полноценный квантовый компьютер. Ну что же, Голубой гигант подарил этому миру немало прорывов в области информационных технологий. Подождем, что у них выйдет на сей раз.
Криптоанализ
Криптоанализом называется область деятельности, направленная на раскрытие чужих зашифрованных сообщений при неизвестном ключе шифрования и/или алгоритме. Трудно определить криптоанализ только как науку. Ему присущи и элементы искусства, и везения, и даже шаманства.
Современная криптография исходит из принципа, что стойкость криптографического преобразования должна обеспечиваться только сохранением в тайне ключа. При проектировании криптографической системы изначально предполагается, что алгоритм является открытым (или как минимум известен вероятному противнику), а ключ, наоборот, надежно защищен. Стойкость алгоритма шифрования обычно оценивают в количестве типовых операций, требующихся для расшифрования зашифрованного сообщения и/или подбора ключа шифрования наилучшим алгоритмом.
Криптоанализ традиционно используется для решения следующих задач:
- восстановление исходной информации по ее криптограмме;
- вычисление закрытого ключа по известному открытому;
- формирование электронной цифровой подписи сообщения без знания закрытого ключа;
- создание фальшивого электронного документа, соответствующего известной подписи.
Помимо классического криптоанализа для атак на криптосистемы могут использоваться недостатки в реализации криптоалгоритмов. Вспомним, для иллюстрации, найденные дыры в парольной системе защиты известного архиватора Pkzip/WinZip.
Какие возможны вообще атаки на системы криптографической защиты данных?
В этой ситуации атакующий имеет возможность получить шифрованный документ для любого нужного ему текста, но не знает ключа. Задачей, естественно, является нахождение последнего. Некоторые методы шифрования (в частности, RSA) весьма уязвимы для атак этого типа. При использовании подобных алгоритмов надо тщательно следить, чтобы атакующий не мог зашифровать таковым свой собственный текст. А как это сделаешь, если шифр стандартен на государственном или международном уровне и на него чуть ли не спецификация существует, к тому же общедоступная?
Тут всплывает неявное противоречие. С одной стороны, в любой книжке про криптографию вы прочтете, что целесообразно использовать известные «именные» шифры, стойкость которых проверена специальными организациями и т. д. и т. п. И с этим не поспоришь, нормальный здравомыслящий человек не станет использовать в серьезной системе алгоритм, который придумал давеча Вася Пупкин. С другой стороны, если алгоритм известен всем, то он известен и взломщикам, поэтому они могут тешиться с ним сколько хотят, объединяясь в интернациональные команды, изобретая всяческие хитроумные сетевые и нейронные взламывающие программы…
Атака на шифрованное сообщение
В данном случае атакующий не знает ничего о содержании сообщения, и ему приходится работать лишь с самим шифрованным текстом. На практике часто можно сделать правдоподобные предположения о структуре текста, поскольку многие сообщения имеют стандартные заголовки. Даже обычные письма и документы начинаются с легко предсказуемой информации, например «здравствуйте» или «привет». Также часто можно предположить, что некоторый блок информации содержит заданное слово (например, в документах MS Word содержится строка вроде «Microsoft Word 9.0»).
Атака с подменой ключей
Эта атака зачастую основана на нападении на протокол обмена ключами. Суть в том, что, когда две стороны обмениваются ключами для секретной связи, противник внедряется между ними на линии обмена сообщениями. Далее он выдает каждой стороне свои ключи. В результате обе стороны будет иметь разные ключи, каждый из которых известен противнику. Теперь противник будет расшифровывать каждое сообщение своим ключом и затем зашифровывать его с помощью другого ключа перед отправкой адресату. Стороны будут иметь иллюзию секретной переписки, в то время как на самом деле противник читает все сообщения. Конечно, не все так просто, и против такого приема придумано множество всяческих «противоядий», но задуматься стоит.
Панацея
Как я уже отмечал, симметричные криптосистемы считаются более «стабильными к взлому» по сравнению с криптосистемами с открытым ключом. Более того, самым лучшим способом защиты принимаются симметричные криптосистемы с одноразовым случайным ключом. Ключ должен быть действительно случайным, а не псевдослучайным. Главное и решающее преимущество симметричной криптосистемы на одноразовых ключах — ее независимость от прогресса в математической теории (конечно, у любого симметричного алгоритма есть множество недостатков, главный из которых — управление ключами; но речь сейчас не об этом). То есть — абсолютная надежность и гарантированная стойкость (насколько позволяет сам алгоритм). Не зря же их используют разведчики всего мира (благо их «трафик» невелик). Стойкость же любого другого криптоалгоритма может катастрофически меняться (в меньшую сторону). Оценить стойкость криптоалгоритма можно, только зная самый эффективный способ его взлома. А такие способы имеют свойство все время появляться (изобретаться), так же как и производительность компьютеров — расти.
Причины ненадежности криптографических программ
Попробуем понять, почему же криптографические программы постоянно взламываются. Можно посмотреть на этот вопрос с другой стороны: какие пробелы, приводящие к успешному взлому, чаще всего встречаются в ПО и в организационной части?
Зачастую взлом происходит из-за того, что применяются недостаточно надежные криптоалгоритмы. Почему? У стойких алгоритмов может быть слишком малая скорость работы, может существовать патент на алгоритм, и право его использования нужно покупать. Наконец, создатели программ могут не знать (недостаточно квалифицированы?) или принципиально не хотеть использовать стойкие алгоритмы. Взлом также возможен вследствие слишком малой длины ключа или неверного его хранения, генерации или передачи. Стойкие криптоалгоритмы могут быть неправильно реализованы: например, отсутствует проверка на слабые ключи или использован плохой датчик случайных чисел.
Наконец, существует человеческий фактор. В любой критической системе ошибки человека-оператора являются чуть ли не самыми дорогостоящими и распространенными. В случае криптосистем непрофессиональные действия пользователя сводят на нет самый стойкий криптоалгоритм и самую корректную его реализацию и применение.
Заключение
Конечно, абсолютного (идеального, не вскрываемого и комфортного одновременно) алгоритма нет и быть, вероятно, не может. Однако все же можно пытаться контролировать стойкость используемого алгоритма (в том числе при помощи изучения возможности и истории его взлома). Многое зависит, в конечном счете, от решаемой задачи.
Литература и ссылки по теме
[1] Bruce Schneier, Self-Study Course in Block Cipher Cryptanalysis Cryptologia, v.24, n.1, pp. 18-34, Jan 2000.
[2] В. Зима, А. Молдовян, Н. Молдовян, Безопасность глобальных сетевых технологий. — СПб.: BHV, 2001.
[3] Максим Левин, Безопасность в сетях Internet и intranet. — М.: «Познавательная книга плюс», 2001.
[4] А. В. Бабаш, Г. П. Шанкин, Криптография. Аспекты защиты. — М.: «Солон-Р», 2002.
[5] А. В. Домашев, М. Л. Грунтовик, В. О. Попов, Д. И. Правиков, А. Ю. Щербина, И. В. Прокофьев, Программирование алгоритмов защиты информации. Издатель Могачева С. В. — М.: «Нолидж», 2002.
[6] Много всего о криптоанализе и криптографии: www.ssl.stu. neva.ru/psw/crypto.html.
[7] Некоммерческий проект проверки криптостойкости алгоритмов при помощи распределенных вычислений: www.distributed.net.
