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 подходит для использования, когда требуется жёсткость к памяти.

Алгоритм

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

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

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

Входные

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

Выходные

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

Алгоритм

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

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

Заполнение

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

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

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

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

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

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

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

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

Извлечение

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

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

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

[math]\displaystyle{ S \cdot T \geq \frac{r\cdot n^2}{32}. }[/math]

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

[math]\displaystyle{ S \cdot T \geq \frac{(2^r -1) n^2}{32}. }[/math]

Ссылки

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