迹忆客 专注技术分享

加密货币爱好者 Christian ‘CodesInChaos’ Winnerlein 曾写道：

plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd 和 eBkXQTfuBqp'cTcar&g* 具有相同的 PBKDF2-HMAC-SHA1 哈希。

这引起了我的兴趣，所以我决定找出到底发生了什么，以及为什么会这样。 如果你也很好奇，请继续阅读。

为了证实这些发现，我编写了一个 Node.js 脚本：

#!/usr/bin/env node

'use strict';

const crypto = require('crypto');
const assert = require('assert');

const salt = 'hunter2'; // can be anything
const iterations = 4; // can be any number
const keyLength = 16; // can be any number

const hash = (passphrase) => {
    return crypto.pbkdf2Sync(passphrase, salt, iterations, keyLength).toString();
};

const string1 = 'plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd';
const string2 = 'eBkXQTfuBqp\'cTcar&g*';

const hash1 = hash(string1);
const hash2 = hash(string2);

assert(string1 != string2, 'Passwords should be different');
assert(hash1 == hash2, 'Hashes should be the same (collision)');

运行脚本确认两个字符串确实具有相同的 PBKDF2-HMAC-SHA1 哈希。

说明

PBKDF2 是一种广泛使用的方法，可以根据给定的密码、salt 和迭代次数导出给定长度的密钥。 在这种情况下，它专门使用 HMAC 和 SHA-1 哈希函数，这是 RFC2898 的默认值。

HMAC 有一个有趣的属性：如果提供的密钥长于正在使用的哈希函数的块大小，它会使用密钥的哈希值而不是密钥本身。

SHA-1 的块大小为 512 位，等于 64 字节。

所以在这种情况下，如果提供的密钥占用超过 64 个字节，则使用 SHA1(key) 作为密钥。 更一般地说，对于任何大于 64 字节的 chosen_password，以下内容成立（伪代码）：

PBKDF2_HMAC_SHA1(chosen_password) == 
PBKDF2_HMAC_SHA1(HEX_TO_STRING(SHA1(chosen_password)))

请注意 ，两者中最小的密码始终具有 20 个字符的长度，因为 SHA1 哈希始终恰好由代表 20 个字节的 40 个十六进制数字组成。 一个字节，即两个十六进制数字用于冲突密码中的每个字符。

例如，在 Bash 中：

$ printf 'plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd' | sha1sum | xxd -r -p
eBkXQTfuBqp'cTcar&g*

这就是为什么 plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd 和 eBkXQTfuBqp'cTcar&g* 具有相同的 PBKDF2-HMAC-SHA1 哈希。

结果

这实际上意味着我们可以想出任意数量的 PBKDF2-HMAC-SHA1 碰撞。 事实上，只要将 PBKDF2 与 HMAC 和任何哈希算法结合使用，就可以应用相同的技巧——唯一的变量是哈希函数的块大小。 在使用 PBKDF2-HMAC-anything 进行散列时，很容易找到冲突的密码。

那么，为什么 Chris 在所有可能的碰撞中选择 plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd 和 eBkXQTfuBqp'cTcar&g* ？

$ printf 'lolololololololololololololololololololololololololololololololol' | sha1sum
6ff0b2d76dae24f8b58472ba19f918f07359c0c0

$ printf 'lolololololololololololololololololololololololololololololololol' | sha1sum | xxd -r -p
o��m�$�r���sY��

虽然很容易找到任何大于 64 字节的给定字符串的冲突（只需运行上面的 Bash 命令），但如果我们希望冲突密码仅由可读的 ASCII 字符组成，就会变得更加棘手。 SHA1 散列可以包含任何十六进制数字，将这样的散列转换回字符串可能会导致至少一个字符超出可打印的 ASCII 范围 ([\x20-\x7E])。

我编写了一个 Python 脚本来暴力破解 PBKDF2-HMAC-SHA1 冲突，其中相对较长的密码（> 64 字节）有一个选择的前缀，并且冲突密码仅包含可打印的 ASCII 字符。

#!/usr/bin/env python
# coding=utf-8

import hashlib
import itertools
import re
import string
import sys

TOTAL_LENGTH = 65
PREFIX = sys.argv[1] if len(sys.argv) > 1 else ''

