Split method generating duplicate shares sometimes

[nalo26]

Description of the issue
I need to use this module for sharing a secret key. To ensure the good working of it, I created a test function that generate a random key, split it in shares (3 parts and 2 thresholds), and then combining it back.

For some reason, it appears that sometimes I got the error Duplicate sample when combining the keys. In fact, 2 of my keys are exactly the same.

After a bit of investigating, I found out that it is caused by x_coordinates when generating the shares. If a number is duplicated in the parts firsts values (where parts = 3 in my case), then the shares at index of those duplicates will be the same.

Expected behaviour
Shares are all different

Random bad behaviour
Some shares are exactly the same

To Reproduce
Steps to reproduce the behaviour:

1. Go to shamir.py line 77
2. Replace x_coordinates = [secrets.randbelow(255) for _ in range(1, 256)] with some random numbers, except that there's a duplicate in the 3 firsts one. For example (notice the two 1 at the beginning of the list) :

x_coordinates = [1,1,57,119,170,112,72,53,195,195,131,192,11,101,31,200,190,241,209,89,228,99,82,125,78,208,199,62,225,97,136,19,152,115,66,53,245,214,98,78,165,113,182,159,8,64,223,201,118,117,246,207,22,136,48,50,218,73,107,43,219,83,188,234,104,1,108,206,221,38,183,77,96,138,35,1,213,184,246,241,242,64,239,246,37,206,22,224,159,133,221,64,207,211,24,128,114,227,236,96,42,254,165,64,103,233,143,45,225,97,187,140,98,174,183,209,132,225,233,94,64,180,200,109,190,40,143,153,210,207,220,130,139,75,114,87,45,45,93,111,102,42,247,50,82,208,233,52,67,242,193,218,158,239,22,220,47,136,114,99,244,150,39,198,21,108,64,228,180,214,215,24,248,81,193,215,6,106,84,128,26,196,232,9,247,119,203,64,247,158,16,45,233,108,85,67,94,39,157,64,240,184,129,151,158,117,85,105,254,116,203,252,160,90,56,226,118,105,157,106,239,162,39,50,117,187,187,102,177,101,114,96,250,70,103,26,113,168,2,140,5,151,105,136,129,235,167,75,154,199,204,243,149,156,251]

3. Run this simple piece of code (you can find it here) :

from base64 import b64decode
import pyshamir

secret = b64decode("a+m4G0kEkKDQK4MFGz7L0vLz5oViQkDSLThiC4zDRZU=")
shares = pyshamir.split(secret, 3, 2)
for share in shares:
    print(share.hex())

4. As a result, shares 1 and 2 will be exactly the same (as a result of the duplicates 1 in the list), and share 3 will be fine

How to resolve
I think that to solve this problem, the solution is as simple as ensure that the parts first numbers of this x_coordinates are unique. But as I don't know the deep working of this, I don't wanted to make a pull request.

Desktop

• OS: Ubuntu 22.04
• Python: 3.10.6
• Pyshamir: 1.0.0

[sidsbrmnn]

@nalo26 Hi there! That's a good catch there. Thanks for raising the issue. We'll take a look at it as soon as we can and attempt on a fix for it.

[konidev20]

Hey @nalo26,

The domain of the x_coordinates should be in the open interval [0, 256) and we need 256 unique x_coordinates, logically because of pigeon hole principle, if we try to generate numbers less than 256 in 256 unique positions, then we will always have duplicate x_coordinates.

We found that we need to generate a random shuffle of x_coordinates rather than generating unique x_coordinates. To achieve this, we have generated x_coordinates in the open interval [0,256) and always generate a random shuffle of this array using secrets.SystemRandom().shuffle(x_coordinates).

I ran the unit tests multiple times, similar to your script, and couldn't find a duplicate with the split. Please check the MR and comment if you're good with it.

Thanks,
@konidev20

[nalo26]

Alright, that's a good fix ! Thanks @sidsbrmnn @konidev20, but i'm afraid there still is an issue :

File "pyshamir/shamir.py", line 85, in split
  output[i][len(secret)] = int(x_coordinates[i]) + 1
ValueError: byte must be in range(0, 256)

Before the fix, the x_coordinates where generated as follow : [secrets.randbelow(255) for _ in range(1, 256)]
This is generating a list of 255 values in the open interval [0, 255) (or in the closed interval [0, 254])

With the fix, this is now generating a list of 256 values in the open interval [0, 256) (or in the closed interval [0, 255])

I managed to fix this little issue by removing the +1 when generating the list in the generate_x_coordinates(n) function.
This is fixing the issue by generating back 255 values in the open interval [0, 255), as before.

Thanks for having addressed the issue that fast ! After this little fix, is it possible for you to create a new release ? It would be more convenient for me to update with pip instead of editing the sources !

[konidev20]

Hey @nalo26, thank you for your continued help to improve this package. I have raised another MR. Please share with us your script you're testing this package with.

[nalo26]

@konidev20 Here's the code i'm using:

import pyshamir
import random

from Crypto.PublicKey import RSA
from tqdm import tqdm

PARTS = 3
THRESHOLD = 2


def main():
    for _ in tqdm(range(1000)):
        rsa_key = RSA.generate(2048)
        base_pk = rsa_key.export_key("PEM")

        # Splitting private key
        shares = pyshamir.split(base_pk, PARTS, THRESHOLD)
        shares_hex = [share.hex() for share in shares]

        # Reforming private key
        shares_bytes = [bytes.fromhex(share) for share in shares_hex]
        shares_rdm = random.sample(shares_bytes, k=THRESHOLD)
        reformed_pk = pyshamir.combine(shares_rdm)
        assert base_pk == reformed_pk


if __name__ == "__main__":
    main()

It's a simply version of my needs: Generating a RSA secret key, splitting it with the module, exporting the shares as hexadecimals numbers to be given, before reforming all of it back.
In case you're wondering, the tqdm module and function is only used for tracking the progress of my bruteforce test.

Thanks again for the fixes!

[konidev20]

Hey @nalo26,

we will do a release shortly by this weekend I reckon.

Thanks
@konidev20

[konidev20]

Hey @nalo26,

you can find the latest release here : https://pypi.org/project/pyshamir/

Thanks & Regards,
@konidev20