- cypherpunks-legacy - lists.cpunks.org

Re: Weakness of the PGP scheme ?
by ghsvax!hal＠uunet.UU.NET 04 Dec '92

04 Dec '92

Vanguard(a)gribb.hsr.no asks about trying all the IDEA keys. If you will look in idea.h you will see that the IDEA key is 16 bytes long, which is 128 bits. This is long enough to make trying them all impossible. Trying to predict one IDEA key by knowing the previous one also looks hard, as PGP basically cycles IDEA on random input and takes the output as the keys. If you could predict this output it would be similar to breaking IDEA. On the other hand, PGP normally keeps its random information in a small file called randseed.bin. It uses the contents of this file plus the current time of day in seconds as the input to generate the IDEA key. If you stole this file from someone (it's not cryptographically protected, unlike the secret key ring), and you know within several hours or a day when he sent each message, you could probably calculate all possible IDEA keys in a feasible amount of time (by trying all plausible values for the time of day in seconds). This would also let you calculate the new contents of the randseed.bin file. As long as you didn't miss any messages he sent, you could keep doing this and break all of his outgoing messages. You can prevent this by removing your randseed.bin file and substituting an empty file (or one that is less than 16 bytes long) in its place. This will cause PGP to prompt you for random keyboard input each time you send a message, which would make it impossible for the attack above to work. It would mean less convenience, though. The relevant routines are make_random_ideakey() and strong_pseudorandom() in crypto.c, as well as the code in random.c. Hal 74076.1041(a)compuserv.ecom

1 0

No Subject
by Karl L. Barrus 04 Dec '92

04 Dec '92

FutureNerd Steve Witham writes: >I should be able to verify with my own eyes how cypher technology works. >Otherwise I'm trusting my security to somebody's black box. This is important, which is why its nice to have source code. However, be prepared to invest a little :-) time in the study of PGP's code; I recently printed it out and must have sucked a toner cartridge nearly dry as it took more than 500 pages! Check out 'wc -l *.[ch]' which results in 22720 lines for me. > The signature algorithm (MD5?) > 128 bits? > Is that based on RSA? Get the md5.doc from rsa.com - available via anonymous ftp. It explains the algorithm (which is largely bitwise operations on blocks of the input stream) and even includes source code. > A cryptostrong pseudorandom # generator? > Is this based on RSA? Somebody posted a cryptographically strong prng to sci.crypt recently, but I haven't had a chance to look it over. I have my own rng - a ten sided die, which I haven't had occasion to use, yet. > A binary<-->ascii translator Phil Karn's DES package includes source code for uuencode, which performs this translation. I'm sure it is somewhere in the PGP code as well. There is also RFC 1113. >What's the formula for RSA again? > out = in * something ^ somethingelse mod yetanother?? > I know it can't be, because the key is only one number. Close! That looks like the formula for solving ax mod n = d for x given a, n, d. RSA: pick two primes p and q. Then n=pq. As Hal Finney said, the two primes should be "good" in the sense that p-1 and q-1 have no small prime factors. Obviously, you can't avoid having 2 divide p-1 and q-1, but that should be about it. Also, p and q should differ in length by a few digits otherwise an enemy may begin to try factoring n by starting near sqrt(n). Pick a decryption exponent d. d and phi(n) should be relatively prime, where phi(x) = Euler totient function = # of numbers less than x which are relatively prime to x = x-1 for x prime. For n, phi(n) = (p-1)(q-1). Calculate the inverse of d mod phi(n) and call it e, your encryption exponent (e = d^(-1) mod phi(n)). Publish n and e as your public info, and keep d secret as your decryption key. Somebody encrypts a message by calculating M^e mod n. You decrypt the ciphertext by calculating C^d mod n. For example: p=7, q=11 => n=77 and phi(n)=60. I pick d=13, gcd(13,60) = 1 so it is acceptable. Then e = 13^(-1) mod 60 = 37. Check: 13 37 mod 60 = 1. A message M=20 is encrypted as 20^37 mod 77 = 48. I decrypted the ciphertext 48 like this: 48^13 mod 77 = 20, and I got back the original message. /-----------------------------------\ | Karl L. Barrus | | barrus(a)tree.egr.uh.edu (NeXTMail) | | elee9sf(a)menudo.uh.edu | \-----------------------------------/

1 0

PGP questions
by ghsvax!hal＠uunet.UU.NET 04 Dec '92

