IBM's original S-Boxes for DES?

[John Kelsey]

>From: Dave Howe <DaveHowe at gmx.co.uk>
>Sent: Oct 5, 2004 12:32 PM
>To: cryptography at metzdowd.com
>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 majordomo at metzdowd.com