December 2003 - cypherpunks-legacy

Nx2 DES Found Weak
by ritter＠cactus.org 17 Dec '03

17 Dec '03

Ritter Software Engineering 2609 Choctaw Trail Austin, Texas 78745 (512) 892-0494, ritter(a)cactus.org Nx2 DES Found Weak Terry Ritter February 11, 1994 Summary Any Nx2 DES system succumbs to meet-in-the-middle attack at a cost only N times that of normal DES, and is probably not worth using. If we assume that DES would fall with 2^55 cipherings (on average), then the 4x2+ DES system which I previously recommended would require only 2^57 cipherings. Such an attack, however, might require substantially more storage and might be more difficult to mechanize and slower in operation than an attack on normal DES. Nx3 DES systems seem not to be affected by this attack, but they are also not faster than triple-DES (1x3 DES), which was the main reason for recommending Nx2 DES over triple-DES. On the other hand, Nx3 DES systems apparently would provide added strength against dictionary attacks; such attacks might be possible against ASCII plaintext when ciphered in small 8-byte blocks. Double-DES A 1x2 DES construct (double-DES) is something like this: A v k1 -> DES1 v B v k2 -> DES2 v C Each single capital letter represents an 8-byte DES block. Meet-In-The-Middle Attack on 1x2 DES (double-DES) [ This is probably similar to: Merkle, R. and M. Hellman. 1981. On the security of multiple encryption. Comm. ACM 27(4): 465. which I have not seen. This analysis resulted from trying to understand the comments on NxM DES made by email from Eli Biham, which led me to: Davies, D. and W. Price. 1984. Security for Computer Networks. Wiley. 75. and the attack on double-DES. Obviously I did not expect that attack to work on Nx2 DES, or I would have skipped Nx2 entirely. ] First we need some known-plaintext (A) and its associated ciphertext (C). Now we encipher A with every possible random key k1 and save the results. Then we decipher C with random keys k2, eventually finding a match to the enciphered data. There are many possible pairs of keys (k1, k2) which will produce matching B's. Since there are 112 key bits (k1, k2), and we match 64 bits each time, there should be about 112 - 64 or 48 bits of freedom (that is, 2^48 possibilities) to be resolved with one or two more known-plaintext blocks. We can guarantee to find the correct key pair if we try every possible key for k1 and also every possible key for k2; this is only twice the effort of a full DES key search, and we need only search half that, on average. (In practice, we would do some k1's and then some k2's, repeated until success occurred.) However, we should note that this technique may require the intermediate storage of 2^56 results. This would be over 2^59 bytes of store, and this amount of storage and lookup is not nearly as easy or fast as the on-chip ciphering-and-compare solution for DES. Still, the result is not comforting. A 2x2 DES construct is something like this: A B v v k1 -> DES1 k2 -> DES2 v v C D Exchange Half E F v v k3 -> DES3 k4 -> DES4 v v G H Meet-In-The-Middle Attack on 2x2 DES Suppose we first try the 2x1 approach: With one known-plaintext block, we can search two keys (say k1 and k2) until a match is found for the center block. Then we can validate that match with additional known-plaintext blocks. (Since there is only a 32-bit match-check and a 112-bit keyspace, there will be 112 - 32 or 80 bits of freedom to resolve at about 32 bits per known-plaintext pair, so we would want to check a minimum of 3 or 4 other known-plaintexts. The cost of the subsequent cipherings and comparisons would be relatively insignificant, however.) We can guarantee that the two keys will be found by searching all possible k1 and k2. This is only twice the normal DES keyspace, and we only need search half of that, on average. And we can do this again for the other two keys at a similar cost. Again, the attack hardware will be considerably more awkward than any simple search for a DES key which matches a given ciphertext value, but the total number of DES cipherings will be about twice the DES keyspace, on average. Nx2 DES Falls Similar arguments lead to the conclusion that, for any N, Nx2 DES must be generally comparable in strength to DES itself. This means that the larger block has not helped strength much in any Nx2 DES system, despite the fact that every ciphertext bit is demonstrably a function of every plaintext bit in the large block as well as every bit in all the separate DES keys. Note that the form of the inter-stage permutation has absolutely no effect on this attack or overall strength, despite the fact that a great deal has been written about designing S-P permutations. The meet-in-the-middle attack seems not to apply to Nx3 DES. Dictionary Attacks Normally we define "strength" as the *minimum* effort expected to "break" a cipher, when taken over *all possible attacks*. Working out the extent of "all possible attacks" is a major part of the effort in cryptography. With respect to DES, most of the current attacks have considered the relatively-small 56-bit keyspace. But I am also concerned by the relatively-small 8-byte block size. Consider an 8-byte block of ASCII text: Modern data-compression programs typically compress such data by 60 percent. This means that we typically have less than 26 bits or so of "uniqueness" in the various blocks. Rigidly-formatted business documents, letters, or forms would be even less unique, and, thus, even more attackable. To the extent that a substantial amount of known-plaintext could be acquired (or possibly even inferred), a dictionary attack becomes possible. For this reason, if a change is to be made, then I would like to see a block size at least four times that now used. This would be a reasonable approach with a 4x3+ DES system, which would be comparable in throughput to a 1x3 DES system, but, alas, not faster. Conclusion A two-stage or Nx2 DES construction is probably not worth using.

