CDR: RE: Musings on AES and DES
---------- From: Vin McLellan[SMTP:vin@shore.net] Reply To: Vin McLellan Sent: Monday, October 09, 2000 3:22 AM To: Ray Dillinger; cypherpunks@cyberpass.net Subject: Re: Musings on AES and DES
Ray Dillinger <bear@sonic.net> wrote:
<snip>
[As the DES,] Dataseal/Demon/Lucifer was pretty good. It may not have been the *most* secure algorithm of its time, but neither was it a transparent and useless "cipher" with obvious flaws other than the 56-bit keyspace. However, the important part of building up trust (or lack thereof) in the cipher came after it was chosen as the DES.
I suggest that you give insufficient weight to the importance of the NSA imprimatur on the DES.
The DES became the standard we know today -- for years, universally accepted in US commerce, banking, and trade -- largely because
the US National Security Agency (NSA) issued, upon the designation of the DES by NIST, a statement that the NSA's cryptanalysts knew of no attack on
the DES algorithm more effective than a brute force search of all possible
56-bit keys. [...]
DES was pretty much what they said it was (even down to that tweak in the S-boxes to block differential analysis, which the academic crypto researchers didn't discover for many years.) The NSA was/is really very good at what they did, and -- particularly in the US computer industry (which until 1960 had been pretty much guided by NSA R&D contracts) -- their cryptanalytic expertise was wholly unchallenged.
If you read the ostensible charter of the NSA, its duties include assisting in the securing of US civilian communications. While I expect this mainly means making sure that Boris & Natasha aren't tapping US internal comm links without permission, it can also be interpreted to make sure we aren't using snakeoil ciphers. Making DES not suck seems well within the NSA charter. In 1986, when the second recertification came up, I remember considerable consternation over the key-length reduction to 56 bits, and the unexplained tweaking of the S-boxes. There was serious discussion at the time that one or both of these changes were done to introduce backdoors. You'd probably have to find a usenet archive from the period to confirm this. I seem to recall reading somewhere that the extra (8?) bits in the original were shown not to add to the security of the cipher. Clearly 56 was too short - Diffie & Hellman published a paper to that effect in 1977. In the end, we now know that the tweaking prevented differential cryptanalysis, but not linear cryptanalysis. DCA had apparently been discovered internally at IBM (and presumably at NSA). LCA was not then known within IBM (whether it was known inside NSA is an interesting question :-) I would not be suprised if 30 or 50 years down the road, we find out that NSA did its level best to ensure that the AES selection process picked the best candidate. Equally, I would not be suprised to find that they already have some black cryptanalytic technique which can defeat it. On the balance I favor the former: the NSA is as aware as the rest of us of the huge cost (both financial and security) of embedding a broken cipher in the infrastructure of the nation. Peter Trei
On Tue, 10 Oct 2000, Trei, Peter wrote:
If you read the ostensible charter of the NSA, its duties include assisting in the securing of US civilian communications. While I expect this mainly means making sure that Boris & Natasha aren't tapping US internal comm links without permission, it can also be interpreted to make sure we aren't using snakeoil ciphers. Making DES not suck seems well within the NSA charter.
True enough. I have little trust for them though; they have been very irritating to american companies who want to make stuff with strong ciphers, at least for export.
In 1986, when the second recertification came up, I remember considerable consternation over the key-length reduction to 56 bits, and the unexplained tweaking of the S-boxes. There was serious discussion at the time that one or both of these changes were done to introduce backdoors. You'd probably have to find a usenet archive from the period to confirm this.
No, I wouldn't. I remember it too, and in fact I was one of the conspiracy theorists at that time. As time went on, though, and nobody *outside* the NSA worked out the supposed backdoor, I became more and more convinced that the inadequate key length was really the only problem. Switch to independently keyed 3DES, preferably with a half-block shift between encryptions for more diffusion, and that problem goes away.
In the end, we now know that the tweaking prevented differential cryptanalysis, but not linear cryptanalysis. DCA had apparently been discovered internally at IBM (and presumably at NSA). LCA was not then known within IBM (whether it was known inside NSA is an interesting question :-)
Hardly matters. The NSA couldn't realistically have expected to exploit linear cryptanalysis on the DES, because it requires them to capture something like (IIRC) 2^48 unique plaintext/ciphertext pairs. While that could happen on a high-speed link if they monitored it (and the target didn't change keys) for a long time, it doesn't seem too likely for the relatively small bandwidths employed by terrorist, rebel, and other "fringe" organizations. If that's a backdoor, it's a backdoor that takes a bulldozer to open. I'm thinking now that they just didn't know about it.
I would not be suprised if 30 or 50 years down the road, we find out that NSA did its level best to ensure that the AES selection process picked the best candidate. Equally, I would not be suprised to find that they already have some black cryptanalytic technique which can defeat it.
The NSA was very badly burned in public opinion and by conspiracy theorists for their involvement with the DES selection; having learned their lesson, I note that they have definitely taken a much more hands-off role with AES. Of course, this is also consistent with civilian cryptographic know-how having gotten sufficiently better that they no longer have to tell us what a secure cipher is.
On the balance I favor the former: the NSA is as aware as the rest of us of the huge cost (both financial and security) of embedding a broken cipher in the infrastructure of the nation.
Hm. Our opinions differ. The NSA has a stated agenda to embed broken ciphers in the infrastructure of the world, in order to preserve their sources of sigint. In the past, they have been perfectly willing to embed broken ciphers in the infrastructure of the United states (especially US-produced software) in order to further this agenda. I don't think I'm a full-out NSA-conspiracy theorist any more, but judging strictly from their record, that is evidently where they are coming from. They have been acting according to the idea that the sigint from broken ciphers furthers US interests more effectively than having strong ciphers in place. In the light of Echelon and the Crypto AG fiasco, they may even be right about that. But I don't think it's reasonable for the entire world to suffer the pain that broken ciphers in the infrastructure costs, for a transitory advantage to one nation. The best thing the US could do, for its allies, for the world at large, and for global trust right now would be to just plain quit trying to put broken ciphers into the infrastructure of this planet. This is a direct attack on infrastructure, and ought to be treated in world courts just as seriously as mining shipping lanes or poisoning water supplies. I hope somebody has realized this. It would be nice to think that the AES process represents a step in that direction. Bear
participants (2)
-
Ray Dillinger -
Trei, Peter