Техника сетевых атак

Касперски Крис

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

К шестнадцатибайтовому хеш - значению дописываются пять нулей, образуя последовательность из двадцати одного байта (16+5=21) обозначенную в этой книге как h_1…21.

Эта последовательность разрезается на три равных части по семь байт, обозначенные h_1…7, h_8…14, h_15…21.

Каждая их них используется в качестве ключа для шифровки challenge, переданного сервером, с помощью алгоритма DES.

Полученный результат (обозначенный как R) отсылается на сервер. Весь процесс математически можно выразить так:

1. DES(challenge) -

^h

^1…7

® R_1…8

2. DES(challenge) -

^h

^8…14

® R_9…16

3. DES(challenge) -

^h

^15…21

® R_17…24

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

Поскольку пять старших байт ключа h_15…21 известны заранее (они содержат нули, дописанные для расширения ключа до двадцатиоднобайтовой строки), то для решения уравнения DES(challenge) -

^h

^15…21

® R_17…24 необходимо перебрать всего два байта. В худшем случае это потребует 2¹⁶ операций, а в среднем вдвое меньше 2¹⁵. Если же длина пароля составляет менее восьми символов, то h₁₅…h₂₁ всегда равны 0x04EE0000000000, поэтому короткие пароли элементарно распознать с одного взгляда!

В свою очередь, это облегчает решение уравнения DES(0) -

^P

^8…14

®H_9…16, поскольку H_15…16=h_15…16. Перебором всех возможных значений P_8…14, всего за 1+k+k²+k³+k⁴+k⁵+k⁶+k⁷ операций можно найти всех «кандидатов» в пароли, которых будет не более чем (1+k+k²+k³+k⁴+k⁵+k⁶+k⁷⁾/2¹⁶.

Остается перебрать 2⁸*(1+k+k²+k³+k⁴+k⁵+k⁶+k⁷⁾/2¹⁶ комбинаций, чтобы среди «кандидатов» в ключи уравнения DES(challenge) -

^h

^8…14

® R_9…16 найти единственный действительный ключ.

Уравнение же DES(challenge) -

^h

^1…7

® R_1…8 решается перебором 1+k+k²+k³+k⁴+k⁵+k⁶+k⁷ вариантов в худшем случае и (1+k+k²+k³+k⁴+k⁵+k⁶+k⁷)/2 в среднем, а сравнения значений DES(0) -

^P

^1…7

®H_1…8;можно вести одновременно с DES(0)-

^P

^8…14

®H_9…16 сократив количество требуемых операций вдвое.

Но сколько времени [165] в худшем случае займет поиск пароля? Для этого необходимо знать величину k (количество допустимых символов) и скорость вычисления функции DES. В пароль могу входить: 10 цифр ‘0’-‘9’, 26 заглавных букв латинского алфавита ‘A’-‘Z’ и все 32 спецсимвола. Итого выходит 10+26+32=68. Следовательно, всего существует 68⁰+68¹+68²+68³+68⁴+68⁵+68⁶+68⁷=6 823 331 935 125 или приблизительно 7 x 10¹² комбинаций.

Скорость же вычисления функции DES в зависимости от производительности процессора и эффективности реализации алгоритма варьируется от стотысячных (на младших моделях процессора Pentium) до миллионных (Pentium III, XEON) долей секунды.

В худшем случае поиск пароля потребует 2¹⁶+(1+k+k²+k³+k⁴+k⁵+k⁶+k⁷)+2¹⁶*(1+k+k²+k³+k⁴+k⁵+k⁶+k⁷)/2¹⁶ операций, т.е. 2¹⁶+2*(1+k+k²+k³+k⁴+k⁵+k⁶+k⁷), а в среднем и того меньше: 2¹⁵+(1+k+k²+k³+k⁴+k⁵+k⁶+k⁷).

Если перебирать все возможные пароли со скоростью 500 000 операций в секунду, то поиск займет в худшем случае (65 536+ 2*6 823 331 935 125) / 500 000 = 27 293 328 секунд или около 316 дней, а в среднем порядка ста пятидесяти дней.

Но если перебирать пароли, состоящие из одних латинских символов, то в худшем случае процесс закончится за 33 412 секунд, то есть займет всего около девяти часов, а в среднем за срок, вдвое меньший - порядка четырех часов! (Разумеется, если искомый пароль действительно состоит из одних латинских символов).

Процесс перебора очень легко распараллелить, задействовав более одного компьютера. Группа злоумышленников, вооруженная десятком Pentium II способна гарантированно найти любой пароль менее чем за месяц. А если учесть, что пользователи склонны выбирать не абсолютно случайные, а в той или иной степени осмысленные пароли, этот срок можно заметно сократить.

Логотип программы L0phtCrack

Существует готовая программная реализация, описанной выше атаки, воплощенная в утилиту 10phtcrack, которая занимается подбором LM и NT хешей. Авторы разработки - некто L0pht Heavy Industries .

Разработчики L0phtCrack 2.5 - утверждают, что с ее помощью на Pentium II/300 более 90% паролей удается найти в течение 48 часов, а 18% паролей вскрываются менее чем за 10 минут!

Приведенные цифры интересны сами по себе. При условии криптостойкости алгоритма DES (а в его криптостойкости сомневаться не приходится), грубой силой небходимо перебрать по крайней мере порядка 1+k+k²+k³+k⁴+k⁵+k⁶+k⁷ комбинаций. И если бы L0PhtCrack 2.5 действовал тривиальным перебором, для обеспечения заявленной скорости перебора ему пришлось бы совершать (1+k+k²+k³+k⁴+k⁵+k⁶+k⁷)/(48*60*60) операций в секунду, то есть 6 823 331 935 125 / 172800 =39 486 874 - почти сорок миллионов вычислений функции DES каждую секунду. Даже старшие модели процессоров Pentium не обеспечивают такой производительности!