Реализация CubeHash в JavaScript

Введение

CubeHash — это криптографический хэш ARX от DJB, представленный на конкурс SHA-3. Его удивительно просто реализовать, он имеет переменный вывод размером до 64 байт и позволяет довольно легко настраивать параметры. К сожалению, CubeHash не прошел в финальные раунды конкурса (предположительно по политическим причинам, хотя истинная причина неизвестна). CubeHash — хороший хэш, однако его реализации в JavaScript (и других языках) довольно ограничены. Реализации CubeHash в JavaScript обычно поддерживают только один набор параметров для CubeHash, а также не используют более современные API-интерфейсы JavaScript, такие как типизированный массив. Поэтому я написал собственную реализацию CubeHash на JavaScript. Эта статья представляет собой анализ этой реализации и руководство для разработчиков CubeHash (на любом языке, однако это руководство специально предназначено для JavaScript).

Теперь давайте рассмотрим, что такое CubeHash на самом деле. CubeHash в основном выполняет множество преобразований в 5-мерном гиперкубе (представленном как состояние, состоящее из 32 32-битных целых чисел без знака). CubeHash принимает параметры i, r, b, f и h. i — количество раундов инициализации, r — количество раундов на блок сообщения, b — количество байтов на блок сообщения, f — количество раундов завершения, h — длина вывода, а m — сообщение для быть хэшированным. Параметры по умолчанию и набор, членом которого должны быть параметры, будут рассмотрены позже. Чтобы создать хэш, мы сначала:

1. Дополнить сообщение последовательностью входных блоков размером b байт. Заполнение в реализациях с выравниванием по байтам состоит из добавления одного 128 байта, а затем добавления минимального количества 0 байтов, чтобы получить число, кратное b байтам.
2. Вычислите начальное состояние. Первое слово — h/8, второе слово — b, а третье слово — r. Затем состояние трансформируется через i раундов.
3. Для каждого входного блока выполните xor состояния с входным блоком, а затем преобразуйте состояние через r раундов.
4. Xor 1 в последнее слово в состоянии, затем преобразовать состояние через f раундов.
5. Выведите первые h/8 байтов состояния.

Раунд работает следующим образом (индексы массива записываются в двоичном виде, а состояние, представляющее собой последовательность из 32 беззнаковых 4-байтовых целых чисел, представляется как x):

1. Добавьте x[0jklm] к x[1jklm] по модулю 2³² для каждого (j, k, l, m).
2. Поверните x[0jklm] влево на 7 бит для каждого (j, k, l, m).
3. Замените x[00klm] на x[01klm] для каждого (k, l, m).
4. Xor x[1jklm] в x[0jklm] для каждого (j, k, l, m).
5. Поменяйте местами x[1jk0m] с x[1jk1m] для каждого (j, k, m).
6. Добавьте x[0jklm] к x[1jklm] по модулю 2³² для каждого (j, k, l, m).
7. Поверните x[0jklm] влево на 11 бит для каждого (j, k, l, m).
8. Замените x[0j0lm] на x[0j1lm] для каждого (j, l, m).
9. Xor x[1jklm] в x[0jklm] для каждого (j, k, l, m).
10. Замените x[1jkl0] на x[1jkl1] для каждого (j, k, l).

Теперь, когда у нас есть базовые знания, необходимые для продолжения, давайте перейдем к фактической реализации. Реализация CubeHash на JavaScript, которую я написал, реализует класс CubeHash, так что вектор инициализации можно легко предварительно вычислить без дополнительной работы со стороны пользователя.

Конструктор

