17 ms·

Back when DES was being designed, IBM had a bunch of values in their S-boxes. NSA told them "don't use those values; use these values instead." People freaked

Back when DES was being designed, IBM had a bunch of values in their S-boxes. NSA told them "don't use those values; use these values instead." People freaked that it was a backdoor the NSA put in. About 15 years later, differential cryptoanalysis was publicly discovered. The original S-box values would have been very vulnerable to the attack, but the ones the NSA used were resistant, suggesting that NSA knew about differential cryptoanalysis way ahead of time and were suggesting ways to protect the public against its eventual discovery. It is possible that there is still some magic in there to let the NSA magically defeat DES, but we still haven't found it. Similarly, it's possible that this random number generator exists for some nefarious purpose, but we have no evidence for it. Also, this article is 5 years old (the headline didn't say so when I first read this). Schneier was in pretty big self-promotion mode at that time.

Nikker 14y ago
Don't forget that IBM actually designed Lucifer which was 128bits but it was the (edit:s/NSA/NHIS) that truncated it to 56bits and named it DES. So maybe this is an example of "6 of one or half a dozen of the other"?
- tptacek 14y ago
  And don't forget that Eli Biham smote Lucifer with differential cryptanalysis, found more than half of the keys insecure, reduced its security to 235, and published a journal article concluding that NSA strengthened the cipher design; DES was better than Lucifer.
  - Nikker 14y ago
    Maybe 3 decades after it was released according to this paper; http://scholar.google.ca/scholar_url?hl=en&q=http://59.127.136.65/crypto/biham.pdf&sa=X&scisig=AAGBfm2hvYp0XLUMppevbSUagUxH60-pPw&oi=scholarr&ei=aYJkUOCbAof50gG5-ICwDA&ved=0CBsQgAMoADAA http://scholar.google.ca/scholar_url?hl=en&q=http://59.1... Even if the NSA appointed S-Boxes did improve Lucifer then decreasing the block size does not really improve on your point.
    - tptacek 14y ago
      You're not arguing with me; you're arguing with Eli Biham. He addressed the question you asked head on.
CWuestefeld 14y ago
I can't find the citation right now, so treat this as apocryphal, but... I've read an explanation that the USA's focus on security has changed in the days since 9/11/2001. At one time, the philosophy was that the country was more secure when we could all be assured that the privacy of our communications was intact. But in the last decade we've changed that philosophy. The government's security philosophy now is that the most important thing is for the government to be able to tell what's going on. So it may be that the parent post's anecdote is quite correct, and reflects the policy of that time. But in the days of the War On Terror, we can't trust that anymore. (And OT, I believe it reflects a fundamental change in the philosophy of governance that is against the founding principles of the country, and a pretty bad thing. I believe that our strength derives from ... us -- we the people. And so strengthening the government by weakening us in fact weakens the nation.) EDIT: fix date. Thanks, Retric.
- dpark 14y ago
  > At one time, the philosophy was that the country was more secure when we could all be assured that the privacy of our communications was intact. That's never really been the view of the U.S. government. It's always been the view that you should be able to have communications with your neighbor that are secure from everyone except the US government, who obviously need to snoop in order to protect us all. The security agencies and the police agencies have always pushed for more comprehensive and more invasive surveillance. We've had wiretapping for as long as we've had wires to tap. We crippled Internet security for years. I remember the days of separate US and international Netscape releases, due to crypto export restrictions. It wasn't until 2000 that the restrictions were truly relaxed.
  - pgeorgi 14y ago
    US and international Netscape releases (as well as Windows and various other tools) rather indicate that the US govt was interested in secure communication for US citizens and corporations, while being able to snoop on the rest of the world. If you need an example, pick the Clipper chip - and even that doesn't _quite_ work out, given how publically that proposal was shot down.
antidoh 14y ago
Well, the NSA is building that data center in Utah to store and process all the data they're hoovering up. That data would be much more useful if it weren't encrypted. So they do at least have a motive, even if the ability can't be proved.
- Nelson69 14y ago
  If I'm not mistaken, they've sort of tweaked the definition of "interception" too. The game plan is to capture everything and then it's 'intercepted' when they actually listen and analyze it.
  - sigkill 14y ago
    So do they basically work on the definition of Schroedinger's box? "We've captured a bunch of data. But as long as we don't observe it, it's not legally going to be counted as intercepted." Sounds to me, like a massive slippery slope just waiting to happen.
    - Nelson69 14y ago
      Yeah, you think? That was the talk at Defcon, I didn't do enough follow up to find out but it's pretty open that the new Utah data center can store every American's phone calls, emails, .. everything for a century. If you can slip that through whoever it is that protects us, there are some corner cases. Say we do rub out a terrorist cell that does a successful attack (20 years after this database is running,) could you then mine that database to determine if your AI that finds terrorists works? If I was training up voice finger printing algorithms and such, you have an incredible dataset and there are likely other signals coming in to help populate it (maybe the census? say you're training something that detects Arab accents) Never mind the fact that it's so huge and so much data that 1) is has to be online and 2) all intelligent queries will be given to AI/Google like software agents to find. Could a future president query the database to dig up dirt on an upcoming election opponent? (He's the president right?)
      - 14y ago
