News for hackers. Stuff that matters.
Re:I made an app that lets you split a file into horcruxes by compsciphd on Sunday August 02, 2020 @10:00AM (#24028747)
what is the difference between reed solomon erasure codes and shamir secret sharing?

i.e. if I just split the secret into a number of reed solomon error correcting blocks (where n blocks are sufficient to recover the full data), is that fundamentally different?

Re:I made an app that lets you split a file into horcruxes by OskarS on Sunday August 02, 2020 @11:06AM (#24029149)
Yes, it's very different: if you split some error coded thing across several files, each individual file is going to give you some chunk of the data. It's not secret in any way, it's just that you've only got, like, 1/7th of it.

With Shamir's secret sharing, having anything less than the required number of files is useless, you can't decrypt any of the data unless you reach the required number.

Re:I made an app that lets you split a file into horcruxes by pxx on Sunday August 02, 2020 @12:24PM (#24029594)
I wouldn't say it's "very" different as long as you make the code non-systematic. In a systematic code the first n blocks are the input data, but there's no reason you need to have it this way.

Even the par2 format will let you do what you want here. Just toss out the original input data and give people 1/k the correct amount of parity blocks. Given a large enough file size [1], there is a vanishing probability that you can recover additional bits of the input with fewer blocks than needed. This also allows you to transmit less bits total (each target gets 1/k as many bits).

Of course, if you don't like this argument, you can always just encrypt the par2 blocks and use Shamir to share the key. This reduces the overhead to a multiple of the (hopefully much-shorter) key. EDIT: Commentary further down the thread indicates that a better idea is just to use an all-or-nothing transform.

[1] We have information theoretical security in the sense than you can't recover n bytes from (k-1)n/k bytes, so what I'm saying is that we need large enough n/k.

Re:I made an app that lets you split a file into horcruxes by compsciphd on Sunday August 02, 2020 @11:25AM (#24029258)
hmm, googling around after my Q found this

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.80....

where the authors explicitly write: "Shamir's scheme for sharing secrets is closely related to Reed-Solomon coding schemes."

now, my eyes glaze over when it comes to the math, so I'll need to look it through a few times before I understand what they are saying.

Re:I made an app that lets you split a file into horcruxes by lowercase1 on Sunday August 02, 2020 @01:05PM (#24029880)
You could also look at http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf

You can combine the reconstruction properties of Reed Solomon (you need k of n pieces) with the All or Nothing Transform. Encrypting data so that you need all of the data to decrypt.

Then you can essentially do Shamir secret sharing witout storage overhead. A 1 MB file split so you need 5 pieces would have 200 KB pieces instead of 1mb pieces. This is at a cost of exchanging information theoretic security for computational security.

Re:I made an app that lets you split a file into horcruxes by ScottEvtuch on Sunday August 02, 2020 @10:14AM (#24028828)
Presumably the secret sharing algorithm is more resistant to brute forcing if you have one less than the required pieces. They solve opposite problems
Re:I made an app that lets you split a file into horcruxes by myself248 on Sunday August 02, 2020 @12:55PM (#24029807)
Could you make one equivalent to the other, by R-S encoding a key? And if you have less than the whole key (assuming it's large enough that the missing portion is still bruteforce-resistant), then even a partial reconstruction of the key still gives you none of the data.
Re:I made an app that lets you split a file into horcruxes by lowercase1 on Sunday August 02, 2020 @01:08PM (#24029910)
Yes you can! Apply an All or Nothing Transform before RS encoding so that you need all of the original data to decrypt. Then you can only decrypt if you have k of n pieces. You save by a factor of k in piece size over SSS.

http://web.eecs.utk.edu/~plank/plank/papers/FAST-2011.pdf