Security strength for encryption and authentication (wrapping) of cryptographic keys

Let $K$ and $M$ be AES secret keys. The purpose is to wrap $K$ using $M$ to allow $K$ to be used at a later time (see, e.g. NIST SP 800-38F, section 3.1). One method to achieve this goal is to use $M$ with an Authenticated-Encryption algorithm such as AES-CCM or AES-GCM. Another way is Encrypt-then-MAC such as AES-CBC + AES-CMAC with independent keys $M_1$, $M_2$.

The general question is how one must choose the values for the parameters in the above methods in order to preserve the security strength of $K$. To be more specific:

1. What should be the size of $M$ (relative to the size of $K$)?
Suppose $K$ is an AES-256 key and $M$ is an AES-128 key. Presumably, encrypting $K$ with $M$ will reduce the security strength of $K$ to 128 bits since the complexity of a brute-force attack on the wrapped key is $\mathcal{O}(2^{128})$.

2. What should be the size of the authentication tag (relative to the size of $K$)?
Now suppose both $K$ and $M$ are AES-256 keys so there shouldn't be an issue with the encryption mentioned in the previous paragraph. However, in all the algorithms mentioned above, the maximal tag size is 128 bits so in all the cases the authentication can be attacked with complexity of $\mathcal{O}(2^{128})$ regardless of the size of $M$.

1 Answer

There is a non-academic kind of answer, that states that there is no better security than "cannot break it", and 128-bit keys are already quite far into that zone, leading to the following recommendation: 128 bits for everything, and be done with it.

A dual version, often encountered in marketing and compliance circles, is that larger keys are always better, and more apt at wooing auditors or customers; thus, you need 256-bit keys everywhere. If you could paint keys, you would make them red, or decorated with shark teeth drawings.

Of course, this cannot please everybody. There are some rational objections related to multi-target attacks: if you want "128-bit security" but you have a set of $2^{30}$ keys to try to attack, and finding any one of them is enough for the attacker to "win", then you need 158-bit keys to reach your specific level.

For that kind of analysis, context matters a lot. For instance, if you have one wrapping key $M$, used to protect $2^{30}$ keys $K$, and you want 128-bit security, then $M$ must live in a space of size at least $2^{158}$. Conversely, if you have a single key $K$ but it has been wrapped with $2^{30}$ distinct keys $M$, then the attacker only has to break on of the wrapping keys to obtain $K$; in that situation, $M$ should have length 158 bits or more, while $K$ may remain at 128 bits.

Therefore, there is no fully defined clearcut context-free answer.

The authentication tag is not about confidentiality, but integrity. Integrity matters, notably because in most contexts where attackers can observe confidential data, then can also change it. For instance, over the Internet as it is practiced today, to eavesdrop on a link, you must be physically connected to that link, or arrange to make the link pass through hardware you control (e.g. you run your own WiFi access point, or you poison the DNS to make target names resolve to the IP address of your own server).

There again, context matters a lot, as well as application conditions. Suppose, for instance, that wrapping uses AES/GCM with a 256-bit wrapping key $M$. An attacker could try to find the key through exhaustive search, which is going to be expensive ($2^{255}$ tries on average). On the other hand, the attacker may "just" want to make a forgery (feeding the recipient with a fake encrypted key); with a 128-bit authentication tag, the attacker has probability $2^{-128}$ of succeeding at each attempt. In that sense, the authentication tag offers only 128-bit security.

But the situation is quite different! In the exhaustive search on the key, each "try" correspond to the spending of some computational power by the attacker on his own machines. This attack is not limited by anything else than the attacker's budget. On the other hand, each "try" on a forgery attempt implies talking to the recipient, to see if the altered wrapped key will still be accepted. That attack is then running on the defender's budget, which is usually a lot less than the attacker's. Moreover, it's much less discreet: after a few billions of failed attempts, the defender may catch up that something's running afoul.

Thus, it would be wrong to equate "128-bit symmetric key security" with "128-bit authentication tag security". They don't really live in the same world.

• Usually I'm all for the "can we live with a 256 bit authentication tag and 256 bit AES?" Unfortunately, quite often in my smart card related world the answer is no, but I'm all for choosing the higher size if you can spare the time/resources. It won't protect you against a bad protocol or bad implementation of course, usually much more important than the key size. Any second spent on key size is probably better spent somewhere else. – Maarten Bodewes Mar 26 '18 at 20:01
• 128-bit keys are suspect to being broken with massively parallel and quantum adversaries. AES has 128-bit blocks, so even using 256-bit keys for AES may not be enough. We should be using both 256-bit keys and 256-bit or larger blocks. Today it may be "fine" and so is sha1; but if there exists an attack cheaper than exponential, the scheme is "broken". – cypherfox Mar 27 '18 at 3:47