Bcrypt

Bcrypt

Bcrypt – представляет собой функцию хэширования паролей, основанную на шифре Blowfish. Впервые была представлена в USENIX в 1999 году разработчиками Niels Provos и David Mazières. Помимо включения salt для защиты от атаки Rainbow Table, bcrypt является адаптивной функцией: со временем, счетчик итераций может быть увеличен, чтобы сделать процесс медленнее, и таким образом повысить устойчивость к Brute-forse, даже с увеличением вычислительной мощности.

Функция bcrypt – это хэш-алгоритм пароля по умолчанию для OpenBSD и других систем, включая некоторые дистрибутивы Linux, такие как SUSE Linux. Существуют реализации bcrypt для C, C ++, C #, Go, Java, JavaScript, Perl, PHP, Python, Ruby и других языков.

Содержание

История

Blowfish примечателен среди блочных шифров для его дорогостоящей фазы настройки ключа. Он начинается с подключений в стандартном состоянии, затем использует это состояние для выполнения блочного шифрования с использованием части ключа и использует результат этого шифрования (более точно хеширование) для замены некоторых из подраздела. Затем он использует это измененное состояние для шифрования другой части ключа и использует результат для замены большего количества подразделов. Это происходит таким образом: используется прогрессивно измененное состояние для хеширования ключа и замены бит состояния, пока не будут установлены все подразделы.

Прово и Мазьер воспользовались этим и продолжили. Они разработали новый алгоритм настройки ключей для Blowfish, дублируя полученный шифр «Eksblowfish» («дорогой ключевой график Blowfish»). Настройка ключа начинается с измененной формы стандартной настройки ключа Blowfish, в которой и salt, и пароль используются для установки всех подразделов. Затем выполняется ряд раундов, в которых применяется стандартный алгоритм Key Blowfish, используя альтернативу salt и пароль в качестве ключа, каждый раунд, начинается с состояния подраздела из предыдущего раунда. Теоретически это не более сильное, чем стандартное расписание ключевых событий Blowfish, но количество раундов переключения настраивается; поэтому этот процесс можно сделать произвольно медленным, что помогает предотвратить атаки грубой силы на хэш или salt.

Описание

Префикс «$ 2a $» или «$ 2b $» (или «$ 2y $») в хэш-строке в файле теневого пароля указывает, что хэш-строка является хэшем bcrypt в модульном формате склепа. Остальная часть хэш-строки включает параметр стоимости, 128-битную salt ( Radix-64, закодированную как 22 символа) и 184 бит полученного хеш-значения ( Radix-64, закодированное как 31 символ). Кодировка Radix-64 использует алфавит unix / crypt и не является «стандартным» Base-64 . Параметр cost указывает количество итераций расширения ключа как мощность двух, что является входом в алгоритм.

Например, запись теневого пароля $2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWyуказывает параметр стоимости 10, что указывает на 2 10 раундов расширения ключа. Salt тут N9qo8uLOickgx2ZMRZoMyeи полученный хеш IjZAgcfl7p92ldGxad68LJZdL17lhWy. В стандартной практике пароль пользователя не сохраняется.

Версии Bcrypt

$ 2 $ (1999)

В исходной спецификации Bcrypt определен префикс $2$. Это следует за форматом Modular Crypt Format, используемым при хранении паролей в файле паролей OpenBSD:

  • $1$: MD5
  • $2$: Bcrypt
  • $sha1$: SHA-1
  • $5$: SHA-256
  • $6$: SHA-512

$ 2a $

Изначально, в спецификации не значилось, как обрабатывать не-ASCII-символ и нулевой ограничитель, поэтому она была дополнена, чтобы утвердить следующие положения:

  • строка должна кодироваться в кодировке UTF-8
  • нулевой ограничитель должен быть включен

С этим изменением версия была изменена на $2a$]

$ 2x $, $ 2y $ (июнь 2011 г.)

В июне 2011 года была обнаружена ошибка в crypt_blowfish, в PHP-реализации Bcrypt, которая заключалась в некорректности символов с 8-м битом. Они предложили, чтобы системные администраторы обновили свою существующую базу паролей, заменив ее $2a$на $2x$, чтобы указать, что эти хэши не рабочие (и нужно использовать старый сломанный алгоритм). Они также предложили идею иметь crypt_blowfish выпускающий $2y$для хешей, генерируемых фиксированным алгоритмом.

Никто, включая канонический OpenBSD, не принял идею 2x / 2y. Это изменение маркера версии было ограничено crypt_blowfish .

$ 2b $ (февраль 2014 г.)

Обнаружена ошибка в реализации bcrypt OpenBSD. Они сохраняли длину своих строк в unsigned char ( т.е. 8-битный Byte).] Если пароль был длиннее 255 символов, он переполнялся и завершался на 255.

BCrypt был создан для OpenBSD. Когда у них была ошибка в их библиотеке, они решили поднять номер версии.

Алгоритм

