Hello!

I've noticed there are very few crates implementing shamir's secret sharing scheme and RustySecrets seems to be the most advanced (and the only one that is still maintained, sadly).

I've noticed there are issues with protobuf (#69 and the current protobuf dependency is outdated) and since I had trouble with protobuf+rust myself in the past I'm feeling a bit uncomfortable about that.

I'm very interested in the ssss code itself though and considering to use it in a project. I would probably solve the signature problem myself by specifying a binary format and write a nom parser manually, and possibly drop K and N from the shares-string and store that information somewhere else in the application.

If there's interest I could also prepare a patch to replace protobuf in RustySecrets, but this is probably not what you want since that would be a breaking change.

The reason why a separate crate might be a good idea is because even if protobuf would be changed to an optional dependency, this still needs to be handled when packaging the crate for debian. This is a bit far ahead, but something I started paying attention to recently.

Please let me know if you have any thoughts about that :)

https://github.com/rust-unofficial/awesome-rust/

Looks like an awesome project, but unsure if this is being actively maintained, but it seems it is not bv the looks of open pull requests awaiting being merged such as #77.

Any input on this would be appreciated.

Thank you.

Since protobuf has removed MessageStatic in version 1.6.0, including rusty_secrets as a dependency in Cargo.toml now leads to build failure.

To reproduce this, create a new Rust project with cargo new, add the dependency rusty_secrets = "0.2.1" and build this project with cargo build.
This happens even though protobuf version is pinned to 1.5.1 in the Cargo.lock file.

Self-reminder I still have to write documentation for anyone willing to use it as a Rust library.

eg.

error.keyGroups = [[0, 2], [1]]

In the the SSS::secret_share function, the author clearly intended to make col_in an array of threshold bytes, but put a comma where the semi-colon should go in the vec! macro. Thus the code always generates just a single coefficient instead of threshold - 1 coefficients for our secret polynomial. So regardless of how high the threshold is set two shares are enough to uncover the secret.

This did not cause an error in the secret recovery code because of the fundamental uniqueness of the Lagrange polynomial: regardless of the number of nodes (shares) presented in excess of k + 1 for a k degree polynomial, Langrange interpolation finds the unique polynomial of degree k.

Here is an illustration of the problem:

extern crate rand;
use rand::{OsRng, Rng};

fn main() {
    let threshold: u8 = 6;
    let mut col_in = vec![0u8, threshold];
    let mut osrng = OsRng::new().unwrap();
    osrng.fill_bytes(&mut col_in[1..]);
    println!("{:?}", col_in);

    let threshold: u8 = 6;
    let mut col_in = vec![0u8; threshold as usize];
    osrng.fill_bytes(&mut col_in[1..]);
    println!("{:?}", col_in);
}

[0, 234]
[0, 196, 181, 63, 217, 112]

The error I get:

error: multiple packages link to native library `ring-asm`, but a native library can be linked only once

package `ring v0.12.1`
    ... which is depended on by `lamport_sigs v0.5.0`
    ... which is depended on by `merkle_sigs v1.5.0`
    ... which is depended on by `rusty_secrets v0.2.2 (file:///xxx)`
    ... which is depended on by `foo v0.1.0 (file:///xxx)`
links to native library `ring-asm`

package `ring v0.13.2`
    ... which is depended on by `merkle v1.10.0`
    ... which is depended on by `merkle_sigs v1.5.0`
    ... which is depended on by `rusty_secrets v0.2.2 (file:///xxx)`
    ... which is depended on by `foo v0.1.0 (file:///xxx)`
also links to native library `ring-asm`

I've submitted a PR to update lamport_sigs:
SpinResearch/lamport_sigs.rs#15

I've tried to do the same for merkle_sigs, but the current master depends on a different version of merkle.rs that I couldn't build on my system due to a build failure in a dependency:
SpinResearch/merkle.rs#47

It appears that all simple solutions to do code coverage reporting with Travis appear to be broken. Travis-Cargo broke and appears to be no longer maintained. I'm not willing to commit maintaining a fork of it at the moment, so for now I look at code coverage locally before merging pull requests.

This issue is a placeholder for a discussion about longer-term plans.

cargo +nightly bench fails because benchmark files are trying to import modules not included in the library. I don't know how you'd like to address this, or else I'd make a PR. I've just been commenting out benches/{ss1,thss}.rs.

After #74 is merged. #74 will fix #71, and is a breaking change (since it includes semver breaking updates of multiple dependencies), so it will have to be version 0.3.0 instead of version 0.2.3.

https://github.com/japaric/trust

Currently there is a (1 / 256) ^ t probability that a secret byte can be recovered with k - t shares. This happens if the a_k-1, a_k-2, ..., a_k-t coefficients are uniformly chosen to be 0. By ensuring the a_k-1 coefficient is non-zero, this probability would be zero.

