Hal Finney <hfinney@shell.portal.com> writes on cpunks:
Another approach is to do lots of keys simultaneously - so you set up this distributed effort which is continually re-sweeping the 40 bit keyspace, say every couple of days or whatever. You can sweep for more than one key at once at very low incremental cost, an extra key costs close to nothing. So say you are searching for 1000 keys at once [...] on average a key will fall out every 3 minutes.
I don't see how you can sweep for more than one key at once at low cost. Because of the salt, every possible SSL encrypted message has to be swept independently. You can't sweep for two messages' keys at once because the input to the MD5 is different even for the same 40-bit key.
Agreed. I was not being clear and mixing various things in one post. I was talking about 3 different systems: 1) export SSL 88 + 40 2) pure RC4-40 (hypothetical - possible microsoft / other apps) 4) DES (56 bits, can it be done) In the part you quote I was talking about pure RC4 40, I'm not sure which applications fall into this category, but it is one thing we have yet to determine. Perhaps Microsoft Access falls in to this category? Other microsoft applications / other vendor applications? someone needs to do the microsoft equivalent of a FOIA to extract this info. Anyone have any Microsoft software with encryption that they could quiz Microsoft tech support about? For export SSL it does not work for the reason you describe, the 88 bit salt effect. For DES I think it does work (attacking many keys at once), but then my understanding of DES is limited, but as a block cipher, presumably you can just brute keys in a straight forward manner? If so you can try multiple keys at once, unless there is some salt effect involved with typical CBC 56 bit DES operation too? Depending on the relative costs of the parts of the block cipher, a) key-setup b) block / stream decrypt pure RC4 is designed so that a) is vastly more expensive than b). How does this pan out for DES? DES (and RC4) are designed for fast encrypt / decrypt, but is there an appreciable key setup phase? I have these figures courtesy of Andy Brown:
Using Eric Young's very fast libdes code, and using the supplied speed test program I get the following output on a Sparc 20 (1 processor):
Doing set_key for 10 seconds 582771 set_key's in 9.83 seconds Doing des_ecb_encrypt's for 10 seconds 989184 des_ecb_encrypt's in 9.85 second Doing des_cbc_encrypt on 8192 byte blocks for 10 seconds 982 des_cbc_encrypt's of 8192 byte blocks in 9.92 second Doing crypt for 10 seconds 37101 crypts in 9.89 second set_key per sec = 59284.94 ( 16.9uS) DES ecb bytes per sec = 803398.17 ( 10.0uS) DES cbc bytes per sec = 810941.94 ( 9.9uS) crypt per sec = 3751.37 (266.6uS)
So what is a brute DES program on multiple keys with CBC mode (is this the most common mode?) going to look like in terms of calls to these various calls? The set_key looks slow compared to the DES cbc bytes per sec, even if you have to cycle a couple of blocks to get to your known plaintext location. Am I on the right tracks? It seems to me that you gain considerably by doing multiple keys even with CBC and random IV due to relatively fast block decrypt as compared to key setup.
If digital cash in micro amounts became practical, people could be paid to let the "idle cycles" on their computers be used for this kind of highly parallel application. (Some people have speculated that graphics rendering would be another suitable choice.) It would be interesting to see what the market price of cycles became in such an environment. That would give a better benchmark for the cost to break keys.
I think this would be an interesting way to determine the market value of idle cycles, and likely lead to cheaper figures for breaking things than are touted (by newspapers, and people to whose advantage it is to estimate generously the cost). Adam