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]

Алгоритм

править

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

править

В качестве вспомогательной функции используется стандартная (не жёсткая к памяти) криптографическая функция  , где  — большое целое число,   — длина выходной битовой строки  . Для анализа авторы алгоритма считают   случайным оракулом.

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

править

Входные

  • Пароль   длиной от   до  
  • Соль   длиной от   до  
  • Временная стоимость   (число циклов)
  • Пространственная стоимость   (число блоков в буфере)
  • Параметр безопасности   (число зависимостей у каждого блока при перемешивании)

Выходные

  • Битовая строка фиксированной длины, равная  [1]

Алгоритм

править

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

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

Заполнение

править

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

 

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

 

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

править

Всего   раз выполняется итерация по всем блокам. Во время каждой итерации     содержимое всех блоков от   до   меняется.

На   итерации в блок номер   записывается хеш предыдущего блока  .

Затем   раз в   блок записывается псевдослучайная битовая последовательность:  , где  ,   — соль. Значение   (целое число от   до  ) выбирается однозначно в зависимости от номера блока  , номера итерации   и того, сколько раз в блок уже записывалась псевдослучайная последовательность,  , то есть  .

Извлечение

править

Происходит извлечение последнего блока буфера.  .

Псевдокод

править

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

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

Пусть   — алгоритм, который вычисляет Balloon с   блоками,   циклами и параметром безопасноси  ,   считаем случайным оракулом. Если   использует не более   блоков буферного пространства, то почти наверняка   должен работать в течение времени (приблизительно)  , такого что:

 

Если же  , а  , то выполняется более сильное соотношение:

 

Примечания

править
  1. 1 2 3 4 5 6 Dan Boneh, Henry Corrigan-Gibbs, Stuart Schechter. Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks. — 2016. — № 027. Архивировано 8 декабря 2020 года.
  2. Balloon Hashing | Stanford Applied Crypto Group. crypto.stanford.edu. Дата обращения: 8 декабря 2020. Архивировано 12 ноября 2020 года.
  3. NIST SP800-63B Section 5.1.1.2. Дата обращения: 12 декабря 2020. Архивировано 1 апреля 2019 года.
  4. J. Alwen, J. Blocki. Towards Practical Attacks on Argon2i and Balloon Hashing // 2017 IEEE European Symposium on Security and Privacy (EuroS P). — 2017-04. — С. 142–157. — doi:10.1109/EuroSP.2017.47. Архивировано 27 ноября 2020 года.
  5. George Hatzivasilis. Password-Hashing Status (англ.) // Cryptography. — 2017/9. — Vol. 1, iss. 2. — P. 10. — doi:10.3390/cryptography1020010. Архивировано 21 апреля 2022 года.

Ссылки

править