Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-10 Thread Jerry Leichter
On Sep 9, 2013, at 9:17 AM, Kent Borg wrote:
 Which brings into the light the question:  Just *why* have so many random 
 number generators proved to be so weak.
 
 Your three cases left off an important one: Not bothering to seed the PRNG at 
 all.  I think the Java/Android cryptographic (!) library bug that just came 
 up was an instance of that.
 
 I think the root of the problem is that programs are written, and bugs 
 squashed, until the program works. Maybe throw some additional testing at it 
 if we are being thorough, but then business pressures and boredom says ship 
 it.
 
 That won't catch a PRNG that wasn't seeded, nor a hashed password that wasn't 
 salted, the unprotected URL, the SQL injection path, buffer overflow, etc.
Good observations, but I think you're being too pessimistic.  All the examples 
you give *could* be tested - but not by ignorant black box testing - testing 
that ignores not just what's inside the box, but the actual requirements on 
what the box is supposed to produce.  A non-seeded PRNG, and even one seeded 
with a very small amount of entropy, will be caught by a test that runs 
multiple instances of the PRNG from the system starting state and ensures that 
the ensemble of first outputs (and, for good measure, the first *couple* of 
outputs) has the right statistics.  Similarly, a test that inserts the same 
password into multiple instances of the same system in the same state can check 
that the hashed versions have the right statistics.  No, these can't catch 
deliberate attack code which produces random-looking values that the attacker 
can predict - no test can.  But it will catch a broad class of common errors.

The others aren't cryptographic issues and require different approaches.

The fact that there are bad testing practices - and that those bad practices 
are used all too often - doesn't mean there aren't good practices, and that 
they could not be applied.  Where the testing is bad because of ignorance of 
what is actually important and how to test for it, learning from the failures 
of the past is the way forward - which was exactly the point of PRMG failures 
classification.
-- Jerry

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


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-10 Thread Perry E. Metzger
On Sun, 8 Sep 2013 15:22:32 -0400 Perry E. Metzger
pe...@piermont.com wrote:
 Ah, now *this* is potentially interesting. Imagine if you have a
 crypto accelerator that generates its IVs by encrypting information
 about keys in use using a key an observer might have or could guess
 from a small search space.

Oh, and of course, if you're doing a DSA style algorithm, you can
leak information in your choice of random nonce. This is yet more
reason to force protocols to use nonces that are deterministic based
on context, and to enforce that.

Perry
-- 
Perry E. Metzgerpe...@piermont.com
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-09 Thread ianG

On 9/09/13 06:42 AM, James A. Donald wrote:

On 2013-09-09 11:15 AM, Perry E. Metzger wrote:

Lenstra, Heninger and others have both shown mass breaks of keys based
on random number generator flaws in the field. Random number
generators have been the source of a huge number of breaks over time.

Perhaps you don't see the big worry, but real world experience says
it is something everyone else should worry about anyway.


Real world experience is that there is nothing to worry about /if you do
it right/.  And that it is frequently not done right.

When you screw up AES or such, your test vectors fail, your unit test
fails, so you fix it, whereas if you screw up entropy, everything
appears to work fine.



Precisely.


It is hard, perhaps impossible, to have test suite that makes sure that
your entropy collection works.

One can, however, have a test suite that ascertains that on any two runs
of the program, most items collected for entropy are different except
for those that are expected to be the same, and that on any run, any
item collected for entropy does make a difference.

Does your unit test check your entropy collection?



When I audited the process for root key ceremony for CAcert, I worried a 
fair bit about randomness.  I decided the entropy was untestable 
(therefore unauditable).


So I wrote a process such that several people would bring their own 
entropy source.  E.g., in the one event, 3 sources were used, by 
independent people on independent machines:


  * I used a sha-stream of laptop camera on dark paper [0]
  * Teus used sound card driver [1]
  * OpenSSL's RNG.

The logic was that as long as one person was honest and had a good 
source, and as long as our mixing was verifiable, the result would be good.


Then, I wrote a small C program to mix it [2];  as small as possible so 
a room full of techies could spend no more than 10 minutes checking it 
on the day [3].


