Hacker News Reader

Comment by tptacek | Hacker News Reader

In which Brian Smith proposes that instead of coding each of the specific curves a TLS library has to support in independent but closely coupled C libraries, we instead invent a DSL for expressing curve routines and a compiler to compile it down directly to C or assembly.

View on HN

I am working on something (toy) similar to this in my spare time using luaJIT.

I like the idea of using a simpler DSL to interact with ECC.

Quite nice, but how about the need for key functions to be constant-time to thwart time-based attacks? It's probably quite hard to express and requires low-level per-platform tweaking.

It's a lot easier to produce properties like constant-time execution by construction than to have to shoehorn things into them after the fact.

One project that tries to do something like this is Nadeko: https://www.reddit.com/r/rust/comments/3696wt/checking_that_...

The idea is that the DSL compiler would be responsible for ensuring constant-timeness. Note that C, C++, and Rust offer no guarantee of constant-timeness. Even processors don't offer constant-timeness guarantees and some instructions (often division) are not constant-time. See also http://blog.erratasec.com/2015/03/x86-is-high-level-language....

I wrote the paper mostly in the context of implementing signature verification, which doesn't require side-channel protection since there are no secrets in verification. But, I think the DSL approach is even more important for ECDH and signing, where side-channel protection is important.

Finally, given that processors don't even promise us that any instruction is constant-time, and given that other types of attacks are possible where constant-timesness doesn't help so much (e.g. power analysis), I think it is worth considering other approaches to side-channel protection (e.g. blinding). For many applications, constant-timeness isn't sufficient and I'd love to learn that it isn't necessary.

Sounds like a good topic for a Ph.D. thesis to me.

Or could just use a good language with proper support for abstraction and operator overloading like C++ (or Rust, but might not be good enough yet) and define suitable types with constant-type finite field operations implemented in inline assembly.

And write the non-crypto TLS protocol part in a safe language like Rust while we are at it.

I see I didn't do a good job of explaining why that doesn't work so well. See, papers on high-performance elliptic curve cryptography tend to give formulas for implementing calculations using the three-operand style I mentioned. One reason for having a DSL is to make it so that we can copy/paste, with minimal changes, those formulas into our programs so that we can easily see that we're implementing the formula from the paper exactly. If you C++-ify or Rust-ify them, then you lose that obvious "this is the same" comparison ability. Also, for the kinds of code where such a DSL would be relevant, you really don't want a C++ or Rust compiler's optimizer to be involved at all. And, if you want to prove the correctness of your ECC code, you don't really want to have to first (1) Define a formal semantics for C++ or Rust, (2) Prove that your C++ or Rust compiler is correct with respect to that formal semantics, and (3) Prove that your transliterations of the original formulas are equivalent to the original formulas.

I've already written a prototype that compiles that DSL into C, which requires a leap of faith that the C compiler won't ruin things for us. That prototype convinced me that it would likely be much less work to go the DSL route than the C++/Rust library route. Note that I prefer writing C++ and Rust libraries to creating DSLs, so this was a disappointing conclusion for me.

Would it make more sense to go directly to something like LLVM? It's already a pseudo-assembly.

LLVM is every bit as bad as C for this—it's impossible to compile stuff with timing guarantees.

Integrating with LLVM is almost definitely more work than just porting the simple compiler to multiple architectures. Plus, LLVM is actually the source of the difficulty of writing constant-time code using Rust's official compiler, because LLVM is too smart.

I'm sure you've thought about this: what are your thoughts on embedding the DSL into Rust code, using a compiler plugin that emits assembly?

Right now, I don't see any advantage of embedding the DSL into Rust code, when instead I could have the DSL completely separate from Rust, and just use Rust's FFI to access what the DSL compiler generates. One benefit of the FFI route is that the result wouldn't be Rust-specific.

Remember that one of the goals is to become confident that the implementation is correct without also having to analyze whether rustc is correct or whether the Rust language has meaningful semantics. If we involve rustc in it, then we've greatly expanded the scope of what we have to analyze.

Even if asm! were stable in Rust, I would still prefer to have my assembly language in separate .s/.asm files. rustc gets updated every 6 weeks, which is great, but I'd really kind of like my assembler to be more static than that. Assembly language benefits massively from having macros, but Rust actually is not as good of a macro language for assembly as existing assembler macro languages. I'd rather see rustc improve at compiling Rust code than have it try to also compile ASM code.

https://github.com/klutzy/nadeko is an example of doing this.

Reply on news.ycombinator.com