密码学系列之:bcrypt 加密算法详解

简介今天要给大家介绍的一种加密算法叫做 bcrypt, bcrypt 是由 Niels Provos 和 David Mazières 设计的密码哈希函数，他是基于 Blowfish 密码而来的，并于 1999 年在 USENIX 上提出。

除了加盐来抵御 rainbow table 攻击之外，bcrypt 的一个非常重要的特征就是自适应性，可以保证加密的速度在一个特定的范围内，即使计算机的运算能力非常高，可以通过增加迭代次数的方式，使得加密速度变慢，从而可以抵御暴力搜索攻击。

bcrypt 函数是 OpenBSD 和其他系统包括一些 Linux 发行版（如 SUSE Linux）的默认密码哈希算法。

bcrypt 的工作原理我们先回顾一下 Blowfish 的加密原理。 blowfish 首先需要生成用于加密使用的 K 数组和 S-box, blowfish 在生成最终的 K 数组和 S-box 需要耗费一定的时间，每个新的密钥都需要进行大概 4 KB 文本的预处理，和其他分组密码算法相比，这个会很慢。但是一旦生成完毕，或者说密钥不变的情况下，blowfish 还是很快速的一种分组加密方法。

那么慢有没有好处呢？

当然有，因为对于一个正常应用来说，是不会经常更换密钥的。所以预处理只会生成一次。在后面使用的时候就会很快了。

而对于恶意攻击者来说，每次尝试新的密钥都需要进行漫长的预处理，所以对攻击者来说要破解 blowfish 算法是非常不划算的。所以 blowfish 是可以抵御字典攻击的。

Provos 和 Mazières 利用了这一点，并将其进一步发展。他们为 Blowfish 开发了一种新的密钥设置算法，将由此产生的密码称为 “Eksblowfish”（”expensive key schedule Blowfish”）。这是对 Blowfish 的改进算法，在 bcrypt 的初始密钥设置中，salt 和 password 都被用来设置子密钥。然后经过一轮轮的标准 Blowfish 算法，通过交替使用 salt 和 password 作为 key，每一轮都依赖上一轮子密钥的状态。虽然从理论上来说，bcrypt 算法的强度并不比 blowfish 更好，但是因为在 bcrpyt 中重置 key 的轮数是可以配置的，所以可以通过增加轮数来更好的抵御暴力攻击。

bcrypt 算法实现简单点说 bcrypt 算法就是对字符串 OrpheanBeholderScryDoubt 进行 64 次 blowfish 加密得到的结果。有朋友会问了，bcrypt 不是用来对密码进行加密的吗？怎么加密的是一个字符串？

别急，bcrpyt 是将密码作为对该字符串加密的因子，同样也得到了加密的效果。我们看下 bcrypt 的基本算法实现：

Function bcryptInput:cost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterationssalt: array of Bytes (16 bytes) random saltpassword: array of Bytes (1..72 bytes) UTF-8 encoded passwordOutput:hash: array of Bytes (24 bytes)

//Initialize Blowfish state with expensive key setup algorithm//P: array of 18 subkeys (UInt32[18])//S: Four substitution boxes (S-boxes), S0...S3. Each S-box is 1,024 bytes (UInt32[256])P, S <- EksBlowfishSetup(cost, salt, password)

//Repeatedly encrypt the text "OrpheanBeholderScryDoubt" 64 timesctext <- "OrpheanBeholderScryDoubt" //24 bytes ==> three 64-bit blocksrepeat (64)ctext <- EncryptECB(P, S, ctext) //encrypt using standard Blowfish in ECB mode

//24-byte ctext is resulting password hashreturn Concatenate(cost, salt, ctext)上述函数 bcrypt 有 3 个输入和 1 个输出。

在输入部分，cost 表示的是轮循的次数，这个我们可以自己指定，轮循次数多加密就慢。

salt 是加密用盐，用来混淆密码使用。

password 就是我们要加密的密码了。

最后的输出是加密后的结果 hash。

有了 3 个输入，我们会调用 EksBlowfishSetup 函数去初始化 18 个 subkeys 和 4 个 1K 大小的 S-boxes，从而达到最终的 P 和 S。

然后使用 P 和 S 对”OrpheanBeholderScryDoubt” 进行 64 次 blowfish 运算，最终得到结果。

接下来看下 EksBlowfishSetup 方法的算法实现：

Function EksBlowfishSetupInput:password: array of Bytes (1..72 bytes) UTF-8 encoded passwordsalt: array of Bytes (16 bytes) random saltcost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterationsOutput:P: array of UInt32 array of 18 per-round subkeysS1..S4: array of UInt32 array of four SBoxes; each SBox is 256 UInt32 (i.e. 1024 KB)

//Initialize P (Subkeys), and S (Substitution boxes) with the hex digits of piP, S <- InitialState()

//Permutate P and S based on the password and salt

P, S <- ExpandKey(P, S, salt, password)

//This is the "Expensive" part of the "Expensive Key Setup".//Otherwise the key setup is identical to Blowfish.repeat (2cost)P, S <- ExpandKey(P, S, 0, password)P, S <- ExpandKey(P, S, 0, salt)