2 1

What is the CANNET/NEWBRIDGE RNG-810
by Paul Elliott 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- I have been asked by several cypherpunks what the CALNET/NEWBRIDGE RNG-810 is. It is a board you can place in a 8 or 16 bit slot of an 80x86 computer. Each time you do an inb instruction for the board's port address you get a random byte. I have one in my computer, and it works. I got mine from CALNET electronics INC. I paid $300 for it several years back. However I have been informed that CALNET no longer sells them and they must be obtained from NEWBRIDGE MICROSYSTEMS. See quoted message: >From: bretth(a)Newbridge.COM (Brett Howard) >To: Paul.Elliott(a)hrnowl.lonestar.org >Subject: Calnet RNG-810 > > >Paul, > >The RNG-810 is now licensed to Newbridge Microsystems. I have done some work > with a 1-bit hybrid version of the technology (RBG-1210) and I do > know a *little* bit about it. If you have questions, you should > probably write to Newbridge (address at bottom) or you can email > me and I'll do my best! > >Take care, >Brett > >Newbridge Microsystems >603 March Rd. >Kanata, Ontario >Canada K2K 2M5 >Tel: 1-800-267-7231 > 613-592-0714 >FAX: 613-592-1320 I have a catalog from Newbridge Microsystems, Document:90000.MD300.02, Copyright 1992. Page 4-77 Says: "The NM 810 RNG Random Number Generator is an implementation of the latter approach, with eight RBG 1210s in parallel and a PC XT/AT bus interface. Random bytes are input to the computer through an I/O (Input/Output) port. Any data type (integer, floating point etc.) can then be easily constructed in software by using successive random bytes and arranging them according to the desired internal data format." I do not know if Newbridge still has RNG-810s to sell. Perhaps someone will call the 800 number above and find out. One restriction that I received in the docs with my CALNET RNG-810 is that if you attempt to read the device too fast (less the 40u sec between reads), the succesive bytes are not randomly independent. This is a problem for my IO driver as you do not want to do a spin wait on a real operating system like OS/2 and timer interrupts only occur 18.2 times per second. This causes my driver to run _MUCH_ slower than the hardware would require. I believe that the simple interface used by the RNG-810 is natural enough that it is likely to be used by others who create random number generators. And so my driver may be useful with other devices. But I have received mail recently from someone that makes a RNG that you attach to you serial port and runs at 9600 baud. You could probably use your standard serial port driver with such a device. - -- - ------------------------------------------------------------------------------ Paul Elliott Telephone: 1-713-781-4543 Paul.Elliott(a)hrnowl.lonestar.org Address: 3987 South Gessner #224 Houston Texas 77063 -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLVtrJ/BUQYbUhJh5AQH6UQP/TXJ5X14vUKPf1J8To5AtwQchPrgabUBT 03lN0+XbsDE6JEgJm7SDN1e3B5EqNEZGi3RMh63HMN7oYf1f7UUMGVoZJdqFNmBM e09s37VcGsZZaZZnlXb5ogQwnjeNGkRSoldWqMcwYQWSBZJskpohHvqrhoge7MQ4 Ka9jDhGCNhg= =ULN8 -----END PGP SIGNATURE-----

1 0

An available RNG
by bart＠netcom.com 17 Dec '03

17 Dec '03

