4 ms·

The choice of the numbers used for S-boxes can be very mysterious unless the designers explain it. So reverse engineering the S-box design might reveal somethin

by alister 11y ago

The choice of the numbers used for S-boxes can be very mysterious unless the designers explain it. So reverse engineering the S-box design might reveal something interesting (something good or something evil). For years people thought that the S-boxes in the Data Encryption Standard (DES) hid a back door since the NSA had helped design it. It surprisingly turned out years later that the NSA had actually strengthened the S-boxes against an attack called differential cryptanalysis that was not known to the public crypto community at the time[1]. But neither were they entirely benevolent: The NSA also weakened DES by shortening the key length so they could brute force it, and in the heyday of DES, the NSA was probably the only organization in the world that had the computing power to do so. [1] https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.2...

duskwuff 11y ago
> ...in the heyday of DES, the NSA was probably the only organization in the world that had the computing power to do so. Less an issue of the computing power, more an issue of the knowledge. As you noted, civilian cryptographers hadn't even discovered differential analysis yet, so hardening the cipher against it wasn't even a consideration.
- alister 11y ago
  > Less an issue of the computing power, more an issue of the knowledge. I think you're mixing up two issues: (a) Strengthening DES against differential cryptanalysis is a knowledge issue. The NSA knew about that attack, and maybe the Soviets knew too, but the public didn't. (b) The key length for DES however is entirely a computing power issue; it is not a knowledge issue. It would be obvious to everyone even in 1977 that a 64-bit key as originally proposed would have been better than the 56 bits they ended up using[1]. Furthermore, everyone understood how to do a brute force attack, but it just wasn't feasible for the public. Only the NSA would have had the budget and inclination to develop special-purpose computing hardware to actually do it in the 1980's DES era. [1]I have to mention one nitpick here, otherwise someone else will point it out. The 56-bit key length was supposedly ideal because DES would have been more easily cracked using differential cryptanalysis than brute force with any key longer than 56 bits. Thus the NSA can claim, "no we didn't weaken DES by shortening the key, we optimized it because 64 bits doesn't buy you extra security over 56 bits". But that argument is bogus. They could have improved DES in such a way that it used 64-bit keys and wasn't vulnerable to differential cryptanalysis. But they did the latter and not the former, because it keeps DES secure against the Soviets (assuming they knew about differential cryptanalysis) and against the public (who can't mount a brute force attack) but does allow the NSA to be able crack it.
  - rasz_pl 11y ago
    Coincidentally A5/1 was also compromised down to 56bits.

by alister 11y ago

duskwuff 11y ago

> ...in the heyday of DES, the NSA was probably the only organization in the world that had the computing power to do so. Less an issue of the computing power, more an issue of the knowledge. As you noted, civilian cryptographers hadn't even discovered differential analysis yet, so hardening the cipher against it wasn't even a consideration.

alister 11y ago
> Less an issue of the computing power, more an issue of the knowledge. I think you're mixing up two issues: (a) Strengthening DES against differential cryptanalysis is a knowledge issue. The NSA knew about that attack, and maybe the Soviets knew too, but the public didn't. (b) The key length for DES however is entirely a computing power issue; it is not a knowledge issue. It would be obvious to everyone even in 1977 that a 64-bit key as originally proposed would have been better than the 56 bits they ended up using[1]. Furthermore, everyone understood how to do a brute force attack, but it just wasn't feasible for the public. Only the NSA would have had the budget and inclination to develop special-purpose computing hardware to actually do it in the 1980's DES era. [1]I have to mention one nitpick here, otherwise someone else will point it out. The 56-bit key length was supposedly ideal because DES would have been more easily cracked using differential cryptanalysis than brute force with any key longer than 56 bits. Thus the NSA can claim, "no we didn't weaken DES by shortening the key, we optimized it because 64 bits doesn't buy you extra security over 56 bits". But that argument is bogus. They could have improved DES in such a way that it used 64-bit keys and wasn't vulnerable to differential cryptanalysis. But they did the latter and not the former, because it keeps DES secure against the Soviets (assuming they knew about differential cryptanalysis) and against the public (who can't mount a brute force attack) but does allow the NSA to be able crack it.
- rasz_pl 11y ago
  Coincidentally A5/1 was also compromised down to 56bits.