Subject: [therightkey] common factors

From: Stephen Farrell <[email-masked]>
Date: Wed, 15 Feb 2012 19:17:29 +0000

Hiya,

I guess the recent publications about common factors [1,2]
are something else that this group might want to consider.

I wonder if an rsa modulus checker protocol might help or
something. Not sure if that's something that could be run
quickly enough though, other than for the straight
duplicates or dumbass things with small factors you should
spot yourself. Anyone know?

Or maybe you could register your public key and get a
nonce, then come back periodically to see if any problems
have been detected for your key.

And yes, better prngs are needed, but there'll probably
always be bad ones out there.

S.

[1] http://eprint.iacr.org/2012/064
[2] 
http://it.slashdot.org/story/12/02/15/1540212/factorable-keys-twice-as-many-but-half-as-bad

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 16 Feb 2012 13:12:55 +0000

Dunno if anyone else thinks this might be interesting
but I do:-)

So I sketched out an initial idea for how it might fit
in here. [1]

Comments welcome.

S.

[1] http://www.ietf.org/id/draft-farrell-kc-00.txt

On 02/15/2012 07:17 PM, Stephen Farrell wrote:
> _______________________________________________
> therightkey mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/therightkey
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 16 Feb 2012 08:51:57 -0500

My first thought was that this should be done by the CA. Then it turns
out that these are all (apparently) embedded systems generated keys
and only some of those are CA certified. So maybe there is a need for
this protocol.

As I have mentioned before though, public key is problematic in
embedded systems. Most of the systems don't have the resources to do
the job right and this will only get worse as time goes on because as
a $1 processor gets more powerful a chip with a 6502 core gets cheaper
and more are made. More 6502 type chips were made last year than in
any previous year.

So my view is that we have to get away from the idea that the endpoint
has to do public key crypto. I have developed technology (rights
reserved) that moves the public key stuff off the endpoint device
without creating holes the maker or key repository can exploit.

-- 
Website: http://hallambaker.com/

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 16 Feb 2012 14:13:32 +0000

On 02/16/2012 01:51 PM, Phillip Hallam-Baker wrote:
> My first thought was that this should be done by the CA.

In the cited material, they also cover PGP and SSH keys and
not every CA will have a collection beyond its own end
entities so I don't think this is a CA function since its
not checking one public key, but one public key against
a population of keys and is independent of X.509, PGP, SSH
etc.

 > Then it turns

That too.

> has to do public key crypto.

Well, that's one position but not necessarily the only one
with merit.

S

 > I have developed technology (rights

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 16 Feb 2012 09:20:31 -0500

>> and only some of those are CA certified. So maybe there is a need for

Problem being that it is probably easier to implement a RNG right than
to implement any additional protocol for checking. Or at least the
only people who are likely to implement your protocol are people who
(1) would do the RNG right or (2) are required to for an audit
requirement.

It would be really nice if there was some way to audit RNGs algorithmically...

> Well, that's one position but not necessarily the only one

Well certainly it is better that they do have a PKI stack but only if
they do it right and that puts us way above what a PIC controller
class chip with only a few Kb can be expected to do.

Hence we need to have two tracks. Rather than telling people that they
must do PKI on 16 bit chips, maybe have a different approach there.

---

From: Stephen Farrell <[email-masked]>
Date: Thu, 16 Feb 2012 14:29:24 +0000

> (1) would do the RNG right or (2) are required to for an audit

A fair point. But one we don't seem to be able to get right
and there are to also be fair some subtleties.

Apparently some of the problem is also not the PRNG algorithm,
but rather when you call it.

For example, the 1st prime generation might happen just after
1st boot when there're few sources of randomness on the device.
So while the 2nd prime may be much more random the probability
of the 1st one being the same as someone else's is high enough
to be a problem. (Apparently. He repeated:-)

So there might be reasons to call this even if you're
confident of your key generation code, in case someone fed the
PRNG a crap seed.

S

---

From: Nico Williams <[email-masked]>
Date: Fri, 17 Feb 2012 14:37:43 -0600

> It would be really nice if there was some way to audit RNGs algorithmically...

Separate the HW RNG and other entropy gathering parts from the rest of
the RNG (i.e., the entropy pool, the mixer, the extractor), and you
provide a per-device seed for testing.  To test you put the device in
test mode so that the only entropy will be from the test seed, thus
making the RNG completely deterministic.  The production mode can also
use the test (or another per-device) seed and date/time of boot to
initialize the entropy pool, just in case the HW RNG get stuck on all
ones or all zeros (or all nines).  Testing production mode can also be
done by, e.g., statistical analysis of the RNG outputs (and inputs)
under various operating conditions (e.g., different temperatures,
etc...), and by extracting a copy of the entropy pool contents once to
check that the RNG is not deterministic from that point forward
(because new entropy gets mixed in).  But you have to make sure that
any test modes can't be enabled without tampering with the physical
device.  Once the device is sealed you should not be able to test the
RNG in any way other than by statistical analysis of its outputs.

Nico
--

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 17 Feb 2012 17:51:26 -0500

I don't see how you get ergodicity into the device without the
possibility of observation. Without addressing that problem you are
going to have a protocol that always tells the client 'yep you are
hosed'.

I see the following possibilities for ergodicity

1) Random seed installed during manufacture
2) Random capture from embedded RNG source / environmental capture
3) Random caputure from UI
4) Obtain random data from the network

