[Cfrg] how to guard against VM rollbacks

I've mentioned in a previous thread that the security of a nonce-based
cryptographic scheme may be compromised due to unintentional nonce reuse
caused by rollback of one's virtual machine state to an earlier snapshot.
Apparently this problem has been noticed by few others and no one has
proposed a solution (that I could find). The only mention I found of this
issue is in [1].

I'll throw out some ideas in the hope of bringing more attention to this
problem. It seems a fairly serious one given the increasing popularity of
virtualization and the fact that virtually every protocol and application
software that uses cryptography may be affected.

First of all it seems necessary to abandon the use of counter-based and
other state-derived nonces, and return to either random nonces or
deterministic cryptography. Until we have operating system support (perhaps
an API to designate a memory buffer or file as protected from rollbacks?)
it's hard to see how we can safely use state-derived nonces when state
rollbacks are a possibility.

If random nonces are used, care must still be taken to guard against
rollbacks. At a minimum, the nonce must be randomly generated *after* the
message to be encrypted and/or authenticated has been fixed. This way, if
nonce reuse occurs due to a rollback, it will be reused only with the same
message that it was used with previously, which should be safe.

Where possible, it may be best to go back to deterministic cryptography. For
example HMAC does not use a nonce and therefore is not affected by this
problem. If faster speed is desired and you want to use a MAC in the
Wegman-Carter paradigm, notice that tag=PRF(hash) works just as well as
tag=hash xor PRF(nonce) (i.e., they both have collision probabilities that
grow as the square of the number of messages) if nonce is generated
randomly. tag=PRF(hash) does not suffer from nonce reuse problems, and also
lets you save complexity and bandwidth by not having to transport a nonce.

[1] Tal Garfinkel and Mendel Rosenblum,"When Virtual is Harder than Real:
Security Challenges in Virtual Machine Based Computing Environments"
http://www.stanford.edu/~talg/papers/HOTOS05/virtual-harder-hotos05.pdf