The output of this was then fed into the OpenSSL script to do the root 
key.  (I'm interested if anyone can spot a flaw in this concept.)




iang



[0] This idea from Jon Callas from memory, the idea is that the lack of 
light and lack of discrimination between pixels drives the photocells 
into a quantam uncertainty state.

[1] John Denker's sound card driver.
[2] As an amusing sidenote, I accidentally used | to mix the bytes not 
^.  My eyeball tests passed at 2 sources but at 3 sources it was 
starting to look decidedly wonky.
[3] It was discussed on the group at this time, it was advised that the 
output of the mix should be sha'd, which I eventually agreed with, but I 
don't think I did in the event.

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


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-09 Thread Kent Borg

On 09/08/2013 11:56 PM, Jerry Leichter wrote:

Which brings into the light the question:  Just *why* have so many random 
number generators proved to be so weak.


Your three cases left off an important one: Not bothering to seed the 
PRNG at all.  I think the Java/Android cryptographic (!) library bug 
that just came up was an instance of that.


I think the root of the problem is that programs are written, and bugs 
squashed, until the program works. Maybe throw some additional testing 
at it if we are being thorough, but then business pressures and boredom 
says ship it.


That won't catch a PRNG that wasn't seeded, nor a hashed password that 
wasn't salted, the unprotected URL, the SQL injection path, buffer 
overflow, etc.


Computer security is design, implementation, and skepticism.  But unless 
you can sell it with a buzzword...



-kb

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


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread Perry E. Metzger
On Sun, 8 Sep 2013 15:55:52 -0400 Thor Lancelot Simon
t...@rek.tjls.com wrote:
 On Sun, Sep 08, 2013 at 03:22:32PM -0400, Perry E. Metzger wrote:
  
  Ah, now *this* is potentially interesting. Imagine if you have a
  crypto accelerator that generates its IVs by encrypting
  information about keys in use using a key an observer might have
  or could guess from a small search space.
  
  Hadn't even occurred to me since it seems way more blatant than
  the other sort of leaks I was thinking of, but of course the mere
  fact that it is blatant doesn't mean that it would never be
  tried...
 
 Well, I guess it depends what your definition of blatant is.
 Treating the crypto hardware as a black box, it would be freaking
 hard to detect, no?

Ah, but it only needs to be found once to destroy the reputation of a
company.

Inserting bugs into chips (say, random number generators that won't
work well in the face of fabrication processes that alter analog
characteristics of circuits slightly) results in a could be an
accident sort of mistake. Altering a chip to insert an encrypted
form of a key into the initialization vectors in use cannot be
explained away that way.

You may say but how would you find that?. However, I've worked
in recent years with people who decap chips, photograph the surface
and reconstruct the circuits on a pretty routine basis -- tearing
apart secure hardware for fun and profit is their specialty. Even
when this process destructively eliminates in-RAM programming,
usually weaknesses such as power glitching attacks are discovered by
the examination of the dead system on the autopsy table and can
then be used with live hardware.

Now that it has been revealed that the NSA has either found or
arranged for bugs in several chips, I would presume that some of
these people are gearing up for major teardowns. Not all
such teardowns will happen in the open community, of course -- I'd
expect that even now there are folks in government labs around the
world readying their samples, their probe stations and their etchant
baths. Hopefully the guys in the open community will let us know
what's bad before the other folks start exploiting our hardware
silently, as I suspect the NSA is not going to send out a warning.

 I also wonder -- again, not entirely my own idea, my whiteboard
 partner can speak up for himself if he wants to -- about whether
 we're going to make ourselves better or worse off by rushing to the
 safety of PFS ciphersuites, which, with their reliance on DH, in
 the absence of good RNGs may make it *easier* for the adversary to
 recover our eventual symmetric-cipher keys, rather than harder!

I'll repeat the same observation I've made a lot: Dorothy Denning's
description of the Clipper chip key insertion ceremony described the
keys as being generated deterministically using an iterated block
cipher. I can't find the reference, but I'm pretty sure that when she
was asked why, the rationale was that an iterated block cipher can be
audited, and a hardware randomness source cannot.

Perry
-- 
Perry E. Metzgerpe...@piermont.com
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread John Kelsey
On Sep 8, 2013, at 3:55 PM, Thor Lancelot Simon t...@rek.tjls.com wrote:
...
 I also wonder -- again, not entirely my own idea, my whiteboard partner
 can speak up for himself if he wants to -- about whether we're going
 to make ourselves better or worse off by rushing to the safety of
 PFS ciphersuites, which, with their reliance on DH, in the absence of
 good RNGs may make it *easier* for the adversary to recover our eventual
 symmetric-cipher keys, rather than harder!

I don't think you can do anything useful in crypto without some good source of 
random bits.  If there is a private key somewhere (say, used for signing, or 
the public DH key used alongside the ephemeral one), you can combine the hash 
of that private key into your PRNG state.  The result is that if your entropy 
source is bad, you get security to someone who doesn't compromise your private 
key in the future, and if your entropy source is good, you get security even 
against someone who compromises your private key in the future (that is, you 
get perfect forward secrecy).

 Thor

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


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread Viktor Dukhovni
On Sun, Sep 08, 2013 at 06:16:45PM -0400, John Kelsey wrote:

 I don't think you can do anything useful in crypto without some
 good source of random bits.  If there is a private key somewhere
 (say, used for signing, or the public DH key used alongside the
 ephemeral one), you can combine the hash of that private key into
 your PRNG state.  The result is that if your entropy source is bad,
 you get security to someone who doesn't compromise your private
 key in the future, and if your entropy source is good, you get
 security even against someone who compromises your private key in
 the future (that is, you get perfect forward secrecy).

Nice in theory of course, but in practice applications don't write
their own PRNGS.  They use whatever the SSL library provides, OpenSSL,
GnuTLS, ...  If we assume weak PRNGS in the toolkit (or crypto chip,
...) then EDH could be weaker than RSA key exchange (provided the
server's key is strong enough).

The other concern is that in practice many EDH servers offer 1024-bit
primes, even after upgrading the certificate strength to 2048-bits.

Knee-jerk reactions to very murky information may be counter-productive.
Until there are more specific details,  it is far from clear which is 
better:

- RSA key exchange with a 2048-bit modulus.

- EDH with (typically) 1024-bit per-site strong prime modulus

- EDH with RFC-5114 2048-bit modulus and 256-bit q subgroup.

- EECDH using secp256r1

Until there is credible information one way or the other, it may
be best to focus on things we already know make sense:

- keep up with end-point software security patches

- avoid already known weak crypto (RC4?)

- Make sure VM provisioning includes initial PRNG seeding.

- Save entropy across reboots.

- ...

Yes PFS addresses after the fact server private key compromise,
but there is some risk that we don't know which if any of the PFS
mechanisms to trust, and implementations are not always well
engineered (see my post about GnuTLS and interoperability).

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


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread Kent Borg

On 09/08/2013 06:16 PM, John Kelsey wrote:
I don't think you can do anything useful in crypto without some good 
source of random bits.


I don't see the big worry about how hard it is to generate random 
numbers unless:


 a) You need them super fast (because you are Google, trying to secure 
your very high-speed long lines), or


 b) You are some embedded device that is impoverished for both sources 
