Bruteforcing LUKS Volumes Explained

Some weeks back, we were forced to reboot one of our server machines because it stopped responding. When the machine came back up, we were greeted with a password prompt to decrypt the partition. No problem, since we always used a password combination (ok, permutation) that consisted of a few words, something along the lines of “john”, “doe”, “1954”, and the server’s serial number. Except that it didn’t work, and we forgot the permutation rules AND whether we used “john” “doe” or “jack” “daniels”.

All the search results for bruteforcing LUKS are largely the same — “use cryptsetup luksOpen --test-passphrase“. In my case, the physical server is in the server room, and I don’t want to stand in front of the rack trying to figure all this out. My question is, can I do this offline on another machine? None of those blog entries were helpful in this regard.

The LUKS Header

To answer this question, I took a look at the LUKS header. This header is what provides multiple “key slots”, allowing you to specify up to 8 passwords or key files that can decrypt the volume. cryptsetup is the standard userspace tool (and library) to manipulate and mount LUKS volumes. Since LUKS was designed based on TKS1, the TKS1 document referenced by the cryptsetup project was very helpful. After consulting the documentation & code, I came up with the following diagram that describes the LUKS key verification process:

LUKS encryption flowchart

Basically, rectangular blocks represent pieces of data and parallelograms represent processes, specifically crypto operations. Gray data blocks are stored in the LUKS header, whereas clear data blocks are not.

  1. The user-provided password goes through the standard Password-Based Key Derivation Function 2 (PBKDF2), with the parameters specified in the LUKS header.
  2. This forms a key, which is then used to decrypt (using the specified block cipher and mode) the encrypted master key (MK) that is stored in anti-forensics (AF) stripes. The AF stripes cause the key to be stored across a large amount of disk space, such that the erasure of a single stripe renders the key unrecoverable.
  3. Once the master key (MK) is decrypted, it can be used to decrypt the data stored in the volume.
  4. LUKS provides a means for verifying the master key by having stored the MK digest. This digest is also computed using PBKDF2, but using a different set of parameters. By comparing the computed MK digest against the one stored in the header, the correctness of the MK (and hence the user password) can be verified.

As you can see, the LUKS header (plus key slot area) alone is sufficient for the recovery of passwords or key files. Given an input password, its correctness can be verified by going through PBKDF2, block cipher decryption, followed by another PBKDF2. Thus to prevent bruteforcing, the number of PBKDF2 iterations are chosen such that they take a sufficiently long time (1000ms) for one verification on that particular machine. The various parameters stored in the header can be viewed using cryptsetup luksDump.

The LUKS header can be extracted using cryptsetup:

cryptsetup luksHeaderBackup \
    --header-backup-file /path/to/save-headers \
    /dev/encrypted-partition

Once the header has been extracted, the conventional luksOpen technique so commonly described can be used on this backup file.

Bruteforcing the Password

Initially, I looked at John the Ripper, a popular password bruteforcing tool. I found that it does have LUKS support in the bleeding-jumbo branch. Apparently you use the luks2john utility to preprocess the LUKS partition/header, then use john to actually bruteforce the processed file. However it didn’t work. Also, I couldn’t find a way to make it use password combination like the ones I described earlier.

I fell back to using just a Python script that calls cryptsetup, because the bruteforce was definitely not going to take long and that was not worth optimizing or constructing an elaborate program:

#!/usr/bin/python

from itertools import permutations
import subprocess 
import sys

words = ['jack', 'daniels', 'john', 'doe', '1952', 'c5295bfeed0']

luks_file = sys.argv[1]

for combo in permutations(words, 4):
    passwd = ''.join(combo)
    print 'Trying %s...' % repr(passwd)

    r = subprocess.call('echo %s | cryptsetup luksOpen --test-passphrase %s' % (passwd, luks_file), 
                shell=True, stdout=None, stderr=None)
    if r == 0:
        print 'Password is %sn' % repr(passwd)
        break

Take note that the cryptsetup bundled with CentOS allocates a device first, for the verification of passphrase as well as mounting:

