Трунов
Д.Н.
АЛГОРИТМ
КРИПТОГРАФИЧЕСКОЙ ХЕШ-ФУНКЦИИ CSA-3
Введение
Хеш-функция,
или функция свёртки, — функция,
осуществляющая преобразование входного
массива данных произвольной длины в
битовую строку фиксированной длины,
выполняемую определённым алгоритмом
[1]. Преобразование, производимое
хеш-функцией, называется хешированием,
исходные данные называются входным
массивом, прообразом или сообщением, а
результат преобразования — хешем,
хеш-кодом или контрольной суммой.
Применяемые
в криптографии хеш-функции должны быть
криптографически стойкими, то есть быть
необратимыми и обладать стойкостью к
коллизиям. Необратимая (однонаправленная)
хеш-функция — это функция, которая
работает только в одном направлении:
легко вычислить значение хеш-функции
по прообразу, но трудно создать прообраз,
значение хеш-функции которого равно
заданной величине. Стойкость к коллизиям
заключается в том, что трудно создать
два прообраза с одинаковым значением
хеш-функции.
Безопасность
однонаправленной хеш-функции заключается
именно в её однонаправленности. У выхода
нет видимой зависимости от входа.
Изменение одного бита прообраза приводит
к изменению, в среднем, половины битов
значения хеш-функции. Вычислительно
невозможно найти прообраз, соответствующий
заданному значению хеш-функции [2].
Идея
алгоритмов серии CSA
Требования
к хеш-функции определяются спецификой
решаемой задачи. Например, при вычислении
криптографических контрольных сумм
для файлов большого размера имеет
значение высокая скорость вычисления.
А вот при хешировании паролей в системах
аутентификации [3] важна не скорость, а
максимальная защита от вскрытия пароля
по его хеш-коду (потому в таких системах
часто применяется многократное
хеширование).
Хеш-функции
применяются также и в цифровых подписях
[4]. Однако область применения цифровых
подписей обычно подразумевает, что
вычисленный для подписи хеш-код будет
проверяться в пределах ограниченного
времени. Надёжность хеш-функции должна
быть достаточной, чтобы исключить
подделку документа за это ограниченное
время. Но как быть, если необходимо
исключить подделку документа за более
длительный промежуток времени? Как
вариант — повышать надёжность хеширования
и вычислять одновременно несколько
хеш-функций.
В
авторских алгоритмах серии CSA были
реализованы оба подхода. Идея заключалась
в том, чтобы производить вычисления с
большим количеством повторений цикла,
которое можно менять. Изменение количества
повторений цикла позволяет не только
регулировать скорость вычисления
(функция становится более универсальной),
но и вычислять несколько разных хеш-кодов
одной функцией (меняя параметры цикла).
Цель
разработки алгоритма CSA-3
Предшественником
разрабатываемого алгоритма является
CSA-2 [5]. В
сравнении с
распространёнными алгоритмами, например,
SHA-2 [6],
SHA-3 [7]
и ГОСТ
Р 34.11-2012 [8,9],
CSA-2
обладает следующими недостатками:
*
при
излишне большом размере блока
данных (1024 байта) не обеспечивается
должный
уровень взаимосвязи между его
элементами
при
малом количестве повторений цикла;
*
схема хеширования имеет сильную
зависимость от самих хешируемых данных;
*
громоздкий
двухступенчатый
способ
образования
хеш-кода: вначале код
получается размером
1024 байта, затем сжимается до 40 байт, из
которых формируется символьная строка
результата;
*
строка хеша может включать
символы
(например, «#», «@», «%» и другие), которые
некоторыми программами интерпретируются
непредсказуемым образом;
*
вероятность полного отсутствия изменений
результата при изменении одного бита
прообраза, предположительно, выше нуля
(хотя и очень маленькая);
*
элементарная
функция обработки каждого отдельного
элемента рабочего массива хотя и зависит
от нескольких других элементов, однако,
в конечном счёте, сводится к простой
операции сложения;
*
вычисления производятся над 32-битными
числами, хотя на современных процессорах
эффективнее выполнять 64-битные вычисления.
Разработка
алгоритма CSA-3
призвана устранить эти
недостатки
и
при этом
сохранить
главную идею: повышение надёжности за
счёт большого количества повторений
цикла и гибкая настройка этого
количества.
Класс
CSA3Hash. Общие принципы
Алгоритм
CSA-3 реализован в виде объектного класса
CSA3Hash, объявление которого на языке
программирования Object Pascal (Lazarus) приведено
ниже (полный текст алгоритма приведён
в приложении А):
const
MaxBufSz
= 512*1024; // размер файлового буфера
type
CSA3Hash
= class
private
M:
Array[0..7] of UInt64; // рабочий массив
_Cycles:
Cardinal; // количество циклов
шифрования
Sum:
UInt64; // контрольная сумма
N:
UInt64; // количество обработанных
байт
Passwd:
UnicodeString; // пароль (для парольного
хеша)
Buf:
Array[0..MaxBufSz-1] of Byte; // файловый буфер
Stopped:
Boolean; // состояние остановки
вычислений
protected
procedure
Init(Cycles: Cardinal);
procedure
Enc;
procedure
EncryptMass(Var Mass: Array of Byte; Size: Cardinal);
function
EncryptFile(FileName: String): Cardinal;
public
function
GetHash: String;
function
HashMass(Var Mass: Array of Byte; Size: Cardinal;
Cycles:
Cardinal): String;
function
HashString(S: UnicodeString; Cycles: Cardinal): String;
function
HashFile(FileName: String; Cycles: Cardinal): String;
procedure
SetPassword(Password: UnicodeString);
procedure
Stop;
end;
Хеширование
производится функциями HashMass, HashString и
HashFile соответственно для байтового
массива, текстовой строки в формате
Юникод (UTF-16) и файла. Функция GetHash
возвращает последний вычисленный
хеш-код, SetPassword позволяет установить
пароль хеширования, а процедура Stop —
остановить вычисления (запускается из
другого потока).
Общий
принцип хеширования заключается в том,
что байтовый массив, строка или файл
делятся на блоки по 64 байта и добавляются
к рабочему массиву M (предварительно
инициализированному процедурой Init),
который зашифровывается процедурой
Enc. Цикл шифрования выполняется столько
раз, сколько задано в поле _Cycles. В
шифровании также участвуют поля Sum
(контрольная сумма добавляемых данных)
и N (общее количество обработанных байт).
Из того же массива M впоследствии
формируется строка результата.
Процедура
EncryptMass
Процедура
EncryptMass организует разбивку хешируемого
массива на блоки, их добавление в рабочий
массив и запуск его шифрования. При
добавлении очередного блока в M все его
64 байта разбиваются на группы по 8 байт,
которые объединяются в числа типа UInt64
(64-битное целое без знака), а затем
присоединяются к соответствующему
элементу массива M при помощи операции
XOR (попутно добавляясь и к контрольной
сумме Sum):
for I :=
0 to 7 do
begin
P :=
@Mass[Pos + I * 8];
M[I]
:= M[I] XOR P^;
Sum
:= Sum + P^;
end;
Здесь
P — переменная ссылочного типа ^UInt64, а
Pos — позиция текущего 64-байтного блока
в хешируемом массиве.
Если
размер блока J меньше 64, то его содержимое
копируется в отдельный массив B, размером
64 байта. Первый свободный (после
скопированного блока) байт устанавливается
равным $80, а остальные (если есть)
заполняются нулями:
for I :=
0 to J - 1 do
B[I]
:= Mass[Pos + I];
B[J] :=
$80;
for I :=
J + 1 to 63 do
B[I]
:= 0;
Массив
B добавляется в M аналогично добавлению
блока из Mass. После добавления каждого
блока поле класса N увеличивается на
размер блока в байтах (64 для полного
блока или значение J для неполного).
После этого запускается процедура
зашифровки Enc.
Похожим
образом работает функция EncryptFile: файл
загружается в буфер, разбивается на
блоки, которые добавляются к массиву
M, а тот шифруется процедурой Enc.
Процедура
шифрования Enc
Процедура
Enc предназначена для зашифровки рабочего
массива M. Перед началом непосредственно
шифрования массив M копируется в массив
ключа шифрования K. Затем запускается
основной цикл шифрования (счётчик цикла
J меняется от 1 до _Cycles). Ещё один цикл
(счётчик I от 0 до 7) предусматривает
изменение каждого элемента массива
M[I], причём таким образом, чтобы он зависел
от всех элементов ключа K.
Поскольку
для каждого элемента массива M берутся
одни и те же элементы ключа, массив K
предполагается модифицировать перед
вычислением M[I]. Причём модификация
ключа подразумевает не изменение его
бит, а только смену их взаимного
расположения.
Первый
способ модификации ключа K выполняется
в виде циклических смещений (сдвигов)
его элементов и зависит от текущего
состояния рабочего массива M. Смещение
для 8 элементов ключа перед шифрованием
каждого из 8 элементов рабочего массива
предполагает 64 возможных смещения.
Какое из этих 64 смещений будет выполнено,
а какое — нет, устанавливается таблицей
сдвигов S, представленной в виде целого
64-битного числа. Смещение конкретного
элемента на конкретном этапе производится,
если соответствующий ему бит в S равен
1, иначе смещение не производится.
Для
расчёта S перед циклом изменения массива
M рассчитывается временная переменная
T, которая зависит от текущего значения
счётчика цикла J, значений всех элементов
рабочего массива M, а также текущего
количества обработанных уже байт N:
T := J;
for I :=
0 to 7 do
begin
Rot
:= T + M[I];
T :=
(Rot SHL 9) OR (Rot SHR 55);
end;
T := T
XOR N;
После
этого формируется значение S разбивкой
полученной переменной T на 8 байт и их
заменой по таблице Pi (операция B := T
подразумевает получение младшего байта
переменной T). В завершение над величиной
S и текущим значением контрольной суммы
Sum выполняется операция XOR:
S := 0;
for I :=
0 to 7 do
begin
B :=
T;
S :=
(S SHL 8) + Pi[B];
T :=
T SHR 8;
end;
S := S
XOR Sum;
Когда
значение S вычислено, запускается цикл
шифрования элементов массива M. В начале
этого цикла как раз производятся
циклические смещения вправо на 3 бита
элементов ключа K (по таблице S):
for L :=
0 to 7 do
begin
if S
AND 1 = 1 then
K[L]
:= (K[L] SHR 3) OR (K[L] SHL 61);
S :=
S SHR 1;
end;
После
этого ключ K дополнительно изменяется
по одной из двух схем: для чётных номеров
I весь массив ключа сдвигается влево на
15 бит как одно большое число, а для
нечётных — происходит перестановка
элементов K по таблице Tau:
if I AND
1 = 0 then
begin
T :=
K[0] SHR 49;
for
L := 0 to 6 do
K[L]
:= (K[L] SHL 15) OR (K[L+1] SHR 49);
K[7]
:= (K[7] SHL 15) OR T;
end
else
begin
for
L := 0 to 7 do
K1[L]
:= K[L];
for
L := 0 to 7 do
K[L]
:= K1[Tau[L]];
end;
После
этого выполняется непосредственно
шифрование элемента M[I]. Вначале в этом
участвуют часть элементов ключа K:
Rot :=
M[I] XOR (K[0] AND K[4]);
M[I] :=
(Rot SHL 17) OR (Rot SHR 47);
Rot :=
M[I] XOR (K[1] OR (NOT K[5]));
M[I] :=
(Rot SHL 19) OR (Rot SHR 45);
Rot :=
M[I] XOR (NOT (K[2] XOR K[6]));
M[I] :=
(Rot SHL 13) OR (Rot SHR 51);
Далее
к этому прибавляется зашифровка M[I] при
помощи соседнего к нему элемента и
операции замены по таблице Pi (как в
случае с вычислением величины S):
if I = 0
then
T :=
M[I] + M[7]
else
T :=
M[I] + M[I - 1];
M[I] :=
0;
for L :=
0 to 7 do
begin
B :=
T;
M[I]
:= (M[I] SHL 8) + Pi[B];
T :=
T SHR 8;
end;
Наконец,
завершается зашифровка M[I] при помощи
оставшихся незадействованными элементов
ключа K:
Rot :=
M[I] XOR (NOT (K[3] AND K[7]));
M[I] :=
(Rot SHL 3) OR (Rot SHR 61);
Таблица
замен Pi подобрана таким образом, чтобы,
вычисляя I := Pi[I] в цикле, можно было обойти
всю таблицу. Похожим образом устроена
и таблица Tau: перестановки с её помощью
в массиве K позволяют произвести 8
перестановок, пока все элементы станут
на свои первоначальные места. В процедуре
таблицы Pi и Tau объявлены следующим
образом:
Pi:
Array[0..255] of Byte = (
$20,
$19, $CC, $78, $DA, $C4, $24, $A4, $03, $27, $E1, $E5, $2E, $BD, $F2,
$08,
$5A,
$1E, $7C, $7F, $44, $4A, $46, $DD, $04, $A1, $3F, $58, $F7, $10, $BB,
$77,
$37,
$88, $EA, $1C, $E9, $47, $BA, $6E, $BF, $E2, $B0, $ED, $82, $E4, $45,
$F6,
$3A,
$C7, $48, $C9, $A8, $A9, $69, $30, $8A, $26, $14, $21, $A2, $35, $2F,
$1B,
$13,
$E7, $CA, $01, $71, $90, $18, $7D, $C3, $63, $06, $B5, $56, $F0, $95,
$AE,
$B3,
$A3, $F9, $5F, $66, $99, $28, $5C, $07, $F5, $2C, $E6, $65, $15, $1A,
$85,
$5B,
$9D, $34, $0D, $54, $FE, $43, $6B, $DB, $C2, $C6, $38, $BE, $81, $5D,
$C0,
$50,
$A6, $96, $9A, $2B, $AC, $AA, $0B, $23, $4E, $E8, $4F, $1F, $EB, $C5,
$B1,
$FF,
$6C, $DC, $CD, $0F, $B7, $79, $D3, $F8, $93, $8E, $22, $EE, $61, $E0,
$32,
$17,
$BC, $EF, $FD, $83, $9F, $86, $8D, $84, $25, $B4, $33, $52, $9E, $F3,
$9B,
$B8,
$F1, $D9, $40, $51, $62, $6D, $CB, $59, $94, $B6, $11, $8B, $8C, $F4,
$AB,
$02,
$CE, $AD, $B2, $68, $60, $0A, $CF, $0E, $00, $A0, $D4, $6F, $53, $D8,
$98,
$8F,
$B9, $FA, $31, $C1, $89, $49, $3C, $DF, $3D, $7A, $12, $EC, $5E, $36,
$91,
$D2,
$16, $70, $29, $67, $75, $DE, $3E, $74, $64, $4C, $92, $2D, $1D, $39,
$7E,
$A7,
$C8, $55, $D6, $2A, $80, $D0, $7B, $87, $AF, $09, $97, $57, $73, $0C,
$3B,
$D1,
$FB, $41, $4D, $A5, $72, $9C, $FC, $4B, $6A, $42, $05, $76, $D5, $E3,
$D7);
Tau:
Array[0..7] of Byte = (3, 6, 7, 2, 5, 1, 0, 4);
Процедура
начальной инициализации Init
Процедура
Init предназначена для установки начальных
параметров вычислений, а также
инициализации рабочего массива M, который
впоследствии будет шифроваться при
добавлении в него данных. Основная часть
процедуры выполняет сохранение указанного
количества повторений цикла шифрования,
заполняет массив M, устанавливает равными
нулю начальные значения полей Sum и N
(контрольная сумма и количество
обработанных байт) и завершает процедуру,
если пароль хеширования не задан:
if
Cycles > 1 then
_Cycles
:= Cycles
else
_Cycles
:= 2;
M[0] :=
$F1D4B79A;
M[0] :=
M[0] SHL 32 + $7D503316;
for I :=
1 to 7 do
begin
M[I]
:= (NOT M[I - 1] XOR (I SHL 15));
M[I]
:= (M[I] SHL 1) OR (M[I] SHR 63);
end;
Sum :=
0;
N := 0;
if
Passwd = '' then
Exit;
Если
же пароль хеширования задан, выполняется
его преобразование в динамический
байтовый массив BM, шифрование процедурой
EncryptMass (она изменит состояние M), после
чего массив освобождается, а пароль
очищается:
BM :=
TEncoding.Unicode.GetBytes(Passwd);
L :=
Length(BM);
EncryptMass(BM,
L);
SetLength(BM,
0);
BM :=
Nil;
Passwd
:= '';
Функция
GetHash для получения хеш-кода
Функция
GetHash преобразует полученный результат
шифрования массива M в символьную строку.
Для этого массив M разбивается на 64
отдельных байта, каждый из которых
делится на 62 и остаток от этого деления
формирует символ результата. 62 возможных
варианта символа результата составляют
следующие группы символов:
*
10 цифр (от 0 до 9);
*
26 символов латиницы верхнего регистра
(от A до Z);
*
26 символов латиницы нижнего регистра
(от a до z).
В
тексте функции это выглядит следующим
образом:
Hash :=
'';
for I :=
0 to 7 do
begin
U :=
M[I];
for
J := 1 to 8 do
begin
Bt
:= (U MOD 62) + $30;
U
:= U SHR 8;
if
Bt > $39 then
Bt
:= Bt + 7;
if
Bt > $5A then
Bt
:= Bt + 6;
Hash
:= Hash + Chr(Bt);
end;
end;
Result
:= Hash;
Хеширование
байтового массива
Рассмотренных
процедур и функций достаточно для того,
чтобы вычислять хеши для байтовых
массивов или файлов. Для этого нужно
лишь инициировать функцию с помощью
процедуры Init (указав необходимое
количество повторений цикла), запустить
процедуру EncryptMass или EncryptFile и получить
результат с помощью GetHash. Собственно,
так это и реализовано, например, в функции
HashMass:
function
CSA3Hash.HashMass(Var Mass: Array of Byte; Size: Cardinal;
Cycles:
Cardinal): String;
begin
Init(Cycles);
EncryptMass(Mass,
Size);
Result
:= GetHash;
end;
Некоторые
замечания
В
процедуре EncryptMass загрузка 8 байтов из
массива Mass в соответствующую ячейку
рабочего массива M производится с помощью
ссылочной переменной P. При этом на
разных архитектурах эти 8 байт могут
объединяться в одно число в разном
порядке. Установленный в алгоритме
порядок следующий: первым загружается
младший байт, последним — старший. То
есть при загрузке массива (1, 2, 3, 4, 5, 6, 7,
8) должно получиться число $0807060504030201.
Если операция P
:= @Mass[Pos + I * 8] формирует результат
в P^ в другом порядке, её следует заменить
на более корректную.
В
алгоритме принято, что количество
повторений цикла _Cycles не должно быть
меньше 2. Если в Init указано меньшее
количество, оно обязательно должно быть
установлено равным 2.
Если
размер хешируемого массива или файла
равен нулю, никакие данные в массив M
добавляться не будут, как не будет
выполняться и его шифрование. Результат
хеширования будет получен из начального
значения массива M, установленного после
процедуры начальной инициализации
Init.
Заключение
В
отличие от своего предшественника
(CSA-2) в данном алгоритме устранены все
основные его недостатки:
*
блок данных теперь имеет размер 64 байта,
при этом обеспечивается высокий уровень
взаимосвязи между его элементами;
*
зависимость схемы хеширования от
исходных данных теперь не настолько
сильна, чтобы это ослабляло надёжность
хеширования, но достаточна, чтобы
обеспечивать тесную взаимосвязь любого
бита прообраза с любым битом результата;
*
устранён громоздкий двухступенчатый
способ вычисления хеш-кода: теперь
хеш-код формируется из того же массива,
в который добавляются хешируемые данные;
*
строка хеша теперь состоит только из
символов латиницы и цифр, которые не
искажаются другими программами;
*
поскольку биты ключа K только переставляются,
но не изменяются, это исключает риск
нивелирования изменений отдельных
битов прообраза, а, значит, исключает и
вероятность полного отсутствия изменений
результата при изменении одного бита
прообраза;
*
функция обработки каждого отдельного
элемента рабочего массива включает
несколько этапов, на каждом из которых
этот элемент изменяется;
*
вместо
32-разрядных операций теперь выполняются
64-разрядные.
Источники
информации
1.
Википедия. Хеш-функция. [Электронный
ресурс] — URL: https://ru.wikipedia.org/wiki/Хеш-функция
2.
Шнайер Брюс. Прикладная криптография.
Протоколы, алгоритмы, исходные тексты
на языке Си. – М.: Триумф, 2002. – 816 с.
3.
Википедия. Аутентификация. [Электронный
ресурс] — URL: https://ru.wikipedia.org/wiki/Аутентификация
4.
Википедия. Электронная подпись.
[Электронный ресурс] — URL:
https://ru.wikipedia.org/wiki/Электронная_подпись
5.
Трунов Д.Н. Описание и исходный текст
алгоритма криптографической подписи
CSA-2 [Электронный ресурс] — URL:
http://d-raft5.blogspot.com/2018/04/csa-2.html
6.
Википедия. SHA-2. [Электронный ресурс] —
URL: https://ru.wikipedia.org/wiki/SHA-2
7.
Википедия. SHA-3. [Электронный ресурс] —
URL: https://ru.wikipedia.org/wiki/SHA-3
8.
ГОСТ Р 34.11-2012. Информационная технология.
Криптографическая защита информации.
Функция хэширования. [Электронный
ресурс] — URL: http://docs.cntd.ru/document/gost-r-34-11-2012
9.
Википедия. Стрибог (хеш-функция).
[Электронный ресурс] — URL:
https://ru.wikipedia.org/wiki/Стрибог_(хеш-функция)
Опубликовано
19 октября 2019 г. на https://d-raft5.blogspot.com
©
Трунов Д.Н., 2019 г.
Приложение А. Исходный текст алгоритма CSA-3 Object Pascal (Lazarus)
Текст приложения приведён в оригинальном файле.
Приложение Б. Контрольный пример
Текст приложения приведён в оригинальном файле.
Оригинальный файл: Открыть
