Русская Википедия:Balloon hashing
Balloon hashing, или Balloon — функция формирования ключа, разработанная Дэном Боне (Шаблон:Lang-en), Генри Корриган-Гиббсом (англ. Henry Corrigan-Gibbs) из Стэнфордовского университета и Стюартом Шехтером (Шаблон:Lang-en) из Microsoft Research в 2016 году.[1][2] Национальный институт стандартов и технологий США рекомендует Balloon как один из возможных алгоритмов для хеширования паролей.[3]
Авторы утверждают, что Balloon:
- обладает доказанной жёсткостью к памяти (memory-hardness)
- легко применяется
- так же эффективен, как похожие алгоритмы[1]
Авторы Balloon сравнивают его с Argon2, аналогичным по действию алгоритмом. Они показывают, что Balloon превосходит Argon2i-A.[1] Однако, Argon2i-B лучше сопротивляется атакам, чем Argon2i-A и Balloon hashing.[4]
Сравнение схем хеширования паролей показывает, что Balloon hashing подходит для использования, когда требуется жёсткость к памяти.[5]
Алгоритм
Вспомогательная функция
В качестве вспомогательной функции используется стандартная (не жёсткая к памяти) криптографическая функция <math>H: \mathbb{Z}_N\times\{0,1\}^{2k}\rightarrow \{0,1\}^{k}</math>, где <math>N</math>— большое целое число, <math>k </math> — длина выходной битовой строки <math>H</math>. Для анализа авторы алгоритма считают <math>H</math> случайным оракулом.
Входные и выходные данные
Входные
- Пароль <math>P</math> длиной от <math>0</math> до <math>2^{32}-1</math>
- Соль <math>S</math> длиной от <math>8</math> до <math>2^{32}-1</math>
- Временная стоимость <math>T</math> (число циклов)
- Пространственная стоимость <math>n </math> (число блоков в буфере)
- Параметр безопасности <math>\delta</math> (число зависимостей у каждого блока при перемешивании)
Выходные
- Битовая строка фиксированной длины, равная <math>k</math>[1]
Алгоритм
Алгоритм Balloon hashing состоит из трёх шагов:[1]
- Заполнение. На этом этапе Balloon заполняет большой буфер <math>B</math> псевдослучайными байтами.
- Перемешивание. Далее алгоритм «перемешивает» псевдослучайные байты в буфере.
- Извлечение. На последнем шаге Balloon возвращает последний блок буфера.
Заполнение
Буфер <math>B</math> состоит из <math>n </math> блоков, длиной <math>k </math> битов каждый. Сначала заполняется нулевой блок:
<math>B[0]=H(P,S)</math>
Каждый последующий блок заполняется хешем предыдущего:
<math>B[i]=H(B[i-1]),\ i=1\ ...\ n</math>
Перемешивание
Всего <math>T</math> раз выполняется итерация по всем блокам. Во время каждой итерации <math>t</math> <math>(t=1\ ...\ T)</math> содержимое всех блоков от <math>0</math> до <math>n</math> меняется.
На <math>t</math> итерации в блок номер <math>i</math> записывается хеш предыдущего блока <math>B[i]=H(B[(i-1)\bmod{n}])</math>.
Затем <math>\delta</math> раз в <math>i</math> блок записывается псевдослучайная битовая последовательность: <math>B[i]=H(B[i], B[other])</math>, где <math>other= int(H(S, index))\bmod{n}</math>, <math>S</math> — соль. Значение <math>index</math> (целое число от <math>0</math> до <math>n</math>) выбирается однозначно в зависимости от номера блока <math>i</math>, номера итерации <math>t</math> и того, сколько раз в блок уже записывалась псевдослучайная последовательность, <math>j\ (j = 1\ ...\ \delta)</math>, то есть <math>index=index(i,t,j)</math>.
Извлечение
Происходит извлечение последнего блока буфера. <math>output=B[n]</math>.
Псевдокод
Данный псевдокод описывает алгоритм Balloon:
func Balloon(block_t passwd, block_t salt,
int s_cost, // Пространственная стоимость (число блоков в буфере)
int t_cost): // Временная стоимость (число циклов)
int delta = 3 // Число зависимостей у каждого блока
int cnt = 0 // Счётчик (используется для повышения безопасности)
block_t buf[s_cost]): // Основной буфер
// Шаг 1. Заполнить буфер входными данными.
buf[0] = hash(cnt++, passwd, salt)
for i from 1 to s_cost-1:
buf[i] = hash(cnt++, buf[i-1])
// Шаг 2. Перемешать содержимое буфера.
for t from 0 to t_cost-1:
for i from 0 to s_cost-1:
// Шаг 2а. Записать в текущий блок хеш предыдущего
block_t prev = buf[(i-1) mod s_cost]
buf[i] = hash(cnt++, prev, buf[i])
// Шаг 2б. Записать в текущий блок хеши псевдослучайных блоков
for j from 0 to delta-1:
block_t idx_block = ints_to_block(t, i, j)
int other = to_int(hash(cnt++, salt, idx_block)) mod s_cost
buf[i] = hash(cnt++, buf[i], buf[other])
// Шаг 3. Извлечь выходные данные из буфера.
return buf[s_cost-1]
Безопасность
Авторы Balloon доказывают, что злоумышленники, которые попытаются вычислить хеши алгоритмом Balloon, не имея достаточно памяти, затратят много времени на вычисление.[1]
Неформальная формулировка теоремы:
Пусть <math>\mathcal{A} </math> — алгоритм, который вычисляет Balloon с <math>n </math> блоками, <math>r</math> циклами и параметром безопасноси <math>\delta=3 </math>, <math>H</math> считаем случайным оракулом. Если <math>\mathcal{A} </math> использует не более <math>S </math> блоков буферного пространства, то почти наверняка <math>\mathcal{A} </math> должен работать в течение времени (приблизительно) <math>T </math>, такого что:
<math>S \cdot T \geq \frac{r\cdot n^2}{32}. </math>
Если же <math>\delta=3 </math>, а <math>S < n/64 </math>, то выполняется более сильное соотношение:
<math>S \cdot T \geq \frac{(2^r -1) n^2}{32}. </math>
Примечания
Ссылки
