- cypherpunks-legacy - lists.cpunks.org

Random numbers
by Timothy Newsham 15 Sep '93

15 Sep '93

Anon Wrote > mjr(a)TIS.COM writes: > >So figure you want more than 56 bits of pure unpredictability as your > >seed. This is a tricky problem. One option is to give the user a typematic > >buffer: "hit keys for 30 seconds" - you NEED unpredictability! > > So, it sounds like what we *really* need is a little box with a shot-noise > generator that attaches to a serial port and generates truly random > numbers to use for the key. Anyone out there feel like designing one for us ? Last time I was fingering through an analog parts catalog under the telephony section I noticed a bunch of parts that generate audio-noise. Maybe some of these would be suitable (if they dont use an internal digital state machine to generate the noise).

1 0

Unix version of PGP
by williacw＠vuse.vanderbilt.edu 15 Sep '93

15 Sep '93

Is there a UNIversion of PGP? Please Email me the location at: WESLEY(a)ctrvax.vanderbilt.edu Thanks

1 0

Random numbers
by an31185＠anon.penet.fi 15 Sep '93

15 Sep '93

mjr(a)TIS.COM writes: >So figure you want more than 56 bits of pure unpredictability as your >seed. This is a tricky problem. One option is to give the user a typematic >buffer: "hit keys for 30 seconds" - you NEED unpredictability! So, it sounds like what we *really* need is a little box with a shot-noise generator that attaches to a serial port and generates truly random numbers to use for the key. Anyone out there feel like designing one for us ? Also, what's the recommended book/books on cryptanalysis ? Looks like I have a fair amount to read up on..... ------------------------------------------------------------------------- To find out more about the anon service, send mail to help(a)anon.penet.fi. Due to the double-blind, any mail replies to this message will be anonymized, and an anonymous id will be allocated automatically. You have been warned. Please report any problems, inappropriate use etc. to admin(a)anon.penet.fi.

1 0

Re: Testing randomness of PGP-generated IDEA keys
by mjr＠TIS.COM 15 Sep '93

15 Sep '93

Anonymous writes: >Yes, obviously you're right. PGP seems to take the randseed.bin file, >the MD5 of the input, and the current time, and munge all of them together >using the IDEA encryption routines to create the final results. Assume the current time is a wash. Any message sent is going to have an approximate time (in seconds) inserted in the header as the MTA moves it, so that value is searchable trivially. For example, this message nicely contains a timestamp: Date: Wed, 15 Sep 1993 18:22:10 UTC I figure searching all the seeds within 12 hours of that will eliminate the time as a seed, and that's only 84,000 searches, which is huge orders of magnitude easier than searching DES. You don't even need gnarly fictional $1.5million DES-searching machines to do it. That leaves the MD5 of the input and randseed.bin. The MD5 of the input is by definition unknown to the attacker in MOST cases, right? If you're using this for confidentiality, that is. If the input is known, then you're left with just randseed.bin. >The contents of randseed.bin are created by generating some random bytes >using the same generation routine as the key and encrypting it with the key, >so they should be as random as the sample I created. I'm not entirely clear on this. It uses the same mechanism as the key and feeds it back through itself? What is the input into this process? Again: ignore the apparent randomness of the output, you need to look at the unpredictability of the input seed. Randseed.bin should be kept secret, clearly, as it's part of your key. >What bearing might this have on the suggestions of using electronic cheques >(presumably encrypted with PGP) ? If the cheque is a standard format, that >might open up some possibilities with this kind of approach, especially if >you know who it came from and/or who it's payable to. If I know the layout of the check and know that the only values that will change are a serial number which increases monotonically, and a value, which averages around $1,000, I can probably crack your PRNG in an hour or two, depending on how many processors I throw at it. Remember that this parallelizes trivially. Also, when you crack the PRNG with a public key system, you *KNOW* instantly that you've gotten the correct key, so the entire process is very hands off. One way of thinking about the problem is trying to count how many bits of unpredictability go into your PRNG seed. If you're willing to assume your adversary can brute-force search DES' 56-bit keyspace, then you'd better assume he's also willing to brute-force search your PRNG. So figure you want more than 56 bits of pure unpredictability as your seed. This is a tricky problem. One option is to give the user a typematic buffer: "hit keys for 30 seconds" - you NEED unpredictability! mjr.

