JIYIK CN >

Cryptocurrency enthusiast Christian 'CodesInChaos' Winnerlein once wrote:

plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd and eBkXQTfuBqp'cTcar&g* have the same PBKDF2-HMAC-SHA1 hash.

This intrigued me, so I decided to find out what was going on and why. If you’re curious, keep reading.

To confirm these findings, I wrote a Node.js script:

#!/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)');

Running the script confirms that the two strings do have the same PBKDF2-HMAC-SHA1 hash.

illustrate

PBKDF2is a widely used method to derive a key of a given length from a given password, salt, and number of iterations. In this case, it exclusively uses the HMACand SHA-1hash functions, which are the defaults per RFC2898.

HMACThere is one interesting property: if the key provided is longer than the block size of the hash function being used, it uses the hash of the key instead of the key itself.

SHA-1The block size is 512 bits, which is equal to 64 bytes.

So in this case, if the supplied key takes up more than 64 bytes, then use SHA1(key)as the key. More generally, for any chosen_password larger than 64 bytes, the following holds (pseudocode):

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

请注意, the smallest of the two passwords will always be 20 characters long, because SHA1the hash will always consist of exactly 40 hexadecimal digits representing 20 bytes. One byte, or two hexadecimal digits, is used for each character in the colliding password.

For example, in Bash:

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

That's why plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmdand eBkXQTfuBqp'cTcar&g*have the same PBKDF2-HMAC-SHA1hash.

result

This effectively means that we can come up with any number of PBKDF2-HMAC-SHA1collisions. In fact, the same trick can be applied just by using PBKDF2 with HMAC and any hashing algorithm - the only variable is the block size of the hash function. PBKDF2-HMAC-anythingIt is easy to find colliding passwords when hashing with .

plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmdSo why did Chris choose and among all possible collisions eBkXQTfuBqp'cTcar&g*?

$ printf 'lolololololololololololololololololololololololololololololololol' | sha1sum
6ff0b2d76dae24f8b58472ba19f918f07359c0c0

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

While it's easy to find collisions for any given string larger than 64 bytes (just run the Bash command above), it gets a bit trickier if we want the colliding password to consist only of readable ASCII characters. SHA1A hash can contain any hexadecimal digits, and converting such a hash back to a string may result in at least one character being outside the printable ASCII range ( [\x20-\x7E]).

I wrote a Python script to brute force PBKDF2-HMAC-SHA1collisions where relatively long passwords (> 64 bytes) have a chosen prefix and the colliding password contains only printable ASCII characters.

#!/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)

First, I let it run for a few hours without specifying a prefix, and it found the following conflicts:

$ ./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)
…

The brute force collision with the chosen prefix is ​​more interesting though:

$ ./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
…