Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Разумеется, только для одного-единственного р мы получим исходную последовательность 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:\SOURCE\ASM_C\PAROLE\parole.asm, а выше приводится только ключевой фрагмент. Предложенный алгоритм исключительно прост и быстр; при этом он достаточно гибок и может быть применен для произвольных перечисленных множеств.
Тот же алгоритм изящно выражается одной строкой на языке Си (file: //CD:\SOURCE\VC\PAROLE\parole.cpp):
while ((pasword[index++] ++) >' z') pasword [index-1] =' ';
Математический смысл сводится к последовательному перебору всех элементов множества [ ‘ ’,'z’] путем добавления единицы с учетом переноса. Т.е. эту функцию иначе можно назвать INC х, где х— число практически неограниченной разрядности.
Данный алгоритм относится к числу простейших, но для практического применения не годится. Нам необходимо перебирать пароли из произвольного множества символов. Данный пример работает на единственном интервале [х1, хn] линейного множества С.
Вот тут нам и пригодится математика! В самом деле, усложнять алгоритм нет никакой нужды, достаточно лишь отобразить линейное множество С на перечисленное Z.
Дата публикования: 2014-11-18; Прочитано: 330 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!