Моим первым хобби-проектом по изучению Rust было внедрение криптографических хеш-алгоритмов [MD5, SHA-2, SHA-3]. Последний, SHA-3, был самой сложной реализацией.
Это произошло из-за а) существенных отличий в конструкции алгоритма от более знакомых предшественников MD5 и SHA и б) меньшего количества и менее интуитивно понятных эталонных реализаций и объяснений алгоритмов. В этой статье я кратко обобщу некоторые высокоуровневые различия между SHA-3 и более ранними алгоритмами, а затем пройдусь по его реализации.
Высокоуровневая структура MD5, SHA-1 и SHA-2 довольно похожа; эти алгоритмы основаны на Конструкции Меркле-Дамгарда. Это особая методология последовательного связывания фрагментов входного сообщения вместе с помощью функции одностороннего сжатия (которая может состоять из нескольких различных операций). Они также часто строятся из блочных шифров.
С десяти тысяч футов эти алгоритмы выглядят так:
MDHash(M: message):
bytes P = padding (M) // extends length to a multiple of N bits
bytes S = initial working state default values
for chunk in P:
S += compression_function(S, chunk)
return S
Функция сжатия выполняет ряд нелинейных побитовых операций смешивания состояний, постоянных значений и входных битов сообщения. Вот пример из части функции сжатия SHA-2:
// See https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf # 6.2.2
while indx < 64 {
/*
* From https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf # 4.1.2
*
* The functions Σ0, Σ1, Ch(x, y, z) and Maj(x, y, z)
*/
let s0 = state.a.rotate_right(2) ^ state.a.rotate_right(13)
^ state.a.rotate_right(22);
let s1 = state.e.rotate_right(6) ^ state.e.rotate_right(11)
^ state.e.rotate_right(25);
let ch = (state.e & state.f) ^ ((!state.e) & state.g);
let maj = (state.a & state.b) ^ (state.a & state.c) ^ (state.b & state.c);
// See https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
// # 6.2.2 section 3
state.rotate(
state.h.wrapping_add(s1)
.wrapping_add(ch)
.wrapping_add(K[indx])
.wrapping_add(w[indx]),
s0.wrapping_add(maj)
);
indx += 1;
}
Этот метод построения хэшей страдает множеством уязвимостей, и подход, используемый в SHA-3, отличается.
SHA-3 был выпущен NIST в 2015 году и основан на алгоритме хеширования под названием Keccak, представленном в 2012 году. Ниже я буду использовать эти термины как синонимы. Вместо того, чтобы полагаться на процесс Меркла-Дамгарда, SHA-3 / Keccak использует технику, называемую конструкцией губки.
С десяти тысяч футов это выглядит примерно так:
SHA-3(M: message, N: digest length):
bytes P = padding (M) // extends length to a multiple of N bits
bytes S = 0x0 // state
// "absorb"
for chunk in P:
S[index] ^= chunk
permute(S) // mix entire state
bytes output = []
// "squeeze"
while output length < N:
output += S[0...M]
permute(S) // mix entire state
return output
Я не буду пытаться охватить здесь многие сложные свойства этого подхода. Пара пунктов высокого уровня:
- Длина массива состояний в битах не соответствует 1:1 предполагаемому размеру или содержимому вывода дайджеста. Вместо этого фрагменты префикса итеративно извлекаются из состояния.
- Во время вычисления дайджеста состояние дополнительно переставляется по достижении конца каждого фрагмента состояния. Этот процесс повторяется до тех пор, пока выходной буфер не достигнет заданной длины.
Ниже я подробно расскажу о том, как работает SHA-3.
Прокладка
Заполнение в SHA-3 является простым и напоминает подходы к заполнению в более ранних алгоритмах хеширования. Цель заполнения — увеличить длину входного сообщения до кратного скорости, значения, определенного в этой таблице как r, что позволяет легко разбивать на фрагменты.
0x06 должен быть добавлен сразу после сообщения, даже если сообщение уже кратно r. Ноль или более нулевых байтов добавляются до тех пор, пока длина массива не станет на 1 байт меньше кратного r, а затем 0x80 объединяется как последний байт.
В особом случае, когда длина входного сообщения равна r — 1, эти два разделителя объединяются вместе как 0x06 | 0x80 в одном байте.
Вы можете увидеть эту реализацию здесь, в Rust.
fn pad (message: &mut Vec<u8>, rate: usize) {
let rate_bytes = rate / 8;
if message.len() == rate_bytes - 1 {
// Special case. 0x06 and 0x80 must always be present.
// If the message length is 1 byte less than a
// multiple of the rate, append these two values OR'd together
// so the last byte is 0x86
message.push(0x06 | 0x80);
} else {
// Messages are padded to something like
// [... 0x06, 0x0, 0x0 ..., 0x80]
message.push(0x06);
while (message.len() % rate_bytes) != rate_bytes - 1 {
message.push(0x0);
}
message.push(0x80);
}
}
Однако одно интересное замечание заключается в том, что спецификация SHA-3 вносит небольшое изменение по сравнению со спецификацией алгоритма Кекчака — в определении заполнения. Алгоритм Keccak добавляет 0x01 сразу после сообщения:
Спецификация SHA-3 изменила начальные 0x1 на 0x6. Это означает, что, несмотря на то, что SHA-3 основан на Keccak, хэш сообщения Keccak приведет к другому результату дайджеста, чем SHA-3. Разница здесь всего в трех битах в заполнении, но значение дайджеста будет совершенно другим из-за лавинного эффекта.
Состояние, фрагментация и поглощение
Спецификация алгоритма определяет массив состояний как трехмерный массив битов, в зависимости от конфигурации и значения параметра w, в диапазоне от 25 до 1600 полных битов.
Это моделирование состояния не было особенно полезным для меня; было намного проще думать о состоянии как о массиве 5x5 64-битных целых чисел (u64), который захватывал максимальный размер состояния 1600 бит. В отличие от других алгоритмов хеширования, состояние инициализируется не набором магических чисел, а просто нулем.
Входное сообщение разбивается на 512-битные блоки, что эквивалентно 8 u64. Каждое из этих целых чисел затем «поглощается» состоянием, что означает XOR-помещение входящего целого числа в соответствующее место в состоянии.
// Each 512-bit chunk is further broken into 8 64-bit words;
// each is independently absorbed into the state array
for chunk in block.chunks(8) {
// Convert message byte chunks into a little-endian u64 integer
let (b1, b2, b3, b4, b5, b6, b7, b8)
= (chunk[0] as u64, chunk[1] as u64, chunk[2] as u64, chunk[3] as u64,
chunk[4] as u64, chunk[5] as u64, chunk[6] as u64, chunk[7] as u64);
let word = (b8 << 56) | (b7 << 48) | (b6 << 40) | (b5 << 32)
| (b4 << 24) | (b3 << 16) | (b2 << 8) | b1;
state.absorb(indx, word);
indx += 1;
}
fn absorb (&mut self, indx: usize, word: u64) {
// Some transformation from single index to element in this 2D state array
self.state[indx / 5][indx % 5] ^= word;
}
После поглощения каждого блока из восьми u64 фрагментов состояние меняется.
Перестановка
Шаг перестановки — это 24 раунда выполнения пяти функций над данными состояния. Каждый раунд приводит к необратимой промежуточной перестановке битов в состоянии.
/**
* From https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf # 3.3
*
* Given a state array A and a round index ir, the round function Rnd
* is the transformation that results from applying the
* step mappings θ, ρ, π, χ, and ι, in that order, i.e.:
* Rnd(A, ir) = ι(χ(π(ρ(θ(A)))), ir).
*
* See also https://keccak.team/keccak_specs_summary.html for pseudo-code
* descriptions of this permutation, its 24 rounds, and
* the underlying functions.
*/
fn permute (&mut self) {
for i in 0..24 {
self.theta();
self.rho_and_pi();
self.chi();
self.iota(i);
}
}
Каждая из этих функций выполняет мутацию на некоторой плоскости массива состояний. Например, здесь проиллюстрирован эффект rho, визуализирующий «лист» или столбец полных целых чисел в состоянии с использованием 3D-моделирования состояния из предыдущего:
Эта конкретная функция выполняет целочисленное вращение для каждого u64 в массиве состояний, где смещения вращения определены в Сводке Keccak. Эта конкретная функция связана с pi, которая меняет расположение каждого u64 в массиве состояний. Это немного похоже на вращение кубика Рубика.
Я постарался описать и процитировать конкретные детали реализации каждой из этих функций (theta, rho, pi, chi, iota) в коде для тех, кто заинтересован.
сжатие
Последним шагом является извлечение содержимого массива состояний в выходной байтовый вектор перед кодированием base-64. Я нашел псевдокод Кекчака неинтуитивным; Псевдокод NIST под конструкцией губки был понятнее.
В ржавчине
/**
* From https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
* # 4 and Algorithm 8, steps 7 to 10
*
* This function extracts bytes from the state array and returns
* a vector capturing the number of digest bytes corresponding to
* the request digest output size.
*/
fn squeeze (&mut self, rate: usize, md_size: usize) -> Vec<u8> {
let num_words = rate / 64;
let len_bytes = md_size / 8;
let mut bytes = Vec::with_capacity(len_bytes * 2);
// Iterates until sufficient bytes have been read to fill the
// final message digest byte vector
while bytes.len() < len_bytes {
// Read the first 'num_words` integers from the state array
for i in 0..num_words {
bytes.extend_from_slice(&self.state[i / 5][i % 5].to_le_bytes());
}
if bytes.len() < len_bytes {
// If we have more bytes to read, permute
// the state for the next round of reading
self.permute();
}
}
// Return the first len_bytes of the result, consistent
// with requested message digest size
return bytes[0..len_bytes].to_vec();
}
Ранее я описал общие различия между этим подходом и более старыми методами хэш-функции для извлечения значений дайджеста из хеш-состояния. Выходные байты извлекаются партиями с начала массива состояний (как в state[0][0]). По достижении определенной длины остальная часть состояния отбрасывается, и весь массив проходит еще один раунд из 24 перестановок.
Последний шаг — кодирование байтов в базе 64.
~/code/sha-3 ~>> ./target/release/sha3 --algo 224 --string rust
c44aa66c6a741d515297a91554d6a669323288ba1d42a7402938e5df
~/code/sha-3 ~>> ./target/release/sha3 --algo 256 --string rust
dcd84e60f950eebbeaf1db530fd4ed1ccf61aab94b558653072a205fb0fedee7
~/code/sha-3 ~>> ./target/release/sha3 --algo 384 --string rust
e7e13b16b131f1a8bc3ef00601beb13031d82de118bf5204757d3f5d8fa3c69431d0944ed9ee8cfd479acb0b16a93941
~/code/sha-3 ~>> ./target/release/sha3 --algo 512 --string rust
31805399bdec85ad94582da495b92cc3054835ac97d475ff1946ba85b2d9bd02f6ac2d8ccc6b72622de5c63a5eee28c1323bfec26fc56116193ae988c59b3bc8
~/code/sha-3 ~>> time ./target/release/sha3 --test
[OK] SHA3-224 ("")
[OK] SHA3-224 ("abcde")
[OK] SHA3-224 ("6acfaab70afd8439cea3616b41088bd81c939b272548f6409cf30e57")
[OK] SHA3-256 ("")
[OK] SHA3-256 ("abcde")
[OK] SHA3-256 ("d716ec61e18904a8f58679b71cb065d4d5db72e0e0c3f155a4feff7add0e58eb")
[OK] SHA3-384 ("")
[OK] SHA3-384 ("abcde")
[OK] SHA3-384 ("348494236b82edda7602c78ba67fc3838e427c63c23e2c9d9aa5ea6354218a3c2ca564679acabf3ac6bf5378047691c4")
[OK] SHA3-512 ("")
[OK] SHA3-512 ("abcde")
[OK] SHA3-512 ("1d7c3aa6ee17da5f4aeb78be968aa38476dbee54842e1ae2856f4c9a5cd04d45dc75c2902182b07c130ed582d476995b502b8777ccf69f60574471600386639b")
All 12 tests completed successfully!
real 0m0.007s
user 0m0.002s
sys 0m0.003s
Для читателей, которые ищут простое пошаговое руководство или удобочитаемую реализацию SHA-3, надеюсь, вы нашли это полезным.
Ржавчина
Что касается самого Rust, вот несколько мыслей:
- Как человек, привыкший к C и C++, я обнаружил, что борьба с типами Rust и системами безопасности разочаровывает — поначалу
- После того, как программы скомпилировались, было приятно запускать их без необходимости отладки ошибок сегментации.
- Я думал, что многие из встроенных методов коллекций и примитивных типов удобны, интуитивно понятны и очень хорошо документированы.
- Производительность этих программ кажется сравнимой со встроенными собственными хеш-утилитами MacOS.
Cargoотлично подходит для управления пакетами и зависимостями.