Алгоритм bcrypt является результатом шифрования текста «OrpheanBeholderScryDoubt» 64 раза с использованием Blowfish. В bcrypt обычная функция настройки ключа Blowfish заменяется функцией дорогостоящей настройки ключа (EksBlowfishSetup):

Function bcrypt

  Input:      cost:     Number (4..31)                      log 2 (итерации). например, 12 ==> 2 12 = 4096 итераций      salt:     array of Bytes (16 bytes)           случайный salt      password: array of Bytes (1..72 bytes)        Пароль с кодировкой UTF-8   Output:       hash:     array of Bytes (24 bytes) 
  // Инициализировать состояние Blowfish        state   EksBlowfishSetup(cost, salt, password)  
  // Повторно шифровать текст «OrpheanBeholderScryDoubt» 64 раза       ctext   "OrpheanBeholderScryDoubt" // 24 байта ==> три 64-битных блока       repeat (64)      ctext   EncryptECB(state, ctext) // шифрование с использованием стандартного Blowfish в режиме ECB 
  // 24-байтовый ctext    return Concatenate(cost, salt, ctext)

Установка дорогостоящего ключа

Алгоритм bcrypt в значительной степени зависит от алгоритма настройки ключа «Eksblowfish», который работает следующим образом: Function EksBlowfishSetup

 Input:      cost:     Number (4..31)                   log 2 (итерации). например, 12 ==> 2 12 = 4096 итераций      salt:     array of Bytes (16 bytes)        случайный salt        password: array of Bytes (1..72 bytes)     Пароль с кодировкой UTF-8      Output:       state:    opaque BlowFish state structure       state   InitialState()      state   ExpandKey(state, salt, password)      repeat (2cost)      state   ExpandKey(state, 0, password)      state   ExpandKey(state, 0, salt) 
   return state

InitialState работает как в оригинальном алгоритме Blowfish, заполняя записи P-массива и S-box дробной частью Pi в шестнадцатеричном формате.

Расширение ключа

Функция ExpandKey выполняет следующие действия: Function ExpandKey(state, salt, password)

  Input:      state:    Opaque BlowFish state structure     Внутренне содержит записи массива P-массива и S-поля      salt:     array of Bytes (16 bytes)           случайный salt      password: array of Bytes (1..72 bytes)        Пароль с кодировкой UTF-8   Output:       state:    opaque BlowFish state structure    // Смешиваем пароль во внутренний P-массив state   for n   1 to 18 do      Pn   Pn xor password[32(n-1)..32n-1] // обрабатываем пароль как циклический 
  // Шифруем состояние, используя более низкие 8 байт соли, и сохраняем результат 8 байтов в P1|P2      block   Encrypt(state, salt[0..63])      P1   block[0..31]  //lower 32-bits      P2   block[32..63] //upper 32-bits 
  // Продолжаем шифрование состояния с salt и сохранение результатов в оставшемся P-массиве   for n   2 to 9 do      block   Encrypt(state, block xor salt[64(n-1)..64n-1]) // шифруем с использованием текущего ключа графика           P2n-1   block[0..31] //lower 32-bits      P2n   block[32..63]  //upper 32-bits 
  // Перемещаем зашифрованное состояние во внутренние S-поля e   for i   1 to 4 do      for n   0 to 127 do         block   Encrypt(state, block xor salt[64(n-1)..64n-1]) //as above         Si[2n]     block[0..31]  //ниже 32-bits         Si[2n+1]   block[32..63]  //выше 32-bits    return state

Следовательно, это то же самое, что и регулярное расписание ключей Blowfish, поскольку все XOR с нулевым значением соли неэффективны. Аналогичен, но использует salt в виде 128-битного ключа. ExpandKey(state, 0, key)ExpandKey(state, 0, salt)

Вход пользователя

Многие реализации bcrypt урезают пароль до первых 72 байтов. Сам математический алгоритм требует инициализации с 18 32-разрядными подразделами (эквивалентно 72 октетам / байтам). Исходная спецификация bcrypt не предусматривает какого-либо одного конкретного метода для преобразования паролей на основе текста из userland в числовые значения для алгоритма. Один краткий комментарий в тексте упоминает, но не дает мандата, о возможности просто использовать кодированное значение ASCII символьной строки: «Наконец, ключевым аргументом является секретный ключ шифрования, который может быть выбранным пользователем паролем до 56 байтов (включая завершающий нулевой байт, когда ключ является строкой ASCII)”.

Обратите внимание, что в приведенной выше цитате упоминаются пароли «до 56 байтов», хотя сам алгоритм использует начальное значение в 72 байта. Хотя Provos и Mazières не указывают причину более короткого ограничения, они, возможно, были мотивированы следующим утверждением от первоначальной спецификации Bruce Schneier «Blowfish» «Ограничение по размеру ключа 448 [бит] гарантирует, что [ sic ] каждый бит каждого подраздела зависит от каждого бита ключа”.

Реализации различаются по своему подходу к преобразованию паролей в начальные числовые значения, в том числе иногда уменьшая силу паролей, содержащих символы, отличные от ASCII.

См. также на BitcoinWiki

Подробнее