Is there a practical security difference between XXX-bit encryption?

Question

I know I'm treading in dangerous waters asking this - my comprehension of cryptography math is sorely lacking. On the flip side it gives me massive admiration for what many of you are able to do.

From my understanding of crypto functions, a password is typically used to create a xxx-bit secret key. This could be 128-bit, 256 bit... 2048-bit (aka xxx-bit encryption) etc. This key is then used to encrypt the data via whatever algorithm is chosen (AES, etc). As I understand it (I could be wrong) you can either decode the information by supplying the correct secret key, or by supplying the correct password which produces the correct secret key.

Given that typically something like an 8 digit alpha numeric case sensitive password would supply 30 bits of entropy, my assumption is that in almost all cases the password would have significantly less entropy than the cryptographic secret key, hence the logical target for brute force attacks. Because of this weak point, which is independent of the encryption key length, is the target of the attack, is there any practical advantage of going for longer bit encryption schemes in keeping data safe?

Caveats

• Being very new to cryptography, I probably have gotten terminology wrong. Feel free to correct me but don't get hung up on strict interpretation of what I've said, more the 'theme' of the question.
• If I've gotten anything wrong about how the encryption process works please let me know.
• This question is targeted towards encryption / decryption with human interaction rather than say SSL certificates. Let's assume a password exists and is used.
• I'll try and follow any math you give, but you might lose me!

Thanks so much crypto. First question here, sorry if I've missed anything.

Edit: As an obvious follow up after two answers have been provided showing I'm largely on the right track with my thinking - What's the virtue of choosing longer keyspace algorithm? Again basic understanding is it would give "more" security at the cost of computational intensity in calculating the key. Why do we worry about 1024-bit and 2048-bit encryption? Aren't they both essentially unbreakable anyway?

Answer 1

Key size represents the maximum number of attempts it would take to try every possible key. If your key size is 4 bits, it will take you no more than $2^4$ or sixteen tries before you stumble upon the correct key (this is called brute-forcing the algorithm.) Key size represents the maximum theoretical strength of an algorithm, but it does not directly represent the actual strength. The actual strength is represented by the number of brute force attempts you have to make. And that number can be reduced by clever attacks.

( Generally speaking, requiring $2^{80}$ attempts is near the edge of where brute force is considered impractical. )

Different algorithms have different ways of using the keys, and those can reduce the number of attacks needed to exhaust the keyspace, effectively "reducing the strength" of the algorithm. For example, a DES hardware implementation takes a 64 bit key, but 8 of those bits are discarded, leaving only $2^{56}$ possible keys. DES also has an inversion property, meaning if you decrypt a message like this: $m=DESdecrypt(k,c)$, if you then invert all the bits in the key so that $k' = !k$, then $m' = !m$. In other words, it's a free test for exactly half the remaining keyspace, bringing the cost of a brute force attack to $2^{55}$. Other weaknesses have led to improved attacks on DES such that the cost of brute forcing it is somewhere around $2^{48}$ attempts. That is significantly less strength than the $2^{64}$ bits of key material it started with.

As a proof of the weakness of DES, Deep Crack was purpose built to test all of its keyspace within one day.

DES provides us with another example. In an attempt to extend its lifetime, 3DES was created using three back-to-back-to-back implementations of DES, with three different keys. While the actual keyspace is $2^{56*3}$ = $2^{168}$, a meet in the middle attack reduces its actual strength to $2^{112}$. This is still plenty strong against a brute force attack, so 3DES remains secure. Its only drawback is speed - 3DES is much slower than AES-128 or other modern cyphers.

In general, while the brute force range remains above $2^{100}$, an algorithm is still likely to be secure.

RSA and other asymmetric algorithms use math differently, so keysize has to be understood to be different as well. Their strength lies in the difficulty of solving a hard math problem, such as factoring the product of two large prime numbers. Different factoring algorithms have different efficiencies, and it's the factoring algorithms that define brute force. 20 years ago, a $2^{512}$ bit key was strong enough to survive a brute force attack. Today, a $2^{1024}$ bit RSA key is near the edge of what can be factored. And RSA lives only at the mercy of mathematicians making no more advances in factoring algorithm efficiency. If some brilliant mathematician were to find a general solution to factoring, RSA would be completely broken. (And people are always trying, because that path leads to eternal glory - literally. We still discuss the Sieve of Eratosthenes today, and he died over 2000 years ago.)

