December 2003 - cypherpunks-legacy

Cryptanalysis
by Brendan McKenna 17 Dec '03

17 Dec '03

Hi, I light of recent threads about recognising whether or not a given message/file is encrypted, and using CBW and things along those lines, is there any way to determine how something was encrypted? For example, I know that a statistical analysis of the cyphertext will uncover simple substitution cyphers fairly quickly. Does the same sort of analysis apply to determining whether something was encrypted using IDEA or DES or RSA? I realize that they attempt to maximize the entropy of the cyphertext -- perhaps there is some characteristic amount or range of amounts of entropy associated with these cyphers? Not every package is as nice as PGP in labeling everything it encrypts with headers... Any pointers would be greatly appreciated.... Brendan PS. What I'd like to be able to do is take a given chunk of cyphertext and analyze it and say: "There is an x% probability that this was encrypted using method y...." Hopefully I'd have a reasonable chance of recognizing how it was encrypted, and not all of the percentages would be so low as to make the exercise meaningless.

1 0

analysis of RemailerNet
by Wei Dai 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- I've been reading through T.C. May's FAQ, and came upon this section about analyzing the RemailerNet. > + What's needed: > - aggreement on some terminology (this doesn't require > consensus, just a clearly written paper to de facto > establish the terminology) > - a formula relating degree of untraceability to the major > factors that go into remailers: packet size and > quantization, latency (# of messages), remailer policies, > timing, etc. > - Also, analysis of how deliberate probes or attacks might > be mounted to deduce remailer patterns (e.g., Fred always > remails to Josh and Suzy and rarely to Zeke). > - I think this combinatorial analysis would be a nice little > monograph for someone to write. > 8.10.2. A much-needed thing. Hal Finney has posted some calculations > (circa 1994-08-08), but more work is sorely needed. I think one of the most difficult aspects of analyzing remailers is the large number of variables you have to deal with. In contrast, when analyzing ciphers things are pretty much static. The only thing variable you have to worry about is key length. But think of the factors you have to include in a complete analysis of the RemailerNet: 1. different methods of attack - passive traffic analysis (i.e., packet sniffing) - active attacks: including physical attacks, subverting remailer security, flooding, denial-of-service, starting "trap" remailers, etc. 2. differences at the user level - fixed vs random chains vs something in between - length of chains - numbers of real messages sent - numbers of fake (cover) messages sent - concerns about latency, bandwidth, and monetary costs - acceptibility of risk, and benifits of anonymity 3. differences at the individual remailer level - the mixing mechanism: does batched mailing occur by time or by the number of messages in the queue, and is there a rollover pool? - security: including vulnerabilities to political, physical, and electronic attacks - usage level - price 4. differences at the RemailerNet level - total numbers of remailers - average security (or the number of compromised remailers) - total number of users ... and I'm sure there are more. The number of variables and the complex way they're all interrelated make the analysis difficult. Perhaps a good way to go about this is to construct simplified models which focus on different aspects. For example, someone pointed out that if you didn't have to worry about active attacks, and the attacker can monitor all the remailers, then you can treat the entire RemailerNet as a single large remailer. I'm not sure how well this approach would work, since I don't know how easy it would be to integrate the different simplified models into a realistic one. Anyhow, this might at least give us some insights, so I'll make some attempts in this direction, and post my results. Just to start things off though, let me try an *extremely* simple model. Assume there is just one remailer, it's perfectly secure, and it does 4 batches of remailing at equal intervals each day. There are one million users, each of whom receives a mail from the remailer once per day. Alice is sending anonymous mail to Bob through this system, also once per day. But just to be extra careful, she also sends a cover mail to the remailer at some other time each day, which gets redirected to its /dev/null. So the situation looks like this on day 1: Alice sends Bob receives some random user receives Batch #1: 0 0 0 Batch #2: 1 1 0 Batch #3: 0 0 1 Batch #4: 1 0 0 Suppose Eve, the traffic analyst, is trying to figure out who Alice is sending mail to. After the first day, she can eliminate about half of the remailer users from the list of possible targets, because they, like the the random user above, received a mail even though Alice didn't send one out during the collection period of that batch. Now, since Eve can eliminate on average half of the list every day, Bob will be the only person left on that list after about (log base 2 of one million) = 20 days. Suppose Alice sent out some different numbers of cover e-mail: # of cover mail # of days to discover Bob 0 log base 4 of 1,000,000 = 10 1 log base 2 of 1,000,000 = 20 2 log base 4/3 of 1,000,000 = 48 3 log base 1 of 1,000,000 = infinity! Hopefully that makes sense... Comments? Wei Dai -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBLxU0QTl0sXKgdnV5AQFkoAP/SSyqbbDw+zoh+q5aL0+xr5BcLzaEoS4h NASocZvKHGLe8/sfefDj4J2zPINKhmQzbKdD4oHirPEVbnWZC+7Us3giCKl80t2V bKx6QPB1hJWi6n3cFme6NCuTjmHCsgrQ/bI2j524O43FhW6BIQAAxQ6GGN10t1V8 3nv3SzUC6jE= =Y2qv -----END PGP SIGNATURE-----

1 0

time stamping service (again)
by Wei Dai 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- My PGP based time stamping service is back online. I took it down a while ago thinking the folks at notary.com (Digital Time-Stamp, Inc.) were going to release their commercial time stamping product soon (it uses a more elegant protocol that doesn't require trust in the time stamper, but the algorithm is patented). But I haven't heard anything from them in a while. Anyway, it is now running as the following procmail recipe: :0 w * ^Subject: Time Stamp This Mail { PGPPASS=whateveryourpassphraseis :0 c w | (lockfile timestamp.lock ; pgp -fast +batchmode +force +verbose=0 \ +clearsig=off) > timestamp.out :0 a h | (formail -r -i 'Subject: Time Stamp Output';cat timestamp.out) | \ ($SENDMAIL -t ;rm -f timestamp.lock) } To use it, just send whatever you need time stamped to me with the subject "time stamp this mail". BTW, can a procmail expert explain to me why the locallockfile mechanism doesn't work with this recipe? If I use :0 w : as the first line, procmail will happily ignore the locallockfile flag and proceed to munge up timestamp.out, so I have to do the filelocking manually. Wei Dai -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBLxU7Zjl0sXKgdnV5AQE1agP/TFGtHEUj6GUwEF1ISGLcUZ/T64Vs7BUJ PIcydYUDk/5AVPLS2F8r81oLLxDUzYFkVy/6uvhnj6Pvo17ZIx6ELhKNPLPVoLPL iklR9E7rmY2cRMQfuCPRYi10x4mD9yJcw0GmlQmgOqZS/HfQ30njrsAeDXBUNvA5 SvFBaPKuOro= =NNoJ -----END PGP SIGNATURE-----

4 3

Re: Cryptanalysis
by rparratt＠london.micrognosis.com 17 Dec '03

17 Dec '03

> I light of recent threads about recognising whether or not a given > message/file is encrypted, and using CBW and things along those lines, is there > any way to determine how something was encrypted? For example, I know that > a statistical analysis of the cyphertext will uncover simple substitution > cyphers fairly quickly. Does the same sort of analysis apply to determining > whether something was encrypted using IDEA or DES or RSA? I realize that they > attempt to maximize the entropy of the cyphertext -- perhaps there is some > characteristic amount or range of amounts of entropy associated with these > cyphers? Not every package is as nice as PGP in labeling everything it > encrypts with headers... Any pointers would be greatly appreciated.... If the encryption method is any good, the output will be pseudo-random with no digit being more frequent than any other. This certainly applies to IDEA and DES. With RSA, you usually have a random (IDEA) session key encrypted using the senders private key. This will also be an effectively 'random' number. > PS. What I'd like to be able to do is take a given chunk of cyphertext and > analyze it and say: "There is an x% probability that this was encrypted > using method y...." Hopefully I'd have a reasonable chance of recognizing > how it was encrypted, and not all of the percentages would be so low as > to make the exercise meaningless. This would only work for ciphers that are effectively 'broken'. Also, many packages and users compress data before encryption. Compression algorithms work by removing patterns from data, so the resultant compressed plaintext becomes fairly random anyway, removing the utility of frequency analysis. -- Richard Parratt

1 0

good stuff
by nelson＠crynwr.com 17 Dec '03

17 Dec '03

Interestingly enough, there are lots of interesting documents, including anti-clipper screeds etc, on the New York State Education Department's gopher. Good stuff for political activists (as opposed to passivists :). gopher://unix5.nysed.gov:70/11/TelecommInfo/Reading%20Room%20-%20Points%20of%20View -- -russ <nelson(a)crynwr.com> http://www.crynwr.com/crynwr/nelson.html Crynwr Software | Crynwr Software sells packet driver support | ask4 PGP key 11 Grant St. | +1 315 268 1925 (9201 FAX) | What is thee doing about it? Potsdam, NY 13676 | What part of "Congress shall make no law" eludes Congress?

1 0

Knowing Something's Encrypted
by Jeff A Licquia 17 Dec '03

17 Dec '03

Maybe I'm missing something here. If I am, please bonk me. Here's a simple method for knowing that some data you received is encrypted: 1. Require a specific method (we'll use PGP in this example). 2. When a message comes in, check for a PGP format message. If you really wanted to get fancy, you could parse the PGP header a bit to make sure the data was really encrypted. It's true that this isn't "cryptographic" in the sense of testing the ciphertext itself, but it should work for the practical goal of enforcing a "must be encrypted" rule. ---------------------------------------------------------------------- Jeff Licquia (lame .sig, huh?) | Finger for PGP 2.6 public key jalicqui(a)prairienet.org | Me? Speak for whom? You've got licquia(a)cei.com (work) | to be kidding!

1 0

Re: Cryptanalysis
by daleh＠ix.netcom.com 17 Dec '03

17 Dec '03

You wrote: >If the encryption method is any good, the output will be pseudo-random >with no digit being more frequent than any other. This certainly applies >to IDEA and DES. With RSA, you usually have a random (IDEA) session key >encrypted using the senders private key. This will also be an effectively >'random' number. Just a technical note, but a normal distribution of digits (i.e. 'no digit more frequent than any other') is no inidication of either randomness or 'good' encryption. A better test is to look for a normal distribution at all scale levels. For example, the following text block: "UUU" (in ASCII) has a normal distribution at the bit level "0101 0101 0101 0101 0101 0101", but not at the byte level. Dale H.

1 0

Re: Pornography, What is it?
by frissell＠panix.com 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- At 06:29 PM 1/11/95 -0600, root wrote: >Article XIV (1868) > >Sec. 1. > >All persons born or naturalized in the United States, and subject to the >jurisdiction thereof, are citizens of the United States and of the States >wherein they reside. No state shall make or enforce any law which shall >abridge the privileges or immunities of citizens of the United States; >nor shall any State deprive any person of life, liberty, or property, >without due process of law; nor deny to any person within its jurisdiction >the equal protection of the laws. > >Where in there is the protection you speak of? I see no guarantee of my >Constitutional rights, only of privileges and immunities as granted >by the federal government. The courts have held that the term "liberty" in the XIVth Amendment includes the liberties protected by the body of the Constitution and the other Amendments. DCF - -- PGP signing encouraged by Private Idaho (for Windows Eudora) by Joel McNamara -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBLxVIOYVO4r4sgSPhAQHPfgP+PisOuBlvGgb96M5bjkVdIfDb2JEkb0Nb N4Uw9FoILGtUPibEphsJbRF4GpCd8qfHJvZjP5jTCLztCwo0r/kPc4qDKYPzRpVv EmZm2WwByOBSDqljJJAb3a7bC5b9vOEr2shr29u1apYmGl6sldvi4lTHYMjTOxI3 rUmivlpfsOc= =kTT1 -----END PGP SIGNATURE-----

1 0

Re: How do I know if its encrypted?
by Hal 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- The data haven concept as I understood it held data for public access in some form (for sale or for free) which would be illegal in some jurisdiction. This might include credit information that was older than the legal limit, libelous claims, damaging medical records, etc. Frankly, I suspect that most usages would be directed towards reducing, rather than increasing, individual privacy. So this is not an area I am interested in working towards. The idea of offsite storage doesn't seem that helpful since you can just store the data on your own disk in encrypted form. Maybe if encryption gets outlawed it would be useful, but then you can't use encryption to communicate with the haven. As far as remailers requiring encryption, one purpose would be to reduce complaints by making it impossible to send some kinds of messages which people would object to. It would be hard to post to usenet, for example, in a useful way. And mail to private individuals could not contain obvious obscenities or other objectionable material. The problem with this is that if people become able to handle and deal with incoming encrypted mail in a transparent way, this restriction is no longer effective in the latter purpose. Someone could get encrypted hate mail and have it transparently decrypted and displayed just like normal mail. They will be just as upset as people are today when they get objectionable mail from the remailer. As far as usenet posts, if a particular decryption key were widely and customarily used in a particular newsgroup, objectionable material could still be widely read if encrypted with that key. Tim May's example of a fake encrypted post containing inflammatory material is a good example of the heat which could occur, especially when the message is real and not a fake one like he did. So I don't think this restriction would really accomplish the desired goal except perhaps in the short term. If the purpose is to have plausible deniability by the remailer operator, I feel we can still get that by publicizing the remailer software source, which has no provisions for manual filtering. A policy of sending only encrypted mail so that the operator can't filter would be no more acceptable to critics of anonymity than a policy of just not filtering at all. Entropy checking is not adequate to detect encryption, as compressed files have maximal entropy as well. For these purposes, compression may be nearly as good as encryption, except that standard compression formats are already widely used. An entropy checker might well pass a gif, jpeg, or zip file, so this filter would by itself be useless to prevent posting of unencrypted graphics. It would probably have to be augmented at least by some checks for these special file formats. Hal -----BEGIN PGP SIGNATURE----- Version: 2.6 iQBVAwUBLxVgSRnMLJtOy9MBAQF66wIA3a01avgc0jBjKXH6IMjO+6wj4tBeSUmM ZeRl+xFZFZ4Cfsrik1ghuHXI31isiHUzrPAIVEZfFIpTw6w9T0QdSQ== =YVRq -----END PGP SIGNATURE-----

2 1

Chain
by assets＠alpha.c2.org 17 Dec '03

17 Dec '03

I use Hal Finney's 'Chain' a lot: it is an easy way of automatically building a remailer chain. But it won't PGP correctly with the Usura and the Flame remailers because these two have e-mail addresses that have changed and/or are different from the addresses specified in their public keys (Usura, for instance, is now <usura(a)replay.com>, but this is not the address given in its public key ID). Is there a way for me in PGP to edit and update the information contained in the public keys of others? I would want to add an "also known as" line for 'Chain' to spot. O.A. <assets(a)alpha.c2.org>

2 1