Flenser 14y ago
suggesting that NSA knew about differential cryptoanalysis way ahead of time and were suggesting ways to protect the public against its eventual discovery The NSA may also have know who else knew about differential cryptoanalysis, and didn't want it to be weak in ways that others could break it, but left it weak in ways that they could.
- dalke 14y ago
  You would think that after this many decades any such built-in weakness to DES would have been discovered. Do you think the NSA crypto knowledge (or rather, IBM crypto knowledge, since that's where differential cryptanalysis was developed) back in the 1970s was better than the modern crypto knowledge?
  - DanBC 14y ago
    To give one small example: Clifford Cocks invented RSA about 3 years before RSA did. But he did it by himself, and he did it in his head. Cocks' version was revealed 25 years after he created it; 22 years after RSA was revealed. They're only just released some of the stuff that Turing did. They keep things secret, and they use things hard. There's not really anyway to know what they know about your system, which is why cryptography likes systems that seem secure even when you know everything about that system. (http://www.youtube.com/watch?v=a-xEiOvXux4 http://www.youtube.com/watch?v=a-xEiOvXux4)
    - trhtrsh 14y ago
      "3 years" in not quite the same secret head start that "30 years" is.
      - DanBC 14y ago
        The point is that even though PKI had been independently developed, and made public, 3 years after Cocks did it they still kept it secret for 22 years. So imagine what they do with the secrets that are still secret - the secrets not independently developed and made public.
cerebrum 14y ago
From https://en.wikipedia.org/wiki/Differential_cryptanalysis https://en.wikipedia.org/wiki/Differential_cryptanalysis "In 1994, a member of the original IBM DES team, Don Coppersmith, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal."
apawloski 14y ago
To expand a little, the NSA also required the initial permutation of plaintext bits. This was done before the first 16 rounds of DES, and looked like this: 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Which meant "put the 58th bit of the plaintext into the first position, put the 50th bit into the second position, etc, and THEN run through the encryption algorithm." At the time, it was totally unclear why you had rearrange the bits in this very exact way. After all, you were about to encrypt it (and obliterate any plaintext patterns) anyway. And would it be as strong if you started with the 57th bit, instead of the 58th? The whole thing seemed so arbitrary. Now it's true that this is robust to differential cryptanalysis, but it's also true that these bit permutations significantly slow down software implentations of DES. But it's trivial to implement the initial permutation in hardware. In the 1970s, the hardware required to crack DES costed $20,000,000 US dollars [1] (about $120 million in today's dollar [2]). The general tinfoil-theory at the time was that 1) only the NSA had the resources to build such a machine and 2) by forcing DES to use this initial permutation, the NSA was giving themselves a significant "head-start" over everybody else using software to crack DES. [1]http://www.krapp.org/hydra/courses/analysis/3-DataEn.pdf http://www.krapp.org/hydra/courses/analysis/3-DataEn.pdf (PDF) [2]http://www.wolframalpha.com/input/?i=%2420%2C000%2C000+1970+dollars+today http://www.wolframalpha.com/input/?i=%2420%2C000%2C000+1970+...
- pbsd 14y ago
  The permutations in DES have nothing to do with security; there is an excellent explanation by Thomas Pornin on what their purpose was: http://crypto.stackexchange.com/a/6/592 http://crypto.stackexchange.com/a/6/592 What was altered were the 8 S-boxes, seemingly random lookup tables that map 6- to 4-bit values. More details by Don Coppersmith himself at: http://simson.net/ref/1994/coppersmith94.pdf http://simson.net/ref/1994/coppersmith94.pdf
  - apawloski 14y ago
    I phrased that poorly (and just edited my first sentence to reflect your correction). What I was trying to add was that the NSA made some other modifications to DES that were also seen as dubious at the time.
