В этой статье мы покажем вам, как реализуется криптографическая хэш-функция SipHash, которая дает небольшой по размеру хэш и обладает очень высокой производительностью. Реализация данной функции есть на многих языках: C, C#, Rust и даже Haskell, но нет версии на D — и наша команда решила исправить это недоразумение…
Хэш-функция SipHash — это семейство псевдослучайных функций на основе add-rotate-xor (AXR), созданное Жаном-Филиппом Омассоном и Даниэлем Дж. Бернштейном в 2012 году. Эта функция базируется совершенно на иных принципах, нежели привычные функции наподобие SHA, и применяется в основном для реализации разного рода имитовставок.
Наша реализация была получена путем перевода с языка программирования Swift и также анализом референсной реализации, написанной на C. Для перевода был выбран Swift, поскольку к первоначальному варианту на C был ряд вопросов, а Swift как ни парадоксально очень близок к D и последний даже повлиял на синтаксис этой разработки Apple. Детали реализации рассматривать не будем, упомянем лишь то что метод __toLEUlong и функции-хэлперы hash8 — созданы нашей командой.
Код модуля siphash выглядит так:
module siphash;
class SipHash(ubyte NUMBER_OF_COMPRESS_ROUNDS = 2, ubyte NUMBER_OF_FINALIZATION_ROUNDS = 4)
{
private
{
/// Secret key: 0 - low part of key, 1 - high of key
ulong key0, key1;
ulong v0 = 0x736f6d6570736575;
ulong v1 = 0x646f72616e646f6d;
ulong v2 = 0x6c7967656e657261;
ulong v3 = 0x7465646279746573;
ulong pendingBytes = 0;
ulong pendingByteCount = 0;
long byteCount = 0;
}
private
{
ulong _toLEUlong(ubyte* ptr) @system
{
ulong h = 0x0000000000000000;
h |= (cast(ulong) ptr[0]);
h |= (cast(ulong) ptr[1]) << 8;
h |= (cast(ulong) ptr[2]) << 16;
h |= (cast(ulong) ptr[3]) << 24;
h |= (cast(ulong) ptr[4]) << 32;
h |= (cast(ulong) ptr[5]) << 40;
h |= (cast(ulong) ptr[6]) << 48;
h |= (cast(ulong) ptr[7]) << 56;
return h;
}
ulong _rotateLeft(ulong value, ulong amount)
{
return (value << amount) | (value >> (64 - amount));
}
void _round()
{
v0 += v1;
v1 = _rotateLeft(v1, 13);
v1 ^= v0;
v0 = _rotateLeft(v0, 32);
v2 += v3;
v3 = _rotateLeft(v3, 16);
v3 ^= v2;
v0 += v3;
v3 = _rotateLeft(v3, 21);
v3 ^= v0;
v2 += v1;
v1 = _rotateLeft(v1, 17);
v1 ^= v2;
v2 = _rotateLeft(v2, 32);
}
void _compress(ulong m)
{
v3 ^= m;
for (ubyte i = 0; i < NUMBER_OF_COMPRESS_ROUNDS; i++)
{
_round;
}
v0 ^= m;
}
ulong _finalize()
{
pendingBytes |= (cast(ulong) byteCount) << 56;
byteCount = -1;
_compress(pendingBytes);
v2 ^= 0xff;
for (ubyte i = 0; i < NUMBER_OF_FINALIZATION_ROUNDS; i++)
{
_round;
}
return v0 ^ v1 ^ v2 ^ v3;
}
}
this()
{
import std.random : Random, uniform, unpredictableSeed;
auto rng = Random(unpredictableSeed);
this(uniform(0UL, ulong.max, rng), uniform(0UL, ulong.max, rng));
}
this(ulong key0, ulong key1)
{
key0 = key0;
key1 = key1;
v0 ^= key0;
v1 ^= key1;
v2 ^= key0;
v3 ^= key1;
}
void append(ubyte[] buffer...)
{
import std.algorithm : min;
auto i = 0;
if (pendingByteCount > 0)
{
ulong readCount = min(buffer.length, 8 - pendingByteCount);
ulong m = 0;
switch (readCount)
{
case 7:
m |= cast(ulong)(buffer[6]) << 48;
goto case;
case 6:
m |= cast(ulong)(buffer[5]) << 40;
goto case;
case 5:
m |= cast(ulong)(buffer[4]) << 32;
goto case;
case 4:
m |= cast(ulong)(buffer[3]) << 24;
goto case;
case 3:
m |= cast(ulong)(buffer[2]) << 16;
goto case;
case 2:
m |= cast(ulong)(buffer[1]) << 8;
goto case;
case 1:
m |= cast(ulong)(buffer[0]);
break;
default:
break;
}
pendingBytes |= m << cast(ulong)(pendingByteCount << 3);
pendingByteCount += readCount;
i += readCount;
if (pendingByteCount == 8)
{
_compress(pendingBytes);
pendingBytes = 0;
pendingByteCount = 0;
}
}
ulong left = (buffer.length - i) & 7;
ulong end = (buffer.length - i) - left;
while (i < end)
{
ulong m = 0;
auto ptr = buffer[i .. i + 8].ptr;
_compress(_toLEUlong(ptr));
i += 8;
}
switch (left)
{
case 7:
pendingBytes |= cast(ulong)(buffer[i + 6]) << 48;
goto case;
case 6:
pendingBytes |= cast(ulong)(buffer[i + 5]) << 40;
goto case;
case 5:
pendingBytes |= cast(ulong)(buffer[i + 4]) << 32;
goto case;
case 4:
pendingBytes |= cast(ulong)(buffer[i + 3]) << 24;
goto case;
case 3:
pendingBytes |= cast(ulong)(buffer[i + 2]) << 16;
goto case;
case 2:
pendingBytes |= cast(ulong)(buffer[i + 1]) << 8;
goto case;
case 1:
pendingBytes |= cast(ulong)(buffer[i]);
break;
default:
break;
}
pendingByteCount = left;
byteCount += buffer.length;
}
ulong finalize()
{
return _finalize();
}
}
auto hash8(ubyte[] bytes, ulong[2] key = [0UL, 0UL])
{
SipHash!(2, 4) sh = new SipHash!(2, 4)(key[0], key[1]);
sh.append(bytes);
return sh.finalize;
}
auto hash8(string s, ulong[2] key = [0UL, 0UL])
{
import std.string : representation;
SipHash!(2, 4) sh = new SipHash!(2, 4)(key[0], key[1]);
sh.append((cast(ubyte[]) s));
return sh.finalize;
}Проверить можно следующим образом:
void main()
{
import std.stdio;
SipHash!(2, 4) s = new SipHash!(2, 4)(0x0000000000000000, 0x0000000000000000);
s.append(cast(ubyte[]) `Test`);
writefln(`%0.16x`, s.finalize);
writefln(`%0.16x`, hash8(`Test`));
writefln(`%0.16x`, hash8(`TesT`));
writefln(`%0.16x`, hash8(`Тест`));
writefln(`%0.16x`, hash8(``));
}Результат:
В этой реализации класс SipHash параметризуется двумя параметрами: количеством раундов сжатия и количеством раундов финализации, поскольку именно эти два параметра влияют непосредственно на работу алгоритма, который выдает 64-битный хэш. По двум вышеописанным параметрам алгоритм обозначают в литературе, к примеру 2 раунда сжатия и 4 финализации (классический вариант) приводят к алгоритму, который обозначается как SipHash-2-4.
Использование класса предполагает инициализацию экземпляра класса при создании не только внутренним состоянием (это переменные v0, v1, v2, v3), но и некоторым 128-битным ключом key, который разбит на две 64-битные переменные — key0 и key1, представляющие собой младшую и старшую части ключа. Если ключ не указать при создании экземпляра класса, то будет сгенерирован псевдослучайный ключ, который и будет использоваться далее.
После создания экземпляра класса, в полученный объект SipHash с помощью метода append подаются байты потока, который подвергнется дальнейшему хэшированию. Метод append не выдает каких-либо результатов и требует запуска метода finalize, который завершает генерацию хэша и выдает итоговый результат в виде 64-битного беззнакового числа. Последующие функции hash8 избавляют от взаимодействия с логикой класса SipHash и позволяют получить хэш просто вызвав любой из этих двух методов (в зависимости от типа входных данных — массива байтов или строки) и при необходимости указав свой ключ.