Why do we need special key-wrap algorithms?

Question

Wikipedia says:

Key Wrap constructions are a class of symmetric encryption algorithms designed to encapsulate (encrypt) cryptographic key material.

We are using these algorithms to encrypt (and authenticate) a key, using a symmetric algorithm (and symmetric key, named key encryption key).

Some of these algorithms are quite complicated, like the AES-keywrapping algorithm AESKW defined by NIST originally in 2001, with a new draft 800-38F available now. In the following image, each red box is one invocation of the AES block cipher, to encrypt in total only 256 bits (i.e. 2 blocks) of plaintext (including a constant part as integrity check/authentication):

(Image from Figure 7 of Deterministic Authenticated-Encryption - A Provable-Security Treatment of the Key-Wrap Problem, by Rogaway/Shrimpton, 2007.)

Why do we need such complicated algorithms, when a simple combination of CBC or CTR mode with a MAC, or an authenticated encryption mode like AEX would give us the same security result?

Answer 1

The paper you cite (Deterministic Authenticated-Encryption...) gives quite a bit of useful information (but I'm assuming you already knew that). It looks like a pretty good read (I'll let you know if that assumption holds after I finish it).

For why simpler constructions (CBC/CTR with a MAC or even AEX mode) don't satisfy (emphasis added):

A key-wrap scheme is a kind of shared-key encryption scheme. It aims to provide “privacy and integrity protection for specialized data such as cryptographic keys, . . . without the use of nonces” (meaning counters or random bits). So key-wrap’s raison d’etre is to remove AE’s reliance on a nonce or random bits.

The reason for removing the nonce/IV/random bits, at least according to the paper, is to make the protocol "more resilient to IV misuse."

I also found the following paragraph useful (emphasis added):

That said, in many contexts where one would think to use key wrap, one can use a conventional AE scheme, instead. This does not make studying the key-wrap problem pointless. First, it clarifies the relationship between key wrap and conventional AE. Second, DAE leads to misuse-resistant AE, and methods that achieve this aim make practical alternatives to conventional (not misuse-resistant) two-pass AE methods. Finally, practitioners have already “voted” for key-wrap by way of protocol-design and standardization efforts, and it is simply not productive to say “use a conventional AE scheme” after this option has been rejected.

Another potential reason for key-wrap algorithms is their analyzability. I'm not completely sure about this, but it could be that under the key-wrap algorithms, security is provable, but that might not be possible under a more simplistic approach.

On a side note, when reading through the intro to that paper, it made me wonder how the notion of Entropic Security plays into key-wrap algorithms. In the paper, they briefly mention it as a related work, but that is all.

Answer 2

With most standard modes of operation, the encryption of the first bit of plaintext is only functionally dependent on the other input bits in its block (plus the IV if one is used). It isn't dependent on any of the bits in the next block of plaintext, for example.

Key wrapping is essentially a mode of operation where the encryption of every bit of input is functionally dependent on every other bit of input in every other block in a non-trivial way.

The application to keys (instead of general data) is somewhat inconsequential. Key wrapping can be used for either keys or data, and standard modes of operation used for data are often also used for keys. Since the constructions are complicated (the number of encryptions needs to be at least quadratic linear in the number of plaintext blocks for everything to touch everything else), it is generally pitched for encrypting things that are only a few blocks long (but more than one block) and where the added non-linearity could be beneficial.