- cypherpunks-legacy - lists.cpunks.org

Re: DES Optimization (Brute Force DES)
by Peter Trei 17 Dec '03

17 Dec '03

> "Peter Trei" writes: > > The fastest general purpose, freely available des implementation I'm > > aware of is libdes. by Eric Young. With this, I can do a set_key in > > 15.8 us, and an ecb_encrypt in 95 us/block. That adds up to > > about 9,000 keytests/sec (this is on a 90 MHz P5, running NT). > > I'll point out that like most DES implementations, Eric's tries to > spend a lot of time in key setup to save time later on in > encryption/decryption. This tradeoff would probably be very different > if you didn't plan on trying more than one or two blocks of decryption > after getting a key. > > Perry Yep - with good optimization, the keygen and the des rounds get very close to each other in processing cost. Let's look at the steps involved (I'm refering to the DES description in Schneier, 2nd ed, p 270-278). I've not yet coded these optimizations, so this may be subject to revision. I'm assuming a known plaintext attack on a single 64 bit block, ECB mode. What we want to obtain is the key (which was presumably also used to encode interesting data which we can't read) First of all, we can move the initial and final permutes (tables 12.1 and 12.8) completely out of the testing loop. These have to done only once per run, and thus are effectively zero cost. Similarly, we can eliminate the key permutation (table 12.2), and iterate the permuted 56 bit key. If we get at hit, we invert the key permutation and add back the parity bits to get the original key. In the DES round The S-box and P-box steps can be combined into a single 48->32 bit permutation. So, per round (there are 16), we now have: 1. copy 32 bit sub-block to use as 'other' half in next round. 2. expansion permutation (32 -> 48) 3. xor with appropriate subkey. 4. perform the s-p permutation. (48->32) 5. xor with 'other' half from previous round. The key scheduling can be done in parallel with the rounds, since we're only planning on using each key once. However, on the Pentium it may be more efficient to do it before the des rounds, due to register starvation. Generating the subkeys is actually quite painful. You have to rotate the 56 bit key as two 28 bit halves, by one or two bits depending on the round, and then do a 56-> 48 bit permutation to generate the subkey. This step needs to be done 16 times. In a regular DES implementation, you generate the key schedules once at the start, and reuse them for each block, so there is little to be gained by optimzing this step. In a keysearch situation it's a different matter. Optimizing the permutations: DES was originally designed for hardware implementation, where permutation is a simple matter of braiding the wires between the input and output. It's a lot harder in software. I'm aware of two basic approaches: 1. Algorithmic: Analyse the permutation table to find bits which get shifted in the same direction, by the same number of bits, and arrange a series of SHIFTs, ANDs, and ORs to generate the desired permutation. This is essentially a geometry problem. 2. Lookup: Create tables for the permutation. While a permutation with n bits of input requires 2^n entries (each the size of the output data) if done as a single table, it's possible to break the permutation into several smaller tables, at increased processing time. This is a classic speed vs space tradeoff, with a big step if your tables are too large to fit into cache (and even bigger if they go to virtual memory) Example: A straight 32 -> 32 bit permutation: If done as one table, it would have 2^32 entries, and take about 16 Gbytes. If broken up into 4 tables, each of which dealt with 8 bits of the input, it would take 4096 bytes total. However, the calculation would require extracting the four eight bit subkeys from the input, doing four lookups, and ORing the four results together to get the final output. A 32 bit perm could also be done with two tables, but they would occupy half a Mb. The S-P step and the compression step of the key schedule are probably faster by lookup than by algorithm. I'm not sure about the expansion permutation, which is very regular. The size and number of tables used is going to depend a lot on cache size and available memory - for example, the rotates in the key scheduling can be eliminated if I'm willing to maintain 16 key compression tables (one for each round). I strongly expect that the whole key testing loop can fit into the 8k L1 code cache. The lookup tables *may* fit into the L2 cache. If anyone has any other optimizations, I'd like to hear about them. Peter Trei trei(a)process.ocm Peter Trei Senior Software Engineer Purveyor Development Team Process Software Corporation http://www.process.com trei(a)process.com

1 0

emscrypt 0.01 ALPHA
by Matt Carpenter 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- I finally managed to find some time to do a little testing of emscrypt and make some of the changes that were suggested here earlier. It is still rather ugly and I haven't added many of the features/capabilities I hope to eventually implement. But I'm making it available so that people can play with it if they want. It looks like I'm going to be very busy for at least the next month trying to finish up the work for my master's degree, so I probably won't be making any major changes for a while. emscrypt's purpose is to automatically run PGP signed scripts received by e-mail and return the results to the submitter. emscrypt is a heavily mutated version of morepgp, originally by Jason Steiner and modified by Greg Spencer. Please realize that this program has NOT undergone extensive testing, so you may encounter strange behaviour. Make sure you read the documentation that exists. Using this program may make your system insecure, especially if you don't follow the installation procedure carefully. Use at your own risk. You should be able to find emscrypt and some documentation at: http://www.bmen.tulane.edu/~carpente Look under the "Other random projects or possibly useful stuff" heading. In order to try out emscrypt you need the following: * Perl -- emscrypt is written in Perl. * PGP 2.6.2 -- Other versions may work, but I haven't tested them and emscrypt relies strongly on knowing the format of the PGP output messages. * Procmail -- For passing incoming mail to emscrypt. This can be accomplished in other ways, but at this point I haven't tried any of them. If you don't have procmail you can still play with emscrypt by piping messages to it manually. I strongly suggest you do this anyway, to make sure you trust emscrypt to answer incoming mail. Here are the major things that have changed with emscrypt since I described it here a while ago: There are now two required headers which must be included in the body of the signed message: 'Reply-To:' and 'PGP-Key-Fingerprint:'. Both must appear before the beginning of the script. The beginning of the script is considered to be anything other than the above headers, blank lines, or lines that begin with '::' but that are otherwise empty. Duplicate headers will generate an error and prevent the script from executing. Case within the headers is not important. (You are free to use eLiTE d00dz capitalization techniques, just don't try to use kRe8yv sP3lliNg5.) 'Reply-To:' must be followed by a valid e-mail address, otherwise you won't get your results. (emscrypt will also recognize a 'Request-Remailing-To:' header in place of 'Reply-To:'. I added this so that emscrypt could be treated as a "remailer". The idea is that you could use software such as premail to automate the generation of messages going to emscrypt, so that you don't have to do the signing/encrypting manually. Then you could just send a script to yourself, "chaining" it through your emscrypt "remailer". But I don't think this will work without slight modifications to the remailer message generating programs, since emscrypt requires the 'Request-Remailing-To:' header within the signed body of a message (it would also be nice if the 'PGP-Key-Fingerprint' header could be automagically included)). The 'PGP-Key-Fingerprint:' header gives the fingerprint of the key used to sign the message and which will also be used to encrypt the results. It must also be included within the signed body of the message. Most of the other changes involved minor debugging and general clean-up (not that I consider it clean now). I also improved the error handling a little, but it needs more work, too. Right now emscrypt generally tries to generate, encrypt, and mail an error report if things go wrong. If that doesn't work, then it saves an error message to a log file. If you find any problems, please let me know. Comments, suggestions, etc. are also welcome. Thanks, - --Matt - -- mcarpent(a)mailhost.tcs.tulane.edu -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQEVAwUBMfXlaijtJAMyBnp9AQHAdAf+MQ/ZroKoLeYyQDYabVrIq1eLSQB6vpr+ 2tXu63wDbcUeFoeSFNx6Sar7DNtAJyJUlwVcVKlb5SOuYR/8aFDvAnIYuQLPfdXd xXjC4iv+Hh3hNx4ibeyAB4xbFmDYAMB19zEf6nhmJdxR03oFXP+Qfx2m/aN/LDKZ zVSjtOs/ujTa6ltP6r/9x1vdiqmSNuSCNLvL/f4YulfdzR8frF0uLyLmiDH6mUpm etKxSpIg4ZI+iy1YvvSd+FtA0F3XSziaLEepx4X8gYjZKP0YXPTEMGhTeWj1o6bP yl06KUIRTL5k56P0xnW2MezGN5c0Cz2W9TEa9NBbHxY1DgSTDWa3sg== =DTpY -----END PGP SIGNATURE-----

1 0

Re: Flaws of Thinkers (Jefferson, Rand, Nietzsche, Voltaire, etc.)
by tcmay＠got.net 17 Dec '03

17 Dec '03

At 11:40 AM 7/23/96, bryce(a)digicash.com wrote: >I know a lot about Rand, and about her deep flaws as an >individual, especially in terms of treatment of her supporters, >but this is the first I've heard of this one. Perhaps Tim is >thinking of a play by Murray Rothbard called "Mozart Was a Red" >in which the Ayn Rand caricature insists that her followers >smoke. > >As for smoking being "proof" of man's dominance over nature, >Rand _did_ believe that in the sense of "demonstration" or >"symbol" but she did not believe that in the rigorous sense of >"proof". This was well-known to a bunch of us in the early 70s who were interested in Rand (and her extreme followers, known widely as "Randroids"). I think some of her essays in her Objectivist Newsletter had explained why smoking was essentially de rigeur. (By the way, at the time Rand was writing this stuff, doctors were recommending smoking as a digestive and health aid, and nearly everyone smoked. I don't condemn Rand for smoking, or for falling into the all-too-common practice of using "logic" to justify one's beliefs and practices.) Rothbard was a source for the smoking example, but not in a play (although he may have also used his knowledge in a play...I wouldn't know). Rothbard wrote an article for "Liberty," circa 1986-8, which is where I read the details. Also, I believe Barbara Branden's biography of Rand dealth with this, but I haven't read it in many a year. And there is this comment, from an admittedly off-beat source (http://www.zonpower.com/zonpower/book/chapters/chapter29.html) "Whatever the root of his irrationality, Dr. Peikoff's persona shrinks with his advocating force-backed intolerance as he expressed during his 1995 Ford Hall Forum lecture. Recall how Ayn Rand's life wastragically diminished by her irrational, deadly, "dot-of-light" glamorization of smoking. Her emotional, irrational denials of the narcotically addictive, physically destructive nature of tobacco smoking led her and some of her "caped" followers to the grave." --Tim May Boycott "Big Brother Inside" software! We got computers, we're tapping phone lines, we know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Licensed Ontologist | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."

2 1

Re: A Global Village; an open letter to Bill & Hill [rant]
by Alex F 17 Dec '03

17 Dec '03

> The world is everchanging and Mrs. Clinton is correct in that the > industrialized > countries have lost, most, of their extended families. This makes children > vulnerable to danger. This is such crap, and I'll tell you why. It is a classic example of political double speak. Here Hillary says that children are in danger because of lost family values. Absolutely true. Let me ask you then why is it that Bill(ary) signed an unconstitutional law? I am referring to the CDA and the telephony bill. What about the terrorism bill? They apparently support censorship on the Internet. They don't want "bigtitties.gif" on the net and accessable to little Johnny. They say that it is WRONG for little Johhny to have access to "bigtitties.gif," and that the GOVERNMENT should DO SOMETHING about this. What happened to family values? Just HOW the hell can you support and promote family values when you are telling the parents (who you want to pay more attention to their children, get more involved, and be kinder) "WE know what is best for little Johnny, and WE will make the decisions, NOT YOU" To me this sends a message of "The government knows best because most parents are stupid and uncaring." It is much more likely that little Johnny will go over to Sammy's house and look at the Playboys that Sammy's dad has hidden under the bed than collect nudie .gifs off of the net, but they wouldn't dare censor that. The Internet is another story, however. I got news for them, we had pornography LONG before the net ever existed, and there is NO solid psychological link to viewing porn and becoming a sex offender. Anyone who thinks so needs to realize that they are talking about something about which they have no clue. Anyway, getting off-topic again. I'll be quiet now :) Alex F =-=-=-=-=-=-=-=-=-=-=-=-=- Alex F alexf(a)iss.net Marketing Specialist Internet Security Systems =-=-=-=-=-=-=-=-=-=-=-=-=-

1 0

RE: Democracy... (fwd)
by Jim Choate 17 Dec '03

17 Dec '03

Forwarded message: > From: Matthew James Gering <mgering(a)ecosystems.net> > Subject: RE: Democracy... (fwd) > Date: Wed, 16 Sep 1998 15:07:37 -0700 > > Try pantheism. If one fundamentaly believes that god does not > > exist, which clearly involves faith, then yes it is a religion. > > Then I guess you could say that pantheism is an atheist religion, as > opposed to a theist religion. You could, but you'd be wrong. > My nice definition of atheism is reason over faith, science over > mysticism, basically an anti-religion. While that may be etymologically > unjustified, it does accurately reflect the views of the majority of > people I know who call themselves atheist, myself included. Atheism means that one believes that there is no God. > > By your view an agnostic can't be religion > > No, and it's not, it's like standing in the doorway of a religion, not > sure whether to enter or leave, perhaps practicing but not believing. Ah, so there are personal beliefs that aren't religion and then there are personal beliefs that are? What a self-rightous, pretentious, egotistical viewpoint. Your view is *exactly* why the 1st was put in there. > Such indecisiveness annoys me, but it accounts for the majority of the > population. Actualy not, the vast majority of people believe in God, just not your particular brand - which after all is what the 1st is all about. ____________________________________________________________________ The seeker is a finder. Ancient Persian Proverb The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage(a)ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- --------------------------------------------------------------------

1 0

Re: Bare fibers
by Bill Stewart 17 Dec '03

17 Dec '03

h > > Doesn't that make it vulnerable (detectable) to Tempest attacks? h > > Harka rw> No. rw> Transmitting light via fiber doesn't emit EM. Light is electromagnetic :-) rw> Anyway, the original post, as I recall, was about keeping sensitive data rw> on a second hard drive, connected via (very thin, therefore harder to rw> notice) fiber. Tempest monitoring was not a factor. rw> -r.w. I assume that if you've got a fiber hanging from your PC, and thugs come in to steal/confiscate/forfeitize your PC, that they're bright enough to notice it and maybe to follow it. Thugs who want your information will follow it to find information; thugs who just want to resell your hardware will follow it to find more hardware. I had initially assumed that the mention of fiber optics was in the context of "Infrared transmitter on the PC, fiber optic sticking out of the wall to receive the IR and transmit it to a hidden detector." or something silly like that. If you want to hide a small PC in your attic/wall/etc and use the newer faster IR stuff for clandestine backups, and have a Real Operating System so you can run it in the background (since your disk drive is presumably much faster than IR), I suppose you could do that. The main use of TEMPEST here is to detect backup systems hidden in the attic that they hadn't noticed. Hiding it in your stereo system doesn't protect it from honest thieves, who might also want to resell your stereo, and info thieves have been known to seize anything even resembling computer equipment, such as Mozart CDs. You could also hide the computer in your kitchen cabinets like one Famous Cypherpunk, but you'd have to use a thinner bundle of cables than he does to connect the monitors and keyboards :-) # Thanks; Bill # Bill Stewart +1-415-442-2215 stewarts(a)ix.netcom.com # http://www.idiom.com/~wcs # Confuse Authority!

1 0

RE: Distributed DES crack
by koontz＠netapp.com 17 Dec '03

17 Dec '03

>I'd like to see a very general hardware processing power equivalence table. >For example, 1 MasPar equals how many Pentiums. One MasPar MP2 (4K processors) could run 300,000 crypt(3) crack attempts per second (a password checker). That should give you 6 or 7 million brute force key attempts per second. Unfortunately the only way to show an equivalance for a particular problem is to have both machines work on the same problem. (Perhaps we could manage to break a DES key in the course of executing a new benchmark?)

1 0

RE: Distributed DES crack
by Bill Stewart 17 Dec '03

17 Dec '03

At 03:40 PM 7/23/96 PDT, koontz(a)netapp.com (Dave Koontz) wrote: > > I'd like to see a very general hardware processing power equivalence table. > > For example, 1 MasPar equals how many Pentiums. > >One MasPar MP2 (4K processors) could run 300,000 crypt(3) crack attempts >per second (a password checker). That should give you 6 or 7 million >brute force key attempts per second. Interesting - thanks for the result. Do you know how tightly tuned the crack implementation was (e.g. straight C with MasPar optimizer, hand-tuned assembler, etc.)? Since the MasPar has a large number of very small processors, I'd expect it to be better at bit-twiddling than conventional processors. # Thanks; Bill # Bill Stewart +1-415-442-2215 stewarts(a)ix.netcom.com # http://www.idiom.com/~wcs # Confuse Authority!

1 0

Re: Digital Watermarks (long, getting off-topic)
by tcmay＠got.net 17 Dec '03

17 Dec '03

(My comments are really minor quibbles, based on my longtime use of DAT machines, which I now have three of.) At 2:19 PM 7/23/96, Alex F wrote: >The Ent. Ind. got what they wanted though. There are taxes, etc. >(some sort of import restrictions anyway) that keep DAT player/recorder >devices at around $700 per unit. By this time normally the prices >*should* be down to like $200 (using the CD industry as a guide) As I said, I have three DAT machines. They are complicated machines, having lots of moving parts and precise tolerances. (And they are prone to break!) CD players are vastly simpler. I'm not at all surprised that prices have remained at about the $400 level for DAT decks, and about the same for DAT portables. After all, camcorders, which use much the same technology, have also remained at about the same price. And I don't think the SCMS code had too much to do with mass-acceptance. Most comsumers, according to available figures, *buy* C-90 cassette tapes, and do not make their own. (That _you_, the CP list reader, may use your cassette deck to make tapes has little to do with the vast numbers of cassette users out there do...most don't know how to record with their cassette decks.) Pre-recorded DAT tapes were available for a while...they did not sell. I believe this was because DAT machine purchasers were sophisticated and new how to make CD-to-DAT copies, with or without SCMS. Thus, the failure of DAT as a consumer medium (not to mention the much-hyped MD and DCC formats) probably is due to other reasons, including the mechanical issues, the lack of a real need for consumer DAT, and the confusion over new emerging formats. --Tim May Boycott "Big Brother Inside" software! We got computers, we're tapping phone lines, we know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay(a)got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Licensed Ontologist | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."

2 1

the VTW---FBI Connection (fwd)
by Sharma 17 Dec '03

17 Dec '03

I am asking for some verification that you (cypherpunks) have something to do with this before I forward it anywhere. I looked at the vertexgroup and so-oregon webpages, and there is no investigative journalism there that I was able to find. Please get back to me soon. Thanks, sharma sharma(a)aa.net >X-URL: <URL:http://www.vertexgroup.com> >X-URL: <URL:http://www.program.com> >X-URL: <URL:http://www.so-oregon.com> > >>Date: Sun, 21 Jul 1996 20:51:23 -0600 >>To: cypherpunks(a)toad.com >>From: nobody(a)zifi.genetics.utah.edu (Anonymous) >> >>We have received information that VTW is run and supported by the FBI, >>which we have suspected for reasons listed here. >> >>I) They appear to have no financial support or funding source. They >>do not accept donations. They have no corporate funds. And yet they >>appear to be a thriving business. >> >>II) They are secretive about their location, and do not seem to have >>a headquarters. The address listed in the NIC is a vacant lot in of >>all places Brooklyn, NY. They do not have a listed telephone. >> >>III) On a tip from a "friend" we learned that the power leader behind VTW >>is a cleancut man with the unusual name "Shabbir M. Safdar." Not exactly >>a common name. Several people say they've met him. Our "friend" says >>that Mr. Safdar is in reality an agent of the FBI. >> >>IIII) We didn't believe this without external verification. So we called >>the Brooklyn office of the FBI and asked for Agent Safdar. No such person. >>I called the Washington office. No such person. Checked if there is >>any agent named Safdar. They don't give out this info. Then we tried to find >>ANY public records on a Safdar, with no luck. No driver's license in NY, >DC, NJ, >>etc. No phone, etc. Odd that such a person does not exist and yet runs a >>"human rights" organization? Then Alice called the NY FBI office. Asked for >>Agent Safdar. Guess what? "He's not in. Can I take a message". No message, >>thanks. He'll get the message all right. >> >>Now the big question: What is the FBI trying to do getting all these >>names? What else has "VTW" been doing? And what other organizations like >>them are there? Who else is in on it? What does this say about EPIC, CDT, EFF? >>Are Blaze and Schneier dupes, or willing participants? What about their >>ISP? I think we are all owed an explanation. This is serious. Maybe FOIA or >>a lawsuit before they burn the files. >> >>What do you want to bet "VTW" quietly fades away after a few prefunctory >>denials, and gets replaced by another organization in due course? >> >>Faithfully, >> >>Net reporter team Alice and Bob >>

2 1