[Cryptography] True RNG: elementary particle noise sensed with surprisingly simple electronics

[Ray Dillinger]

On 09/17/2016 10:03 AM, Thierry Moreau wrote:
> On 16/09/16 09:29 PM, Ray Dillinger wrote:

>> Let the philosophers debate a definition of "randomness."

> A definition of randomness is needed in the discipline of mathematics if
> some theoretical arguments about randomness extractors is part of the
> justification for trust in the whole scheme.

> The more demanding expectations may not be fulfilled by hardware alone.

Doubtless.  That is absolutely true.  But one can formulate an
expectation sufficiently demanding that it won't be met by anything.
Would that expectation help you keep a system safe?

My expectation is for "some" unpredictable output from a device that can
be visually inspected to assure that it contains nothing other than
the components and functionality that it is supposed to contain.  That
would help with my relentlessly practical security needs.

> I offered Sebastian a self-contained digital device with a simple serial
> port outputting unpredictable bits, totally incompressible. The device
> implements a CPRNG with a fixed seed, stored in EEPROM memory when the
> device is manufactured (the vendor would not reveal the seal except as
> ordered by a legal subpoena). When Sebastian listened to my explanation,
> he started to worry about a definition of randomness.

Ah.  Now I understand.  That device was not "biased" - it was in fact
deterministic.  He may express it using words that make you think he's
worried about a definition of randomness, but the security concern is
with a definition of trustworthiness.

Firstly there is the matter of the fixed seed.  The information about
the seed state was known to someone other than the current owner at the
time the device was manufactured, and that information can be used to
predict or reconstruct the device's whole output.  There is no such
thing as evidence that information once known to someone has not been
retained, or that it has not been sold to mobsters, crooks, and crackers.

Second, if a CPRNG-based device comes up in the same state each time
it's powered on, it will repeat the same sequence of output bits - and
that's also untrustworthy because it's trivially predictable if you've
seen it before, or trivially reconstructable if you're seeing it later.
Anyone who has possessed the device previously (including the
fabricator, shipper, manufacturer, wholesaler, retailer, somebody who
broke into a warehouse to make a substitution during storage or
shipment, etc) or gets hold of the device in the future (including
burglars, heirs, randoms who got it accidentally at an estate sale,
creditors who seize assets at a site, lawyers with subpeonas, etc) can
discover the output being used by the current owner.

Avoiding that obvious mistake increases the complexity (and degrades the
inspectability) of the device.

Third, if a malicious actor 'tweaks' the code for the CPRNG that gets
baked into the device and substitutes one s/he can easily analyze or
predict, that's equally dire, can't be revealed by visual inspection,
and has already happened several times so people now EXPECT it and want
direct evidence (manifest trustworthiness, visually inspectable
hardware, etc) that that is not what you're doing.

Finally, even if those aren't problems, there's a worry that the CPRNG
algorithm will get stale and eventually rot.  Had you implemented a
deterministic generator based on, say, Arc4, 10 years past, it would
have seemed "random" at the time - but someone equipped with modern
mathematical knowledge could analyze its output, detect that it was
Arc4, and start reverse-engineering its state.  Eventually, having seen
enough output and applied enough computing cycles, one could, in theory,
predict every output that would ever be made by the device from that
point on. And somebody could make a discovery next week that reduces the
amount of output needed or the number of computing cycles required to
process it.

Trustworthiness is a legitimate concern.  The output of a CPRNG-based
device mustn't be used directly, for any high-value keys or other
sensitive material.

I would be happy to feed such output into dev/random to be mixed with
everything else, but: first, it would do nothing that I can't do in
software so why am I buying the device? Second, it would be incorrect to
make the ioctl() call that said dev/random was entitled to produce
output based on no *other* bits so my system wouldn't get new
capabilities that satisfy a need for a given rate of dev/random bits.
Third, dev/urandom already implements such a CPRNG.

>> To me the value of your idea is that here is a way to build something
>> that is visibly trustworthy because it's made of simple components and
>> can be built in a way that every component and circuit trace can be seen
>> from outside the device.

> I would add that once the wheatstone resistor bridge schematic is
> accepted as a reliable way to sense resistor current noise as a
> controlled "physics experiment," it should be reasonable to assess some
> entropy quantification which might then allow a link to entropy
> extractor theoretical work.

Work which I shall read with interest, but which I have no expectation
will require any change in my behavior regarding relentlessly practical
security concerns.  Given the choice between someone trying to sneak a
gimmicked, non-inspectable RNG into use, and someone making a huge
mathematical breathrough of equally dire import?  The gimmicked RNG is
billions of times more likely (and here "billions" is likely a
misspelling of a far larger number).  In fact it has already happened
several times.

It's especially dire if the output of the gimmicked RNG is given
privilege to bypass the mixing step in dev/random and get used directly
as keys etc, which is why there is ABSOLUTELY NOTHING to do with the
output of any such device, under any circumstances, other than feeding
it to dev/random.

If you try to do anything else with it or make its output privileged in
any way, alarm bells will go off.  Suspicious bastards like me, with
relentlessly practical security concerns, will think, "Hey, that's the
way they were telling us to use Dual-EC-DRBG!  And the way Intel wants
us to use that stupid chip instruction from the mask we can't inspect!
Somebody's cheating again!"

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160917/c7520707/attachment.sig>