Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-09 Thread David Johnston

On 9/8/2013 4:27 AM, Eugen Leitl wrote:

- Forwarded message from James A. Donald jam...@echeque.com -

Date: Sun, 08 Sep 2013 08:34:53 +1000
From: James A. Donald jam...@echeque.com
To: cryptogra...@randombit.net
Subject: Re: [cryptography] Random number generation influenced, HW RNG
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130801 
Thunderbird/17.0.8
Reply-To: jam...@echeque.com

On 2013-09-08 3:48 AM, David Johnston wrote:

Claiming the NSA colluded with intel to backdoor RdRand is also to
accuse me personally of having colluded with the NSA in producing a
subverted design. I did not.

Well, since you personally did this, would you care to explain the
very strange design decision to whiten the numbers on chip, and not
provide direct access to the raw unwhitened output.
#1 So that that state remains secret from things trying to discern that 
state for purposes of predicting past or future outputs of the DRBG.


#2 So that one thread cannot undermine a second thread by putting the 
DRNG into a broken mode. There is only one DRNG, not one per core or one 
per thread. Having one DRNG per thread would be one of the many 
preconditions necessary before this could be contemplated.


#3 Any method of access is going have to be documented and supported and 
maintained as a constant interface across many generations of chip. We 
don't throw that sort of thing into the PC architecture without a good 
reason.


 #4 Obviously there are debug modes to access raw entropy source 
output. The privilege required to access those modes is the same debug 
access necessary to undermine the security of the system. This only 
happens in very controlled circumstances.




A decision that even assuming the utmost virtue on the part of the
designers, leaves open the possibility of malfunctions going
undetected.

That's what BIST is for. It's a FIPS and SP800-90 requirement.


That is a question a great many people have asked, and we have not
received any answers.

Yes they have. I've answered this same question multiple times.


Access to the raw output would have made it possible to determine that
the random numbers were in fact generated by the physical process
described, since it is hard and would cost a lot of silicon to
simulate the various subtle offwhite characteristics of a well
described actual physical process.
Access to the raw output would have been a massive can of worms. The 
statistical properties of the entropy source are easy to model and easy 
to test online in hardware. They are described in the CRI paper if you 
want to read them. That's a necessary part of a good entropy source. If 
you can't build an effective online test in hardware then the entropy 
source is not fit for purpose.


DJ



___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-09 Thread James A. Donald

 would you care to explain the very strange design decision
 to whiten the numbers on chip, and not provide direct
 access to the raw unwhitened output.

On 2013-09-09 2:40 PM, David Johnston wrote:
 #1 So that that state remains secret from things trying to
 discern that state for purposes of predicting past or
 future outputs of the DRBG.

This assumes the DRGB is on chip, which it should not be.  It
should be in sofware.  Your argument is circular.  You are
arguing that the DRGB should be on chip, because it is on
chip, that is has some of its menacing characteristics
because it has other menacing characteristics.

 #2 So that one thread cannot undermine a second thread by
 putting the DRNG into a broken mode. There is only one
 DRNG, not one per core or one per thread. Having one DRNG
 per thread would be one of the many preconditions necessary
 before this could be contemplated.

You repeat yourself.  Same circular argument repeated.

 #3 Any method of access is going have to be documented and
 supported and maintained as a constant interface across
 many generations of chip.

Why then throw in RDSEED?

You are already adding RDSEED to RDRAND, which which fails to
address any of the complaints.  Why provide a DRNG in the
first place.

Answer:  It is a NIST design, not an Intel design.  Your design
documents reference NIST specifications. And we
already know that NIST designs are done with hostile intent.


___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-09 Thread Owen Shepherd
 -Original Message-
 From: cryptography-bounces+owen.shepherd=e43...@metzdowd.com
 [mailto:cryptography-bounces+owen.shepherd=e43...@metzdowd.com]
 On Behalf Of David Johnston
 Sent: 09 September 2013 05:41
 To: cryptography@metzdowd.com
 Subject: Re: [Cryptography] [cryptography] Random number generation
 influenced, HW RNG
 
 #1 So that that state remains secret from things trying to discern that
