LUKS, how to make strongest possible and reasonable passphrase?

Question

Let us say I have a volume encrypted under LUKS with a 512-bit key. That would mean there are 2 ^ 512 possible values which the key may be.

Now I need a passphrase which is at least as resistant to brute force as the actual 512-bit volume encryption key. Correct me if my assumptions below are wrong, all numeric values are used for mathematical example only:

Let's say my passphrase is generated by base64 encoding random input and therefore the keyspace for my passphrase is 64 characters. So in order for my passphrase to be at least as strong as the volume encryption key then there need to be at least 2 ^ 512 possible combinations within the length of the passphrase. This can be expressed as:

(size_of_keyspace) ^ number_of_characters >= 2 ^ (size_of_key)

So for this example of a volume key size of 512 and a passphrase keyspace of 64 then the minimum number of characters my passphrase should be in order to be at least as secure as the volume key would be 86.

Is this logic correct or is there some drawbacks I should be aware of? Any other recommendations which can be offered along the lines of this question?

My reasoning for this is that there is no inherent benefit of having a passphrase which is stronger than the actual payload key itself -- someone brute forcing my drive is ultimately trying to crack my encryption key, not my passphrase. If my passphrase is stronger than the encryption key then an attacker can brute force the encryption key faster than they can the passphrase. Is this correct or is there some benefit to having a passphrase which is stronger than the encryption key, maybe as a resource drain for an attacker who doesn't diversify their methods well enough?

Answer 1

In the context of security, everything is a trade off. More on that in a second....

What are the attack options for breaking into your encrypted volume? They are, basically:

1. Brute force search of the keyspace for the key utilized by the symmetric encryption primitive.

2. Brute force the passphrase by trying every possible password utilizing your volume's specific salt and key derivation parameters.

3. Evil maid, rubber hose, key logger, or other "non crypto" means of securing your keymat.

You should worry about number 3. Because its the obvious attack vector.

No one is going to succeed in brute forcing the key used for the block encryption primitive.

From a basic security perspective, I remain convinced that even 128 bit keys are fully secure if the implementation is not broken. A brute force search in that case has to exhaust on average half of a key space that has 340,282,366,920,938,463,463,374,607,431,768,211,456 possibilities.

For a 256 bit keyed primitive, you're talking about 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936 possibilities.

So even with 256 bits of key security you're already reaching numbers that approach the number of atoms in the known universe.

So that's out.

What you're worried about is someone trying every possible pass phrase.

Now, remember that LUKS uses some salt + PBKDF2 to stretch your pass phrase to the size of the key space. What this means is that even a password of "a" can map to any possible spot in the entire key space. So attackers aren't going to have a rainbow table that will help here.

If they're going to brute force the pass phrase, they will have try all the possible inputs, running each through the key derivation function with the parameters used on your volume (salt & iterations). That takes time. And, if memory serves, LUKS actually sets the iterations to take a specific amount of time per "try."

What this means is that you simply need a pass phrase length that has enough entropy to make it unfeasible for an attacker to try a sufficient number of possible phrases to locate your phrase. The attacker can of course use GPUs or specialized ASIC hardware to speed this process up (its why folks are experimenting with things like Scrypt to make that harder), but you will be more than protected with 20 to 30 characters containing lowercase, uppercase, numbers and keyboard symbols (including symbols from shifted numbers and other symbols on the keyboard).

This brings me back to my initial comment. Its important to keep in mind the trade offs. You can try to come up with a pass phrase that is equivalent to the difficulty of your 512 bit key space, but it will IMPACT your behavior. You might find yourself not dismounting / logging off when you get up to get a cup of coffee because its such a pain to get that pass phrase right when its time to log back in. You might store the long pass phrase on a phone or piece of paper. If you store it in a password manager, you will be limited by the security of the password manager and not the security of the length of your pass phrase.

Meanwhile, once an attacker has to try 20 to 30 characters of pass phrase utilizing 93 possible characters, the attacker is facing (effectively) 95 to 150 bits of entropy which puts it outside of the reasonable range of brute force.