stanfordkid 14y ago
Spot on. You have to realize that the government buys software and systems that rely on encryption from the private sector. It is in their own interest to have the strongest crypto in government hardware and software. So while they know a lot of exploits they also know that it is quite plausible that our enemies know the same exploits (i.e China, Russia) and using government hardware that uses a poor standard is not a great idea.
stordoff 14y ago
It is possible that the NSA modified this RNG for perfectly good reasons, but, in my opinion, even the slight possibility of an attack existing is too high when other better RNGs exist.
- tptacek 14y ago
  This isn't a controversy. Nobody would have used that RNG anyways. There's probably no bignum math in any commonly used RNG, let alone elliptic curve math. Not only that, but Dual EC had problems even before Furguson pointed out the parameter weirdness. You do not need to be on guard against secret NSA Dual EC backdoors.
gizmo686 14y ago
>>It is possible that there is still some magic in there to let the NSA magically defeat DES, but we still haven't found it. Actually the NSA s-boxes are weak against linear crypto analysis. http://reference.kfupm.edu.sa/content/l/i/linear_cryptanalysis_of_des_diploma_thes_83690.pdf http://reference.kfupm.edu.sa/content/l/i/linear_cryptanalys... If I remember Schneider's applied cryptography correctly, the NSA s-boxes were among the worst 7% possible. I wonder what we would be saying about the NSA if we (publicly) discovered linear crypto-analysys before differential. However, I suspect the vulnerabilty to linear analysys is the result of how structured they made it to resist differential.

Nikker 14y ago

Don't forget that IBM actually designed Lucifer which was 128bits but it was the (edit:s/NSA/NHIS) that truncated it to 56bits and named it DES. So maybe this is an example of "6 of one or half a dozen of the other"?

tptacek 14y ago
And don't forget that Eli Biham smote Lucifer with differential cryptanalysis, found more than half of the keys insecure, reduced its security to 235, and published a journal article concluding that NSA strengthened the cipher design; DES was better than Lucifer.
- Nikker 14y ago
  Maybe 3 decades after it was released according to this paper; http://scholar.google.ca/scholar_url?hl=en&q=http://59.127.136.65/crypto/biham.pdf&sa=X&scisig=AAGBfm2hvYp0XLUMppevbSUagUxH60-pPw&oi=scholarr&ei=aYJkUOCbAof50gG5-ICwDA&ved=0CBsQgAMoADAA http://scholar.google.ca/scholar_url?hl=en&q=http://59.1... Even if the NSA appointed S-Boxes did improve Lucifer then decreasing the block size does not really improve on your point.
  - tptacek 14y ago
    You're not arguing with me; you're arguing with Eli Biham. He addressed the question you asked head on.

CWuestefeld 14y ago