I got this recently, but hesitated to post, after previously being told by folks on the hardware list "thats too much". Perhaps not, compared to the RNG-810 that Paul Elliot spoke of. Forwarded message: > From bierman(a)cc.ruu.nl Mon Feb 7 08:44:23 1994 > Date: Mon, 7 Feb 1994 17:42:36 +0100 > Message-Id: <199402071642.AA18036(a)accucx.cc.ruu.nl> > X-Sender: bierman(a)accucx.cc.ruu.nl > Mime-Version: 1.0 > Content-Type: text/plain; charset="us-ascii" > To: bart(a)netcom.com (Harry Bartholomew) > From: bierman(a)cc.ruu.nl (Dick J. Bierman) > Subject: Re: Your hardware RNG > > NOW AVAILABLE (second series)/ ordering info at the end of this file/ > > > Hardware Random Number Generator > > Random Number Generator > Excerpt from the USER MANUAL > > How the RNG works > The Random Number Generator consists of two independent analogue > Zener diode based noise sources. Both signals are converted into random bit > streams, combined and subsequently transmitted in the form of bytes to the > RS-232 port of your computer. Special timing circuits ensure that crucial > logical operations occur at moments that the device has stable signals. > The baud rate is 9600. So the device is capable of supplying you with about > 960 random bytes or 7600 random bits per second > Power is drawn from the RTS and TXD signal. (pins 4 and 2 of the D-25 > connector). In order to work properly the RTS signal should be high (5 volts > or higher) and one should not send bytes to the device! > > WARNING: part of the RNG is shielded. It is not recommend to open the > device. It is not allowed to copy or use the design of the RNG without > written permission of the developer, the Foundation for Fundamental > Research on Man and Matter (FREMM). > > The testdata > Each RNG passes a 256 run randomness test before being shipped. Each run > consists of 8192 samples. The unselected results of this test are included > with the package. If at the end of the test runs the cumulative first order > deviation is larger than 1.5 standard deviations the RNG is tested another 20 > times. If it is accepted after these 20 tests this will be indicated. > > How to connect the RNG to the computer > The RNG is functionally similar to a 'crazy' modem producing random > information to your machine. It should be connected like any modem. In > some cases when the computer has a standard D-25 male connector you can > plug the RNG directly into that connector. In other cases (e.g.. for Apple > machines) you have to connect the RNG through a standard modem cable. > > > > SOFTWARE supplied on the disk > > DOS > > The program RTEST (for listing see appendix) takes two arguments. > > RTEST <port> <ncycles> > > <port> indicates which serial port is used (either 1 or 2. (default:2)). > <ncycles> gives the number of test runs. One test run consists of reading > 26500 bytes and calculating the Chi-2 and the number of bits on each one of > the eight positions within the byte. If more test runs are specified the > numbers (except the chi-2) accumulate. > If the program is started it will display one sample from the specified port. > More samples can be displayed by hitting the ENTER-key. > Continuous sampling of the test runs is started by the ESC key. The results > will be available for further statistical analysis in the textfile 'TEST'. > > The program RAND3 takes one argument. > > RAND3 <port> > > This program starts in the same way as RTEST by displaying individual > samples after each time the ENTER key is hit. . After hitting the ESC key > continuous sampling starts and the bytes are displayed tin a graphical form > in real time. The continuous samples can be restarted by hitting the space- > bar. Exit through the ESC key. > > The software addresses the serial port directly. It is also possible to > implement a driver which is interrupt driven (like the software supplied for > the Mac). A driver is available upon request and can also be obtained > electronically from the FTPsite: > PSI_LINE.psy.uva.nl > in directory GUESTS/RNG/SOFTWARE/DOS > In the near future this site will also offer PK-test programs. > > Macintosh > > The Macintosh software is based upon the standard serial port drivers rather > than on direct access of the serial ports. The bufferspace for this driver > should be large enough to hold incoming bytes while the driver is active and > no reading occurs. In cases where this is not clear one should close the > driver and reopen it when needed. > In the examples the modem-port is used. In the listings it is indicated how to > use the printer-port. > > RNG_test > The program rng_test will ask for the number of test runs to perform. Each > test run consists of 8192 samples. The chi-2 (df=255) and the number of '1' > bits minus the number of '0' bits on each of the positions within the byte are > displayed after each run. Chance expectation is of course 0. When more runs > are specified the cumulative number of '1' bits minus the cumulative > number of '0' bits are displayed as well as the corresponding standard > deviation. > All data are saved in the file RNGTESTDATA. Each run on a separate line > and the data separated by spaces. > > __________ END OF EXCERPT FROM USER MANUAL _______ > > ORDERING INFORMATION: > > Single unit: $195, -excl shipping; add $10 shippng for the US & Asia, > $5 for Europe > > Reduction is possible for larger quantities. > > > Send check to: > Stichting FREMM > Alexanderkade 1 > 1018 CH Amsterdam > The Netherlands > > Make check payable to: Stichting FREMM > > or send your order by FAX to: > > (+31) 20 4206075 > > With a signed specificiation of your mastercardnumber & expiration date. > > Contact for more info: > bierman(a)cc.ruu.nl > > > _______ DJB________ > > >

