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 : Z N × { 0 , 1 } 2 k → { 0 , 1 } k {displaystyle H:mathbb {Z} _{N} imes {0,1}^{2k} ightarrow {0,1}^{k}} , где N {displaystyle N} — большое целое число, k {displaystyle k} — длина выходной битовой строки H {displaystyle H} . Для анализа авторы алгоритма считают H {displaystyle H} случайным оракулом.

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

Входные

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

Выходные

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

Алгоритм

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

Заполнение. На этом этапе Balloon заполняет большой буфер B {displaystyle B} псевдослучайными байтами.

Перемешивание. Далее алгоритм «перемешивает» псевдослучайные байты в буфере.

Извлечение. На последнем шаге Balloon возвращает последний блок буфера.

Заполнение

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

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

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

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

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

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

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

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

Извлечение

Происходит извлечение последнего блока буфера. o u t p u t = B [ n ] {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, не имея достаточно памяти, затратят много времени на вычисление.

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

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

S ⋅ T ≥ r ⋅ n 2 32 . {displaystyle Scdot Tgeq {frac {rcdot n^{2}}{32}}.}

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

S ⋅ T ≥ ( 2 r − 1 ) n 2 32 . {displaystyle Scdot Tgeq {frac {(2^{r}-1)n^{2}}{32}}.}