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

[160].

Но алгоритм DES нестоек к перебору! Он не требует больших объемов вычислений и допускает существование эффективных реализаций. В среднем случае злоумышленнику потребуется 1+k+k²+k³+k⁴+k⁵+k⁶+k⁷ операций [161] для подбора пароля, где k максимально допустимое количество символов, использующихся для составления пароля [162]. Это намного меньше ожидаемого количества операций, необходимых для подбора четырнадцати символьного пароля!

1+k+k²+k³+k⁴+k⁵+k⁶+k⁷ «(1+k+k²+k³+k⁴+k⁵+k⁶+k⁷⁺+k⁸+k⁹+k¹⁰+k¹¹+k¹²+k¹³+k¹⁴)*1/2, где знак “«” обозначает «намного меньше». И пароль, состоящий из восьми и более символов, окажется ничуть не сложнее пароля, состоящего всего из семи символов! Фактически система запрашивает два семисимвольных пароля и обрабатывает их независимо друг от друга [163].

Причем, пароли, состоящие менее чем из восьми символов, легко распознать! Если пароль, введенный пользователем, оказывается меньше четырнадцати символов, то система расширяет его до требуемой длины нулями. Пусть пользователь ввел пароль из семи или менее символов, тогда P_8…14 = 0, а DES(0) - ^{P 8…14}® 0xAAD3B435B5140EE - однако, константа! (А, разработчики, однако, чукчи).

Поэтому, если старшие восемь байт LM-хеша равны 0xAAD3B435B5140EE, то исходный пароль состоит из семи или менее символов. Впрочем, на результаты поиска это не оказывает сильного влияния (дальше будет объяснено почему).

Если оптимизировать алгоритм, то скорость перебора можно увеличить вдвое! В самом деле, совершенно ни к чему дважды вычислять значение функции DES в уравнении 1 и в уравнении 2, поскольку области определения обеих функций одинаковы. Следовательно, для каждого P достаточно один раз вычислить значение DES(0) и поочередно сравнить его с H_1…8; и с H_9…16. Если пренебречь временем, затраченным на сравнение значения функции с H_1…8 и H_9…16 (а их для ускорения можно поместить в один 16-разрядный регистр), то скорость перебора возрастет вдвое!

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

Поскольку хеш представляет собой 16-байтовую строку, то всего возможно 2¹²⁸ комбинаций, то есть перебор потребует нереальных вычислительных мощностей, недоступных злоумышленнику. Даже для современных суперкомпьютеров эта задача слишком сложна. Если, конечно, реализация алгоритма DES свободна от ошибок [164].

А такие ошибки и в самом деле есть - функция 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⁷).