One-Time Programs

https://blog.cryptographyengineering.com/2022/10/27/one-time-programs/

by feross • 4 years ago

57 13 4 years ago

blog.cryptographyengineering.com

mattdesl2• 4 years ago

I don’t have much to add except to say this was enlightening and great to read.

My first thought is whether this could be used with ZKP at some point: one pitfall of ZKP is that you can copy a proof to other people and they could potentially reuse it to pretend to have the same knowledge/attestation. You can use a nonce/nullifier to force each proof to be newly signed, but even then the prover could just keep generating new proofs and send them out. Some kind of one-time ZKP generating program would be pretty interesting.

_0ffh• 4 years ago

I thought that at least some ZKPs rely on responses to one or a set of specific challenge(s) randomly chosen by the interrogator. So, as long as the challenge space is big enough, it seems unlikely that you can easily collect enough responses to satisfy such a random (set of) challenge(s) with any significant probability.

Please correct me, if I got that wrong.

mattdesl2• 4 years ago

I was imagining this for protocols like zkSNARK and similar, which do not have interactive challenges.

cowtools• 4 years ago

The solution is to use a locked-down co-processor? Whoop-de-doo. This is just a shameful re-marketing of "remote attestation"

zimpenfish• 4 years ago

The solution is to use a locked-down co-processor?

I think that was "the solution -with the hardware we have right now, that is readily available in people's hands and that we can actually do something with-".

He seemed to be pretty clear (to me, at least) that the OTM USB dongles were a much better solution but no-one makes them which kinda hampers the whole scheme.

alkonaut• 4 years ago

like one of those old copy-protection dongles from the 1990s

Ok now I feel like the software I’m making for a living isn’t very modern since it’s using copy protection dongles…

nonrandomstring• 4 years ago

A brilliant read from a computer science POV. An interesting theoretical problem indeed. But ultimately it feels like a rainbow solution looking for a real problem with attendant potential evil side effects.

dingaling• 4 years ago

I followed how the One Time Memory 'device' can ensure that only one input string is ever emitted, but I didn't understand how that integrates with the One Time Program to prevent brute forcing.

Can't Bob just shim the OTPrg to a fake OTM generator and keep running reset attacks?

noam_k• 4 years ago

I recommend looking at Vitalik's post, which is linked to.

In a nutshell: the program itself is garbled (hence the term "garbled circuits") in such a way that it can be evaluated on garbled inputs. Say you have a function f(a, b). One way to encode this is as a lookup table. Now, instead of the table mapping from plain values (bits, in our case) to plain values, we set the inputs to be random labels. The output bit is used with the OTM to get the input label for the next function (logical gate).

The security here is that each bit can only be garbled _once_, meaning that Bob can't get the output for a different input.

I'm not sure what kind of fake OTM generator you want to set up. Bob can only get half of the data from the hardware, and that data corresponds to a single input evaluation (if at all).

nextaccountic• 4 years ago

If you spend a few minutes thinking about this problem, it should become obvious that we can’t build OTPs using (pure) software: at least not the kind of software that can run on any general-purpose computer.
The problem here stems from the “can only run once” requirement.

Couldn't this be done by a blockchain?

I mean, make a smart contract work like a GKR Token

sterlind• 4 years ago

What a charmingly brilliant hack! Shuffle the lockboxes for one bit, resulting in a 50% chance you correctly guess both values, then boost the security into being infeasible to attack using secret sharing.

I've been wanting OTPs for a while for a project, this looks almost feasible.

xg15• 4 years ago

Honestly, I can't really feel exceited about this. It's a fun bit of cryptography, but in the end, it would be yet another tool to lock down devices even more - if it worked. However, my impression is that it wouldn't work really well in practice anyway, even if the "delivery problem" for OTMs were solved.

My understanding of the whole thing is as follows:

The "program" in "one time programs" is a function f(x) -> y that takes a bitstring of some fixed size as input and outputs a value y. (So really f(x1, x2, ..., xn) -> y). The function is also pure, meaning if you input the same bitstring, you'll always get the same output.

