Boffins rekindle one-time program cryptographic concept

Authentication idea advanced but not yet fulfilled

ANALYSIS Advances in technology over the last decade have enabled academics to make progress in creating so-called one-time programs.

One-time programs (OTPs) – originally presented at the Crypto ‘08 conference – describe a type of cryptographically obfuscated computer program that can be run only once, a special property that makes them useful for several applications and use cases.

OTPs were first proposed by researchers Goldwasser, Kalai, and Rothblum.

The general idea is that ‘Alice’ can send ‘Bob’ a computer program that is encrypted in such a way that:

1. Bob can run the program on any computer with any valid inputs and obtain a correct result. Bob cannot rerun the program with different inputs.
2. Bob can learn nothing 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 more than a decade.

OTP revived

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.

Garbled circuits

The researchers’ work 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’ is due to be presented at the upcoming Theory of Cryptography conference (TCC 2022).

The clearest application for OTPs is preventing brute-force attacks, says one researcher

Hardware-route discounted

One alternative means of constructing one-time programs, 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.

RELATED Post-quantum cryptography hits standardization milestone

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 [pdf] 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.

A bastion against brute-force attacks

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

“The clearest application of a one-time program (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.

‘Autonomous’ ransomware risk

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.”

Read more of the latest encryption security news

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,” Eldridge told The Daily Swig. “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,” Prof. Woodward told The Daily Swig.

“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.”

RECOMMENDED Matrix address flaws that break message encryption assurances