I can't find the citation right now, so treat this as apocryphal, but... I've read an explanation that the USA's focus on security has changed in the days since 9/11/2001. At one time, the philosophy was that the country was more secure when we could all be assured that the privacy of our communications was intact. But in the last decade we've changed that philosophy. The government's security philosophy now is that the most important thing is for the government to be able to tell what's going on. So it may be that the parent post's anecdote is quite correct, and reflects the policy of that time. But in the days of the War On Terror, we can't trust that anymore. (And OT, I believe it reflects a fundamental change in the philosophy of governance that is against the founding principles of the country, and a pretty bad thing. I believe that our strength derives from ... us -- we the people. And so strengthening the government by weakening us in fact weakens the nation.) EDIT: fix date. Thanks, Retric.

dpark 14y ago
> At one time, the philosophy was that the country was more secure when we could all be assured that the privacy of our communications was intact. That's never really been the view of the U.S. government. It's always been the view that you should be able to have communications with your neighbor that are secure from everyone except the US government, who obviously need to snoop in order to protect us all. The security agencies and the police agencies have always pushed for more comprehensive and more invasive surveillance. We've had wiretapping for as long as we've had wires to tap. We crippled Internet security for years. I remember the days of separate US and international Netscape releases, due to crypto export restrictions. It wasn't until 2000 that the restrictions were truly relaxed.
- pgeorgi 14y ago
  US and international Netscape releases (as well as Windows and various other tools) rather indicate that the US govt was interested in secure communication for US citizens and corporations, while being able to snoop on the rest of the world. If you need an example, pick the Clipper chip - and even that doesn't _quite_ work out, given how publically that proposal was shot down.

antidoh 14y ago

Well, the NSA is building that data center in Utah to store and process all the data they're hoovering up. That data would be much more useful if it weren't encrypted. So they do at least have a motive, even if the ability can't be proved.

Nelson69 14y ago
If I'm not mistaken, they've sort of tweaked the definition of "interception" too. The game plan is to capture everything and then it's 'intercepted' when they actually listen and analyze it.
- sigkill 14y ago
  So do they basically work on the definition of Schroedinger's box? "We've captured a bunch of data. But as long as we don't observe it, it's not legally going to be counted as intercepted." Sounds to me, like a massive slippery slope just waiting to happen.
  - Nelson69 14y ago
    Yeah, you think? That was the talk at Defcon, I didn't do enough follow up to find out but it's pretty open that the new Utah data center can store every American's phone calls, emails, .. everything for a century. If you can slip that through whoever it is that protects us, there are some corner cases. Say we do rub out a terrorist cell that does a successful attack (20 years after this database is running,) could you then mine that database to determine if your AI that finds terrorists works? If I was training up voice finger printing algorithms and such, you have an incredible dataset and there are likely other signals coming in to help populate it (maybe the census? say you're training something that detects Arab accents) Never mind the fact that it's so huge and so much data that 1) is has to be online and 2) all intelligent queries will be given to AI/Google like software agents to find. Could a future president query the database to dig up dirt on an upcoming election opponent? (He's the president right?)
    - 14y ago

Flenser 14y ago

suggesting that NSA knew about differential cryptoanalysis way ahead of time and were suggesting ways to protect the public against its eventual discovery The NSA may also have know who else knew about differential cryptoanalysis, and didn't want it to be weak in ways that others could break it, but left it weak in ways that they could.

