- cypherpunks-legacy - lists.cpunks.org

PGP bug *NOT* yet fixed
by Ben.Goren＠asu.edu 17 Dec '03

17 Dec '03

Y'all remember that bug that Colin Plumb told us about in the true random number generation part of PGP? It's still there, in the version from net-dist.mit.edu, as of late yesterday evening. There is *no* mention of the bug anywhere, in any readme files, in the documentation, anything. This strikes me as irresponsible. I would expect PGP 2.6a to have been released the day of the announcement, with the bug fixed. If there's some reason why that couldn't be done, then at least there should be some sort of prominent notice detailing the change, and probably a diff file--or even a simple shell script--to apply the (very simple!) fix. The signature on the following file checks as follows: >File has signature. Public key is required to check signature. . >Good signature from user "Colin Plumb <colin(a)nyx.cs.du.edu>". >Signature made 1994/06/01 14:04 GMT That's a month and a half ago. The *only* copies of PGP 2.6 out there that are free of the bug are those that have been fixed by hand. That's probably not all that many of them. I'm going to bite the bullet and paste in the original message here. Feel free to flame me if this is unnecessary re/cross-posting, but I'm not aware of any place to get this aside from digging through archives, and.... b& -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.5 mQCNAi3L864AAAEEAKRe8j9QUqL4PDQSsliTKQ0yTkdLL8BFBm7c03RC9Ol5PP9K j/RtnsdxFMTtW7wkMwTpY1jF23HR+x54LrOpi8ig6HEmiXVVWuNByRjSMgz8jvrn MM0/tIOCPAgNMxiANUWqretPEWCZE9sLbylkJrrOd54ZKyXBTw/D7AL7u4qxAAUR tCFDb2xpbiBQbHVtYiA8Y29saW5Abnl4LmNzLmR1LmVkdT6JAJUCBRAtyxCUZXmE uMepZt0BAeiyA/4tNXz6loqEwyMv65TMGtqxTlT5ocGNzyE8mkZXvbmoS0m7sdsd aVBvHfK8lrkQz/anrzAHJMBOaZ0V6T7aCLAK6GnjHoeanP8ZyhaXpc2e7EVut4Zi hCpmq45uiA/1diwLXhC8OoHwKqZDT+uNnJLLdlAzrJiOaELAzXXeOvtMXokAYAIF EC3L/BnKPaH9hlqn8wEBXWgCWMgIh8Lsww5pFHRFbAe2HehjGIiOmQ+ZcnL3pOhw tLdoGm6lqWZ4njDSTULxDpKUtbe4pWNv6Go13t9p+1GmTh+RrnGoq6rs3Mlg+IkA lQIFEC3L+zgPw+wC+7uKsQEBDZkEAJYkHK5n02GXLwEEgFKpxQvWLqI2xz33rPDa 0eT6+RYMDcr/1vzTqX7CwNpCuTaFTVNRbRznvwNTDcQXVsnyPg5yGdRIIMPnWuGf gSEP7vjm8zzvfdh5te4ag6jobCN1PVyqIIxIV5S8iPv632gm4vQboJiQ+4+53qoS WJ6BNDq9 =Wjfi -----END PGP PUBLIC KEY BLOCK----- -----BEGIN PGP SIGNED MESSAGE----- I have the unpleasant task of reporting a significant bug in PGP's random number generation (for making primes), and that it's my fault. It *is* a significant problem, although it is *not* end-of-the-world severity. That is, the code is not doing performing as intended, and the results aren't as random as intended. On the other hand, this does not appear to make any generated keys easier to break. Because it has to do with random-number generation, there are no interoperability issues raised. Please read on for details. Thanks to the many people who have submitted other bug reports and porting patches. A new release from MIT is forthcoming with more cleanups. * The Bug In pgp 2.6 (and 2.5), there is a file named "randpool.c", which accumulates entropy from keyboard timings. These random numbers are used in generating session keys, although the primary random number generator for session keys, based on IDEA, is unaffected. The main use of these random numbers is the much more sensitive task of generating RSA secret keys. In that file, a tiny helper function is xorbytes: static void xorbytes(byte *dest, byte const *src, unsigned len) { while (len--) *dest++ = *src++; } A character is missing. '^', to be precise. That "=" should be "^=". I wrote it, and I knew when I was writing it that it was critical code. Since you can't test a random-number generator (except for the most trivial of flaws), you have to walk through the code very carefully. I did, or thought I did, yet still managed to miss this. Oops is too mild. That code is not supposed to have ANY bugs. In other words, I screwed up. There's a lesson in there somewhere. I'll try to learn it. * The Effect The randpool.c code works by maintaining a pool (buffer) of random bits and adding in new "noise" from the environment each time a key is pressed. This "adding" is done by exclusive-oring it with successive bytes from the existing pool. When the pool is "full", a cryptographic stirring operation is performed to mix all the information in the pool together and get ready for new noise. The bytes in the pool at the end are intended to be uncorrelated with the noise bytes that will be added, so the XOR adding does not cause any sort of "cancellation" of information. This stirring is done with a key, which is taken from the pool at the end of each pass. With the bug in place, the noise bytes *replace* the bytes in the pool rather than being added to them. So the information that was in the pool is obliterated. The only trace that remains is what's stored in the key. This is at most the size of the key, 512 bits, rather than the size of the whole pool, 3072 bits. PGP tries to ensure that generated RSA keys are completely unpredictable by accumulating enough Shannon information to make the whole key. Thus, infinite computational power would not let you predict a generated secret RSA key. This bug subverts that. * Security Analysis What effect does this have on someone's chances of breaking an RSA secret key generated with PGP 2.6? Not much, as far as I can tell. But it requires more careful thought and that eats into the comfort margin that should be there. Just for comparison, the RSAREF library's random number generation routines are also based on MD5, but use 16 bytes of seed. Successive random bytes are taken by computing the MD5 hash of the 16-byte seed, using those 16 bytes, incrementing the seed by 1 (taken as a 128-bit number), and repeating. Taking the MD5 of a 16-byte value involves one pass of the MD5Transform function, with 16 of the 64 key bytes unknown, 48 bytes are known (fixed, in fact), and the input hash is known (fixed, in fact). Compared to this, PGP 2.6, even with the bug, is excellent. All 64 bytes of key to MD5Transform are dependent on all of the seed, the input hash varies widely, and the output is XORed with some difficult-to-predict data. The reason that you can get away with less than perfect random numbers (less Shannon information than the size of the generated key) is that you only have to make sure that the weakness does not make any attack easier than the best known attack without the weakness. As long as guessing is only useful to a brute-force attack, it remains far easier to factor. Paul Leyland estimated that the work to try all possible 128-bit IDEA keys is equivalent to factoring a 3100-bit RSA key. Now, recent work by Arjen Lenstra on the number field sieve (Paul Leyland was assuming the MPQS used in RSA-129) has raised this RSA key length somewhat. Thus, an argument can be made in favour of RSAREF's use of a 128-bit random number seed, since that's all that is necessary. PGP prefers to be a little bit more paranoid. Still, once you have 512 bits of uncertainty, trying all possibilities is more work than trying to break a 1024-bit RSA key by trial division. So let's see just how much entropy is in there. Each keystroke, the following data is added to the random pool: - - The cahracter typed, an int (2 or 4 bytes) - - the time_t result of time() (4 bytes) - - the clock_t result of clock() (4 bytes) - - On MS-DOS, 2 bytes of hardware timer 0 - - On Unix, 8 bytes of gettimeofday() and 20 bytes of times() results - - On VMS, 8 bytes of high-resolution timer. The total is 12 bytes on MS-DOS, 32 bytes on Unix (this may vary, but that's very common), and 20 bytes on VMS. The information content of the bytes is taken at a maximum of 8 bits, although it's actually closer to 15 bits on MS-DOS, and less (maybe as low as 1 or 2) on a Unix system with a fast typist and a slow (60 Hz) clock. VMS is in between. This means that the entropy density in the added bytes varies from 1/12 (or better) in MS-DOS to 1/256 on Unix. Thus, the content of a pool's worth (3072 bits) is 256 bits (or more) under MS-DOS and may be as low as 12 bits on some flavours of Unix. The random number accumulation operation adds bytes to the pool until it is either full or the desired number of bits have been accumulated. Then it stors the pool. For a maximum-sized key (1024 bits), it will take many passes through the pool to accumulate the entropy, but owing to the bug, each time the pool is overwritten with the most recently collected data. The only entropy that remains from the previous pass is in the 512-bit key buffer. This applies to every stirring pass until the last, after the last noise data has been added and new data is about to be withdrawn from the pool. This last pass is very likely to be incomplete; some of the data at the tail of the pool is probably not overwritten. This can carry over extra entropy from the previous pass. No more than is there (the 12 to 256 bit range observed before), and then you have to add an unknown fraction of that for data that has been added in the current pass, but the total will vary from 12 bits (an average of 18) to 256 bits (an average of 384). Plus the entropy preserved in the key buffer. So there is from just over 512 to an average of 896 bits of entropy in the pool. 1016 random bits are used to make the starting values for the two primes in a 1024-bit key. This is clearly not the perfect Shannon entropy PGP aims for. As long as the stirring operation is still considered cryptographically strong, this reduction in the possible range of generated keys is not useful to a factoring algorithm, so it doesn't make a factoring attack any easier, yet a factoring attack is still far easier than a guessing attack, so the easiest attack is no easier. So I don't think anything is more attackable. Still, it's NOT what was intended, and that's always bad. My apologies to users of PGP. - -- -Colin -----BEGIN PGP SIGNATURE----- Version: 2.5 iQCVAgUBLeyVSw/D7AL7u4qxAQEjCQP/YlzY5DWT4FrSErQ8W0TP9ibRqpck4gKL YOkUgiMQnvCE2XHEvP1VTfUANgU9O/P7lClJ1oaOXIEbt5GW45DAVPgSZk5PoJ10 TZ5Ly4wqDzMa8YLDu4I2l2Use5wwIIYl5IbGEdZiRlYdox7eWaGRLfOiA8CPVb9p yZ7PgFZU10Y= =Bj83 -----END PGP SIGNATURE----- -- Ben.Goren(a)asu.edu, Arizona State University School of Music net.proselytizing (write for info): Protect your privacy; oppose Clipper. Voice concern over proposed Internet pricing schemes. Stamp out spamming. Finger ben(a)tux.music.asu.edu for PGP 2.3a public key.

1 0

Sue D. Nym
by merriman＠metronet.com 17 Dec '03

17 Dec '03

I trust that everyone got the joke: Sue D. Nym = pseudonym Dave Merriman Wherever you go in Life - there you are!

1 0

Re: PGP bug *NOT* yet fixed
by jis＠MIT.EDU 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Chill out friend. We are working on a bugfix release to PGP which will fix several important bugs. The bug you mention is fixed in our development sources and will be fixed in the next release. Read Colin's note carefully. If you do you will realize that this problem is not a disaster. The reason that you need good random numbers for cryptographic purposes is to make an exhaustive search through all possible values of a key too hard to do. There is more then enough randomness in the random pool even with this bug to prevent someone from being able to search all possible values. -Jeff -----BEGIN PGP SIGNATURE----- Version: 2.6x iQBVAgUBLinTiVUFZvpNDE7hAQGm2QH/S7uvlJMUGeYNTncQ9rvr0Dkowjto2GG7 Pi+f0cLlUGTfDNTtAlSdao0HxwT5uv2PUwXMAd6Cns3uo3ordRiP1Q== =9BZ3 -----END PGP SIGNATURE-----

1 0

Re: Nixon, Johnson, and the Dollar
by Blanc Weber 17 Dec '03

17 Dec '03

From: Sandy Sandfort "When the government makes any announcement (ESPECIALLY a denial), you should figure out what the government is trying to get you to do. . . . . . " ...................................... I think this is what is called "providing incentive" or in corporate-speak, "incentivization" (when they make an announcement and you take the kind of action which they intended you should). Blanc

2 1

Re: Key length security (calculations!)
by Hal 17 Dec '03

17 Dec '03

solman(a)mit.edu writes (quoting someone else initially): >> You mention Shamir, etc. However I would point out that even if any of the >> original RSA mathematicians found a better factoring algorithm, they'd be >more >> than likely to keep it under lock and key. The obvious reason is that their >> money supply depends on such an algorithm being suppressed. >What about Shamir's triple pass key exchange protocol (explained briefly >below). Its the perfect key exchange algorithm. It obsoletes Public key >systems entirely as long as you only need to exchange keys and not >authenticate. I'd say that is pretty decent evidence that he does still >do things to help the field when it might hurt RSADSI. (although I wouldn't >say the same thing about all of them) I suspect this protocol is covered by the Diffie-Hellman patent, which is quite broad, covering many sorts of key exchanges. Diffie-Hellman is now owned by PKP, the sister company to RSA. If so, Shamir has not undercut his own financial interests by this work. (Also, this does not obsolete PK since it requires several exchanges before communication can occur, making it inappropriate for high-latency communications, such as for most email.) Hal

