-----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-----