Вычисление хеш-функций

Все хеш-функции вычисляются следующим образом. Входное значение (сообщение, файл и т.п.) рассматривается как последовательность n-битных блоков. Входное значение обрабатывается последовательно блок за блоком, и создается m-битное значение хеш-кода.

Одним из простейших примеров хеш-функции является побитный XOR каждого блока:

С_i = b_i1 b_i2 . . . b_ik

Где

Сi - i-ый бит хеш-кода, 1 i n.

k - число n-битных блоков входа.

bij - i-ый бит в j-ом блоке.

- операция XOR.

В результате получается хеш-код длины n, известный как продольный избыточный контроль. Это эффективно при случайных сбоях для проверки целостности данных.

Часто при использовании подобного продольного избыточного контроля для каждого блока выполняется однобитный циклический сдвиг после вычисления хеш-кода. Это можно описать следующим образом.

• Установить n-битный хеш-код в ноль.

• Для каждого n-битного блока данных выполнить следующие операции:

  • сдвинуть циклически текущий хеш-код влево на один бит;

  • выполнить операцию XOR для очередного блока и хеш-кода.

Это даст эффект "случайности" входа и уничтожит любую регулярность, которая присутствует во входных значениях.

Хотя второй вариант считается более предпочтительным для обеспечения целостности данных и предохранения от случайных сбоев, он не может использоваться для обнаружения преднамеренных модификаций передаваемых сообщений. Зная сообщение, атакующий легко может создать новое сообщение, которое имеет тот же самый хеш-код. Для этого следует подготовить альтернативное сообщение и затем присоединить n-битный блок, который является хеш-кодом нового сообщения, и блок, который является хеш-кодом старого сообщения.

Хотя простого XOR или ротационного XOR (RXOR) недостаточно, если целостность обеспечивается только зашифрованным хеш-кодом, а само сообщение не шифруется, подобная простая функция может использоваться, когда все сообщение и присоединенный к нему хеш-код шифруются. Но и в этом случае следует помнить о том, что подобная хеш-функция не может проследить за тем, чтобы при передаче последовательность блоков не изменилась. Это происходит в силу того, что данная хеш-функция определяется следующим образом: для сообщения, состоящего из последовательности 64-битных блоков Х₁, Х₂,..., Х_N, определяется хеш-код С как поблочный XOR всех блоков, который присоединяется в качестве последнего блока:

С = Х_N+1 = X₁ X₂ . . . X_N

Затем все сообщение шифруется, включая хеш-код, в режиме СВС для создания зашифрованных блоков Y₁, Y₂, ..., Y_N+1. По определению СВС имеем:

Х₁ = IV D_K [Y₁]

Х_i = Y_i-1 D_K [Y_i]

Х_N+1 = Y_N D_K [Y_N+1]

Но X_N+1 является хеш-кодом:

Х_N+1 = X₁ X₂ . . . X_N =

(IV D_K [Y₁]) (Y₁ D_K [Y₂]) . . .

(Y_N-1 D_K [Y_N])

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

Первоначальный стандарт, предложенный NIST, использовал простой XOR, который применялся к 64-битным блокам сообщения, затем все сообщение шифровалось, используя режим СВС.