search

jesseduffield / horcrux

Split your file into encrypted fragments so that you don't need to remember a passcode
MIT License
4.53k stars 116 forks source link

Implement Shamir's Secret Sharing #1

Closed kiwivogel closed 4 years ago

kiwivogel commented 4 years ago

You could also look at implementing Shamir's so that you can create more parts but don't need all of them. Might be a fun project.

Could probably just import this library and use the split method if you want to be lazy about it :P https://github.com/hashicorp/vault/blob/master/shamir/shamir.go

simonerni commented 4 years ago

Adding to @kiwivogel and repeating my comment from HN here:

This tool is pretty unsafe and should not be used. It is simply splitting the key in multiple pieces, thus for every piece you have, you gain additional information about the key, allowing for exponentially easier brute-forcing of the remaining key.

Example: Assume someone creates 3 horcruxes and you can get your hands on 2 of them. This gives you 85 bits of the full 128 bit key, thus you only need to brute force 43 bits for the rest. Of course you don't have the full data anyways, but you still learn about 2/3 of it.

An additional already existing tool is ssss which uses Shamir's Secret Sharing. http://point-at-infinity.org/ssss/ - or you use what's implemented by hashicorp.

jesseduffield commented 4 years ago

@simonerni what are your thoughts on having n separate keys when creating n horcruxes?

jesseduffield commented 4 years ago

@simonerni I've switched to using n full keys and it didn't have much of a performance cost for large files so I'm happy with that solution. As for Samir's secret sharing, I'll give that a look

jesseduffield commented 4 years ago

I've just downloaded ssss and given it a try. It only works for max 128 character secrets (unless I'm mistaken), whereas the purpose of my program is to encrypt whole files of arbitrary size. You could do a two-step where you use ssss to obtain the secret then another program to encrypt the original file but my plan was to make the program super easy to use for myself in 20 years time (which also means no dependencies, but ssss uses GnuPG)

I like the look of Hashicorp's approach, but the interface for those functions requires you have all the bytes you need in memory, which will cause issues for large files. Having said that, I could just change my approach to only do horcrux-y stuff regarding the key, and then use the key to encrypt the same file n times. Issue there being that each of the horcruxes will roughly be the same size as the original file, but I can't think of any way around that if I want to allow for horcrux thresholds (i.e. only requiring 3 out of 5 horcruxes).

I'll see what I can do

jesseduffield commented 4 years ago

@kiwivogel I've adapted the code (i.e. copied) from where you linked, and it works like a charm :) I believe I've done my due diligence by the mozilla MPL license (i.e. linking to the original code). Let me know if there's anything here I haven't addressed :)

simonerni commented 4 years ago

@simonerni what are your thoughts on having n separate keys when creating n horcruxes?

I assume in this scheme, each shard i is encrypted with it's key k_i. If you then store the encrypted shard e_i and k_i together, the original shard i is trivially recovered by simply decrypting e_i with k_i again, so you could argue that in this scheme, no encryption is applied at all and the data has only been encoded in a convoluted way.

but I can't think of any way around that if I want to allow for horcrux thresholds (i.e. only requiring 3 out of 5 horcruxes).

There are erasure codes which allow you to do exactly this. Popular example are the reed solomon codes, with lots of implementations and even hardware acceleration in certain Intel processors.

kiwivogel commented 4 years ago

Proper way to do this is create a master key and then split/distribute that using shamir's I guess.