1 0

Re: Testing randomness of PGP-generated IDEA keys
by an31185＠anon.penet.fi 15 Sep '93

15 Sep '93

mjr(a)TIS.COM said: > I found myself embroiled in a similar exploration of random >number generation as part of some other work, and it took me a while >to realize that running statistics on the output of the PRNG is >almost useless, if you're using a cryptosystem or cryptographic hash >as the PRNG. Yeah, this is a good point. I was assuming that there was no simple way of determining the possible keys from the time and other information you'd get with a random PGP-encrypted file that you wanted to crack. *If* that is the case, then looking at the output of the PRNG is useful to show that the worst-case of a brute force attack using all possible keys cannot be improved by taking the relative frequencies into account when creating the possible keys. It would be embarassing if 0x2A appeared 100 times more frequently than any other byte value, or if there was a strong correlation between the bytes in each key, for example. Whatever the case, we can probably write off any idea of brute force attack like the DES one, unless you have a few billion years to play with. (In which case, you'll do better attacking the RSA key anyway) > What you've got to look at is the predictability of the >input to the PRNG. PGP is in really good shape here, because it >bootstraps its PRNG with its input, which presumably is unknown >to the attacker. An example of a weak PRNG would be: [ Description deleted ] > Anyhow, I've been over-long winded. I think PGP is >in good shape because of the aforementioned property of >using the message as a seed. Messages that don't change >much, or that change predictably, are subject to exhaustive >searching. A means of analysing the unpredictability of >the seed is more worthwhile. Yes, obviously you're right. PGP seems to take the randseed.bin file, the MD5 of the input, and the current time, and munge all of them together using the IDEA encryption routines to create the final results. So, it's not at all clear how to test this end of things (one of the reasons why I decided to look at the output rather than the input). I'll have to poke around more in the code and see if I can work out what it's actually doing with all this stuff to get some idea of how to test it, if possible. The contents of randseed.bin are created by generating some random bytes using the same generation routine as the key and encrypting it with the key, so they should be as random as the sample I created. I could easily rewrite the program to generate the files and just calculate the MD5 and look at that, but, like you, I'm not sure that will tell us anything. Still, I can easily afford the CPU time, so it might be worthwhile anyway. Overall, I'm willing to accept that the key generation works pretty well at this point. What bearing might this have on the suggestions of using electronic cheques (presumably encrypted with PGP) ? If the cheque is a standard format, that might open up some possibilities with this kind of approach, especially if you know who it came from and/or who it's payable to. >My hat >is off to the guy who came up with the idea of seeding >the PRNG with the message. That was *clever*. > >mjr. Definitely. In fact, I wonder if this explains the 'fatal flaw' that people have mentioned. According to the comments in the code, the MD5 was introduced as an improvement over the previous method of generating the key, so perhaps there really was a flaw in this key generation that has now been fixed, or at least greatly improved. ------------------------------------------------------------------------- To find out more about the anon service, send mail to help(a)anon.penet.fi. Due to the double-blind, any mail replies to this message will be anonymized, and an anonymous id will be allocated automatically. You have been warned. Please report any problems, inappropriate use etc. to admin(a)anon.penet.fi.

1 0

Re: caching scripts
by wcs＠anchor.ho.att.com 15 Sep '93

15 Sep '93

Hal writes, on the subject of filler messages > It is true that user messages can be distinguished from dummy ones when > they are on their first or last stage in the chain; on the first stage, > they are the only messages coming from non-remailer addresses, and on the > last stage they are the only messages going to non-remailer addresses. > One way to fix this would be, instead of having the final destination > of the message be a "bit bucket" address, to instead choose a random > Internet address (say, from one of the "whois"-type databases), and to > send a message whose body starts with "Test message, please ignore". > With the tens or hundreds of thousands of addresses available (and with > the geometric growth of the Internet), it should not be necessary ever > to repeat an address. So perhaps this slight annoyance to Internet users > would be tolerable. Only a small fraction of users would ever receive > such a message. This is a way to increase the public's annoyance with remailers, when what we need to do is increase their acceptance of them. It also doesn't work - a cleartext message saying "Please ignore" is visible to any eavesdropper, an encrypted message to a real person is annoying and non-readable, and an encrypted message to a bogus person will usually generate bounce-mail (which is obvious to eavesdroppers), or will at least drop on an operator's floor, annoying the operator. If we can get a reasonable number of remailers operating, it makes much more sense to have standard bit-bucket addresses, and if we want to get more traffic to sites that aren't obviously remailers, we need to get their permission. This can either be done by asking people (which the Bad Guys can watch), or perhaps by providing some semi-useful service, like a netnews test sink or mail-a-joke or something; even those tend to be obvious - unless they can also be remailers or at least require crypto or other illegible data input. Bill Stewart

1 0

PGPC 2.2 available
by nate＠VIS.ColoState.EDU 15 Sep '93

15 Sep '93

-----BEGIN PGP SIGNED MESSAGE----- PGPC 2.2 is available for anonymous ftp from 129.82.156.104 in /pub/pgpc/pgpc22.tar.[Z,gz] It is available in either gnuzip or regular compress. Read the README. It comes with a makefile that will add the public keys to your public keyring... you may need to edit that if you don't need it (or want it) to add the keys. I added support for the encrypted remailers... it's quite slick now, IMHO. It can nest as many rounds of encrypted remailing you want, and it will also mail through anon.penet.fi into the remailers. I also signed the archives, and put the signature certificates in near the archives, you can get my public key from fingering nate(a)monet.vis.colostate.edu have fun, - -nate +-------------------------------------------------------------------- | Nate Sammons email: nate(a)VIS.ColoState.Edu | Colorado State University Computer Visualization Laboratory | Finger nate(a)monet.VIS.ColoState.Edu for my PGP key | #include <std.disclaimer> | Always remember "Brazil" +----------------------+ -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLJYBudTgi1fmrpxlAQEG4wP9HTn4xqBP/1rvPUwsuUoDpnoN/uzvVl73 fY/j9jnFjA+cAJ0/fnvUtl7Iq1OcowLauZAlIPg8ts7aR3sCT4eQnZZg2fon4xj3 dMeVjy/K3nTXPCoz+67KzIurZxHgyS5BQMzYs8YWi6lE/t7cWfFxE/6IyYMr7bYL B4OG6tKJOL4= =OIsL -----END PGP SIGNATURE-----

3 2

FTP location for sci.crypt FAQ
by cme＠ellisun.sw.stratus.com 15 Sep '93

15 Sep '93

>sci.crypt Usenet newsgroup FAQ. It's posted occasiuonally to sci.crypt, >but I can't think of a site (offhand) where you can FTP it. [from the FAQ] The sections of this FAQ are available via anonymous FTP to rtfm.mit.edu as /pub/usenet/news.answers/cryptography-faq/part[xx]. The Cryptography FAQ is posted to the newsgroups sci.crypt, sci.answers, and news.answers every 21 days.

1 0

caching scripts
by hfinney＠shell.portal.com 15 Sep '93

15 Sep '93

-----BEGIN PGP SIGNED MESSAGE----- I am very excited to hear about Karl's progress in experimenting with caching (batching) mail messages. Karl, if it becomes convenient, I'd appreciate seeing a copy of your scripts. I have two thoughts about batching. The first regards the mechanism for arranging for activation of the batch scripts at regular intervals. Karl mentioned at and crontab as two ways of arranging for this. Some users may not be allowed use of these functions. I am not sure I can use them on the systems which I use. Another possibility, it occurs to me, would be an "activation" message sent to each remailer from some system where crontab usage is allowed - one of the systems which is owned by a remailer operator, for example. This system would send out an activation message at midnight every night to each remailer which had requested this function. The activation message would have a special header field which could be trapped by the slocal program and cause it to run the batch script. The other idea I had was to increase the volume of messages passing through the remailers. This way we could batch at more frequent intervals while still having good "mixing" at each step. Suppose some remailer system took on the task of periodically injecting messages into the remailer web. Each message would be a large chain, perhaps through a dozen randomly- chosen remailers, which would end up disappearing by being sent to a "bit bucket" address like nobody(a)soda.berkeley.edu. With the new scripts appearing for producing random remailer message chains such a program would be quite easy to write. The message injection rate would be adjusted to give each remailer in the system an average load large enough that batching would usually have (say) ten or more messages to work with. Perhaps nine of those ten would be these dummy messages, while one is an actual user message. But it would not be easy to tell these apart, at least for user messages which are in the middle of their chain; each message, dummy and real, is from another remailer and to another remailer. There is no hint as to which are the actual messages. It is true that user messages can be distinguished from dummy ones when they are on their first or last stage in the chain; on the first stage, they are the only messages coming from non-remailer addresses, and on the last stage they are the only messages going to non-remailer addresses. One way to fix this would be, instead of having the final destination of the message be a "bit bucket" address, to instead choose a random Internet address (say, from one of the "whois"-type databases), and to send a message whose body starts with "Test message, please ignore". With the tens or hundreds of thousands of addresses available (and with the geometric growth of the Internet), it should not be necessary ever to repeat an address. So perhaps this slight annoyance to Internet users would be tolerable. Only a small fraction of users would ever receive such a message. The increase in traffic brought about by this dummy message source would not be large in terms of the net as a whole. It would only need to introduce messages at the rate of (# messages per batch) * (# of remailers) / (size of chain per message) per (batch interval). Plausible values might be: # messages per batch: 10 # of remailers: 20 size of chain per message: 10 batch interval: 6 hours This works out to about 3 messages per hour, not too large a load. Of course, this message injection system would only be maintained as long as user message traffic remained too low to provide good mixing in a batch system. As user message traffic increases, the injection rate would be decreased to compensate, until finally it might be possible to eliminate the dummy-message injection completely. Comments are appreciated, as usual. Hal Finney hfinney(a)shell.portal.com -----BEGIN PGP SIGNATURE----- Version: 2.2 iQCVAgUBLJaN5agTA69YIUw3AQECnwP9F+0gMxoL4xoLPyAJS4/owHOmTGW2OE0a nOLkjop+vT388LyZjbj40cRwm0OWpjNXwvsxsmY+Uhc8EYyTu/H1wKn2N2PR0Ufu TD/EYxLFuvXQGviGKftMfM/VbwRXUf1SiUnPovZ7jVaBhacp62y4+C6BQtFSZIft l3T2U1KI+Y4= =11AS -----END PGP SIGNATURE-----

1 0

Re: more than spread spectrum
by George A. Gleason 15 Sep '93

15 Sep '93

Re. Carl's suggestion to "lay our own wires/fibers..." That's exactly what I'm up to with the Community Dialtone project. Basically it comes down to having a neighborhood switch. We may be doing our first installation in the Winter, about 800 lines if all goes well. Seems to me that owning the switching & transmission infrastructure has a lot of possibilities. Anyway, more news to come on this in a few weeks... The thing is, I've looked into things like having infrared laser networks and various non-switched message relay systems... these just don't have the overall reliability of a decent switched system, for a large number of reasons which essentially boil down to the fact that each individual link is weak enough that even a redundant system can break down badly at points where the link density is relatively thin. Then also there's the question of economic feasilbility; to make a decentralised/non-switched system work, you need an application that is *so* popular that everyone in an area will want to be in. This comes down to subscriber density, and the issue is basically the same with telephone lines, but everyone needs a phone line... cable TV has high market penetration but satellite TV doesn't... how can we expect a lot of average folks to set up an infrared relay, eh...? Seems to me the best thing is to have the IR relays located where they can connect among the switching systems serving the various blocks and neighborhoods. (and if anyone's figured out how to do that at 2.048 Mb, i.e. approx double T1, please email me ASAP). -gg

1 0