[Cryptography] A simple RNG reseeding tweak to prevent malicious but passive sources from introducing bias

[Natanael]

There's some literature on various CSPRNG designs and malicious sources,
covering the different possible capabilities they may have.

One of these attack models involves a hypothetical malicious CSPRNG source
for seeding / reseeding the entropy pool, where the source would have total
visibility into the system but would not tamper with it in any other way
but a single one, in that it would feed the CSPRNG with maliciously
generated "degenerate" seed values.

This would be done in an attempt to attack the mixing function in the RNG,
attempting to induce bias which could break things like ECDSA signing via a
predictable k value. Hypothetically, a modified Intel RDRAND chip or
similar could perform an attack like this while attempting to stay covert
and not take actions that might lead to visibly altered state in computer.

To generate this bias in the output, the mixing function would be attacked
by this source by iterating through candidate inputs and testing them to
find one which produces an output from the CSPRNG with the desired bias
(when combined with the other sources' inputs, which here is known).

(Depending on the mixing function, the limits to bias introduction can have
a computational limit similar to proof-of-work functions, but the adversary
might still be able to achieve their goal under this constraint.)

In a distributed network where each source is an independent computer you
can easily perform distributed entropy generation by using commitments of
the inputs while they're still secret, but you can't use that against a
malicious chip inside your own computer as it would already know all inputs.

However, we can introduce another recent development, by using a VDF -
verifiable delay functions, a type of function similar to timelock puzzles
where the output takes a certain minimum amount of time to solve for.

So instead of using classical hash function commitments, the input value to
feed into the CSPRNG becomes the output of the VDF:s derived from each
source's generated seed (note, using a type of VDF where even the generator
don't know what the output will be in advance).

We can then make the CSPRNG sample inputs from each source on a schedule
(using short contribution time windows) and creating a VDF based on the
inputs, and then using the final output of the VDF to reseed the CSPRNG
state.

Let's say the sources collects entropy for 10 minutes and contributions to
the system CSPRNG are then immediately afterwards open for 1 minute, then
you can generate a 20 minute VDF to then start the solving process. This
way the malicious source can not have determined what the final output from
any other source will have been at the point in time when it is forced to
submit its own contribution.

Thus it is not possible for a malicious RNG source which refrains from
otherwise tampering with the system to introduce bias in the final output
of the CSPRNG.

-----

Any feedback?

In particular, what would this look like when integrated into an existing
CSPRNG design such as Fortuna? Or any suggestions for simplification?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20201030/4bacd3b9/attachment.htm>