For the web browser or server the usual approach is (3).  It works
fine because there is sufficient ergodicity in the UI interactions to
provide 128 bits just waiting a few seconds. But we can't do that on
an embedded device

1) Is actually not as bad as might be imagined, you trust the
manufacturer not to backdoor your crypto so having them give you a
seed is not terrible.

2) Is ideal but adds to hardware cost. Unless that is someone can work
out a cheap way to get random data into a D/A port or other I/O pin.

4) Is clearly sub optimal since the service knows the data sent.

How about this for a better protocol approach?

Client generates random seeds. S1, S2
Client sends Trunc(H(S1)) to the service
Service says 'hey I have seen that before' or 'nope it is new' + returns S3

Client generates new seed from H(S1 + S2 + S3 +c)
Where c is a counter that is incremented for each call for more random bits.

Advantages:

1) The checking protocol is tied into the PRNG algorithm so that it is
really hard for the programmer to balls it up.

2) Only part of the ergodicity is checked, the protocol checks to see
that there are at least 128 bits worth of random data in the output.

Cons:

1) Requires twice the amount of randomness to do the job right.

A scheme of this type might well be best implemented as a canary type
scheme so that issues the the PRNG during configuration were being
detected...

Also, this looks to me to be the sort of thing that you would want to
be a part of some form of device enrollment protocol.

---

From: Adam Back <[email-masked]>
Date: Sat, 18 Feb 2012 00:11:06 +0100

I dont think this is going to be very robust because the fact that the
entropy seeding is so bad that some implementations are generating
literally the same p value (but seemingly different q values) I would
think you could view the fact that this can be
detected and efficiently exploited via batch GCD as an indication of an even
bigger problem.

Namely if the seeding is that bad you could outright compute all possible
values of p even for cases where p was not shared, by running through the
evidently small by cryptographic standards number of possible PRNG states...

Then you might be looking at more than 1% or whatever the number is that
literally collide in specific p value.  Assuming p is more vulnerable than
q, you could then use the same batch GCD to test.

Adam

---

From: Nico Williams <[email-masked]>
Date: Fri, 17 Feb 2012 17:11:16 -0600

On Fri, Feb 17, 2012 at 4:51 PM, Phillip Hallam-Baker <[email-masked]> wrote:
>[...]

Right.  There's nothing wrong with this as a fallback.  Also, we
assume a clock or stable storage for a counter so as to avoid starting
with the same seed every time.

> out a cheap way to get random data into a D/A port or other I/O pin.

A floating D/A input will do.  Also, CPUs can implement an RNG
relatively cheaply.  Sun did it in UltraSPARC CPUs, and Intel does it
now in theirs.  As with all other things electronic is just a matter
of getting it into one massively manufactured chip/chipset and then it
will quickly get cheaper.  (Smartphones, for example, are chuck-ful of
inputs suitable for entropy gathering, and have modern CPUs.  Even
non-smartphone phones have lots of suitable inputs.  You have to reach
for devices like keyfobs to find devices where it'd be expensive to
retrofit an RNG.)

> 4) Is clearly sub optimal since the service knows the data sent.

(4) is not so bad if you also have (1), because a) the vendor doesn't
know the entropy obtained in (4) and the service in (4) doesn't know
the vendor seed, thus if the device combines both then the vendor and
service have to collude in order to recover the device's state.

> Where c is a counter that is incremented for each call for more random bits.

Sure.  And if you have RSA keys for the service and the client then
you can authenticate the service and encrypt the entropy (so
eavesdroppers can't see it).

> really hard for the programmer to balls it up.

If there are small enough perturbations in the seeding of the PRNG
then eventually there will be enough devices with colliding state that
will be detected.  Yes, this is good.

> 1) Requires twice the amount of randomness to do the job right.