2 2

Federal Control of Financial Transactions
by frissell＠panix.com 17 Dec '03

17 Dec '03

As regular readers will be aware, Tim May and I have been sparring with each other about the risks of various control strategies that the world's governments may deploy. I thought it might be helpful to make one of his fears concrete so that we can analyze it. I trust that I am not putting words in Tim's mouth. The major concern is the same one mentioned in the Book of Revelations: "REV 13:16 And he causeth all, both small and great, rich and poor, free and bond, to receive a mark in their right hand, or in their foreheads: REV 13:17 And that no man might buy or sell, save he that had the mark, or the name of the beast, or the number of his name." So the Feds deploy a card (smart or dumb) that has to be used for most transactions and lets them track everything we do. Tourists are brought into the system through the use of temporary cards (or the machine-readable strip on their passports which already includes a space for a national ID number.) How is this most likely to come about? I consider force majeure to be unlikely. It would be rough to get Congress to impose a burden like this on businesses (who would have to completely wire themselves) in a formal vote. It is not necessary to do this in any case since they know they can't snag everyone into the system. They just want to capture most of the transaction data. If they can do it administratively without involving Congress in controversy, they will use that approach. Clipper and the Post Office agitprop on the US Card give us a possible scenario. The P.O., desperate to find a reason to exist as its core business drains away to the wires and private carriers, would like to become the primary digital signature authorizers for the U.S. It claims to be able to put millions of "US Cards" in the hands of happy shoppers within months of the go-ahead. (Assuming they use FedEx for the actual *shipments* of course). The recently attempted "Clipper maneuver" of game strategy (government preemption by standard setting rather than by direct application of force) shows us how the US Card system might be actually deployed. The government adopts the standard it likes and tries to make it the de facto standard by requiring it for most official business. An instant market is thereby created. No congressional action required. Similarly, the government might try to preempt the market for digital signature and commercial encryption technology by deciding to make anyone who wants to use a digital signature system in dealings with the government use the Post Office or some such agency as the signature authenticator. Thus bids, purchasing, benefits, and taxes could all require your "US Card" registered at your local post office. The government would then hope that commercial users who would need to use the government's system for tax filings anyway would also use it for its ordinary dealings with the public. Then if a health care bill drafting you into a "universal coverage" army is ever passed, the "US Card" also becomes the Health Security Card you will have to show to get a job in the US. Thus, all sorts of authentication transactions would pass through the powerful and efficient post office data network and the ex-countercultural/born-again control freaks Inside the Beltway could get their jollies tracking your employment and purchases. What's the big hole in this frightening scenario? Ask yourself one question. Why is the Post Office looking around for some useful work these days? Didn't they have a monopoly guaranteed by the Federal Government for more than 100 years? If they couldn't make a go of it with a pure coercive monopoly during a time of slower commercial activity, what makes them think that they can compete *without* a genuine coercive monopoly in a time of constant change. Governments have proved over and over again that they can go broke running "guaranteed" money spinners like state lotteries and such. They don't stand a chance in a marketplace that will break the hearts of the brightest people this planet has ever produced. What has recent history established? Governments are weaker. Why didn't the Amin mandate Clipper? No political ability to do so. Why are banks and telecoms being deregulated in nearly every country on earth (in spite of propaganda about "risks" and "public needs"? Why have exchange controls (a common feature of life a generation ago) become impossible almost everywhere on earth? Is it "free market ideology" that has triumphed or did the *reality* of markets rather than the *idea* of markets hit governments on the head. To those who romanticize the power of the State in the modern world I ask, why doesn't Clinton impose wage and price controls, exchange controls, tariffs, and a full-blown industrial policy? Why doesn't he nationalize the steel industry, guarantee jobs for all, confiscate all estates above $100,000, impose 95% income taxes on those making more than $40,000/year, and all of the other proposals that were popular earlier in this century? I doubt that he is restrained because of his deep commitment to human liberty. He doesn't do it because he can't. Markets wouldn't put up with it. His government would be destroyed (by capital flight.) In this connection, I invite everyone to read the excellent profile of Japan in last week's Economist. It discusses the current and growing Japanese commitment to deregulation and what is driving it. That issue is a keeper anyway because of an article on commerce on the Internet and (as has been mentioned before) the use of the word "anarcho-capitalism" in an article comparing Thailand and Singapore. Assuming that the government were to attempt to establish a Post Office mediated digital authentication system, there is no guarantee that it would work. Foreign users would presumably use foreign systems to authenticate their transactions. Some of these systems might be run by privatized foreign PTTs or by others. Note that since banks and credit agencies will still have to approve the transactions anyway (to make sure you've got the dough), they may decide to use other systems for signature authentication. It would not really cost them any more. Since information is cheap, setting up a system to use several authentication systems is almost as easy as setting up a system to use one. (Particularly since you have to do it anyway.) It is difficult to imagine the P.O. being able to compete in the cutthroat world of credit processing. Recall that even today, there are companies that pick up and deliver your mail to the P.O. to speed the process along. Similarly, expediters may interpose themselves between the customer and the P.O. to speed authentication in the even that the P.O. network is slow or inefficient (likely). Here again, Clipper gives us some hints as to how the attempted market cornering might work out in practice: The Admin is currently floating stories about perhaps withdrawing Clipper in favor of "wider discussions" with the industry. Clipper is already painfully obsolete and it isn't even shipping in quantity. Inefficient government monopolies create marvelous profit opportunities for markets to arbitrage the gap between cost and price. In a highly efficient networked world, it will be very difficult for governments to compete. DCF Why Pizza Hut should hire *me* as their spokesman: "Why does Pizza Hut oppose mandatory, employer-paid health insurance in the US even though we are forced to pay it in Japan and Germany? We support the principle of cultural diversity under which different societies experiment with different methods of social organization. Germany and Japan have chosen one road, we have chosen another. Pizza Hut would not voluntarily impose on our US customers the burden of the very high food costs that the agricultural policies of Germany and Japan impose on their citizens. Similarly, we would not choose to impose on our US employees the burden of bureaucratically designed employment contracts. Pizza Hut supports the right of our customers to enjoy the least expensive and best pizza on earth and the right of our employees to bargain with us collectively and individually concerning the conditions of their employment."