04 Dec '92

It's probably good to discuss how PGP works here, for educational purposes, but I would expect people to get the source code if they really are interested. I can give some pointers here to answers to some of the questions people have asked. Steve Witham asks several questions. I think the crypto glossary which Tim posted a couple of weeks ago tells how RSA works, so I won't reiterate that here. Steve, if you didn't get it, maybe Tim could send it to you. PGP's signature algorithm creates an MD5 message digest of the message, then signs that digest by raising it to the secret exponent "d", mod "n". MD5 is a public-domain message digest algorithm created by RSA Data Security, Inc, which breaks messages into blocks of 64 bytes as input and produces a 16-byte (128-bit) digest. PGP then pads this 16-byte number to be about the size of n, and does the exponentiation. PGP does not do its decryption/signature exponentiation by actually raising the number to the power of d mod n, but by doing a mathematically equivalent operation involving two exponentiations, one mod p and one mod q. Since p and q are half the length of n, and exponentiation takes roughly the third power of the number of bits in the modulus, this reduces the amount of time by a factor of 4. The random number generator has several different modes, and I can only suggest looking at random.c. The data-compression algorithm is not really relevant but is based on zip. The binary-ascii translator is also not important but is a variant on the PEM standard. Steve asks a lot of questions about the speed of different versions. Maybe asking on alt.security.pgp would produce some representative values. I'm not sure whether anyone has a database with all these numbers. I understand that PGP 2.1 may have a faster version of the Upton modmult. Preliminary timings suggest that it's still slightly slower than the Merritt modmult on the Sparc, but if Merritt really is unreliable (I haven't heard about this) then switching to Upton will not involve much of a penalty. PGP is very fast on Sparcs anyway and I don't think making it 10% slower would matter. Profiling indicates that yes, during the RSA encryption phase, most of the time is spent in modmult. An interpreter could be built to do a modular exponentiation using a C implementation of modmult and it would be about as fast. However, that still leaves the generation of the random session key, padding it with random numbers so that it is suitable for RSA operations, converting the RSA-encrypted session key into a format suitable for writing to a file, doing the IDEA encryption, wrapping this all up with control information so that it can be decrypted, looking up key information from a key ring file or some other data file (possibly decrypting it on the fly), converting to ASCII, etc. All these are part of an encryption/decryption cycle and can't really be skipped. Hal 74076.1041(a)compuserve.com

1 0

Weakness of the PGP scheme ?
by VANGUARD＠gribb.hsr.no 04 Dec '92

04 Dec '92

To my knowledge there is done very little cryptographical anlysis on the PGP protocol, and just recently I saw I possible weak point in the PGP scheme. The underlying security of the PGP scheme is based on two different systems, the RSA asymetric cipher and the IDEA cipher. For standard encryption the plaintext is encrypted with a IDEA using a "random" key, then the key is communicated using RSA. Then we have two direct ways of analysing a message, we might have a run a plaintext attack on the ciphertext trying out all possible IDEA keys which will tak a lot of effort, or we might break the RSA key to get the IDEA key. But I propose an easier attack; Using a Encrypted Ciphertext together with the public key used for encryption, It would be possible to run a trial encrypting all possible IDEA keys using the RSA public key and compare it with the encrypted IDEA key, if a match is found then you have the IDEA key for this one message. Using an RSA chip that is capable of performing exponetsiations VERY fast I dont think that this would be unfeasable. The most important factor in this attack is the length of the IDEA key. But another concern is the generation of the IDEA key, is it possible knowing the value of the RANDSEED to know all the subsequent IDEA keys?, or would knowing the last IDEA key drastically reduce the time needed to search for a subsequent one? So far I haven't studied PGP enough to answer all these questions.

2 1

Chosen cryptotext and RSA
by miron＠extropia.wimsey.com 04 Dec '92

04 Dec '92

Can chosen crypto-text break RSA? (I.e., having access to the decryption machine - as a black box and finding the decryption exponent.) -- Miron Cuperman <miron(a)extropia.wimsey.com> | NeXTmail/mime ok <miron(a)cs.sfu.ca> | Public key avail AMIX: MCuperman | cybercomputingimmortallaissezfaire |

1 0

Re: enjoy enjoy
by George A. Gleason 04 Dec '92

04 Dec '92

Great one...! When I was taking undergrad social science stats, I came up with a similar one, just one verse though... Pearson-product-moment-correlation coefficients! If you still can't get it then you're mentally deficient Is this really learning or selection by attrition? Pearson-product-moment-correlation coefficients! -gg

1 0

Suggest splitting things up
by Eric Hughes 04 Dec '92

04 Dec '92

A word on the subject of altering the list from the list maintainer. There's been lots of discussion about splitting up the list into various pieces. In a word, it's not going to happen. Look, this is the cypherpunks list. Cypherpunks write code. A corollary to this is that cypherpunks take responsibility for the volume of mail they receive. If you're getting too much mail, use a filter. Many of you may not know that the remailer software as currently configured pressed into service just such a filter. In the just-announced ftp site, there's the source code, in perl, to just such a filter. You can change it to do whatever you like. In particular, you can install it to filter all your cypherpunks mail to a separate mailbox, file, or subdirectory. You can also use MH, whose slocal the above perl filter was based on. slocal can filter all of your cypherpunks mail to separate places. You can also send all of your cypherpunks mail to a separate directory and use a newsreader to read it. I've never done this, but certain list members have. If one of them (say, Mitra, who recently mentioned that he does this) would post a short summary of how it's done to the list and offer to answer questions off-line, I'd appreciate it. Eric

2 1

Re: digital banking
by ghsvax!hal＠uunet.UU.NET 04 Dec '92

04 Dec '92

I enjoyed seeing Karl's walk-through of Chaum's digital cash algorithm. The numbers looked right. One point is that doing different denominations isn't that much harder, you just need to have more exponents. As you generate your primes p and q, make sure that p-1 and q-1 aren't divisible by any small primes (other than 2). This will ensure that phi = (p-1)(q-1) is not divisible by small primes, hence that gcd(e, phi) will be 1 for those same small primes, in fact for all the odd numbers. Karl also quoted a comment from Ray Cromwell expressing concern over proving deposits. Ideally you'd get a signed receipt from the bank for every deposit you make. In the case of electronic deposits, there exist protocols for "gradual secret exchange" that might be suitable for this purpose. What you'd like is to send the bank your deposit "gradually", while the bank simultaneously gradually sends you a digitally signed receipt. I don't recall the details of these protocols. Gradual exchange would not be very convenient for email because of the long turnaround times in mail systems, but if you had a better connection it might be useful, especially for large deposits. Another way to look at it is, what stops the local merchant from taking your payment, putting it in his pocket, and then denying that you've given him anything? It would just be his word against yours. One answer is, if he does that to multiple people, their multiple stories would have more credibility than his denials. Similarly, a bank which made a habit of cheating its customers would find itself publically exposed. So it may be reasonable to trust the bank for routine transactions. Hal 74076.1041(a)compuserve.com

1 0

Brand-spanking new key
by cordones＠IMAGE.CS.NYU.EDU 04 Dec '92

04 Dec '92

Hello everyone. I just finished installing PGP2.0 in a rush...so..here goes my 1024-bit Military grade (he..guess I am a little paranoid..) key. Give it a try and perhaps I will experience some ESP... -----BEGIN PGP PUBLIC KEY BLOCK----- Version: 2.0 mQCNAisdxzYAAAEEALaDepo7QeCT2MCu+02nGuAZIJtoRwbxlwulUT/SehKH7xFW 43UqHZKHwMjDT5S8TESpGLtanhKsgmGa+Pp1X/tEImS2CqEvnPQhy0mjQMqR1WZ7 NfKenvUesXkE6pTpg/8Fk1AwsqRiypUEHoiNeU4k14gceilSg2Z/lrxl5FyxAAUR tCNFbCBab3JybyA8Y29yZG9uZXNAcm9ib2NvcC5ueXUuZWR1Pg== =o+Oh -----END PGP PUBLIC KEY BLOCK----- so..have phun... El Zorro

1 0

Re: Suggest splitting things up
by DrZaphod 04 Dec '92

04 Dec '92

In Message Wed, 2 Dec 92 21:56:54 PST, Eli Brandt <jarthur.Claremont.EDU!ebrandt(a)netcomsv.netcom.com> writes: > I personally don't object to this kind of list volume. Neither do I, just to cast my vote in the hat. In fact, I don't even think that we need to tag the messages for the type of content. I'm interested in anything that is posted in this list and read every message. TTFN! DrZaphod [AC/DC] / [DnA][HP] [drzaphod(a)ncselxsi.uucp] Technicolorized

1 0