Slashdot Mirror
NIST Proposes Abandoning DES
Mr. Manometer writes "With little fan-fare, NIST proposed yesterday to withdraw the Federal Information Processing Standard (FIPS) for the Data Encryption Standard (DES) with a Federal Register notice (pdf). NIST is encouraging federal agencies to use the Advanced Encryption Standard (AES) instead since they feel that DES is 'now vulnerable to key exhaustion using massive parallel computations.' We all knew this day would come as computers got faster & cheaper... and this should put more pressure on folks to use stronger encryption techniques with is a good thing." Some would argue that DES has been insufficient for some time now.
In '76 Lucifer was adopted and renamed "DES". Of course as computers became faster and more powerful, it was recognized that a 56-bit key was simply not large enough for high security applications. As a result of these and other serious flaws, NIST abandoned their official endorsement of DES in 1997 and began work on a replacement, to be called the Advanced Encryption Standard (AES). And so the story continues...
Sigs cause cancer.
I thought NIST had already recommended replacing DES with AES several years ago. It's been fairly obvious for a while now that distributed computing could crack DES encoded data.
It will be AES's time before long anyways, with quantum computing these algorithms become fairly useless.
Actually, triple DES uses one of the keys twice, so you only get a key space of 112 (56 * 2) bits.
Triple DES actually has a key complexity of around 112 bits, but more importantly is signifigantly slower then AES due to the need for three sequential passes with three (or more often two) seperate keys.
As a result AES has more key complexity and runs faster, which is why it makes sense to drop DES/3DES.
Many cryptanalysts don't trust ECC yet because there has not been enough peer review (i.e. attmepts to break it) of the mathematics of the algorithm.
no, the confusion comes from DES being 64-bit with a byte's worth of parity. effective length of single DES key is 56 bits.
now, to really mess it up - the effective key length of 3DES is 112 bits, because only 2 keys are actually used, key A and B. Encrypt with A, then B, then A.
Although DES's key length is short, it's a remarkably strong cipher. There are some methods to crack DES where you can do a ~little~ better than trying all the combinations, but not much better.
r diq.com/definition/Advanced_Encrypti on_Standard
Triple DES extends the key length to something acceptable and there isn't any serious cryptanalytic attack on it -- after decades of people hammering at it. Today we even know that the NSA did a good job choosing the S-boxes (although we could do a little better today.)
AES wasn't really designed to be secure, it was designed to have low CPU and power requirements so it could run on smart cards. As a result, they chose to use the absolute minimum number of rounds that they could get away with. Take away a few rounds and AES falls... If you have to use AES, use it in 192-bit mode or greater. Not for the key length but for the extra rounds.
AES is just a few years old and there are a lot of attacks that are nearly successful and practical. In 128-bit mode it's like a 12-inch wall with an 11-inch long crack in it. That last inch might hold, but I wouldn't bet on it. I tell my clients to use 3DES, and you should too...
http://www.cryptosystem.net/aes/
http://www.wo
Elliptic curve cryptography is a public/private key system like DSA or RSA. It's an asymmetric cipher method where the key used to encrypt is not the necessarily the same key used to decrypt.
DES and AES are symmetric ciphers, where you use the same key for both operations.
The two forms of crypto have different uses, and ECC isn't all that useful as a replacement for DES. That's what AES is for.
As an aside, Diffie-Hellman is a method of key agreement, and is not a cipher in itself, but rather it is used in conjunction with other crypto systems. (IPsec, for instance, uses DH, I believe.)
J
Also, 3DES is about as good as AES with regards to security, but magnitudes slower. Thousands of cycles compared to AES's 100 cycles.
One of the earliest critics of DES (FIPS-46) was Whitfield Diffie, a maverick of his time. The government, industry, and press all hailed the 56-bit DES as a milestone breakthrough. At that time, ITAR regulations limited encryption algorithms to 28 or 40 bits, a serious restriciton for international corporations. IBM was prohibited from using Lucifer with its offshore subsidiaries because the Feds equated it with nuclear weaponry.
Diffie is probably best renowned for his methodology known as knapsack encryption. This was alternative to RSA which was computationally prohibitive in the early 1980s.
I remember my having difficulty in my old college days in obtaining a copy of RSA. My school had to obtain a copy of their paper from MIT through inter-library loan. I had not realized that RSA would gain such widespread adoption because ITAR would prevent international implementation for any US-based company.
signature pending slashdot approval
If you could try one key at every clock cycle, which would be amazing in and of itself, it would take you 54,844,652,936,586,090.5 years of computation on a 3 GHz machine to try every key. If you take half of that it gives you the average time to break the key. So to break it, on average, in one year you would 27,422,326,462,045 3 GHz computers all working together on it non-stop. Still too weak for you? Its amazing what doubling the bits can do to the complexity.
Then we can use it forever.
You mean a one time pad?
You cannot use a one time pad forever. The name should be a pretty good hint about that. Unfortunately reusing a one time pad is suggested again and again by people not fully understanding what it is all about. In many cases a one time pad is unrealistic because you have to exchange new keys over a secure channel. And usually you want to use the one time pad because you don't have a secure channel. But actually some secure channels exists that can be used to exchange the key, but cannot be used for the data transfer. One such example is seen in quantum cryptography.
However though a one time pad is unconditionally secure, it only guarantees secrecy. Integrity is an interely different matter. Luckily there also exist unconditionally secure MACs for that, and they are a lot more realistic than a one time pad, because the key is smaller and most of the key can be reused. This is very important because without integrity over a clasical channel, even quantum cryptography would have been vulnurable to a man in the midle attack.
But quantum cryptography is not the only way to exchange a one time pad. Other unrealistic ways to exchange a one time pad is using either noisy channels or assumptions about memory bounded adversaries. I call them unrealistic because they are both based on somewhat unrealistic assumptions and require extreme amounts of data to be transfered to create a small one time pad. The most realistic way to exchange a one time pad probably still is to do it in advance. In some cases the exchange in advance makes a lot of sense. Think for example wireless equipment. You'd consider a wire to be secure, but it is inconvenient. But you still have to connect a wire occationally to recharge your battery, at the same time a one time pad could be tranfered over a faster and more secure wired link.
Do you care about the security of your wireless mouse?
First of all it should be explained why they came up with 3-DES instead of just 2-DES. The reason is, that 2-DES would be vulnurable to a meet in the middle attack. If you knew just one plaintext/ciphertext pair you could efficiently compute a small set of possible keys. It would require a lot of disk space, but in the end you would be down to approximately 2^48 keys, and it would require only 2^57 cipher block operations. Another plaintext/ciphertext pair can easilly be tested against the remaining 2^48 keys to find the right one.
In other words 2-DES is not significantly more secure than DES, but 3-DES makes the meet in the middle attack more difficult. You can no longer meet exactly in the middle, but you could meet with 1 cipher on one side and 2 ciphers on the other side. That way you have to brute force the 2 ciphers and that way 3-DES presumably give you the security of a 112 bit key. This is also why you normally only use two different keys for 3-DES. The third key would add no extra security.
But 3-DES have inherited one of the weaknesses of DES. The block size is still only 64 bits. That makes you vulnurable to birthday attacks. For this reason I always advice against using the same 3-DES key for more than 512KB of data. With a 128 bit block like AES uses, a key can be safe for use for longer time, I would say 64GB should be secure.
Do you care about the security of your wireless mouse?
The knapsack algorithm was devised by Ralph Merkle and Martin Hellman. Knapsacks would still be computationally prohibitive if they had not been broken.
Also, Whitfield Diffie is certainly best renowned for the Diffie-Hellman algorithm for key exchange.
sig intentionally left blank
Diffie didn't invent knapsack encryption. Diffie and his colleague, Martin Hellman, invented the first public key cryptosystem, Diffie-Hellman, and founded the modern field of cryptography. We all owe them (and Ralph Merkle, who basically did the same things at the same time) an enormous debt.
There were no ITAR limits on key length. The law simply stated that you needed a license to export products that included cryptography; strictly interpreted that would have included a Secret Decoder Ring. It wasn't until Lotus wanted to export Notes with crypto built in that the NSA got involved in the process of making it possible for products that used crypto to be granted export licenses by demanding features such as CDWF, which made it easy for the NSA to break messages while keeping it hard for everyone else.
Lucifer was vulnerable to a differential cryptanalytic attack that reduced the effective key strength to around 56 bits. However, IBM and the NSA kept their knowledge of DC secret until Biham and Shamir rediscovered it in 89.
RSA was invented later. It was never prohibitively slow, though of course it's got much faster over the years.
If you wanted a description of RSA, why didn't you just buy a copy of Scientific American, where it was first published in Martin Gardener's "Mathematical Games" column?
Xenu loves you!
Actually, 3DES uses encrypt with A, decrypt with B, encrypt with A. This makes the degenerate case where A equals B backwards-compatible to single-key DES, and is why 3DES is also called DES-EDE.
However, using 3 keys with any cipher only squares the time to key recovery, regardless of whether the first key and the last key are equal. Assuming you know both the plaintext P and ciphertext C for a given message, compute a table of all possible results of encrypting P with keys 1 and 2, and a table of all possible results of decrypting C with key 3, then join on the intermediate ciphertext. If only 2 keys were used, computing and joining two single-key tables would bring the time cost down to only 1 additional bit of key strength.
...when you're writing a game...tweak the difficulty of "Easy" to something [your mother] can cope with. -- onion2k
It was known when 3DES was proposed that the "meet in the middle" attack reduced the effective strength to 112 bits. Lucks's attacks reduce that strength to 90 bits. See
k s/ papers.html
http://th.informatik.uni-mannheim.de/People/Luc
Xenu loves you!
I misremembered the efficacy of Lucks's attacks - it's more like 90 bits. See
k s/ papers.html
http://th.informatik.uni-mannheim.de/People/Luc
Xenu loves you!
Terrible, terrible, HORRIBLE analogy.
Cryptography rounds are not like walls... It's not like a wall, where defeating each one removes strenghth. In cryptography, even if you can break up to 127-bits, that last 1-bit stll means it's just as strong as ever.
A good example (besides AES) is skipjack... NSA's own. There would have been a vulnerability if it used one less round, but since it uses 1 more, it's still perfectly safe, and hasn't been broken yet...
In other words, find a new analogy, and don't tell people that AES is insecure. It's gone through detailed analysis to make sure it's secure... The same process that approved of DES years ago.
If you trust 3-DES, you should trust AES, too.
Personally, I use blowfish whenever possible, but I haven't seen any crypto hardware with blowfish built-in so I doubt it'll get more widespread anytime soon.
Slashdot gets worse every day... Pipedot: News for nerds, without the corporate slant
More information about the Cryptographic Module Validation Program (the current standard for encryption is FIPS 140-2) can be found here: http://csrc.nist.gov/cryptval/140-2.htm
Also, here's a group which has both Windows and Linux versions of a FIPS 140-2 AES implementation, if you want to know what it looks like in action: http://www.standardnetworks.com/moveitcrypto
They knew. The IBM team discovered differential cryptography (IIRC called it the "T attack") while developing the cipher. NSA already knew about it even then, though, so Biham and Shamir are at least the third set of inventors/discoverers of that technique.
but you can't get collisions with a cipher...?
Encryption is a litle more than just using a cipher. You need some mode of operation. ECB mode where you just split your message into 64 bit blocks and apply the cipher to each is weak. The problem is, that an attacker can easilly see which blocks contains the same cleartext, because they will all result in the same ciphertext. I once saw this illustrated by encrypting some black and white image where each 8x8 pixels where encrypted using DES in ECB mode. In the encrypted version you could still faintly see the outline of the original picture.
We have a definition of semantic security, that handles this and other problems. It is impossible to achieve semantic security with a deterministic encryption, you need a probabilistic encryption, where a litle randomness is added to the message. The encrypted message will then be larger than the original, and if the same cleartext is encrypted twice, you will get different ciphertexts. Typically you would use modes like CBC or CFB where the encrypted version is just one block longer than the original. So a 1000 bytes cleartext would be 1008 bytes encrypted. What happens in CBC mode is that each cleartext block is XORed with a random bitstring before being encrypted. Actually you only chose a random bitstring for the first block, for the remaining blocks you use the encrypted version of the previous block, but that is actually random because the cleartext was XORed with a random bitstring before being encrypted.
So in CBC mode you will not be encrypting your cleartext, but rather a sequence of random blocks. As long as you don't encrypt the same block more than once, the adversary cannot learn anything about your message, without actually performing an attack against the cipher. But if you keep using the same key for a long time, eventually two random blocks will be the same, and the adversary will be able to see this, and can use it to compute some information about the cleartext.
Do you care about the security of your wireless mouse?