F(Ai) —P--->Aj

Разумеется, только для одного-единственного р мы получим исходную после­довательность Aj, а для всех остальных р — "мусор". Каким способом можно удостовериться в том, что полученная Aj и есть искомая последовательность (при условии что самой последовательности в наличии не имеется)? Можно сохранить фрагмент исходной последовательности и затем сверить его с полученным резуль­татом. Однако это делает возможной атаку по открытому тексту на шифр и, кроме того, очень ненадежно, так как совпадение одного фрагмента не обязательно обеспечивает совпадение всей последовательности.

Вот тут-то на помощь и приходит хеш-преобразование. Мы можем вычислить CRC32 для исходного текста. Сравнивая его с CRC32 Aj, мы можем проверить правильность расшифровки. Поскольку количество Aj наверняка больше 2^32, то хеш-функция окажется неинъективной и хеш-значение не даст никакого представ­ления об исходной последовательности.

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

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

Функция f: Х —> Y называется односторонней, если f(x) может быть легко вычислена для любого элемента X, тогда для всех элементов Y вычисление такого аргумента х, для которого f(x) = у, не разрешимо полиномиально. Ясно, что CRC32 не является односторонней функцией и, невзирая на распространенное мнение, подлежит реверсированию. Поскольку для каждого значения х CRC32 существует бесконечное множество верных аргументов А, таких что F:CRC32(A) = х, то получение множества подходящих аргументов А' ничем не помогает нахождению в нем искомого элемента. Именно этим и вызвано широкое (и, между прочим, не оправданное) применение CRC32 в криптографии. Односто­ронность этой функции держится всего лишь на ее неинъективности. Однако, как было показано выше, возможно существование такого интервала I, на котором выбранная хеш-функция является инъективной. Практически во всех популярных криптосистемах не делается никаких попыток проверки принадлежности хеширу-емых данных к этому интервалу. Более того, для любого конечного перечислен­ного множества Z возможен как прямой (предвычисленный), так и обратный реверс хеш-функции. CRC32 успешно обращается полиномиально. И, как следст­вие, часто становится уязвимым местом криптозащит.

Рассмотрим табличное реверсирование. Для этого вычислим CRC32 каждого элемента перечисленного множества Z и сравним ее с исходной. Среди получен­ных элементов находится по крайней мере один действительный пароль. Множе­ство Z в нашем случае это множество возможных паролей. Нетрудно вычислить, что даже для восьмисимвольных паролей потребуется по крайней мере 4^8 (или 2^16) байт памяти для хеш-сумм и еще больше для хранения образа паролей. Кроме того, потребуется очень большое число итераций.

Поэтому особый интерес представляет обратный полинормальный алгоритм. Заметим сразу — он является полинормальным только для конечных перечислен­ных множеств. А выглядит для каждого бита обращенного аргумента так:

b == !Hibit(xor (crc32,0xEDB88320)) | Hibit(crc32)

Предположим, что каждый бит аргумента может являться как нулем, так и единицей. Проверим оба результата на принадлежность к множеству Z и отбро­сим ненужные. Если оба значения принадлежат Z, то запоминаем оба и дальше вычисляем оставшиеся биты для обоих из них — и так до тех пор, пока не будет отброшен последний элемент, как не принадлежащий к множеству Z. Иначе говоря, мы строим бинарное дерево. Очень легко подсчитать необходимое число итераций для нахождения всех возможных паролей. Кроме того, для этой ситуа­ции применимы все эффективные алгоритмы, работающие с двоичными деревья­ми. Сбалансированное двоичное дерево позволит эффективно реверсировать CRC32 даже в случае большого рассеяния элементов Z. Т.е. мы можем быстро проверить, не является ли этот хеш контрольной суммой какого-нибудь словарно­го слова. Обратное преобразование осуществит эту проверку намного быстрее, чем прямой перебор множества словарных слов. Подробнее операции с двоичны­ми деревьями изложены в книге Майкла Ласло "Вычислительная геометрия и компьютерная графика на C++" (Москва, БИНОМ, 1997) и во многих других изданиях. Очень рекомендую ознакомиться с конспектами лекций Манфрейда Броя "ИНФОРМАТИКА" (Диалог-Мифи, 1998).

