some discussion of rannos in PGP (was: of a hole in PGP)

[A.Back@exeter.ac.uk]

-----BEGIN PGP SIGNED MESSAGE-----

Fred Cohen <fc@all.net> writes on cpunks:
: PGP is a product that is specifically disliked by the powers that be
: because it provides free access to strong cryptography which is against
: the public policy of the US government.  That means that people in that
: same said government likely feel it is their duty to make certain that
: they can still read PGP mail.

Certainly granted!  Hence persecution of Phil Z.

A bit difficult to achieve in the presence of available source code, I
(and many others) are using PGP compiled by themselves.  That doesn't
prove there are no subtle back-doors but it rules out unsophisticated
backdoors in distributed executables.  (Even such things could be
checked if someone got suspicious, things can be reverse engineered).

Now to the question of what can be done practically to help further
validate PGPs authenticity, and freeness from back-doors.

The way I see it the only attack which you could reasonably expect to
pull off in terms of being subtle enough to hope to get away with
given full access to source is the random number generator.

The code which actually generates the random primes, and converts them
to PGP output format is reasonably short and well defined.  Wouldn't
take long to single step that and watch that nothing happened on the
way out to file.

Encryption is a similarly simple operation, M ^ e % n you could easily
check that manually (with a certain small piece of perl even).  Same
for generation of IDEA keys.

I don't really feel qualified to comment properly on the random number
generation, but to me (I looked at the source in fair detail) it looks
good.

I mean there is real entropy being generated (timing key strokes
against a high speed clock on PCs lower on UNIX systems typically)
and the stirring operation looks good, MD5 + XOR on key.

Presuming that the MD5 implementation is correct?  Seems a pretty good
likelihood to be, it's been given enough real world tests that you
could do a very nice probablistic statistical confidence test on it.
Which would easily say that it was correct to some huge degree of
certainty.

The legitimacy of using a high frequency clock to time intervals
between key strokes, seems a very good way of generating random
numbers.  I mean there is most definately *some* entropy being
generated, PGP makes reasonably conservative estimates of the amount
of entropy generated, and stirs the whole number in (not just the
expected entropy).

I'm not saying your comments aren't useful; they are, and analysis and
critique of the random number generation in particular is very
important.  Indeed given the sheer cost of factoring a 2048 bit RSA
modulus, or of brute forcing a 128bit IDEA key, it is indeed a
pertinent question as to whether any kind of brute force attack could
be generated on the random number generation, which could be slighly
cheaper than either of these.  128bits is a lot to play with.

To me it looks good, but then I'm not a cryptographer, and also there
is the kind of "NP problem aspect" to it all in that for reasonably
complex code it will not be apparent whether a proof is possible with
out looking at the specifics.

Still I think some analysis of the random number generation code would
be useful work.  I'm not expecting to see a flaw, but doesn't mean it
shouldn't be entered into with an open mind.

I think it does not fall in the same league as the apparent difficulty
of having a secure sendmail (you said a compromising couple of bugs
seem to get found a couple of times a year), for at least two reasons,
one is that with sendmail the code being examined must take input from
Charlie who is trying to mess the system up.  So a deliberate attempt
to foul the works, examining the source, looking for any kind of
subtle weakness, or weird combination of inputs (which would almost
certainly never occur by accident during normal usage) which could
cause it to compromise security.  For PGP for the section we are
talking about (key generation) the only input comes from *you*, the
person who is presumably trying to obtain security, not trying to
generate a weak key through some tortuous input string.  So things
like the stack over flow with carefully crafted machine code for the
particular architecture which was exploited with finger in the fave
old example of the worm of yore, is not the kind of attack you need to
be worried about (IMO).

