Fast, low-level W-OTS+ signatures in rust
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
yak 58b02f56c4 inaugural commit 3 months ago
src inaugural commit 3 months ago
Cargo.toml inaugural commit 3 months ago
LICENSE Initial commit 3 months ago
README.txt inaugural commit 3 months ago

README.txt

Winternitz One-Time Signatures+

-----

Pretty much does what it says on the tin. Configurable and high-performance, meant to be used as a base for more complicated cryptosystems or for more convenient abstractions. Makes heavy use of const generics. no-std supported. Use whatever hash function and PRF you want, although I have provided an implementation that makes all the decisions for you.
The only thing you *can't* do is re-use a secret key, because the SignerBase type overwrites itself as soon as you sign anything. :)
Read https://eprint.iacr.org/2017/965.pdf for information about WOTS+ signatures. The primitive implemented in this library is identical to the one described in that paper. It is NOT the same primitive as the one described in RFC8391. THIS CRATE CANNOT BE USED TO IMPLEMENT RFC8391. However it would be simple to implement XMSS+ using this crate.
Only real limitations are: w must be a power of two, in fact you have to feed W_EXP so that w = 2^W_EXP. W_EXP must also be less than or equal to 8.
Enabling the 'blake3_chacha' feature gives you access to a basic standalone implementation. Read it in lib.rs if you want to see an example of how to make your own implementation, it's easier than it seems.
I did my best to make this implementation as embedded-friendly as possible, in particular the signer and verifier don't have to be initialized in the stack. But sometimes rather large arrays (the message converted to base-w) are stored on the stack, since to do otherwise would be slow.
Performance: it's pretty good. Key generation of the blake3_chacha variant takes between 22 and 600 microseconds (depending on the winternitz parameter) on my machine, which has a Ryzen 5 5500 CPU. Signing and verifying take roughly half that time on average, as expected. Based on tests with my machine, the overhead is very low, that is, the time it takes to generate a key is almost exactly the time it takes to calculate L+W-1 random values from a seed and W*L keyed hashes of those values.

SECURITY WARNING: I just read a paper and implemented what the paper said. I have no formal qualifications in cryptography and I cannot give you a good reason to trust me.
DO NOT TRUST THIS CODE unless 1) you have read it yourself and decided it is good AND 2) someone whose judgement on cryptographic matters you trust for good reason has read it and decided it is good.
DO NOT TRY TO MAKE YOUR OWN IMPLEMENTATION unless you have read and understood the paper linked above, in particular the security guarantees that the PRF & PRNG need to satisfy to be used in a WOTS+ signature scheme.

-----

USAGE

To get started, you need an implementation of SignerBase and/or VerifierBase. This meaning of 'implementation' is different from that of implementing a trait, since in reality there is only one SignerBase struct which is highly templated. For the purposes of this README I will refer only to the blake3_chacha implementation which comes with the library.
mk_blake3_chacha_wotsplus_instance!(m,w_exp,name) generates typedefs for Signer_name and Verifier_name, instances of the blake3_chacha SignerBase and VerifierBase respectively, which act on messages of length m and winternitz parameter 2^w_exp.
To generate a new random keypair, let mut signer = Signer_name::generate(seed_rng,None), where seed_rng is some cryptographically secure RNG which is used to generate K, the RNG seed for the key, and the random bytes for the secret key. This will return a Signer_name object.
The public key for this keypair can be output to a byte slice buf with signer.format_public_key(&mut buf). The secret key can be formatted to buf with signer.format_secret_keypair(&mut buf).
Secret keys can be read from buf, which carries formatted data, using mogrify_from(&buf).unwrap() and mogrify_from_mut(&mut buf).unwrap(). Buf must be _exactly_ the same size as the Signer_name struct. The return value of these functions is a reference with the same lifetime and mutability as the underlying buffer.
Owned secret keys can be read, let signer = Signer_name::from_formatted_keypair(&buf).unwrap();
To write a signature for message into buf, use signer.sign(&message,&mut buf,None). This will destroy the secret key; further uses of this key will produce signatures which cannot verify.
To generate a signer in-place given a mutable reference signer, use Signer_name::generate_inplace(signer,seed_rng,None);

To create a new verifier from the formatted public key in buf, let verifier = Verifier_name::mogrify_from(&buf) or let verifier = Verifier_name::mogrify_from(&mut buf). Like the mogrify functions of the signer, buf must be exactly the same size of the struct.
Owned verifiers can be read, let verifier = Verifier_name::from_formatted_pubkey(&buf).unwrap().
The verifier can be formatted using verifier.format_pubkey(&mut buf).
To verify message with signature sig, use verifier.verify_destructive(&message,&mut sig,None). The return value is Err(()) if there was some error reading the signature/message and Ok(false) iff the message failed to verify.
This will overwrite sig. Clone the signature before calling if you need to use it again.

Signer_name and Verifier_name have static fields which tell how large the message,signature,pubkey,and keypair need to be.
Signer_name::PKLEN = Verifier_name::PKLEN is the length of a formatted public key.
Signer_name::SIGLEN = Verifier_name::SIGLEN is the length of a signature
Signer_name::KEYPAIRLEN is the length of a formatted keypair.

It is VERY IMPORTANT that you only ever try to sign or verify messages which are exactly the same message length as you speciified when using mk_blake3_chacha_wotsplus_instance!(), and that you ONLY try to verify or decode signatures & public keys which were created using the exact same WOTS+ variant and formatting used in this crate. Otherwise nothing will work.

-----

CARGO

You may have noticed that I haven't done the 'traditional' thing for rust, which is to upload my project to crates.io or some such. This may mean some people don't know how to compile their code using this library!
Luckily the fix is pretty easy: simply put the wots release folder in your root tree and add this line to your Cargo.toml under [dependencies]:

wots = { path = "wots_release" }