А мы не будем на этом больше задерживаться и рассмотрим алгоритмы генерации любой заданной последовательности ключей. Атака перебором — это один из вариантов вскрытия односторонних хеш-функций. Все криптосистемы строятся с учетом того, что полный перебор ключей займет заведомо чрезмерно большой промежуток времени. Ситуации с выбором короткого пароля мы безжа­лостно отбросим. Не то чтобы они были достаточно редки, но уповать на это очень рискованно: отнюдь не гарантировано, что данные попытки увенчаются успехом. Однако в ряде случаев возможен ограниченный перебор ключей. Так, например, в архиваторе гаг ранних версий любой пароль преобразовывался в 80-битовую хеш-последовательность. Перебором 2^80 вариантов можно было вскрыть любой, сколь угодно длинный пароль. С другой стороны, для паролей, состоящих менее чем из восьми символов, необходимо было перебрать гораздо меньшее число вариантов. Таким образом, нам нужно построить последовательность всех воз­можных вариантов для перебора. Она будет очень велика, но вполне разрешима за приемлемое время.

Чтобы научиться строить эффективные алгоритмы, необходимо хотя бы вкратце ознакомиться с теорией формальных языков. Алфавитом является конечное перечис­ленное множество А. Множество всех конечных последовательностей элементов А называется формальным языком. Языки оперируют словами. Для заданного множе­ства А последовательность элементов х1...хn, принадлежащих А, образует слово длины п, которое записывается как <х1...хn>. Множество всех слов равняется АхАх...хА, что принято записывать как А*. Для каждого слова формального языка существует отображение length:A*—> N, где N — длина слова.

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

Для начала рассмотрим простейший алгоритм генерации паролей, построен-

MOV АН, 9h ; Телетайпный вывод
LEA SI, Password ; Начальный пароль
MOV DX, SI ; для f.9/lnt 21h

NextPassword: ; Генерация следующего пароля

ХОR ВХ, ВХ ; С нулевого разряда

CheckOver: ; проверка на переполнение
INC Byte Ptr DS:[SI+BX] ; Увеличиваем первый слева символ
CMP Byte Ptr DS:[SI+BX],'z' ; Выход за допустимые границы?
JB WritePassword ; —{Нет переноса}—

mov Byte Ptr [SI+BX], ' ' ; Сбрасываем текущий разряд

INC ВХ ; перенос на следующий разряд

jmp short CheckOver ; __________________________________

WritePassword: ; вывод пароляна экран

IНТ 21h ;-//-

JMP SHORT NextPassword ;—

Password DB 8 Dup(' ') ;<—начальный пароль

DB 13, 10, '$' ; <—конец строк-и

Полный исходный текст находится на file://CD:SOURCEASM_CPAROLEparole.asm, а выше приводится только ключевой фрагмент. Предложенный алгоритм исключительно прост и быстр; при этом он достаточно гибок и может быть применен для произвольных перечисленных множеств.

Тот же алгоритм изящно выражается одной строкой на языке Си (file: //CD:SOURCEVCPAROLEparole.cpp):

while ( (pasword[index++] ++) >' z' ) pasword [index-1] =' ' ;

Математический смысл сводится к последовательному перебору всех элемен­тов множества [‘ ’,'z’] путем добавления единицы с учетом переноса. Т.е. эту функцию иначе можно назвать INC х, где х— число практически неограниченной разрядности.

Данный алгоритм относится к числу простейших, но для практического применения не годится. Нам необходимо перебирать пароли из произвольного множества символов. Данный пример работает на единственном интервале [х1, хn] линейного множества С.

Вот тут нам и пригодится математика! В самом деле, усложнять алгоритм нет никакой нужды, достаточно лишь отобразить линейное множество С на перечис­ленное Z.