Shares converted to mnemonic form intermittently fail to recombine

[dcow]

Roughly half the time shares are generated and converted to their mnemonic representation, they recombine yielding an incorrect result. Here's some sample code to demonstrate the issue:

use bitcoin_wallet::{
    account::Seed,
    error::Error,
    sss::{ShamirSecretSharing, Share},
};

pub fn split(data: &[u8; 32], scheme: &[(u8,u8)]) -> Result<Vec<Share>, Error>
{
    let seed = Seed(data.to_vec());
    ShamirSecretSharing::generate(1, scheme, &seed, None, 1)
}

pub fn combine(shares: &[Share]) -> Result<Vec<u8>, Error>
{
    let seed = ShamirSecretSharing::combine(shares, None)?;
    Ok(seed.0)
}

#[cfg(test)]
mod unit
{
    use super::*;
    use rand::RngCore;

    #[test]
    pub fn sss_roundtrip_internal()
    {
        let mut data = [0u8;32];
        rand::thread_rng().fill_bytes(&mut data);

        let shares = split(&data, &[(2,3)])
            .unwrap();

        let r1 = combine(&shares[..2])
            .unwrap();
        let r2 = combine(&shares[1..3])
            .unwrap();

        assert_eq!(data, &r1[..]);
        assert_eq!(data, &r2[..]);
    }

    #[test]
    pub fn sss_roundtrip_mnemonic()
    {
        let mut data = [0u8;32];
        rand::thread_rng().fill_bytes(&mut data);

        let shares = split(&data, &[(2,3)])
            .unwrap();

        let mnemonics = shares.iter()
            .map(|s| s.to_mnemonic())
            .collect::<Vec<_>>();

        let internals = mnemonics.iter()
            .map(|i| Share::from_mnemonic(&i).unwrap())
            .collect::<Vec<_>>();

        let r1 = combine(&internals[..2])
            .unwrap();
        let r2 = combine(&internals[1..3])
            .unwrap();

        assert_eq!(data, &r1[..]);
        assert_eq!(data, &r2[..]);
    }
}

The sss_roundtrip_internal test never fails, however, the sss_roundtrip_mnemonic test fails intermittently.
Here is some example output (6 success, 3 failure):

% cargo test --package adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

% cargo test --project adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

% cargo test --package adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

% cargo test --package adi
    Finished test [unoptimized + debuginfo] target(s) in 0.02s
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

% cargo test --package adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

% cargo test --package adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... FAILED

failures:

---- unit::sss_roundtrip_mnemonic stdout ----
thread 'unit::sss_roundtrip_mnemonic' panicked at 'assertion failed: `(left == right)`
  left: `[124, 73, 15, 220, 128, 78, 234, 135, 187, 43, 221, 55, 182, 237, 162, 30, 228, 106, 239, 61, 254, 176, 109, 129, 196, 216, 125, 68, 29, 164, 26, 12]`,
 right: `[14, 153, 8, 23, 69, 184, 201, 116, 216, 126, 136, 164, 120, 231, 52, 206, 176, 198, 221, 190, 86, 44, 196, 53, 6, 169, 139, 77, 47, 5, 189, 198]`', adi/src/lib.rs:99:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    unit::sss_roundtrip_mnemonic

test result: FAILED. 1 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '-p adi --lib'

% cargo test --package adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... FAILED

failures:

---- unit::sss_roundtrip_mnemonic stdout ----
thread 'unit::sss_roundtrip_mnemonic' panicked at 'assertion failed: `(left == right)`
  left: `[190, 184, 191, 130, 17, 80, 154, 245, 204, 38, 145, 178, 106, 235, 87, 21, 79, 57, 239, 33, 35, 99, 180, 148, 143, 242, 250, 8, 226, 203, 232, 151]`,
 right: `[126, 235, 37, 157, 73, 41, 228, 71, 35, 159, 119, 113, 31, 108, 153, 163, 222, 33, 161, 108, 235, 50, 177, 174, 110, 163, 75, 247, 206, 13, 175, 47]`', adi/src/lib.rs:99:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    unit::sss_roundtrip_mnemonic

