GRUB LUKS support is slow?

GRUB LUKS support is slow?

[Ludovic Courtès]

Hello Guix,

I have an encrypted root.  When GRUB asks me for my passphrase, it takes
5–10 seconds after I hit enter before it displays the menu; then, once
I’ve selected an entry, it takes another 5 seconds or so to boot.

It’s always been this way for me (that’s on UEFI), but I’m sufficiently
annoyed to write this message today.  :-)

Are others experiencing this as well?  Any hints?

Ludo’.

Re: GRUB LUKS support is slow?

[Mark H Weaver]

ludo@gnu.org (Ludovic Courtès) writes:

> I have an encrypted root.  When GRUB asks me for my passphrase, it takes
> 5–10 seconds after I hit enter before it displays the menu; then, once
> I’ve selected an entry, it takes another 5 seconds or so to boot.
>
> It’s always been this way for me (that’s on UEFI), but I’m sufficiently
> annoyed to write this message today.  :-)
>
> Are others experiencing this as well?  Any hints?

I also use a LUKS-encrypted root partition, and the same thing happens
to me.  I would guess that the cryptographic operations in GRUB are not
well optimized, but I haven't looked closely.

      Mark

Re: GRUB LUKS support is slow?

[Adam Van Ymeren]

On December 15, 2017 5:53:15 PM EST, Mark H Weaver <mhw@netris.org> wrote:
>ludo@gnu.org (Ludovic Courtès) writes:
>
>> I have an encrypted root.  When GRUB asks me for my passphrase, it
>takes
>> 5–10 seconds after I hit enter before it displays the menu; then,
>once
>> I’ve selected an entry, it takes another 5 seconds or so to boot.
>>
>> It’s always been this way for me (that’s on UEFI), but I’m
>sufficiently
>> annoyed to write this message today.  :-)
>>
>> Are others experiencing this as well?  Any hints?
>
>I also use a LUKS-encrypted root partition, and the same thing happens
>to me.  I would guess that the cryptographic operations in GRUB are not
>well optimized, but I haven't looked closely.
>
>      Mark

Even unoptimized 5-10s seems pretty long.  It's not like it has a lot of data to process.

I have an encrypted root as well, I don't think it takes 5s after I enter the passphrase to get the grub men, maybe 1 or 2.  Next time I reboot I'll make a note of it.

Re: GRUB LUKS support is slow?

[Tobias Geerinckx-Rice]

Guix,

I'm afraid you'll all be somewhat disappointed by the answer...

Adam Van Ymeren wrote on 16/12/17 at 00:25:
> On December 15, 2017 5:53:15 PM EST, Mark H Weaver <mhw@netris.org> 
> wrote:
>> ludo@gnu.org (Ludovic Courtès) writes:
>> 
>>> I have an encrypted root.  When GRUB asks me for my passphrase, 
>>> it takes 5–10 seconds after I hit enter before it displays the
>>> menu; then, once I've selected an entry, it takes another 5 seconds
>>> or so to boot.
>>> 
>>> It’s always been this way for me (that’s on UEFI), but I’m
>>> sufficiently annoyed to write this message today.  :-)
>>> 
>>> Are others experiencing this as well?  Any hints?
>> 
>> I also use a LUKS-encrypted root partition, and the same thing 
>> happens to me.  I would guess that the cryptographic operations in 
>> GRUB are not well optimized, but I haven't looked closely.
>> 
>> Mark
> 
> Even unoptimized 5-10s seems pretty long.  It's not like it has a
> lot of data to process.

Alas, you'd be wrong :-)

The whole point of the key derivation function (PBKDF2 in this case) is
to take a long time — i.e., generate *a lot* of data — before deriving
the actual encryption key from your passphrase. It's basically a slow
hash, run many times over. That's the delay we're talking about here.

PBKDF2 is designed to be ‘impossible’ to optimise, parallelise, or cut
short[0], so there's no way around running several seconds of busy work
before you can even check a passphrase.

On GuixSD, the default run time is:

  $ cryptsetup --help | grep iteration
  -i, --iter-time=msecs        PBKDF2 iteration time for LUKS (in ms)
  Default PBKDF2 iteration time for LUKS: 2000 (ms)

However, this run time is measured at volume creation time, with all
fancy CPU features available. It wouldn't surprise me if real-mode[1]
GRUB and the early kernel code are badly optimised and take longer to
complete the same number of iterations to obtain the key.

Furthermore, as Ludo' discovered, it's very likely that both GRUB *and*
Linux will have to re-calculate the key, doubling the total time.

> I have an encrypted root as well, I don't think it takes 5s after I 
> enter the passphrase to get the grub men, maybe 1 or 2.  Next time I 
> reboot I'll make a note of it.