The task at hand is as follows: There is an untrusted second party "Bob". You want Bob to pick one particular bitstring, calculate the function on it and retrieve the value. But Bob must not be able to pick a second, different bitstring after it and calculate f() on that one too. (So "can run the program only once" really means "can only run the program on one particular input" - but because the function is pure, that's essentially the same)

This implies that Bob must not know in detail what f() actually calculates, otherwise he could just reimplement the function and run as many inputs on their version as he likes - yet he is the one who is supposed to do all the calculations. How can this work? Answer: You don't hand Bob the f() itself, but a "garbled" version of it, fg().

I have no idea how this garbling works, but apparently it leads to the following things:

- For each bit that f() takes, fg() takes a 128-bit key. So if f() has 10 inputs, fg() will have 1280 inputs.

- For each input position and each value, there is a secret key ("label"). I.e. there is one key for x1=0, another key for x1=1, a third one for x2=1, etc etc.

- If you input the appropriate labels for your bitstring, fg() will output the same result as f(). If you input anything else, fg() will output a random nonsense value (I think - the article doesn't go into detail here)

- The "garbling" operation somehow magically makes it so that you can neither reconstruct f() nor any of the labels from just fg() - or at least not by statically analysing fg().

So before Bob can input his bitstring, he has to convert it to the appropriate set of labels. Bob would like to have a conversation table with all the labels on it, but of course you don't give them that. Instead, you hand Bob a bunch of One Time Memory devices. There is one device for each input position (so one for x1, one for x2, ...). Each device can be queried once for either 1 or 0. It will return the appropriate label and then self-destruct. So if Bob gets to know the label for x1=0, the device ensures he'll never get to know the label for x1=1.

So if Bob has a bitstring "11001" and he wants to know f("11001"), he can call $labels := ask_otms("11001") to get the labels, then fg($labels) to get the value. But after that call, ask_otms() will be broken and he cannot obtain the labels for any other input.

----

That's all well and good, but in the end, Bob still knows fg() - and can run all kinds of experiments in the hope to get f() back, or at least learn the missing labels. In particular, as soon as he has a way to distinguish "garbage" results from fg() from "non-garbage" results, he can try to brute-force the labels. So the only way to prevent bruteforcing seems to me is to ensure that Bob can never know if an output from fg() is garbage or not garbage. And that's a constraint that is very easily broken if you use the function in the wrong context.

For example, suppose I want to use an OTP for signing: I want to "borrow" my private key to Bob, so he can sign one piece of data with it, but only one. I prepare my function fg() so that it produces a valid signature if the correct labels are input and a random value otherwise. fg() contains my private key, but that's ok as the key is garbled and unretrievable. I also hand Bob a bunch of OTMs which contain the labels. Bob can call fg(ask_otms(data)) to obtain the signature.

However, suppose my public key is widely available, as is usually the case for public keys. Then Bob can do the following:

- Take the result from ask_otms(data). Say for Bob's data, the value for x1 is 0, so he knows the label for x1=0 but not for x1=1.

- Change the label for x1 to some new value and apply the new set of labels to fg().

- Verify the result from fg() using my public key to see if it's a valid signature.

- If it is, Bob just found the label for x1=1.

- If it isn't, Bob has to try out more keys.

In the worst case, Bob has to brute-force 2^128-1 keys for each input. That's a lot, but it's also an "embarrasingly parallel" task: Bob can can try out each key in isolation as well as brute-force each input in parallel.

Also, the OP contains this note about the "garbling" operation:

(And it gets worse: if Bob obtains two labels on the same input wire, the entire garbled circuit construction will often unravel like a cheap sweater.)

This suggests that it might be enough to brute-force one additional label, then Bob can simply reconstruct f() and obtain my private key!

This means that suddenly, both my keys are sensitive: The whole scheme only stays secure if I keep my private key and my public key under wraps!

Another scenario: This time, I keep both my keys secret, but I want to allow Bob to sign up to two pieces of data independenly. So I build a function f() which contains my private key, then produce two garbled functions from it, fg() and fh(), each with its own set of labels. I send fg() and fh() to Bob and ship them two sets of OTMs with the labels.

However, Bob knows:

- If he supplies invalid labels to fg() and fh(), the functions will very likely produce different results.

- If he supplies valid labels that correspond to the same bitstring, the functions must produce identical results (as they both must produce the same result as f() would for that bitstring).

So Bob can do the following:

- run fg(ask_otms_for_g("00000...")); store the result as $yg.

- run fh(ask_otms_for_h("10000...")), i.e. use a bitstring which only differs in one bit from the one for fg().

- run fh() again and brute-force all possible labels for x1.

- if for some value, fh() produces the same result as $yg, the value is a strong candidate for being the correct label for x1=0 on fh().

Once Bob has both the labels for x1=1 and x1=0 on fh(), he can try to "unravel" fh() and get back f().

So I think even if the problem how to deliver OTMs was solved, there is still an enormous amount of ways how you could shoot yourself in the food by using OTPs.

cryptonector• 4 years ago

Solving the hardware problems around this makes all sorts of things possible, not just one-time programs. What's needed? Some sort of secure element, and something like an HSM or, probably better, a TPM (2.0).

Why is a TPM better? Because it has a very powerful authorization system that can be used to implement things like one-time operations among many other things.

AWS Nitro has a clever secure element scheme -- something that can work for clouds, which might be good enough. Their NitroTPMs do not come with Endorsement Key (EK) certificates (EKcert), and there's no AWS VM<->EKpub lookup service either (unlike in Google's cloud, where there are no EKcerts but they provide an equivalent EKpub lookup service). So using NitroTPM right now is hard: how do you decide to trust the enclave in which the one-time program is to run?

Being able to run secure enclaves on user devices would be great for some things, but, of course, the user loses a lot of control. Being able to run on a cloud enclave that is accessed by the user might be good enough in some cases, but now you need a strong binding of user to cloud enclave so that you can ensure that the program runs only once. On the plus side to running in a cloud enclave: there's less hardware to create if you trust the cloud operator.

One-Time Programs

Related Stories