Взлом криптоалгоритмов

       

Человеческий фактор


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

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

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



Хранение ключа вместе с данными


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

Типичным примером здесь будут все WWW-, ftp-, e-mail-клиенты. Дело в том, что для базовой (наиболее часто встречающейся) аутентификации в этих протоколах пароль должен передаваться серверу в открытом виде. Поэтому клиентские программы вынуждены шифровать (а не хэшировать) пароль, причем с фиксированным ключом, чтобы не надоедать пользователю постоянными вопросами. Отсюда следует, что где-то внутри любого броузера, почтового или ftp-клиента (будь то Netscape Communicator, Eudora, Outlook, FAR и т.п.) лежат все ваши пароли в практически открытом виде, и что расшифровать их не представляет труда. (Чаще всего, кстати, пароль в таких программах даже не шифруется, а кодируется алгоритмом типа base-64).



Экспортные ограничения


Это причина, связанная с экспортом криптоалгоритмов или с необходимостью приобретать патент или права на них. В частности, из США запрещен экспорт криптоалгоритмов с длиной ключа более 40 бит. Очевидно, что такая криптостойкость не может считаться надежной при современных вычислительных мощностях и даже на персональном компьютере, положив скорость перебора в 50 000 паролей/сек, получим время перебора в среднем порядка 4 месяцев.



Криптоанализ и атаки на криптосистемы


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

Атака со знанием лишь шифрованного текста (ciphertext-only attack): Это ситуация, когда атакующий не знает ничего о содержании сообщения, и ему приходтся работать лишь с самим шифрованным текстом. На практике, часто можно сделать правдоподобные предположения о структуре текста, поскольку многие сообщения имеют стандартные заголовки. Даже обычные письма и документы начинаются с легко предсказумой информации. Также часто можно предположить, что некоторый блок информации содержит заданное слово. Атака со знанием содержимого шифровки (known-plaintext attack): Атакующий знает или может угадать содержимое всего или части зашифрованного текста. Задача заключается в расшифровке остального сообщения. Это можно сделать либо путем вычисления ключа шифровки, либо минуя это. Атака с заданным текстом (chosen-plaintext attack): Атакующий имеет возможнот получить шифрованный документ для любого нужного ему текста, но не знает ключа. Задачей является нахождение ключа. Некоторые методы шифрования и, в частности, RSA, весьма уязвимы для атак этого типа. При использовании таких алгоритмов надо тщательно следить, чтобы атакующий не мог зашифровать заданный им текст. Атака с подставкой (Man-in-the-middle attack): Атака направлена на обмен шифрованными сообщениями и, в особенности, на протокол обмена ключами. Идея заключается в том, что когда две стороны обмениваются ключами для секретной коммуникации (например, используя шифр Диффи-Хелмана, Diffie-Hellman), противник внедряется между ними на линии обмена сообщениями. Далее противник выдает каждой стороне свои ключи. В результате, каждая из сторон будет иметь разные ключи, каждый из которых известен противнику. Теперь противник будет расшифровывать каждое сообщение своим ключом и затем зашифровывать его с помощью другого ключа перед отправкой адресату. Стороны будут иметь иллюзию секретной переписки, в то время как на самом деле противник читает все сообщения. Одним из способов предотвратить такой тип атак заключается в том, что стороны при обмене ключами вычисляют криптографическую хэш-функцию значения протокола обмена (или по меньшей мере значения ключей), подписывают ее алгоритмом цифровой подписи и посылают подпись другой стороне. Получатель проверит подпись и то, что значение хэш-функции совпадает с вычисленным значением. Атака с помощью таймера (timing attack): Этот тип атак основан на последовательном измерении времен, затрачиваемых на выполнение операции возведения в стенень по модулю целого числа. Ей подвержены по крайней мере следующие шифры: RSA, Диффи-Хеллман и метод эллиптических кривых.



Квантовый компьютер




В августе 2000 года корпорация IBM объявила о разработке первого в мире квантового компьютера. Экспериментальная модель, построенная на пяти атомах, продемонстрировала потенциал систем такого рода, решая определенные задачи со скоростью, значительно превышающей быстродействие обычных компьютеров. Что получится, если количество работающих атомов увеличить до тысячи? А до миллиона? Как признался руководитель группы ученых из IBM, Стэнфордского университета и Университета Калгари Исаак Чуанг (Isaac Chuang), квантовый компьютер можно использовать, в частности, и для взлома криптографических шифров.

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

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



Малая скорость стойких криптоалгоритмов


Это основной фактор, затрудняющий применение хороших алгоритмов в, например, системах "тотального" шифрования или шифрования "на лету". В частности, программаNorton DiskReet, хотя и имеет реализацию DES, при смене пользователем ключа может не перешифровывать весь диск, т.к. это займет слишком много времени. Аналогично, программа компрессии "на лету" Stacker фирмы Stac Electronics имеет опцию закрытия паролем компрессируемых данных. Однако она не имеет физической возможности зашифровать этим паролем свой файл, обычно имеющий размеры в несколько сот мегабайт, поэтому она ограничивается очень слабым алгоритмом и хранит хэш-функцию от пароля вместе с защищаемыми данными. Величина криптостойкости этой функции была исследована и оказалась равной 28, т.е. пароль может быть вскрыт тривиально.



