Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was thinking of how to create an IV for a block cipher that doesn't require stored state, and I came up with the idea of using an HMAC of the (padded) plaintext and a (possibly distinct) key as the IV.

This seems to be secure:

  • The IV will only be reused if there is an HMAC collision or if the plaintext and key are the same. The former would imply that the HMAC is broken and the latter is harmless, since it is just producing the output twice.
  • The HMAC is verified after decryption, but before padding is checked, so padding-oracle attacks should not be an issue.

In particular, if the HMAC and the block cipher use different keys, there seems to be a very simple proof of security, assuming that either (1) the HMAC cannot be distinguished from a random function or (2) the block cipher is secure against maliciously-chosen (but unique) IVs:

  • The attacker cannot forge the HMAC, since this would require knowledge of the signing key.
  • Since the signing and encryption keys are different in this case, and the HMAC is assumed random, malicious IVs cannot be triggered by an attacker.

Alternatively, if the cipher is secure against malicious (but unique) IVs, then the security of the cipher+security of the HMAC seem to prove the security of the system.

This (obviously) provides no protection against replay attacks, but that requires state anyway.

However, I am not a cryptographer so I do not trust my conclusions on this matter. If this technique is secure, it would appear to be quite useful in practice, as it is simple and provides both encryption and authentication.

share|improve this question
    
The point you highlighted (same plaintext and same key produce same ciphertext) is not a problem for a cryptanalityc point of view: you don't give any additional information to the attacker, but it is a weakness from a traffic analysis point of view. If the same ciphertext is stored in different location or is broadcast multiple times on the network an attacker is able to say, for sure, that the same plaintext has been transmitted. the better, standard, way is to generate a random IV per file. – ddddavidee Dec 17 '15 at 7:03
    
@ddddavidee Ah! Didn't think of traffic analysis! That could easily leak sensitive information (ex. image split into many files). Add an answer and I will accept it. – Demetri Dec 17 '15 at 7:26
    
Nota Bene: This newer question is a generalization of “Using HMAC as a nonce with AES-CTR encrypt-and-MAC”. Mod consensus is to handle both Q&As as non-duplicates, keeping them as-is since both questions have their value and according (accepted) answers. This comment is meant to inter-link both. – e-sushi Dec 18 '15 at 13:57
    
This conversation (including the removed comments) has been moved to chat for reference purposes. – e-sushi Dec 18 '15 at 14:01
up vote 6 down vote accepted

The scheme you describe is essentially same as the "SIV construction"* introduced by Rogaway and Shrimpton in their 2007 paper "Deterministic Authenticated-Encryption: A Provable-Security Treatment of the Key-Wrap Problem".

This construction takes a PRF (such as HMAC) and a conventional IV-based encryption scheme (such as, say, a block cipher in CTR mode), and constructs a deterministic authenticated encryption scheme by first feeding the plaintext (and any associated header fields) into the PRF to obtain a pseudorandom authentication tag, and then using this authentication tag as the IV for the cipher.

In the paper, Rogaway and Shrimpton show that, assuming that the underlying PRF and cipher are secure**, the resulting scheme satisfies a security definition they call DAE security. They supply several equivalent versions of this definition, of which perhaps the easiest to paraphrase in plain English is the two-part version given in the appendices, which says that a determinstic encryption scheme is DAE secure if:

  • a (polynomial-time) attacker, given access to the encryption oracle, is unable to distinguish it (with non-negligible advantage) from a random oracle with the same output length, and

  • the attacker, also given access to the decryption oracle, is unable to forge a message (that is, produce a valid ciphertext that it did not receive from the encryption oracle) with non-negligible probability.

They also define a related security notion called MRAE, or misuse-resistant authenticated encryption, which is basically the same as DAE security except that the encryption and decryption functions take an additional (public) input called a nonce. They show that:

  1. any DAE secure encryption scheme that supports associated data (i.e. additional header fields that are authenticated but not encrypted) can be used as an MRAE scheme, simply by treating the nonce as part of the associated data;

  2. when used with a random nonce (of sufficient length), an MRAE secure encryption system is a secure nonce-based authenticated encryption scheme in the conventional sense (and, in particular, is IND-CCA2 secure); and

  3. when the nonce is repeated, omitted, or even controlled by the attacker, an MRAE scheme still remains DAE secure.

In conclusion, yes, this is indeed a secure way to construct a deterministic authenticated encryption scheme — assuming, as always, that the implementation is correct, the underlying primitives are secure, and none of the assumptions of the proofs are violated. It does leak slightly more information than randomized encryption schemes, namely whether or not two plaintexts are identical, but no more than that. (Of course, like all general-purpose encryption schemes, it also leaks information about the length of the plaintext.)

Also, a particular detail to pay attention to, when implementing this construction in environments where timing or other side channel attacks may be possible, is that both the PRF (e.g. HMAC) as well as the encryption layer need to be checked for such vulnerabilities.

(In conventional Encrypt-then-MAC schemes, the MAC layer is not vulnerable to most kinds of side channel attacks, since it only operates on data that has already been encrypted. Of course, even for conventional schemes, comparing the authentication tags can be vulnerable to side channel attacks, so... it just goes to show that one needs to be careful when implementing crypto.)


*) Not to be confused with the SIV mode of operation they define later in the paper, which is an instance of the SIV construction using a block cipher in CTR mode as the encryption layer, and a multi-input variant of CMAC as the PRF. Yes, it's a bit confusing.

**) The specific security property they require of the cipher is IND\$ security, or indistinguishability from "fake" cipher that outputs purely random ciphertext. The main difference between IND\$ and standard IND-CPA or semantic security is that the former does not permit any detectable redundancy in the ciphertext, even if it leaks nothing about the plaintext. It seems to me that the difference here is mostly technical, and that an IND-CPA secure scheme could be used just as well, if the definition of DAE security was also relaxed to permit such redundancy, yielding something like a deterministic analogue of RCCA security.

share|improve this answer

The point you highlighted (same plaintext and same key produce same ciphertext) is not a problem for a cryptanalytic point of view: you don't give any additional information to the attacker, but it is a weakness from a traffic analysis point of view. If the same ciphertext is stored in different locations or is broadcast multiple times on the network, an attacker is able to say, for sure, that the same plaintext has been transmitted (even not knowing its content). More generally a deterministic link between a plaintext and the IV used to encrypt it its bad and a weakness. One could also read some critics and analysis on the full disk encryption theory and techniques where (to not waste to much space) IV are (roughly) generated from the sector number and a secret.

The better, standard, way is to generate a random IV per file.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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