dalke 14y ago
You would think that after this many decades any such built-in weakness to DES would have been discovered. Do you think the NSA crypto knowledge (or rather, IBM crypto knowledge, since that's where differential cryptanalysis was developed) back in the 1970s was better than the modern crypto knowledge?
- DanBC 14y ago
  To give one small example: Clifford Cocks invented RSA about 3 years before RSA did. But he did it by himself, and he did it in his head. Cocks' version was revealed 25 years after he created it; 22 years after RSA was revealed. They're only just released some of the stuff that Turing did. They keep things secret, and they use things hard. There's not really anyway to know what they know about your system, which is why cryptography likes systems that seem secure even when you know everything about that system. (http://www.youtube.com/watch?v=a-xEiOvXux4 http://www.youtube.com/watch?v=a-xEiOvXux4)
  - trhtrsh 14y ago
    "3 years" in not quite the same secret head start that "30 years" is.
    - DanBC 14y ago
      The point is that even though PKI had been independently developed, and made public, 3 years after Cocks did it they still kept it secret for 22 years. So imagine what they do with the secrets that are still secret - the secrets not independently developed and made public.

cerebrum 14y ago

From https://en.wikipedia.org/wiki/Differential_cryptanalysis https://en.wikipedia.org/wiki/Differential_cryptanalysis "In 1994, a member of the original IBM DES team, Don Coppersmith, published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal."

apawloski 14y ago

To expand a little, the NSA also required the initial permutation of plaintext bits. This was done before the first 16 rounds of DES, and looked like this: 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Which meant "put the 58th bit of the plaintext into the first position, put the 50th bit into the second position, etc, and THEN run through the encryption algorithm." At the time, it was totally unclear why you had rearrange the bits in this very exact way. After all, you were about to encrypt it (and obliterate any plaintext patterns) anyway. And would it be as strong if you started with the 57th bit, instead of the 58th? The whole thing seemed so arbitrary. Now it's true that this is robust to differential cryptanalysis, but it's also true that these bit permutations significantly slow down software implentations of DES. But it's trivial to implement the initial permutation in hardware. In the 1970s, the hardware required to crack DES costed $20,000,000 US dollars [1] (about $120 million in today's dollar [2]). The general tinfoil-theory at the time was that 1) only the NSA had the resources to build such a machine and 2) by forcing DES to use this initial permutation, the NSA was giving themselves a significant "head-start" over everybody else using software to crack DES. [1]http://www.krapp.org/hydra/courses/analysis/3-DataEn.pdf http://www.krapp.org/hydra/courses/analysis/3-DataEn.pdf (PDF) [2]http://www.wolframalpha.com/input/?i=%2420%2C000%2C000+1970+dollars+today http://www.wolframalpha.com/input/?i=%2420%2C000%2C000+1970+...

pbsd 14y ago
The permutations in DES have nothing to do with security; there is an excellent explanation by Thomas Pornin on what their purpose was: http://crypto.stackexchange.com/a/6/592 http://crypto.stackexchange.com/a/6/592 What was altered were the 8 S-boxes, seemingly random lookup tables that map 6- to 4-bit values. More details by Don Coppersmith himself at: http://simson.net/ref/1994/coppersmith94.pdf http://simson.net/ref/1994/coppersmith94.pdf
- apawloski 14y ago
  I phrased that poorly (and just edited my first sentence to reflect your correction). What I was trying to add was that the NSA made some other modifications to DES that were also seen as dubious at the time.

stanfordkid 14y ago

Spot on. You have to realize that the government buys software and systems that rely on encryption from the private sector. It is in their own interest to have the strongest crypto in government hardware and software. So while they know a lot of exploits they also know that it is quite plausible that our enemies know the same exploits (i.e China, Russia) and using government hardware that uses a poor standard is not a great idea.

stordoff 14y ago

It is possible that the NSA modified this RNG for perfectly good reasons, but, in my opinion, even the slight possibility of an attack existing is too high when other better RNGs exist.

tptacek 14y ago
This isn't a controversy. Nobody would have used that RNG anyways. There's probably no bignum math in any commonly used RNG, let alone elliptic curve math. Not only that, but Dual EC had problems even before Furguson pointed out the parameter weirdness. You do not need to be on guard against secret NSA Dual EC backdoors.

gizmo686 14y ago

>>It is possible that there is still some magic in there to let the NSA magically defeat DES, but we still haven't found it. Actually the NSA s-boxes are weak against linear crypto analysis. http://reference.kfupm.edu.sa/content/l/i/linear_cryptanalysis_of_des_diploma_thes_83690.pdf http://reference.kfupm.edu.sa/content/l/i/linear_cryptanalys... If I remember Schneider's applied cryptography correctly, the NSA s-boxes were among the worst 7% possible. I wonder what we would be saying about the NSA if we (publicly) discovered linear crypto-analysys before differential. However, I suspect the vulnerabilty to linear analysys is the result of how structured they made it to resist differential.