2 1

Re: Detweiler Remailer filtering
by qwerty＠netcom.com 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Hal told the oral history of my remailer as... >I suggest, then, that you run a remailer (it only costs $20 a month on the >system I use), and publicize the fact that Detweiler can use yours with >impunity. Set up a mail-to-news gateway that other remailer operators can >use so that they don't have to worry about the consequences of abuse. >It's easy to talk about sacred ideas, but perhaps not so easy to keep an >unpopular and misunderstood remailing infrastructure in place. "Xenon" >also accused us of hypocrisy, started up a remailer, and stopped it in just >a couple of days faced with these kinds of problems. However, I experienced *no* abuse of my remailer, I being at the time on fairly good terms with Mr. Detweiler. (I had a single amusing "abuse" in which the person told someone in personal anonymous mail that their continued us of their IP number was a copyright violation and would be procecuted. Guy just didn't have a sense of humour.) I did not accuse anyone of hypocrisy. All I said was that a simple quick fix solution of blocking his known address would ONLY MAKE THINGS WORSE, since then he would forge mail instead. Besides, fight him and he'll fight back with renewed energy, I reasoned. I also thought it was sort of funny to see all the propellor-beenie types yelling at the top of their lungs about some inappropriate posting in their oh so precious newsgroups, and said that his posts could be called performance art. I said we needed an *abuse* filter not a Detweiler filter. This of course got me flamed :-). I shut down qwerty-remailer, after perhaps a month of operation, due to two reasons. I felt moderated remailers were necessary (until Usenet is "fixed" to catch such abuses in some open moderation scheme) and did not have the *time* to moderate qwerty. The major reason however was the public threats of other remailer operators sending *their* abusive user's mail through qwerty-remailer when I refused to block Detweiler's address! That threw me for a loop. Wow. Nasty situation that was, and an isolated remailer is not an effective one. I also was not at all effective at trying to gather FULL information about the existing remailers, and my "Full Discosure Remailer List" is still incomplete, as well as now outdated. -=Xenon=- P.S. If anyone is interested in a few radical essays on remailer/internet security from an output larger than the internet, see the Rant Series on ftp.netcom.com in /pub/qwerty/Writings. -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLinKgQSzG6zrQn1RAQE7JwQApnXmm35jUxq0QyAYEN+pJgPxnQE5Jcqz RJfMKNjNT/1LDkgRvKoJxCoYfzd9ga/nQvIZczwefAPI2Ko8Q7bLMh1zm/txZzN7 RnCVd8Hdhq9UpPue3rwZ037jRc6K/XTEwgeKT9Ct3tmIJDbu5FyMqsK4asT4fgFi b/8h2TZG7ks= =FemC -----END PGP SIGNATURE-----