of entropy and non-volatile storage, and you need good random bits the 
moment you boot.


On everything in between, there are sources of entropy. Collect them, 
hash then together and use them to feed some good cryptography.  If you 
seem short of entropy, look for more in your hardware manual. Hash in 
any local unique information. Hash in everything you can find! (If the 
NSA knows every single bit you are hashing in, no harm, hash them in 
anyway, but...if the NSA has misunderestimated  any one of your 
bits...then you scored a bit! Repeat as necessary.)


I am thinking pure HW RNGs are more sinful than pure SW RNGs, because 
real world entropy is colored and hardware is the wrong place to fix 
that. So don't buy HW RNGs, buy HW entropy sources (or find them in your 
current HW) and feed them into a good hybrid RNG.


On a modern multi-GHz CPU the exact LSB of your highspeed system 
counters, when the interrupt hits your service routine, has uncertainty 
that is quite real once the you push the NSA a few centimeters from your 
CPU or SoC.  Just sit around until you have a few network packets and 
you can have some real entropy. Wait longer for more entropy.


In case you did notice, I am a fan of hybrid HW/SW RNGs.

-kb


P.S.  Entropy pools that are only saved on orderly shutdowns are risking 
crash-and-playback attacks. Save regularly, or something like that.


P.P.S. Don't try to estimate entropy, it is a fool's errand, get as much 
as you can (within reason) and feed it into some good cryptography.


