A Programmer Solved a 20-Year-Old Forgotten Crypto Puzzle

In early April, 1999, a time capsule was delivered to the famed architect Frank Gehry with instructions to incorporate it into his designs for the building that would eventually host MIT’s Computer Science and Artificial Intelligence Lab, or CSAIL. The time capsule was essentially a museum of early computer history, containing 50 items contributed by the likes of Bill Gates and Tim Berners-Lee.

The time capsule wasn’t meant to be opened for another 35 years—unless someone could crack the cryptographic puzzle that was included in its design. The puzzle was designed by Ron Rivest, whose name lends the “R” to RSA, arguably one of the most important cryptographic protocols ever created. He says it wasn’t designed to be complicated. Instead, Rivest created the puzzle so that it should take almost exactly 35 years to compute the answer.

On April 15, almost 20 years to the day after Rivest announced the puzzle, Bernard Fabrot, a self-taught Belgian programmer, solved it. The puzzle’s original instructions dictated that the solution be sent to the director of the Laboratory for Computer Science, but Fabrot says he was surprised to learn that the lab no longer existed (it was merged with MIT’s AI lab in 2003 to create CSAIL.) In fact, Fabrot says CSAIL director Daniela Rus wasn’t even aware of the puzzle’s existence when he told her he had the solution.

Rivest’s puzzle basically involved finding the number that results from running a squaring operation nearly 80 trillion times. For example, if you start with squaring two you’d get four, then square four to get 16, and then repeat this process 80 trillion more times. You then take the number you arrive at and run a mathematical operation that uses that number and a number given in the instructions to the puzzle. Doing so spits out a new number that can be translated into a short congratulatory phrase. (Rivest and Fabrot declined to reveal the exact phrase, which will be announced at the opening of the time capsule on May 15.)

 

The key to this puzzle is that it requires sequential operations, which means you can’t get to the answer faster by using parallel computing. You need to go through the squaring process one step at a time, building on the previous answers, to arrive at the solution, so using more computers or throwing a supercomputer at the problem won’t help. Based on Moore’s law and how long it took to run the squaring operation in 1999, Rivest estimated that computing the answer to the puzzle should take approximately 35 years.

 

Fabrot, who works as an independent developer, says he stumbled upon the puzzle by accident in 2015. Although Rivest initially released the puzzle’s code in Java, Fabrot realized it could be solved faster if he used the GNU Multiple Precision Arithmetic Library, free software written in C for doing “precise arithmetic.” So Fabrot dedicated one of the CPU cores on his home desktop computer to running squaring operations in an attempt to solve the puzzle. He says his computer was running the operation 24/7, except when he would have to leave on vacation or there was a power outage.

“During all these years I told no one I was trying to solve the puzzle except very close friends,” Fabrot says. “I knew I had a chance but if I told anyone they could have used a more powerful CPU to overtake me.”

 

Three-and-a-half years later, Fabrot finally completed approximately 80 trillion squaring operations and had derived the solution to the puzzle. It couldn’t have been better timing. 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 only be derived 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 multi-purpose chip that is programmed to only run a specific algorithm, which makes it more efficient than a general purpose CPU. Using Ozturk’s algorithm, this FPGA was about ten 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.

 

 

Read more: https://www.wired.com/story/a-programmer-solved-a-20-year-old-forgotten-crypto-puzzle/

Leave a Reply

Your email address will not be published.