4 ms·

I had another idea for making constant time programs. The idea is that you create a virtual machine without loops or branch instructions, in which each instruct

by jkabrg 9y ago

I had another idea for making constant time programs. The idea is that you create a virtual machine without loops or branch instructions, in which each instruction is tested so that the amount of time it takes is independent of the instruction's input or output. You then compile your C code to this instruction set, and execute it on the VM. A program running on this VM, no matter how it's produced, will execute for the same amount of time. Why not do this for crypto?

voidmain 9y ago
Because as explained in the article, elementary things like memory access a[i] are not constant time with respect to i? Because an arbitrary C program will have non-constant branches (so may become exponentially long in your proposed instruction set) and loops (not representable at all in your proposed instruction set)? If what you are saying is that a language could hypothetically statically verify that the execution of a function was constant time with respect to certain inputs, that sounds like it would work and that the only obstacle is engineering effort. But compiling to such a language doesn't sound very practical to me.
- Verdex_3 9y ago
  I think someone wrote an applicative functor instance in haskell that would accomplish something like this. I forget if it was constant space or time or what (I can't find the link unfortunately). All I remember at the time was thinking I had no idea why anyone would want this. But then someone (on either hn or proggit) mentioned that there were crypto reasons why it would be useful. So I suspect that compiling isn't too bad ... however, programming with it probably is annoying. EDIT: Actually, it looks like it was top comment in this thread: https://news.ycombinator.com/item?id=7557089 https://news.ycombinator.com/item?id=7557089 Kind of a neat idea at any rate.
pjc50 9y ago
I'd do it the other way round. A VM is a bit of a pain and you can't target a constant-time-only VM with a regular C compiler. Instead I'd produce a restricted C compiler that only accepted constant time programs, and mapped directly to a limited set of machine instructions. Regardless of what you do, you'd have to produce a whilelist of constant-time machine instructions, so you might as well emit them directly rather than relying on a general purpose optimising compiler to do the right thing. You can then emit an object file containing the functions you're interested in and link it to the rest of your non-constant-time program.
- nickpsecurity 9y ago
  "Instead I'd produce a restricted C compiler that only accepted constant time programs, and mapped directly to a limited set of machine instructions." This has more potential just because it could be licensed in embedded sector to reduce work on things such as WCET analysis for hard-real-time. That money and uptake can feed back into the compiler's development for things such as constant-time-preserving optimizations. I haven't seen one of these, though. They typically do timing analysis manually (i.e. specific tool) since they have to assess the algorithms themselves, interactions with other components, and so on. Neatest thing I found looking into that was a formally-verified WCET analyses that was built on top of CompCert compiler. Oh wait, just found something: https://cseweb.ucsd.edu/~dstefan/pubs/cauligi:2017:fact.pdf https://cseweb.ucsd.edu/~dstefan/pubs/cauligi:2017:fact.pdf
- fuklief 9y ago
  "Instead I'd produce a restricted C compiler that only accepted constant time programs, and mapped directly to a limited set of machine instructions." How would the compiler knows if the code it's given is constant-time ? It's actually a property quite hard to verify due to pointer aliasing or whatnot. Another angle is to have a compiler that always outputs constant-time code. It's always possible, at least for crypto code according to Peter Schwabe, just that it's probably not going to be very fast code...

by jkabrg 9y ago

voidmain 9y ago

Because as explained in the article, elementary things like memory access a[i] are not constant time with respect to i? Because an arbitrary C program will have non-constant branches (so may become exponentially long in your proposed instruction set) and loops (not representable at all in your proposed instruction set)? If what you are saying is that a language could hypothetically statically verify that the execution of a function was constant time with respect to certain inputs, that sounds like it would work and that the only obstacle is engineering effort. But compiling to such a language doesn't sound very practical to me.

Verdex_3 9y ago
I think someone wrote an applicative functor instance in haskell that would accomplish something like this. I forget if it was constant space or time or what (I can't find the link unfortunately). All I remember at the time was thinking I had no idea why anyone would want this. But then someone (on either hn or proggit) mentioned that there were crypto reasons why it would be useful. So I suspect that compiling isn't too bad ... however, programming with it probably is annoying. EDIT: Actually, it looks like it was top comment in this thread: https://news.ycombinator.com/item?id=7557089 https://news.ycombinator.com/item?id=7557089 Kind of a neat idea at any rate.

pjc50 9y ago

I'd do it the other way round. A VM is a bit of a pain and you can't target a constant-time-only VM with a regular C compiler. Instead I'd produce a restricted C compiler that only accepted constant time programs, and mapped directly to a limited set of machine instructions. Regardless of what you do, you'd have to produce a whilelist of constant-time machine instructions, so you might as well emit them directly rather than relying on a general purpose optimising compiler to do the right thing. You can then emit an object file containing the functions you're interested in and link it to the rest of your non-constant-time program.

nickpsecurity 9y ago
"Instead I'd produce a restricted C compiler that only accepted constant time programs, and mapped directly to a limited set of machine instructions." This has more potential just because it could be licensed in embedded sector to reduce work on things such as WCET analysis for hard-real-time. That money and uptake can feed back into the compiler's development for things such as constant-time-preserving optimizations. I haven't seen one of these, though. They typically do timing analysis manually (i.e. specific tool) since they have to assess the algorithms themselves, interactions with other components, and so on. Neatest thing I found looking into that was a formally-verified WCET analyses that was built on top of CompCert compiler. Oh wait, just found something: https://cseweb.ucsd.edu/~dstefan/pubs/cauligi:2017:fact.pdf https://cseweb.ucsd.edu/~dstefan/pubs/cauligi:2017:fact.pdf
fuklief 9y ago
"Instead I'd produce a restricted C compiler that only accepted constant time programs, and mapped directly to a limited set of machine instructions." How would the compiler knows if the code it's given is constant-time ? It's actually a property quite hard to verify due to pointer aliasing or whatnot. Another angle is to have a compiler that always outputs constant-time code. It's always possible, at least for crypto code according to Peter Schwabe, just that it's probably not going to be very fast code...