1 0

Re: Card Playing Protocol?
by kentborg＠world.std.com 17 Dec '03

17 Dec '03

rarachel(a)prism.poly.edu writes some interesting looking details on crypto cards, but I am too exhausted to make sense of it tonight. I am not ignoring it. Thanks, -kb -- Kent Borg +1 (617) 776-6899 kentborg(a)world.std.com kentborg(a)aol.com Proud to claim 35:00 hours of TV viewing so far in 1994!

1 0

Re: Card Playing Protocol
by kentborg＠world.std.com 17 Dec '03

17 Dec '03

rarachel(a)prism.poly.edu writes about problems with card protocols, >Anyway, you can ask him about it, his address is rvslyke(a)prism.poly.edu I will once I am sure I will understand the answer. Thanks, -kb, the Kent who does have some reading ahead of him -- Kent Borg +1 (617) 776-6899 kentborg(a)world.std.com kentborg(a)aol.com Proud to claim 35:00 hours of TV viewing so far in 1994!

3 2

Encrypting fax machine
by John Young 17 Dec '03

17 Dec '03

Pointer: Encrypted fax patent Publication: The New York Times, July 18,, 1994; Business Section D; Patents column; p. D2. Title: A small Company offers a scanning device to make faxes private by encoding their computer bits. By: Sabra Chartrand Some excerpts: The Kryptofax Corporation . . . was set up to sell a scanning device that uses encryption algorithms to turn fax text into indecipherable dots on a page. *** Then the most critical thing is to provide a password, says Richard Varga, a former computer programmer who is the president. *** The encoded page emerges with the title and addressee name appearing in plain language at the top. The rest is a grid of random dots. *** As the [receiving] Kryptofax machine reads the encrypted grid, it begins simultaneously to print a decrypted version of the page. *** We use an encryption algorithm called seeded pseudo-random number generator, Mr. Varga said. The company chose that algorithm because it is in the public domain, he added. *** The Kryptofax Corporations's patent is 5,321,749.

1 0