Хеши. Односторонние функции

"Ночь — это туннель, — подумала она. — Это дыра в завтра, если только оно наступит, это завтра."

Ф. Херберт. "Дюна".

Вся современная криптография основана на использовании методов хеширо­вания. Метод хеширования позволяет хранить элементы множества А в линейном массиве X. Математически это можно записать:

h: А -> {0,х-1}

Это читается; функция h отображает каждый элемент А в индекс множества X. Поскольку число элементов А, как правило, намного больше X, то функция h наверняка неинъективна.

Однако возможно существование такого интервала на области определения функции, в границах которого она становится инъективной. Это означает, что только для одного элемента А существует индекс х1. Функция будет инъективной и в том случае, если ни один элемент А не отображается на интервал {х1,х2} при условии, что последний не равен нулю. В любом другом случае на каждый индекс множества Х отображается более одного элемента А. Это так называемая коллизия хеш-функции.

Реверс хеш-функции заключается в поиске всех отображаемых на данный индекс элементов. Для любого конечного множества А это разрешимая задача, которая имеет наиболее простое решение на инъективных интервалах хеш-мно­жества.

Давайте остановимся на инъективных интервалах. Невозможно практическое использование хеш-преобразований без понимания их значения. В качестве примера рассмотрим следующую задачу: пусть нам требуется эффективный алгоритм сравнения строк, допустим, для синтаксического анализатора. Простое посимвольное сравнение потребует значительной памяти для хранения образов строк. Представим все возможное множество строк в данной разрядной сетке массивом S, тогда мы можем хеш-преобразованием привести его к множеству b {0,OxFF}. Разумеется, b много меньше S и требует для хранения значительно меньше памяти.

Рассмотрим практическую реализацию для некоторого множества команд IF', THEN', 'BEGIN', 'END'. Выберем простейшую хеш-функцию, посимвольно скла­дывающую элементы строки. Это плохая хеш-функция (ниже мы поясним поче­му), но для нашего примера ее будет достаточно.

Для начала нужно построить хеш-таблицу значений для всех элементов множества S.

Воспользуемся для этого программой file://CD:\SOURCE\VC\hashOO — "хеш-калькулятор". Рассмотрим ее ключевой фрагмент:

BYTE GetHash (CString s0)

(

BYTE hash=0;

for (int a=0; a<s0.GetLength();a++)

hash=hash+s0[a]; // Вычисляем хеш-сумму

return hash;

}

Мы посимвольно складываем элементы множества символов s0, получая в результате некоторый элемент из множества calc {0,OxFF}. Как нетрудно видеть, на каждый элемент множества calc отображается не более чем один элемент S. Таким образом, в заданных рамках функция calc=calc+s0[a] инъективна. Следо­вательно, для заданного индекса единственным образом определяется элемент S. Этим доказывается корректность работы хеш-анализатора.

