In praise of the Feistel network
Cryptographer Horst Feistel ’37 spearheaded the work leading to encryption standards used during the 20th century.
On March 17, 1975, the National Bureau of Standards (NBS) published its proposed Data Encryption Standard (DES) in the Federal Register. The algorithm used a 56-bit encryption key, which (it was hoped) meant there was no possible way for an attacker to decrypt the resulting ciphertext without setting out to try each of the 72,057,594,037,927,936 possible keys one by one.
DES was based on a revolutionary new approach to encryption developed at IBM by Horst Feistel ’37 and published in the May 1973 Scientific American. But while the 1973 article provided merely a broad outline of his approach, the DES publication contained step-by-step instructions for building a strong encryption system that businesses and individuals could use.
The advent of shared computing in the early 1970s made it clear that government agencies, banks, and other organizations needed to protect their data, but most of the good information about encryption was locked up inside the National Security Agency. Though a variety of proprietary systems were on the market, few people outside the NSA knew what made a strong encryption algorithm and what was junk.
What the government needed was a single, strong standard that would create trust and help the growing information technology market thrive. So NBS solicited encryption algorithms from the public, and IBM ultimately submitted two of Feistel’s: first one with a 128-bit key he called Lucifer, and then, after some back-and-forth, what became DES.
Given that context, the NBS’s 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 what’s 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 Hellman’s 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 Zürich, 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 Eidgenössische Technische Hochschule (ETH) in Zürich 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 couldn’t 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.
A career in cryptography
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.
Feistel’s group found a flaw with the system and developed a better approach based on cryptography. It’s 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 inventor’s pride.”
Lincoln didn’t work out for Feistel, though, and neither did MITRE, the Bedford-based research firm, where he went in 1961. “My father wasn’t 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 didn’t 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.” It’s 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. It’s 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 patent—but NSA’s order, dated October 17, 1973, was five months after the Scientific American article. NSA’s 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.
Putting DES to rest
Work by Don Coppersmith ’72 published in the IBM Journal of Research and Development in 1994, four years after Feistel’s 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.
Geoffrey Hinton tells us why he’s now scared of the tech he helped build
“I have suddenly switched my views on whether these things are going to be more intelligent than us.”
ChatGPT is going to change education, not destroy it
The narrative around cheating students doesn’t tell the whole story. Meet the teachers who think generative AI could actually make learning better.
Meet the people who use Notion to plan their whole lives
The workplace tool’s appeal extends far beyond organizing work projects. Many users find it’s just as useful for managing their free time.
Learning to code isn’t enough
Historically, learn-to-code efforts have provided opportunities for the few, but new efforts are aiming to be inclusive.
Get the latest updates from
MIT Technology Review
Discover special offers, top stories, upcoming events, and more.