state
 for purposes of predicting past or future outputs of the DRBG.
 
 #2 So that one thread cannot undermine a second thread by putting the
 DRNG into a broken mode. There is only one DRNG, not one per core or one
 per thread. Having one DRNG per thread would be one of the many
 preconditions necessary before this could be contemplated.
 
 #3 Any method of access is going have to be documented and supported and
 maintained as a constant interface across many generations of chip. We
don't
 throw that sort of thing into the PC architecture without a good reason.
 
   #4 Obviously there are debug modes to access raw entropy source output.
 The privilege required to access those modes is the same debug access
 necessary to undermine the security of the system. This only happens in
very
 controlled circumstances.

There are lots of aspects of IA-32/AMD64 which aren't consistent across
generations. The power management interface, for example, tends to get
somewhat infrequent backwards incompatible tweaks.

Fundamentally, I don't think anybody would have complained if you provided
some potentially non-stable method of /reading/ the RNG state; for example,
a bunch of MSRs (Hell, the potential instability is there in the name:
_Model_specific_, as much as a misnomer that is for the majority of stuff
dumped into an MSR) which could read the state wouldn't be out of the
question.

Plus, there it is: the required security protections. The only pieces of
software which can read MSRs are the kernel and SMM. If either of those is
compromised, well, you're boned anyway.

Some way of reading the raw RNG output, and establishing that things are
working as they should? That would give a lot of confidence

Also, you could have made rdrand set CF or similar if its state could be
predictable due to a recent read of the DRNG's state or similar.

-BEGIN PGP MESSAGE-
Version: GnuPG v2.0.21 (MingW32)