As you correctly observed, password strength is a weak point in many implementations because there are only about $2^{19}$ words in the English language (and people are not terribly creative), but it's not the only weak point. Timing attacks can reveal bit-by-bit details on key information. Protocol errors can allow an attacker to pretend to be an old piece of equipment and force the choice of an old or broken form of encryption, or no encryption at all. Chris Paget demonstrated this at DEFCON 18 with a brilliant man-in-the-middle attack on ordinary cell phone encryption.

One phrase you will hear in cryptography is that "attacks never get worse." Once a wedge has been driven into an algorithm, it can be forever exploited by other attackers, and multiple wedges can often be stacked making an algorithm powerless against attack. They all can contribute to reducing the strength of an algorithm.

Answer 2

From my understanding of crypto functions, a password is typically used to create a xxx-bit secret key... Given that typically something like an 8 digit alpha numeric case sensitive password would supply 30 bits of entropy, my assumption is that in almost all cases the password would have significantly less entropy than the cryptographic secret key, hence the logical target for brute force attacks.

First, many (if not most) secret keys should be generated by a cryptographically secure source of random numbers. This will generate a key with maximum entropy: 128 bits, or 256 bits, depending on the size of the key. This is well out of the range of brute force.

If you do need to generate a key from a password, there are algorithms like PBKDF2 which attempt to increase the cost of brute-forcing the key. They have a configurable work factor which, when increased, exponentially increases the amount of computing power required to turn a password guess into a key. You still should avoid using trivially weak passwords, but if the work factor is configured such that each brute force attempt requires around one second to compute (using today's hardware), it would take 17 years on average to break an 8-character alphanumeric key.

That's still obviously far short of the amount of time it would take to brute force a 128-bit randomly generated key, so the use of strong passwords is still absolutely mandatory. Something like a 10-digit password consisting of any of the glyphs on a standard US keyboard would take over 800 billion years to crack given a work factor requiring roughly one second to generate a key from each password guess, given today's hardware.

Why do we worry about 1024-bit and 2048-bit encryption?

The strength of a key given a certain size is based upon how that key is generated. For 128-bit and 256-bit keys, we are almost inevitably talking about symmetric encryption. For these types of algorithms, the key is randomly generated.

Asymmetric (public/private key) encryption is a different beast. For algorithms like RSA, the key is not simply a very large random number: it is a very large semiprime. In simplified terms, your private key typically will consist of two large prime numbers, and the public key is the 1024-bit or 2048-bit semiprime that results from multiplying those two primes. The difficulty of breaking the key is the amount of effort an attacker would need to spend to factorize the public key in order to discover the two primes that make up the private key — this is a task we believe to be extremely hard.

Based on how hard we think that problem is, we currently believe the effort to factorize a 1024-bit semiprime to be roughly equivalent to brute-forcing a 128-bit keyspace. Likewise for 2048-bit semiprimes and 256-bit keyspaces. There are other asymmetric cryptosystems that rely on other "hard" mathematical problems, and their key lengths are likewise based on how hard we believe those problems to be.

Answer 3

I'm just an enthusiastic amateur, so hopefully this is not too far off base!

You're correct that in the contexts you are talking about, the password is indeed used to create a secret key.

What's more, the process by which that occurs (ie. the key derivation algorithym) is assumed to be public knowledge.

So, guessing the password, is equivalent to guessing the secret key - regardless of the length of that secret key. If the password was guessable, or could be determined by brute force, or found in common password lists, it wouldn't matter how long the derived secret key was. In that scenario, a 256-bit derived secret key would not provide any more practical security than, say, a 128-bit one.

I believe that answers your question.

As a vaguely related fact of interest, understand that you can't always assume that longer keys are more secure than shorter ones anyway! Asymmetric (public key) ciphers generally need much longer keys than symmetric (private key) ciphers, to provide the same security. So for example, I gather that a 1024-bit asymmetric cipher key is weaker than a 256 bit symmetric cipher key.

More on key lengths and symmetric/asymmetric ciphers here: http://en.wikipedia.org/wiki/Key_size

TC