3DES weak because DES falls to brute-force? (was Re: John Gilmore...)
[recipients list trimmed somewhat] I think it is always reasonable to be cautious, but there is a point where overcautiousness is counterproductive. Believing 3DES weak because DES is so strong that it has thusfar withstood more analysis than any other cipher and only falls to brute force is, I believe, one of these cases of excessive paranoia. Assumptions: * Brute forcing DES with a 56-bit key took $50k in materials in today's money. * 3DES with 3 keys is strong enough to resist everything weaker than a 112-bit brute force attack (due to the meet-in-the-middle attack) * Physics, as you say, is not optional. * The notation 2**56 is two raised to the fifty sixth power. At first approximation, doing the same thing to a 112bit 3DES problem would require 2**56 more chips. and thus 2**56 more money, to do in the same amount of time. My copy of gnu bc tells me this is "3602879701896396800000", or three and a half sextillion dollars. This is more than a billion times the current world industrial output. This is somewhat of a naive calculation, though. Those chips were not ideal. There's a general rule about chips doubling in transistor count (and for this application, performance) every 1.8 years. Assuming this rate of improvement, and let's say a random factor of a million for better design, and a fabrication improvement rate (due to buying all your raw-materials suppliers, them becoming more efficient, etc.) which together with Moore's law doubles performance every year (mostly for ease of calculation). Let's assume the target is to be able to complete the calculation within ten centuries. It is better to wait until this is possible before starting than to start and run a calculation for a billion years waiting for it to catch up, as few things are of value that far in the future, and also there is the time value of money to worry about. Let's also place a budget cap of $20t US today's money on the problem at the start of calculation. (2**56)*50000/1000000 == 3602879701896396 dollars today 1000*365/3 == 121660 gilmore-kocher periods in a 1000 years 3602879701896396/121660 == 2961433258175568 dollars today to crack in 1000 years log(2,2961433258175568) == slightly more than 51 years So, this *highly* optimistic calculation says that even if we are willing to assume an *incredible* performance speedup due to better technology and vertical integration that continues unabated (and exceeds reality), *and* we're willing to wait 1000 years for our answer, *and* are willing to spend $20t to build the machine, it is at least 51 years before you should start. This also doesn't take into account the incredible power consumption of such a machine -- about half a million times more than the gilmore-kocher machine. I assume their chips drew 5 watts each -- it would need 3 GW, which is a major nuclear facility with multiple reactors. Cost of power is *not* going down, so it's about $250 billion dollars a year in electricity, for 1000 years. This doesn't take into account the potential for a "technology refresh" throughout the 1000 year calculation period. It's a long enough period of time to make this significant. I'd say the odds of an analytic attack against DES or a fundamental breakthrough in quantum computing or something in 50 years, let alone 1050 years, are far higher than the chances anyone would go through this much trouble. While I agree that data intended to remain secure should be secured with something other than 3DES, it is for the potential of a breakthrough in algorithms, not speedup in brute force techniques, which is worrisome. Brute force techniques are basically public knowledge. A secret analytic breakthrough, however, could be completely black. The solution some people have come up with is multiple ciphers used in such a way as to be as strong as the strongest link. The increase in keysize is not a major issue for something intended to last this long. If you can get a cipher which has as its weakest point a brute force attack, you have won. If you can get a *system* which has as its weakest point a brute force attack on a 112 bit key, you've probably killed everyone in the world already several times over in a preemptive strike, especially everyone who ever had any knowledge of the keys or data. Humint, monitoring hardware, etc. are far more appealing than a brute force attack against any real system. -- Ryan Lackey rdl@mit.edu http://sof.mit.edu/rdl/
Sigh. One should not do math before coffee. Let's try this again: If you assume 2^56 requires $50k and 3 days, and are willing to take 2^8 times longer and spend 2^16 times more, and want to break a 2^112 bit key, and assume technology doubles in performance for this particular operation per year, then the calculation is easy to do. 112 - 56 - 16 - 8 = 32 If you wait 32 years, and have *incredible* performance gains in excess of what we have now (but which I think could be possible for worst-case crypto breaking chips, since they have relatively little in the way of communication, and have small units), and have a budget of 16 times what the DES cracker had (about $3b, which is totally reasonable), and are willing to wait about 2 years, you can brute force 3DES in the year 2030. There is still very little that is relevant in 32 years, and there is still a far better chance that some analytic attack will be discovered, a fundamental breakthrough in computation will happen, etc. before that time. 112 bits is below the "physical impossibility" point as far as key size goes (I like the calculation based on free energy in the universe in Applied Crypto). Chapter 7 in Applied Crypto is probably a far better analysis than mine, especially as it includes the caveat emptor section. Perhaps it is correct, "It's time to bring on those 128, 192, and 256-bit keys", at least for some systems, although I'd definitely prefer multiple ciphers separately keyed with long keys than n-DES for such long-term use. Calculating future key lengths really *is* a losing game. -- Ryan Lackey rdl@mit.edu http://sof.mit.edu/rdl/
On Mon, 20 Jul 1998, Ryan Lackey wrote:
Humrph .. your calculations came in just before I was gonna send mine out .. bc is a nice utility, ain't it? :)
Well, I disagree here.. unless the "something other than 3DES" is an OTP, of course. I don't see anything that looks better than DES, minus the key-size issue. DES has had the fiercest analysis done on it for the longest amount of time. If we are worried about a breakthrough in the algorithmics, then it seems to me we ought to use DES based on the fact that it has been analyzed longer, and has proved itself strong. We've covered the new vs. old algorithm debate here recently, so I'll shut up.. suffice it to say, I fall in line with the 'old' school. I don't find it useful to worry about possible new general cryptanalytic breakthroughs: it is basically impossible to defend against them. In the face of an attacker who has infinite secret cryptanalytic ability (within the bounds of what can be done brute-force wise) only an OTP would be useful, but we are talking long-term archival here.. I don't see how an OTP helps us. If we have a secure vault to lock the pads up in until either a) the heat death of the universe, or b) the Big Crunch then we may as well just put the plaintext in there and be done with it. As I see it, OTP are only workable in communications, and then obviously in a limited manner. Michael J. Graffam (mgraffam@mhv.net) http://www.mhv.net/~mgraffam -- Philosophy, Religion, Computers, Crypto, etc I think that we should be men first, and subjects afterward. It is not desirable to cultivate a respect for the law, so much as for the right. Henry David Thoreau "Civil Disobedience"
Are we talking long-term archival? I'm more concerned about someone grabbing communications in transit, storing them and throwing chips and mathematicians at it. If the government comes with the search warrant, then I should have already deleted the file if I didn't want it available. If someone wants to face security guards or a gun by my bedside they can steal the archive. It's the same rules as always. (except the theif must also have the math and chips). In the case of archive you have the protection of physical security and in most cases the knowledge of when it has been breached -- It's a lot friendlier than in communications where who knows what is going on between the sender and recipient. OTP is a pain, and is not effective for archival -- but it is the only way I've seen to protect communications in excess of ~30 years. Bryan Waters http://www.ultimateprivacy.com Director of Marketing Voice: 512-305-0505 Fax: 512-305-0506 Ultimate Privacy Corporation 3925 W Braker Ln #305, Austin, TX, 78759
participants (3)
-
Bryan Waters
-
mgraffam@mhv.net
-
Ryan Lackey