On 2016-04-28 3:49 AM, Watson Ladd wrote:
If only there was an asymptotically good design that didn't require
any estimation at all. See
https://www.schneier.com/cryptography/fortuna/ for details.
The money shot is:
"At first, it might appear that the only way to prevent this attack is
by discovering a sound way to estimate the current entropy in the state
and to use this estimate to block the premature next calls. This is
essentially the approach taken by Linux’s /dev/random and many other
RNGs with input. Unfortunately, sound entropy estimation is hard or even
infeasible [SV03, FS03] (e.g., [DPR+13] showed simple ways to
completely fool Linux’s entropy estimator). This seems to suggest that
the modeling of RNGs with input should consider each premature next call
as a full state compromise, and this is the highly conservative
approach taken by [DPR+13] (which we will fix in this work). Fortuna.
Fortunately, the conclusion above is overly pessimistic. In fact, the
solution idea already comes from two very popular RNGs mentioned above,
whose designs were heavily affected by the desire to overcome the
premature next problem: Yarrow (designed by Schneier, Kelsey and
Ferguson [KSF99] and used by MacOS/iOS/FreeBSD), and its refinement
Fortuna (subsequently designed by Ferguson and Schneier [FS03]
and used by Windows [Fer13]). The simple but brilliant idea of these
works is to partition the incoming entropy into multiple entropy “pools”
and then to cleverly use these pools at vastly different rates when
producing outputs, in order to guarantee that at least one pool will
eventually accumulate enough entropy to guarantee security before it is
“prematurely emptied” by a next call."
Which however still means that calls to produce valuable keys shortly
after boot are going to fail.
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography