bcrypt哈希碰撞问题

USE CASE

salt = bcrypt.gensalt()
hashed = bcrypt.hashpw(password, salt)
if bcrypt.checkpw(password, hashed):
print("It Matches!")
else:
    print("It Does not Match :(")

FUCK HASH

python的hashpw是通过rust实现的：

bcrypt/src/_bcrypt/src/lib.rs at main · pyca/bcrypt

rust-bcrypt不允许明文超过72字节：

#[cfg(any(feature = "alloc", feature = "std"))]
fn _hash_password(
    password: &[u8],
    cost: u32,
    salt: [u8; 16],
    err_on_truncation: bool,
) -> BcryptResult<HashParts> {
    if !(MIN_COST..=MAX_COST).contains(&cost) {
        return Err(BcryptError::CostNotAllowed(cost));
    }

    // Passwords need to be null terminated
    let mut vec = Vec::with_capacity(password.len() + 1);
    vec.extend_from_slice(password);
    vec.push(0);
    // We only consider the first 72 chars; truncate if necessary.
    // `bcrypt` below will panic if len > 72
    let truncated = if vec.len() > 72 {
        if err_on_truncation {
            return Err(BcryptError::Truncation(vec.len()));
        }
        &vec[..72]
    } else {
        &vec
    };

    let output = bcrypt::bcrypt(cost, salt, truncated);

    #[cfg(feature = "zeroize")]
    vec.zeroize();

    Ok(HashParts {
        cost,
        salt: BASE_64.encode(salt),
        hash: BASE_64.encode(&output[..23]), // remember to remove the last byte
    })
}

注意到 vec.push(0);，在散列前将password添加 \x00。

而bcrypt会调用setup，初始化带有cost和salt的 Blowfish 加密状态。

fn setup(cost: u32, salt: &[u8], key: &[u8]) -> Blowfish {
    assert!(cost < 32);
    let mut state = Blowfish::bc_init_state();

    state.salted_expand_key(salt, key);
    for _ in 0..1u32 << cost {
        state.bc_expand_key(key);
        state.bc_expand_key(salt);
    }

    state
}

salted_expand_key会扩展key：

其中p是u32类型，这里会循环18次，也就是说刚好扩展到72字节！

内部的处理流程大概是：

venom -->\x00作为分隔符
venom\x00 --> 循环填充key
venom\x00venom\x00venom\x00venom\x00venom\x00venom\x00venom\x00venom\x00venom\x00venom\x00venom\x00venom\x00

因此得出结论，设字符为m， {m}\x00{m}和 {m}对应的hash结是一致的！

import bcrypt
salt = bcrypt.gensalt()

password1 = b'venom\x00venom'
password2 = b'venom'

hash1 = bcrypt.hashpw(password1, salt)
hash2 = bcrypt.hashpw(password2, salt)
assert hash1 == hash2
print("good")

password1 = b'couqi11zifu\x00couqi11zifu'
password2 = b'couqi11zifu'

hash1 = bcrypt.hashpw(password1, salt)
hash2 = bcrypt.hashpw(password2, salt)
assert hash1 == hash2

print("good")

password1 = b'124312111\x00124312111'
password2 = b'124312111'

hash1 = bcrypt.hashpw(password1, salt)
hash2 = bcrypt.hashpw(password2, salt)
assert hash1 == hash2
print("good")

TODO

1. 调研其它语言bcrpt库的实现，是否存在类似的padding逻辑。