[148920] in cryptography@c2.net mail archive
Re: [Cryptography] Dual_EC_DRBG backdoor: a proof of concept
daemon@ATHENA.MIT.EDU (ianG)
Sat Jan 4 10:18:58 2014
X-Original-To: cryptography@metzdowd.com
Date: Sat, 04 Jan 2014 13:49:14 +0300
From: ianG <iang@iang.org>
To: =?ISO-8859-1?Q?Kriszti=E1n_Pint=E9r?= <pinterkr@gmail.com>,
Theodore Ts'o <tytso@mit.edu>
In-Reply-To: <129731091.20140103235015@gmail.com>
Cc: Thierry Moreau <thierry.moreau@connotech.com>,
Cryptography Mailing List <cryptography@metzdowd.com>,
Jon Callas <jon@callas.org>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
On 4/01/14 01:50 AM, Kriszti=E1n Pint=E9r 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
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