owGdVmtsFUUULigNVPABEX9o6BASHuH2UmgxUhEo1FLQUmyJDTakzt2dvTvt7sw6
M9vLQqI/JCBqVHzEGAMGI4I/MCUiCSgGCUHxQWLA1MYYqII2waAmJCoS4jmz996W
+M8mt72zO3POd77vO2f60qSbKsaOefu9fQemPju2MObLS7mK9ppvDy4hNfjTpnie
CxqQVqY1zTP7cFLVEtKsZNhAHJVERuYVjfykJidj4TA9VxaYyGqfRT5T7gOsvi7L
4mUhM5tcWXCzjgzxfFdIeWBkw/+LsAFDtAmynPk08EibR5poH3fJaukLbaTA1x1M
mAZSuwi+RIaFOabIgtr5daR2YUP9fNywTt5YwH8wdsS5HuZAkHbWQLpWjNq6gXQ5
NyzbqXBlSERs8+SZYIoangLhwgtiBoW5GdLSSdrXrMSn+Jkxn3RIYnxq0l/aUMOI
YsCN0EQzRzFDPGAaXnOR18SoBP4SI4nLtcOUGHUOA3pSkShWkdRME+mRSDGXOwbP
RFQbAq+92MSKERmbKDZ2k/EZaWpfvjJbhrWgDEsKBl8Uoy5xqBDSkFi4TIUcnlNE
KIVb2pBLILexySAkBmqCWqF8gEtJTsleJkgoXZYl60BYRjikF0Fik+DWDMEEuIqA
REciTIVrjIWP0kRZ0gJiQ5bSuVHvSEHGAUBh9mWxuJCKxIZQFi9HYTQRzEFPqwR2
e5gLONaQtXgedoJrogCYdUeYqSONIiFgFF+6GJ46GAQryUuE5NM+hvJAAFc6cQge
ZC4BcxAdR5FUxRXGQpENfPCJBoIgIegoDBLGlEcdYNhREqIj/lGesqI5Po+ypBPT
iFkG4wEBslD0AyRKi0dMVgDkYe0KQhUcNGBq9ECBQxmxgdx5CeUAf1qKcq2EzKgn
bbk+LmMNIhkrGYWPy3Jx3gqpsdQiBYoWCFSrZJRA/lg5JY/ZgCA40M/7eMDy6PAn
Yg7WHHUckGhWDMq1hatpWEqWbsJAI6rB2REv2v3MiRU3SUl2nWhQEM1WMppPo4gB
f1yQPqasJ1BmJYMAwDhcgWKoAaQA1JOq1pVrDmTaK1RHQJ79uqqxpm7BvMbWpnvr
ScHnjo8bQQsrJIfUIGVRwFHaZVMqYMIp1BVGKnpkRPOM7WG2kYL1YAFRXMtynqGs
ISugvjBRkEI8mKNOb4EqF4uCsRVBllwAfBQY7U2LaAaWKCahQZBkyKrUMdYbveDF
JCfdpNg21r0YJUh9yT2SyBiEkzBcYY0AADuWxjEa9KuoAcIw40hPzMNGBOPNsypg
f9r5dP+NlcFEgGHv44HWjnZNZrewIMjYI+UMUBNG5wGqmroCx4awuwQU1UC6W8Ey
QTfKwj3udGewmcIY1cCmCrkWAFqlfQEhEEM6E3pkySzaxJ5H3DiMsGY7rgSCmlPU
NZ0JdrxYX9kpbRlDInPW6CXTgSoahbbUrw1inSmhxvQNdk/Z/mXHAsPYlCMGsXaN
OJrdIpSeKaAPi4AAn4VjmaMq9X8v3AcssMOmo7U1S1Z5hHFMnmLD/rIDLoRswAte
RwXLOWg8C2LkpJ1Fx7pEUqCJLaADBYcFRiiqmlYAzY7Cph2esTmZNQLXfrqJmtKl
ZXFL1YvPqRURJoSP9C2FWmFfar4878M7JZCWS2giDzwHrYg4GgMtLc6iFtaoIXUB
iavsdIX2WNGM14XmIQ+oQu9yaNRUrPJUL16I1rFubEc1hcocbCXLaPk+XLNyVun0
SNTs9jH33FwxZmxF5bix+F9SRdWE20v/Ou0+PL7i/ZOTf95ywq/8dPquc+7J8eS2
2XOeOjv+m+P9H4fjxu+bPnB64mtXZz4UdN+yZ8+EaYsvH9/xxw8HZjbWnh4+++af
Xy3+5Vpbzc7HTq3Yf5Rt7x88NrRxOB545sUH5645P/HHt+oHn26a3H/qRM+lqfcN
DW9rca/c+vqVV/euv2tz8+r+i3d3fLA3f/3cjsyj7kdDnw0f2PTqw69UVcYv7Ny9
6uSZlw9OGxg+NHT5i8WP7CDLtv302+bjucd7sjOGf/9rad8RTx6tvtpZOfBG9a+r
71x/eP+FubP52U/OLNxy8cPTU7YOdn7+XfU/7/QPbv363BHxnDr6/CE+ZfK7xy7d
sfX4ovOZ609e+/v75Xurdw1VtfIL1f8C
=YDgw
-END PGP MESSAGE-

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-08 Thread John Kelsey
There are basically two ways your RNG can be cooked:

a.  It generates predictable values.  Any good cryptographic PRNG will do this 
if seeded by an attacker.  Any crypto PRNG seeded with too little entropy can 
also do this.  

b.  It leaks its internal state in its output in some encrypted way.  Basically 
any cryptographic processing of the PRNG output is likely to clobber this. 

The only fix for (a) is to get enough entropy in your PRNG before generating 
outputs.  I suspect Intel's RNG and most other hardware RNGs are extremely 
likely to be better than any other source of entropy you can get on your 
computer, but you don't have to trust them 100%.  Instead, do whatever OS level 
collection you can, combine that with 256 bits from the Intel RNG, and throw in 
anything else likely to help--ethernet address, IP address, timestamp, anything 
you can get from the local network, etc.  Hash that all and feed it into a 
strong cryptographic PRNG--something like CTR-DRBG or HMAC-DRBG from SP 800-90. 
 If you do that, you will have guarded against both (a) and (b).  