Appears rusty_secrets::sss::generate_shares returns Result<Vec<String>>, which sounds odd for ciphertext. In fact, collections::string::String says "Strings are always valid UTF-8. This has a few implications, the first of which is that if you need a non-UTF-8 string, consider OsString. It is similar, but without the UTF-8 constraint." I suppose your encoding via protobuf makes all that fine though and you mean to send this over text channels anyways?

• rustc 1.17.0 (56124baa9 2017-04-24)
• cargo 0.18.0 (fe7b0cdcf 2017-04-24)

RustySecrets ~> cargo build
    Updating registry `https://github.com/rust-lang/crates.io-index`
    Updating git repository `https://github.com/SpinResearch/merkle_sigs.rs`
 Downloading ring v0.6.3
 Downloading rand v0.3.15
 Downloading protobuf v1.2.1
 Downloading rustc-serialize v0.3.22
 Downloading libc v0.2.20
 Downloading untrusted v0.3.2
 Downloading lamport_sigs v0.1.2
 Downloading merkle v1.1.0
   Compiling ring v0.6.3
   Compiling rustc-serialize v0.3.22
   Compiling rusty_secrets v0.0.3 (file:///Users/garrett/code/freedomofpress/RustySecrets)
   Compiling untrusted v0.3.2
   Compiling protobuf v1.2.1
   Compiling libc v0.2.20
   Compiling rand v0.3.15
   Compiling lamport_sigs v0.1.2
   Compiling merkle v1.1.0
   Compiling merkle_sigs v1.1.0 (https://github.com/SpinResearch/merkle_sigs.rs?tag=1.1.0#0f59ad68)
warning: use of deprecated item
   --> src/share_data.rs:259:29
    |
259 |                 fields.push(::protobuf::reflect::accessor::make_repeated_bytes_accessor(
    |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: #[warn(deprecated)] on by default

    Finished dev [unoptimized + debuginfo] target(s) in 29.90 secs

https://docs.rs/error-chain/0.11.0-rc.2/error_chain/

I was reading draft-mcgrew-tss-03.txt on the IETF tracker, it has some very good ideas that I would love to see in here.

I'll do some more research on it and come up with a list of enhancements. Would be also cool to be compatible with other libraries implementing the standard.

https://github.com/japaric/criterion.rs

Protocol buffers could be the default deserialized structure.

It could contain:

• A version of the result (if can't be parsed, suggest to update the software)
• Extension / MIME-Type of the data
• The actual data

Optional values such as generation date, a signature of a potential sender ...

The Build fail due to merkle v1.10.0:

   Compiling merkle v1.10.0
error: failed to run custom build command for `merkle v1.10.0`
process didn't exit successfully: `/Users/kaller/IdeaProjects/dssaa_s/target/debug/build/merkle-f78177df6eb47b03/build-script-build` (exit code: 101)
--- stderr
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: Os { code: 2, kind: NotFound, message: "No such file or directory" }', src/libcore/result.rs:1009:5
note: Run with `RUST_BACKTRACE=1` for a backtrace.

When generating shares, first the terms a_k-1, a_k-2, ..., a₁ are picked (pseudo-)uniformly at random from GF(256). a₀ is the secret we wish to split. The resulting polynomial is a_k-1x^k-1 + a_k-2x^k-2 + ... +a₁x¹ + a₀. We then evaluate this polynomial at x = 1, 2, ..., n to generate n shares. Observe that if we know k and n already, it is possible to select k - 1 terms, and to evaluate the polynomial a_k-1x^k-1 + a_k-2x^k-2 + ... +a₁x¹ at x = 1, 2, ..., n. Thus we have done the bulk of the computational work before even receiving a secret, and to "finalize" the shares we need only perform n XOR operations (addition in GF(256)). Of course, signing cannot start until the shares are "finalized."

Imagine a user application where the user is first asked to define k and n. While the user is then entering the secret--typing/pasting text, selecting file(s), etc.--the share generation is being mostly completed. The time difference would be user-perceivable for large k and n.

Imagine a network application that frequently splits and distributes secrets. It waits on some other process for a new secret to become available, and then splits it and sends it to a number of other nodes/ parties. If it is able to mostly precompute the shares before receiving a secret, this could cut down signficantly on system latency, especially as n and k grow.

There's no standalone implementation of GF(256) on https://crates.io, and it's a finite field that's used often in cryptography. Making gf256 a standalone crate would be a good contribution to the Rust community.

I think adding the isomorphic GF(256) representation generated by x + 1 and 0x1B, as that's used in AES and many other implementations such as the IETF draft Threshold Secret Sharing
draft-mcgrew-tss-03.txt (see #8) would be a good idea if this were to be done.