Finite field arithmetic

jedisct1 commented 4 years ago

We need to expose basic arithmetic over finite fields and common operations on EC points in our API.

This is required to implement PAKEs and threshold signatures among things that the module doesn’t implement directly.

Operations over elliptic curves and quotient groups

Minimal set of operations we probably need:

Hash-to-group (once the irtf-cfrg-hash-to-curve draft settles)
Map to (optional)/from uniform random strings. This differs from the hash-to-group operation by the optional presence of an inverse map (e.g. Elligator)
Element verification: for an EC point, check the curve equation and that the point is on the main subgroup <— do we actually need this, or should we make it impossible to create an invalid group element?
Random group element
Addition, subtraction
Import, export
Scalar multiplication <— What about clamping? How do we go from this to a standard x25519 key? Shall curve25519 and curve25519-unclamped be exposed as different groups? Should scalar multiplication be clamped by default, and clamping can be disabled by setting a property on the point object? Should we expect applications to clamp themselves? Should a keypair import function clamp and recompute the public key?
Fixed base scalar multiplication

We also need to add functions to create public and secret keys (for DH and signing) from group elements.

Operations on scalars

Import, export
Addition, subtraction, multiplication, squaring, exponentiation, inversion, negation
Comparison, conditional move
Get 0, 1.

We probably don’t want a general bignum library here, and only support field sizes relevant to the curves we support. This will allow us to use optimized and formally verified (e.g. generated by fiat-crypto or HACL*) implementations.

Should that be in another module?

These operations can be in a different module.

If we go that route, how can a key pair be created from a handle coming from that other module?

Do we make a serialized representation the only way to import a key?

Thoughts?

tniessen commented 4 years ago

That's a really good point. This makes me wonder... Maybe it would be enough to provide these primitives? Sure, it would be a terribly long list, but if we assume that people need direct access to these primitives anyway, it doesn't matter. Maybe most cryptographic features could be implemented in WebAssembly then? For example, if we add timing-safe primitives, most timing vulnerabilities should not be a problem anymore. However, then hardware features such as AES acceleration are inaccessible again...

I am just putting this out there. I think it might not be entirely wrong to try to prevent WASI from becoming a full-featured crypto library with key import & export, hundreds of algorithms, ....

spitters commented 4 years ago

fiat-crypto can generate wasm via rust. For F* there is this library.

Did you consider those?

beurdouche commented 4 years ago

A better reference for F based code in WASM would be: https://github.com/project-everest/hacl-star/tree/master/dist/wasm (Directly comoiled from F to WASM) Or you could get faster code by compiling the generated C code with emscripten but without the translation guarantees.

spitters commented 4 years ago

@beurdouche Thanks. As you know the library well. How much of the issues above are already provided by F*.

jedisct1 commented 4 years ago

Having these operations implemented as a distinct WASM module is very compelling.

There will be some additional considerations, such as how to provide a universal API to convert an element into a key, but that should be pretty straightforward.

F* support for WASM is great news, and I know that there has been interest in supporting WASM on the fiat-crypto side as well.

The main issue is that WASM cannot guarantee the absence of side channels right now. The absence of some operations can also make it less efficient than native implementations.

Before suggesting pure WASM implementations, we should probably wait until some issues raised in https://github.com/WebAssembly/wasi-crypto/issues/21 have been addressed.

spitters commented 4 years ago

Fiat cryptography produces straight line code. Would that be constant time in wasm?

jedisct1 commented 4 years ago

Right now, there are no guarantees, especially since the code can be JIT'ed.

WebAssembly / wasi-crypto