--John

___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-08 Thread Eugen Leitl
- Forwarded message from James A. Donald jam...@echeque.com -

Date: Sun, 08 Sep 2013 08:34:53 +1000
From: James A. Donald jam...@echeque.com
To: cryptogra...@randombit.net
Subject: Re: [cryptography] Random number generation influenced, HW RNG
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:17.0) Gecko/20130801 
Thunderbird/17.0.8
Reply-To: jam...@echeque.com

On 2013-09-08 3:48 AM, David Johnston wrote:
 Claiming the NSA colluded with intel to backdoor RdRand is also to
 accuse me personally of having colluded with the NSA in producing a
 subverted design. I did not.

Well, since you personally did this, would you care to explain the
very strange design decision to whiten the numbers on chip, and not
provide direct access to the raw unwhitened output.

A decision that even assuming the utmost virtue on the part of the
designers, leaves open the possibility of malfunctions going
undetected.

That is a question a great many people have asked, and we have not
received any answers.

Access to the raw output would have made it possible to determine that
the random numbers were in fact generated by the physical process
described, since it is hard and would cost a lot of silicon to
simulate the various subtle offwhite characteristics of a well
described actual physical process.


___
cryptography mailing list
cryptogra...@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography

- End forwarded message -
-- 
Eugen* Leitl a href=http://leitl.org;leitl/a http://leitl.org
__
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-08 Thread Ray Dillinger

On 09/08/2013 04:27 AM, Eugen Leitl wrote:


On 2013-09-08 3:48 AM, David Johnston wrote:

Claiming the NSA colluded with intel to backdoor RdRand is also to
accuse me personally of having colluded with the NSA in producing a
subverted design. I did not.



Well, since you personally did this, would you care to explain the
very strange design decision to whiten the numbers on chip, and not
provide direct access to the raw unwhitened output.


Y'know what?  Nobody has to accuse anyone of anything.  The result,
no matter how it came about, is that we have a chip whose output
cannot be checked.  That isn't as good as a chip whose output can
be checked.

A well-described physical process does in fact usually have some
off-white characteristics (bias, normal distribution, etc). Being
able to see those characteristics means being able to verify that
the process is as described.  Being able to see also the whitened
output means being able to verify that the whitening is working
correctly.

OTOH, it's going to be more expensive due to the additional pins of
output required, or not as good because whitening will have to be
provided in separate hardware.

Ray
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-08 Thread Jon Callas
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1


On Sep 7, 2013, at 8:06 PM, John Kelsey crypto@gmail.com wrote:

 There are basically two ways your RNG can be cooked:
 
 a.  It generates predictable values.  Any good cryptographic PRNG will do 
 this if seeded by an attacker.  Any crypto PRNG seeded with too little 
 entropy can also do this.  
 
 b.  It leaks its internal state in its output in some encrypted way.  
 Basically any cryptographic processing of the PRNG output is likely to 
 clobber this. 

There's also another way -- that it's a constant PRNG.

For example, take a good crypto PRNG, seed it in manufacturing, and then in its 
life, it just outputs from that fixed state. That fixed state might be secret 
or known to outsiders, but either way, it's a cooked PRNG.

Sadly, there were (are?) some hardware PRNGs on TPMs that were precisely this.

Jon



-BEGIN PGP SIGNATURE-
Version: PGP Universal 3.2.0 (Build 1672)
Charset: us-ascii

wj8DBQFSLLbjsTedWZOD3gYRAhMzAJ93/YEF8mTwdJ/ktl5SiR5IPp4DtwCeIrZh
KHVy+CIpN69GpJNlX0LiKiM=
=i4b8
-END PGP SIGNATURE-
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] [cryptography] Random number generation influenced, HW RNG

2013-09-07 Thread Eugen Leitl
- Forwarded message from Thor Lancelot Simon t...@panix.com -