It takes about ~7s on my systems (rough guess; they're all servers
so I'm not that impatient). It should *never* take less than 2 seconds
unless you or your distro changed ‘--iter-time’, or your volumes were
encrypted on a different, slower machine, or something's just wrong.

                                * * *

TLDR: unfortunately, these delays sound quite normal. Aside from writing
optimised PBKDF2 implementations that can run in whatever CPU modes GRUB
does[1], the only way to significantly reduce the wait is to use a lower
‘--iter-time’ when creating volumes.

It's probably not worth it. Your box will boot a few seconds faster;
your attacker just saw their brute-force speeds double — or worse.

Kind regards,

T G-R

[0]: This is from memory, but should be correct for all practical
     purposes.
[1]: I presume real-mode; don't ask me how UEFI affects all this.

Re: GRUB LUKS support is slow?

[Adam Van Ymeren]

On December 15, 2017 8:10:24 PM EST, Tobias Geerinckx-Rice <me@tobias.gr> wrote:
>Guix,
>
>I'm afraid you'll all be somewhat disappointed by the answer...
>
>Adam Van Ymeren wrote on 16/12/17 at 00:25:
>> On December 15, 2017 5:53:15 PM EST, Mark H Weaver <mhw@netris.org> 
>> wrote:
>>> ludo@gnu.org (Ludovic Courtès) writes:
>>> 
>>>> I have an encrypted root.  When GRUB asks me for my passphrase, 
>>>> it takes 5–10 seconds after I hit enter before it displays the
>>>> menu; then, once I've selected an entry, it takes another 5 seconds
>>>> or so to boot.
>>>> 
>>>> It’s always been this way for me (that’s on UEFI), but I’m
>>>> sufficiently annoyed to write this message today.  :-)
>>>> 
>>>> Are others experiencing this as well?  Any hints?
>>> 
>>> I also use a LUKS-encrypted root partition, and the same thing 
>>> happens to me.  I would guess that the cryptographic operations in 
>>> GRUB are not well optimized, but I haven't looked closely.
>>> 
>>> Mark
>> 
>> Even unoptimized 5-10s seems pretty long.  It's not like it has a
>> lot of data to process.
>
>Alas, you'd be wrong :-)
>
>The whole point of the key derivation function (PBKDF2 in this case) is
>to take a long time — i.e., generate *a lot* of data — before deriving
>the actual encryption key from your passphrase. It's basically a slow
>hash, run many times over. That's the delay we're talking about here.
>
>PBKDF2 is designed to be ‘impossible’ to optimise, parallelise, or cut
>short[0], so there's no way around running several seconds of busy work
>before you can even check a passphrase.
>
>On GuixSD, the default run time is:
>
>  $ cryptsetup --help | grep iteration
>  -i, --iter-time=msecs        PBKDF2 iteration time for LUKS (in ms)
>  Default PBKDF2 iteration time for LUKS: 2000 (ms)
>
>However, this run time is measured at volume creation time, with all
>fancy CPU features available. It wouldn't surprise me if real-mode[1]
>GRUB and the early kernel code are badly optimised and take longer to
>complete the same number of iterations to obtain the key.
>
>Furthermore, as Ludo' discovered, it's very likely that both GRUB *and*
>Linux will have to re-calculate the key, doubling the total time.
>
>> I have an encrypted root as well, I don't think it takes 5s after I 
>> enter the passphrase to get the grub men, maybe 1 or 2.  Next time I 
>> reboot I'll make a note of it.
>
>It takes about ~7s on my systems (rough guess; they're all servers
>so I'm not that impatient). It should *never* take less than 2 seconds
>unless you or your distro changed ‘--iter-time’, or your volumes were
>encrypted on a different, slower machine, or something's just wrong.
>
>                                * * *
>
>TLDR: unfortunately, these delays sound quite normal. Aside from
>writing
>optimised PBKDF2 implementations that can run in whatever CPU modes
>GRUB
>does[1], the only way to significantly reduce the wait is to use a
>lower
>‘--iter-time’ when creating volumes.
>
>It's probably not worth it. Your box will boot a few seconds faster;
>your attacker just saw their brute-force speeds double — or worse.
>
>Kind regards,
>
>T G-R
>
>[0]: This is from memory, but should be correct for all practical
>     purposes.
>[1]: I presume real-mode; don't ask me how UEFI affects all this.

Ah I definitely didn't think it through, using a key derivation function on the passphrase makes sense and definitely explains the slowness.  Thanks for the explanation!

Re: GRUB LUKS support is slow?

[Ludovic Courtès]

Hi Tobias,

Tobias Geerinckx-Rice <me@tobias.gr> skribis:

> The whole point of the key derivation function (PBKDF2 in this case) is
> to take a long time — i.e., generate *a lot* of data — before deriving
> the actual encryption key from your passphrase. It's basically a slow
> hash, run many times over. That's the delay we're talking about here.
>
> PBKDF2 is designed to be ‘impossible’ to optimise, parallelise, or cut
> short[0], so there's no way around running several seconds of busy work
> before you can even check a passphrase.
>
> On GuixSD, the default run time is:
>
>   $ cryptsetup --help | grep iteration
>   -i, --iter-time=msecs        PBKDF2 iteration time for LUKS (in ms)
>   Default PBKDF2 iteration time for LUKS: 2000 (ms)
>
> However, this run time is measured at volume creation time, with all
> fancy CPU features available. It wouldn't surprise me if real-mode[1]
> GRUB and the early kernel code are badly optimised and take longer to
> complete the same number of iterations to obtain the key.

I see, thanks for the explanation!

Apparently GRUB embeds a copy of libgcrypt, which is supposed to be
somewhat optimized.  Maybe there’s really nothing we can do.

Ludo’.

Re: GRUB LUKS support is slow?

[Ludovic Courtès]

Hi,

Tobias Geerinckx-Rice <me@tobias.gr> skribis:

> Adam Van Ymeren wrote on 16/12/17 at 00:25:
>> On December 15, 2017 5:53:15 PM EST, Mark H Weaver <mhw@netris.org> 
>> wrote:
>>> ludo@gnu.org (Ludovic Courtès) writes:
>>> 
>>>> I have an encrypted root.  When GRUB asks me for my passphrase, 
>>>> it takes 5–10 seconds after I hit enter before it displays the
>>>> menu; then, once I've selected an entry, it takes another 5 seconds
>>>> or so to boot.
>>>> 
>>>> It’s always been this way for me (that’s on UEFI), but I’m
>>>> sufficiently annoyed to write this message today.  :-)
>>>> 
>>>> Are others experiencing this as well?  Any hints?
>>> 
>>> I also use a LUKS-encrypted root partition, and the same thing 
>>> happens to me.  I would guess that the cryptographic operations in 
>>> GRUB are not well optimized, but I haven't looked closely.
>>> 
>>> Mark
>> 
>> Even unoptimized 5-10s seems pretty long.  It's not like it has a
>> lot of data to process.
>
> Alas, you'd be wrong :-)

