search

WebAssembly / design

WebAssembly Design Documents
http://webassembly.org
Apache License 2.0
11.42k stars 694 forks source link

Constant-Time WebAssembly #1299

Open chicoxyzzy opened 5 years ago

chicoxyzzy commented 5 years ago

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 commented 4 years ago

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

binji commented 4 years ago

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 commented 4 years ago

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

deian commented 4 years ago

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

vhnatyk commented 4 years ago

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

a base for Constant-Time proposal

deian commented 4 years ago

@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 commented 4 years ago

@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 commented 4 years ago

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.