Enter passphrase for /home/darell/luks-header.bin:
# Trying to open key slot 0 [ACTIVE_LAST]
# Reading key slot 0 area.
# Allocating a free loop device.
Cannot use a loopback device, running as non-root user.
Device /home/darell/luks-header.bin doesn’t exist or access denied.

For this reason, it makes the bruteforcing process slightly slower and it also requires root privileges. You will therefore want to use a fairly recent cryptsetup, at least version 1.6.6, which processes the LUKS keyslots in userspace instead (commit a3c0f6), removing the need for root privileges when verifying passphrases. Here is the speed comparison for 19 tries:

  • cryptsetup 1.6.3 — 14.744s
  • cryptsetup 1.7.0 — 14.098s
  • speed up: 0.646s

Avoiding the device allocation and setup saves more than half a second, which isn’t much but it does add up over several iterations. There are probably more efficient ways to bruteforce LUKS, such as using multiple threads instead of just one. That’s exactly what bruteforce-luks (GitHub) does, and by directly invoking the cryptsetup API, the process fork costs are eliminated. I did not use this because it performs a “dumb” bruteforce, and it doesn’t support custom passwords rules like the combinations I mentioned.

Good News Everyone!

Fortunately, we managed to recover the password for the server and disaster has been averted.

Going forward, a truly random password will be generated for LUKS encryption to avoid someone bruteforcing the password as we have done. To achieve a high bus factor and to ensure “business continuity”, this password will be printed out and placed in a sealed envelope for safe-keeping by trusted persons. To reduce the chances of someone having to reach for the envelope, we can deploy the mechanism I developed for my home server earlier this year that automatically unlocks the LUKS volume.

Advertisements

9 comments on “Bruteforcing LUKS Volumes Explained

  1. Bernard says:

    Oh that sounds very interesting because i’m searching for a programm to bruteforce my LUKS password that i lost. But i think i know a part of the password.

    Can you please help me. I didn’t totally understood the process you were going throw.

  2. Marcus says:

    Many thanks for the post. Regarding the code, I would make use of pythons `repr`-function for `passwd` in line 15 like you did in line 13 and 18.

    • darell tan says:

      Hi Marcus, that’s a good idea. Since this is a quick and dirty solution, and the passwords are only composed of alphanumeric characters, it’s probably fine for this task 🙂

  3. I was wondering why didn’t you try to do it completely offline? You said
    “LUKS provides a means for verifying the master key by having stored the MK digest. This digest is also computed using PBKDF2, but using a different set of parameters. By comparing the computed MK digest against the one stored in the header, the correctness of the MK (and hence the user password) can be verified.”

    Why don’t you take the digest from the header with the correct parameters and then from the guessed key you try to calculate the guessed digest for the master key. If I understand correctly, this will enhance the computations greatly. You wont need to call cryptsetup at all or am I missing something? That given the fact that I can call PBKDF2 from python (I am not sure if it is implemented or not but I think it has to be it is standardised function)

    • darell tan says:

      Yes you are correct. You can do everything in Python. Offline here simply means without any other data or access to the physical machine. However, you need to write code to parse the header, extract the digest and parameters, write code for the algorithm etc. I’m just lazy and this is the fastest approach 🙂 If you are writing a tool that you will be using frequently, then yes, please write a customized program to extract the parameters once, then perform only the computation in parallel.

      • I just want to make sure that I get everything correctly I might write it for the sake of fun and knowledge. Is the PBKDF2 used in cryptsetup the same as the standard PBKDF2 in PKCS#5? or is it a custom made one with many iterations to slow down the brute-forcing technique?

        • darell tan says:

          It’s the standard PBKDF2, which is designed to slow down brute-forcing. The implementation is all in cryptsetup, which is open-source; feel free to take a look at it. I have updated the links in the post.

  4. […] ĂŞtre prĂ©sents dans mon mot de passe, j’utilise un petit script python rĂ©pĂ©ré  sur un blog (que je vous encourage vivement Ă  parcourir !!) et qui m’a permis d’avancer […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s