Balloon hashing (Balloon hashing)

Balloon hashing, или Balloon — функция формирования ключа, разработанная Дэном Боне (англ. Dan Boneh), Генри Корриган-Гиббсом (англ. Henry Corrigan-Gibbs) из Стэнфордовского университета и Стюартом Шехтером (англ. Stuart Schechter) из Microsoft Research в 2016 году. Национальный институт стандартов и технологий США рекомендует Balloon как один из возможных алгоритмов для хеширования паролей.

Авторы утверждают, что Balloon:

• обладает доказанной жёсткостью к памяти (memory-hardness)
• легко применяется
• так же эффективен, как похожие алгоритмы

Авторы Balloon сравнивают его с Argon2, аналогичным по действию алгоритмом. Они показывают, что Balloon превосходит Argon2i-A. Однако, Argon2i-B лучше сопротивляется атакам, чем Argon2i-A и Balloon hashing.

Сравнение схем хеширования паролей показывает, что Balloon hashing подходит для использования, когда требуется жёсткость к памяти.

Алгоритм

Вспомогательная функция

В качестве вспомогательной функции используется стандартная (не жёсткая к памяти) криптографическая функция $H:\mathbb {Z} _{N}\times \{0,1\}^{2k}\rightarrow \{0,1\}^{k}$, где $N$— большое целое число, $k$ — длина выходной битовой строки $H$. Для анализа авторы алгоритма считают $H$ случайным оракулом.

Входные и выходные данные

Входные

• Пароль $P$ длиной от $0$ до $2^{32}-1$
• Соль $S$ длиной от $8$ до $2^{32}-1$
• Временная стоимость $T$ (число циклов)
• Пространственная стоимость $n$ (число блоков в буфере)
• Параметр безопасности $\delta$ (число зависимостей у каждого блока при перемешивании)

Выходные

• Битовая строка фиксированной длины, равная $k$

Алгоритм

Алгоритм Balloon hashing состоит из трёх шагов:

1. Заполнение. На этом этапе Balloon заполняет большой буфер $B$ псевдослучайными байтами.
2. Перемешивание. Далее алгоритм «перемешивает» псевдослучайные байты в буфере.
3. Извлечение. На последнем шаге Balloon возвращает последний блок буфера.

Заполнение

Буфер $B$ состоит из $n$ блоков, длиной $k$ битов каждый. Сначала заполняется нулевой блок:

$B[0]=H(P,S)$

Каждый последующий блок заполняется хешем предыдущего:

$B[i]=H(B[i-1]),\ i=1\ ...\ n$

Перемешивание

Всего $T$ раз выполняется итерация по всем блокам. Во время каждой итерации $t$ $(t=1\ ...\ T)$ содержимое всех блоков от $0$ до $n$ меняется.

На $t$ итерации в блок номер $i$ записывается хеш предыдущего блока $B[i]=H(B[(i-1){\bmod {n}}])$.

Затем $\delta$ раз в $i$ блок записывается псевдослучайная битовая последовательность: $B[i]=H(B[i],B[other])$, где $other=int(H(S,index)){\bmod {n}}$, $S$ — соль. Значение $index$ (целое число от $0$ до $n$) выбирается однозначно в зависимости от номера блока $i$, номера итерации $t$ и того, сколько раз в блок уже записывалась псевдослучайная последовательность, $j\ (j=1\ ...\ \delta )$, то есть $index=index(i,t,j)$.

Извлечение

Происходит извлечение последнего блока буфера. $output=B[n]$.

Псевдокод

Данный псевдокод описывает алгоритм 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, не имея достаточно памяти, затратят много времени на вычисление.

Неформальная формулировка теоремы:

Пусть ${\mathcal {A}}$ — алгоритм, который вычисляет Balloon с $n$ блоками, $r$ циклами и параметром безопасноси $\delta =3$, $H$ считаем случайным оракулом. Если ${\mathcal {A}}$ использует не более $S$ блоков буферного пространства, то почти наверняка ${\mathcal {A}}$ должен работать в течение времени (приблизительно) $T$, такого что:

$S\cdot T\geq {\frac {r\cdot n^{2}}{32}}.$

Если же $\delta =3$, а $S<n/64$, то выполняется более сильное соотношение:

$S\cdot T\geq {\frac {(2^{r}-1)n^{2}}{32}}.$

Ссылки

• Исследовательский прототип на Github
• Balloon hashing на Python