Is it okay to use an HMAC of the plaintext and a (possibly distinct) key as the IV for symmetric cryptography? 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.
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:


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;
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
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 &mdash; 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.