Score:2

Why do most authenticated encryption primitives expect an unpredictable and uniformly random key in order to be secure?

cn flag

I've noticed that keys for authenticated encryption primitives like AES must be unpredictable and uniformly random in order to be secure. IV values and seeds for PRNGs also have to be unpredictable and random.

My question is: How those unpredictable and random values are different from predictable values that contain whole english words, for example (like verysecretkey123456)?

I assume from the perspective of the algorithm it doesn't matter (as long as the key length is correct), but attackers can guess predictable keys/passwords more easily because they try weak keys/passwords first. Am I right?

And uniformly random only has meaning when the keys are generated more than once? If so, then what will happen when we use non-uniformly random keys?

kelalaka avatar
in flag
[Attacks Relying on Poor Entropy](https://security.stackexchange.com/a/239397/86735)
Score:4
tr flag

I assume from the perspective of the algorithm it doesn't matter (as long as the key length is correct), but attackers can guess predictable keys/passwords more easily because they try weak keys/passwords first. Am I right ?

Indeed the security of such a scheme comes from the secrecy of the key. Therefore, being easy to predict implies that the scheme cannot be secure.

My question is: How those unpredictable and random values are different from predictable values that contain whole English words, for example (like verysecretkey123456)?

It's not hard to directly answer this question(I will discuss caveat at the end). To better understand this, it is worth looking closely into the actual requirements for a key. When we talk about a "random" key, we are not talking about how that key "looks", but rather, we are talking about a property of the process that generates this key. If the processed itself is good (to be defined later), like, for example, using a CSPRNG, then it doesn't matter that the key is b"YELLOW SUBMARINE" or b"\x84\x1cR\xc5X\x07\xd0\x07\xd9R'\xd1\xa2\xad\xbef" or b"verysecretkey123456". The reason is that in the ideal scenario, they both are as likely to be generated by the key generation process. In other words, I cannot tell just looking at the value b"verysecretkey123456" that it is not a secure key or not; I'll have to look at how this was generated.

caveat: Now, we live on earth, and we can make some assumptions... Seeing a key that looks like b"verysecretkey123456", it is reasonable to assume that the process wasn't a proper CSPRNG, but perhaps someone copied from Stackoverflow...

And uniformly random only has meaning when the keys are generated more than once? If so, then what will happen when we use non-uniformly random keys?

There are no general limitations on the number of times you can generate a value from such a process(unless indicated otherwise and depending on the context). For instance, you could run the following code without issues in Python. Note that we are not guaranteed the os module.

import os

keys = [os.urandom(16) for _ in range(100)]
Eugene avatar
cn flag
Thank you for the answer. I'd accept both answers if I could)
Score:1
in flag

TL;DR Because that is how they have been designed. You can use a KDF to derive keys containing at most the randomness present in the input key material.

I've noticed that keys for authenticated encryption primitives like AES must be unpredictable and uniformly random in order to be secure.

Well, they need to have 128 bits to have ~128 bit security as AES promises. In principle you could also generate, say, 112 bits of random key, then use 16 zero valued bits to make a 128 bit key. Most API's only accept bytes - i.e. multiples of 8 bits, so that would be 14 bytes random and 2 zeroed bytes for a 16 byte key. AES, in principle, doesn't require well distributed keys.

I've removed this part of the answer it has been pointed out in the side channel chat that this is not the case. That said, the known related key attacks on the key schedule won't directly work as they assume that specific attack requires a specific change in the supplied keys. However, without further analysis we cannot say that the result is secure; more information can be found here.

IV values and seeds for PRNGs also have to be unpredictable and random.

Not necessarily. IV requirements are different for each mode of operation. For instance, CBC requires an unpredictable IV (which generally translates into a randomized IV). CFB requires a nonce that is the same size as the block size. CTR mode can use any sized nonce, as long as the counter block doesn't repeat. GCM mode usually uses a 12 byte nonce. Nonces - numbers used once - can be randomized, but they may also be a serial number, for instance.

My question is: How those unpredictable and random values are different from predictable values that contain whole english words, for example (like verysecretkey123456)?

They are generally generated by a well seeded secure random number generator (CSPRNG or DRBG). Or they are derived from other information. For instance, they may be created using key agreement, usually followed by a key based key derivation function (KBKDF).

Keys may indeed also be generated from a password using a PBKDF. Those functions also require a salt and work factor (and possibly other parameters) to mitigate the risk of an attacker guessing the password. Unless other countermeasures are present the scheme could still be insecure as passwords are generally easy to guess.

"verysecretkey123456" is generally not considered a key, it would be considered a password or passphrase. The fact that it is a string rather than binary is enough of a hint for that.

I assume from the perspective of the algorithm it doesn't matter (as long as the key length is correct),

Correct, although AES requires a bit string as a key, so to use it at all you'd first have to encode the password or passphrase. Note that e.g. DES keys have parity bits in the encoded key, so not all keys take just randomized bits. More modern ciphers than DES - including AES - are generally designed to take fully randomized keys though.

but attackers can guess predictable keys/passwords more easily because they try weak keys/passwords first. Am I right?

Yes, that would generally be called a dictionary attack when they try specific words. Of course, they may test very small keys separately, and dictionary attacks can be augmented by other tricks.

And uniformly random only has meaning when the keys are generated more than once? If so, then what will happen when we use non-uniformly random keys?

No, as mentioned in the other answer uniformly random talks about the generation process, not the outcome as such. If you have non-uniformly random keys then there is a chance that an adversary can guess them - at least more likely than if the keys were uniformly random.

As per the Kerckhoff principles we generally assume that attackers know how keys or passwords are generated, so from that they would be able to guess the distribution.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.