Recovering a forgotten LUKS password

A friend of mine just forgot the fulldisk encryption password for a laptop.. sounds like a fun little adventure!

This is not exactly a new topic, there are nice posts about this problem such as this one, however this is how I’ve tried to tackle the problem.

The password was generated according to a couple of rules and only partially lost.

Lets assume here for the sake of this little post that the password was generated by using a word list and contained multiple words, some of which are missing.

Lets build ourselves a little prototype:

First let’s grab a wordlist, in this case lets grab a copy of the EFFs short word list from here:

$ wget https://www.eff.org/files/2016/09/08/eff_short_wordlist_1.txt
--2023-11-03 18:34:27--  https://www.eff.org/files/2016/09/08/eff_short_wordlist_1.txt
Resolving www.eff.org (www.eff.org)... 2a04:4e42:8d::201, 146.75.116.201
Connecting to www.eff.org (www.eff.org)|2a04:4e42:8d::201|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: 13660 (13K) [text/plain]
Saving to: ‘eff_short_wordlist_1.txt’

eff_short_wordlist_1.txt                        100%[====================================================================================================>]  13.34K  --.-KB/s    in 0.002s

2023-11-03 18:34:28 (6.58 MB/s) - ‘eff_short_wordlist_1.txt’ saved [13660/13660]

$ head eff_short_wordlist_1.txt
1111    acid
1112    acorn
1113    acre
1114    acts
1115    afar
1116    affix
1121    aged
1122    agent
1123    agile
1124    aging

$ cat wordlist.txt | wc -l
1296

Taking a look at the wordlist, we can see it contains two columns and is 1.3k lines long, since we are only interested in the words itself and this is an example, lets create a new shorter wordlist file:

$ shuf -n 100 eff_short_wordlist_1.txt | sort | cut -f 2- > wordlist.txt

$ head wordlist.txt
aloft
arson
bagel
bunny
cache
cheer
cleat
clump
comma
crush

$ cat wordlist.txt | wc -l
100

Now lets generate a file containing all possible passwords according to what we know. We have a couple of words we know and are missing two of them, but we know the positions of the missing words.

Lets grab a couple of words start with so we can generate a test password:

$ shuf -n 6 wordlist.txt
march
scoff
large
drove
wavy
crush

So lets assume our password is the following string with X and Y being the missing words:

march scoff X large drove wavy Y crush

Based on this we can quickly generate a list of possible passwords from the wordlist:

input_string="march scoff X large drove wavy Y crush"
readarray -t words < wordlist.txt

for word_x in "${words[@]}"; do
  for word_y in "${words[@]}"; do
    replaced_string="${input_string/X/$word_x}"
    replaced_string="${replaced_string/Y/$word_y}"
    echo "$replaced_string"
  done
done > password_list

This gives us a list with 10000 possible combnations for passphrases.

However we can probably assume, that the forgotten passphrase does not contain the same two words twice, so lets cut it down a bit further:

input_string="march scoff X large drove wavy Y crush"
readarray -t words < wordlist.txt

for word_x in "${words[@]}"; do
  for word_y in "${words[@]}"; do
    replaced_string="${input_string/X/$word_x}"
    replaced_string="${replaced_string/Y/$word_y}"
    if [[ "$word_x" != "$word_y" && "$input_string" != *"$word_x"* && "$input_string" != *"$word_y"* ]]; then
      echo "$replaced_string"
    fi
  done
done > password_list

This way we end up with only 8742 possible words, so we have already eliminated ~13% of possible passwords, nice.

At this point we’ve generated every possible combination that makes sense to check, however the word list still looks like this:

$ head password_list
march scoff aloft large drove wavy arson crush
march scoff aloft large drove wavy bagel crush
march scoff aloft large drove wavy bunny crush
march scoff aloft large drove wavy cache crush
march scoff aloft large drove wavy cheer crush
march scoff aloft large drove wavy cleat crush
march scoff aloft large drove wavy clump crush
march scoff aloft large drove wavy comma crush
march scoff aloft large drove wavy cycle crush
march scoff aloft large drove wavy dab crush

Lets add some randomness into the mix by shuffling the order around:

$ shuf password_list > passwords

$ head passwords
march scoff thud large drove wavy icon crush
march scoff deck large drove wavy slimy crush
march scoff said large drove wavy slept crush
march scoff jet large drove wavy snap crush
march scoff penny large drove wavy fiber crush
march scoff decoy large drove wavy slept crush
march scoff wipe large drove wavy spoon crush
march scoff clump large drove wavy recap crush
march scoff deck large drove wavy fiber crush
march scoff said large drove wavy radar crush

This looks way better already, now a script running through every line of that list won’t be prone to extensive runtime due to alphabetical ordering. Hopefully that will speed things up a bit.