prefix_length = len(PREFIX)
brute_force_length = TOTAL_LENGTH - prefix_length
passwords = itertools.product(string.ascii_lowercase, repeat=brute_force_length)
regex_printable = re.compile('[\x20-\x7E]+$')
base_hasher = hashlib.sha1()
base_hasher.update(PREFIX)

for item in itertools.imap(''.join, passwords):
    hasher = base_hasher.copy()
    hasher.update(item)
    sha1_hash = hasher.digest()
    if regex_printable.match(sha1_hash):
        print u'%s \U0001F4A5 %s'.encode('utf-8') % (PREFIX + item, sha1_hash)

首先，我让它在不指定前缀的情况下运行几个小时，它发现了以下冲突：

$ ./brute-force.py
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaadzuyfdt 💥 /JRb+z%,6f{$;*|#\LHT
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaebihgje 💥 @3d9ggezHn@iy,vV/#YC
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaagkpicoe 💥 m;Ec4m@1JW)TOSgGl3ZO
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaidwsoeu 💥 Y#pt*^.[}~.6jx!:fu'P
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaitkpvbh 💥 RFvc?%tbygGt(fy7G*+,
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaajhixpyq 💥 @x!iEK2B*N]X`S$u"CEV
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaakidzupe 💥 1t_lP?o}R;YWoJPF7!GY
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaamyrpmpv 💥 &nbSlEfC.X`D0(l)x[tV
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaandkfdci 💥 %U;/> ,3S/4dv!fUku*N
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaowdgicp 💥 b<-'^;Qt7~G[8>\6=wH(
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaqdpodre 💥 EmjaaG|_\Eq;+Wgl%<@)
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaqsmqyjo 💥 oZD49:*Cd)PFCubU[^)_
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaasbvoipq 💥 Woyw!itp af;uJo'Z-x#
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaslsvwra 💥 +ME:wn{F[<f_Zw%yWN\j
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaatljisbf 💥 w<0k!([95gEP%G^?&tP*
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaavdramcj 💥 ?!`e6 m]e/JJubY`|ZM1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaavutrypa 💥 d63mH`L=IW3Ucwb.FRec
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaawdxljmb 💥 h?2O+Pm5^x|^`du`A:@^
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaxdovzru 💥 ks*A]XD!U1I4[`!:+@s)
…

不过，与选定前缀的暴力冲突更有趣：

$ ./brute-force.py 'trololololololololololololololololololololololololololo'
trololololololololololololololololololololololololololoaaabaslrsc 💥 M,2p[;|4rkZQ,G5`W 9j
trololololololololololololololololololololololololololoaaablkqqic 💥 Fs>"Y0,'Pj:.D8SYiJ!4
trololololololololololololololololololololololololololoaaacblecnb 💥 _0jZI5O+23MGs-1*I\oQ
trololololololololololololololololololololololololololoaaaltyeuck 💥 &8T-gvxEwb`>r\E_.E2@
trololololololololololololololololololololololololololoaaalyxrcss 💥 TGPwn!L?}]x20&U}[^*&
trololololololololololololololololololololololololololoaaaotcvgrg 💥 _b7z7m(^!?`wI;!_~vl<
trololololololololololololololololololololololololololoaaarbaxieg 💥 zR;cd7\'~6zr,*NHQsd$
trololololololololololololololololololololololololololoaaarwxcedc 💥 D`nPK5Is$>.vO9Pi!8\c
trololololololololololololololololololololololololololoaaasghxurd 💥 VI\T]xa:oZ{H04g0`|).
trololololololololololololololololololololololololololoaaayavvpbc 💥 {Aj_idpOz)S/mmc$k/aT
trololololololololololololololololololololololololololoaaazdtxalo 💥 xgdMs~n(Y<jD"?3^#"?}
trololololololololololololololololololololololololololoaabdfbdoeb 💥 Bz+\his88.X1=5@{%<vW
trololololololololololololololololololololololololololoaabhtispji 💥 _z)7#`~I8$!q$x#h_VUI
trololololololololololololololololololololololololololoaabjvvgkfw 💥 h7Kt8oO&#r$jG=BM^DVh
trololololololololololololololololololololololololololoaabkgljluc 💥 agtQL=tZ55nk['ts1t'|
trololololololololololololololololololololololololololoaabmaaoavm 💥 ~;Zp2M=!k>hE[c]6C'nI
trololololololololololololololololololololololololololoaabmhyfjbt 💥 \pEYgz=BP`W3e89zov-R
trololololololololololololololololololololololololololoaabnyplvil 💥 &_f[/u^R@CL|PnNgYI{V
trololololololololololololololololololololololololololoaabogonxnp 💥 FD(}rO@+GIpZo<];#<^o
trololololololololololololololololololololololololololoaabpskyycf 💥 j./w=Ct}HQF:Y5>@a\\Y
trololololololololololololololololololololololololololoaabsnvfhys 💥 ;>[}h6^ha.SNtW:]0`|1
trololololololololololololololololololololololololololoaabtuuecis 💥 emmP*T3"k4$iObPFRFxm
trololololololololololololololololololololololololololoaabuhtrkfz 💥 bMYCnc[o}r\}gcRaL^CG
…

$ ./brute-force.py 'collision_my_mission_when_the_dawn_breaks_with_a_hand_'
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaaaappxze 💥 uYmwXw'c04\LHh=i!E|*
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaaarcgqpq 💥 s%K>G0KHOdx#l*_y"pDj
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaabejvnge 💥  zI%j'd1f4$U&iZ@w|$!
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaabzkzrce 💥 <9.f8Zu5e?H"U&;ha!8%
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaacbszkmz 💥 k^VyGxWJJNy&{^Aa"}Nl
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaaddcwxmd 💥 oSnr*x=`Ky4`b<{Uh+C@
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaadqzyizo 💥 &6JZj4jQ0(E0[LrN'K:Y
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaadsjngbc 💥 DRq9</HIxBLD9Q]Ll6Bj
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaafcgqfrb 💥 6f.ZfjBU2TLkd2k\+Qxu
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaafgrkiwn 💥 Ac#Db(cOs\VWz6PU6/sU
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaafzbytnn 💥 M"F<(|/*K5TS~`:?[kjG
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaafzwvfen 💥 Z)Jd;6Ql[j5#EE8)=f/U
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaagkntuew 💥 voC,;s}M;vfggl}}6sr'
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaagssyiwu 💥 F..Ncx3Z.C]/2n.XX%bu
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaaibapezf 💥 v/+|qU1erE#4(<ko0D P
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaajdxotoa 💥 dNLKU-sFik_=AK[FKJTb
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaakhddjzb 💥 n(?}=^N^52WaozN7*UAh
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaakxafnmx 💥 "Dy.9Giik;[i$cC#hP_H
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaamdzdfpk 💥 5wE}l`Rn]nhiX]N/"EII
collision_my_mission_when_the_dawn_breaks_with_a_hand_aaaamofydxb 💥 z\ c_>Q`F?s;jybKeM#(
…

$ ./brute-force.py 'chosen-prefix_hash_collisions_ftw_'
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaabcjenbr 💥 e=D&^kQ^qs+^PRL!j_.q
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaafikpjor 💥 |BHwN@zatb0TT:5I3|7<
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaaguatnrr 💥 #f.FDRuJz1V%"i*8nLOz
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaahqmauyt 💥 dUH}]4wi($\O/L`fej0[
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaaifuaosw 💥 iKd3djP<]g(WLt%2>Uq;
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaajkzsniz 💥 D>e{,OD%KwQb-y\67nn2
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaajzgkoyv 💥  WGoWj5#JC+N! w*oH.A
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaanlmxgoc 💥 >IZASesr9T+_bA?64 LU
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaaogmbbtc 💥 #f,U~l|=7p<L{'l;wrcr
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaaolrkjhw 💥 D.^GkKUq$%yn$kmT_,'Z
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaapetgdgr 💥 6I}z8;8M4Nts,D~D&Z-@
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaapgkvttr 💥 auk+ *^c%1^\PC2qVi;g
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaapvkfwkv 💥 .,vNus(7m0'TyIEKHaKX
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaaqlxcssl 💥 ri%kSz\<mF +|,}=~NB9
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaasacwjzq 💥 Zx25[b K:94U>DPvV/(P
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaasqapqmw 💥 sc'S^?vOtrg;"8gF)U}f
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaatczlqqs 💥 bMob/6%C,=?an0fCtl^O
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaaxtjsnyi 💥 E0|^i;HKYSht*@T'FAqc
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaazjcrflx 💥 `]|D]>=4b8O>0{vwZ],e
chosen-prefix_hash_collisions_ftw_aaaaaaaaaaaaaaaaaaaaaaaazxwmsbm 💥 G0FFrj-[w]m pfx>W$Un
…