3
$\begingroup$

Suppose we have a state of block cipher initialized with some key unknown to us, that is, we have the state after running key schedule, but we have no access to actual key or subkeys, all we can do is encrypt and decrypt data with this state. How to safely derive an HMAC key from it that we can use to authenticate data encrypted with the same state?

If we use CTR mode to encrypt data, it's probably safe to use the first $n$ bytes of keystream as HMAC key, and then use the other $n + i$ bytes for the actual encryption (at least, that's what NaCl do to derive Poly1305 key from XSalsa20 stream).

What is the best way to do this if we use CBC mode to encrypt data?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Well, if you are using CBC mode in the recommended way (always using an unpredictable IV), then it turns out to be easy.

With CBC mode, the value that is presented to the encryptor is always a plaintext block exclusive-or'ed with an IV or a previous ciphertext block. If plaintext blocks are uncorrelated with both the IV and the previous ciphertext block (and the latter just means we didn't deliberately pick plaintext blocks depending on what the previous ciphertext block looked like), that means that what is presented to the block cipher are effectively random values, with no specific value being any more probable than any other.

So, if we need a bit of additional keying data, what we can do is pick an arbitrary block value $B$ (perhaps the all-zero block), encrypt that using the block cipher in ECB mode, and use that $Encrypt_{key}(B)$ value as the HMAC key. The attacker will gain information on that value only if the CBC mode cipher also happens to present that exact value $B$ while encrypting some text, that is, $B = Plaintext_0 \oplus IV$ or $B = Plaintext_n \oplus Ciphertext_{n-1}$. However, by the above argument, the values on the right hand side are effectively random, and so if we have a $b$-bit block cipher and are encrypting no more than $2^{b/2}$ blocks (going past that is not recommended because of the birthday bound; you'll be leaking plaintext blocks at that point), then the probability of that happening will be less than $2^{-b/2}$; if $b=128$, this is usually considered sufficiently small.

If you are ultraparanoid about that slight possibility, what you could do is select two blocks $B$ and $B'$ (for example, the all-zeros block and the all-ones block), and use the value $Encrypt_{key}(B) \oplus Encrypt_{key}(B')$. The attacker will know that your HMAC key is not the all-zeros value; other than that, he will gain information on the value only if both $B$ and $B'$ happen to crop up during the CBC operation; that would be bounded by $2^{-b}$

The above analysis rather assumed that you need only one block of information for your HMAC key; if you happen to need multiple, it is easy to extend this analysis to $Encrypt_{key}(B_0), Encrypt_{key}(B_1), ... , Encrypt_{key}(B_n)$ for preselected distinct values $B_0, B_1, ..., B_n$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you! Regarding your last point: would it make sense (assuming that we can use block cipher with our own keys) to derive an intermediate key like you said, and then run block cipher with this key in CTR mode to generate the final MAC key of the requested length? $\endgroup$
    – dchest
    Commented Aug 27, 2012 at 18:30
  • 1
    $\begingroup$ @dchest: that would work as well. The key that this process derives is effectively independent of the CBC encryption process (with high probability); it follows that anything derived from this key is also independent of the CBC encryption. $\endgroup$
    – poncho
    Commented Aug 27, 2012 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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