And, all of which leads back to that third possibility of getting into your volume. Compared to brute forcing the key to the encryption primitive or trying all the possible pass phrases, the third scenario "COMPROMISE" is really what you should be worrying about. An attacker that gets you to point a compromised web browser at an exploit that gives escalated privileges on your running system can scan the memory for your password. An attacker that gets a rootkit on your system can do the same. If you plug in a compromised USB or firewire device, you're potentially compromising security. And these are all much easier for the attacker than brute forcing the keyspace or pass phrase space.

Answer 2

In practice, an attacker will attempt to attack your passphrase before your key. In some cases it is much more difficult to attack the actual key. Keep in mind that for both the passphrase and the key, it is important to have lock out policies.

In reality, on a system with a good lockout policy, attackers against high quality 10-12 character pass phrases are unrealistic. 86 characters of high quality pass phrase would be very hard to beat indeed. If I were an attacker, I would simply find another way. I think a 20 character passphrase would be more than sufficient for your purposes.

So to answer your question, I would say that you shouldn't worry about whether your password length might attract malicious users toward directly cracking the key. I would instead insure that there are proper lockout, and rate limiting policies so that brute force attacks are essentially impossible in the first place.

It is easy to miss the forest for the trees here. Don't go to all the trouble with the passwords, over thinking them, when you didn't do the research to make sure that there wasn't already an auth bypass for an outdated piece of software you are using. Try to see the whole security picture. Research your software platform, and make sure there aren't any more grave security holes - that will be the next target once the attacker realizes your password isn't "password."

Answer 3

The question essentially boils down to "How many bits of entropy should a passphrase have?". Too much, and we are memorizing extra characters with no additional benefit, too little, and an attacker can brute force the access to the hard drive. As pointed out by boggard's answer, at a certain point other risks (like physical access to the machine when hard drive is unencrypted, or vulnerability in the software, or keylogger, or something else) outweigh the risk of the brute force attack on the passphrase, so once your passphrase is secure enough, you should worry about those other risks, and the longer passphrase only increases those other risks.

Let's start by describing the most powerful realistic attacker. To brute force a long passphrase, an attacker would have to be good at quickly computing sha256 hashes. A well-known set of devices good at computing sha256 hashes are the ones participating in bitcoin mining. For all practical purposes, it is safe to assume that an attacker can compute at most as many sha256 hashes as the bitcoin network. As of May 2021, the hashrate of bitcoin network is 1.72 * 10^20 bitcoin hashes per second, which (given that one needs to compute 2 sha256 hashes to compute one bitcoin hash) is 3.44 * 10^20 sha256 hashes per second. This rate grows over time at a rate somewhat below doubling every year. Thus, it seems safe to assume that by the end year y the amount of sha256 hashes computed will be at most 2 * 3.44 * 10^20 * (#seconds per year) * 2^(y-2021) ≈ 2^(94 + y - 2021).

Assuming you are using the default cryptsetup options for creating a LUKS volume, you are probably (as of 2021) using PBKDF2 key derivation algorithm with the number of iterations num_iterations picked such that num_iterations iterations complete in about 2 seconds on your machine. That means that an attacker will need to compute sha256 at least num_iterations times to check 1 passphrase, essentially adding log_2(num_iterations) bits to the entropy of your key. If you already created an encrypted container, you can find the number of iterations num_iterations you are using by running sudo cryptsetup luksDump /dev/sdXi where /dev/sdXi should be replaced with the actual path to the encrypted device.

Based on the above, I would suggest that 95 + (y - 2021) - log_2(num_iterations) bits of entropy of your passphrase would be enough to ensure that the most powerful realistic attacker above only has 1/2 chance brute-forcing your passphrase. E.g. if you want to ensure nobody bruteforces your passphrase by year 2041 and you have num_iterations = 2*10^6 (that's what I get on my laptop), 94 bits of entropy, or 16 random base-64 characters is enough. At this point it will be easier (cheaper) to run 51% attack on bitcoin than to brute-force your hard drive.

Leaving the realm of realistic scenarios, if you suspect brute-forcing your passphrase will be #1 goal of NSA or Chinese government for the next 20 years (they will have a copy of your encrypted hard drive with highly valuable information and no other way to get it), and you still want to ensure they fail with probability 99.999999%, then use 124 bits of entropy, or 21 random base-64 characters.

Disclaimers:

• The above considers brute-force attack only. In case of cryptographic advancements some other attack methods on PBKDF2 may be possible.
• I am not a cryptographer.