Re: IBM's original S-Boxes for DES?
From: Dave Howe [EMAIL PROTECTED] Sent: Oct 5, 2004 12:32 PM To: [EMAIL PROTECTED] Subject: Re: IBM's original S-Boxes for DES? More accurately, they didn't protect against linear cryptanalysis - there is no way to know if they knew about it and either didn't want to make changes to protect against that (they weakened the key, so may have wished to keep *some* attacks viable against it to weaken it still further), had to choose (against *either* differential or linear, as they didn't know how to protect against both) or simply the people doing the eval on DES didn't know, as it was rated above their clearance level. I believe people have since come up with S-boxes that resist both linear and differential cryptanalysis. But we don't know whether there were still other attacks or constraints they were trying to address. However, it makes no sense to assume that they left linear attacks in as a backdoor, for two reasons: a. They already left a 56-bit key, which was a practical backdoor for people with experience and expertise in building keysearch machines. (Think of all the expertise in parallel and distributed keysearch that has come out in the public world in the last fifteen years; surely, that was an area NSA had worked on at great depth years earlier! Things like time-memory tradeoffs, parallel collision search and meet-in-the-middle search, clever optimization tricks for getting the keysearch to run efficiently, etc., along with a large hardware budget, must have made a 56-bit key look much worse from inside the agency than from outside. (Though there were plenty of people who saw the problems from outside, as well, thus leading to our current understanding of keysearch techniques.) b. Linear attacks on DES, at least the ones we know about, are spectacularly impractical, requiring more plaintexts than you could ever hope to get from an innocent party using the speeds of hardware available when DES was designed and standardized. --John - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: IBM's original S-Boxes for DES?
Steven M. Bellovin wrote: It was only to protect against differential cryptanalysis; they did not know about linear cryptanalysis. More accurately, they didn't protect against linear cryptanalysis - there is no way to know if they knew about it and either didn't want to make changes to protect against that (they weakened the key, so may have wished to keep *some* attacks viable against it to weaken it still further), had to choose (against *either* differential or linear, as they didn't know how to protect against both) or simply the people doing the eval on DES didn't know, as it was rated above their clearance level. We only have a single event to go from (that DES was indeed protected against one not the other) so can't really judge motivation or knowledge. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: IBM's original S-Boxes for DES?
In message [EMAIL PROTECTED], Nicolai Moles -Benfell writes: Hi, A number of sources state that the NSA changed the S-Boxes (and reduced the ke y size) of IBM's original DES submission, and that these change were made to strengthen the cipher against differential/linear/?? cryptanalysis. Does anybody have a reference to, or have an electronic copy of these original S-Boxes? It was only to protect against differential cryptanalysis; they did not know about linear cryptanalysis. See Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, IBM Journal of Research and Development, Vol. 38, n. 3, pp. 243-250, May 1994. --Steve Bellovin, http://www.research.att.com/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: IBM's original S-Boxes for DES?
In a personal interview with Walt Tuchman (IBM at the time, worked for StorageTek when I met him, now retired) he described the process for creating the s-boxes. A set of mathematical requirements were created and candidate s-boxes meeting these requirements would be printed out on a regular basis. The process ran over a weekend on a 360/195 and the results were given to the ASIC developers to determine which would result in the smallest ASIC size. One was selected by them. I was told that after the requirements were set, NSA did not have a hand in selecting the final S-Boxes. jim http://www.stortek.com/hughes On Sep 30, 2004, at 12:25 PM, Steven M. Bellovin wrote: In message [EMAIL PROTECTED], Nicolai Moles -Benfell writes: Hi, A number of sources state that the NSA changed the S-Boxes (and reduced the ke y size) of IBM's original DES submission, and that these change were made to strengthen the cipher against differential/linear/?? cryptanalysis. Does anybody have a reference to, or have an electronic copy of these original S-Boxes? It was only to protect against differential cryptanalysis; they did not know about linear cryptanalysis. See Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, IBM Journal of Research and Development, Vol. 38, n. 3, pp. 243-250, May 1994. --Steve Bellovin, http://www.research.att.com/~smb - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
IBM's original S-Boxes for DES?
Hi, A number of sources state that the NSA changed the S-Boxes (and reduced the key size) of IBM's original DES submission, and that these change were made to strengthen the cipher against differential/linear/?? cryptanalysis. Does anybody have a reference to, or have an electronic copy of these original S-Boxes? Nicolai. [Moderator's note: Google for information on the original cipher, called Lucifer. --Perry] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]