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

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

Из-за прежних ограничений патентного права алгоритм RSA не получил широкого распространения и до середины 1990-х годов применялся в основном в разработках компании RSA Security. Но сейчас можно встретить много программ, широко использующих алгоритм RSA. Прежде всего это программы PGP и Secure Shell (SSH). Сведения об алгоритме RSA были полностью раскрыты за две недели до истечения срока действия патента в сентябре 2000 года. Ныне алгоритм RSA свободно распространяется для любых целей.

«Грубая сила»

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

Основы метода «грубой силы»

В качестве примера рассмотрим велосипедный замок, который открывается набором ключевой комбинации из трех цифр. Каждая цифра – это число от 0 до 9. Открыть замок нетрудно, если располагать временем и если ключевая комбинация во время вскрытия замка не изменяется. Общее число всевозможных комбинаций (ключей) – 10 3, или 1000. Предположив, что велосипедный вор способен перебирать 30 комбинаций в минуту, определим, что в худшем для него случае он откроет замок приблизительно через 1000: 30 = 33 мин. При этом имейте в виду, что после выбора очередной комбинации число возможных комбинаций (ключевое пространство) уменьшается, а шансы угадать ключевую комбинацию на следующем шаге увеличиваются.

Метод «грубой силы» всегда приводит к успеху, потому что ключевое пространство, как бы велико оно ни было, всегда конечно. Противостоять «грубой силе» можно, увеличивая длину ключа и тем самым время расшифровки сообщения. В случае примера с велосипедным замком три цифры ключевого пространства позволят велосипедному вору украсть велосипед максимум за 33 мин. Поэтому для велосипедного вора в данном случае метод «грубой силы» выглядит привлекательным. Рассмотрим велосипедный замок с ключевой комбинацией из пяти цифр, для которого число возможных комбинаций равно 100 000. Теперь для подбора ключевой комбинации методом «грубой силы» потребуется 55,5 ч. Ясно, что большинство воров отказалось бы от этой затеи и искало бы более легкую добычу.

Суть метода «грубой силы» применительно к симметричным алгоритмам, например к DES, аналогична подбору ключевых комбинаций велосипедного замка. Именно таким образом алгоритм DES был взломан компьютером «Deep Crack» («Искусный взломщик»). Ключ DES состоит из 56 бит, поэтому при взломе проверялись все битовые комбинации ключа между строкой из 56 нулей и 56 единиц, пока не был найден нужный ключ.

В случае распределенных попыток взлома DES пример с пятицифровым велосипедным замком должен быть слегка изменен. Идею метода распределенной «грубой силы» можно проиллюстрировать на примере подбора ключевой комбинации несколькими ворами, действующими одновременно и имеющими в своем распоряжении точную копию велосипедного замка, закрытого одной и той же ключевой комбинацией оригинала. Предположим, что 50 воров пытаются одновременно подобрать ключевую комбинацию. Каждый из них должен перебрать 2000 комбинаций (подпространство ключей). Причем ни у каких двух воров подпространства ключей не пересекаются. В таком случае каждую минуту тестируется ни 30 комбинаций, а 1500 комбинаций в минуту, и все возможные комбинации могут быть проверены приблизительно за 67 мин. Вспомните, что ранее одному вору требовалось для подбора ключевой комбинации 55 ч, а 50 совместно подбирающих комбинации воров смогут украсть велосипед за время, едва превышающее 1 ч. Распределенные компьютерные приложения, основанные на тех же принципах, позволили Distributed.net взломать DES менее чем за 24 ч.

Использовать метод «грубой силы» к RSA и к другим криптосистемам с открытым ключом сложнее. Поскольку алгоритм RSA может быть раскрыт разложением ключа на сомножители, то при небольшой длине используемых ключей (намного меньше, чем любая программная реализация RSA смогла бы себе позволить) человек с помощью карандаша и бумаги сможет взломать алгоритм. Но для ключей с большим количеством битов время нахождения сомножителей ключа (время факторизации) резко возрастает. Кроме того, факторизацию трудно реализовать распределенными вычислениями. Атаки, основанные на распределенной факторизации, потребуют большей координации действий участников атаки, чем при параллельном подборе ключей из ключевого пространства. Известны проекты, например проект www-факторизации (www.npac.syr.edu/factoring.html), предназначенные для решения этих вопросов. В настоящее время в рамках проекта www-факторизации предпринимаются попытки разложить на сомножители ключи со 130 цифрами. Для сравнения 512-битовые ключи приблизительно состоят из 155 цифр.

Применение метода «грубой силы» для расшифровки паролей

Часто, особенно если доступен список зашифрованных паролей, для расшифровки паролей используется метод «грубой силы». Обычно точное число символов в пароле неизвестно, но в большинстве случаев справедливо полагать, что в пароле от 4 до 16 символов. Одному символу пароля может быть присвоено около 100 значений, поэтому число паролей изменяется от 1004 до 10016. Несмотря на внушительные числа, они конечны, поэтому пароль может быть определен с помощью атаки методом «грубой силы».

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

Обычно пароли хранятся в формате кэш-величин. После ввода пароля при помощи однонаправленных кэш-функций вычисляется его кэш-величина, например как это реализовано в алгоритме MD5 (Message Digest 5 – дайджест сообщения 5). Вычисленная кэш-величина запоминается. Функции кэширования однонаправлены в том смысле, что по кэш-величине практически невозможно восстановить данные, по которым она была вычислена. Серверу не обязательно знать пароли. Ему достаточно удостовериться, что пользователь знает свой пароль. При установлении подлинности пользователя вычисляется кэш-величина введенного им пароля, которая сравнивается с величиной, хранимой на сервере. При их совпадении подтверждается подлинность пользователя. В противном случае системой попытка подключения отвергается и в журнале регистрации сохраняются необходимые сведения.

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

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

Наиболее часто для вскрытия паролей методом «грубой силы» используются программы L0phtcrack для Windows и Crack and John the Ripper для UNIX. Их применяют не только зловредные хакеры. Специалисты в области безопасности считают их полезными при аудите компьютерных систем. Ведь зная, сколько времени потребуется на взлом пароля специалисту в области безопасности, можно приблизительно оценить время, необходимое злоумышленнику для того, чтобы сделать то же самое. Далее будет кратко рассказано о каждой их этих программ. Но помните, что всегда следует получить письменное разрешение системного администратора на их использование до начала применения любой из этих программ.