NSA and Lucifer / DES
To be fair the NSA suggested changes to DES which -as I recall - included a shorter key. Years later it was discovered that their suggestions strengthened DES, so there is a precedent. Odd course, you could argue that they thought they were weakening DES, and what happened was unexpected.
Argh (and argh also to Pet Peeve, who posted a better but still agonizingly vague summary of the story).
Really, in the time it takes to write a post like this, you could, y'know, look it up. The whole thing is in Applied Cryptography and no doubt many online sources.
1973-1975: NBS, the precursor to NIST, sends out a call for a cipher to establish as a standard. IBM creates Lucifer, as part of its research into block ciphers. (Many notables in the crypto industry were involved: Feistel, Coppersmith, etc.) IBM submits Lucifer to NBS, agreeing to license it without charge.
1975: NBS asks NSA to evaluate the algorithm and suggest changes. NSA makes various changes, in particular shortening the key (effectively to 56 bits) and changing the S-boxes. This is the NSA acting in its official "help US business" role, as DAM said. And many people were suspicious, in their public responses to NBS - contradicting RSA's ridiculous claim "hey, we all used to trust the NSA without reservation" (I paraphrase).
1976-1977: NBS holds public workshops to evaluate the revised Lucifer. There is much debate, but NBS standardizes it as DES anyway.
Schneier notes: "Off the record, NSA has characterized DES as one of their biggest mistakes". Why? Because the standard described it as a hardware cryptosystem, but provided enough information to implement it in software. Apparently someone high up at NSA thought DES would only ever appear in hardware, which would be much easier to keep under export control.
In the '80s, various other groups (ANSI, some ISO working groups) adopted DES as a general standard, or as part of other standards. It became entrenched (later in 3DES form to fix the short key).
1977-1981: Various researchers show just how vulnerable DES's short key is. Specifically, they come up with informed estimates for DES brute-force cracking machines (between $5m and $50m) and estimate how long such a machine would take to crack a ciphertext (on the order of a few days; remember this is for circa 1980). There's widespread suspicion that NSA shortened the key so well-funded adversaries (i.e., the NSA) could decrypt communications they felt were particularly interesting.
There was also a lot of worry that DES was a group, possibly a pure or even closed group; that would make multiple-encryption pointless (3DES would be no stronger than DES), and if closed would cut the effective key length in half, to 28 bits (via a meet-in-the-middle attack). The associated concern was that the NSA knew DES was a group, and possibly had made it a group by mucking with the S-boxes. In 1992 this was publicly disproven (DES is not a group), and Coppersmith says IBM always knew it wasn't a group, but kept the details secret (because, hey, they're IBM).
What about those S-boxes? They're the non-linear part of DES, and the only real security. Each S-box is a substitution table with a 6-bit input and a 4-bit output. IBM submitted Lucifer with one set of S-boxes; the NSA sent it back with a different set. IBM couldn't find anything wrong with the NSA's set. Some found this worrying.
Did the NSA use subtly-weak S-boxes (i.e., ones with hidden algebraic structure) so they could break DES? Did they change the S-boxes because they were worried IBM might have put a similar backdoor in their original set? Did they know something that wasn't in the published literature?
In 1990, we got a strong indication that the answer to the last question was "yes", when Biham and Shamir published their work on differential cryptanalysis. DES is "vulnerable" to DC, in the sense that there are better-than-brute-force attacks against DES with DC. But the S-boxes in DES turn out to be optimized against DC. What a coincidence! Coppersmith has said that IBM and NSA knew about DC back when DES was created.
In 1993, Matsui published on linear cryptanalysis. It turns out the DES S-boxes are not optimized against LC. You can crack stock DES with around 243 known plaintexts using LC.
So: Did the NSA not know about LC in 1976? Did they know about it, and keep it as their own backdoor? Did they know about it, but also know about something worse that made it impossible to optimize the S-boxes against both DC and LC and mystery-analysis? Only their tobaccanist knows for sure.
tl;dr: The NSA both strengthened and weakened DES, almost certainly deliberately. Their involvement was always controversial.
Biting the hand that feeds IT
