Full encryption with LUKS (SHA512, aes-xts-plain64) – grub2 really slow ….

My German readers know that I work on an article series regarding a reasonable full encryption of customer related Linux laptops and virtual machines with dm-crypt/LUKS. Whilst experimenting with different configurations I found that all my naive assumptions regarding the boot time of fully encrypted systems on standard laptops were wrong.

The boot manager for Linux - Grub2 - can lead to unacceptable long boot times (> n * 10 secs) - despite much smaller and reasonable values for the time required by the kernel to open encrypted devices. Delay factors during boot of more than 7 to 8 are possible and have to be taken into account during the encryption setup.

In my case Grub2 appears to be dead slow regarding a distinct factor which determines the time required during a first boot phase until the graphical Grub menu with choices for bootable installations gets displayed. The time for later boot phases (loaded kernel with initrd-support, access to encrypted volumes by the kernel) is much, much shorter.

A quick test showed that Grub2 is inefficient with respect to the SHA512 and not to the core and aes-based symmetric decryption algorithm.

The problem

A fully encrypted Linux system would in many cases include

  1. a separate encrypted partition with a filesystem for the "/boot" contents (comprising grub, kernel, initrd).
  2. or a "/boot"-directory as part of an encrypted partition or logical LVM volume for the "/"-filesystem.

Grub2 must in both cases decrypt the contents of "/boot" during an early boot phase to be able to analyze its contents, to load the kernel and establish a filesystem with basic drivers in the RAM. In my case the "/boot"-directory was located inside the encrypted volume for the "/"-filesystem (=variant 2 above).

I had prepared an encrypted "LUKS on LVM" configuration on an external SSD (attached via USB). This was done on a Linux desktop system. I had created an encrypted "Logical Volume" [LV] with ext4, which I wanted to use for the later "/"-filesystem of a new Linux installation for my laptop. Key data for the encryption were given by the following options:

cryptsetup --cipher aes-xts-plain64 --key-size 512 --hash sha512 --iter-time 2000 --align-payload=2048 -v luksFormat /dev/mapper/vga-lva1

Indeed, it took about 2 secs to open the encrypted LV on the desktop system. I knew that my laptop would be slower by a factor around 3. I had gotten related comparison values via the help of "cryptsetup benchmark" on both systems.

However, after an installation of Opensuse Leap 15 and testing on my laptop I got an astounding a boot time of around 45 secs between two distinct points during the boot phase - between the point in time when I had entered my passphrase at the initial GRUB prompt until the point when I was presented with the graphical Grub2 interface and the choice of bootable installations.

The display of the graphical Grub2-interface requires an analysis of the "/boot"-directory-contents - which has to be be deciphered before. So, GRUB had certainly opened the encrypted volume with the "/"-filesystem at this point. Naturally, I was tempted to damn Grub for an inefficient decryption library. But this was wrong in a way ...

Factors which determine the time for opening an encrypted volume

En-/Decryption with LUKS depends on symmetric algorithms - e.g. aes-based "aes-xts-plain64". So, sure, you should have an efficient library that uses HW-support to do the en/decryption.

However, the time required to open a LUKS-encrypted device also depends on the time to calculate the key required to decipher the encrypted Master-Key stored in a LUKS key slot. This calculation is based on hash-algorithms as e.g. SHA512, uses salts and - most importantly - many, many iterations. All this is performed by the PBKDF2-method which in itself also uses HMAC. See e.g.
dm-crypt/Luks – Begriffe, Funktionsweise und die Rolle des Hash-Verfahrens – I
dm-crypt/Luks – Begriffe, Funktionsweise und die Rolle des Hash-Verfahrens – II
(sorry - only available in German; see however further links in these articles).
The number of iterations can be determined directly or indirectly by parameters when you create a LUKS encrypted device. In my case I had done this indirectly by giving a standard "--iter-time=2000". This defines a time in msec required to perform the PBKDF2-iterations. This time is compared to internal LUKS benchmark results for the PBKDF2 performance.

As we have multiple parameters (key-size, aes-method, iterations, hash-algorithm) which could potentially have an impact on required time intervals I decided to make a second test - for which I changed the PBKDF2 iteration number for a given key slot explicitly.

Exchanging the iteration parameter for a key slot

On my desktop system I first checked the iteration number for my external device with its LVM volume group "vga" and the encrypted LV "lva1" by cryptsetup luksDump:

mytux:~ # cryptsetup luksDump /dev/vga/lva1       
LUKS header information for /dev/vga/lva1

Version:        1
Cipher name:    aes
Cipher mode:    xts-plain64
Hash spec:      sha512
Payload offset: 4096
MK bits:        512
...
MK iterations:  108863
....
Key Slot 0: ENABLED
        Iterations:             2612730
...
        Key material offset:    8
        AF stripes:             4000