The second aspect in which analysing PGPs ran no generation, is
different to sendmail or http type problems is that what PGP is doing
with it's random no generation is well defined, contained in few
lines of code, and only really relying on a couple of assertions:

	1) MD5 is itself not inherently flawed
	2) the MD5 implementation is correct
	3) key stroke timings are a source of a safely conservatively
	   estimatable amount of entropy
	4) the key generation method does not narrow the search space
	5) there are no other compromising bugs between key generation
	   of the key and it being written to the keyring

1) Heh, not a lot you can do about that.  Is it or isn't it?  Time
will tell.

2) Seems pretty likely to me there are test strings which come with
the RFC implemenation, and it would be unbelievably unlikely that it
should produce the complete set of tests and yet somehow still be
flawed.  Given that there are _no_ branches in the algorithm (ie just
various permutations and bit twidlings based on the key info, which
get mangled into the digest.

3) Pretty good I think, especially on a PC, which has a higher speed
timer.  Some entropy is surely generated, and with safe entropy
estimation, and cryptographically secure stirring, it sounds pretty
good to me.

4) For RSA keys, I don't think so, unless you believe that strong
primes will agains become important.  For current factoring algorithms
strong primes are just as hard to factor as a completely randomly
generated prime, except for certain primes which are in any have an
infinitesimal chance of occurring.  For IDEA keys there is little
value added over a striaght ran no, as there are no special properties
which an IDEA key must have.

5) I would assert is relatively trivial to demonstrate, a couple of
hours with a debugger should demonstrate that.  You could do testing
more rigourously, test every branch, so that you have checked that the
outcome is that the key gets written to the keyfile, with various
options, not utterly fool proof of course, but pretty darn good given
the simplicity.

On the more philosophical side, with the idea that you can never be
sure that folks aren't NSA agents with hidden agendas etc, well you
can't be sure.

But the open source and sheer number of folks reading is the best
argument against this.  That means that at least some true blue
cpunks, "live free or die" types will read it in earnest, and examine
very carefully.

Another philosophical argument against PGP having any cleverly hidden
"back-doors" in the form of purposefully weakened ran-no generators or
what have you is that the NSA et all hate PGP with such vehemence.
Heh if they don't like it, it must be good :-)

And remember, say NO to key escrow :-)

(It's no good having an ultra carefully validated PGP if you go to
jail for being caught with a copy on your HD, welcome to the Land of
the Freeh, and all you know.  May happens sooner than expected, then
the only folks using crypto will be the "live free or die" folks, plus
of course the criminals who figure they have more to hide and would
get in more trouble for what they are really up to than for a
"possesion of crypto" charge.)

Adam

PS to any folks who may have sent me mail in the last couple of days,
note the temporary change of email addr to: A.Back@ex.ac.uk due to
local hw failure, similarly the same m/c was the WWW server, should
all return to normal in a couple of days.  (Talk about single point of
failure, all the X-terms booted off it too).

- --
HAVE *YOU* EXPORTED RSA TODAY? --> http://dcs.ex.ac.uk/~aba/rsa/
- --rsa--------------------------8<-------------------------------
#!/bin/perl -s-- -export-a-crypto-system-sig -RSA-3-lines-PERL
$m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%Sa
2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,s/^.|\W//g,print
pack('H*',$_)while read(STDIN,$m,($w=2*$d-1+length($n)&~1)/2)
- -------------------------------8<-------------------------------
TRY: rsa -k=3 -n=7537d365 < msg | rsa -d -k=4e243e33 -n=7537d365

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i

iQCVAwUBMB9U5ynIuJ1VakpnAQGLcgP/fNe2cBJKNJrKE3iHiFrHgUM4So/Q0nqg
GYgJu+gYZIlnQSv6JUXBDWFw/29n/ARN9oENjxmgAs6rTiE9bjPhD8IuftGaENsF
ou3v4Y04B/7UFG8sXx9Opdr0G6P+sHM7f+pdwkCW4rtWA1tclUigrkIF/+65Q0a4
iZN1c4Y23tk=
=35BY
-----END PGP SIGNATURE-----