-----BEGIN PGP SIGNED MESSAGE----- On Mon, 31 Jul 1995, Dr. Frederick B. Cohen wrote:
I wrote:
On Fri, 28 Jul 1995, Dr. Frederick B. Cohen wrote:
How (specifically) do you know that this is true? Key generation is very tricky stuf, and very subtle changes can have very profound impacts. I doubt that Zimmerman's original was truly perfect at this either, but how do we really know?
Because I've succesfully run the primes that PGP generates through the primality tests in other mathematical packages, most notably Arjen Lenstra's FreeLIP package. The remaining steps to generating an RSA keypair are very easy to follow, and the result simple to check by verifying that the components PGP comes up with satisfy ed=1 mod(p-1)(q-1). rsagen.c is pretty easy to follow if anyone wants to check for themselves.
But that doesn't guarantee there aren't weak keys at all. For example, primes of the sort 2^N+1 would pass the primality tests and be very weak keys.
As I'm sure you know, PGP picks its primes by choosing a random starting point and testing each odd number upwards until it gets a probable prime. The random number generator used to seed this search is mixed using MD5 which gives a uniform 1/0 distribution. I'd hazard a guess that the chances of a start point having so many contiguous 1's as to be close to 2^N is so vanishingly small that it's more likely a non-prime would pass the probabalistic tests! I suppose if I were really paranoid I'd feed in fixed starting points for the search to MIT PGP and PGP 2.6.2 to make sure that they come out with the same keys. - - Andy +-------------------------------------------------------------------------+ | Andrew Brown Internet <asb@nexor.co.uk> Telephone +44 115 952 0585 | | PGP (2048/9611055D): 69 AA EF 72 80 7A 63 3A C0 1F 9F 66 64 02 4C 88 | +-------------------------------------------------------------------------+ -----BEGIN PGP SIGNATURE----- Version: 2.6.2i iQEVAwUBMBzOMCXfPV+WEQVdAQEs3Af/Qr1RSfgKw0lHSdo+3A59ZY/7cmw1voA3 6zrl1uAOxUfXVO36UPrSh5/lGHjGNW25FU4mckZ5qwhD9x8BEI3NemIddAtSrnbH tNxTD5+dUpYyiab4j9CKE9FTBsuY+TriyafFOMRBvjELYVgh0zhnS6GBb2ZVN3R5 J1B+qItB/kK2rvrPN+9tqXaH6/lleOquZxA4quoVGOKOmdOg/uWA9xme90NqjjzS ZbTKVSWEuqWvbaIvm3KexgH1/t9jIU7EcRbfoRWiFDQrW/ecvInW61J6kEGfVqPK RmjsoyDsYZJ11AqPaZLgVDLY8lmAN9qzaiUH785tVRQY/A5qQzLrkA== =sDbg -----END PGP SIGNATURE-----
As I'm sure you know, PGP picks its primes by choosing a random starting point and testing each odd number upwards until it gets a probable prime. The random number generator used to seed this search is mixed using MD5 which gives a uniform 1/0 distribution. I'd hazard a guess that the chances of a start point having so many contiguous 1's as to be close to 2^N is so vanishingly small that it's more likely a non-prime would pass the probabalistic tests!
Well, not exactly random starting points. Starting points generated by user keystrokes with characteristics that may be analyzed so as to reduce the key space to a searchable size, starting points that are determined by a transformation of those keystroke sequences using an algorithm, starting points that are determined by an algorithm that uses a deterministic (albeit complex) algorithm which performs input and output based on timeslices and interrupt mechanisms and queues that may tend to alter the statistics of arrival times.
I suppose if I were really paranoid I'd feed in fixed starting points for the search to MIT PGP and PGP 2.6.2 to make sure that they come out with the same keys.
The term paranoid is inappropriate in this context. Paranoia refers to an irrational fear, while I am expressing a rational concern over a system that has been taken over by a (partially) government funded university and which has not been properly verified. The history of cryptography (as they say) is (quite literally) littered with the dead bodies of people killed because somebody else thought a cryptosystem was good enough when it was not. -- -> See: Info-Sec Heaven at URL http://all.net Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236
Hey, Doc...
The term paranoid is inappropriate in this context. Paranoia refers to an irrational fear, while I am expressing a rational concern over a system that has been taken over by a (partially) government funded university and which has not been properly verified. The history of cryptography (as they say) is (quite literally) littered with the dead bodies of people killed because somebody else thought a cryptosystem was good enough when it was not.
If you are concerned that someone put a whole or backdoor in PGP, then go grab the source and take a look for yourself. Thats why the code is available. If you can't understand it, then you probably have no real right to complain! However if you are still paranoid (and yes, I do believe this is an irrational fear, being the person who maintains the MIT PGP development sources) then go find someone who can understand it and ask them. As a side note, PGP does not go out of its way to choose "good" primes over other primes. Take a look at genprime.c and read the comment near the top of the file. It explains why. -derek
Hey, Doc...
The term paranoid is inappropriate in this context. Paranoia refers to an irrational fear, while I am expressing a rational concern over a system that has been taken over by a (partially) government funded university and which has not been properly verified. The history of cryptography (as they say) is (quite literally) littered with the dead bodies of people killed because somebody else thought a cryptosystem was good enough when it was not.
If you are concerned that someone put a whole or backdoor in PGP, then go grab the source and take a look for yourself. Thats why the code is available. If you can't understand it, then you probably have no real right to complain! However if you are still paranoid (and yes, I do believe this is an irrational fear, being the person who maintains the MIT PGP development sources) then go find someone who can understand it and ask them.
As a side note, PGP does not go out of its way to choose "good" primes over other primes. Take a look at genprime.c and read the comment near the top of the file. It explains why.
My assertion regarding weakness of the key generation algorithm was not related to the response you gave. As a result, it appears that you are avoiding the issue. This looks bad if you are, as you claim, maintaining a legitimate algorithm. Perhaps you would be better served by addressing the specifics of my comments - to wit: What makes you think PGPs method of getting seeds does not lead to a limited key space that is within the realm of modern computers to search? Your assertion that I could find the backdoor by inspecting the program is the wrong tactic for secure programs. If you want people to believe that a program is secure, you had better come up with good reasons that it is secure, and not hide behind "if you can't find any holes, it must be secure". Clever back doors are not accomplished by an obvious program change, but rather by the subtle use of some technique that appears to do one thing when it actually does something else. As a good example, a subtle interation with the rest of the environment could modify the key generation algorithm after it is loaded. Unfortunately, PGP is too large to verify against such back doors, so I ask again: Why (specifically) do you think the MIT version of PGP has no backdoors and is not subject to attacks such as the one outlined in my previous posting? -- -> See: Info-Sec Heaven at URL http://all.net Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236
Your assertion that I could find the backdoor by inspecting the program is the wrong tactic for secure programs. If you want people to believe that a program is secure, you had better come up with good reasons that it is secure, and not hide behind "if you can't find any holes, it must be secure".
This is where you are very wrong. I am not saying that "if you can't find any holes it must be secure". What I am saying is that the source is available, and thousands of people have looked at the source, and none of them have found any holes in it.
- to wit: What makes you think PGPs method of getting seeds does not lead to a limited key space that is within the realm of modern computers to search?
How do you propose that a user's keystrokes can be analyzed? If you assume that the PC's internal clock speed >> typing speed (which is a good assumption -- how many keystrokes/second can you type?) then you have a large amount of randomness that can be gained from timing keystrokes. Even a good typist will not have an even typestroke! Have you read RFC 1750? If not, I would recommend you read it before you consider continuing this thread!
Why (specifically) do you think the MIT version of PGP has no backdoors and is not subject to attacks such as the one outlined in my previous posting?
I think it has no backdoors because Jeff Schiller and I (among others) have looked closely at the random number generator code (he has taken a much closer look than I) and believe it to be secure. I also know that I did not put any backdoors into the code (but why would you believe me, I must be paid by the government to say this, right?) As to why I believe it is not subject to attack, I ask you again to go read RFC 1750. PGP follows its recommendations fairly closely. There is only one place where PGP fails to follow, and that is that PGP does expose the bucket of random bits, rather than mixing them before exporting them. However I do not believe that this would affect the generation of PGP Public Keys. -derek PS: In what field is your Doctorate?
Your assertion that I could find the backdoor by inspecting the program is the wrong tactic for secure programs. If you want people to believe that a program is secure, you had better come up with good reasons that it is secure, and not hide behind "if you can't find any holes, it must be secure".
This is where you are very wrong. I am not saying that "if you can't find any holes it must be secure". What I am saying is that the source is available, and thousands of people have looked at the source, and none of them have found any holes in it.
History shows that your approach fails. Here are some examples: Tens of thousands of people had source to the http daemon from CERN, and yet none of them noticed a hole that was detected as it was being exploited only a few months ago. Tens of thousands of people have access to sendmail and yet new holes are found by attackers several times per year on average. Tens of thousands of people have access to the sources of various versions of hundreds of software packages, yet there are holes found every day.
- to wit: What makes you think PGPs method of getting seeds does not lead to a limited key space that is within the realm of modern computers to search?
How do you propose that a user's keystrokes can be analyzed? If you assume that the PC's internal clock speed >> typing speed (which is a good assumption -- how many keystrokes/second can you type?) then you have a large amount of randomness that can be gained from timing keystrokes. Even a good typist will not have an even typestroke! Have you read RFC 1750? If not, I would recommend you read it before you consider continuing this thread!
Request for Comments: 1750 - Randomness Recommendations for Security "...Choosing random quantities to foil a resourceful and motivated adversary is surprisingly difficult. ...recommends the use of truly random hardware techniques and shows that the existing hardware on many systems can be used for this purpose." PGP does not use "truly random hardware techniques" "...For the present, the lack of generally available facilities for generating such unpredictable numbers is an open wound in the design of cryptographic software. ... the only safe strategy so far has been to force the local installation to supply a suitable routine to generate random numbers. To say the least, this is an awkward, error-prone and unpalatable solution." - 1994 - after PGP was implemented. and then: "This informational document suggests techniques for producing random quantities that will be resistant to such attack. It recommends that future systems include hardware random number generation or provide access to existing hardware that can be used for this purpose." "...Systems like Kerberos, PEM, PGP, etc. are maturing and becoming a part of the network landscape [PEM]. These systems provide substantial protection against snooping and spoofing. However, there is a potential flaw. At the heart of all cryptographic systems is the generation of secret, unguessable (i.e., random) numbers. " (Internet RFCs are searchable at http://all.net) So I guess the RFC supports my contention and not yours.
Why (specifically) do you think the MIT version of PGP has no backdoors and is not subject to attacks such as the one outlined in my previous posting?
I think it has no backdoors because Jeff Schiller and I (among others) have looked closely at the random number generator code (he has taken a much closer look than I) and believe it to be secure. I also know that I did not put any backdoors into the code (but why would you believe me, I must be paid by the government to say this, right?)
You might be, but even if you are not, that doesn't mean there are no back doors. Your inability to detect a backdoor gives me little confidence, since this is at least an NP-complete problem and, with all due respect, today, nobody can prove that PGP is free of backdoors
As to why I believe it is not subject to attack, I ask you again to go read RFC 1750. PGP follows its recommendations fairly closely. There is only one place where PGP fails to follow, and that is that PGP does expose the bucket of random bits, rather than mixing them before exporting them. However I do not believe that this would affect the generation of PGP Public Keys.
But the RFC acknowledges that these methods are highly suspect and should not be trusted.
PS: In what field is your Doctorate?
Ph.D. Electrical and Computer Engineering, U. of Southern California, 1986, subject "Computer Viruses". My complete resume is available through the W3 server (below) under Management Analytics. -- -> See: Info-Sec Heaven at URL http://all.net Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236
[NB: Due to some as-yet-undiagnosed bugs in my .procmailrc, I apparently sent all my mail received between sometime Saturday and about 17:00 PT Monday straight into the bit bucket. *sigh* Archives are a Good Thing. If you sent me mail during that approximate period, please contact me again. Thanks.] Dr. Frederick B. Cohen writes:
Request for Comments: 1750 - Randomness Recommendations for Security
"...Choosing random quantities to foil a resourceful and motivated adversary is surprisingly difficult. ...recommends the use of truly random hardware techniques and shows that the existing hardware on many systems can be used for this purpose."
PGP does not use "truly random hardware techniques"
Correct. However, the excerpt of RFC 1750 you quoted above does not claim that all PRNG techniques are unreasonably insecure, nor does it suggest that they should never be used.
"...For the present, the lack of generally available facilities for generating such unpredictable numbers is an open wound in the design of cryptographic software. ... the only safe strategy so far has been to force the local installation to supply a suitable routine to generate random numbers. To say the least, this is an awkward, error-prone and unpalatable solution." - 1994 - after PGP was implemented.
I agree with the RFC's authors that mandating provision of platform- dependent routines is an awkward and unappealing strategy. Note, however, that they characterize it as "the only safe strategy". They say that the _strategy_ is error-prone; they do not say that all locally-supplied routines are unreasonably insecure, and should not be used.
and then: "This informational document suggests techniques for producing random quantities that will be resistant to such attack. It recommends that future systems include hardware random number generation or provide access to existing hardware that can be used for this purpose."
This is just a reiteration of the first section you quoted.
So I guess the RFC supports my contention and not [Derek Atkins']. [...] [re: PGP's key generation methods] But the RFC acknowledges that these methods are highly suspect and should not be trusted.
Where ? Give a citation, please. It doesn't say anything of the sort in the part you quoted previously. Furthermore, you inexplicably omitted all mentions of keystroke-timing PRNG techniques in RFC 1750. Here are some excerpts that strike me as particularly germane to the quality of the randomness in PGP: ------------------------------------------------------------------------ 4.2 Timing and Content of External Events It is possible to measure the timing and content of mouse movement, key strokes, and similar user events. This is a reasonable source of unguessable data with some qualifications. On some machines, inputs such as key strokes are buffered. Even though the user's inter- keystroke timing may have sufficient variation and unpredictability, there might not be an easy way to access that variation. Another problem is that no standard method exists to sample timing details. This makes it hard to build standard software intended for distribution to a large range of machines based on this technique. The amount of mouse movement or the keys actually hit are usually easier to access than timings but may yield less unpredictability as the user may provide highly repetitive input. [...] 6.2 Non-Hardware Sources of Randomness The best source of input for mixing would be a hardware randomness such as disk drive timing affected by air turbulence, audio input with thermal noise, or radioactive decay. However, if that is not available there are other possibilities. These include system clocks, system or input/output buffers, user/system/hardware/network serial numbers and/or addresses and timing, and user input. Unfortunately, any of these sources can produce limited or predicatable values under some circumstances. [...] The use of multiple random inputs with a strong mixing function is recommended and can overcome weakness in any particular input. For example, the timing and content of requested "random" user keystrokes can yield hundreds of random bits but conservative assumptions need to be made. For example, assuming a few bits of randomness if the inter-keystroke interval is unique in the sequence up to that point and a similar assumption if the key hit is unique but assuming that no bits of randomness are present in the initial key value or if the timing or key value duplicate previous values. The results of mixing these timings and characters typed could be further combined with clock values and other inputs. This strategy may make practical portable code to produce good random numbers for security even if some of the inputs are very weak on some of the target systems. However, it may still fail against a high grade attack on small single user systems, especially if the adversary has ever been able to observe the generation process in the past. A hardware based random source is still preferable. ------------------------------------------------------------------------- I find it difficult to reconcile your claim that "the RFC acknowledges that these methods are highly suspect and should not be trusted" with the RFC's assertions that: "the timing and content of [...] key strokes [...] is a reasonable source of unguessable data" "the timing and content of requested `random' user keystrokes can yield hundreds of random bits" "this strategy may make practical portable code to produce good random numbers for security" etc. Having said that, allow me to state my position on some of the other issues you've raised. I do not _know_ nor can I _prove_ that PGP has no cryptographic backdoors. I happen to _believe_ that it does not -- among other things, I have met Derek Atkins and Jeff Schiller, and I trust them in this regard. I don't consider that any reason for you to believe that it's backdoor-free. In fact, I'm not interested in trying to persuade you or anyone else that it is backdoor-free. By the same token, I don't see any reason for anyone here to heed your demands that they justify _their beliefs_ to _your satisfaction_. I remain rather baffled as to your motives in this mini-campaign. You said that no-one can prove PGP has no backdoors, and many here essentially said "what else is new ?". In the white paper about your small "secure" HTTP daemon, thttpd, (found at http://all.net/ManAl/white/whitepaper.html, to save you the trouble of more self-promotion ;), it says:
Proof of program correctness to verify even simple security properties, for example, grows almost exponentially with the number of program statements. Verifying a 100 line limited-language program for the simple security properties associated with the Bell-LaPadula model of security takes about 24 hours of CPU time on a Cray supercomputer. The source code for the NCSA W3 server in widespread use today is about 6600 lines long, so there is no computer around today that is likely to be able to verify its security (or more likely demonstrate its insecurity).
If we adopt this standard, it seems hopeless to "verify" the PGP source, as others have noted here. [BTW, I read your detailed code walkthrough for thttp with interest, and commend your work on that. I'm planning some sort of similar review for a larger piece of code, and it's encouraging to see other people pulling it off.] Nobody has suggested a serious, better-understood alternative to PGP as it is used today (except maybe 2.6.2ui (?), the current int'l. version, for merely MIT-allergic people :) So, in summary, we effectively can't know for sure that PGP is secure, but as a practical matter we have no choice but to accept it, albeit with varying degrees of caution. This is hardly novel. Did you have a point I missed somewhere ? Your good stuff tends to get lost in your rhetoric, recriminations, and advertising.... [On a largely unrelated note, why does http://all.net/admin/usepolicy.html contain the following warning ? Specifically, why the age limit ? "This service is ONLY for use by legally competent adults human [sic] individuals of age 18 or older. If you do not meet these criteria, you should immediately cease and desist your use of this service."] -Futplex <futplex@pseudonym.com> "...because of Dr. Cohen's frequent, blatant, and intentional disregard for the guidelines that this list operates under, and because of his apparent disregard for the frequently expressed opinions of many of the members of this list that they don't appreciate his antics, I've configured Majordomo to divert all messages he posts to Firewalls to the list owner for review and approval before posting..." -Brent Chapman, July 24, 1995
PGP does not use "truly random hardware techniques"
Correct. However, the excerpt of RFC 1750 you quoted above does not claim that all PRNG techniques are unreasonably insecure, nor does it suggest that they should never be used.
Nor do I.
"...For the present, the lack of generally available facilities for generating such unpredictable numbers is an open wound in the design of cryptographic software. ... the only safe strategy so far has been to force the local installation to supply a suitable routine to generate random numbers. To say the least, this is an awkward, error-prone and unpalatable solution." - 1994 - after PGP was implemented.
I agree with the RFC's authors that mandating provision of platform- dependent routines is an awkward and unappealing strategy. Note, however, that they characterize it as "the only safe strategy". They say that the _strategy_ is error-prone; they do not say that all locally-supplied routines are unreasonably insecure, and should not be used.
But in practice, PGP is not used this way by the masses. They use standard distributions withou alteration. ...
So I guess the RFC supports my contention and not [Derek Atkins']. [...] [re: PGP's key generation methods] But the RFC acknowledges that these methods are highly suspect and should not be trusted.
Where ? Give a citation, please. It doesn't say anything of the sort in the part you quoted previously. Furthermore, you inexplicably omitted all mentions of keystroke-timing PRNG techniques in RFC 1750. Here are some excerpts that strike me as particularly germane to the quality of the randomness in PGP:
That is my interpretation, however, reasonable people may differ...
------------------------------------------------------------------------ 4.2 Timing and Content of External Events
It is possible to measure the timing and content of mouse movement, key strokes, and similar user events. This is a reasonable source of unguessable data with some qualifications. On some machines, inputs such as key strokes are buffered. Even though the user's inter- keystroke timing may have sufficient variation and unpredictability, there might not be an easy way to access that variation. Another problem is that no standard method exists to sample timing details. This makes it hard to build standard software intended for distribution to a large range of machines based on this technique.
The amount of mouse movement or the keys actually hit are usually easier to access than timings but may yield less unpredictability as the user may provide highly repetitive input. [...]
Sounds like this is not very random - I agree that "the user may provide highly repetitive input". Just because one type of input is more repetitive, doesn't make the other truely random. ...
I find it difficult to reconcile your claim that "the RFC acknowledges that these methods are highly suspect and should not be trusted" with the RFC's assertions that:
"the timing and content of [...] key strokes [...] is a reasonable source of unguessable data"
You left out "with some qualifications". This is the part where I have concern.
"the timing and content of requested `random' user keystrokes can yield hundreds of random bits"
You missed the "but conservative assumptions need to be made" part. Hundreds of random bits are possible, but how many actual bits of content are contained in PGP input.
"this strategy may make practical portable code to produce good random numbers for security"
You missed the "However, it may still fail against a high grade attack on small single user systems, especially if the adversary has ever been able to observe the generation process in the past. A hardware based random source is still preferable." part and your reliance on the term "may" as "does" is overly optimistic.
Having said that, allow me to state my position on some of the other issues you've raised. I do not _know_ nor can I _prove_ that PGP has no cryptographic backdoors. I happen to _believe_ that it does not -- among other things, I have met Derek Atkins and Jeff Schiller, and I trust them in this regard. I don't consider that any reason for you to believe that it's backdoor-free. In fact, I'm not interested in trying to persuade you or anyone else that it is backdoor-free. By the same token, I don't see any reason for anyone here to heed your demands that they justify _their beliefs_ to _your satisfaction_.
Not demands - questions. Why is it that you are unwilling to take questions as questions and instead translate them into demands? You could have answered my questions without all the other side comments. Why didn't you? I interpret this as being defensive, which means to me that you are not as sure as you outwardly indicate and that there may be some lingering issues. So I ask more questions. You respond with more posturing and fewer answers, so I become even more concerned. It's probably my fault for not asking them in the way you are used to hearing them, or maybe we are all over-sensitive about our work.
I remain rather baffled as to your motives in this mini-campaign. You said that no-one can prove PGP has no backdoors, and many here essentially said "what else is new ?". In the white paper about your small "secure" HTTP daemon, thttpd, (found at http://all.net/ManAl/white/whitepaper.html, to save you the trouble of more self-promotion ;), it says:
Proof of program correctness to verify even simple security properties, for example, grows almost exponentially with the number of program statements. Verifying a 100 line limited-language program for the simple security properties associated with the Bell-LaPadula model of security takes about 24 hours of CPU time on a Cray supercomputer. The source code for the NCSA W3 server in widespread use today is about 6600 lines long, so there is no computer around today that is likely to be able to verify its security (or more likely demonstrate its insecurity).
Which is why we need very small programs (which PGP is not) that do the security-critical functions. We can then analyze these programs and determine many important properties with regard to their security, which we cannot do with PGP.
If we adopt this standard, it seems hopeless to "verify" the PGP source, as others have noted here. [BTW, I read your detailed code walkthrough for thttp with interest, and commend your work on that. I'm planning some sort of similar review for a larger piece of code, and it's encouraging to see other people pulling it off.]
Thank you, but I think it may be too hard to do for a much larger piece of code. There is another gentleman who is now working on formally (and automatically) verifying these properties. Perhaps his results will be of value in your problem and similar problems for other programs. ...
[On a largely unrelated note, why does http://all.net/admin/usepolicy.html contain the following warning ? Specifically, why the age limit ?
"This service is ONLY for use by legally competent adults human [sic] individuals of age 18 or older. If you do not meet these criteria, you should immediately cease and desist your use of this service."]
I think that some of the popular literature sections may be considered pornography (Fanny Hill, the Kama Sutra, etc.) and in order to comply with the applicable laws, I thought it would be prudent to warn off our fragile youth.
"...because of Dr. Cohen's frequent, blatant, and intentional disregard for the guidelines that this list operates under, and because of his apparent disregard for the frequently expressed opinions of many of the members of this list that they don't appreciate his antics, I've configured Majordomo to divert all messages he posts to Firewalls to the list owner for review and approval before posting..." -Brent Chapman, July 24, 1995
And if enough of those on this list feel that this discussion and my postings are too commercial or too abusive to take, I am certain that Brent will send you a free copy of his Fred filter. -- -> See: Info-Sec Heaven at URL http://all.net Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236
Dr. Frederick B. Cohen writes:
It's probably my fault for not asking them in the way you are used to hearing them, or maybe we are all over-sensitive about our work.
Since I've had no involvement in the writing of PGP and RFC 1750, I don't think I'm being sensitive about my work :] [...]
And if enough of those on this list feel that this discussion and my postings are too commercial or too abusive to take, I am certain that Brent will send you a free copy of his Fred filter.
Nah, we're not into third-party censorship here. As for myself, I intend to keep reading what you write here. Your manner is not a legitimate reason to ignore the value of (some of) your words. -Futplex <futplex@pseudonym.com>
-----BEGIN PGP SIGNED MESSAGE-----
"warlord" == Derek Atkins <warlord@mit.edu> writes:
warlord> This is where you are very wrong. I am not saying that "if warlord> you can't find any holes it must be secure". What I am warlord> saying is that the source is available, and thousands of warlord> people have looked at the source, and none of them have warlord> found any holes in it. While I largely disagree with Dr. Cohen's conclusions, I do think we should extinguish the "Examine the source!" mantra. I find it surprising that people so familiar with public key cryptography would be reassured by the argument, "Here, this algorithm has been examined by thousands and nobody has found a trap door." Public key cryptography demonstrates that it is possible, in principle, to construct an algorithm with a trap door that nobody else is *ever* going to find. I wonder whether Rivest could construct a hash function which only he could invert... :-) When an algorithm is essentially defined by a tangle of C code, like the PGP random number generator, the "Examine the source!" mantra becomes even more hollow. Ironically, the fact that it was designed by competent cryptographers potentially makes it even more dangerous. Of course, there is no practical alternative at this time. Maybe someday your entire operating environment will be formally proven correct, and the cryptographic algorithms will be provably as hard as factoring, and factoring will be proven hard, and the system will ask you to flip a coin and type "0" or "1" every time it needs a random bit. But until that day, you will have to decide whom to trust. Personally, I trust the authors of PGP. So do most of the people on this list, I suspect. Maybe Dr. Cohen can convince me that my trust is misplaced; but to do so, he will need something better than NSA conspiracy theories. -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Processed by Mailcrypt 3.3beta, an Emacs/PGP interface iQCVAwUBMB5IU3r7ES8bepftAQGRvQP+Masb3fWdJg9UA6YYufuVZ5EZU8wfhuar IXpjID+iSyVV1UnMN5CiWj8912H3buUslygVnbCwv/vnuKdtz5h9k2+lpCUX4r11 2QVAWg4ij1LiA1DU7N2l2K4oqb5mszVZrQcW6aJJzqiuPcvij5Vl7cN3hDTfdttJ x9emd0xEjPA= =nxBy -----END PGP SIGNATURE-----
"Patrick J. LoPresti" writes:
I find it surprising that people so familiar with public key cryptography would be reassured by the argument, "Here, this algorithm has been examined by thousands and nobody has found a trap door." Public key cryptography demonstrates that it is possible, in principle, to construct an algorithm with a trap door that nobody else is *ever* going to find.
This is not correct as you have phrased it. Although it is not possible to find a decision proceedure for any non-trivial property of programs in general (whether it halts, for example) in practice well written code can be well understood and cannot conceal very much at all. In order to use public key cryptography to obfuscate a program as you suggest, you'd have to include huge tables of large numbers in it. Any idiot can observe the existance of such mysterious tables. Trying to conceal anything in cleanly written code is an enormous challenge, and one that has nothing to do with public key crypto per se. Incidently, this doesn't mean that you can't conceal things by producing subtle flaws in, for example, random number generation code. However, such flaws are hardly of the form "nobody else is *ever* going to find" -- anyone being extremely cautious in his analysis will find such flaws. .pm
-----BEGIN PGP SIGNED MESSAGE-----
"perry" == "Perry E Metzger" <perry@panix.com> writes:
perry> "Patrick J. LoPresti" writes:
I find it surprising that people so familiar with public key cryptography would be reassured by the argument, "Here, this algorithm has been examined by thousands and nobody has found a trap door." Public key cryptography demonstrates that it is possible, in principle, to construct an algorithm with a trap door that nobody else is *ever* going to find.
perry> This is not correct as you have phrased it. On the contrary, it is *precisely* correct as I have phrased it. perry> Although it is not possible to find a decision proceedure for perry> any non-trivial property of programs in general (whether it perry> halts, for example) in practice well written code can be well perry> understood and cannot conceal very much at all. Check my phrasing again. Note the use of "in principle". Whether the principle applies in practice is certainly a matter for debate. I would point out that 1) PGP is hardly well written code, and 2) many current cryptographic algorithms make ideal places for concealing all sorts of things. perry> In order to use public key cryptography to obfuscate a program perry> as you suggest, you'd have to include huge tables of large perry> numbers in it. Any idiot can observe the existance of such perry> mysterious tables. Sorry, I can't resist. From "md5.c" in the PGP distribution: /* * Start MD5 accumulation. Set bit count to 0 and buffer to mysterious * initialization constants. */ void MD5Init(struct MD5Context *ctx) { ... (Note: Of course I don't think that MD5 has a back door, but that has more to do with my trust of Rivest than the fact the algorithm is public.) perry> Trying to conceal anything in cleanly written code is an perry> enormous challenge, and one that has nothing to do with public perry> key crypto per se. By "cleanly written code", I presume you mean code which is either formally proven to be a correct implementation, or code which is so transparent that it is "obviously" a correct implementation. PGP's random number generator is neither. Moreover, as I precisely mentioned, the algorithms themselves can conceal back doors. This has plenty to do with public key cryptography. A reduction proof from a known hard problem would make this virtually impossible, but there is no such proof for PGP's random number generator. (Nor for any other algorithm used by PGP, although I admit RSA comes close.) -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Processed by Mailcrypt 3.3beta, an Emacs/PGP interface iQCVAwUBMB5XVXr7ES8bepftAQGkJgP9Gopf96k2vu5ORjqQCOk0hPNrdwtmcR71 THm+nPgWk2m1CHGXHF3FhgZ7FNZS8zubv1fzunKA+QDFcqKghHCFfhD+pof4bUF6 fYVq89Oc3P7/pIvS3pCR8BBN/8BTLwxlP+OsPbF4YNANXqsbiqyjvezruojKaOI8 QiVInZxdeoI= =BfP6 -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE-----
"warlord" == Derek Atkins <warlord@mit.edu> writes:
warlord> This is where you are very wrong. I am not saying that "if warlord> you can't find any holes it must be secure". What I am warlord> saying is that the source is available, and thousands of warlord> people have looked at the source, and none of them have warlord> found any holes in it.
While I largely disagree with Dr. Cohen's conclusions, I do think we should extinguish the "Examine the source!" mantra.
I find it surprising that people so familiar with public key cryptography would be reassured by the argument, "Here, this algorithm has been examined by thousands and nobody has found a trap door." Public key cryptography demonstrates that it is possible, in principle, to construct an algorithm with a trap door that nobody else is *ever* going to find. I wonder whether Rivest could construct a hash function which only he could invert... :-)
That's a neat metaphor, but it doesn't always apply. It shouldn't apply to algorithms which are primitive recursive. Elementary algorithms like multiprecision add, sub, multiply, divide, modmult, and modexp (the basis of public key encryption) are all provably correct and all terminate. (the basis is polynomial operators over a ring) It is possible to verify the implementation (assuming the correctness of the compiler). Now there could be a "factoring" trapdoor in RSA, but that's a trapdoor not in the implementation of PGP, but in the algorithm itself. RSA-in-4-lines-perl is probably provably correct. To guard against trapdoors in PGP, you should verify the correctness of the PRNG, Key Generator, and that no private key bits or session key bits are leaked. I would suspect this could be difficult, but approximations could be determined to within a high degree of confidence. -Ray
-----BEGIN PGP SIGNED MESSAGE-----
"rjc" == Ray Cromwell <rjc@clark.net> writes:
rjc> That's a neat metaphor, but it doesn't always apply. It rjc> shouldn't apply to algorithms which are primitive rjc> recursive. Elementary algorithms like multiprecision add, sub, rjc> multiply, divide, modmult, and modexp (the basis of public key rjc> encryption) are all provably correct and all terminate. (the rjc> basis is polynomial operators over a ring) It is possible to rjc> verify the implementation (assuming the correctness of the rjc> compiler). Now there could be a "factoring" trapdoor in RSA, but rjc> that's a trapdoor not in the implementation of PGP, but in the rjc> algorithm itself. RSA-in-4-lines-perl is probably provably rjc> correct. To guard against trapdoors in PGP, you should verify rjc> the correctness of the PRNG, Key Generator, and that no private rjc> key bits or session key bits are leaked. I would suspect this rjc> could be difficult, but approximations could be determined to rjc> within a high degree of confidence. As I suggested, you could 1) only use algorithms which are provably as hard to break as known hard problems, and 2) only use implementations which are proven correct. PGP does neither. In addition, the complexity of the source makes #2 difficult even to approximate. Now, we could certainly take care of #1 fairly easily by using a different set of algorithms. And as you suggest, #2 can be approximated if the code is written cleanly. But this would be a big project, and it would not be PGP. I personally would find such a project pointless, since I trust PGP enough for my needs. The availability of the source is a necessary prerequisite for that trust, but it is by no means convincing. -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Processed by Mailcrypt 3.3beta, an Emacs/PGP interface iQCVAwUBMB5cZHr7ES8bepftAQFtBwQA2qDiS0BpvkFBj9HRRd/83OxjSczna/jn wj5eb+2KMSbj87SuD3ByUFcXQmWIqO6bNq5CkzoxmGvrk/y1futjAF/BeGcVlM1+ T4ClfmrIFbqwd/j7i1Qaw7ExN6rNjgQUdRYmo8Nlr1JVaAymCtx2f4GqKRuwP3oy Tc/W8GXThM0= =qdFB -----END PGP SIGNATURE-----
Agreed. If PGP has a hole it in it's not in the sources, nor in the executables. Any hole would be a breaking of the RSA or IDEA cyphers by the TLA's who wouldn't talk about it, or the availablity of enough super fast hardware to brute force it. It wouldn't be that PGP, it's sources, or algorithms have holes. It would be that there is a way to factor RSA that as of yet we don't know about. And hell, that's as likely as meeting Elvis at your local 7-11. ;-) =================================================================93======= + ^ + | Ray Arachelian | Amerika: The land of the Freeh. | \-_ _-/ | \|/ |sunder@escape.com| Where day by day, yet another | \ -- / | <--+-->| | Constitutional right vanishes. |6 _\- -/_ 6| /|\ | Just Say | |----\ /---- | + v + | "No" to the NSA!| Jail the censor, not the author!| \/ | =======/---------------------------------------------------------VI------/ / I watched and weeped as the Exon bill passed, knowing that yet / / another freedom vanished before my eyes. How soon before we see/ /a full scale dictatorship in the name of decency? While the rest / /of_the_world_fights_FOR_freedom,_our_gov'ment_fights_our_freedom_/
This might be a minor thing, but could people posting to the mailing list please make sure that the Subject line doesn't say "re: your mail". it really slows me down to have to check manually what the actual subject was or if it was directed to ME but put my addres in the cc instead of the To. Thankyou. Syed Yusuf http://www.uidaho.edu/~yusuf921
participants (10)
-
Andy Brown -
Derek Atkins -
fc＠all.net -
futplex＠pseudonym.com -
lmccarth＠cs.umass.edu -
Patrick J. LoPresti -
Perry E. Metzger -
Ray Arachelian -
Ray Cromwell -
Syed Yusuf