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.