Hey! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

# Slim

## posted August 2014

I talked about Slim the other day. I wanted to do a similar project not so long ago that I would have called weblang.

I first thought about an indented language with no symbols to declare html elements. Something like that:

p
ul
li
hey !

But then I thought, how will I distinguish markups from text. If I want to write ul without it being translated to <ul></ul>, how do I do that?
And if I want to write several lines of text, will I have to indent them all the time ?

## posted May 2014

If you're a college student in the US today might be your lucky day. Coinbase is offering 10$in bitcoin to students from some american universities. I guess if yours is not accepted you can ask them directly. To support bitcoin awareness among college students, today we are announcing a bitcoin giveaway: we are gifting$10 worth of bitcoin to students who create a new Coinbase account using their .edu email address.

Here you go

comment on this story

# Bruteforce Apr1 hashes.

## posted May 2014

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:$apr1$oTsx8NNn$bAjDZHpM7tCvHermlXKfZ0 user1:$apr1$UxOdpNtW$funTxZxL/8y3m8STvonWj0
user2:$apr1$w7YNTrjQ$0/71H7ze5o9/jCnKLt0mj0 user3:$apr1$AIw2h09/$Ti0TRlU9mDpCGm5zg.ZDP. user4:$apr1$048HynE6$io7TkN7FwrBk6PmMzMuyC. user5:$apr1$T2QG6cUw$eIPlGIXG6KZsn4ht/Kpff0 user6:$apr1$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($mdp, $salt) {$max = strlen($mdp);$context = $mdp.'$apr1$'.$salt;
$binary = pack('H32', md5($mdp.$salt.$mdp));
for($i=$max; $i>0;$i-=16)
$context .= substr($binary, 0, min(16, $i)); for($i=$max;$i>0; $i>>=1)$context .= ($i & 1) ? chr(0) :$mdp{0};
$binary = pack('H32', md5($context));
for($i=0;$i<1000; $i++) {$new = ($i & 1) ?$mdp : $binary; if($i % 3) $new .=$salt;
if($i % 7)$new .= $mdp;$new .= ($i & 1) ?$binary : $mdp;$binary = pack('H32', md5($new)); }$hash = '';
for ($i = 0;$i < 5; $i++) {$k = $i+6;$j = $i+12; if($j == 16) $j = 5;$hash = $binary{$i}.$binary{$k}.$binary{$j}.$hash; }$hash = chr(0).chr(0).$binary{11}.$hash;
$hash = strtr( strrev(substr(base64_encode($hash), 2)),
'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/',
'./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
);
return '$apr1$'.$salt.'$'.$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]='$apr1$oTsx8NNn$bAjDZHpM7tCvHermlXKfZ0'
salt[1]='oTsx8NNn'

test[2]='$apr1$UxOdpNtW$funTxZxL/8y3m8STvonWj0' salt[2]='UxOdpNtW' test[3]='$apr1$w7YNTrjQ$0/71H7ze5o9/jCnKLt0mj0'
salt[3]='w7YNTrjQ'

test[4]='$apr1$AIw2h09/$Ti0TRlU9mDpCGm5zg.ZDP.' salt[4]='AIw2h09/' test[5]='$apr1$048HynE6$io7TkN7FwrBk6PmMzMuyC.'
salt[5]='048HynE6'

test[6]='$apr1$T2QG6cUw$eIPlGIXG6KZsn4ht/Kpff0' salt[6]='T2QG6cUw' test[7]='$apr1$2aLkQ0oD$YRb6aFYMkzPoUCj70lsdX0'
salt[7]='2aLkQ0oD'

do
if [ "${#line}" == 7 ] then for num in {1..7} do noob=$(openssl passwd -apr1 -salt $salt[$num] $line) if [ "$noob" == "$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=$a$b$c$d$e$f$g;

for num in {1..7}
do
noob=$(openssl passwd -apr1 -salt$salt[$num]$truc)
if [ "$noob" == "$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 =) comment on this story # Find all the pairs in a list that are summing to a known number ## posted May 2014 I got asked this question in an interview. And I knew this question beforehands, and that it had to deal with hashtables, but never got to dig into it since I thought nobody would asked me that for a simple internship. I didn't know how to answer, in my mind I just had a simple php script that would have looked like this: $arr = array(-5, 5, 3, 1, 7, 8);
$target = 8; for($i = 0; $i < sizeof($arr) - 1; $i++) { for($j = $i + 1;$j < sizeof($arr);$j++)
{
if($arr[$i] + $arr[$j] == $target) echo "pair found:${arr[i]}, \${arr[j]}";
}
}

But it's pretty slow, it's mathematically correct, but it's more of a CS-oriented question. How to implement that quickly for machines? The answer is hash tables. Which are implemented as arrays in PHP (well, arrays are like super hash tables) and as dictionaries in Python.

I came up with this simple example in python:

arr = (-5, 5, 3, 1, 7, 8)
target = 8

dic = {}

for i, item in enumerate(arr):
dic[item] = i

if dic.has_key(target - item) and dic[target - item] != i:
print item, (target - item)
1. iterate the list
2. assign the hash of the value to the index of the value in the array
3. to avoid finding a pair twice, we do this in the same for loop:
we do the difference of the target sum and the number we're on, we hash it, if we find that in the hash table that's good!
4. but it could also be the number itself, so we check for its index, and it has to be different than its own index.

Voilà! We avoid the n-1! additions and comparisons of the first idea with hash tables (I actually have no idea how fast they are but since most things use hash tables in IT, I guess that it is pretty fast).

comment on this story