Recovery key is low-entropy

Bug #1928860 reported by Madars
258
This bug affects 1 person
Affects Status Importance Assigned to Milestone
ubiquity (Ubuntu)
Fix Released
High
Jean-Baptiste Lallement
Impish
Fix Released
High
Jean-Baptiste Lallement

Bug Description

Ubuntu 21.04 Desktop ISO includes Ubiquity installer which offers the user to set up full-disk encryption. In this set-up a recovery key is automatically generated and added to the system.

The recovery key is 16 decimal digits or ~53.2 bits of entropy so within capabilities of offline brute-force attacks for well-resourced attackers.

To confirm, the key is generated here: https://git.launchpad.net/ubuntu/+source/ubiquity/tree/ubiquity/plugins/ubi-partman.py#n306 and used here: https://git.launchpad.net/ubuntu/+source/ubiquity/tree/scripts/plugininstall.py#n915 (see also the attached screenshot).

Tags: impish hirsute
Revision history for this message
Madars (madars) wrote :
Revision history for this message
Seth Arnold (seth-arnold) wrote :

Hello Madars, thanks for the report; can we make this bug public to get more feedback on it? (Is that recovery key in your screenshot something that's important to you?)

Thanks

Changed in ubiquity (Ubuntu):
status: New → Confirmed
Revision history for this message
Madars (madars) wrote :

Thank you! This can absolutely be public; it was a throwaway key in a test VM.

information type: Private Security → Public Security
Revision history for this message
Seth Arnold (seth-arnold) wrote :

Excellent, thanks Madars. I think you're right, something closer to 80 bits would probably make more sense, and if it were output with base64 rather than a decimal string it might not be significantly harder to work with.

Thanks

Revision history for this message
Sebastien Bacher (seb128) wrote :

Thanks, there are also some discussions on https://discourse.ubuntu.com/t/ubuntu-21-04-encryption-recovery-key about the key security which concluded that a brute force attack would take a very long time to success.

Could you give some details on the 'within capabilities of offline brute-force attacks for well-resourced attackers' statement? Did you disagree with the finding from Alex on the post mentioned before?

tags: added: hirsute impish rls-ii-incoming
Changed in ubiquity (Ubuntu):
importance: Undecided → High
Revision history for this message
Seth Arnold (seth-arnold) wrote :

Thanks Sebastian for the reference; I hunted around the Internet to try to find references for current 'best' cracking speed for luks2 without much success. Alex's results are suddenly the best I've seen.

200 years sounds like a long time in isolation but that's also just spinning up 2000 cloud instances for a month: Expensive but not impossible. Furthermore, many of these attacks parallelize across multiple targets *very* cheaply -- I do not know if luks2 bruteforcing is the same -- but it's quite often only slightly more expensive to search for hundreds or millions at the same time.

That's why I thought the 53 bits Madar reports or the 64 bits that I thought I saw via code inspection didn't feel like they were long enough.

Thanks

Revision history for this message
Madars (madars) wrote :

Hi all,

LUKS2 (in zys-format invocation of the corresponding cryptsetup
version) uses Argon2i password-based key deriviation function and
automatically tunes the iteration count/memory cost to be under 2000
milliseconds.

Note that this is timed on the target's machine, and attacker's
machines can be more powerful than that. For example, I created a LUKS
volume on ThinkPad X200 (old hw, but still popular in Coreboot /
Libreboot circles), and a 4 years old Xeon workstation was able to
mount 8 bruteforce-luks passwords/sec against it. (Whereas, for a LUKS
volume generated on the same Xeon machine the passwords/second were
just 2.)

The keyspace of 10^16 recovery keys would mean ~39 610 109 CPU years,
so probably out of reach for current botnets. However, this estimate:

- does not take in account potential improvements in attacker's
  capabilities. E.g. Argon2 GPU implementation exists
  <https://gitlab.com/omos/argon2-gpu/> (but is yet to be incorporated
  into something like hashcat); the author estimates the Nvidia
  Tesla/Xeon speed-up to be around 4-6x.

- leaves little margin of error for compromised entropy. For example,
  if someone saw first 4 digits of my recovery code, the remaining
  keyspace would shrink by 10000x.

So while not threatening in any concrete way, I'd definitely love for
the default to be higher :-) For comparison, BitLocker recovery keys
are 48 decimal digits (not sure how much of it is pure key material
though).

There is, of course, also a balance of security and usability: can
users accurately write down a high-entropy string? Maybe one could get
inspiration from the cryptocurrency world where 12 words from BIP39
wordlist contain 128 bits of entropy (incl 4 bits of checksum), and
can be asked to be entered back (either in full or via random
spot-checks).

tags: added: rls-ii-notfixing
removed: rls-ii-incoming
tags: removed: rls-ii-notfixing
Changed in ubiquity (Ubuntu Impish):
assignee: nobody → Jean-Baptiste Lallement (jibel)
Revision history for this message
Jean-Baptiste Lallement (jibel) wrote :

This is being worked on. In summary the following changes will be done in 21.10:
- The length of the generated numerical key will be increased to 48 digits (like bitlocker)
- It will be optional
- It will be editable and accept letters, digits and special characters.

Changed in ubiquity (Ubuntu Impish):
status: Confirmed → Triaged
Revision history for this message
Alex Murray (alexmurray) wrote :

Thanks jibel!

Changed in ubiquity (Ubuntu Impish):
milestone: none → ubuntu-21.10
milestone: ubuntu-21.10 → ubuntu-21.10-beta
Revision history for this message
Jean-Baptiste Lallement (jibel) wrote :

ubiquity (21.10.4) impish; urgency=medium

  [ Didier Roche ]
  [ Jean-Baptiste Lallement ]
  * Make the recovery key a 48 digits password by default
   (LP: 1928860)
  * Recovery key is editable and optional.
  * Show the recovery key during manual partitioning.
  * Display a warning if recovery key is stored on a non removable media.

Changed in ubiquity (Ubuntu Impish):
status: Triaged → Fix Released
To post a comment you must log in.
This report contains Public Security information  
Everyone can see this security related information.

Other bug subscribers