Can RFC 5649 be used to wrap multiple keys with the same KEK? I am unable to convince myself that RFC5649 is secure when storing multiple keys with the same KEK. My point is: RFC5649 uses AES-ECB, therefore the usual weakness of this method applies, namely an observer can deduce equalities among sections of the wrapped keys.

However, the sizes of the wrapped content make it less likely to have collisions (except for the AIV, but I do not believe that that could be an issue), as the payload will be 256bits of random data.

My question is therefore, is it secure to wrap multiple keys with the same KEK? If the answer is no, then what is the point of RFC5649 and what alternatives are there available?

(I believe the same doubt applies also to RFC 3394)
There are basically two purposes for which "ECB mode" encryption (i.e. simply splitting the input plaintext into blocks and applying the raw block cipher encryption function to each block) is safe and useful:


To deterministically encrypt messages up to one cipher block (i.e. 128 bits, for AES) long, in situations where the determinism of the encryption is acceptable (i.e. either it is extremely unlikely for two messages to ever be identical, even under an active attack, or it is acceptable for an adversary to learn if two messages are identical).
As a building block for other encryption schemes with (preferably provably) better security properties.


This is, in fact, what the scheme described in RFC 5649 does.  First, it is a deterministic key wrap scheme: this means that, by design, it does not even attempt to conceal whether or not two wrapped keys are identical.

Second, the scheme described in RFC 5649 only uses AES directly in ECB mode if the key to be wrapped is less than 64 bits long, which means that the key and the 64 bit "IV" together fit in a single 128 bit AES block.  Otherwise, it instead uses the wrapping process described in RFC 3394.  This process is not simple ECB mode encryption, but rather a kind of a wide-block cipher construction built on top of AES.

While RFC 3394 does not contain a security proof for this construction (and if one exists elsewhere, I'm not aware of it), it seems plausible that one could be found, perhaps in a manner similar to Luby and Rackoff's famous 1988 result on Feistel ciphers.  And that's not just my personal guess, either; Rogaway and Shrimpton, who review (and criticize) a version of the scheme in their 2006 paper on deterministic authenticated encryption, also state that:


  "The above criticism notwithstanding, we find it likely that the mechanism is correct. Namely, the modified Feistel network illustrated in Figure 7 is, we conjecture, a secure enciphering scheme (in the sense of a strong, variable-input-length PRP). Scheme AESKW is then seen as an instance of the PTE paradigm, except that the header is folded into the plaintext instead of used to tweak the enciphering scheme."


That said, there's really not much point: in the same paper I just quoted and linked to above, Rogaway and Shrimpton also introduce SIV mode (since then standardized in RFC 5297), which provides a more efficient, flexible and provably secure (in a precise sense also defined in the paper) method for deterministic key wrapping.

As a bonus, in situations where deterministic encryption (and the resulting leak of plaintext equality) is not desired, SIV mode can also be used with an optional nonce to provide a fully CCA secure authenticated encryption scheme.