Ниже приведен фрагмент реально работающего эмулятора виртуального про­цессора GetMe01 (file://CD:\SOURCE\ASM_C\CRACKme\GetMe01.asm).

LEA SI, Buffer; Буфер исполнительных команд

start_r:

CALL GetHashe; Вычисление хеш-суммы очередной команды
CALL CallIt; Вызов обработчика для данной команды
MOV SI,DI; Позиционирование указателя команд
CALL Seek;-//-
JMP short start_r; — [uncond] -------------------------------------------

GetHashe PROC NEAR

PUSH SI; Сохраняем виртуальный указатель команд
XOR АХ,АX; АН == сумматор

gh_Repeat:; <——------------------------------------------------------
LODSB; Берем очередной элемент множества s0
ADD AH,AL; Добавляем в сумматор
XOR AL,':'; Проверка на конец команды
JNZ gh_Repeat; —([SI] <>': ' }----------------------------------

POP DI; si—>di; return SI

RETN; --\

ENDP

Seek PROC HEAR

s_repeat:;---------------------------------------------------------------

LODSB; Взять "следующий символ

OR AL,AL; Проверить на равенство нулю

JNZ s_repeat; —([SI]<>NULL)—--------------------------

RETH; ~-\

ENDP

CallIt Proc NEAR

PUSH SI; Сохранить SI

LEA SI,TableOf Range; Таблица указателей на обработчики

XCHG AХ,ВХ; ВН == AL

ci_rep:;-----------------------------------------------------

LODSB; Читаем очередную хеш-сумму
OR AL,AL; Конец таблицы?
JZ _err; --достигнут конец таблицы-~>
СМР AL,BH;- Хеш найден?
lodsw; Читаем очередное смещение обработчика
JNZ ci_rep; —('.Hash)—--------------------------------------

XCHG AХ,ВХ; ВХ == AX == смещение обрабочика
POP SI; восстановить SI
CALL ВХ; Вызвать обработчик данной команды
RET.- —\

_err:; Исключительная ситуация. Неверная команда

MOV АН, 9; Печать строки MS-DOS
LEA DX,errr; Смещение печатаемой строки
IНТ 21h

mov AH,4Ch; Завершение работы
INT 21h; --\

errr DB 'неизвестная команда', 0Dh,OAh,'$'
ENDP

; //////////////////////////////////////////////////////////////////////////
; // ТАБЛИЦА ПОДДЕРЖИВАЕМЫХ КОМАНД И СООТВЕТСТВУЮЩИХ ИМ ОБРАБОТЧИКОВ
; //—-——-
TableOfRange:

DB 0EFh; Хеш-сумма команды

DW offset Proc1; Обработчик данной команды

DB 0E3h

DW offset Proc2

DB 79h

DW offset РгосЗ

DB 0E6h

DW offset Proc4

DB 01h

DW offset Proc5

DB 0D1h

DW offset Proc7

DB 054h

DW offset Proc8

DB 0ADh

DW offset Proc9

DB 0; конец таблицы

Buffer:; Буфер исполнительных команд

Данный пример хранит восьмибитную хеш-сумму каждой команды. Следова­тельно, независимо от длины используемых команд для хранения потребуется всего N байт памяти (где N — число команд), что существенно меньше объема, необходимого для полного хранения тех же самых команд. Теоретически восьми­битная хеш-сумма может вместить до OxFF+l команд. Однако практически предложенная реализация при добавлении некоторого числа команд окажется неработоспособной. Это случится, когда двум разным командам будет соответст­вовать одна и та же хеш-сумма. В таком случае математики говорят о коллизии хеш-функции. Следовательно, на выбранном интервале хеш-функция становится неинъективной и для рассматриваемой задачи непригодной.

Казалось бы, если множество S намного больше X, то любая хеш-функция на полной области определения S окажется неинъективной. На самом деле число элементов S практически всегда много меньше его мощности. Например, множе­ство слов русского языка представляется множеством последовательностей от одного до десяти и более символов, но общее число существующих слов заведомо меньше OxFFFFFFFF. Поэтому возможно существование 32-битной инъективной хеш функции для синтаксического анализатора русского языка.

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

Наиболее часто используется и хорошо изучен мультипликационный метод отображения. Математически его можно выразить как h(S[x])=C*S[x] mod N, где N — это число элементов хеш-множества или другими словами его мощность. С — любая константа из интервала [О,N). При С=1 эта формула приобретает вид h(S(x])=S[xl mod N и является самостоятельным хеш-преобразованием, называе­мым методом остатка. Данный алгоритм также широко используется и для генерации псевдослучайных чисел. И неудивительно, ведь генераторы случайных чисел являются ничем иным, как хеш-преобразованием!

К числу наиболее популярных принадлежит также необычайно мощная функция CRC32 (сгс16): cyclic redundancy check (код циклического контроля). Эта функция в первую очередь призвана подтверждать неискаженность выбранной числовой после­довательности. Это еще одна область применения хеш-преобразований. А на самом деле здесь осуществляется все то же хеш-сравнение. Конечно, существует опреде­ленная вероятность таких искажений, которые не отразятся на хеш-сумме, но она достаточно невелика при условии хорошего рассеяния и чувствительности к незна­чительным изменениям выбранного хеш-преобразования.

CRC32 — это многократно проверенная, быстродействующая качественная хеш-функция, дающая превосходный результат. Для большинства последователь­ностей она будет инъективна. Так, например, многие текстовые редакторы реализуют синтаксическую "подсветку" именно на основе CRC32, не вызывая при этом коллизий.

Рассмотрим алгоритм этой функции. Целую беззнаковую 32-х битовую пере­менную инициализируем значением OFFFFFFFFh. Далее умножаем на 2 аргумент функции и значение CRC. Если старшие биты окажутся не равны, тогда CRC = CRC XOR OxEDB88320, И так до последнего бита аргумента. Если аргумент — строковая (или какая-либо другая) последовательность, то операции проводятся над двойными словами. В каноническом варианте в конце цикла требуется инвертировать все биты CRC, но это важно только для совместимости результатов, полученных разными функциями, и никак не сказывается на качестве. "Магическое число" 0xEDB88320 есть стандартный полином, менять который не следует, так как это ухудшит качество функции.

Может возникнуть такая ситуация, когда требуемое число элементов хеш-мно­жества будет заметно меньше, чем 2^32. Чтобы избежать лишних расходов, умножают результат сам на себя и берут N старших бит так, чтобы 2^N было по возможности близко к требуемому значению. Смысл этой операции в том, чтобы получить битовую последовательность, чувствительную ко всем битам значения CRC.

Рассмотрим теперь применение хеш-преобразований в криптографии. Од­ной из задач последней является проверка достоверности пароля. Для этого используют особые хеш-функции. Почему поступают так мы поймем, рассмот­рев принцип действия криптосистем. Пусть имеется некоторая криптографиче­ская функция F, расшифровывающая паролем р последовательность Ai в последовательность Aj.