What’s also “reassuring” is that the searching for “grub luks slow”
suggests that the whole world is booting slowly, not just GuixSD users.
:-)

Ludo’.

Re: GRUB LUKS support is slow?

[Tobias Geerinckx-Rice]

> Tobias Geerinckx-Rice <me@tobias.gr> skribis:
>> [..] It wouldn't surprise me if real-mode[?] GRUB and the early
>> kernel code are badly optimised [...]>

An unfortunate choice of words.

What I meant to say was: ‘as optimised as can be realistically expected,
but hardly more.’ I did not wish to malign the GRUB or gcrypt authors.

Kind regards,

T G-R

Re: GRUB LUKS support is slow?

[Clément Lassieur]

Ludovic Courtès <ludo@gnu.org> writes:

> Hello Guix,
>
> I have an encrypted root.  When GRUB asks me for my passphrase, it takes
> 5–10 seconds after I hit enter before it displays the menu; then, once
> I’ve selected an entry, it takes another 5 seconds or so to boot.
>
> It’s always been this way for me (that’s on UEFI), but I’m sufficiently
> annoyed to write this message today.  :-)
>
> Are others experiencing this as well?  Any hints?

I experience the same, and it's very annoying.  I thought it was because
of Libreboot, I'm glad to know it's not (assuming you don't use
Libreboot).

Re: GRUB LUKS support is slow?

[Chris Marusich]

[-- Attachment #1: Type: text/plain, Size: 1871 bytes --]

Clément Lassieur <clement@lassieur.org> writes:

> Ludovic Courtès <ludo@gnu.org> writes:
>
>> Hello Guix,
>>
>> I have an encrypted root.  When GRUB asks me for my passphrase, it takes
>> 5–10 seconds after I hit enter before it displays the menu; then, once
>> I’ve selected an entry, it takes another 5 seconds or so to boot.
>>
>> It’s always been this way for me (that’s on UEFI), but I’m sufficiently
>> annoyed to write this message today.  :-)
>>
>> Are others experiencing this as well?  Any hints?
>
> I experience the same, and it's very annoying.  I thought it was because
> of Libreboot, I'm glad to know it's not (assuming you don't use
> Libreboot).

There may also be a Libreboot-specific problem legitimately slows down
the boot process:

https://notabug.org/libreboot/libreboot/issues/197

When I boot on a machine that does not use Libreboot, I see a few
seconds' delay while the GRUB payload opens the LUKS volume.  As
explained by Tobias, this is probably expected behavior.

However, on a machine with Libreboot, I find that about 1 or 2 MINUTES
of time is required before any progress is made, during which the HDD
light is constantly illuminated, as if the drive is being heavily
accessed.  I suspect it might be related to the bug linked above.  In
addition, after that time passes, Libreboot spits out a bunch of errors
about how it couldn't find various devices.  Nevertheless, pressing a
button like the "up arrow" on my keyboard takes me to the next phase of
the bootstrap process, which is the Guix-installed GRUB menu.  From
there on out, it's smooth sailing.

Anyway, I have no reason to suspect that's a GuixSD issue.  I just
wanted to mention that there may be other Libreboot-specific delays when
using the GRUB payload to boot.  At least it boots reliably, if slowly.

-- 
Chris

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]