Five secret phrases used to create the encryption algorithms that secure everything from online banking to email have been lost to history – but now cryptographers are offering a bounty to rediscover them.
Could you solve a cryptography mystery?
Secret phrases that lie at the heart of modern data encryption standards were accidentally forgotten decades ago – but now cryptographers are offering a cash bounty for anyone who can figure them out. While this won’t allow anyone to break these encryption methods, it could solve a long-standing puzzle in the history of cryptography.
“This thing is used everywhere, and it’s an interesting question; what’s the full story? Where did they come from?” says cryptographer Filippo Valsorda. “Let’s help the trust in this important tool of cryptography, and let’s fill out this page of history that got torn off.”
The tool in question is a set of widely-used encryption algorithms that rely on mathematical objects called elliptic curves. In theory, any of an infinite number of curves can be used in the algorithms, but in the late 1990s the US National Security Agency (NSA), which is devoted to protecting domestic communications and cracking foreign transmissions, chose five specific curves it recommended for use. These were then included in official US encryption standards laid down in 2000, which are still used worldwide today.
Exactly why the NSA chose these particular curves is unclear, with the agency saying only that they were chosen at random. This led some people to believe that the NSA had secretly selected curves that were weak in some way, allowing the agency to crack them. Although there is no evidence that the elliptic curves in use today have been cracked, the story persists.
In the intervening years, it has been confirmed that the curves were chosen by an NSA cryptographer named Jerry Solinas, who died earlier this year. Anonymous sources have suggested that Solinas chose the curves by transforming English phrases into a string of numbers, or hashes, that served as a parameter in the curves.
It is thought the phrases were along the lines of “Jerry deserves a raise”. But rumours suggest Solinas’s computer was replaced shortly after making the choice, and keeping no record of them, he couldn’t figure out the specific phrases that produced the hashes used in the curves. Turning a phrase into a hash is a one-way process, meaning that recovering them was impossible with the computing power available at the time.
Dustin Moody at the US National Institute of Standards and Technology, which sets US encryption standards, confirmed the stories to New Scientist: “I asked Jerry Solinas once, and he said he didn’t remember what they were. Jerry did seem to wish he remembered, as he could tell it would be useful for people to know exactly how the generation had gone. I think that when they were created, nobody [thought] that the provenance was a big deal.”
Now, Valsorda and other backers have offered a $12,288 bounty for cracking these five hashes – which will be tripled if the recipient chooses to donate it to charity. Half of the sum will go to the person who finds the first seed phrase, and the other half to whoever can find the remaining four.
Valsorda says that finding the hashes won’t weaken elliptic curve cryptography – because it is the nature of the curves that protects data, not the mathematical description of those curves – but that doing so will “help fill in a page of cryptographic history”. He believes that nobody in the 1990s considered that the phrases would be of interest in the future, and that the NSA couldn’t have released them anyway once they discovered that they were jokey phrases about one of their staff wanting a raise.
There are two main ways someone could claim the prize. The first is brute force – simply trying vast numbers of possible seeds, and checking the values created by hashing them against the known curves, which is more feasible than in the 1990s because of advances in computing power.
But Valsorda says someone may already have the phrases written down. “Some of the people who did this work, or were in the same office as the people who did this work, probably are still around and remember some details,” he says. “The people who are involved in history sometimes don’t realise the importance of what they remember. But I’m not actually suggesting anybody, like, goes stalking NSA analysts.”
Keith Martin at Royal Holloway, University of London, says that the NSA itself would be best-equipped to crack the problem, but probably has other priorities, and anybody else will struggle to find the resources.
“I would be surprised if they’re successful,” he says. “But on the other hand, I can’t say for sure what hardware is out there and what hardware will be devoted to this problem. If someone does find the [phrases], what would be really interesting is how did they do it, rather than that they’ve done it.”
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Matthew Sparkes*