One Time Programs could create autonomous ransomware with no call home

In the wonderful world of cyber security One Time Programs (OTPs), originally presented at the Crypto ‘08 conference, are somewhat of a holy grail. They describe a type of cryptographically obfuscated computer program, or algorithm, that can be run only once, a unique special property that makes them perfect for several applications and use cases.

OTPs were first proposed by researchers Goldwasser, Kalai, and Rothblum at Microsoft and while progress in commercialising them is slow behind the scenes there’s progress. Contextualising them for you the general idea is that ‘Alice’ can send ‘Bob’ a computer program that is encrypted in such a way that Bob can run the program on any computer with any valid inputs and obtain a correct result, but that Bob cannot rerun the program with different inputs and he can’t learn anything about the secret program by running it.

The run-only-once requirement runs into trouble because it would be trivial to install a run-once-only program on multiple virtual machines, trying each one with different inputs. This would violate the whole premise of the technology.

The original idea for thwarting this fairly obvious hack was to only allow the secret program to run if accompanied by a physical token that somehow enforced the one-time rule for running the copy of the secret program that Alice had sent to Bob.

No such tokens were ever made, so the whole idea has lain dormant for the past few years. But now a team of computer scientists from Johns Hopkins University and NTT Research have laid the groundwork for how it might be possible to build one-time programs using a combination of the functionality found in the chips found in mobile phones and cloud-based services.

More specifically they have hacked ‘Counter Lockbox’ technology and applied its use to an unintended purpose. Counter lockboxes protect an encryption key under a user-specified password, enforcing a limited number of incorrect password guesses (typically 10) before the protected information is erased.

The hardware security module in iPhones or Android smartphones provides the needed base functionality, but it needs to be wrapped around technology that prevents Bob from attempting to cheat the system, the focus of the research.

The new research shows how multiple counter lockboxes might be chained together to form so-called ‘garbled circuits’, a construction that might be used to build one-time programs.

A paper describing this research, entitled ‘One-Time Programs from Commodity Hardware’ was presented at the Theory of Cryptography Conference.

One alternative means of constructing OTPs, considered by the paper, is using tamper-proof hardware. But tamper-proof hardware would require a “token with a very powerful and expensive, not to mention complex, general purpose CPU”, as explained in a blog post by cryptographer Matthew Green, a professor at Johns Hopkins University and one of the co-authors of the paper.

“This would be costly and worse, [and] would embed a large attack software and hardware attack surface, something we have learned a lot about recently thanks to Intel’s SGX, which keeps getting broken by researchers,” Green explains.

Rather than relying on hardware or the potential use of blockchain plus cryptographic tool-based technology, the Johns Hopkins’ researchers have built a form of memory device or token that spits out and erases secret keys when asked. It takes hundreds of lockboxes to make this construction, at least 256 for a 128-bit secret, a major drawback that the researchers are yet to overcome.

In practical terms, someone could realize this technology by creating multiple iCloud or Google accounts and then using Apple’s iCloud Key Vault or Google’s Titan Backup service to store a ‘backup key’ for each of them. This is anything but elegant and the computer scientists at John Hopkins are inviting other researchers to progressing their research by coming up with neater schemes.

Harry Eldridge from Johns Hopkins University, who is lead author of the paper, told reporters that one-time programs could have multiple uses.

“The clearest application of an OTP is preventing brute-force attacks against passwords,” Eldridge explained. “For example, rather than send someone an encrypted file, you could send them an OTP that outputs the file if given the correct password. Then, the person on the other end can input their password to the OTP and retrieve the file.

“However, because of the one-time property of the OTP, a malicious actor only gets one chance to guess the password before being locked out forever, meaning that much weaker passwords such as a four-digit PIN can actually be pretty secure,” Eldridge added.

More generally this could be applied to other forms of authentication, for example if you wanted to protect a file using some sort of biometric match like a fingerprint or face scan.

One danger posed by the approach is that bad guys might use the technique to develop ‘autonomous’ ransomware.

“Typically, ransomware needs to ‘phone home’ somehow in order to fetch the decryption keys after the bounty has been paid, which adds an element of danger to the group perpetrating the attack,” according to Eldridge. “If they were able to use one-time programs however, they could include with the ransomware an OTP that outputs the decryption keys when given proof that an amount of bitcoin has been paid to a certain address, completely removing the need to phone home at all.”

The feedback on the work so far has been “generally positive”, according to Eldridge.

“[Most agree] with the motivation that OTPs are an interesting but mostly unrealized cryptographic idea, with the most common criticism being that the number of lockboxes required by our construction is still rather high,” said Eldridge. “There is possibly a way to more cleverly use lockboxes that would allow for fewer of them to be used.”

Professor Alan Woodward, a computer scientist at the University of Surrey, welcomed the research.

“It’s a nice paper and it doesn’t claim to be the ultimate answer: it gives a solution in the hope that others may find better ways of doing the same thing,” said Prof. Woodward. “If achievable it means one-time programs become viable, and that opens up an interesting array of applications where you want someone to be able to run your program but not to be able to undertake differential analysis to learn about how the program functions.”