The change the NSA made was to replace the s-boxes used with ones that made using differential crypto analysis slightly less efficient than brute force. As it happens, the s-boxes provided by the NSA were also among the worst 9%-16% possible with respect to linear crypto analysis. "A software implementation of this attack recovered a DES key in 50 days using 12 HP9000/735 workstations" [1]. I do not know the specs of said workstations, but for reference the book claims that was the fastest attack at the time of writing (1996).
This is not to say that the NSA was aware of linear crypto analysis when they made their recomendation. Indeed the fact that their s-boxes also happened to be just good enough to beet differential, and the fact that an independent government investigation (the details of which are classified) cleared them of wrongdoing, are enough to convince that they did not intend to introduce a hole. Furthermore, the NSA has also now published the requirements they used to generate their s-boxes. Schneier suggests in his book that the s-boxes were weakened unintentionally by the act of introducing structure to them, without knowing to defend against linear analysis.
Correct. The NSA suggested changes in the DES S-boxes, which led to many questions. Ultimately, what was discovered is that their changes strengthened DES, not weakened it, as some had feared.
This is not to say that the NSA was aware of linear crypto analysis when they made their recomendation. Indeed the fact that their s-boxes also happened to be just good enough to beet differential, and the fact that an independent government investigation (the details of which are classified) cleared them of wrongdoing, are enough to convince that they did not intend to introduce a hole. Furthermore, the NSA has also now published the requirements they used to generate their s-boxes. Schneier suggests in his book that the s-boxes were weakened unintentionally by the act of introducing structure to them, without knowing to defend against linear analysis.
[1] Bruce Schneier, Applied Cryptography