03.12.2021

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}}.}


    Похожие новости:

    Алгоритм Монтгомери (эллиптические кривые)

    Алгоритм Монтгомери (эллиптические кривые)
    Алгоритм Монтгомери(англ. Montgomery ladder) — это алгоритм, позволяющий проводить операцию скалярного умножения для произвольной точки, принадлежащей эллиптической кривой за конечное время.

    256 бит

    256 бит
    В компьютерной архитектуре 256-битными (англ. 256 bit) числами, адресами памяти и другими объектами данных называются те, которые имеют размер в 256 бит (32 октета). Также 256-битными являются те ЦПУ

    Kaspersky Password Manager

    Kaspersky Password Manager
    Kaspersky Password Manager — инструмент управления учётными записями в интернете и приложениях от Лаборатории Касперского. Программа автоматизирует ввод паролей и других данных на веб-страницах,

    Функция Гёделя

    Функция Гёделя
    Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел. Определение Функцией Геделя Γ ( x
    Комментариев пока еще нет. Вы можете стать первым!

    Добавить комментарий!

    Ваше Имя:
    Ваш E-Mail:
    Введите два слова, показанных на изображении: *
    Популярные новости
    Распространенные причины поломки электродвигателя
    Распространенные причины поломки электродвигателя
    Электродвигатель повсеместно используется не только в промышленности, но и в бытовых условиях:...
    Мебель на заказ - секрет удобства и функциональности малогабаритной кухни
    Мебель на заказ - секрет удобства и функциональности малогабаритной кухни
    Кухня - особое помещение в каждом доме. Именно здесь производится приготовление различных блюд,...
    Выбираем насос для дачи
    Выбираем насос для дачи
    Насосные установки – это оборудование, которое используется для подкачки воды и более эффективного...
    Все новости