Key Slot 1: DISABLED
...

So, I had a fantastic number of 2.6 million PBKDF2-iterations on Key Slot 0. (Thanks to a capable CPU on my desktop). Note that the less security relevant iteration number for the determination of the unique MK-digest is much smaller (see the "MK iterations" above). (The MK digest is used to identify which key-slot produces the right MK for a given passphrase).

Then I tested the time to open the (external) volume on another Linux installation, which I had booted from an internal disk on the laptop. As expected the required time was around 6 secs. This was consistent which benchmark results (cryptsetup benchmark) of 450.000 on the laptop compared to 1.3 million iterations per second on the desktop.

To test the impact of the iteration number on Grub I first added another key slot

mytux:~ # cryptsetup luksAddKey /dev/vga/lva1 -S 1 --pbkdf-force-iterations 200000
Enter any existing passphrase: 
Enter new passphrase for key slot:  

Then I deleted "Key Slot 0" and added it again with a new explicitly set iteration number (--pbkdf-force-iterations):

mytux:~ # cryptsetup luksKillSlot  /dev/vga/lva1 0
Enter any remaining passphrase: 
mytux:~ # cryptsetup luksAddKey /dev/vga/lva1 -S 0 --pbkdf-force-iterations 200000 
Enter any existing passphrase: 
Enter new passphrase for key slot: 

Eventually, I killed the intermediate "Key Slot 1" again. So, all in all I had reduced the iteration number by more than a factor 10: from 2.6 mio to 200.000.

An guess - what time Grub now required until the graphical interface appeared? Only, around 4 seconds.
Again, we see a factor between 7 and 8 between Grub and the kernel: The time the kernel requires for opening the volume was found to be just around 0.8 secs.

Conclusion 1 - do not base your full encryption setup on data of "cryptsetup benchmark", only

It is obvious that the kernel time for opening a LUKS-encrypted device is no measure at all for the time GRUB needs. Thus: If you do not want to wait longer than 10 secs (or whatever your acceptable delay time is) for an initial boot up sequence then you need to make compromises and reduce the number of PBKDF2-iterations for your key slots drastically. In my case I had to go down from 2.6 mio to 300.000 iterations in the end.

Conclusion 2 - delays of GRUB are due to deficits in iterating Hash-algorithms and not so much due to aes-algorithms

Problems with slow boot times and encryption are reported in many Internet articles and forum posts. Very often the discussion is focused on the efficiency of aes-decryption libraries and related HW support by the CPU-sub-features. The results presented above make it clear, in my opinion, that Grub2 is slow with respect to Hash-algorithms (within PBKDF2) - at least for SHA512. It is the calculation of the Master Key which leads to huge delay times. The aes-decryption itself is not a major source of the boot delay time caused by GRUB on fully encrypted systems - at least not in my case.

Conclusion 3 - added 14.12.2018

I would also like to point out that a high number of iterations for the LUKS Master-Key-Digest can make the problems worse as soon as you use multiple active key slots. Reason: A test digest has to be calculated for each slot. If the number of iterations for the MK-Digest were a 1/4th of the PBKDF-iteration number then the required time is doubled for 4 active key slots. Well, without user interventions the present LUKS versions apply a factor of 1/16. The effect on boot time would still be noticeable (25%), however.

Conclusion - added 14.12.2018

In the meantime I have tested things on a different laptop - with basically the same results. All in all I think it is a pity that one is forced by a standard Linux boot-manager to make compromises regarding LUKS security. One should also take into account that an attacker which got the encrypted disk under his physical control would try to break LUKS passwords on much faster machines than yours. So several 10 millions PBKDF2-iterations per second are certainly possible - meaning multiple password trials per second.

One could argue that security has its price - here a very long boot time, probably to be paid also after hibernation processes. (And, of course, also typing long, complicated passphrases.) However, the first point reduces the efficiency of mobile laptop users (e.g. consultants) at customer sites; your MS Windows colleagues will just smile at boot times over 10 Seks .... It won't help to tell them that booting to a graphical KDE interface without LUKS would only take a few seconds (6 in my case).

Therefore, I would appeal to the GRUB2 developers: Please try to accelerate the performance of SHA512 iterations within the PBKDF2/HMAC-algorithm at boot time.

My own consequence so far and a kind of circumvention has been to use virtualization on my laptop with separate LVM Volumes for fully encrypted virtual KVM machines to perform the real work. The latter volumes are mounted manually with help of the kernel of the encrypted laptop's host-system (which uses a relatively low PBKDF2-iteration number of around 300.000). The encrypted volumes for the guests use higher iteration numbers (1.000.000) for their key-slot(s) - but getting access only requires the fast host kernel and no Grub. In such a scenario the host kernel - and not a guest's kernel - performs all encryption for a guest system.