Hacker News Reader

Comment by gizmo686 | Hacker News Reader

Crypto poses a unique challenge with the threat of timing attacks. A major benitif of using low level languages is that it is easier to assure that your code takes constant time regardless of the input.

View on HN

So what candidates are there? While C may make it possible to write code that avoids timing attacks, a quick glance at [1] shows one must avoid memcmp and array lookups based on secret data, neither of which would be prevented by the compiler, and both probably similarly easy mistakes as heartbleed.

Can Rust compile to a shared lib the programs can use as easily as a C library? (I think the answer is "not yet", but I'm not sure? At least, I've seen projects for compiling Rust without any runtime library).

Today I learned this is possible with Ada [2], but it seems there is some boilerplate to start/stop the runtime. Does Ada provide the necessary low-level control to implement crypto?

Are there sufficiently strict dialects of C?

NaCl [1] says "There are an increasing number of cases where the C implementations and assembly-language implementations are automatically generated from code that was actually written in another language, such as CAO or qhasm."

CAO is a "a domain specific language for describing cryptographic software" [3], while qhasm [4] is a portable assembly seemingly not focused on safety.

[1] http://nacl.cr.yp.to/internals.html

[2] http://gcc.gnu.org/onlinedocs/gcc-3.4.3/gnat_ugn_unw/Creatin...

[3] [PDF] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.113...

[4] http://cr.yp.to/qhasm.html

Can Rust compile to a shared lib the programs can use as easily as a C library?

Yes it can! You use the `#[no_std]` if you wish to be rid of the runtime, and the `#[crate_type = "lib"]` for outputting shared libraries (or use the `--crate-type` compiler flag).

Here's an older blog post on it, though the rust code there probably won't compile as-is with current Rust: http://bluishcoder.co.nz/2013/08/08/linking_and_calling_rust...

Unfortunately, this means giving up the powerful Rust standard library and threads. Fortunately, third-party devs are creating a "zero-runtime" standard library that can be used in situations like this, and in embedded programming:

https://github.com/thestinger/rust-core

Right now, rust-core only provides basic collections and io, but more may be in the works. I suspect rust-core will eventually grow into a small but capable standard library.

rust-core has been coasting along in maintenance mode for quite a while now, because it was only intended as a temporary stopgap. Nobody really wants to fragment the community with a third-party standard library.

Instead, the Rust devs intend to restructure the standard library such that it has multiple profiles, and that you can jettison parts of it (such as the parts that require the runtime) without losing all of the other goodies. Here's the most recent RFC for doing so, filed yesterday: https://github.com/rust-lang/rfcs/pull/40/files

Oh, very cool. I was hoping something like this would emerge.

To be clear, #[no_std] only "removes" the runtime by ensuring you don't accidentally use any functions that need the runtime. Something like

  #![crate_id="basic_lib"]
  #![crate_type="dylib"] // for a .so

  /* not there's no `no_std` */

  #[no_mangle]
  pub extern "C" fn add_in_rust(x: i32, y: i32) -> i32 {
      x + y
  }

Compiling that will give a `libbasic_lib....so` which can be linked against by any C program, and the `add_in_rust` function called without the Rust code needing to touch a runtime. (I imagine that one may have to add some extra linker flags.)

There are many functions/types in libstd etc. that can be used without a runtime (although its still not as great as it will be in future).

> qhasm [4] is a portable assembly seemingly not focused on safety.

When you start to worry about compiler bugs, hand written macro assembly isn't such a crazy idea for algorithms like SHA, MD5, RC4, AES. It is also easier to reason about timing in assembly. The truly paranoid would have to check compiler output anyways.

The truly paranoid worry that the processor will not execute instructions as they think it will. This ranges from timing irregularities from branch prediction and instruction re-order to bugs in CPU microcode or deliberate backdoors in the the design, or even the fab altering the mask to change the design. https://eprint.iacr.org/2007/039.pdf http://www.cl.cam.ac.uk/~sps32/microsemi_re.pdf

Ada allows much more precise and standardised control of low level details than C or C++ do. You can, in a standardised way, define a record (struct) where the fields are a signed integer taking up 3 bits, followed by a 1 bit bool and then a 4 bit signed integer, followed by two 16 bit unsigned integers, and have them all packed in the order you've specified (including whether it is big or little endian), and only allowed to be used in the specific memory locations you've selected (think memory mapped control registers on a MCU). This is all part of the language spec. Not only that, if you want you can have a pointer (or access type) to that single bit bool if you need to (so obviously access types are more powerful than pointers because almost anything can be addressed, including things on remote machines if memory serves).

You also get the powerful feature of pre and post conditions being part of the language from Ada 2012 onwards, meaning you can even more precisely control what's happening. You can have types for potentially dangerous data and safe data that cannot be intermixed without being very explicit about it (something that would've avoided this bug if I understand it correctly).

I've said it in other threads, and it's worth saying again (as someone whose primary language is Haskell) Ada is absolutely the right choice for this sort of programming. It's just as low level, if not more so, as C, with all the high level constructs of C++ (well most anyway), it encourages writing safe code by making the safe easy and the unsafe hard, and has excellent open source tools backed by commercial compiler writers (AdaCore).

you could also probably go a little further for the core of the library and use the SPARK subset of Ada. It is almost like it was made for the purpose http://www.adacore.com/sparkpro/language-toolset http://en.wikipedia.org/wiki/SPARK_(programming_language)

With the downside being that things like Heartbleed become possible. Dealing with timing attacks in high-level code is not necessarily hard -- Haskell, for example, has strict evaluation.

I may err, but I don't really think it's that big issue. First off, "low level" isn't exactly synonymous to "efficient machine-code", I guess we well can expect from languages like Rust to become both efficient and predictable after a while. In fact, every non-lazy well designed static typed language implementation makes it very much possible to write code that compiles in pretty predictable way, so you can control execution time as well.

And the last, but not the least, timing attacks aren't chief vulnerability, really. If you expect a timing attack being real hazard you can randomize return time explicitly.

The problem is that a memory unsafe language leaves gaping holes. Protection against timing attacks doesn't help me if one can read my private keys (remotely!) with a simple Python script. Timing attacks at least require colocation in most cases and are much harder to implement and run for meaningful results. It's certainly worth thinking about how we can put memory problems to death in at least crypto code and imho C has proven to be a permanent problem in that regard.

I am still a (interested) Haskell beginner but whenever this discussion comes up the first thing I think is "why not try this in Haskell?" and I never give a thought that I would do this in Java which is my everyday language (and reasonably memory safe).

"Timing attacks at least require colocation in most cases and are much harder to implement and run for meaningful results"

Not true. It's long been known that timing attacks over a LAN are practical (replace LAN with intra-datacenter network). Relevant paper from 2003: https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

Isn't it then marvellous that Rust is (also) a low-level language?

Reply on news.ycombinator.com