Subject: [Cfrg] how to guard against VM rollbacks

From: "Wei Dai" <[email-masked]>
Date: Wed, 10 Jan 2007 22:20:34 +0800

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
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "Wei Dai" <[email-masked]>
Date: Wed, 10 Jan 2007 23:09:30 +0800

> message that it was used with previously, which should be safe.

I should add that this advice also applies to cryptographic schemes that use
randomness that's not in the form of external nonces. For example, when
using DSA, the practice of precomputing g^k mod p should be abandoned, and
the random number k should be generated only after the message to be signed
has been fixed.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "Hal Finney" <[email-masked]>
Date: Wed, 10 Jan 2007 09:50:05 -0800

On 1/10/07, Wei Dai <[email-masked]> wrote:
> 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.

Even with a random nonce there could be duplication if the OS RNG
state does not get changed from the time the rollback occurs until the
RNG is queried for the nonce. (Here I am assuming that the RNG is part
of the virtualized OS and not a global resource.) Note that some RNGs
buffer entropy and do not add it to the main RNG state until a certain
amount of estimated entropy has been acquired, to avoid state
following attacks. That will increase the window of vulnerability to
this problem. Nonce duplication could be avoided by creating the nonce
as a hash of RNG data and the message being hashed, to achieve the
condition that nonce reuse would only happen with the same message.

This issue could especially be a problem for counter mode encryption,
where reuse of the counter initial value will largely destroy secrecy
guarantees. Something like CBC tends to be more robust to IV reuse and
still gives you an ECB-like level of security when it happens.

Hal Finney

---

From: [email-masked]
Date: Wed, 10 Jan 2007 11:45:20 -0700

> rollbacks are a possibility.

(By the way, this problem is already present in non-virtual systems -- see
below.)

If the guest code could detect that a rollback (or equivalently a
crash-and-restart), then it could update its sensitive state -- that state
which is required to be unpredictable or perhaps only non-repeating -- in
response to that event.  The update in response to restart would have to be
distinct from any update that might be applied in the absence of restart.  For
example, if you are storing a counter of e.g. 160 bits in order to generate
non-repeating numbers, and you are incrementing it each time you are asked for
another number, then every time you restart you would add 2^80.

An equivalent scheme would work for unpredictable state, e.g. when updating the
unpredictable state during normal (non-restart) operation, you set new_state =
MAC(secret_key_1, old_state), and when updating the state in response to a
restart operation, you set new_state = MAC(secret_key_2, old_state).

The point is that as long as guest code can reliably detect restart events,
then it doesn't require much support from the host in order to maintain
non-repeatingness or unpredictability -- notification of restart is sufficient.

Note that this also obviates the need for expensive "durable write" of updates
to your persistent state during normal operation.  Indeed, given this design,
one might as well never write the state back to disk except during restart (at
which point you do indeed require expensive durable write).

Unfortunately guest code cannot reliably detect such events in current VMware,
as far as I know.  (One might attempt to hack it by watching the hardware clock
closely to see if it jumps ahead.  One redeeming feature of that hack would be
that a false alarm which causes you to update your state as if you had
restarted when you hadn't doesn't cost much.)

Note that this problem is already present without virtualization -- operating
system random pools e.g. Linux's /dev/random might deliver the same
"unpredictable" state more than once in a row due to a crash and restart.  The
techniques described above ought to protect /dev/random from such a failure but
that isn't currently done as far as I know.

Regards,

Zooko

---

From: [email-masked] (Peter Gutmann)
Date: Thu, 11 Jan 2007 22:35:54 +1300

>proposed a solution (that I could find). The only mention I found of this

