Re: is "premature next" a real world rng concern, or just an academic exercise?

[Yevgeniy Dodis <dodis@cs.nyu.edu>]

resending in plain text... (hope got it right)

On Mon, May 9, 2022 at 11:15 AM Yevgeniy Dodis <dodis@cs.nyu.edu> wrote:
>
> Hi Jason and all.
>
> Thank you for starting this fascinating discussion. I generally agree with everything Jason said. In particular, I am not
> 100% convinced that the extra cost of the premature next defense is justified.(Although Windows and MacOS are adamant it is
> worth it :).)
>
> But let me give some meta points to at least convince you this is not as obvious as Jason makes it sound.
>
> 1) Attacking RNGs in any model is really hard. Heck, everybody knew for years that /dev/random is a mess
> (and we published it formally in 2013, although this was folklore knowledge),  but in all these years nobody
> (even Nadya's group :)) managed to find a practical attack. So just because the attack seems far-fetched, I do not think we should
> lower our standards and do ugly stuff. Otherwise, just leave /dev/random the way it was before Jason started his awesome work.
>
> 2) As Jason says, there are two distinct attack vectors needed to make the premature next attack.
> A) compromising the state
> B) (nearly) continuously observing RNG outputs
>
> I agree with Jason's point that finding places where
> -- A)+B) is possible, but
> --- A)+A) is not possible,
> is tricky. Although Nadya kind of indicated a place like that. VM1 and VM2 start with the same RNG state (for whatever
> reason). VM1 is insecure, so can leak the state via A). VM2 is more secure, but obviously allows for B) through system
> interface. This does not seem so hypothetical for me, especially in light of my mega-point 1) above -- almost any real-world
> RNG attack is hard.
>
> But I want to look at it from a different angle here. Let's ask if RNGs should be secure against A) or B) individually.
>
> I think everybody agrees protection from B) is a must. This is the most basic definition of RNG! So let's just take itas
> an axiom.
>
> Protection against A) is trickier. But my read of Jason's email is that all his criticism comes exactly from this point.
> If your system allows for state compromise, you have bigger problems than the premature next, etc. But let's ask ourselves
> the question. Are we ready to design RNGs without recovery from state compromise? I believe nobody on this list would
> be comfortable saying "yes". Because this would mean we don;t need to accumulate entropy beyond system start-up.
> Once we reach the point of good initial state, and state compromise is not an issue, just use straight ChaCha or whatever other
> stream cipher.
>
> The point is, despite all arguments Jason puts, we all would feel extremely uncomfortable/uneasy to let continuous
> entropy accumulation go, right?
>
> This means we all hopefully agree that we need protection against A) and B) individually.
>
> 3) Now comes the question. If we want to design a sound RNG using tools of modern cryptography, and we allow
> the attacker an individual capability to enforce A) or B) individually, are we comfortable with the design where we:
> * offer protection against A)
> * offer protection against B)
> * do NOT offer protection against A)+B), because we think it's too expensive given A)+B) is so rare?
>
> I do not have a convincing answer to this question, but it is at least not obvious to me. On a good note, one worry
> we might have is how to even have a definition protecting A), protecting B), but not protecting A)+B).
> Fortunately, our papers resolve this question (although there are still theoretical annoyances which I do not
> want to get into in this email). So, at least from this perspective, we are good. We have a definition with
> exactly these (suboptimal) properties.
>
> Anyway, these are my 2c.
> Thoughts?
>
> Yevgeniy
>
> On Sun, May 1, 2022 at 7:17 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote:
>>
>> Hi Ted,
>>
>> That's a useful analysis; thanks for that.
>>
>> On Sat, Apr 30, 2022 at 05:49:55PM -0700, tytso wrote:
>> > On Wed, Apr 27, 2022 at 03:58:51PM +0200, Jason A. Donenfeld wrote:
>> > >
>> > > 3) More broadly speaking, what kernel infoleak is actually acceptable to
>> > >    the degree that anybody would feel okay in the first place about the
>> > >    system continuing to run after it's been compromised?
>> >
>> > A one-time kernel infoleak where this might seem most likely is one
>> > where memory is read while the system is suspended/hibernated, or if
>> > you have a VM which is frozen and then replicated.  A related version
>> > is one where a VM is getting migrated from one host to another, and
>> > the attacker is able to grab the system memory from the source "host"
>> > after the VM is migrated to the destination "host".
>>
>> You've identified ~two places where compromises happen, but it's not an
>> attack that can just be repeated simply by re-running `./sploit > state`.
>>
>> 1) Virtual machines:
>>
>> It seems like after a VM state compromise during migration, or during
>> snapshotting, the name of the game is getting entropy into the RNG in a
>> usable way _as soon as possible_, and not delaying that. This is
>> Nadia's point. There's some inherent tension between waiting some amount
>> of time to use all available entropy -- the premature next requirement
>> -- and using everything you can as fast as you can because your output
>> stream is compromised/duplicated and that's very bad and should be
>> mitigated ASAP at any expense.
>>
>> [I'm also CC'ing Tom Risenpart, who's been following this thread, as he
>>  did some work regarding VM snapshots and compromise, and what RNG
>>  recovery in that context looks like, and arrived at pretty similar
>>  points.]
>>
>> You mentioned virtio-rng as a mitigation for this. That works, but only
>> if the data read from it are actually used rather quickly. So probably
>> /waiting/ to use that is suboptimal.
>>
>> One of the things added for 5.18 is this new "vmgenid" driver, which
>> responds to fork/snapshot notifications from hypervisors, so that VMs
>> can do something _immediately_ upon resumption/migration/etc. That's
>> probably the best general solution to that problem.
>>
>> Though vmgenid is supported by QEMU, VMware, Hyper-V, and hopefully soon
>> Firecracker, there'll still be people that don't have it for one reason
>> or another (and it has to be enabled manually in QEMU with `-device
>> vmgenid,guid=auto`; perhaps I should send a patch adding that to some
>> default machine types). Maybe that's their problem, but I take as your
>> point that we can still try to be less bad than otherwise by using more
>> entropy more often, and not delaying as the premature next model
>> requirements would have us do.
>>
>> 2) Suspend / hibernation:
>>
>> This is kind of the same situation as virtual machines, but the
>> particulars are a little bit different:
>>
>>   - There's no hypervisor giving us new seed material on resumption like
>>     we have with VM snapshots and vmgenid; but
>>
>>   - We also always know when it happens, because it's not transparent to
>>     the OS, so at least we can attempt to do something immediately like
>>     we do with the vmgenid driver.
>>
>> Fortunately, most systems that are doing suspend or hibernation these
>> days also have a RDRAND-like thing. It seems like it'd be a good idea
>> for me to add a PM notifier, mix into the pool both
>> ktime_get_boottime_ns() and ktime_get(), in addition to whatever type
>> info I get from the notifier block (suspend vs hibernate vs whatever
>> else) to account for the amount of time in the sleeping state, and then
>> immediately reseed the crng, which will pull in a bunch of
>> RDSEED/RDRAND/RDTSC values. This way on resumption, the system is always
>> in a good place.
>>
>> I did this years ago in WireGuard -- clearing key material before
>> suspend -- and there are some details around autosuspend (see
>> wg_pm_notification() in drivers/net/wireguard/device.c), but it's not
>> that hard to get right, so I'll give it a stab and send a patch.
>>
>> > But if the attacker can actually obtain internal state from one
>> > reconstituted VM, and use that to attack another reconstituted VM, and
>> > the attacker also knows what the nonce or time seed that was used so
>> > that different reconstituted VMs will have unique CRNG streams, this
>> > might be a place where the "premature next" attack might come into
>> > play.
>>
>> This is the place where it matters, I guess. It's also where the
>> tradeoff's from Nadia's argument come into play. System state gets
>> compromised during VM migration / hibernation. It comes back online and
>> starts doling out compromised random numbers. Worst case scenario is
>> there's no RDRAND or vmgenid or virtio-rng, and we've just got the good
>> old interrupt handler mangling cycle counters. Choices: A) recover from
>> the compromise /slowly/ in order to mitigate premature next, or B)
>> recover from the compromise /quickly/ in order to prevent things like
>> nonce reuse.
>>
>> What is more likely? That an attacker who compromised this state at one
>> point in time doesn't have the means to do it again elsewhere in the
>> pipeline, will use a high bandwidth /dev/urandom output stream to mount
>> a premature next attack, and is going after a high value target that
>> inexplicably doesn't have RDRAND/vmgenid/virtio-rng enabled? Or that
>> Nadia's group (or that large building in Utah) will get an Internet tap
>> and simply start looking for repeated nonces to break?
>>
>> Jason