Во-первых, давайте предположим, что this.round(state: Uint32Array): void — это функция, которая выполняет 1 раунд для переданного ей состояния. Помните, что состояние состоит из 32 беззнаковых 4-байтовых целых чисел. Мы не будем проверять параметры, переданные в конструктор (вы можете это сделать, если хотите), но требования к параметрам следующие: я должен быть членом множества {1, 2, 3, …}, r должен быть членом множества {1, 2, 3, …}, b должен быть членом множества {1, 2, 3, …, 128}, f должен быть членом множества {1, 2 , 3, …}, а h должен быть членом состояния {8, 16, 24, …, 512}. Сообщение должно быть строкой до 2¹²⁸ - 1 бит. Теперь, как мы помним, первые 3 слова состояния устанавливаются равными h/8, b и r соответственно, а затем состояние преобразуется через i раундов для создания начального состояния. У нас также должно быть разумное значение по умолчанию для конструктора. DJB рекомендует CubeHash512 (определяется как CubeHash16+16/32+32-512, где для параметров CubeHash используется обозначение CubeHash i+r/b+f-h). Давайте напишем конструктор с учетом этого.

constructor(i = 16, r = 16, b = 32, f = 32, h = 512) {
    // sets the parameters within the class
    this.i = i;
    this.r = r;
    this.b = b;
    this.f = f;
    this.h = h;
    // start the initial state as a Uint32Array with 32 members, then set the first three words. we then transform the state through i rounds.
    this.initialState = new Uint32Array(32);
    this.initialState[0] = h / 8;
    this.initialState[1] = b;
    this.initialState[2] = r;
    for (let j = 0; j < i; j++) this.round(this.initialState);
}

Круглая функция

Давайте подойдем к функции округления в CubeHash шаг за шагом. Во-первых, нам нужна функция ROTL (повернуть влево), которую довольно просто реализовать в JavaScript (# обозначает закрытую функцию в классах). Вращение влево означает побитовый круговой сдвиг влево (Википедия). Операнды побитовых операторов в JavaScript обрабатываются как 32-битные целые числа, поэтому нам не нужно беспокоиться о размере операндов.

#ROTL(a, b) {
    return (a << b) | (a >>> (32 - b));
}

После этого давайте перейдем к реальной функции округления. Предположим, что state — это параметр, который представляет собой Uint32Array с 32 элементами. Наш первый шаг — добавить 0jklm к 1jklm для каждого (j, k, l, m). Это довольно просто. 1111 равно 15, поэтому у нас есть переменная i, представляющая jklm, увеличивающуюся до (включая) 15. 10000 равно 16, поэтому мы просто делаем:

// add 0jklm into 1jklm for each (j, k, l, m)
for (let i = 0; i < 16; i++) {
    state[i + 16] += state[i];
}

Следующий шаг — повернуть 0jklm влево на 7 бит для каждого (j, k, l, m). Нам снова нужна переменная i, представляющая jklm, увеличивающуюся до 15 включительно. Затем мы поворачиваем state[i] влево на 7 бит.

// rotate 0jklm left 7 bits for each (j, k, l, m)
for (let i = 0; i < 16; i++) {
    state[i] = this.#ROTL(state[i], 7);
}

Теперь нам нужно поменять местами 00klm на 01klm для каждого (k, l, m). 111 равно 7, поэтому у нас есть возрастающая переменная i, представляющая klm, которая увеличивается до 7 включительно. 1000 равно 8, поэтому мы меняем местами state[i + 8] с state[i] . Это может быть реализовано следующим образом:

// swap 00klm with 01klm for each (k, l, m)
for (let i = 0; i < 8; i++) {
    let tmp = state[i];
    state[i] = state[i + 8];
    state[i + 8] = tmp;
}

Следующий шаг — преобразовать 1jklm в 0jklm для каждого (j, k, l, m). Как уже упоминалось, 1111 равно 15, поэтому у нас есть переменная i, представляющая приращение jklm до 15 включительно. 10000 равно 16, поэтому мы добавляем 16, чтобы получить 1jklm из 0jklm. Код выглядит следующим образом:

// xor 1jklm into 0jklm for each (j, k, l, m)
for (let i = 0; i < 16; i++) {
    state[i] ^= state[i + 16];
}

Теперь нам нужно поменять местами 1jk0m на 1jk1m для каждого (j, k, m). У нас будет переменная i, представляющая jkm, вплоть до 7 (111) включительно. Затем мы манипулируем jkm, используя побитовые операнды, чтобы получить jk0m, затем добавляем 16, чтобы получить 1jk0m. Из 1jk0m мы можем получить 1jk1m, просто добавив 2. Код будет следующим:

// swap 1jk0m with 1jk1m for each (j, k, m)
for (let i = 0; i < 8; i++) {
    // do some bit manipulation to get 1jk0m
    // (12 is 1100 in binary)
    let jk0m = (((i << 1) & 12) | (i & 1)) + 16;
    let tmp = state[jk0m];
    state[jk0m] = state[jk0m + 2];
    state[jk0m + 2] = tmp;
}

Затем мы добавляем 0jklm к 1jklm для каждого (j, k, l, m). Это то же самое, что и первый шаг, и можно использовать тот же код. Он представлен ниже:

// add 0jklm into 1jklm for each (j, k, l, m)
for (let i = 0; i < 16; i++) {
    state[i + 16] += state[i];
}

Теперь мы поворачиваем 0jklm влево на 11 бит для каждого (j, k, l, m). Как и ранее, у нас просто есть счетчик, представляющий jklm, который увеличивается до 15 включительно (максимальное значение jklm, 1111).

// rotate 0jklm left by 11 bits for each (j, k, l, m)
for (let i = 0; i < 16; i++) {
    state[i] = this.#ROTL(state[i], 11);
}

Затем мы меняем 0j0lm на 0j1lm для каждого (j, l, m). Чтобы реализовать это, нам сначала нужен счетчик, представляющий jlm, который доходит до 7 включительно (111, максимальное значение jlm). Затем нам нужно манипулировать им, чтобы получить 0j0lm. Для этого нам просто нужно выполнить несколько побитовых операций. Ниже приведена реализация этого шага:

// swap 0j0lm with 0j1lm for each (j, l, m)
for (let i = 0; i < 8; i++) {
    // get 0j0lm with bit manipulation
    let j0lm = ((i & 4) << 1) | (i & 3);
    let tmp = state[j0lm];
    state[j0lm] = state[j0lm + 4]; // 4 is 00100
    state[j0lm + 4] = state[tmp];
}

Теперь осталось всего два шага. Первый заключается в преобразовании 1jklm в 0jklm для каждого (j, k, l, m). Это уже было сделано ранее, и код тот же (следующий):

// xor 1jklm into 0jklm for each (j, k, l, m)
for (let i = 0; i < 16; i++) {
    state[i] ^= state[i + 16];
}

Последний шаг — поменять местами 1jkl0 на 1jkl1 для каждого (j, k, l). Для этого нам просто нужна переменная, представляющая jlk, а затем манипулировать ею, чтобы получить 1jkl0. Затем мы просто меняем state[1jkl0] на state[1jkl1]. Это делается следующим образом:

// swap 1jkl0 with 1jkl1 for each (j, k, l)
for (let i = 0; i < 8; i++) {
    // bit manipulation to get 1jkl0
    let jkl0 = (i << 1) + 16;
    let tmp = state[jkl0];
    state[jkl0] = state[jkl0 + 1];
    state[jkl0 + 1] = tmp;
}

Теперь мы закончили с функцией округления! Код каждого из методов будет помещен в метод round(state) внутри класса.

Хэш

Теперь, когда у нас есть функция округления, мы должны реализовать фактический хэш. Предположим, что m — это Uint8Array. Во-первых, нам нужно правильно заполнить сообщение. Как упоминалось ранее, мы просто добавляем 128 байт, а затем минимальное количество байтов, чтобы получить кратное b байтов. Это можно сделать следующим образом:

// initialize our message object to null
let message = null;
// get the proper length of the message
if (m.length % this.b !== 0) {
    // we want the minimum number of bytes to get to a multiple of b bytes
    message = new Uint8Array(Math.ceil(m.length / this.b) * this.b);
}
else {
    // same thing here
    message = new Uint8Array(m.length + this.b);
}
// put the message into the padded object
for (let i = 0; i < m.length; i++) {
    message[i] = m[i];
}
// add a 128 byte. the rest are all zeroes by default
message[m.length] = 128;

Теперь нам нужно инициализировать наше состояние и версию состояния Uint8Array, чтобы упростить операцию xor. Поскольку у нас уже есть состояние, предварительно вычисленное из конструктора, мы можем просто сделать:

// create a state and its uint8array counterpart
let state = new Uint32Array([...this.initialState]);
let uint8State = new Uint8Array(state.buffer);

Теперь нам нужно обработать входные блоки. Для каждого входного блока мы выполняем операцию xor с состоянием, а затем преобразуем его через r раундов.

// for each input block
let inputBlocks = message.length / this.b;
for (let i = 0; i < inputBlocks; i++) {
    // the location of the first byte in the input block in the message
    let iTimesB = i * this.b;
    // for each byte in the input block
    for (let j = 0; j < this.b; j++) {
        // xor the state with the byte
        uint8State[j] ^= message[iTimesB + j];
    }
    // transform the state through r rounds
    for (let j = 0; j < this.r; j++) this.round(state);
}

Теперь, когда мы закончили обработку входных блоков, нам нужно преобразовать 1 в последнее слово состояния, а затем преобразовать его через f раундов.

// xor 1 into the last state word
state[31] ^= 1;
// transform the state through f rounds
for (let i = 0; i < this.f; i++) this.round(state);

Как только это будет сделано, мы вернем первые h/8 байтов состояния, и на этом все:

// return the first h/8 bytes of the state
return uint8State.slice(0, this.h / 8);

Были сделаны! Теперь вы прошли (и, надеюсь, написали) правильную реализацию CubeHash. Если вы хотите протестировать его, ниже приведены проверки работоспособности (из Википедии).

Санитарные проверки

Они взяты из Википедии. Не стесняйтесь использовать их для проверки, работает ли ваша реализация или нет:

Вектор инициализации CubeHash80+8/1+80–512:

5df39869c73009fb108994600f1626e6f37c07360c0d8bb53d19cf57b8e741335b8034a3eff9892014c4ff315038ef2a391812fe52a440e9a293527d12ca45706e0958933470bf814aa4909adb3ec39384e9c314d0db874af21d45bcacb312521ce5ab6a3bf6f05de88abbdd0fcfd3fafb8225d546242eada52540095c3da221

CubeHash80+8/1+80–512 («»):

90bc3f2948f7374065a811f1e47a208a53b1a2f3be1c0072759ed49c9c6c7f28f26eb30d5b0658c563077d599da23f97df0c2c0ac6cce734ffe87b2e76ff7294

CubeHash80+8/1+80–512 («Быстрая коричневая лиса перепрыгивает через ленивую собаку»):

ca942b088ed9103726af1fa87b4deb59e50cf3b5c6dcfbcebf5bba22fb39a6be9936c87bfdd7c52fc5e71700993958fa4e7b5e6e2a3672122475c40f9ec816ba

Заключение

Спасибо, что прочитали эту статью: надеюсь, вы узнали из нее что-то новое. По моему личному мнению, CubeHash — отличная, простая в реализации криптографическая хэш-функция. Тем не менее, я бы не стал использовать его для чего-то важного (хотя криптоанализ CubeHash многообещающий, с начала 2010-х его было немного). Кроме того, скорость этой реализации немного ниже, чем у чисто JavaScript-реализации криптографических хеш-функций аналогичной длины дайджеста (примерно в два раза медленнее для 1 МБ, примерно в 3 раза медленнее для 500 МБ). Однако CubeHash оченьпрост, и его трудно испортить. Будем надеяться, что CubeHash получит больше реализаций (надеюсь, быстрее, чем эта) и лучший криптоанализ в будущем.

Если вы найдете какие-либо опечатки в этой статье, не стесняйтесь, дайте мне знать. Со мной можно связаться в Discord (parabirb#1312) или по электронной почте (parabirb at protonmail dot ch).