Balloon hashing

Balloon hashing, или Balloon — функция формирования ключа, разработанная Дэном Боне (англ. Dan Boneh), Генри Корриган-Гиббсом (англ. Henry Corrigan-Gibbs) из Стэнфордовского университета и Стюартом Шехтером (англ. Stuart Schechter) из 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]

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

Входные

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

Выходные

• Битовая строка фиксированной длины, равная ${\displaystyle k}$^[1]

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

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

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

${\displaystyle B[0]=H(P,S)}$

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

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

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

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

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

Происходит извлечение последнего блока буфера. ${\displaystyle 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, не имея достаточно памяти, затратят много времени на вычисление.^[1]

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

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

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

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

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

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