Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple Secret Sharing using XOR operation (OCaml example).
let shuffle list =
let cmp _ _ = (Random.int 3) - 1 in
List.sort cmp list;;
let share ~secret ~length =
let rec loop secret length buffer =
if length <= 0 then secret :: buffer else
let noise = Random.bits () in
let piece = secret lxor noise in
loop piece (length - 1) (noise :: buffer)
in
let pieces = loop secret (length - 1) [] in
shuffle pieces;;
let recover pieces =
let op x y = x lxor y in
let head = List.hd pieces in
let tail = List.tl pieces in
List.fold_left op head tail;;
let pieces =
Random.self_init ();
share ~secret:23 ~length:10;;
assert (23 = recover pieces);;
@marcoonroad

This comment has been minimized.

Copy link
Owner Author

marcoonroad commented Apr 19, 2019

This is applied on words (integers), but we will rather desire to apply on character-level to split a whole message string as secret, either plain-text or binary bytes sequence. A good approach would be Base-64 encoding, enabling us to operate on a 64 values range during the random generation (think in Random.int 64).

Another future improvement would be to have commitments from such pieces before their sharing. During the recover phase, it provides the tools to avoid luring/cheating attacks. A stored fingerprint of the secret could work as a checksum here.

Finally, the output of plain shares/pieces is not secure. A good approach would be to receive public keys before the sharing phase, and output encrypted versions of such shares.

@marcoonroad

This comment has been minimized.

Copy link
Owner Author

marcoonroad commented Apr 19, 2019

The checksum also enables the brute-force of the message, only if fewer parts are missing due "shareholders" dropping the game in the middle. It possibly will only be feasible in some sense if the threshold is 90%, I guess - I should make a Proof-of-Concept for that...

@marcoonroad

This comment has been minimized.

Copy link
Owner Author

marcoonroad commented Apr 20, 2019

And also, the checksum let me encrypt the pieces in an internal format (for example, JSON) and then validate against corrupted data during traffic.

@marcoonroad

This comment has been minimized.

Copy link
Owner Author

marcoonroad commented Apr 22, 2019

UPDATE:

Full code available here: https://github.com/marcoonroad/shareholders

The shares are encrypted using the checksum (of the secret) as the AES CBC key & IV, then HMAC-alike signed with the digest of this secret checksum.

By encrypting the shares, I can add metadata on them, such as their position (i, j) on the random numbers matrix. Such metadata allow me to track missing matrix cells and them brute-force them against the checksum to recover the secret. The implemented redundancy on the library above will help here, 'cause it will reduce the vector space of missing share pieces to brute-force/discover.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.