Наличие люков


Причины наличия люков в криптосистемах очевидны: разработчик хочет иметь контроль над обрабатываемой в его системе информацией и оставляет для себя возможность расшифровывать ее, не зная ключа пользователя. Возможно также, что они используются для отладки и по какой-то причине не убираются из конечного продукта. Естественно, что это рано или поздно становится известным достаточно большому кругу лиц и ценность такой криптосистемы становится почти нулевой. Самыми известными примерами здесь являются AWARD BIOS (до версии 4.51PG) с его универсальным паролем "AWARD_SW" и СУБД Paradox фирмы Borland International, также имеющая "суперпароли" "jIGGAe" и "nx66ppx".

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



Наличие зависимости во времени обработки ключей


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

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

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



Недостатки датчика случайных чисел (ДСЧ)


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

Малый период и плохой разброс относятся к математическим недостаткам ДСЧ и появляются в том случае, если по каким-то причинам выбирается собственный ДСЧ. Иначе говоря, выбор плохого ДСЧ так же опасен, как и выбор плохого криптоалгоритма.

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

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

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

Такая ситуация имела место в программе Netscape Navigator версии 1.1. Она инициализировала ПСЧ, используя текущее время в секундах (sec) и микросекундах (usec), а также идентификаторы процесса (pid и ppid). Как выяснили исследователи Я. Голдберг и Д. Вагнер, при такой схеме как максимум получалось 47 значащих бит информации (при том, что этот датчик использовался для получения 40- или 128 (!)-битных ключей). Но, если у злоумышленника

была возможность перехватить пакеты, передаваемые по сети; и был доступ (account) на компьютер, где запущена программа,

то для него не составляло труда с большой степенью вероятности узнать sec, pid и ppid. Если условие (2) не удовлетворялось, то злоумышленник все равно мог попытаться установить время через сетевые демоны time, pid мог бы быть получен через демон SMTP (обычно он входит в поле Message-ID), а ppid либо не сильно отличается от pid, либо вообще равен 1.

Исследователи написали программу unssl, которая, перебирая микросекунды, находила секретный 40-битный ключ в среднем за минуту.



Недостаточная защищенность от РПС


РПС (разрушающие программные средства) - это компьютерные вирусы, троянских кони, программные закладки и т.п. программы, способные перехватить секретный ключ или сами нешифрованные данные, а также просто подменить алгоритм на некриптостойкий. В случае, если программист не предусмотрел достаточных способов защиты от РПС, они легко способны нарушить безопасность криптосистемы. Особенно это актуально для операционных систем, не имеющих встроенных средств защиты или средств разграничения доступа - типа MS DOS или Windows 95,98,ME

Перехват пароля. Как пример можно привести самый старый способ похищения пароля, известный еще со времен больших ЭВМ, когда программа-"фантом" эмулирует приглашение ОС, предлагая ввести имя пользователя и пароль, запоминает его в некотором файле и прекращает работу с сообщением "Invalid password". Для MS DOS и Windows существует множество закладок для чтения и сохранения паролей, набираемых на клавиатуре (через перехват соответствующего прерывания), например, при работе утилиты Diskreet v. 6.0. Подмена криптоалгоритма. Примером реализации этого случая является закладка, маскируемая под прикладную программу-"ускоритель" типа Turbo Krypton. Эта закладка заменяет алгоритм шифрования ГОСТ 28147-89, реализуемой платой "Krypton-3" (демонстрационный вариант), другим, простым и легко дешифруемым алгоритмом. Троянский конь в электронной почте. Очень часто используемый способ похищения секретных данных, в письме приходит исполнимый файл, который маскируют под что нибудь полезное (игру, картинку и.т.д.).



Неправильная реализация криптоалгоритмов


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



Ошибки в программной реализации


Ясно, что пока программы будут писаться людьми, этот фактор всегда будет иметь место. Хороший пример - ОС Novell Netware 3.12, где, несмотря на достаточно продуманную систему аутентификации, при которой, по заявлениям фирмы Novell, "нешифрованный пароль никогда не передается по сети", удалось найти ошибку в программе SYSCON v. 3.76, при которой пароль именно в открытом виде попадает в один из сетевых пакетов. Этого не наблюдается ни с более ранними, ни с более поздними версиями этой программы, что позволяет говорить именно о чисто программистской ошибке. Этот ошибка проявляется только если супервизор меняет пароль кому-либо (в том числе и себе). Видимо, каким-то образом в сетевой пакет попадает клавиатурный буфер.



Отсутствие проверки на слабые ключи


Некоторые криптоалгоритмы (в частности, DES, IDEA) при шифровании со специфическими ключами не могут обеспечить должный уровень криптостойкости. Такие ключи называют слабыми (weak). Для DES известно 4 слабых и 12 полуслабых (semi-weak) ключей. И хотя вероятность попасть в них равняется ~2·10-16, для серьезных криптографических систем пренебрегать ей нельзя.

