Excerpt from: Wired Magazine
Although Fabrot didn’t know it, a group of computer scientists and cryptography experts were working on a project called Cryptophage, which was using specialized hardware meant specifically to solve the MIT puzzle.
Led by former Intel engineer Simon Peffers, the Cryptophage group was researching verifiable delay functions as a possible security mechanism for blockchains like Ethereum. Verifiable delay functions are a modern take on Rivest’s early work on time-delayed cryptography, and their solution can be derived only through sequential operations. In the course of their research, Peffers says, the Cryptophage group came across Rivest’s puzzle, which seemed like a good way to put their research to the test.
In mid-March, the group began to run an algorithm designed by Erdinc Ozturk, a researcher at Sabanci University, that was optimized to reduce the amount of delay between squaring operations. This algorithm was implemented on a field-programmable gate array, a multipurpose chip that is programmed to run only a specific algorithm, which makes it more efficient than a general-purpose CPU. Using Ozturk’s algorithm, this FPGA was about 10 times faster than a high-end commercial CPU running non-optimized software.
Based on the chip’s computing efficiency, the Cryptophage group calculated that they would have the correct solution to the MIT puzzle on the evening of May 10, just two months after they started the calculation. Yet when they reached out to MIT to let them know a solution was imminent, Rivest informed them that Fabrot had beaten them to the punch.
“We didn't have anyone come to us until these two came up to us on practically the same day to say 'we've solved your problem,'” Rivest says. “That's an astonishing coincidence.”
Rivest is quick to admit that he had overestimated the difficulty of his puzzle. Making predictions about improvements in technology is difficult on that long of a timescale, and Rivest says he didn’t anticipate breakthroughs like FPGA chips, which weren’t as sophisticated or widely available as they are today.
Although the Cryptophage group wasn’t the first to solve the puzzle, Peffers said they will still be at the ceremony to open the time capsule on May 15. Only the capsule’s designers know its full contents, though it does include contributions from Tim Berners-Lee, inventor of the World Wide Web; Bob Metcalfe, who invented ethernet; and Bill Gates, who contributed the original version of Altair BASIC, Microsoft’s first product. Fabrot said he is most excited to see an original copy of one of the earliest PC games, Zork, included in the capsule.”
For the full article see: https://www.wired.com/story/a-programmer-solved-a-20-year-old-forgotten-crypto-puzzle/