Constant-Time WebAssembly

[chicoxyzzy]

This discussion was started in WASI repo https://github.com/WebAssembly/WASI/issues/65. It'd be great to have a way to keep wasm computations constant time (and prevent JIT optimizations) to implement cryptographic algorithms in userland. There is a great paper CT-Wasm which potentially could become a base for Constant-Time proposal.

[max-mapper]

There's a great talk on constant time cryptography from this years CCC https://www.youtube.com/watch?v=O07uRT-5BDM

[binji]

We discussed this in the Feb 2020 in-person CG meeting, and decided we should add a new repo for this proposal. Any suggestions for the repo name? Maybe constant-time?

[binji]

@deian Are you going to be champion of this proposal? I've added an initial repo here: https://github.com/WebAssembly/constant-time

[deian]

@binji Awesome, thanks for creating the repo! We're going to group champion this if that's okay (+@djrenren @conrad-watt +@hovav)

[vhnatyk]

is there any progress with this 😊 , wondering if CT-wasm was adopted as

a base for Constant-Time proposal

[deian]

@vhnatyk I hope to have a reasonable version by end of Aug! (Too many things on my plate till mid Aug.) The plan is to borrow a bunch of the ideas/design points from CT-Wasm, but leave out the multiple memories (since compiling to multiple memories is kind of hard).

[garrettgu10]

@deian No worries if not, but has there been progress on this recently?

Also, when you mention "leave out the multiple memories," are you saying that memories should not be labeled public/secret as mentioned in the CT-Wasm paper? If so, how can we ensure that secrets are not leaked through loads/stores?

[djrenren]

Hi, one of authors of the CT-Wasm paper here. The purpose of multiple memories was to ensure that the secret types could ensure there was no leakage. When we presented the design to the community group, the feedback was largely that Wasm doesn't need to enforce constant-timedness, instead it only needs to allow for it.

Secret memory existed for two reasons: type preservation (ensuring you don't store as secret but read as public), and protection from runtime optimizations (e.g ensuring secret writes are not omitted so we can zero out memory). The first reason is no longer relevant if we're shifting the responsibility for correctness to the wasm producer (rust/clang/hand-written, etc). We can accomplish the second result through the introduction of new secret memory ops, that operate on the main linear memory, but according to the spec, can't be elided by the runtime.

This model is much more amenable to the way languages and compilers work now. They assume a single heap. However, this weakening of CT-Wasm makes it more difficult for compiler authors to ensure their outputted Wasm is correct. We can't just prove correctness for them as part of typechecking. We envision some kind of static checker that may not be complete but should be able to catch some mismanagement of secrets.