[Cryptography] Dual_EC_DRBG backdoor: a proof of concept

[ianG]

On 4/01/14 01:50 AM, Krisztián Pintér wrote:
>
>
>
> Theodore Ts'o (at Friday, January 3, 2014, 7:01:16 PM):
>> Sure, but a prng is not the only tool in the toolbox.  You can also
>> try to grab entropy from hardware, and from OS-level events.
>
> i call moving goalposts on this one. it can be the case that we don't
> need prngs. we can grab enough unpredictable information from hw
> sources that we can just extract all the randomness we need.


Right, we need collectors of entropy, we need a mixer, and we need an 
output stage, variously called a whitener, expander, PRNG, DRBG.  They 
all need to work together.



> but not needing a solution does not make the solution incorrect. there
> might be a case when we need it.
>
> basically we have two schools on this, and i don't know where i
> belong. one school says that you need true random source. no matter
> how whitened or processed, it won't generate more entropy. the other
> school says you need 128 bits of unpredictability, and then you can
> extract megabytes of randomness with no risk at all. we understand
> that there is only 128 bit uncertainty, but it is enough.


It is the latter, in our space of cryptography (says I).  Entropy was a 
1990s viewpoint, I think.

Entropy is unpredictable by anyone, so it's good for the task, 
theoretically.  But we don't care about us predicting it.  We care about 
the attacker predicting it.

We can draw a circle, and declare everyone inside is us, and everyone 
outside is a potential attacker.  Then we can draw a small amount of 
entropy from inside the circle, and put it into our expansion function. 
  We know by the properties of hashes and ciphers that we can make an 
expansion function that is unpredictable, if the seed is unpredictable: 
  it's the same property as breaking the hash or cipher.  Hence the proofs.

Now, we could use entropy, because it achieves the goal as well.  It 
dominates, which is to say, it is more better in every way, in terms of 
its quality.  But, entropy is very hard to collect, it's expensive.  And 
only comes in small doses.  Not enough to really fill the inputs of say 
big RSA keys, by itself, without a lot of work.  Which we really can't 
rely on, attempts just haven't worked.



Hence we end up with the design:


    Entropy collector  ----\
                            \ _____          _________
                             /     \        /         \
    Entropy collector  ---->( mixer )----->( expansion )-----> RNs
                             \_____/        \_________/
                            /
    Entropy collector  ----/


Which I sometimes call a trident design, someone else called it a 
cascade design, and yet others think of it as Yarrow or Fortuna.  But 
I'm not sure enough about this all to know whether they've stamped the 
name, or what.  They've obviously pioneered the way...


> you can subscribe to the former school. but then, you don't want
> fortuna either, nor any other prng. or you subscribe to the latter
> school, but in this case, you have to admit that the quality of the
> prng matters. and you also have to agree that bbs delivers some
> security properties that for example aes does not.


Well, at the end of the day, it is an engineering problem.  If you 
subscribe to the Entropy school, you do not answer the engineer's 
question of "what happens when it breaks?"

The above design answers it.  We have to care *a fair bit* about the 
mixer and the expansion function, but each component is limited in its 
API and demands on quality.  They are simple black boxes.

Then, say BBS.  Talking about it is fine, but it only makes sense when 
placed in a context.  If it is in the above context, as an expansion, 
then fine, it might work.  (Or as a collector, even.)

But so might AES.  And engineering has it that if we've cared some about 
the modules, once we get to that stage of building the structure, we can 
substitute in different modules and still get the same good result.

As engineers in software, the acid test is whether we can throw it at an 
intern and say "build it this way."  (Which I just did.  It worked. 
RNGs are now a solved engineering problem, as far as I can see.  Until 
someone turns it upside down in a paper...)



iang