Why Constant-Time Crypto? • Hacker News Board

Re: Why Constant-Time Crypto?

#21

Post by nickpsecurity » Wed, Oct 11, 2017, 5:11 PM UTC

pjc50 wrote: post #20

jkabrg wrote: post #14

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 t…

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 rath…

"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

Re: Why Constant-Time Crypto?

#22

Post by brohee » Wed, Oct 11, 2017, 5:34 PM UTC

wbond wrote: post #10

From having spent a bunch of time working on wrapping crypto libraries for Python, the author’s name (Thomas Pornin) is one that I regularly saw providing in-depth answers on the Cryptography stack exchange: https://crypto.stackexchange.com/users/28/thomas-pornin . It is encouraging to see BearSSL at beta stage. I believe the last time I saw it, Thomas still considered it to be alpha. The promise of a small, MIT-lice…

libtomcrypt was started by Tom St Denis as he was learning programming, at the age of 15 years old or so. The exact history could be extracted by reading the Usenet sci.crypt group archives. In its early days suffered the horrible security woes that you can expect with these premises (e.g. https://groups.google.com/d/msg/sci.crypt/j3EW_pt6pKA/u8PYkf...). To his credit, Tom St Denis was always very honest and prompt to fix the issues. Pretty recently, it still had very bad issues (e.g. https://github.com/libtom/libtomcrypt/issues/74)

I got no idea what to expect now, but I've never seen it used in anything I'd consider serious. To many people, it's forever tainted. The lack of CVE in libtomcrypt is not an indication of quality, just and indication of lack of usage. In any case, its lack of support for PKCS#11 means it's not suitable for use cases where keys must be securely stored.

Re: Why Constant-Time Crypto?

#23

Post by fuklief » Wed, Oct 11, 2017, 5:58 PM UTC

pjc50 wrote: post #20

jkabrg wrote: post #14

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 t…

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 rath…

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

Re: Why Constant-Time Crypto?

#24

Post by ecesena » Wed, Oct 11, 2017, 6:22 PM UTC

kierenj wrote: post #2

Silly question here: why not get a reasonable worst-case time measure one-off, then yield the thread until total time elapsed for said crypto op is up?

I think the goal is not necessarily constant time, but more like do the same things independently from the bits of the secrets (symmetric keys, private keys, etc.). As a result, you get constant time.

But you get much more, because if one analyzes physical conditions (cpu/memory usage, temperature, time itself), he can't gather information about the secrets.