Мощность множества слабых ключей IDEA составляет не много - не мало - 251 (впрочем, из-за того, что всего ключей 2128, вероятность попасть в него в 3·107 раз меньше, чем у DES).



Почему криптосистемы ненадежны?


Ненадежность большинства криптосистем можно охарактеризовать следующими причинами:



Повторное наложение гаммы шифра


Уже классическим примером стала уязвимость в Windows 3.x и первых версиях Windows 95, связанная с шифрованием. В этом случае программисты фирмы Microsoft, хорошо известные своими знаниями в области безопасности, применяли алгоритм RC4 (представляющем собой ни что иное, как шифрование гаммированием), не меняя гаммы, несколько раз к разным данным - сетевым ресурсам, хранящимся в файлах типа .pwl.

Оказалось, что один из наборов данных файла .pwl представлял из себя более чем специфичный текст - 20-символьное имя пользователя (в верхнем регистре) и набор указателей на ресурсы (см. рис. 2). Таким образом, угадав им пользователя (которое в большинстве случаев к тому же совпадает с именем файла) можно вычислить по крайней мере 20 байт гаммы. Т.к. гамма не меняется при шифровании других ресурсов (в этом состоит основная ошибка применения RC4 в этом случае), могут быть вычислены первые 20 байт всех ресурсов, в которые входит длина каждого из них. Вычислив длину, можно найти значения указателей и тем самым прибавить еще несколько десятков байт к угаданной гамме. Этот алгоритм реализован в известной программе glide.



Распределенные вычисления


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

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

Метод «распределенного взлома» зачастую используют некоммерческие организации для выяснения криптостойкости алгоритмов.

При применении распределенных вычислений на суперкомпьютерах возможно вскрытие методом грубой силы 75 битных ключей в приемлимый срок.



Суперкомпьютеры


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

Компьютер

Производительность (FLOPS)

56 бит

64 бит

70 бит

75 бит

96 бит

128 бит

Intel ASCII Red 1068*106 8.6 часа 3.2 мес. 17 лет 561 год 38.8*105 лет 3.4*1017 лет
Hitachi Tsukba CP-PAC 368*106 25.8 часа 9.3 мес. 51 год 1628 лет 106*105 лет 9.9*1017 лет
SGI/Cray T3E 265*106 34.6 часа 25.8 мес. 70 лет 2261 год 148*105 лет 137*1017 лет



Уменьшение криптостойкости при генерации ключа


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

Во многих (старых) версиях UNIX пароль пользователя обрезается до 8 байт перед хэшированием. Любопытно, что, например, Linux 2.0, требуя от пользователей ввода паролей, содержащих обязательно буквы и цифры, не проверяет, чтобы 8-символьное начало пароля также состояло из букв и цифр. Поэтому пользователь, задав, например, достаточно надежный пароль passwordIsgood19, будет весьма удивлен, узнав, что хакер вошел в систему под его именем с помощью элементарного пароля password. Novell Netware позволяет пользователям иметь пароли до 128 байт, что дает (считая латинские буквы без учета регистра, цифры и спецсимволы) 68128 ~2779 комбинаций. Но при этом, во-первых, хэш-функция получает на входе всего лишь 32-байтовое значение, что ограничивает эффективную длину пароля этой же величиной. Более того, во-вторых, на выходе хэш-значение имеет длину всего 128 бит, что соответствует 2128 комбинаций. Это дополнительно снижает эффективную длину до =21 символа, т.е. в 6 раз по сравнению с первоначальной. Полностью аналогичная ситуация происходит с архиватором RAR версий 1.5x - выбор пароля больше 10 символов не приводит к росту времени, необходимого на его вскрытие.

Если длина пароля "сверху" в этом случае определяется реализацией криптоалгоритмов, то ограничение на длину "снизу" уже связано с понятием единицы информации или энтропии. В рассмотренном примере с Novell Netware для создания хэш-значения с энтропией 128 бит длина пароля должна быть не менее =69 бит или не менее 22 символов. То, что многие криптосистемы не ограничивают минимальную длину пароля, как раз и приводит к успеху атак перебором не ключей, а паролей.



Взлом криптоалгоритмов




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

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

На современном этапе развития вычислительной техники ключи длиной 40 бит(большинство криптографических программ попадающих под экспортные ограничения США) легко вскрываются на мощном PC, вскрытие 56 битных ключей возможно на специальной апаратуре за несколько часов, 64 битные ключи поддаются вскрытию с использованием распределенных вычислений, что с успехом было доказано проектом http://www.distributed.net/, в наличии спецслужб имеются компьютеры вскрывающие 80 битные шифры. В принципе можно предположить, что в ближайшем будующем (15-20 лет) станет возможным вскрытие 128 битных ключей. Вскрытие 256 битных ключей физически не реализуемо, так как при минимальном энергопотреблении взламывающего вычислителя (оно определяется исходя из квантовой теории) оказывается, что для обеспечения энергией такого вычислителя необходимо рвануть сверхновую.

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



В силу всего вышесказанного, считать


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

© Copyright RemSoft Production 2004
#bn { DISPLAY: block } #bt { DISPLAY: block }

Запрещенные приёмы


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

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

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