There has been only 1 other successful submission at this point, and that's by Dave Walker.
My sincere congratulations to both Adam and Dave.
I'll describe the solution below. This information will likely be useful in solving Daemon Challenge 3. I recommend working through it, if you intend on competing in the next challenge.
The Solution
I told you that the wrapped-passphrase file contains a 128-bit mount passphrase, encrypted using a wrapping passphrase. This perfectly mirrors a normal Encrypted Private Directory setup in Ubuntu, where your login passphrase is used as a wrapping passphrase.
You can use the ecryptfs-unwrap-passphrase utility to (attempt) to unwrap a wrapped passphrase file.
Clearly, trying to brute-force attack the mount passphrase is impractical. That's 2^128 combinations that need to be tested. That's 3.4 x 10^38. A very big number indeed.
The login passphrase, clearly, is the weaker link, and easier to attack. And I gave you two significant hints. I told you that it consists entirely of alphanumeric characters, and that you could break it within 48 hours. There are 62 unique characters among [A-Za-z0-9]. But you do not know the length. A simple calculation, though can narrow that search.
First, let's get a feel for how many password attempts you can make per second. Let's just see how long it takes to try 100 passwords. I don't expect any of these to succeed. I'm only interested in the rate.
$ time seq 1 100 | xargs -i ecryptfs-unwrap-passphrase wrapped-passphrase {} 2>&1 >/dev/nullOkay, so I was able to attempt 100 passphrases in 23 seconds. That's about 4.3 attempts per second.
real 0m23.487s
user 0m21.481s
sys 0m0.180s
So for each of the following passphrase lengths, let's see how long it would take to test the entire keyspace:
- 62 / 4.3tries/sec = 14 seconds
- 62*62 / 4.3tries/sec / 60sec/min= 15 minutes
- 62*62*62 / 4.3tries/sec / 60sec/min / 60 min/hour = 15.4 hours
- 62*62*62*62 / 4.3tries/sec / 60sec/min / 60 min/hour = 40 days
I'm going to take this opportunity to re-enforce the importance of having a high quality passphrase! Let's do this calculation one more time, with a larger set of valid characters, [a-zA-Z0-9~!@#$%^&*()-_=+[]{}|;:'",<.>/?]. That should add about 30 characters. So instead of 62, we have 92 valid characters. Let's also hope that your login passphrase is at least 8 characters long. In this case, we have:
92*92*92*92*92*92*92*92 / 4.3 / 60 / 60 / 24 / 365 = 37 million years
That should take a bit longer ;-)
Now, that 4.3 number was very conservative. There's a few ways we can increase our number of tries per second--primarily through parallel processing.
Let's assume you can crank through the 1- and 2- character long passphrases, and you do not get a hit (you won't).
Let's write a script that will generate every 3-character alphanumeric passphrase:
#!/bin/sh
# generate_passphrases.sh
CHARS="a b c d e f g h i \
j k l m n o p q r s t u v \
w x y z A B C D E F G H I \
J K L M N O P Q R S T U V \
W X Y Z 0 1 2 3 4 5 6 7 8 9"
for i in $CHARS; do
for j in $CHARS; do
for k in $CHARS; do
echo "$i$j$k"
done
done
done
Run that script and output it to a file.
$ ./generate_passphrases.sh > /tmp/passphrasesOkay, so we have 238,328 passphrases we need to test. So you could start crunch through these at this point, in a single thread, on a single system. But most laptops these days have multi-core cpu's. And you might even have access to multiple machines.
$ wc -l /tmp/passphrases
238328 /tmp/passphrases
I have 8 dual-core machines running Ubuntu at my immediate disposal. I'm going to run my 2 instances of my cracking thread on each of these systems. So I'm going split that passphrase file into 16 equal parts (14896 passphrases per file).
$ split -l 14896 /tmp/passphrases
$ ls x*
xaa xab xac xad xae xaf xag xah xai xaj xak xal xam xan xao xap
Yeah, the split command has some wierd idiosyncrasies. There are better ways of doing this, but split is simple, and fast.
Now, I need a small script to attempt the passphrase cracking. This script will take one of our generated passphrase files as an input argument. It will try each of those, printing a status message to screen (to track progress), and will exit 0 if/when it finds a correct passphrase. Note that I also have it send an email message to me. I customized that to send me a text message via SMS to my cell phone ;-)
#!/bin/sh
# try_passphrases.sh
INPUT="$1"
passphrases=`cat $INPUT`
total=`wc -l $INPUT`
i=0
for p in $passphrases; do
ecryptfs-unwrap-passphrase wrapped-passphrase "$p" 2>&1 >/dev/null
if [ "$?" = "0" ]; then
echo "FOUND: $p"
echo "FOUND: $p" | mail me@example.com
exit 0
fi
i=`expr $i + 1`
echo "($p) $i / $total"
done
exit 1
So now, copy this script and two of these input files to each machines. You could use something like puppet to send this information to each system. I didn't mind starting each of these individually, with:
$ time ./try_passphrase.sh xap2 | tee /tmp/outAnd, in less than hour, one of the processes hit the winner:
FOUND: 9zDSweet, now, let's decrypt the mount passphrase:
$ ecryptfs-unwrap-passphrase wrapped-passphrase 9zDSo there's the mount passphrase! Also, let's look at that warning message briefly... I also gave the hint in the challenge that we're using the default eCryptfs salt. For added security, you should always consider adding a salt to such passphrases. There's a simplicity/complexity trade off. Just something you should consider in your own environments and use cases.
Unable to read salt value from user's .ecryptfsrc file; using default
904e740f417955457a5d56accd40ee01
Now, we can use that mount passphrase to establish an ecryptfs mount, and view the contents of challenge_2.txt.
$ mkdir /tmp/1 /tmp/2And we can view the contents of challenge_2.txt:
$ cp challenge_2.txt /tmp/1
$ sudo mount -t ecryptfs /tmp/1 /tmp/2
Select key type to use for newly created files:
1) pkcs11-helper
2) openssl
3) passphrase
4) tspi
Selection: 3
Passphrase: 904e740f417955457a5d56accd40ee01
Select cipher:
1) aes: blocksize = 16; min keysize = 16; max keysize = 32 (not loaded)
2) blowfish: blocksize = 16; min keysize = 16; max keysize = 32 (not loaded)
3) des3_ede: blocksize = 8; min keysize = 24; max keysize = 24 (not loaded)
4) twofish: blocksize = 16; min keysize = 16; max keysize = 32 (not loaded)
5) cast6: blocksize = 16; min keysize = 16; max keysize = 32 (not loaded)
6) cast5: blocksize = 8; min keysize = 5; max keysize = 16 (not loaded)
7) arc4: blocksize = 1; min keysize = 1; max keysize = 256 (loaded)
Selection [aes]: aes
Select key bytes:
1) 16
2) 32
3) 24
Selection [16]: 16
Enable plaintext passthrough (y/n) [n]: n
Attempting to mount with the following options:
ecryptfs_key_bytes=16
ecryptfs_cipher=aes
ecryptfs_sig=dfa024f15f2d12e7
Mounted eCryptfs
$ head -n 5 /tmp/2/challenge_2.txtPage down a bit, if you want the solution to this riddle. Or don't go below here, if you want to try and solve it for fun :-)
Challenge 2:
--------------------------------------------------------------------------
What is the full name of the research partner of a cryptographer who's first name matches the name of a dog on a tv show which has featured a vessel named after the video game played in a movie filmed near the largest city served by the United States telephone area code matching the greatest prime factor of the number of the asteroid named after the person possibly killed by a squeamish ossifrage?
--------------------------------------------------------------------------
Answer: ?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
As tempting as it might be to start at the beginning or somewhere in the middle, it's easiest if you start at the end.
- "squeamish ossifrage" is a tribute to the RSA crypto cipher challenge Ron Rivest posed in 1977. The answer to his challenge was, "The Magic Words are Squeamish Ossifrage"
- An ossifrage is a lammergeier or bearded vulture, Gypaetus barbatus (note the "ae" dipthong)
Legend says (hence the 'possible') that the Greek Aeschylus playright was killed by one of these scary birds dropping a stone on his head. (Again, note the "ae" dipthong.) - Asteroid 2876 is named after him
- 719 is the greatest prime factor of 2876
Prime factors are the basis for most modern cryptography! - Area code 719 serves greater Colorado Springs, CO
- A number of movies were filmed in the Colorado Springs area
But one movie should really stand out to any hacker...WarGames! If it doesn't immediately jump out at you, you might need to do some thinking and research :-) - Dig around for some trivia about the movie, if you don't remember it clearly enough. You'll find that Matthew Broderick had to practice his skills at Galaga quite a bit for the role and the scenes where he plays the game in the film.
- Some basic research on Galaga (one of the best arcade games ever!) should reveal that the submarine in Lost is actually named in honor of the game, as the writers of that show love the game too ;-)
- I'm a big fan of Lost, so I know that there are a couple of dogs that make appearances here and there. But there's certainly one that's been around the longest, and that's Vincent.
- There are probably more than one cryptographer named, 'Vincent', but at least the first page of Google, when searching for 'vincent cryptographer' is dedicated to Vincent Rijmen.
- Vincent Rijmen is the co-inventor of the AES encryption algorithm, which is at the core of eCryptfs.
- And his research partner, co-inventor of AES, is Joan Daemen
The Next Challenge
So the next challenge will build upon this one. I recommend working through some of the exercises on this page and getting comfortable with them.
Additionally, to submit your answer to the final challenge, you will need to use GPG email signatures and encryption. Your public key will need to be hosted on a PKI key server, such as pgp.mit.edu, or even on Launchpad.net.
Good luck!
Cheers,
:-Dustin
I'm glad I didn't try to solve it! :P
ReplyDeleteWell, I'm glad to see that I got the right idea. Trouble is my single-core, 4 year old CPU is still crunching through them!
ReplyDelete(And if only I'd put the digits first in the list of chars I'd literally have got there a day ago!).
Oh well :)