Balloon hashing, или Balloon — функция формирования ключа, разработанная Дэном Боне (), Генри Корриган-Гиббсом (англ. Henry Corrigan-Gibbs) из Стэнфордовского университета и Стюартом Шехтером () из Microsoft Research в 2016 году. Национальный институт стандартов и технологий США рекомендует Balloon как один из возможных алгоритмов для хеширования паролей.
Авторы утверждают, что Balloon:
обладает доказанной жёсткостью к памяти (memory-hardness) легко применяется так же эффективен, как похожие алгоритмы
Авторы Balloon сравнивают его с Argon2, аналогичным по действию алгоритмом. Они показывают, что Balloon превосходит Argon2i-A. Однако, Argon2i-B лучше сопротивляется атакам, чем Argon2i-A и Balloon hashing.
Сравнение схем хеширования паролей показывает, что Balloon hashing подходит для использования, когда требуется жёсткость к памяти.
Алгоритм
Вспомогательная функция В качестве вспомогательной функции используется стандартная (не жёсткая к памяти) криптографическая функция , где — большое целое число, — длина выходной битовой строки . Для анализа авторы алгоритма считают случайным оракулом.
Входные и выходные данные Входные Пароль длиной от до Соль длиной от до Временная стоимость (число циклов) Пространственная стоимость (число блоков в буфере) Параметр безопасности (число зависимостей у каждого блока при перемешивании) Выходные Битовая строка фиксированной длины, равная
Алгоритм Алгоритм Balloon hashing состоит из трёх шагов:
Заполнение. На этом этапе Balloon заполняет большой буфер псевдослучайными байтами. Перемешивание. Далее алгоритм «перемешивает» псевдослучайные байты в буфере. Извлечение. На последнем шаге 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 = 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, не имея достаточно памяти, затратят много времени на вычисление.
Неформальная формулировка теоремы:
Пусть — алгоритм, который вычисляет Balloon с блоками, циклами и параметром безопасноси , считаем случайным оракулом. Если использует не более блоков буферного пространства, то почти наверняка должен работать в течение времени (приблизительно) , такого что:
Если же , а , то выполняется более сильное соотношение:
Примечания
Ссылки Исследовательский прототип на Github Balloon hashing на Python
Категория:Хеш-функции Категория:Криптографические хеш-функции