test result: FAILED. 1 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '-p adi --lib'

% cargo test --package adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... FAILED

failures:

---- unit::sss_roundtrip_mnemonic stdout ----
thread 'unit::sss_roundtrip_mnemonic' panicked at 'assertion failed: `(left == right)`
  left: `[58, 163, 196, 91, 115, 103, 154, 106, 255, 85, 132, 34, 13, 81, 78, 242, 205, 110, 161, 167, 125, 160, 250, 101, 8, 138, 14, 84, 28, 209, 89, 139]`,
 right: `[53, 177, 175, 17, 73, 175, 133, 126, 176, 228, 193, 159, 230, 250, 18, 149, 167, 153, 147, 83, 235, 134, 41, 235, 50, 15, 44, 50, 87, 226, 247, 207]`', adi/src/lib.rs:99:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    unit::sss_roundtrip_mnemonic

test result: FAILED. 1 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '-p adi --lib'

% cargo test --package adi
     Running target/debug/deps/adi-d0276c4a348266c4

running 2 tests
test unit::sss_roundtrip_internal ... ok
test unit::sss_roundtrip_mnemonic ... ok

test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

I've been poking around a little. I notice the to_mnemonic function is not actually tested in sss.rs. The from_mnemonic function is tested to correctly parse the TREZOR test vectors, and a roundtrip is tested using the internal Share representation, however there does not appear to be any code that tests converting shares to their mnemonic form. This leads me to suspect an issue with the encoding process. I started combing the code to see if anything jumps out, but would love some help (:

[stevenroose]

For BIP39 mnemonics, it's probably better to use https://github.com/rust-bitcoin/rust-bip39.

[dcow]

Sure, but this code still doesn't appear to work as demonstrated by the test case.

EDIT
Just to make sure you understand the scenario: I am splitting and recombining a seed using a 2,3 scheme not simply trying to roundtrip a seed to mnemonic and back using a 1,1 "split".

[dcow]

Actually, I'm not sure how BIP39 could even be used in place of the test case I have provided here. The only API exposed by this crate to serialize a SLIP-0039 share involves taking the mnemonic representation of the share. The Share struct, while public, doesn't offer any functions to convert to a vector or slice of u8 in the fixed format specified in slip0039. Are you suggesting that to_mnemonic is deprecated and we should be manually serializing the Share struct and then sending it though your rust-bip39 crate? Why not just update to_mnemonic to use rust-bip39?

[stevenroose]

Oh sorry I missed that you were talking about the SSS feature of this crate. I'm sorry to say that I have actually never looked at it. I took over maintenance from the previous maintainer of this crate. Tbh I spent some time in the past thinking about refactoring a lot of stuff in here and the shamir stuff would be one of the first things to go as it's really not required to build a bitcoin wallet.

[dcow]

Just FYI this crate is linked as an implementation of SLIP-0039 from: https://github.com/satoshilabs/slips/blob/master/slip-0039.md. I agree it would be nice to pull SSS & SLIP-0039 out of the bitcoin_wallet crate and into its own home. It's much cleaner that way and a separate concern.

[stevenroose]

I think the license of this project allows you to do that if you would like :)

…

On Mon, Mar 15, 2021 at 6:00 PM David ***@***.***> wrote: Just FYI this crate is linked as an implementation of SLIP-0039 from: https://github.com/satoshilabs/slips/blob/master/slip-0039.md. I agree it would be nice to pull SSS & SLIP-0039 out of the bitcoin_wallet crate and into its own home. It's much cleaner that way and a separate concern. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#27 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGQLXGMWDD2WZJWW5RJ45DTDZDLRANCNFSM4XROUNWQ> .