Next we need to take a quick look at LUKS partitions. Luckily for us, LUKS stores the encryption key in its header, which can be used independently from the rest of the partition.

So lets quickly create a small (128MB+Header) LUKS container which we can use to test our little script:

$ dd if=/dev/urandom of=luks_container.img bs=1M count=128

$ cryptsetup --verify-passphrase luksFormat luks_container.img

WARNING!
========
This will overwrite data on luks_container.img irrevocably.

Are you sure? (Type 'yes' in capital letters): YES
Enter passphrase for luks_container.img:
Verify passphrase:

In my case I chose the words from line 100 of the password file as passphrase:

$ head -n 100 passwords | tail -n 1
march scoff deck large drove wavy jet crush

We can now non-interactively check for the password and get a return code of 0 in case of success and 2 in case of the wrong password:

$ echo "march scoff deck large drove wavy jet crush" | cryptsetup luksOpen --test-passphrase luks_container.img
$ echo $?
0

$ echo "not the password!" | cryptsetup luksOpen --test-passphrase luks_container.img
No key available with this passphrase.
$ echo $?
2

Now lets detach the LUKS container header:

$ cryptsetup luksHeaderBackup --header-backup-file luks_container_header luks_container.img
$ ls -lah
Permissions Size User Date Modified Name
...
.rw-r--r--  134M tiwa  3 Nov 19:18  luks_container.img
.r--------   17M tiwa  3 Nov 19:22  luks_container_header
...

At this point we are left with a 17MB header file, which we can use independently from the encrypted data to check for the password. The header behaves exactly like the LUKS container:

$ echo "march scoff deck large drove wavy jet crush" | cryptsetup luksOpen --test-passphrase luks_container_header
$ echo $?
0

$ echo "not the password!" | cryptsetup luksOpen --test-passphrase luks_container_header
No key available with this passphrase.
$ echo $?
2

Bruteforcing the password is quite easily done with a simple loop:

start_time=$(date +%s)
line_number=0
while IFS= read -r line; do
  ((line_number += 1))
  echo $line_number > progress
  echo "$line" | cryptsetup luksOpen --test-passphrase luks_container_header
  return_code=$?
  if [ $return_code -eq 0 ]; then
    end_time=$(date +%s)
    runtime=$((end_time - start_time))
    formatted_runtime=$(date -u -d @$runtime +'%H:%M:%S')
    echo "Total runtime : $formatted_runtime" >> result
    echo "PASSPHRASE    : $line" >> result
    exit 0
  elif [ $return_code -eq 2 ]; then
    continue
  fi
done < passwords

Running the script with the correct password in line 100 took about 4min on my laptop:

Total runtime : 00:03:58
PASSPHRASE    : march scoff deck large drove wavy jet crush

Now lets add parallel into the mix, a tool, which can run bash functions concurrently on their input. On NixOS we can simply use nix-shell to grab a version of it:

$ nix-shell -p parallel
...
$ parallel --help
Usage:

parallel [options] [command [arguments]] < list_of_arguments
parallel [options] [command [arguments]] (::: arguments|:::: argfile(s))...
cat ... | parallel --pipe [options] [command [arguments]]
...

From there we just need to rewrite our code to use a function instead of a while loop and then use parallel in order to input the passphrases line by line.

start_time=$(date +%s)

check_passphrase() {
  start_time="$1"
  line="${@: -1}"
  echo "$line" | cryptsetup luksOpen --test-passphrase luks_container_header
  return_code=$?
  echo -n '.' >> progress
  if [ $return_code -eq 0 ]; then
    end_time=$(date +%s)
    runtime=$((end_time - start_time))
    formatted_runtime=$(date -u -d @$runtime +'%H:%M:%S')
    echo "Total runtime : $formatted_runtime" >> result
    echo "PASSPHRASE    : $line" >> result
    exit 1
  fi
}

export -f check_passphrase

parallel --halt 1 --line-buffer -a passwords check_passphrase $start_time

Using parallel the script ran only a tiny bit faster, which initially did not look too impressive for a speedup:

Total runtime : 00:03:52
PASSPHRASE    : march scoff deck large drove wavy jet crush

However my laptop only has 4 cores, whereas my desktop for example has 12 all of which are a bit more powerful, there already the speedup is quite significant already almost cutting the time it took to find the password in half:

$ cat result # without parallel
Total runtime : 00:04:15
PASSPHRASE    : march scoff deck large drove wavy jet crush
$ cat result # with parallel
Total runtime : 00:01:46
PASSPHRASE    : march scoff deck large drove wavy jet crush

In conclusion, given with access to multiple machines (and by splitting up the password list in a way that makes sense), it is probably possible to get ahold of the password in time.

If something should go wrong we can even recover the progress by looking into the ./progress file, counting the dots and removing as many lines from the password list.