In praise of the Feistel network – MIT Technology Review

Given that context, the NBSs choice was perplexing. On the one hand, DES did deliver on its promise: after decades of analysis, there is still essentially no way to decrypt DES-encrypted data other than potentially trying every key, in whats called an exhaustive search. But on the other hand, one would expect that the 56-bit key would be nowhere near as strong as the 128-bit Lucifer.

Mounting an exhaustive search against DES was at the edge of possibility in 1975. Martin Hellman, a professor of computer science at Stanford University, and Whitfield Diffie 65, a researcher in Hellmans lab, estimated that for $20 million the US government could build a machine capable of trying all possible keys; adding just eight more key bits would increase the difficulty by a factor of 256, making a key search practically impossible. It was as if the proposed standard had been carefully designed so that DES-encrypted messages could be cracked by the US government but not by US corporations.

Feistel was born in Germany in 1915 into a middle-class Protestant family. His aunt married a wealthy German Jew named Franz Meyer, and the two fled Germany for Zrich, Switzerland, before 1931.

When Hitler came to power in 1933, Feistel was terrified that compulsory military service would be reinstated (which it was). So his uncle devised a plan to have Feistel attend summer school at Columbia University in 1934 to improve his English, then enroll at the Eidgenssische Technische Hochschule (ETH) in Zrich for college, and finally transfer to a university in the US to complete his studies and obtain permanent residence. The plan worked, and Feistel entered MIT in the fall of 1936. Meyer and his wife followed, moving to New York City before 1940.

Feistel graduated from MIT in 1937 with a degree in physics and continued as a graduate student until 1938, when he enrolled at Harvard. He became a US citizen on January 31, 1944. The following day, he told me, he was given a top secret clearance, recalls Diffie. Yet Feistel felt that he experienced discrimination because of his German heritage. Although he had been interested in codes and cryptography since he was a child, he couldnt work on them. He said something to someone during the war and was told that it was not the time for a German to be talking about cryptography, Diffie recalls.

Finally, he got his chance. After working at the MIT Radiation Laboratory, Feistel got a job at the Air Force Cambridge Research Center (AFCRC), which had been asked to evaluate an Identification Friend or Foe (IFF) system that aircraft used to identify themselves to radar systems so as not to be shot down.

Feistels group found a flaw with the system and developed a better approach based on cryptography. Its not clear whether it was ever deployed: within a few years, the AFCRC cryptography group was shut down, likely because the Department of Defense was centralizing cryptographic research at the NSA. But modern IFF systems do employ cryptography and a key that is changed regularly.

In November 1957 Feistel took a job at MIT Lincoln Laboratory, where he wrote a report summarizing the IFF work done at AFCRC. Whatever the particular application may be, any scheme of secret communication should be carefully analyzed and evaluated for its merits and faults, he concluded. It is better to know where one stands, than being SPOOFED into a false sense of security, through lack of knowledge or perhaps even inventors pride.

Lincoln didnt work out for Feistel, though, and neither did MITRE, the Bedford-based research firm, where he went in 1961. My father wasnt very happy there, recalls his daughter, Peggy Chester: again, Feistel thought colleagues discriminated against him because he was German. Feistel took pride in his German heritage and in German engineering, says Harold Mattson, PhD 55, who worked with Feistel at AFCRC. He adds that Feistel was also somewhat bitter about the postwar world order, describing the United Nations as a Victors Club on more than one occasion.

It may have been during his years at MITRE that Feistel developed his encryption approach. But if so, he didnt share it. He was very cautious about revealing his Lucifer code, his daughter says. He was afraid that other people would take it from him. Its also possible that cryptography work he wanted to do at MITRE was being stifled by the NSA.

In 1968, Feistel moved to IBM, which hired him specifically to work on cryptography for commercial applications. Its here that he likely perfected his encryption algorithm. On June 30, 1971, the company filed a patent application for his Block Cipher Cryptographic System. NSA reviewed the application and issued a secrecy order blocking publication of the patentbut NSAs order, dated October 17, 1973, was five months after the Scientific American article. NSAs order was rescinded on November 14, 1973, and US Patent 3,798,359 was published on March 19, 1974, with H. Feistel listed as the inventor.

Horst was key to the IBM cryptographic research effort, says Hellman, who also taught at MIT from 1969 to 1972. In 1973, when Horst published that paper, it was an eye-opener for many of us. It opened an approach to cryptography that made a lot of sense. Today the approach is so identified with Feistel that the basic design of DES and other similar algorithms is called a Feistel network.

Meanwhile, Diffie and Hellman discovered public-key cryptography in 1976. One of its primary uses is to distribute encryption keys for algorithms like DES.

Work by Don Coppersmith 72 published in the IBM Journal of Research and Development in 1994, four years after Feistels death, revealed that IBM knew by 1975 that the 128-bit Lucifer key would have been vulnerable to differential cryptanalysis, a cryptanalytic attack independently discovered by academics in the late 1980s. In the process of strengthening Lucifer, IBM shortened the key. In other words, when DES was approved for use in the 1970s, it might have been stronger than Lucifer after all.

But by the mid-1990s, computer scientists widely acknowledged that the 56-bit key was no longer secure and argued that DES should no longer be used to protect information.

To demonstrate that US policy was putting privacy at risk, in 1998 the Electronic Frontier Foundation constructed a machine called Deep Crack that cracked a DES-encrypted message in just 56 hours. The machine cost $250,000 to build, but most of that was engineering costs: EFF estimated that the second machine would cost less than $50,000.

Our research results prove that DES can be cracked quickly on a low budget, the EFF book Cracking DES concludes.

DES was replaced by a new algorithm called the Advanced Encryption Standard on May 26, 2002. As near as anyone knows, AES is still secure.

Read this article:
In praise of the Feistel network - MIT Technology Review