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?

  • 1
    As a point of clarity, the goal is to protect against offline attack. – Radmilla Mustafa Feb 22 '15 at 19:20

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.

  • If you have a full copy of the disk, surely you can get around the LUKS rate limiting? – Simon Woodside Jun 20 '16 at 18:38

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."

  • My question pertains to offline attacks. Let's say I have left my computer unattended for a moment or two and my attacker has made a physical 1:1 copy of my hard drive. Now there are two possible paths to my data -- one is to crack my passphrase and the other to crack my key. If the attacker is devoted to decrypting my drive, it is now only a matter of time. – Radmilla Mustafa Feb 22 '15 at 19:17
  • Not if your key is of any reasonable size. Even with a full size cracking rig, you're not going to get anywhere with a proper 512 bit key if the crypto implementation is sound. security.stackexchange.com/questions/4518/… – baordog Feb 22 '15 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.