Suppose I have an AEAD mode based on a block cipher that requires two or more keys.

In some cases, there is a complex proof that one key suffices. But finding such a proof is hard.

An alternative is to use the block cipher in CTR mode to generate a pseudorandom stream from a master key, which is then split as needed into the needed keys. It seems to me that this is always secure (assuming that the block cipher is itself secure, which you almost always are assuming anyway). It is also simple to implement in both hardware and software, allows you to use a longer nonce, and helps with birthday attacks if the extra nonce (used for CTR mode to generate the subkeys) is itself a "nfewtimes" (I don't think the distinguisher against CTR mode is of any use to an attacker until most of the full codebook is exhausted).

Is this recommended? Assuming you can't just use EAX or CCM, that is.


As Maarten Bodewes points out, you should use a known key derivation function instead of this method (i.e. don't roll your own crypto). Having said that we can still try to understand what happens if you do use this method.

I assume that the method you're describing is something as follows. You take a block cipher $E:\mathsf{K}\times \mathsf{X} \to \mathsf{X}$, and a master key $K\in\mathsf{K}$ and then generate subkeys using $$K_0 = E_K(0), K_1 = E_K(1), K_2 = E_K(2), \ldots\,,$$ where $0$, $1$, $2$, $\ldots$ are distinct strings in $\mathsf{X}$.

If you only use the subkeys $K_0,K_1,K_2,\ldots$ as keys in the mode, there should not be an issue, since you're basically using the block cipher as a key derivation function. In order to do this, all you need to assume about the block cipher is that it is a secure pseudorandom permutation when keyed with $K$, $K_0$, $K_1$, $\ldots$. This, of course, also assumes that it is meaningful to use the output of $E_K$ as its key, which you can do for AES128, but not immediately with AES256 (you would have to use two block cipher outputs as a key).

However, the downside to the above approach is that you have to switch keys a few times, which might not be so bad depending upon the application, but is undesirable in general. The optimizations performed by modes such as GCM, EAX, and OCB make it so that you do not need to switch block cipher keys. Their trick is to use $E_K$ and the value $L = E_K(0)$ (or something similar) alongside each other in the mode, without ever using $E_L$. In particular, to ensure security this means that the mode needs to avoid outputting $E_K(0)$ as part of a ciphertext or tag, since then you've released $L$ to the adversary.

Just to be clear, neither method will help you against birthday attacks on the mode. As long as the master key stays the same, you will still find attacks with birthday bound complexity. Also, I don't immediately see the benefit in using a longer nonce, since the number of messages you can process using a key is often well below the number of nonces you can generate using half of a block length. For example, your nonce does not need to exceed 64 bits when using AES128 in GCM, since the birthday bound limits you anyway.

  • $\begingroup$ Is the birthday bound per $2^{n/2}$ uses of the master key, or per $2^{n/2}$ uses of the subkeys? By making parts of the counter variable one can generate up to $2^{n/2}$ subkeys from the master key, and then use each set of subkeys up to $2^{n/2}$ times, for a total of $2^n$. Or did I make a mistake? $\endgroup$ – Demi May 20 '16 at 21:45
  • $\begingroup$ That's an interesting observation. The birthday bound is on the $2^{n/2}$ uses of the subkeys and the $2^{n/2}$ uses of the master key, but it's not obvious that you can just use the master key $2^{n/2}$ times without running into trouble. This is because a block cipher will not give you perfectly independent, uniformly random subkeys, so your assumption on the block cipher changes as you continue to use the master key. However, the trick you describe is used to design a beyond birthday bound mode called CIP (Tetsu Iwata, Africacrypt 2008). $\endgroup$ – pxdnr May 21 '16 at 9:54

No, it's recommended to use a well described KBKDF (key based Key Derivation Function). If you like counters you could try NIST SP 800-108 section 5.1: KDF in Counter Mode. But note that it doesn't use Counter Mode encryption; rather than that it uses a counter combined with a PRF: HMAC or CMAC. If you use CMAC you could still use AES (or any other secure block cipher) as underlying primitive.

If you also have access to hash functions you'd probably be best off with HKDF or just HKDF-expand, although you could also use above counter mode with HMAC.

The creation of additional bits from a lower entropy source is called key stretching. Obviously the resulting keys will not have more entropy then the input but the entropy should be well distributed over the output bits. In general, if you require two outputs, you should call the KBKDF twice with different labels (constant identifiers) for each key.

  • $\begingroup$ I interpreted this question quite differently. I agree with you that people should use key derivation functions instead of this method, but I was under the impression that the person was asking more out of curiosity. I'll change my answer to reflect this. $\endgroup$ – pxdnr May 21 '16 at 9:39
  • $\begingroup$ @pxdnr I was mainly reacting on "Is this recommended" part of the question - hence my specific answer. If Demetri meant one or the other he probably should have mentioned it more clearly. Anyway, there is no single right answer most of the time :) $\endgroup$ – Maarten Bodewes May 21 '16 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.