Cracking a LUKS password/passphrase when parts of the passphrase are known

I went on vacation a few months ago only to come back to a laptop that had important docs on it with an encrypted root partition that I forgot the passphrase too.

DOH!

At first I thought I had a valid backup before I left, however, due to an rdiff-backup error I didn't properly respond to, the backup tanked, and had been tanking for a whole year.  (Noted: test my backups once in a while) It doesn't really matter what the error message was, point was if I couldn't remember the password, and I had about a year of data that would be lost if I couldn't dig it out of my brain.

Luckily... or so I thought, I had my passphrase documented and securely stored. After hours of searching for this and typing in the wrong passphrase countless times, I realized that I may indeed have lost a ton of valuable data.

What to do...

I remembered most of the passphrase, but had spaces, uppercase/lowercase, and special characters mixed up.

I searched the Internet for programs that exist to try combinations with known parts but failed to find one that would do what I needed it too. There were a few questions posed about this subject, but most of the responses were from people that said "You're screwed" or something along those lines. LUKS has a built in mechanism (PBKDF2) that significantly adds to the time it takes to perform a brute force. This can be configured at the LUKS partition creation with the --iter-time switch when running "cryptsetup lukeFormat".

Once I tested that I could successfully echo passwords to STDIN to the cryptsetup program to decrypt the drive, I set out to write the program.

After doing some searching, I found a perl module that fit the bill for running through combinations of a set of arrays.

The perl module is Set-CrossProduct which allowed me to write simple code that ran through all the combinations I thought my password might be.

For example, If I wanted to try variations of "Cats" depending on how I spell it.

This would require 3 arrays with the following values:
C,K (C or K)
4,a (4 or a)
tz,ts (tz or ts)

Which would output:
K4ts
K4tz
Kats
Katz
C4ts
C4tz
Cats
Catz



Armed with this module, I set out to write the script.

combos.pl (see below) was the result. When run it would echo all combinations of 11 arrays that I set up from what I remember of the passphrase.

The result of the below program is 25600 results, which outputs one password per line, then exits after all combinations have been exhausted.

trypass.sh  (see below) is a bash script that takes the output of combos.pl and attempts to decrypt the partition. Upon it's success it will exit, and display the passphrase. It also displays the current iteration and estimated time to completion while it's running.

How to use this script:

• Boot up with a live CD, I used my favorite liveCD distro BackTrack .

• Install the Set-CrossProduct perl module. I did this by using "perl -MCPAN -e install Set::CrossProduct". For more instructions regarding installing perl modules go here.

• Adjust the arrays in combos.pl to fit your needs.

• Adjust trypass.sh with the proper path to your LUKS encrypted partition.

Then run the program:

./trypass.sh

Go get some coffee, read a book, or work on a project.


If the stars align and you setup your combination arrays correctly you'll get a awesome status message "key slot X unlocked"

Good luck and God Speed!

~ stevo

combos.pl

-----------------------------------------

#!/usr/bin/perl

use Set::CrossProduct;

#write
my         @a = ("K");
my         @b = ("ats","atz");
my         @c = (' w',' W','W','w');
my         @d = ('earing');
my         @e = (' h',' H','h','H');
my         @f = ('ats','atz');
my         @g = (
       " (",
       " )",
       ")",
       "(",
       "",
);
my         @h = (
       ' P',
       'P',
       ' p',
       'p',
);
my @i = ("otatoe");
my @j = (" ("," )","(",")","");
my @k = ("!","\$","&","");


my $i = Set::CrossProduct->new([\@a, \@b,\@c,\@d,\@e,\@f,\@g,\@h,\@i,\@j,\@k]);
my @combos = $i->combinations;

foreach my $item (@combos) {
foreach (@$item) {
   print $_;
}
   print "\n";
}

trypass.sh

-----------------------------------------

#!/bin/bash

begin=$(date)
begin_sec=$(date +%s)
try=0
total=$(./combos.pl | wc -l)

./combos.pl | while read i; do
    if echo "${i}" | cryptsetup luksOpen /dev/sda3 mount_st_awesome -; then
       echo "********* ${i} *********** Success!"
       exit
    fi

    try=$(expr ${try} + 1)
    now_sec=$(date +%s)

    echo "try: ${try} of ${total}"
    echo "${i}"
    average=$(echo "((${now_sec} - ${begin_sec}) / ${try})" | bc -l)
    eta=$(echo "((${total} - ${try}) * ${average}) + ${now_sec}" | bc | awk '{print int($1+0.5) }' )
    eta_date=$(echo $(date -d "1970-01-01 UTC ${eta} seconds"))
    echo "ESTIMATED COMPLETION: ${eta_date}"
    echo
done