Can RFC 5649 be used to wrap multiple keys with the same KEK?

Question

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)

Answer 1

Yes, it is secure to wrap multiple keys with the same Key Enciphering Key (KEK) if that's done

• as a single wrap of the keys aggregated together,
• or as multiple wraps with each each key aggregated with a distinct Key IdentiFier (KIF).

Otherwise, it would be possible to tell if two separately wrapped keys have identical values (at least when a fixed Initial Value is used).

---

RFC 3394 aims to (emphasis mine)

securely encrypt plaintext key(s) with any associated integrity information and data, such that the combination could be longer than the width of the AES block size (128-bits). Each ciphertext bit should be a highly non-linear function of each plaintext bit, and (when unwrapping) each plaintext bit should be a highly non-linear function of each ciphertext bit.

RFC 5649 is an extension which aims to

eliminates the requirement that the length of the key to be wrapped be a multiple of 64 bits, allowing a key of any practical length to be wrapped.

Contrary to the question's statement, neither RFCs use AES in Electronic CodeBook mode (ECB). That would not meet the emphasized aim. They use AES as an electronic codebook, otherwise said as a block cipher, with multiple passes over the key (the only exception is for eight-octet keys in RFC 5649).

RFC 3394 (thus its extension) explicitly allows

to include other data with the key, to wrap multiple keys together, or to wrap data that isn’t strictly a key.

Aggregating each of multiple keys with a unique KIF makes them distinct even if they otherwise share the same value, and it becomes safe to wrap them separately with the same KEK, thanks to the emphasized aim.

Addition: as noted in that other answer, we know no formal proof that said aim is met; that's only conjectured, without refutation.

Addition: While I would not recommend that, is seems that using the KIF as RFC 5649's Alternative Initial Value (AIV) would do and allow to upgrade an existing system initially without KIF, without breaking compatibility with a layer transporting fixed-size wrapped keys.

Answer 2

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:

1. 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).

2. 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.