20

On the French wikipedia page about DES it says that the original DES algorithm from IBM used 112 bit keys.

Why did they reduce this to 56 bits?

Edit: ok NSA convinced IBM but today it seems like a mistake. So did they have objective arguments or just impose their will?

psmears
  • 900
  • 7
  • 9
Whysmerhill
  • 562
  • 4
  • 14
  • 1
    Maybe the french Wikipedia is just wrong? The english Wikipedia states that they discussed between 48, 56 and 64 bits. https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design – Lukas May 09 '16 at 11:54
  • 3
    As I recall, Lucifer used 112 key bits. DES (which was based on Lucifer) never had keys that long, however. – user May 09 '16 at 12:30

2 Answers2

34

The NSA convinced IBM that 56 bits was "enough":

But whereas Lucifer had a key that was 112 bits long, the DES key was shortened to 56 bits at the request of the National Security Agency.

from Practical UNIX & Internet Security

In the development of DES, NSA convinced IBM that a reduced key size was sufficient

from Data Encryption Standard - Wikipedia

The NSA made two changes to DES: It tweaked the algorithm, and it cut the key size by more than half.

from The Legacy of DES - Bruce Schneier

Sjoerd
  • 28,707
  • 12
  • 74
  • 102
  • 5
    By convinced, you mean that they already at the time found a way to decrypt it by reducing the key to 56 bits and hide it to everybody or you mean convinced **convinced** ? – Mxsky May 09 '16 at 14:09
  • 3
    @Mxsky: More like "Hey guys, anything beyond 56 bits we can currently not break, and you know we don't like that, sooo about that party you had last weak..." – PlasmaHH May 09 '16 at 15:03
  • Don't forget, at the time the hardware cost was significant, too. – JDługosz May 09 '16 at 15:12
  • 5
    IBM wanted 64 bits, NSA wanted 48 bits. The compromised on 56 bits. It is plausible that the NSA could crack 48 bit keys in a reasonable time in 1977, but I don't think it is likely that the NSA could crack 56 bit keys. EFF cracked a 56 bit DES key in 56 hours in 1998. Using Moore's law to go back to 1977 (i.e. halving the number of work every two years), that would mean that a 46-bit key in 1977 would also take 56 hours to crack. a 48-bit key would then take 9 days, a 56-bit key would take 6 years. – Sjoerd May 09 '16 at 15:15
  • 14
    @Sjoerd You underestimate the difference in resources. EFF built [Deep Crack](https://en.wikipedia.org/wiki/EFF_DES_cracker) for less than $250,000 in 1998 ($375,000 today). [NSA's budget](https://en.wikipedia.org/wiki/National_Security_Agency) is **$11 billion _a year_**. Diffie and Hellman sketched out a DES machine in "[Exhaustive Cryptanalysis of the NBS Data Encryption Standard](https://www-ee.stanford.edu/~hellman/publications/27.pdf)" for $20 million in 1977 ($80 million today). NSA plausibly could have decrypted DES from day 1. – Matt Nordhoff May 09 '16 at 15:58
  • 7
    @MattNordhoff What was NSA's budget in 1977? I don't know exactly for that year but based on previous budgets I could tell you it was no where close to $11 billion. And the NSA's focus in the 70s was on satellite surveillance which likely ate into most of their budget. – Bacon Brad May 09 '16 at 18:13
  • @Sjoerd are you sure you can use Moore law to consistently estimate cracking times like you did? Seems like a nice discussion over crypto.SE... – Mindwin May 09 '16 at 20:22
  • @Mindwin, no, I am not sure. It is just a guess. Even if the speed of the hardware follows Moore's law, the cost and practical possibilities may not. – Sjoerd May 10 '16 at 13:37
  • Taking the useful part of perdo-werneck answer, "convinced' may have included the official argument of smaller memory footprint. What OTHER motivations there may have been is possibly left to speculation, though "so they could decrypt it while no-one else could" seems very plausible. – kaay May 13 '16 at 08:55
9

Key size was reduced to 56 bits because IBM wanted to fit LUCIFER on a single chip. LUCIFER then became DES.

Because of the promising results produced by the LUCIFER project, IBM embarked on an effort to develop a marketable commercial encryption product that ideally could be implemented on a single chip. The effort was headed by Walter Tuchman and Carl Meyer,and it involved not only IBM researchers but also outside consultants and technical advice from the National Security Agency (NSA). The outcome of this effort was a refined version of LUCIFER that was more resistant to cryptanalysis but that had a reduced key size of 56 bits, in order to fit on a single chip.

Stallings, W. Cryptography and network security, 5th ed.. p.78

Pedro Werneck
  • 190
  • 6
  • Hmm... I frist heard the NSA story 30+ years ago. I wonder if your reference is correct. [This answer](http://security.stackexchange.com/a/122743/10885) has references for the NSA story that I've heard. Alas, we may never know the truth. – Neil Smithline May 10 '16 at 04:35
  • Well... 30+ years ago people were worried that NSA interfered to make DES weaker, but that conspiracy theory has been proven wrong long ago. – Pedro Werneck May 10 '16 at 14:17
  • Interesting. Can you add some references? I consider Bruce Schneier to be a pretty solid reference (see above answer). It wouldn't be unheard of for them to do this as, thanks to Snowden, we know that they [messed with RSA algorithms](http://www.reuters.com/article/us-usa-security-rsa-idUSBRE9BJ1C220131220). BTW, I didn't downvote this answer as you have a good reference. I view it as a different opinion and not a wrong answer. – Neil Smithline May 10 '16 at 14:35
  • @NeilSmithline references to what else exactly? – Pedro Werneck May 10 '16 at 15:34
  • For `that conspiracy theory has been proven wrong long ago` – Neil Smithline May 10 '16 at 15:36
  • @NeilSmithline Seriously? OK. "It took the academic community two decades to figure out that the NSA "tweaks" actually improved the security of DES." http://www.cnet.com/news/saluting-the-data-encryption-legacy/ – Pedro Werneck May 10 '16 at 15:58
  • 1
    Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/39564/discussion-between-neil-smithline-and-pedro-werneck). – Neil Smithline May 10 '16 at 16:01
  • @perdo-werneck Your link shows no proof disproving the idea; key length limitations [are a thing that was being done](https://en.wikipedia.org/wiki/Export_of_cryptography_from_the_United_States#PC_era), the idea is not a fringe one and not shaved by Occam's Razor Yes, NSA improved the math. Yes, there is the "fit on a single chip" explanation for cutting key size. Doesn't mean it was their only/main reason, OR a *requirement* for putting it on a chip. I am not claiming I know the truth better than you, only that you're being rude, belittling others with a "conspiracy theorist" label. – kaay May 12 '16 at 13:44
  • @kaay First, it doesn't make any sense to claim NSA deliberately made the algorithm weaker for everyone else, and more resilient to their own attacks. Second, I use the term "conspiracy theory" as an objective description, not as an insult. The claim that IBM and NSA conspired to reduce key length with malicious intent is a conspiracy theory, unless someone provides evidence for that. It's not bellitlement, it's what it is. Maybe you're used to the expression "conspiracy theory" being used as an insult and think I'm being rude. – Pedro Werneck May 12 '16 at 19:25
  • @perdo-werneck [First](https://en.wikipedia.org/wiki/Argument_from_ignorance). Second: I remind you the reason we are talking about it is because you wrote the claim *had been proven wrong*. Not "never been proven true". "Proven wrong". That is what has drawn attention of people who either believed a motivation that *had been demonstrated in similar cases*, or *suspended judgement*, awaiting *proof* either way. It is not here. [nrn](http://www.thefreedictionary.com/Nrn). – kaay May 13 '16 at 08:44
  • @kaay Again, it doesn't make any sense to claim NSA deliberately made the algorithm weaker for everyone else and more resilient to their own attacks, unless you're claiming that deliberate decision was malicious itself, to give them plausible deniability over the other malicious decision to reduce key size. This is the very definition of a conspiracy theory, where evidence against it becomes part of it, making it unfalsifiable. So, if you think my answer can be improved in any way, I'm all ears. Otherwise, as I said before, I'm not going to argue all day over a conspiracy theory. – Pedro Werneck May 13 '16 at 17:10
  • "*I can't imagine how they could at the same time fix its exploitable bugs AND weaken so that only they could decrypt it*" is "the very definition" of an [argument from incredulity]. (https://en.wikipedia.org/wiki/Argument_from_ignorance#Argument_from_incredulity.2FLack_of_imagination). And maybe evidence of [other problems](http://homepages.rpi.edu/~sofkam/isuny/idp.html). You've turned @neal-smithline's claim ("PROOF against it? Please, where? ... Again, where does it say that?") and mine ("you've not shown it's been disproven; it remains probable") into something they're not. I'm done here. – kaay May 14 '16 at 12:35
  • @kaay Again, if you think my answer can be improved in any way, feel free to contribute. Otherwise, not only this is not the place for this kind of discussion, I'm not interested in that at all. If you have an axe to grind, go somewhere else. – Pedro Werneck May 14 '16 at 19:55