Since it looks like the US government will be allowing the export of 56 bit espionage-enabled software, it's time to kill single DES. As some of you will recall, a while back I wondered aloud about the feasibility of brute-forcing DES on general purpose machines, ala the RC4-40 crack last year. Unlike many cypherpunks, I actually write code (:-). I took Phil Karn's DES386 as a starting point, and modified it to run effiiciently on the Pentium. The code I've written will run 14 round DES (all that is required for a key test app) at 254,000 crypts/sec on a 90 MHz Pentium. Allow about 10% overhead for key scheduling (there are some tricks to speed this up), and we're still at about 250,000 keys/sec on a 100MHz Pentium (I'm using a nominal 100 MHz Pentium as my 'unit' of cpu power). On a Pentium, it runs entirely in the L1 cache. The code will also run on a 486, but at less than half the number of crypts/sec for the same clock speed. On this type of processor, it would still take 9133 years to exhaust a 56 bit key space. On the other hand, on 20,000 processors of this power it would take less than 6 months. If the target is encrypted in a chaining mode with an unknown 8 byte IV, the time more than doubles. Clearly, this goes far beyond the number of cpus available to the members of this list (though well within the power of most governments and many corporations) The best idea I've heard for recruiting this many cpu cycles is to create a screen saver which does DES-cracking while machines are idle. Another incentive is to offer a cash prize to the person(s) who find the key. Yes, I KNOW that a hardware based cracker is a LOT more efficient, but between the up-front cost and the difficulty of design and production, it's less likely to get done. (Still if someone wants to buy me a nice FPGA board, I'll see what I can do). If you're interested in volunteering machines to do a key search, please read to the end. Questions for general discussion: 1. Is this a good idea? What will happen if DES becomes perceived as insecure? 2. What is the probability of success required to make it worth doing? 3. What would be the consequences of failure? 4. What other platforms than NT/Win95/Pentium should be considered? I could write a Unix demon version, but unless it's tailored for the cpu, a lot of efficency is lost (The aggregate number of idle cycles available for testing is the crucial number). 5. What's a good target? Ideally, we need a plaintext/ciphertext pair, encrypted in Single DES ECB mode. Preferably from a commercially available program, in which a single key is used for a great deal of traffic over a long period. I would strongly prefer, however, that the target key be a *test* key - I don't want to compromise anyone's actual security. We need a target which is both convincing and realistic. 6. What other incentives can be used to recruit machines? ------------------------------ If you're interested in volunteering cycles: RESPOND ONLY TO ME (trei@process.com), NOT TO THE LIST. The last thing we need is a hundred 'I'll help' messages on the list. Assume that the program will be a Win95/NT screen saver or Unix deamon. Think about how many machines you could get it to run on (maybe you can talk other people into installing it as a screen saver or background task) I have not written the screen saver yet. I will not do so unless it looks like we'lll get enough machines, so nothing is likely to happen for a couple of months at least. I need to estimate how many cpu cycles will be available: Calculate: Number of Pentiums * Hours available/week * MHz + (Number of 486's * Hours available/week * MHz * 0.30) For, Alphas, MIPS, Motorola, PowerPC etc, running UN*X, MAC, etc, just report how many cpus, their speed, and OS - I'll need help to get versions for other platfoms. 64 bit processors like the Alpha can run this stuff *fast*. Send the aggregate numbers to me. I'll also need to know how many machines are directly on the Internet and could thus query a key-space server, and how many would need some other mechanism to get keyspace and report results. If you're volunteering machines which are outside of the US/Canada, please note the fact: ITAR may be an issue here. I'll summarize to the list. Peter Trei trei@process.com