return P, S 代码很简单，EksBlowfishSetup 接收上面我们的 3 个参数，返回最终的包含 18 个子 key 的 P 和 4 个 1k 大小的 Sbox。

首先初始化，得到最初的 P 和 S。

然后调用 ExpandKey，传入 salt 和 password，生成第一轮的 P 和 S。

然后循环 2 的 cost 方次，轮流使用 password 和 salt 作为参数去生成 P 和 S，最后返回。

最后看一下 ExpandKey 的实现：

Function ExpandKeyInput:password: array of Bytes (1..72 bytes) UTF-8 encoded passwordsalt: Byte[16] random saltP: array of UInt32 Array of 18 subkeysS1..S4: UInt32[1024] Four 1 KB SBoxesOutput:P: array of UInt32 Array of 18 per-round subkeysS1..S4: UInt32[1024] Four 1 KB SBoxes

//Mix password into the P subkeys arrayfor n <- 1 to 18 doPn <- Pn xor password[32(n-1)..32n-1] //treat the password as cyclic

//Treat the 128-bit salt as two 64-bit halves (the Blowfish block size).saltHalf[0] <- salt[0..63] //Lower 64-bits of saltsaltHalf[1] <- salt[64..127] //Upper 64-bits of salt

//Initialize an 8-byte (64-bit) buffer with all zeros.block <- 0

//Mix internal state into P-boxes

for n <- 1 to 9 do//xor 64-bit block with a 64-bit salt halfblock <- block xor saltHalf[(n-1) mod 2] //each iteration alternating between saltHalf[0], and saltHalf[1]

  //encrypt block using current key schedule  block   <-  Encrypt(P, S, block)   P2n   <-  block[0..31]      //lower 32-bits of block  P2n+1   <- block[32..63]  //upper 32-bits block

//Mix encrypted state into the internal S-boxes of statefor i <- 1 to 4 dofor n <- 0 to 127 doblock <- Encrypt(state, block xor salt[64(n-1)..64n-1]) //as aboveSi[2n] <- block[0..31] //lower 32-bitsSi[2n+1] <- block[32..63] //upper 32-bitsreturn stateExpandKey 主要用来生成 P 和 S，算法的生成比较复杂，大家感兴趣的可以详细研究一下。

bcrypt hash 的结构我们可以使用 bcrypt 来加密密码，最终以 bcrypt hash 的形式保存到系统中，一个 bcrypt hash 的格式如下：

$2b$[cost]$[22 character salt][31 character hash]比如：

$2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy_// _/___________/Alg Cost Salt Hash 上面例子中，$2a$ 表示的 hash 算法的唯一标志。这里表示的是 bcrypt 算法。

10 表示的是代价因子，这里是 2 的 10 次方，也就是 1024 轮。

N9qo8uLOickgx2ZMRZoMye 是 16 个字节（128bits）的 salt 经过 base64 编码得到的 22 长度的字符。

最后的 IjZAgcfl7p92ldGxad68LJZdL17lhWy 是 24 个字节（192bits）的 hash，经过 bash64 的编码得到的 31 长度的字符。

hash 的历史这种 hash 格式是遵循的是 OpenBSD 密码文件中存储密码时使用的 Modular Crypt Format 格式。最开始的时候格式定义是下面的：

$1$: MD5-based crypt (‘md5crypt’)$2$: Blowfish-based crypt (‘bcrypt’)$sha1$: SHA-1-based crypt (‘sha1crypt’)$5$: SHA-256-based crypt (‘sha256crypt’)$6$: SHA-512-based crypt (‘sha512crypt’)但是最初的规范没有定义如何处理非 ASCII 字符，也没有定义如何处理 null 终止符。修订后的规范规定，在 hash 字符串时：

String 必须是 UTF-8 编码必须包含 null 终止符因为包含了这些改动，所以 bcrypt 的版本号被修改成了 $2a$。

但是在 2011 年 6 月，因为 PHP 对 bcypt 的实现 crypt_blowfish 中的一个 bug，他们建议系统管理员更新他们现有的密码数据库，用$2x$代替$2a$，以表明这些哈希值是坏的（需要使用旧的算法）。他们还建议让 crypt_blowfish 对新算法生成的哈希值使用头$2y$。 当然这个改动只限于 PHP 的 crypt_blowfish。

然后在 2014 年 2 月，在 OpenBSD 的 bcrypt 实现中也发现了一个 bug，他们将字符串的长度存储在无符号 char 中（即 8 位 Byte）。如果密码的长度超过 255 个字符，就会溢出来。

因为 bcrypt 是为 OpenBSD 创建的。所以当他们的库中出现了一个 bug 时, 他们决定将版本号升级到$2b$。

本文已收录于 http://www.flydean.com/37-bcrypt/

最通俗的解读，最深刻的干货，最简洁的教程，众多你不知道的小技巧等你来发现！

欢迎关注我的公众号:「程序那些事」,懂技术，更懂你！