AES key reuse and guessing the key

Question

Bit of a noob question and a fair bit of Googling didn't help. I understand that the current encryption standard is AES256. A few questions

1. Is the point of this (and other encryption techniques) to reuse the same private key for multiple messages? If we're using one-time keys, then a simple addition is enough and the complicated AES256 protocol is unnecessary yes?

2. If we are using the key multiple times, how many times is it okay to use it before the message is no longer secure?

3. How do we measure the strength or weakness of such a protocol? I assume the objective of an attacker is to guess the key but how is it quantified, how easily someone can guess the key?

4. Is it that given the encrypted and the plaintext for a given key, how easy it is to guess the key that is used as the "standard" to judge?

Apologies if this is too basic but all the explanations about AES focused on the details of the protocol, not these more basic concepts.

Answer 1

You're missing a piece in your understanding of modern encryption.

AES is a symmetrical block encryption cipher. It describes how to use a key (which can be 128, 192 or 256 bits long) to encrypt and decrypt a single block of fixed size (128 bits) of data. That's it.

In order to have a complete encryption/decryption system, you need to couple it with several other pieces.

First, you need to decide how you're going to apply that algorithm to data that is not exactly 128 bits long. At the same time, you might want that "system" to provide additional properties: make sure that encrypting two identical pieces of data with the same key will not result in the same encrypted data, providing a (standard) way to verify that a given block of data has been properly decrypted, etc.

That's the job of the mode of operation of your block cipher (and the padding algorithm you pick). There are several you can pick from which have different properties (and some are "protected" by patents which can makes their use expensive). Which one you choose depends mostly on what you're going to apply it to. Almost all of these modes of operation will use something call an initialization vector (IV) which is a block of data that is use to initialize the processing and which should be unique but not private (so you can send it with the cipher text without any risk).

Once you couple these two elements, you can start thinking about key management.

AES is symmetrical so it uses the same key for encryption and decryption. There is no public key involved.

So, after this, the answers to your questions are:

1. The reuse of the key is not a problem as long as you have chosen a mode of operation that is appropriate for your application (and of course, if you have used it properly). This is because the mode of operation will "pre-mix" your clear text data in a way that, even before encryption, two identical block of data you feed to the actual AES algorythm will never be identical (or at least, not more often than by random chance).

2. To simplify, you can reuse a private key as often as you want as long as you can generate new initialization vector for each message.

3. The "strength" of an algorithm mostly is defined on how long it takes for an attacker to test a set keys. A perfect cipher would have you attempt a full decryption using half the possible keys (key space) before you had a 50% chance of finding the right one. Many attacks on modern cryptographic ciphers consist of finding ways to test a key faster than going through the whole system or being able to obtain information about the key based the on input or output (sometimes both). The whole science behind this art if called "Cryptanalysis".

As you can see, finding out if an cipher is "safe enough" is a very complex tasks. That is why no serious system uses its own private crypto: it is just too hard (and expensive, and long) to come up with a good proof of safety. Hence the "rule zero" of secure software development: "don't write your own crypto". It's hard enough to use known algorithms properly...

Answer 2

Apologies if this is too basic but all the explanations about AES focussed on the details of the protocol, not these more basic concepts.

In fact you are asking about general secret key management :)

1) Is the point of this (and other encryption techniques) to reuse the same private key for multiple messages? If we're using one-time keys, then a simple addition is enough and the complicated AES256 protocol is unnecessary yes?

In theory - you can reuse the secret key for encryption directly (this is called ECB mode - Electronic Code Book mode), but then you're leaking information - see Block cipher modes. Comparing multiple cipthertexts you can see the encrypted data are the same (and having information about the plaintext it is possible to recover the plaintext and the key completely). You may want to use other cipher modes (stream, CRT, CBC, ...).

What you mean by the 'addition'? If you mean you XOR / ADD the plaintext with the secret key - you need to make sure the key in fact a 'one time pad' and really random. AES (generally any encryption protocol) is designed not to leak any information about your key or the plaintext.

And very important part - do not forget about the authenticated encryption - make sure the integrity of the ciphertext is ensured.

2) If we are using the key multiple times, how many times is it okay to use it before the message is no longer secure? 3) How do we measure the strength or weakness of such a protocol? I assume the objective of an attacker is to guess the key but how is it quantified, how easily someone can guess the key?

There is a lot of math around - depending on the key size, key usage, usage frequency and estimated adversary computing power. But keeping it practical - look for a chapter "Recommended Cryptoperiods for key types" in the NIST-800-57. It doesn't give you exact answers, but there are guidelines to be more or less secure and still usable.

4) Is it that given the encrypted and the plaintext for a given key, how easy it is to guess the key that is used as the "standard" to judge?

If proper encryption is used, it should be very hard. That's why you may want to use standard encryption protocols, nothing custom or simple (as you mentioned in you first question).

Carpe diem

Answer 3

(Partial answer.)

Yes, you can encrypt multiple plaintexts with the same key, as you couple AES with a cipher-block mode that allows that. ECB does not allow that. But using AES-CTR or AES-CBC with a counter or an IV randomly generated allows you to encrypt a lot of data under the same key.