Date: Sat, 7 Sep 2013 15:36:33 -0400
From: Thor Lancelot Simon t...@panix.com
To: Eugen Leitl eu...@leitl.org
Cc: cryptogra...@randombit.net
Subject: Re: [cryptography] Random number generation influenced, HW RNG
User-Agent: Mutt/1.5.20 (2009-06-14)

On Sat, Sep 07, 2013 at 09:05:33PM +0200, Eugen Leitl wrote:
 
 This pretty much rules out CPU-integral RNGs. It has to be
 a third-party add-on (USB or PCIe), and it has to be open hardware.

I think you take this more than a little too far.  I see CPU-integral
RNGs as very valuable source to be mixed with other sources in a
software pool of entropy.  Why should we reject them, unless we think
the mixing functions themselves are useless?

The lesson here seems to me to be that we should be far more
assiduous in seeking out additional sources of entropy and in always
ensuring software RNGs mix input from multiple such sources into
all output.  We should abandon sacred cows like the notion of
information-theoretic randomness (that we don't actually know how
to measure, but in pursuit of which we hamstring our software RNGs
by arranging that they refuse to produce any output unless, by some
questionable criterion, there is enough of it) and pursue engineering
goals we can actually achieve, like mixing enough other-source input,
of whatever quality, with the output of fast generators we can no longer
trust that the adversary must actually attack the mixing function, rather
than iteratively guessing the few state bits he does not already know.

Secondarily -- and sadly! -- we must now be very suspicious of devices
that integrate random number generation and encryption.  Can we even
trust raw hardware RNG output for the generation of IVs?  I would argue
not, because the same device's AES engine could be leaking key bits into
our explicit IVs, etc, and we couldn't ever know.  Devices that offload
packet processing in its entirety (SSL accellerators, IPsec accellerators,
etc.) have even more opportunity to do this sort of thing.  Hardware
crypto offload may still be very useful -- random number generation perhaps
in particular -- but we will have to apply it with extreme care, and with
a deliberate eye towards eliminating covert channels put in place by
people at least as smart as we are, and with far more time and experience
thinking about the problem from the offensive point of view.

Finally, we have to accept that the game might just be over, period.  So
you use a pure software RNG, mixing in RdRand output or not as you may
prefer.  How hard do you think it is to identify the datastructures used
by that RNG if you can execute code on a coprocessor with access to host
RAM?  Almost every modern server has such a coprocessor built in (its
management processor) and you won't find the source code to its firmware
floating around.  Intel even puts this functionality directly on its
CPUs (Intel AMT).  Rather than beating up on the guy who put a lovely
RNG instruction into every processor we're likely to use any time soon,
it seems to me we ought to be beating up on ourselves for ignoring far
simpler and more obvious risks like this one for well over a decade.

Seriously, show of hands, who here has ever really put his or her foot
down and insisted that a product they were purchasing _omit_ such
functionality?  Not chosen not to pay for it, refused to buy server X
or mainboard Y simply on the basis that management processor functionality
was onboard?  Now, compare to the number of people complaining about
backdoored RNGs here and elsewhere on the Internet.  Go figure.

To me the interesting question, but one to which I don't expect to ever
know the answer, is whether the adversary -- having, we can assume,
identified high value devices to systematically compromise, and lower value
devices to defer for later or simply ignore entirely -- went at those
devices sniper-style, or shotgun-style.  Were a few key opportunities for
tampering identified, and one or two attempted against each targeted
device?  Or were a wide variety of avenues explored, and every single one
that seemed relevant attempted everywhere, or at least against certain
particularly high value devices?  If we knew that, in a way we might know,
when we did finally see concrete evidence of a particular kind of
tampering, how long to keep looking for more.

But we aren't going to know that, no matter how much we might want to.
Attacks on crypto hardware, attacks on management processors, attacks
on supervisory or trusted execution modes seldom exercised in normal
system operation, attacks on flash modules holding boot code, so that
under the right circumstances they replace page P with evil page P',
attacks on elements of IC vendors' standard cell libraries (DMA engines
would seem promising); assume the adversaries are smart, and good at their
jobs, and the sky would seem to be the limit.

The sky will fall, of course, when various