One of my professor organized a Hacking Week this semester but I didn’t have time to do it. Since I’m in holidays I thought I would take a look at it and write a bit about how I solved them.
Here’s the Crypto Challenge number 2 (out of 5) from this CTF (Capture The Flag):
user0:oTsx8NNn$bAjDZHpM7tCvHermlXKfZ0
user1:UxOdpNtW$funTxZxL/8y3m8STvonWj0
user2:w7YNTrjQ$0/71H7ze5o9/jCnKLt0mj0
user3:AIw2h09/$Ti0TRlU9mDpCGm5zg.ZDP.
user4:048HynE6$io7TkN7FwrBk6PmMzMuyC.
user5:T2QG6cUw$eIPlGIXG6KZsn4ht/Kpff0
user6:2aLkQ0oD$YRb6aFYMkzPoUCj70lsdX0
You have 7 different users with their respective password hashed and you have to find them. It’s just the 2nd out of 5 crypto problems, it’s pretty basic, but I never brute forced passwords for real before (I remember using John The Ripper when I was in middle school but that’s for script kiddies).
What’s Apr1 ? It’s a hash function that uses md5. And md5 is pretty weak, lots of rainbow tables on google.
This is how Apr1 looks in PHP according to Wikipedia, also the passwords are supposed to be alpha (a to z) in lowercase.
function apr1(<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>m</mi><mi>d</mi><mi>p</mi><mo>,</mo></mrow></math>salt) {
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>m</mi><mi>a</mi><mi>x</mi><mo>=</mo><mi>s</mi><mi>t</mi><mi>r</mi><mi>l</mi><mi>e</mi><mi>n</mi><mo stretchy="false">(</mo></mrow></math>mdp);
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>c</mi><mi>o</mi><mi>n</mi><mi>t</mi><mi>e</mi><mi>x</mi><mi>t</mi><mo>=</mo></mrow></math>mdp.'<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>'.$salt;
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>b</mi><mi>i</mi><mi>n</mi><mi>a</mi><mi>r</mi><mi>y</mi><mo>=</mo><mi>p</mi><mi>a</mi><mi>c</mi><mi>k</mi><msup><mo stretchy="false">(</mo><mi>′</mi></msup><mi>H</mi><msup><mn>32</mn><mi>′</mi></msup><mo>,</mo><mi>m</mi><mi>d</mi><mn>5</mn><mo stretchy="false">(</mo></mrow></math>mdp.<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>s</mi><mi>a</mi><mi>l</mi><mi>t</mi><mo>.</mo></mrow></math>mdp));
for(<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi><mo>=</mo></mrow></math>max; <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi><mo>></mo><mn>0</mn><mi>;</mi></mrow></math>i-=16)
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>c</mi><mi>o</mi><mi>n</mi><mi>t</mi><mi>e</mi><mi>x</mi><mi>t</mi><mo>.</mo><mo>=</mo><mi>s</mi><mi>u</mi><mi>b</mi><mi>s</mi><mi>t</mi><mi>r</mi><mo stretchy="false">(</mo></mrow></math>binary, 0, min(16, $i));
for(<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi><mo>=</mo></mrow></math>max; <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi><mo>></mo><mn>0</mn><mi>;</mi></mrow></math>i>>=1)
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>c</mi><mi>o</mi><mi>n</mi><mi>t</mi><mi>e</mi><mi>x</mi><mi>t</mi><mo>.</mo><mo>=</mo><mo stretchy="false">(</mo></mrow></math>i & 1) ? chr(0) : $mdp{0};
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>b</mi><mi>i</mi><mi>n</mi><mi>a</mi><mi>r</mi><mi>y</mi><mo>=</mo><mi>p</mi><mi>a</mi><mi>c</mi><mi>k</mi><msup><mo stretchy="false">(</mo><mi>′</mi></msup><mi>H</mi><msup><mn>32</mn><mi>′</mi></msup><mo>,</mo><mi>m</mi><mi>d</mi><mn>5</mn><mo stretchy="false">(</mo></mrow></math>context));
for(<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi><mo>=</mo><mn>0</mn><mi>;</mi></mrow></math>i<1000; $i++) {
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>n</mi><mi>e</mi><mi>w</mi><mo>=</mo><mo stretchy="false">(</mo></mrow></math>i & 1) ? <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>m</mi><mi>d</mi><mi>p</mi><mi>:</mi></mrow></math>binary;
if(<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi></mrow></math>new .= $salt;
if(<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi></mrow></math>new .= $mdp;
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>n</mi><mi>e</mi><mi>w</mi><mo>.</mo><mo>=</mo><mo stretchy="false">(</mo></mrow></math>i & 1) ? <math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>b</mi><mi>i</mi><mi>n</mi><mi>a</mi><mi>r</mi><mi>y</mi><mi>:</mi></mrow></math>mdp;
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>b</mi><mi>i</mi><mi>n</mi><mi>a</mi><mi>r</mi><mi>y</mi><mo>=</mo><mi>p</mi><mi>a</mi><mi>c</mi><mi>k</mi><msup><mo stretchy="false">(</mo><mi>′</mi></msup><mi>H</mi><msup><mn>32</mn><mi>′</mi></msup><mo>,</mo><mi>m</mi><mi>d</mi><mn>5</mn><mo stretchy="false">(</mo></mrow></math>new));
}
$hash = '';
for (<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi><mo>=</mo><mn>0</mn><mi>;</mi></mrow></math>i < 5; $i++) {
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>k</mi><mo>=</mo></mrow></math>i+6;
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>j</mi><mo>=</mo></mrow></math>i+12;
if(<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>j</mi><mo>=</mo><mo>=</mo><mn>16</mn><mo stretchy="false">)</mo></mrow></math>j = 5;
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>h</mi><mi>a</mi><mi>s</mi><mi>h</mi><mo>=</mo></mrow></math>binary{<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>i</mi><mi>}</mi><mo>.</mo></mrow></math>binary{<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>k</mi><mi>}</mi><mo>.</mo></mrow></math>binary{<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>j</mi><mi>}</mi><mo>.</mo></mrow></math>hash;
}
<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>h</mi><mi>a</mi><mi>s</mi><mi>h</mi><mo>=</mo><mi>c</mi><mi>h</mi><mi>r</mi><mo stretchy="false">(</mo><mn>0</mn><mo stretchy="false">)</mo><mo>.</mo><mi>c</mi><mi>h</mi><mi>r</mi><mo stretchy="false">(</mo><mn>0</mn><mo stretchy="false">)</mo><mo>.</mo></mrow></math>binary{11}.$hash;
$hash = strtr(
strrev(substr(base64_encode($hash), 2)),
'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/',
'./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
);
return '<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>'.<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>s</mi><mi>a</mi><mi>l</mi><mi>t</mi><msup><mo>.</mo><mi>′</mi></msup></mrow></math>'.$hash;
}
It seems pretty difficult to reverse. Let’s not forget that hashes are one-way functions and that they also lose information. I don’t know if they do lose information on a 7-letters-password though, but it seemed quite stupid to go down this road when I could just brute force it.
What language offers a good library to hash with Apr1? Well I didn’t know, and I felt like maybe Unix could do it well for me.
Turns out that OpenSSL has a command line for it:
openssl passwd -apr1 -salt SALT PASSWD
A quick bash script later:
#!/bin/bash
test[1]='<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>oTsx8NNn$bAjDZHpM7tCvHermlXKfZ0'
salt[1]='oTsx8NNn'
test[2]='<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>UxOdpNtW$funTxZxL/8y3m8STvonWj0'
salt[2]='UxOdpNtW'
test[3]='<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>w7YNTrjQ$0/71H7ze5o9/jCnKLt0mj0'
salt[3]='w7YNTrjQ'
test[4]='<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>AIw2h09/$Ti0TRlU9mDpCGm5zg.ZDP.'
salt[4]='AIw2h09/'
test[5]='<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>048HynE6$io7TkN7FwrBk6PmMzMuyC.'
salt[5]='048HynE6'
test[6]='<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>T2QG6cUw$eIPlGIXG6KZsn4ht/Kpff0'
salt[6]='T2QG6cUw'
test[7]='<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn></mrow></math>2aLkQ0oD$YRb6aFYMkzPoUCj70lsdX0'
salt[7]='2aLkQ0oD'
while read line
do
if [ "${#line}" == 7 ]
then
for num in {1..7}
do
noob=<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mo stretchy="false">(</mo><mi>o</mi><mi>p</mi><mi>e</mi><mi>n</mi><mi>s</mi><mi>s</mi><mi>l</mi><mi>p</mi><mi>a</mi><mi>s</mi><mi>s</mi><mi>w</mi><mi>d</mi><mo>−</mo><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn><mo>−</mo><mi>s</mi><mi>a</mi><mi>l</mi><mi>t</mi></mrow></math>salt[<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>n</mi><mi>u</mi><mi>m</mi><mo stretchy="false">]</mo></mrow></math>line)
if [ "<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>n</mi><mi>o</mi><mi>o</mi><mi>b</mi><mi>"</mi><mo>=</mo><mo>=</mo><mi>"</mi></mrow></math>test[$num]" ];
then
echo $line;
fi
done
fi
done < /usr/share/dict/words
I read the /user/share/dict/words that contains a simple dictionary of words on Unix, I try only the 7-letters-words.
The test ran in a few minutes and gave me nothing.
Well, I guess with a 7 letters password they must have used gibberish words. Let’s try a real bruteforce:
for a in {a..z}
do
for b in {a..z}
do
for c in {a..z}
do
for d in {a..z}
do
for e in {a..z}
do
for f in {a..z}
do
for g in {a..z}
do
truc=<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>a</mi></mrow></math>b<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>c</mi></mrow></math>d<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>e</mi></mrow></math>f$g;
for num in {1..7}
do
noob=<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mo stretchy="false">(</mo><mi>o</mi><mi>p</mi><mi>e</mi><mi>n</mi><mi>s</mi><mi>s</mi><mi>l</mi><mi>p</mi><mi>a</mi><mi>s</mi><mi>s</mi><mi>w</mi><mi>d</mi><mo>−</mo><mi>a</mi><mi>p</mi><mi>r</mi><mn>1</mn><mo>−</mo><mi>s</mi><mi>a</mi><mi>l</mi><mi>t</mi></mrow></math>salt[<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>n</mi><mi>u</mi><mi>m</mi><mo stretchy="false">]</mo></mrow></math>truc)
if [ "<math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><mrow><mi>n</mi><mi>o</mi><mi>o</mi><mi>b</mi><mi>"</mi><mo>=</mo><mo>=</mo><mi>"</mi></mrow></math>test[$num]" ];
then
echo $truc;
fi
done
done
done
done
done
done
done
done
It ran and ran and… nothing.
Well. Let’s not spend too much on this. There is John The Ripper that does this well and even oclHashcat that does this with the GPU.
Let’s create a john.conf with the following to limit the password to 7 letters:
[Incremental:Alpha7]
File = $JOHN/alpha.chr
MinLen = 7
MaxLen = 7
CharCount = 26
Let’s launch John:
john -i=Alpha7 hackingweek.txt
(don’t forget to put the hashed password in hackingweek.txt).
Wait and wait and wait.. and get the passwords =)
