![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
mjg59Here's an article from a French anarchist describing how his (encrypted) laptop was seized after he was arrested, and material from the encrypted partition has since been entered as evidence against him. His encryption password was supposedly greater than 20 characters and included a mixture of cases, numbers, and punctuation, so in the absence of any sort of opsec failures this implies that even relatively complex passwords can now be brute forced, and we should be transitioning to even more secure passphrases.
Or does it? Let's go into what LUKS is doing in the first place. The actual data is typically encrypted with AES, an extremely popular and well-tested encryption algorithm. AES has no known major weaknesses and is not considered to be practically brute-forceable - at least, assuming you have a random key. Unfortunately it's not really practical to ask a user to type in 128 bits of binary every time they want to unlock their drive, so another approach has to be taken.
This is handled using something called a "key derivation function", or KDF. A KDF is a function that takes some input (in this case the user's password) and generates a key. As an extremely simple example, think of MD5 - it takes an input and generates a 128-bit output, so we could simply MD5 the user's password and use the output as an AES key. While this could technically be considered a KDF, it would be an extremely bad one! MD5s can be calculated extremely quickly, so someone attempting to brute-force a disk encryption key could simply generate the MD5 of every plausible password (probably on a lot of machines in parallel, likely using GPUs) and test each of them to see whether it decrypts the drive.
(things are actually slightly more complicated than this - your password is used to generate a key that is then used to encrypt and decrypt the actual encryption key. This is necessary in order to allow you to change your password without having to re-encrypt the entire drive - instead you simply re-encrypt the encryption key with the new password-derived key. This also allows you to have multiple passwords or unlock mechanisms per drive)
Good KDFs reduce this risk by being what's technically referred to as "expensive". Rather than performing one simple calculation to turn a password into a key, they perform a lot of calculations. The number of calculations performed is generally configurable, in order to let you trade off between the amount of security (the number of calculations you'll force an attacker to perform when attempting to generate a key from a potential password) and performance (the amount of time you're willing to wait for your laptop to generate the key after you type in your password so it can actually boot). But, obviously, this tradeoff changes over time - defaults that made sense 10 years ago are not necessarily good defaults now. If you set up your encrypted partition some time ago, the number of calculations required may no longer be considered up to scratch.
And, well, some of these assumptions are kind of bad in the first place! Just making things computationally expensive doesn't help a lot if your adversary has the ability to test a large number of passwords in parallel. GPUs are extremely good at performing the sort of calculations that KDFs generally use, so an attacker can "just" get a whole pile of GPUs and throw them at the problem. KDFs that are computationally expensive don't do a great deal to protect against this. However, there's another axis of expense that can be considered - memory. If the KDF algorithm requires a significant amount of RAM, the degree to which it can be performed in parallel on a GPU is massively reduced. A Geforce 4090 may have 16,384 execution units, but if each password attempt requires 1GB of RAM and the card only has 24GB on board, the attacker is restricted to running 24 attempts in parallel.
So, in these days of attackers with access to a pile of GPUs, a purely computationally expensive KDF is just not a good choice. And, unfortunately, the subject of this story was almost certainly using one of those. Ubuntu 18.04 used the LUKS1 header format, and the only KDF supported in this format is PBKDF2. This is not a memory expensive KDF, and so is vulnerable to GPU-based attacks. But even so, systems using the LUKS2 header format used to default to argon2i,again not a memory expensive KDFwhich is memory strong, but not designed to be resistant to GPU attack (thanks to the comments pointing out my misunderstanding here). New versions default to argon2id, which is. You want to be using argon2id.
What makes this worse is that distributions generally don't update this in any way. If you installed your system and it gave you pbkdf2 as your KDF, you're probably still using pbkdf2 even if you've upgraded to a system that would use argon2id on a fresh install. Thankfully, this can all be fixed-up in place. But note that if anything goes wrong here you could lose access to all your encrypted data, so before doing anything make sure it's all backed up (and figure out how to keep said backup secure so you don't just have your data seized that way).
First, make sure you're running as up-to-date a version of your distribution as possible. Having tools that support the LUKS2 format doesn't mean that your distribution has all of that integrated, and old distribution versions may allow you to update your LUKS setup without actually supporting booting from it. Also, if you're using an encrypted /boot, stop now - very recent versions of grub2 support LUKS2, but they don't support argon2id, and this will render your system unbootable.
Next, figure out which device under /dev corresponds to your encrypted partition. Run
lsblk
and look for entries that have a type of "crypt". The device above that in the tree is the actual encrypted device. Record that name, and run
sudo cryptsetup luksHeaderBackup /dev/whatever --header-backup-file /tmp/luksheader
and copy that to a USB stick or something. If something goes wrong here you'll be able to boot a live image and run
sudo cryptsetup luksHeaderRestore /dev/whatever --header-backup-file luksheader
to restore it.
(Edit to add: Once everything is working, delete this backup! It contains the old weak key, and someone with it can potentially use that to brute force your disk encryption key using the old KDF even if you've updated the on-disk KDF.)
Next, run
sudo cryptsetup luksDump /dev/whatever
and look for the Version: line. If it's version 1, you need to update the header to LUKS2. Run
sudo cryptsetup convert /dev/whatever --type luks2
and follow the prompts. Make sure your system still boots, and if not go back and restore the backup of your header. Assuming everything is ok at this point, run
sudo cryptsetup luksDump /dev/whatever
again and look for the PBKDF: line in each keyslot (pay attention only to the keyslots, ignore any references to pbkdf2 that come after the Digests: line). If the PBKDF is either "pbkdf2" or "argon2i" you should convert to argon2id. Run the following:
sudo cryptsetup luksConvertKey /dev/whatever --pbkdf argon2id
and follow the prompts. If you have multiple passwords associated with your drive you'll have multiple keyslots, and you'll need to repeat this for each password.
Distributions! You should really be handling this sort of thing on upgrade. People who installed their systems with your encryption defaults several years ago are now much less secure than people who perform a fresh install today. Please please please do something about this.
Or does it? Let's go into what LUKS is doing in the first place. The actual data is typically encrypted with AES, an extremely popular and well-tested encryption algorithm. AES has no known major weaknesses and is not considered to be practically brute-forceable - at least, assuming you have a random key. Unfortunately it's not really practical to ask a user to type in 128 bits of binary every time they want to unlock their drive, so another approach has to be taken.
This is handled using something called a "key derivation function", or KDF. A KDF is a function that takes some input (in this case the user's password) and generates a key. As an extremely simple example, think of MD5 - it takes an input and generates a 128-bit output, so we could simply MD5 the user's password and use the output as an AES key. While this could technically be considered a KDF, it would be an extremely bad one! MD5s can be calculated extremely quickly, so someone attempting to brute-force a disk encryption key could simply generate the MD5 of every plausible password (probably on a lot of machines in parallel, likely using GPUs) and test each of them to see whether it decrypts the drive.
(things are actually slightly more complicated than this - your password is used to generate a key that is then used to encrypt and decrypt the actual encryption key. This is necessary in order to allow you to change your password without having to re-encrypt the entire drive - instead you simply re-encrypt the encryption key with the new password-derived key. This also allows you to have multiple passwords or unlock mechanisms per drive)
Good KDFs reduce this risk by being what's technically referred to as "expensive". Rather than performing one simple calculation to turn a password into a key, they perform a lot of calculations. The number of calculations performed is generally configurable, in order to let you trade off between the amount of security (the number of calculations you'll force an attacker to perform when attempting to generate a key from a potential password) and performance (the amount of time you're willing to wait for your laptop to generate the key after you type in your password so it can actually boot). But, obviously, this tradeoff changes over time - defaults that made sense 10 years ago are not necessarily good defaults now. If you set up your encrypted partition some time ago, the number of calculations required may no longer be considered up to scratch.
And, well, some of these assumptions are kind of bad in the first place! Just making things computationally expensive doesn't help a lot if your adversary has the ability to test a large number of passwords in parallel. GPUs are extremely good at performing the sort of calculations that KDFs generally use, so an attacker can "just" get a whole pile of GPUs and throw them at the problem. KDFs that are computationally expensive don't do a great deal to protect against this. However, there's another axis of expense that can be considered - memory. If the KDF algorithm requires a significant amount of RAM, the degree to which it can be performed in parallel on a GPU is massively reduced. A Geforce 4090 may have 16,384 execution units, but if each password attempt requires 1GB of RAM and the card only has 24GB on board, the attacker is restricted to running 24 attempts in parallel.
So, in these days of attackers with access to a pile of GPUs, a purely computationally expensive KDF is just not a good choice. And, unfortunately, the subject of this story was almost certainly using one of those. Ubuntu 18.04 used the LUKS1 header format, and the only KDF supported in this format is PBKDF2. This is not a memory expensive KDF, and so is vulnerable to GPU-based attacks. But even so, systems using the LUKS2 header format used to default to argon2i,
What makes this worse is that distributions generally don't update this in any way. If you installed your system and it gave you pbkdf2 as your KDF, you're probably still using pbkdf2 even if you've upgraded to a system that would use argon2id on a fresh install. Thankfully, this can all be fixed-up in place. But note that if anything goes wrong here you could lose access to all your encrypted data, so before doing anything make sure it's all backed up (and figure out how to keep said backup secure so you don't just have your data seized that way).
First, make sure you're running as up-to-date a version of your distribution as possible. Having tools that support the LUKS2 format doesn't mean that your distribution has all of that integrated, and old distribution versions may allow you to update your LUKS setup without actually supporting booting from it. Also, if you're using an encrypted /boot, stop now - very recent versions of grub2 support LUKS2, but they don't support argon2id, and this will render your system unbootable.
Next, figure out which device under /dev corresponds to your encrypted partition. Run
lsblk
and look for entries that have a type of "crypt". The device above that in the tree is the actual encrypted device. Record that name, and run
sudo cryptsetup luksHeaderBackup /dev/whatever --header-backup-file /tmp/luksheader
and copy that to a USB stick or something. If something goes wrong here you'll be able to boot a live image and run
sudo cryptsetup luksHeaderRestore /dev/whatever --header-backup-file luksheader
to restore it.
(Edit to add: Once everything is working, delete this backup! It contains the old weak key, and someone with it can potentially use that to brute force your disk encryption key using the old KDF even if you've updated the on-disk KDF.)
Next, run
sudo cryptsetup luksDump /dev/whatever
and look for the Version: line. If it's version 1, you need to update the header to LUKS2. Run
sudo cryptsetup convert /dev/whatever --type luks2
and follow the prompts. Make sure your system still boots, and if not go back and restore the backup of your header. Assuming everything is ok at this point, run
sudo cryptsetup luksDump /dev/whatever
again and look for the PBKDF: line in each keyslot (pay attention only to the keyslots, ignore any references to pbkdf2 that come after the Digests: line). If the PBKDF is either "pbkdf2" or "argon2i" you should convert to argon2id. Run the following:
sudo cryptsetup luksConvertKey /dev/whatever --pbkdf argon2id
and follow the prompts. If you have multiple passwords associated with your drive you'll have multiple keyslots, and you'll need to repeat this for each password.
Distributions! You should really be handling this sort of thing on upgrade. People who installed their systems with your encryption defaults several years ago are now much less secure than people who perform a fresh install today. Please please please do something about this.
no subject
Date: 2023-04-18 04:38 am (UTC)So that's at least 64^20 = 2^120 variants. I call bullshit on brute-forcing. There was some kind of opsec failure.
no subject
Date: 2023-04-18 04:39 am (UTC)no subject
Date: 2023-04-18 06:57 am (UTC)Of course, people use imprecise language all the time, so it could be one that he made up himself, or a pwgen's default algorithm password, but not for example an xkcd correct horse battery staple password
no subject
Date: 2023-04-18 10:23 am (UTC)Absolutely not. A password, that contains upper- and lowercase letters, numbers, and punctuation symbols, just contains these CLASSES of characters, meaning "at least one of each class".
no subject
Date: 2023-04-18 05:19 pm (UTC)"securepassword" => needs caps
"SecurePassword" => needs two numbers and two symbols
"SecurePassword11!!"
no subject
Date: 2023-04-19 12:20 am (UTC)For perspective, the total Bitcoin hashing rate right now is around 2^60 hashes per second. Thus brute-forcing the 100000 iterations of PBKDF2 for a password with 60 bits of entropy would require capacity comparable to a day of total Bitcoin miners' output.
Which apparently requires about 500 gigawatt-hours of energy.
This is on the edge of the "what if this hard drive contains the secret to hyperspace star drive" scenario, but hardly something to do for a regular police investigation.
the problem is the password
Date: 2023-05-06 12:04 pm (UTC)Sure, using a memory intensive KDF like Argon2id is to be advised. But acting like they could encrypt it because PBKDF2 was used is at the very least misleading. We can say, with very high certainty, that the encryption could not have been broken if:
1. a secure password was beeing used (truly random, long enough)
2. the police didn't found out the password another way (e.g. watching him type it in, it was beeing used somewhere else, it was written down, ...)
However, we cannot say that the encryption wouldn't have been broken if argon2id was beeing used, because that would depend on how insecure the password is. But then, the root cause here would still be, that the password is insecure, not that PBKDF2 is beeing used.
If the password would have been 20 random characters (letters and numbers and 8 special characters = 70 options per character) it would take 390 trillion years to brute force all possible options. And that would be for MD5 Hashed passwords using 10000 x A100 GPUs. So realistically, PBKDF2 would take way longer (don't have hashing rates for PBKDF2 to calculate). Even 14 random letters would currently take 3323 years to brute force.