密码学系列之：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 bcrypt
Input:
cost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
salt: array of Bytes (16 bytes) random salt
password: array of Bytes (1..72 bytes) UTF-8 encoded password
Output:
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 times
ctext <- "OrpheanBeholderScryDoubt" //24 bytes ==> three 64-bit blocks
repeat (64)
ctext <- EncryptECB(P, S, ctext) //encrypt using standard Blowfish in ECB mode
//24-byte ctext is resulting password hash
return 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 EksBlowfishSetup
Input:
password: array of Bytes (1..72 bytes) UTF-8 encoded password
salt: array of Bytes (16 bytes) random salt
cost: Number (4..31) log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
Output:
P: array of UInt32 array of 18 per-round subkeys
S1..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 pi
P, 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 ExpandKey
Input:
password: array of Bytes (1..72 bytes) UTF-8 encoded password
salt: Byte[16] random salt
P: array of UInt32 Array of 18 subkeys
S1..S4: UInt32[1024] Four 1 KB SBoxes
Output:
P: array of UInt32 Array of 18 per-round subkeys
S1..S4: UInt32[1024] Four 1 KB SBoxes
//Mix password into the P subkeys array
for n <- 1 to 18 do
Pn <- 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 salt
saltHalf[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 half
block <- 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 state
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] //lower 32-bits
Si[2n+1] <- block[32..63] //upper 32-bits
return state
ExpandKey主要⽤来⽣成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$。
本⽂已收录于
最通俗的解读，最深刻的⼲货，最简洁的教程，众多你不知道的⼩技巧等你来发现！
欢迎关注我的:「程序那些事」，懂技术，更懂你！
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论