Not necessarily.  We should be willing to settle for computational
entropy in many cases (i.e., it should be hard to recover the device's
PRNG state from Trunc(H(S1)).

> be a part of some form of device enrollment protocol.

Yes.  And if there's enough UI then the user can be asked to confirm
that the public key of the RNG service is correct -- SSH-like, but
since there will be few such services in any one org, it will
generally be recognizable.

Nico
--

---

From: Stephen Farrell <[email-masked]>
Date: Fri, 17 Feb 2012 23:23:22 +0000

Hiya,

> q, you could then use the same batch GCD to test.

Sure. But wouldn't this protocol still help then? Assuming that
protocol clients don't ignore the known-bad answers, they'd
hopefully iterate until they get a not-known-bad key one way or
another.

I think so, but maybe you're seeing something I'm not.

Something not that clear in the -00 is that the responder here
can supply random bits as a side effect of answering the
query. (The -01 will make this clearer when its ready.)

S.

>
> Adam
>
> On 16 February 2012 14:12, Stephen Farrell<[email-masked]>  wrote:
>>

---

From: Adam Back <[email-masked]>
Date: Sat, 18 Feb 2012 00:40:26 +0100

While it doesnt hurt as a partial sanity check, but with a huge false
negative rate (ie it wont complain many many times even though the entropy
is too small because it cant measure entropy, just the occasional side
effect that two computers generated the same value), it doesnt robustly fix
the problem which is the entropy of the device RNG is woefully small.

eg say the entropy is 20-bits and there are enough clients participating
that mostly you get a collision for any of the 2^20 (1million) keys.  So
then you tell it to try again, and it repeatedly does until there is no
collision.  All you've done is add a new entry to your previously seen
public key table on the server.  No entropy was added.

You cant really (securely) send entropy over the network to a device with no
entropy because an eavesdropper can read whatever you send it.

There is another RNG problem also where if you add entropy in too small
chunks the attacker can also brute force in stages.  The yarrow design was
supposed to defend against that.  eg consider you break in and copy rng
state, then the user adds 32-bits, draws one externally published or
verifiable output - eg a nonce or encryption using a random key etc, then
adds another 32-bits and repeat.  Well that remains insecure indefinitely
because the attacker can brute force each 32-bits independently.

As a last resort defense its probably better to send the client some
randomness in the clear, or encrypted with a key exchange depending on what
randomness it has - at least then in the off chance that the attacker missed
those messages, you retain some security rather than going forward with an
insecure public key...

But really the device itself should be tracking what entropy it has as
it is the only device in a position to know that and refraining from
generating cryptographic keys with under 128-bits of entropy...

Adam

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 18 Feb 2012 00:12:13 +0000

Some good points.

> public key table on the server.  No entropy was added.

That assumes that the client doesn't get more random bits as time goes
on. In practice I'd say getting more bits is quite likely, but whether
those would be enough to make a difference if we really start with only
20 bits is hard to say. But that's probably a minor effect compared to
sending random bits.

> entropy because an eavesdropper can read whatever you send it.

I disagree. I can often send entropy in practice securely but
with no guarantees, (on that we agree).

That's still better than not doing it in most cases. I'd be pretty
confident that the majority of devices with not so great key
generation could be helped by something like this.

> generating cryptographic keys with under 128-bits of entropy...

Right. But we've seen that device keep not doing it right locally,
hence the idea of trying to help globally.

S

>
> Adam
>
> On 18 February 2012 00:23, Stephen Farrell<[email-masked]>  wrote:
>>
>> Hiya,
>>
>>

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 18 Feb 2012 20:53:00 +0000

So I did a bit on this yesterday and today and now
there's a good bit more detail [1] to beat up on
if someone's interested. :-)

S.

[1] http://tools.ietf.org/html/draft-farrell-kc-01

---

From: Martin Rex <[email-masked]>
Date: Mon, 20 Feb 2012 19:31:41 +0100 (MET)

Nico Williams wrote:
> now in theirs.

I believe that a purely software-based high quality seeding of
a CPRNG is not that difficult, but a lot of implementations are
not going a very (efficient) job here.

What is randomness/entropy?  It is "un-predictability".
In order to create good seeds and reseeds, you have to

  (a) find events that can not be predicted
      with 100% accuracy at 100% of the time and

  (b) collect enough of those events and compress them without
      killing too much of the entropy during compression.

1 Bit of entropy for an event means that it can be predicted with
100% accuracy at most 50% of the time.

0.1 Bit of entropy for an event means that can be predicted with
100% accuracy at most 95% of the time.

The "difficult" part is figuring out possible event sources,
sampling, them and making a very conservative assessment about the
actual amount of randomness in an event (or more precisely in the
delta between two events of the same type).

In order to create a seed with an estimated 128 Bits of entropy
for your CPRNG entropy pool, you would collect at least 1280 0.1-Bit
events or 128 1-Bit events, put them into an array and use a cryptographic
hash as a compression function, preferably a hash with 2x larger output
size than the amount of assumed combined entropy/randomess in the
collected events. 

In typical PCs, workstations & servers you find plenty of "events"
that can be used.  It may be more difficult for embedded devices, where
there is *much* less concurrency inside the device itself.  But as soon
as there is some hardware media attached to such a device (LAN or WLAN),
or a harddisk with physical platters, there should be an event source
available, and if the hardware supports any high resolution counter
(a millisecond or better), such events can be sampled.

An IMHO poor source of entropy is a mouse moved by a human user.
It's actually confusing to see how popular mouse-moves seem to
be for by key-generation programs for PCs, where *MUCH* better
sources of randomness are available that can collect at least
as good entropy without bothering the user.

-Martin

---

From: Martin Rex <[email-masked]>
Date: Mon, 20 Feb 2012 21:03:59 +0100 (MET)

Nico Williams wrote:
> 
> Phillip Hallam-Baker <[email-masked]> wrote:
> >
> provide a per-device seed for testing.

Correct.  You can and should test the entropy _inputs_ whether they
meet your assumption of "unpredictability".  Testing the output
of the CPRNG is of limited value (it would only ring bells if both,
the randomness in the entropy inputs are way behind their assumed
properties, plus there is a serious problem in your CPRNG in
moving from state n to state n+1).

>
>                                       But you have to make sure that

This rings my "snake-oil" alarm bells.

If your assessments of the entropy of your inputs is correct, then
there will NOT be a problem to offer the test mode when the device
is in use.  You just need to ensure that the test mode reveals only
surplus samples that your CPRNG does not use.
Most devices should be able to produce much more samples that what
is needed/consumed by the CPRNG, and there should not be a problem
_per_se_ by allowing the testing of samples when the device is in
productive use.

Not revealing anything may result in the *real* randomness being stronger
than the conservative assessment from the design.  But you should be
using a sufficient safety margin ( factor >= 2 ) in assessing the effective
randomness of your input parameters anyway.  And letting unauthenticated
peers pull entropy input samples is probably always a bad idea.

-Martin

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Mon, 20 Feb 2012 15:46:15 -0500

Stephen's protocol would address one particular type of PRNG screw up,
the case where the PRNG is so badly screwed up that duplicate keys are
seen.

A more common screw up is the Netscape bug where the PRNG has a sound
algorithm but is working on too little initial entropy (about 30 bits
I seem to recall).

In the Netscape case the only way to fix the problem was to reverse
engineer the code. After conversations with Jeff Schiller, Alan
Schiffman and others I had a long conversation with Marc Andressen on
the design of the PRNG in the early editions of Navigator. This was
after I broke SSL 1.0 in ten mins and he wasn't too keen talking to
me. Eventually I managed to convince them that putting 30 bits worth
of entropy through MD5 would not produce 128 bits of randomness.

Marc then did something he should have done at the start and they
finally hired some real crypto people (Taher & the bros Wienstein).
They also asked me how to do the job right so I sent the design notes
for the code in Shen.

A year later the PRNG bug was rediscovered. I asked what had happened
and the response I got back was that they had looked at the design
notes for the PRNG and they were so comprehensive they didn't feel the
need to check the code.

So the moral I draw from that is that where the PRNG is concerned
there really is no substitute for checking the code where public key
algorithms are concerned.

This is not the case for symmetric algorithms where it is sufficient
for either side to introduce a sufficient amount of entropy.

---

From: Stephen Farrell <[email-masked]>
Date: Mon, 20 Feb 2012 21:12:33 +0000

> the case where the PRNG is so badly screwed up that duplicate keys are

Well, anything detectable from the public key (and a signature I
guess, hard to see what that might be but who knows). So both the
common factors thing and e.g. the blacklisted keys from the earlier
debian problems could be detected.

I guess really stupid lengths could be barfed on too and
even even RSA moduli. (I know, these should ever happen,
but...)

Point is that a protocol can help with (some) new types
of problem too as we discover that those problem kinds of key
have gotten out there and been discovered.

Its an open question as to whether this is worthwhile, (e.g. maybe
nobody would offer such a service) but I think it'd be good to have
it (properly) spec'd in case it does turn out to be useful.

(I'd be glad to get more review to get "properly" bit sorted
btw - I'm bound to have done something dumb:-)

S.

PS: I do entirely agree about fixing implementations as well but
am just focusing on another aspect myself.

> finally hired some real crypto people (Taher&  the bros Wienstein).
> On Mon, Feb 20, 2012 at 3:03 PM, Martin Rex<[email-masked]>  wrote:
>> Nico Williams wrote:
>>>
>>> Phillip Hallam-Baker<[email-masked]>  wrote:
>>>>
>> using a sufficient safety margin ( factor>= 2 ) in assessing the effective