Subject: Re: [Cfrg] how to guard against VM rollbacks

From: David McGrew <[email-masked]>
Date: Wed, 2 May 2007 05:35:07 -0700

Hi Wei,

thanks for providing the followup information on VM rollbacks.

I agree that IV-reuse tolerant algorithms are interesting and seem  
worth pursuing.  For that matter, it is interesting that most of the  
MAC proposals that are based on universal hashing use an IV.  A MAC  
that had the same interface as HMAC, and thus could act as a drop-in  
replacement, would be better.  (One recent place where this need  
became apparent was in the standards effort to provide a strong MAC  
within a TCP option, that is, draft-bonica-tcp-auth-06.txt and  
related work.  There are lots of other places too, I bet.)

It would be valuable to write up an analysis of the rollback attacks  
and how they can be mitigated.   It would no doubt recommend such  
good practices as the use of true random sources wherever they are  
available, which is a good thing.  It would be interesting to see  
what algorithms and protocols are robust against a rollback - perhaps  
protocols with more than one participant contributing to key  
generation are stronger against this attack.  DSA is insecure if its  
random source is bad (at least if distinct messages get signed),  
while protocols that rely on a trusted third party to generate keys  
will still be OK.  So in this scenario some of the conventional  
wisdom about good practice doesn't apply.   Also, the rollback attack  
assumes a very powerful adversary, and it would be good to lay out  
exactly what the threats are.   (Here I'm thinking of the obvious  
question: under what conditions can an attacker cause a VM rollback,  
but not directly access secret/private keys or plaintext?)  So I  
think it would be great for the CFRG to sponsor an internet draft in  
this area, if you have the time and interest to contribute.

I also think that work on algorithms or protocols that are tolerant  
of IV reuse is potentially valuable.  I think it would be good to  
discuss where such things could best fit into practice.   There seems  
to be a tension between resistance to IV reuse and efficiency in  
hardware (due to the inability to pipeline, as with wide-block modes  
of operation).  This fact suggests to me that IV-reuse tolerant  
algorithms are best suited for use in control-plane situations like  
key management.

It seems that several people are interested in SIV and its security  
goals.  If people are interested, we could convene a CFRG meeting at  
the IETF venue in Chicago in July and invite Tom and Phil to make a  
presentation to us.

David

On Apr 28, 2007, at 11:13 PM, Wei Dai wrote:

> I have been trying to implement the previously suggested defenses  
> against VM rollbacks, and have some additional information about  
> the problem. It appears that hashing the current time into an OS- 
> generated random number is not sufficient to eliminate the  
> possibility that random numbers will be reused. This is because  
> time can also be virtualized, and rolled back along with memory.  
> For example, according to [1], VMware virtualizes all hardware and  
> software clocks on a virtual machine, except for the CMOS real time  
> clock (also known as RTC or time of day or TOD). Unfortunately, the  
> CMOS RTC is typically not accessible from a program running with  
> normal privileges. And even if the RTC is accessible, its  
> granularity only one second, which means random numbers can still  
> be reused if a VM snapshot is cloned and then both clones are  
> restarted at nearly the same time.
>
> VMware does provide a way to automatically resynchronize the time  
> of the virtual machine after a rollback, by installing a daemon/ 
> service on the guest operating system. However there doesn't seem  
> to be a reason to suppose that after rollback, the daemon/service  
> will be scheduled to run immediately by the guest OS, so  
> resynchronization may not occur for some time.
>
> It seems that fixing this problem at the RNG level is not as easy  
> as I thought, and requires active cooperation between the RNG and  
> the VM software. That may not be feasible in many situations, so  
> there appears to be an urgent need for the design and  
> standardization of crypto schemes that are tolerant of reuse of  
> random numbers, like the SIV mode of operation [2].
>
> [1] http://www.vmware.com/pdf/vmware_timekeeping.pdf
> [2] http://www.cs.ucdavis.edu/~rogaway/papers/keywrap.html
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg