mystenlabs / fastcrypto Goto Github PK

done - now we have https://github.com/MystenLabs/fastcrypto

Approving this, and we need a few extra upcoming PRs

• clear api in our codebase for signing using a) randomized signatures b) deterministic RFC6979, default should be the randomized (just for consistency with most implementations out there and the main ECDSA standard).
• an extra test for randomized sigs (sign with implA, verify with implB and vice versa)
• comparison benchmark and test for ecrecover as well.
• ECDSA-NM (which is already in progress)

Originally posted by @kchalkias in MystenLabs/narwhal#562 (review)

This is low priority and probably over-optimization. BLS aggregated sig verification requires the list of pubkeys to verify against. If the size of this set is large (ie thousands), then aggregation requires some effort (thousand additions in BLS12-381 curve). There are a few tricks here:

• cache most common subsets (ie for validators the top list of stake owners), an LRU might also be useful here
• if we know the full set of signers (N) and because we need 67% (K) of sigs, sometimes it's better to have the SumAllPubKeys already cached and just remove those who didn't sign (by subtraction).

Yes, it lets us set up the binary representation manifest for our project. In fact, this makes me think we should open an issue to inspect the key types and use serde annotations to make sure the OnceCell is elided when serializing, and reset when deserializing. We should open an issue.

Originally posted by @huitseeker in MystenLabs/narwhal#624 (comment)

Throughout fastcrypto, signature::Error is used as a default error. However, we should use the newly introduced FastCryptoError instead since signature::Error is from the signature crate.

At the moment signature verification passes a hash as an argument:
https://github.com/MystenLabs/narwhal/blob/36968d41de1680a8d79dbc3f7c301f322ba4ad1c/crypto/src/lib.rs#L210-L230

https://github.com/SalusaSecondus/CryptoGotchas/blob/master/README.md#signatures

An attacker mustn't be allowed to select the actual value being validated in the signature. (The hashing step in all standard signatures defends against that as they can only select the hash pre-image, not the value of the hash.) If they could then they could trivially craft a valid signature for an arbitrary public key by (essentially) generating a random signature and seeing what message would be verified by that signature and then returning that message/signature pair.

This will be required for benchmarking (similarly to empty/dummy signatures). It cannot empty (as collisions can break operations), maybe we can use the fastest non-cryptographically secure hash function for this purpose.

Unrelated to this PR, but we need a TODO fix here as the rand scalars should be at least 128bits (thus we should set vals[1] as well). Ideally I'd create a private function get_128bit_scalar and invoke that.

Originally posted by @kchalkias in #119 (comment)

We should have a feature for functions that are 100% deterministic and do not include any randomness. This is required from blockchain projects that want to ensure no keygens or signing is available on tx execution and verification; usually only the deterministic verification part should be added as a dependency to avoid any accidental non-deterministic calls.

The BLS12377 signature scheme currently resides in Sui, but it would make more sense to move it to fastcrypto.

Description

Ensure that we zeroize on drop all secrets (private key and key pairs) for every signature scheme implemented.

• BLS12-381
• edDSA
• ecDSA
• BLS12-377

Feedback from writing MystenLabs/narwhal#32 on our ed25519 implementation:

• the "master" record of our keys is now a ed25519_dalek type, which is zeroized properly on drop => can we ensure this sort of thing is kept as a convention for future impls? perhaps with a unit test?
• we do not perform any verifications on deserialization of a key, including:
  • canonical scalar representation for PrivKey,
  • small order element for Public keys and keypairs.
• we should probably add warnings about small order components in keys, as they will disagree with single-signature verification.

Inspirations for accomplishing the above:

• https://github.com/diem/diem/blob/main/crates/diem-crypto/src/ed25519.rs
• https://eprint.iacr.org/2020/1244.pdf
• https://github.com/novifinancial/ed25519-speccheck (contains test vectors!)

At the moment our logs are riddled with the following output:

EdwardsPoint{
	X: FieldElement51([986312278720011, 308481451238697, 499818313507985, 2043434245230999, 529376140600966]),
	Y: FieldElement51([1122918900483925, 1840648545462405, 2049000554172011, 588549553128558, 2195713730548988]),
	Z: FieldElement51([1, 0, 0, 0, 0]),
	T: FieldElement51([167659880001565, 819468384591364, 1320141236765074, 698068994910468, 216442548444488])
}))

We should make sure we have a decent Display/Debug implemented for all public key types, especially as we're about to embed those data types that can contain keys of several types (for user keys) : we will want to e.g. derive / reuse Display on the Sui side.

Conversely, for the PrivateKey type, we should make sure our implementations of Debug / Display never display the byte content of the keys, but rather some "elided private ed25519 key" sort of string.

There is also an optimization, where we can skip randomizing one of the sigs, see #120. This is for a future PR but we can add a TODO and reference the issue.

Originally posted by @kchalkias in #119 (comment)

do we need to support async traits if crypto offloading to workers is required?

ed25519-concensus batch verification is slower than ed25519_dalek due to extra deserialization/decompression requirements (In practice N extra point decompressions in ed25519-consensus). See https://twitter.com/kostascrypto/status/1566580906113912832 for more.

Move API to derive keys on-chain using hkdf. See hkdf_generate_from_ikm in fastcrypto https://www.rfc-editor.org/rfc/rfc5869

Move API to verify the message and its Message Authenticated Code

Q: how is key being passed in?

Inspired by this: MystenLabs/narwhal#627 (review)

For genesis, we have node runners that like to generate their keypair (EdDSA) from the ssh-keygen tool (a well-trusted implementation).

We would like to be able to import and deserialize an EdDSA keypair as generated from ssk-keygen, which means interpreting the armored format for the private key. We would add this functionality as a simple pub function in out ed25519.rs, which would be integrated in our tooling Sui-side.

The rust crate rust-sshkeys provides a lot of tooling for reading the ssh pem files, but unfortunately, at the moment, only reads Pubkeys (whereas we would like to generate a keypair, hence reading private keys).

Atm we only support batch verification of signatures over the same message, we should add functionality to batch verify signatures over different messages too. In practice we only expect impact on BLS timings, as ed25519 batch verification does not care if the message is the same or not.

1. Should we apply the same fix to Ed25519PublicKey:: verify_batch() at line 70?
2. Just curious, when batch is empty, does the verification succeed or fail?

Originally posted by @mwtian in MystenLabs/narwhal#750 (comment)

Moreover, MystenLabs/narwhal#750 probably shows a bunch of tests that live in Sui and check behavior with batches of signatures (to deal with "obligations") should probably live in Narwhal (to catch issues faster!).

/cc @joyqvq @punwai

This will help to avoid surprises in Sui or Narwhal re using different sha2/sha3/keccak deps in different places. Ideally we should control every crypto algorithm in fastcrypto. After having these wrappers, we should update both Narwhal and Sui repos by invoking fastcrypto's api.

I was thinking that the same applies for base64, but let's wait for this, as Rust's popular base64 crate is working on the malleability fix.

Here are two brief papers exposing attacks on key aggregation, tailored to the consensus context:
https://eprint.iacr.org/2021/323
https://eprint.iacr.org/2021/377

It would be great to extract a few test cases that explore our thinking around the attack scenarios in the above & how to defend against them. It would tie up nicely with how we set up PoPs ( MystenLabs/sui#3884 ).

/cc @joyqvq @punwai

MystenLabs/sui#4678

Solve the problem：Fully decentralized support for BTC Move contracts on the Sui network.

reference project： ChainX and ICP
their solution： BTC Light Node + Threshold Aggregate Signature + Smart Contract platform
For the BTC aggregate address to host BTC, only the addresses and accounts hosting BTC are decentralized enough to make BTC look as decentralized as POS. For example: Bind the aggregated custody account to the node account on the chain one by one, which is as decentralized as the POS chain.

There is still a problem with this way of thinking. Our OmniBTC wants to combine this solution of ChainX and the Lightning Network to be deployed on Sui to provide Sui with a fully decentralized BTC. It also allows BTC to carry the Move contract.

OmniBTC solution:
BTC Light Node + Threshold Aggregate Signature + BTC Lightning Network + MoveVM
Lightning Network solves the mutual trust problem between Alice and Bob.
We just need to replace Alice with a BTC aggregate signature account (co-hosted by a sufficiently decentralized POS node on Sui or a Dao administrator selected above).

BTC holders can fully trust the BTC to the Lightning Network, and then come to Sui to use any Defi and gamefi.
It all looks so cool. So we think it is necessary for MoveVM to support the schnorr signature algorithm of Secp256K1

@kchalkias

Atm we only compare batch verification between different schemes, but for BLS this is not ideal, because in practice we should compare an aggregated BLS vs batched ed25519/secp256k1

Quoting a comment by @kchalkias in #119:

Unrelated to this PR, but we need a TODO fix here as the rand scalars should be at least 128bits (thus we should set vals[1] as well). Ideally I'd create a private function get_128bit_scalar and invoke that.

discuss after public testnet

• Thomas Pornin has come up with a faster way to do subgroup checks on Twisted Edwards curves:
  https://eprint.iacr.org/2022/1164
• they are implemented in his library:
  https://github.com/pornin/crrl

These methods are not yet implemented in ed25519-consensus's backend:
https://github.com/zkcrypto/curve25519-dalek-ng/blob/763a0faaf54752b06702b39e2296173ab76c2204/src/edwards.rs#L887-L920

We may want to implement them and/or contribute that implementation upstream.

Description

Keypair serializes, but does not deserialize when trying to test it out in MystenLabs/narwhal#557. Does not break Narwhal nor Sui so continuing with MystenLabs/narwhal#557 anyways.

To replicate this issue, run the following test:

#[test]
fn test_kp_serde() {
    let kp = keys().pop().unwrap();
    let serialized = bincode::serialize(&kp).unwrap();
    let deserialized: Ed25519KeyPair = bincode::deserialize(&serialized).unwrap();
}

We get this error:

thread 'bls12377_tests::test_kp_serde' panicked at 'called `Result::unwrap()` on an `Err` value: Custom("invalid Base64 encoding")', crypto/src/tests/bls12377_tests.rs:375:75

Upon further digging, it looks like removing this line fixes the issue:

#[serde(tag = "type")] // REMOVE THIS LINE
pub struct Ed25519KeyPair {
    name: Ed25519PublicKey,
    secret: Ed25519PrivateKey,
}

Currently, MallocSizeOf (a trait from mysten-infra) is implemented for PublicKeys, Signatures and AggregateSignatures for BLS123381 and Ed25519 in mysten-infra, because it is needed in Sui. However, this introduces som complexity because the fastcrypto version in Mysten-infra and Sui has to be exactly the same.

Z_0 can be safely set to 1 when batching. This allows for a 0.5% faster batch verification when verifying 32 sigs, and about 4.5% when batching 2 sigs. Note that batching 2 and 3 sigs might be applicable to digital certificate paths, which are usually 2-3 certs long. See preliminary results here: https://twitter.com/kostascrypto/status/1541313401787486209

Also required to support drand.love that requires G1 keys. Ensure we have good struct names, so we can distinguish between BLS12381G1keys and BLS12381G2keys.

Note that Sui uses keys in G2 because they are reusable inside epochs, thus we want to optimize on sig size.

Similar to #117, but for BLS.

Wondering if we should avoid mentioning ed25519 directly and switch to zip215 for clarity. Obviously we should explain that it's an ed25519 mode.

The single error case of this TryFrom is just an invalid length error. There is a host of other problems completely ignored by the current implementation:

• there are sequences of 32 bytes that will structurally not ever be usable as an Ed25519 Public Key in any way,
• there are sequences of 32 bytes that will 100% be usable as an Ed25519 Public Key, but that demonstrably and unambiguously aim at tricking anybody who does so.

The above takes exactly none of that into account. Further, several of those checks will not be performed by check_internal's dalek::PublicKey::from_bytes (and the library has a nice warning to mention some of that).

I admit it's probably a completely orthogonal point to this PR, and worth tackling in a different issue (probably extracted from this comment), but I'd appreciate a spectacular comment on PublicKeyBytes making this clear. Here is an example of my personal minimum bar for the word "spectacular".

Originally posted by @huitseeker in MystenLabs/sui#94 (comment)

As we are integrating more crypto schemes in our library (see e.g. MystenLabs/narwhal#484), it would sure be nice to integrate wycheproof ( https://github.com/google/wycheproof ) to our tests to make sure our current and future implementations are not too clowny. In rust, that has recently been made much more easy using https://github.com/randombit/wycheproof-rs

Currently the crate doc has very minimal doctest or example: https://docs.rs/fastcrypto/0.1.2/fastcrypto/

Ideally each API can have an example similar to https://docs.rs/fastcrypto/0.1.2/fastcrypto/hkdf/fn.hkdf_generate_from_ikm.html