SLIP-0039- How to properly split up the bits of a secret share

[Sharpiro]

Hi, i'm new to cryptography and cryptocurrency and thought this would be a cool way to learn more and get involved. I have a few questions about this SLIP. Here is a link to my rough code base that I'm working on if you're interested. Thanks.

From this value, every byte is mapped to the specified field in a little-endian fashion (i.e. the first bit maps to a_7, the last bit maps to a_0). For each such field element, N-share field elements are generated and mapped back to bytes. Each participating party receives the following data:

What does little-endian mean in this case? If i currently have a byte array representing the secret+checksum, do I need to iterate over the bytes in reverse while creating the secret pieces? I don't understand how little-endian is relevant here if I am simply doing bitwise operations/log table lookups on a byte using GF 256 math over the Rijndael field.

This structure is then converted into a mnemonic passphrase by splitting it up by 10 bits which correspond as an index to the a word list containing exactly 1024 words

I'm unclear on how to "split up" the 298 bits in the case of a 256 bit secret. Let's say I want to split up the following bytes into 10 bit chunks:

list := []byte{5, 10, 255, 199} // 0b00000101 0b00001010 0b11111111 0b11000111

Given that "little-endian" was mentioned prior, would my output into 10 bit chunks look like this using LSB bit numbering:

1010000001 0100001111 1111111000 11 // 641, 271, 1016, 3

or using MSB bit numbering:

0000010100 0010101111 1111110001 11 // 20, 175, 1009, 3

[jakubtrnka]

My understanding of the problem is that translating 'data-bits' into field element bits is done in little-endian manner. I. e. data- or, say secret message, bits go in this way: d₀, d₁, d₂...d₇ whereas field elements bits in each octet are represented as f₇, f₆, f₅... , f₀ This is not about parsing message itself, but about implementing field arithmetic IMO.

[Sharpiro]

I guess I'm still confused, because the solution I discovered for how to do the secret sharing is to use GF 256 and essentially do the GF math on each byte in the secret when creating and then recovering.

Also when reviewing BIP0039 and how it splits up the data into 11 bits it followed the same pattern as the "MSB" example I listed above, so that's what I used in my code for this SLIP.

[prusnak]

@onvej-sl can you have a look?

[onvej-sl]

As jakubtrnka suggested, "little-endian fashion" refers to the way a byte is translated to a field element.

More formally: A byte is represented as a 8-tuple of bits. An element of GF(128) is represented as a polynomial over F(2) of degree at most 7. The mapping between bytes and field elements is as follows: A byte represented by

(b_1, b_2, b_3, b_4, b_5, b_6, b_7, b_8)

is mapped to the field element represented by

b_1*x^7 + b_2*x^6 + b_3*x^5 + b_4*x^4 + b_5*x^3 + b_6*x^2 + b_7*x^1 + b_8.

"Splitting up" is something completely different. It's applied to a bit array, which length even doesn't have to be a multiple of 8. And it's done in a "natural way". For example

1100000000111111

is split up to

1100000000 111111.

I see we should specify, whether the last chunk is padded by zeros (or something else) from the left or from the right. In other words, whether 111111 is interpreted as 11111100 (252) or 00111111 (63).

[jakubtrnka]

I'm currently building C++ implementation. It will be ready for review in few days.

[jakubtrnka]

here is my C++ implementation. This is a first version. The code needs to be cleaned and improved, debugged, linked to a better (pseudo)random generator. All this will be done in the future. https://github.com/jakubtrnka/ShamirsSecretSharingScheme

[prusnak]

We did some substantial improvements to our standard and we feel it's moving into right direction. Feel free to comment: https://github.com/satoshilabs/slips/blob/master/slip-0039.md

[jakubtrnka]

@prusnak I'd be happy to implement it. Any suggestion how to do it to make it Trezor-friendly? I guess doing it in C++ is not much usefull for most people.

[prusnak]

We'll write the implementation for Python (both for python-trezor and trezor-core) first. Implementation in C (for trezor-mcu/trezor-crypto) might come later.

[howech]

I have only just learned of SLIP-0039. I spent the weekend writing my own implementation of SSSS in a trezor-T emulator. I kind of independently arrived at many of the features suggested in SLIP-0039, but I did not add any additional error correction over what is already happening with BIP39.

You can find my working prototype (I can deal and collect shares from an emulator) in the 'ssss' branch of https://github.com/howech/trezor-core.git, along with the 'allow_15_21_mnemonic_length' branch of https://github.com/howech/trezor-crypto.git