My code checks for whether it's running inside the most common VMM, VMware.
However, this issue is rather problematic, because so far the major users of
this technique are malware, which means anything that checks for operation
inside a VMM are likely to be identified as potential malware by heuristics-
based scanners (which in practice means pretty much everything except things
like ClamAV).  The reason why I only check for VMware is because many of the
techniques used to do the checking fall into the voodoo category (even the
VMware one isn't exactly elegant), and it's not certain that they'll continue
to work over time, or that they won't cause system instability.

So yes, it is possible to detect this, but the cost may be substantial.  In
addition it's not certain what you should do if it is detected.  With malware
it's easy, submerge again until you're outside the VM so you won't be
detected, but with legitimate software it's not certain what the response
should be

>software that uses cryptography may be affected.

Is it really a problem?  My thinking about this (in the VM check) was:

/* ...

   There is one variant of this problem that we can't work around, and that's
   where we're running inside a VM with rollback support.  Some VMs can take
   periodic snapshots of the system state to allow rollback to a known-good
   state if an error occurs.  Since the VM's rollback is transparent to the
   OS, there's no way to detect that it's occcurred. In this case we'd roll
   back to a previous state of the RNG and continue from there.  OTOH it's
   hard to identify a situation in which this would pose a serious threat.
   Consider for example SSL or SSH session key setup/generation, if we haven't
   committed the data to the remote system yet it's no problem, and if we have
   then we're now out of sync with the remote system and the handshake will
   fail. Similarly, if we're generating a DSA signature then we'll end up
   generating the same signature again, but since it's over the same data
   there's no threat involved.  Being able to cause a change in the data being
   signed after the random DSA k value is generated would be a problem, but k
   is only generated after the data has already been hashed and the signature
   is about to be generated.

   In general this type of attack would require the ability to generate
   information based on random state, communicate it to an external party, and
   then generate different information from the same state. In other words it
   would require cooperation between the VM and a hostile external party (to,
   for example, ignore the fact that the VM has rolled back to an earlier
   point in the protocol so a repeat of a previous handshake message will be
   seen), or in other words control over the VM by an external party.  Anyone
   faced with this level of attack has bigger things to worry about than RNG
   state rollback */

Peter.

---

From: "Wei Dai" <[email-masked]>
Date: Thu, 11 Jan 2007 18:06:08 +0800

> detected, but with legitimate software it's not certain what the response

I think as a writer of cryptographic software, instead of checking whether 
your software is running inside a VM, the safe thing to do would be to 
assume that it is, and take appropriate defensive measures. But I'm curious, 
what does your software do differently if it detects that it's running in a 
VM?

> Is it really a problem?  My thinking about this (in the VM check) was:

Here's the simplest application I can imagine that would be affected by this 
problem: a chat program with messages authenticated by a MAC using a counter 
as the nonce. Say you're the user of such a program, and you roll back your 
VM because your system crashed. As soon as you type the next message (or 
maybe the next few messages depending on the details of the MAC algorithm) 
and send it out, an attacker could start impersonating you to the other 
party.

>   is about to be generated.

In some applications k may be pre-generated in order to precompute g^k mod 
p. As I mentioned earlier this practice would have to be abandoned.

Also, Hal Finney mentioned that generating random numbers after fixing the 
message may not be sufficient, if the RNG does not incorporate new entropy 
into its state after being rolled back and before responding to the next 
request.

---

From: "Wei Dai" <[email-masked]>
Date: Thu, 11 Jan 2007 18:24:25 +0800

Hal Finney wrote:
> this problem.

Hopefully OS vendors will cooperate with VM software writers to fix this 
problem. It should be relatively simple since the fix would be transparent 
to the application software (i.e. not require a new API).

In the mean time, a workaround at the application software level may be to 
always hash the current time into the random number returned by the OS. This 
type of solution may also be applicable to state-derived nonces, for example 
by reserving some bits in the nonce for a timestamp.

> Nonce duplication could be avoided by creating the nonce

This is also a good workaround in some situations, but using it for 
Wegman-Carter MACs would eliminate or significantly reduce their speed 
advantage.

---

From: Ariel Waissbein <[email-masked]>
Date: Thu, 11 Jan 2007 11:08:20 -0300

By the way, have you heard of Joanna Rutkowska's blue pill? Great work.

http://theinvisiblethings.blogspot.com/2006/06/introducing-blue-pill.html

Cheers,
Ariel

Wei Dai wrote:
> problem. It should be relatively simple since the fix would be 
> transparent to the application software (i.e. not require a new API).
> 
> In the mean time, a workaround at the application software level may be 
> to always hash the current time into the random number returned by the 
> OS. This type of solution may also be applicable to state-derived 
> nonces, for example by reserving some bits in the nonce for a timestamp.
>

---

From: Paul Hoffman <[email-masked]>
Date: Thu, 11 Jan 2007 15:52:44 -0800

At 6:06 PM +0800 1/11/07, Wei Dai wrote:
>I think as a writer of cryptographic software, instead of checking 
>whether your software is running inside a VM, the safe thing to do 
>would be to assume that it is, and take appropriate defensive 
>measures.

At 6:24 PM +0800 1/11/07, Wei Dai wrote:
>Hopefully OS vendors will cooperate with VM software writers to fix 
>this problem.

These two responses seem to be at opposition with each other.

I think it is quite safe to assume that even if OS vendors cooperate 
with VM software writers in the future, all or nearly all OSs today 
will have the problem of the randomness state being saved by VM 
snapshots.

--Paul Hoffman, Director
--VPN Consortium

---

From: [email-masked] (Peter Gutmann)
Date: Fri, 12 Jan 2007 16:01:49 +1300

>These two responses seem to be at opposition with each other.

They're not only at opposition with each other, they're both fundamentally
impractical.  For the first one, exactly what "defensive measures" are you
supposed to take?  Since your state can be rolled back at any time (and that
rolls back *everything*) and there's no way to detect this, what can you do
about the problem?  A better approach would be to do a threat analysis and try
and figure out exactly when this really is a threat.  For example in the code
comment I posted yesterday, it shouldn't be a problem for secure interaction
with remote systems because the remote system is holding some of your security
state, so if you experience rollback and replay an old message the session
will be shut down.

For the second one, it's highly unlikely that VM software writers will ever
want to "fix this problem".  The whole point of a VM is to make it as
undetectable to the host OS as possible (look at the lengths that malware
writers are going to to try and identify VMs), so I can't imagine that VM
vendors would deliberately make their software more obvious.

What we need first is a precise threat analysis.  What's vulunerable, under
what conditions, and how.  Only then can we start talking about
countermeasures.

Peter.

---

From: "Hal Finney" <[email-masked]>
Date: Thu, 11 Jan 2007 19:48:16 -0800

Many computers are shipping these days with TPM chips. Among other
things these chips can supply random numbers. They also have
non-volatile monotonic counters. TPM chips have certified keys
allowing authenticated channels to the chip, so that the software
could tell if it were talking to a virtualized TPM.

These seem to be pieces from which a solution could be put together,
if such a chip is available. There might be a substantial performance
penalty since current generation chips are located on a slow PC bus.
I've seen speculation that future CPU architectures may incorporate
TPM functionality.

Hal

---

From: "Wei Dai" <[email-masked]>
Date: Fri, 12 Jan 2007 11:58:01 +0800

> These two responses seem to be at opposition with each other.

They do, don't they? I suppose the point is that 20 years from now we 
shouldn't still be worrying that a call to an OS RNG might result in a 
previously used random number (or if we are, it will be for some other 
reason). Until then, consider my comments to be in support of defense in 
depth.

Phillip Rogaway wrote:
> Let me point you in this connection to
>
>   P. Rogaway and T. Shrimpton, Deterministic Authenticated Encryption:
>   A Provable-Security Treatment of the Key-Wrap Problem,
>   http://www.cs.ucdavis.edu/~rogaway/papers/keywrap.html, full version
>   of Eurocrypt 2006 paper.

Thanks, Phil. That's certainly a very relevant work that anticipated much of 
the discussion here. I can only suggest that it be standardized quickly and 
used for general authenticated encryption (not just key-wrap). I think we 
also need a public-key version of the SIV construction, or is there existing 
work in that area also?

---

From: "Wei Dai" <[email-masked]>
Date: Fri, 12 Jan 2007 13:10:18 +0800

Peter Gutmann wrote:
> For the first one, exactly what "defensive measures" are you
> about the problem?

This question is puzzling since several general suggestions about what to do 
have been posted in this discussion.

> A better approach would be to do a threat analysis and try

This analysis is just wrong. If there is an attacker sitting between you and 
the remote system, he can capture your messages after you experience a 
rollback and *not* send them to the remote system. (Note that in general 
these are not replayed messages, but different messages that reused old 
nonces.) Instead he uses them to forge new messages that appear valid to the 
remote system and send those instead.

> vendors would deliberately make their software more obvious.

It's fair to suppose that a VM might want to remain undetectable to the 
guest OS while running normally, but there's no reason not to send some kind 
of signal to the guest OS after a rollback, at least by default. A 
completely undetectable rollback would have to be a seperate option for 
anyway, since the hardware clock also needs to be rolled back in that case.

> what conditions, and how.  Only then can we start talking about

I think it's clear from the current discussion that there are good 
countermeasures that are relatively cheap and apply in a wide range of 
circumstances. Precise threat analysis is of course a good thing (and I 
asked crypto scheme designers to help with this in the earlier "consequences 
of nonce reuse" thread), but I don't see why we shouldn't be talking about 
general countermeasures as well.

---

From: Jon Callas <[email-masked]>
Date: Fri, 12 Jan 2007 11:36:32 -0800

Peter wrote some things that I was going to write. Long before I did  
any crypto, I was an OS and virtualization guy. The whole point of  
virtual system is that it looks like the real one.

Thus, in the abstract, if you can tell a virtual device from a real  
one, then that is an imperfection in the virtual system. Now, it may  
be an intentional imperfection. For example, if I query the ATA drive  
on my system it may say that its manufacturer is VMware, and this is  
a really big hint that I'm on a VM.

However, let's suppose that I replace a rack of servers with two  
physical machines all doing VMs. If SSL blows up on one of my VMs  
because it is imperfectly virtualized, I'll go talk to the VM maker  
and get them to make it sufficiently virtualized that I can do SSL on  
my VM. Or I redesign my system so that it doesn't need SSL.

I think we're looking at this the wrong way. This discussion presumes  
that VM rollbacks are bad things that we must prevent against. They  
might be, they can be. Some of them will be. But many of them won't  
be. A cryptosystem that prevents a VM from restarting simply won't be  
used on a VM. Some other cryptosystem will be used. However, if the  
way that it dodges the VM is merely that it relies on a TPM, then VMs  
-- both evil and good -- will virtualize the TPM.

In a truly virtualized world, it's like the notion of the Earth being  
carried on the back of a turtle. Where does the turtle stand? On  
another turtle. And it's turtles all the way down.

	Jon

---

From: Ariel Waissbein <[email-masked]>
Date: Fri, 12 Jan 2007 17:06:34 -0300

Hi all,

a good definition of requirements (and a VM that fulfills these) seems 
to be a good solution. Roughly speaking, one of the uses people are 
giving to VM wares is using them as web servers, and having many of 
these inside one "physical" system. I presume that in the following 
years people will start to use more and more this configuration (of many 
servers running in one system), and we need to make sure we take the 
necessary security precautions.

It isn't a requirement that an external user cannot tell a VM ware from 
a physical system. A first requirement is that a user (e.g., the 
attacker) that compromises the VM ware can go outside the VM ware and 
into the hosting physical system. Of course, there's more. Today we are 
using VMs that were constructed with other requirements.

Let's figure out what requirements are for using the servers as we 
already have them and if they are factible, or if we need to design new 
solutions that work in these VM-hosted servers.

Cheers,
Ariel

Jon Callas wrote:
> Peter wrote some things that I was going to write. Long before I did any 
> crypto, I was an OS and virtualization guy. The whole point of virtual 
> system is that it looks like the real one.
> 
> Thus, in the abstract, if you can tell a virtual device from a real one, 
> then that is an imperfection in the virtual system. Now, it may be an 
> intentional imperfection. For example, if I query the ATA drive on my 
> system it may say that its manufacturer is VMware, and this is a really 
> big hint that I'm on a VM.
> 
> because it is imperfectly virtualized, I'll go talk to the VM maker and 
> get them to make it sufficiently virtualized that I can do SSL on my VM. 
> Or I redesign my system so that it doesn't need SSL.
> 
> might be, they can be. Some of them will be. But many of them won't be. 
> A cryptosystem that prevents a VM from restarting simply won't be used 
> on a VM. Some other cryptosystem will be used. However, if the way that 
> it dodges the VM is merely that it relies on a TPM, then VMs -- both 
> evil and good -- will virtualize the TPM.
> 
> carried on the back of a turtle. Where does the turtle stand? On another 
> turtle. And it's turtles all the way down.
> 
>     Jon
> 
> 
>

---

From: "Hal Finney" <[email-masked]>
Date: Fri, 12 Jan 2007 14:28:44 -0800

Seems like there are two classes of threats here. The first is when
some software is trying to keep secrets from the user via obfuscation
and such, and he is intentionally running it in a VM in order to use
rollbacks and similar techniques to try to extract secrets. The second
is when the user is just trying to use some software safely, but in an
environment where rollbacks may occasionally occur due to crashes or
some other reason, and he wants to make sure he does not inadvertantly
reuse data in his crypto protocol that can render it insecure. For
example, encrypting two different messages with the same stream cipher
state, or as Wei said using some of the nonce based MACs that rely on
unique nonces.

Hal

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 30 Jan 2007 23:19:20 +1300

>have been posted in this discussion.

Several *theoretical* suggestions have been posted.  I haven't really seen
anything that'll work in practice.  For example I can't see VM vendors
changing the way their VMs work just to satisfy some (relatively) obscure
security concerns that have close to zero impact on their business models.

>I don't see why we shouldn't be talking about general countermeasures as
>well.

While talking about general countermeasures is interesting, at some point you
have to start talking about practical countermeasures.  "Persuading the world
to change to suit our requirements" doesn't seem like a very practical
countermeasure.  More specifically, I'm not aware of anything that I can put
into my code tomorrow to fix this problem, and I don't even know what specific
problem I'm supposed to be fixing.

Peter.