1 0

No more "Nazis on the Nets"
by danisch＠ira.uka.de 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- Hi everyone, we have to stop this discussion. I have more than 20 mails in my mailbox, everyone very long, serious, interesting and waiting for response. But I can't answer them all within reasonable time, I also have to do my regular work. Furthermore I have a lot of mails of people asking me to stop this discussion "between two persons". Some don't see that it has anything to do with cryptography. I don't share this oppinion, because if we talk about communication, we also have to talk about the danger and the restriction of communication. The german right-/left-wing as well as the american Mafia are known to use modern computer networks, cryptographical software and methods of system security and access control. We can not close the eyes and just don't care about what is done with the tools we are contructing. Meanwhile I can somehow understand that there has to be any form of export restriction if people constructing such tools have so many problems with thinking about possible forms of bad use of their tools. And again I got confirmed what we find so often in so many cases: People love to talk and form a judgement of Germany and don't even really know what they are talking about. This is a never-ending problem of Germany. In this special case of Naziism you should be aware that they found not only germany nazi computer networks. They found this network to be the international connection to other country's nazis, especially Austria, Great Britain and USA. Two of the german politicians asked to forbid private mailbox systems and even modems. Of course this is stupid, but perhaps your politicians get the same idea. When I read the clipper proposals I think they already had such an idea. Hadmut -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLVuI3mc1jG5vDiNxAQGenwQAhruLOjvjbLuLGgnN+48gXneOtT3x0iV7 DIexTGAubZUCW8UCMy5/pOF1nGMgs5GMdZzUzy4TJGoAAsyuoLRTuVjVDqMjBIL1 9mIH/wNRxGj/55YjEWXylPM+PzSZwCerTbJs0Vo2YWwcMRbqd4a/+hb0ji6ul6iT 83Tby8FihjE= =Uy5j -----END PGP SIGNATURE-----

1 0

INFORMATION
by rcasella＠sescva.esc.edu 17 Dec '03

17 Dec '03

I am new on Internet and want to communicate with others.

1 0

csn.org:/mpj/ updates
by Michael Johnson 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- The following updates are available at csn.org:/mpj/ and the Colorado Catacombs BBS (303-938-9654): Magic Money 1.0d -- also requires PGP Tools to compile. /mpj/I_will_not_export/crypto_???????/pgp_tools/mgmny10d.zip PGP Tools 1.0c -- This is the PGP Tools 1.0b difference file sent to me by Pr0duct Cipher, merged with the PGP Tools 1.0 file. Note to Pr0duct Cipher - -- please skip rev c, since I needed to differentiate between files before and after merging them. /mpj/I_will_not_export/crypto_???????/pgp_tools/pgptl10c.zip Secure Drive 1.3a -- On-the-fly sector by sector encryption/decryption with the IDEA cipher for MS-DOS. /mpj/I_will_not_export/crypto_???????/secdrv/secdr13a.zip Other files, including PGP, are available. See /mpj/INDEX. Note to users who want "real crypto" with no magic numbers and no clue what program created the encrypted files -- see mpj2demo.zip. An upgrade of this program that is friendlier and does better variable length key expansion is due out "soon." The upgrade fixes the problem with keys being equivalent to larger keys that repeat the smaller keys (i. e. abcde unlocks what was locked with abcdeabcde). The upgrade will also attempt to find a compromise between ease of use and denial of header information from an adversary. Stay tuned... Because of the International Traffic in Arms Regulations, you must first read csn.org:/mpj/README.MPJ and (1) agree to the access terms therein, and (2) note the characters to replace the ??????? in the directory names above before you can access these files. The crypto_??????? directory is hidden, so it will not show up in a directory listing, but you can change to it. The name of the crypto_??????? directory changes at random times. This is a pain, but I'm open to suggestions on other ways to distribute crypto software widely and easily within the USA without violating the law. I think a crypto related access control method would be really cool, but that raises some chicken and egg issues. See csn.org:/mpj/help for more on accessing the crypto areas. Access to crypto areas on the Colorado Catacombs BBS is easier -- just follow the questionaires carefully if you qualify for access. ___________________________________________________________ |\ /| | | | | \/ |o| | Michael Paul Johnson Colorado Catacombs BBS 303-938-9654 | | | | / _ | mpj(a)csn.org ftp csn.org \mpj\README.MPJ for access info.| | |||/ /_\ | aka mpjohnso(a)nyx.cs.du.edu mikej(a)exabyte.com | | |||\ ( | m.p.johnson(a)ieee.org CIS 71331,2332 VPGP key by finger | | ||| \ \_/ |___________________________________________________________| -----BEGIN PGP SIGNATURE----- Version: 2.4 iQCVAgUBLVsGlD9nBjyFM+vFAQGdbAP8DcItGC54YPT1xBcgSXZuGu3bxxF7xgeR F4N3iGUbuXP3eC2NcO/+EjJx170qP0CITaYZTTo9lRaeVptCKZkKolegjkatWTcu WTLjIRE9T64fNieMTH2DXFtEv8pFjQn392YEnDHqBNtzKPBCxsf8qNI4V2MRQplH JD/+aX/JasI= =T9FO -----END PGP SIGNATURE-----

