|
Home | Adults | Youths | Toadies Our Program | Our Post | Our Members | Scouting | The ExpNews |
(C) Mon May 26 18:30:25 EDT 1997 Explorer Post 369
Table of Contents |
DES Security Broken!
PostScript Version
|
(C) Sun Jun 29 10:36:55 EDT 1997 Explorer Post 369
Calendar of Events:
|
Don't Trust Your FirewallDJ GregorHere is some food for thought: Most computer security professionals agree that about 20% of computer security incidents are caused by someone outside the organization, with the remaining 80% being caused by someone inside the organization. Does your budget for computer security take into account these percentages? Do you spend one-fifth of this budget on firewalls and remote access security, and the rest on security within the company? |
What DESCHALL MeansC. Matt Curtin
With all of the press that DESCHALL has gotten, lots of people are asking "what does this mean?" What follows is an explanation, written for the nontechnical reader. This is important for all of us, because regardless of whether you like it, information about you is protected with DES. What's a cryptosystem? Cryptosystems are locks for data. By using mathematical functions (called algorithms), the data is turned into gibberish that can only be returned to a form that makes sense by applying the appropriate key. It's easy to understand how this works by envisioning a bicycle tumbler lock. In a bicycle lock, there are a number of tumblers, each with numbers on it, from 0 to 9. Because computers are binary -- only working with 0s and 1s -- at their most basic level, a cryptosystem is like a bicycle lock that has only two numbers: 0 and 1. On such a lock, there are two possible choices: 0 and 1. By putting another tumbler with 0 and 1 on it, the number of possible combinations increases exponentially from 2 to 4. (In computers, we use "bits" instead of tumblers, but for our purposes here, it means the same thing.) Possible Combinations for Small Binary Locks TABLE 1. ----------------------------------------------------------- Number Number of Possible of Possible Combinations Tumbler Combinati s ons ----------------------------------------------------------- 1 2 0, 1 2 4 00, 01, 10, 11 3 8 000, 001, 010, 011, 100, 101, 110, 111 ----------------------------------------------------------- DES Code Broken! So, not only does the lock have to be strong -- that is, function as it was designed, without allowing a "shortcut" to solve the problem (such as the application of boltcutters) -- it has to have enough possible combinations to make someone trying every single one infeasible. A cryptosystem with only a 3-bit keyspace would have 8 possible keys, as shown in the chart above, or as we see mathematically: 23 = 8. This would not be very secure, since to decrypt the message, I would try to decrypt it using the key 000, then 001, then 010, etc., up until 111, until I am looking at the contents of that message. Let's catch up with our chart, by moving ahead to as many tumblers as what some cryptosystems are using today: Possible Combinations for Larger Binary Locks TABLE 2. ------------------------------------------------------------- Number Number of Possible Combinations of Tumblers ------------------------------------------------------------- 40 1,099,511,627,776 56 72,057,594,037,927,936 64 18,446,744,073,709,551,616 128 340,282,366,920,938,463,463,374,607,431,768,211,456 ------------------------------------------------------------- For a cryptosystem to be secure, there have to be enough possible keys to make it practically impossible for someone to (on a regular basis) try every possible key until they find the right one that works. DES is a 56-bit cryptosystem, first pronounced a standard in 1977. At that time, it was infeasible for someone to try each of more than 72 quadrillion possibilities and find the contents of the encrypted file. At that time, it was safe. We've proven that this is no longer the case. What We Did We took a message that had been encrypted with DES, and read the contents of the message, as well as figured out which key was used to encrypt the message in the first place. At the same time, we now have more data that shows the kind of horsepower we can assemble by having a bunch of people run a little piece of software (called a client) on their computer that has no noticeable effect on their systems' performance. It is noteworthy that this is the first time that a message encrypted with DES has been broken "in public." It's been widely believed that large governments' intelligence agencies (such as the NSA in the US) have been able to do this for quite a few years now. That client took the encrypted message, and decrypted it using every possible key, until we found the one that resulted in some output that made sense. We were trying about 7 billion keys per second at the time that the solution was found. If that computing power -- assembled using a bunch of PCs, Macs, workstations, and some servers -- was applied to the same cryptosystem of different key sizes, we can see how long it would take to decrypt a message by trying every possible key until the right one is found. This is the computer equivalent of turning the tumblers of a bicycle lock to 0000000 0000000 0000000 0000000 0000000 0000000 0000000 0000000
and try again. We do this until we find the right combination. Which means that we tried 37,350,551,110,358,107 of 72,057,594,037,927,936 possible keys. (Mathematicians, please forgive the following oversimplification. We can compensate for the extra work needed to compute RC5 by adding more computers to the project, so this comparison is possible.) Time to Crack Messages Encrypted with Various Key sizes (On the average, at DESCHALL's final speed.) TABLE 3. -------------------------------------------- Number Time to Crack the message of Tumblers -------------------------------------------- 40 78 seconds 48 5 hours 56 59 days 64 41 years 72 10,696 years 80 2,738,199 years 88 700,978,948 years 96 179,450,610,898 years 112 11,760,475,235,863,837 years 128 770,734,505,057,572,442,069 years -------------------------------------------- For comparison, Hawking[1] notes that the age of the universe is probably "only" 20,000,000,000 (or perhaps 10,000,000,000) years old. So, while it's infeasible for DESCHALL to crack a 72 bit key, it seems that 64 might be within reach, by adding more machines. (We probably used between 15,000 and 20,000 machines.) Consider that the RC5-32/12/5 (40 bits) key crack took three and a half hours. The distributed computer we put together could do it in about 78 seconds. The RC5-32/12/6 (48 bits) key crack took 13 days. A DESCHALL-sized effort could do it in 5 hours. Given Moore's Law, which states that computing power will double every 18 months, and the fact that the brute-force searches done for RC5 and DES so far are written in software on general-purpose computers (a extremely slow method, by comparison to custom hardware), one can see how it's useful to get keys up over that 80 bits mark, especially if it's protecting data that has to be secret for any length of time. (US Census data, by law, must remain secret for 72 years[2].) Imagine not only trying to figure out how much money it would take to build a machine to search a 96-bit keyspace today, but also in 99 years from now. Predicting what we'll be using next year is often tricky enough, much less 10 years, 40 years, or 100 years down the road. (See why we're paranoid?) What's the Solution? (How Do We Address this Problem?) It doesn't "cost" us much more, in terms of computer cycles to encrypt something with 128 bits, instead of 40 or 56. Yet, the level of security that we enjoy as a result of that extra step is amazing. We go from being able to trivially decrypt a message in seconds to requiring more time than the age of the universe many times over. The solution, then, is a simple matter of replacing our DES "locks" with locks (cryptosystems) that use larger keys. Many such systems exist: Triple-DES, IDEA, Blowfish, and RC5, to name just a handful of the more well-known options. Data encrypted with DES must be re-encrypted using the new cryptosystems, and applications must be reprogrammed to stop using DES and begin using the new system for their encryption. To be "safe," then, the data that's been encrypted should be worthless by the time someone is able to read it by using brute force. As an example, a credit card that will expire in a year or two from now might be OK to encrypt with a 64-bit cryptosystem. (Anyone who can raise enough money to build a machine that will crack 64-bit-encrypted messages would be able to find other means -- like bribing clerks -- to get the data he wants, so we'll only look at software-based attacks like DESCHALL.) However, it would be stupid to encrypt census data with a 64-bit algorithm, since DESCHALL could find the key in about 41 years (on the average). Factor in Moore's Law, and you're looking at something that can probably be read in a decade with little-to-no effort. It's undesirable to change standards constantly, and be in a perpetual process of upgrading the cryptographic modules of our software. It's also unnecessary. Simply erring in favor of the paranoid and building systems NOW with keys that seem ridiculously long, and re-encrypting our small-key-encrypted data with these systems will adequately address the problem. ...at least until someone gets a quantum or DNA computer working. Then, all bets are off.:-) References
|
Quote of the MonthDid you ever notice you are working harder than ever before so your employer can make a bigger income? Web Statshttp://www.venturingbsa.com TABLE 4. --------------------------- Pages Users Button --------------------------- 174 39 exploring 1025 239 ExpNews 890 94 links 3386 408 post 52 24 1997.calendar 1436 129 members 515 46 Adults 221 50 Toadies 318 46 Youth 369 55 program 20 12 project 204 47 scouting --------------------------- When we installed "Access Watch" we reset the counters. Therefore, the statistics will not show much growth from the April issue of The ExpNews. |
NobannerDJ GregorI just looked at how to setup the Solaris LP system so that a banner isn't printed. Just do the following: Edit /etc/lp/interfaces/<printer_name> Find the line If you want to REVERSE the `-o nobanner' option to lp(1) so that it prints a banner, go down a few lines in the specified file and change "yes" to "no" in this section of code:
The file /etc/lp/interfaces/<printer_name> is created whenever you make a printer, and it is derived from: /usr/lib/lp/model/standard. |
Up-an-Coming Post Expenses
Up-an-Coming Member ExpensesRegistration 11/01/97 $15.00 |
Post Finances
We are looking for a new sponsor for the ExpNews, Can you help? |
This page has been accessed $pagecount"; ?> times. Since July 6th, 1997