Fred Cohen <fc@all.net> wrote on cpunks:
Since messages sent with netscape are fairly standard for the first so many bytes, why not make a 2^30 element table, store it on a few gigabytes of disk space, use a hash table on the message, and find the keys to one in every 1,000 messages about 1 time per second. If this code is being used to send millions of credit transactions per day, we should be able decode thousands of credit card numbers per day for a one-time cost of about $5,00.
Nice idea and one which works for pure RC4, but unfortunately not for 128 bit, 88 bit known + 40 bit unknown "export" SSL. Netscape's SSL uses "40 bit keys" that are composed in a strange way: you are given 88 bits of known key, and this is combined with the 40 bit key, to give a 128 bit key. That key is used to do the encryption. The problem is that this has a unix password salt like effect, only this time there are 88 bits of salt rather than 12 bits. So this means that you can't precompute anything on the 40 bits as the 88 bits are randomly generated, and likely vary with each session.
The $10,000 estimate of the cost of computing time is far too high for a production-based attack on the netscape codes.
Agreed, it's too high for the other reason that lots of people have spare compute cycles. Idle cycles have low to non-existant incremental cost, and there are plenty of them around in the world. Back to breaking crypto systems. There are a couple of things you can do, there is your pre-compute some proportion of the key space - so that you get some of them, this would work well for straight 40 bit RC4 - and there are quite probably such products around - microsoft has a number of "secure" [sic] things around the Microsoft Access we were looking at earlier, another system for doing remote access (modem) and having the sessions encrypted. The problem with micro$oft is they are a darn closed system, and no-one so far has invested the time to decode what they're doing with a debugger. That was the reason for the failed brute RC4 a while back - no specs. So precompute regions of keys would work on pure RC4-40 as you describe. It would be fast too - a disk seek time being the bounding factor - per key! 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 - a dragnet approach - well keys just pop out at random as they are hit, maybe straight away maybe at worst case the sweeping roll-over time, but on average a key will fall out every 3 minutes. The same approach is applicable to 1 guy with 1 humble PC, it'll sweep the full keyspace it in a year or two, but what does he care if he gets a couple of keys a day, and they're all nice transactions he can pilfer / make nefarious use of. DES breaking schemes... Something similar applies to DES, I mean what's a piffling 56 bit keyspace if you don't really care *which* key of several thousand that you actually want. There are bound to be a large enough supply of DES encrypted banking transactions flowing around the various financial networks in the US to make a nefarious breaking of them emminently possible. It moves on the time for a complete sweep as you now have 56 bits to contend with - but I think with a team of say 1024 workstations like the one I am typing on (an SGI Indy ~$5k workstation) in a distributed effort, and a large supply of DES keys, you could get a workable break on *one* of those keys in a shortish time how long? Well I'm not sure how fast DES can be made to go for these purposes, but 60k keys/sec is a figure I have for DES set_key (Eric Youngs code on a Sparc 20) I'm not too sure of the details of what you'd need to brute a DES key, but setting up the key, and presumably a small additional cost to test the first byte and every 256 tries to test 2 bytes etc. Anyone know if 60k keys/sec sounds reasonable for a DES brute? Anyway working on that, 1024 workstations, 60k keys/sec = 60 M keys/sec = 37 years! But (here's the saving bit) if you try say 64k keys *at once* so you've hoovered up a stack of keys (hypothetically - technically plausible too a tap on a banking network should yield you a whole load of them) *then* you can get much nicer figures: A DES key every 5 hours! I'm thinking 1024 workstation equivalents shouldn't be insurmountable to organise - lots of people have faster / multiprocessor machines, and farms of workstations / PCs etc. Perhaps 64k keys is a bit generous, and 1024 keys would be a more sensible figure, even then that translates to 13 days expected. As some one said a while ago (breaking) Netscape is the big win! Breaking DES is *the* big win! Adam -- HAVE *YOU* EXPORTED RSA TODAY? --> http://dcs.ex.ac.uk/~aba/rsa/ --rsa--------------------------8<------------------------------- #!/bin/perl -s-- -export-a-crypto-system-sig -RSA-3-lines-PERL $m=unpack(H.$w,$m."\0"x$w),$_=`echo "16do$w 2+4Oi0$d*-^1[d2%Sa 2/d0<X+d*La1=z\U$n%0]SX$k"[$m*]\EszlXx++p|dc`,s/^.|\W//g,print pack('H*',$_)while read(STDIN,$m,($w=2*$d-1+length($n)&~1)/2) -------------------------------8<------------------------------- TRY: rsa -k=3 -n=7537d365 < msg | rsa -d -k=4e243e33 -n=7537d365