1 0

Re: FLASH: Vice President Gore Questions Current Key Escrow Policy!
by djw＠eff.org 17 Dec '03

17 Dec '03

At 10:21 PM 2/10/94 -0800, John E. Kreznar wrote: >> The Electronic Frontier Foundation is working to protect your privacy. To >> help stop Clipper and eliminate export controls on cryptography, support a >> bill introduced in the House of Representatives, HR 3627. To support the >> bill, send email to <cantwell(a)eff.org>. > >I wish I knew how to help you wake up and smell the contradiction here. >In one breath you acknowledge that government is an enemy of privacy, >and in the next you encourage acting to endorse and empower that very >government by petitioning it. > >Secede now! Then your works need not be exported from US because they >wouldn't be there to begin with! Part of waking up and smelling the coffee is realizing that there IS a government out there which makes and enforces laws which have an impact on all of us. Now I happen to believe that, on balance, it's a good thing to have a government that is at least marginally representative. But even if I didn't believe that, I would believe that we should be working to change laws that screw up our lives. ************************************************************************** Relying on the government to protect your privacy is like asking a peeping tom to install your window blinds. - John Perry Barlow, EFF co-founder The Electronic Frontier Foundation is working to protect your privacy. To help stop Clipper and eliminate export controls on cryptography, support a bill introduced in the House of Representatives, HR 3627. To support the bill, send email to <cantwell(a)eff.org>. ...................................................................... Daniel J. Weitzner, Senior Staff Counsel <djw(a)eff.org> Electronic Frontier Foundation 202-347-5400 (v) 1001 G St, NW Suite 950 East 202-393-5509 (f) Washington, DC 20001 *** Join EFF!!! Send mail to membership(a)eff.org for information ***

1 0

Meeting this Saturday
by solovay＠math.berkeley.edu 17 Dec '03

17 Dec '03

If one can't spare the time for the whole meeting, what are the best three hours to come? Thanks, Bob Solovay

2 1

Clipper note in NY Newsday
by dmandl＠lehman.com 17 Dec '03

17 Dec '03

The following appeared in today's New York Newsday (2/11/94): ------------------------------------------------------------------------- Gov't Backs Away From "Clipper" Chip The Clinton administration yesterday backed away from key elements of its encryption standard in the wake of protests over the use of the so-called Clipper chip. Vice President Al Gore said he wanted the holders of the "keys" that would allow government agencies to eavesdrop on scrambled conversations to include private companies and the court system. The Clipper would be used to scramble conversations over phone lines and computer networks. In declaring it the standard last week, the federal government was ensuring that the Clipper will be built into every phone and computer. But several civil-liberties groups and some companies objected to the fact that the chip has a "back door" that would allow law-enforcement agencies who obtain the proper court warrants to unscramble conversations and eavesdrop. --Joshua Quittner and Stuart Vincenti -------------------------------------------------------------------------

1 0

Magic money coins.dat files
by qwerty-remailer＠netcom.com 17 Dec '03

17 Dec '03

There was an error in the earlier message describing format of the magic money coins.dat files. The C.ID field (my name for it) has as its low 16 bytes not the coin ID, but rather the MD5 hash of the coin ID. This is supposed to make it harder to create fake money, according to the earlier discussion on cypherpunks list.

1 0