Bcrypt

Материал из BitcoinWiki
Это утверждённая версия страницы. Она же — наиболее свежая версия.
Перейти к: навигация, поиск
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[править]

Подробнее[править]