P.P.P.S. Have an independent RNG? If it *is* independent, no harm in 
XORing it in.

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


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread Perry E. Metzger
On Sun, 08 Sep 2013 20:34:55 -0400 Kent Borg kentb...@borg.org
wrote:
 On 09/08/2013 06:16 PM, John Kelsey wrote:
  I don't think you can do anything useful in crypto without some
  good source of random bits.
 
 I don't see the big worry about how hard it is to generate random 
 numbers unless:

Lenstra, Heninger and others have both shown mass breaks of keys based
on random number generator flaws in the field. Random number
generators have been the source of a huge number of breaks over time.

Perhaps you don't see the big worry, but real world experience says
it is something everyone else should worry about anyway.

Perry
-- 
Perry E. Metzgerpe...@piermont.com
___
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread James A. Donald

On 2013-09-09 11:15 AM, Perry E. Metzger wrote:

Lenstra, Heninger and others have both shown mass breaks of keys based
on random number generator flaws in the field. Random number
generators have been the source of a huge number of breaks over time.

Perhaps you don't see the big worry, but real world experience says
it is something everyone else should worry about anyway.


Real world experience is that there is nothing to worry about /if you do 
it right/.  And that it is frequently not done right.


When you screw up AES or such, your test vectors fail, your unit test 
fails, so you fix it, whereas if you screw up entropy, everything 
appears to work fine.


It is hard, perhaps impossible, to have test suite that makes sure that 
your entropy collection works.


One can, however, have a test suite that ascertains that on any two runs 
of the program, most items collected for entropy are different except 
for those that are expected to be the same, and that on any run, any 
item collected for entropy does make a difference.


Does your unit test check your entropy collection?

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

Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread Kent Borg

On 09/08/2013 09:15 PM, Perry E. Metzger wrote:
Perhaps you don't see the big worry, but real world experience says it 
is something everyone else should worry about anyway.


I overstated it.

Good random numbers are crucial, and like any cryptography, exact 
details matter.  Programmers are constantly making embarrassing 
mistakes.  (The recent Android RNG bug, was that Sun, Oracle, or Google?)


But there is no special reason to worry about corrupted HW RNGs because 
one should not be using them as-is, there are better ways to get good 
random data, ways not obvious to a naive civilian, but still well known.


Snowden reassured us when he said that good cryptography is still good 
cryptography.  If that includes both hashes and cyphers, then the 
fundamental components of sensible hybrid RNGs are sound.


Much more worrisome is whether Manchurian Circuits have been added to 
any hardware, no matter its admitted purpose, just waiting to be activated.


-kb

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


Re: [Cryptography] Techniques for malevolent crypto hardware

2013-09-08 Thread Jerry Leichter
On Sep 8, 2013, at 9:15 PM, Perry E. Metzger wrote:
 I don't see the big worry about how hard it is to generate random 
 numbers unless:
 
 Lenstra, Heninger and others have both shown mass breaks of keys based
 on random number generator flaws in the field. Random number
 generators have been the source of a huge number of breaks over time.
 
 Perhaps you don't see the big worry, but real world experience says
 it is something everyone else should worry about anyway.
Which brings into the light the question:  Just *why* have so many random 
number generators proved to be so weak.  If we knew the past trouble spots, we 
could try to avoid them, or at least pay special care to them during reviews, 
in the future.

I'm going entirely off of memory here and a better, more data-driven approach, 
might be worth doing, but I can think of three broad classes of root causes of 
past breaks:

1.  The designers just plain didn't understand the problem and used some 
obvious - and, in retrospect, obviously wrong - technique.  (For example, they 
didn't understand the concept of entropy and simply fed a low-entropy source 
into a whitener of some kind - often MD5 or SHA-1.  The result can *look* 
impressively random, but is cryptographically worthless.)

2.  The entropy available from the sources used was much less, at least in some 
circumstances (e.g., at startup) than the designers assumed.

3.  The code used in good random sources can look strange to programmers not 
familiar with it, and may even look buggy.  Sometimes good generators get 
ruined by later programmers who clean up the code.

-- Jerry


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