Wei Dai wrote:
>
> 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.


(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


_______________________________________________
Cfrg mailing list
Cfrg@ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg