4 ms·

There's a cool paper-based backup tool that also uses Shamir Secret Sharing to let you distribute a bunch of paper copies to your friends to restore a file opti

There's a cool paper-based backup tool that also uses Shamir Secret Sharing to let you distribute a bunch of paper copies to your friends to restore a file optically: https://github.com/cyphar/paperback https://github.com/cyphar/paperback

wilg 3y ago
This is very neat! Feels a bit too early to rely on it, but could be very cool for lots of people if it was a bit more mature and easy to use.
deleted 3y ago
[deleted]
EE84M3i 3y ago
Does SSS work well for large inputs, or do you need to AEAD the plaintext and then SSS the key?
- cyphar 3y ago
  Paperback uses the AEAD-and-SSS-the-key construction, but that's more to do with the properties such a scheme gives you (it allows more flexibility with how you distribute the secret -- you can keep the main document with a lawyer and distribute the shards so even if the shard holders betray you they don't have access to the original document). You also want to have protections against fake-shard attacks (which allow an attacker with a real shard to withhold the secret from others during recovery and then keep the recovery secret to themselves), and so you need to make use of traditional cryptography anyway by signing shards to detect fakes. To answer your question though, it primarily depends on the SSS construction and how big the quorum (number of shards needed for reconstruction, not the total number of shards created) is. Most constructions use Galios Fields and thus chunk the input and produce a new polynomial for each chunk -- the vast majority use GF(2^8) which means its per-byte. Paperback uses GF(2^32) to get 4-byte chunks so that the x-value used is more collision-resistant. I suspect for large documents GF(2^32) will be about 4x faster because Galois Field operations are very fast (which is why most tools use them over prime fields) but using 4-byte chunks reduces the number of operations needed by 4x. I considered going for GF(2^64) to get 8-byte chunks but doing so requires 128-bit integers in some operations. You can also process the chunks in parallel if needed. While very large documents would take longer, the recovery operation is pretty efficient and recovery time should scale linearly. The main scaling issue with SSS is if you want to increase the quorum size -- most of the algorithms are at least quadratic with respect to the quorum size if not worse. If you implement it the way described in the original paper (using a prime field) then it mostly depends on the efficiency of the bignum library you are using -- though you probably want a bignum library that supports doing operations in a finite field because doing large multiplications and then calculating the modulus afterwards is a lot of wasted work and memory. I suspect Galios Fields are far more efficient at any size. For paperback's SSS implementation, I've written some preliminary benchmarks and it seems you can easily do secret recoveries at a rate of at least 75 KiB/s depending on the quorum size (32-person quorums are around 75 KiB/s while 5-person quorums can run as fast as 900 KiB/s). So, for reasonably-sized quorums you can easily have several-megabyte sized documents with sub-minute recovery times. Of course, doing AEAD and sharding the key is still much faster for larger documents (ChaCha20-Poly1305 can run at ~2GB/s on my machine according to "openssl speed"). But it's not necessary.
fartfeatures 3y ago
Is this different or do they do the exact same thing? https://github.com/paritytech/banana_split https://github.com/paritytech/banana_split
- cyphar 3y ago
  Paperback predates that tool (though to be fair, it still has to have a nice GUI interface made for it, and to be honest I have been working on it off more than on). Also, I suspect they don't support reconstructing lost shards or adding new shards after sharing (this is trivial to do from the maths but very few tools seem to have this pretty important feature). I talk about this in the LCA talk I did on paperback[1]. There are also some attacks against SSS that require workarounds and it seems to me they don't have any protections against them (in paperback's case, there are several measures to defend against forged shards -- one of which is that all shards are signed with an Ed25519 key whose private half is in the sharded secret). That being said, the underlying cryptography is quite old and there aren't too many new ways you can spin it -- the goal of paperback was to make it possible for paper backups to be done in a way that non-technical folks can understand the properties. How well it currently lives up to that goal is a different question, of course. I mainly wrote paperback because the existing SSS systems I could find at the time were all either very primitive, had serious security issues (I found two or three serious cryptographic vulnerabilities in the handful of existing tools at the time -- and I'm not a cryptographer by any stretch of the imagination), or were not usable as a paper backups system. There are more around now and it's possible I wouldn't have bothered with paperback if they'd existed back then. [1]: https://www.youtube.com/watch?v=GI9rKdM9rB8&t=1368 https://www.youtube.com/watch?v=GI9rKdM9rB8&t=1368
- elliotec 3y ago
  It’s the same but with a framework to share between people rather than just hiding pieces of paper around the world.
cyphar 3y ago
I really need to set aside some time to work on some kind of usable interface, graphical stuff has never been my strong suit. At the moment, all of the features work but you need to copy-paste the contents of the QR codes into the command-line. And I need to freeze the on-disk (on-paper?) format.

wilg 3y ago

This is very neat! Feels a bit too early to rely on it, but could be very cool for lots of people if it was a bit more mature and easy to use.

deleted 3y ago

[deleted]

EE84M3i 3y ago

Does SSS work well for large inputs, or do you need to AEAD the plaintext and then SSS the key?

cyphar 3y ago
Paperback uses the AEAD-and-SSS-the-key construction, but that's more to do with the properties such a scheme gives you (it allows more flexibility with how you distribute the secret -- you can keep the main document with a lawyer and distribute the shards so even if the shard holders betray you they don't have access to the original document). You also want to have protections against fake-shard attacks (which allow an attacker with a real shard to withhold the secret from others during recovery and then keep the recovery secret to themselves), and so you need to make use of traditional cryptography anyway by signing shards to detect fakes. To answer your question though, it primarily depends on the SSS construction and how big the quorum (number of shards needed for reconstruction, not the total number of shards created) is. Most constructions use Galios Fields and thus chunk the input and produce a new polynomial for each chunk -- the vast majority use GF(2^8) which means its per-byte. Paperback uses GF(2^32) to get 4-byte chunks so that the x-value used is more collision-resistant. I suspect for large documents GF(2^32) will be about 4x faster because Galois Field operations are very fast (which is why most tools use them over prime fields) but using 4-byte chunks reduces the number of operations needed by 4x. I considered going for GF(2^64) to get 8-byte chunks but doing so requires 128-bit integers in some operations. You can also process the chunks in parallel if needed. While very large documents would take longer, the recovery operation is pretty efficient and recovery time should scale linearly. The main scaling issue with SSS is if you want to increase the quorum size -- most of the algorithms are at least quadratic with respect to the quorum size if not worse. If you implement it the way described in the original paper (using a prime field) then it mostly depends on the efficiency of the bignum library you are using -- though you probably want a bignum library that supports doing operations in a finite field because doing large multiplications and then calculating the modulus afterwards is a lot of wasted work and memory. I suspect Galios Fields are far more efficient at any size. For paperback's SSS implementation, I've written some preliminary benchmarks and it seems you can easily do secret recoveries at a rate of at least 75 KiB/s depending on the quorum size (32-person quorums are around 75 KiB/s while 5-person quorums can run as fast as 900 KiB/s). So, for reasonably-sized quorums you can easily have several-megabyte sized documents with sub-minute recovery times. Of course, doing AEAD and sharding the key is still much faster for larger documents (ChaCha20-Poly1305 can run at ~2GB/s on my machine according to "openssl speed"). But it's not necessary.

fartfeatures 3y ago

Is this different or do they do the exact same thing? https://github.com/paritytech/banana_split https://github.com/paritytech/banana_split

cyphar 3y ago
Paperback predates that tool (though to be fair, it still has to have a nice GUI interface made for it, and to be honest I have been working on it off more than on). Also, I suspect they don't support reconstructing lost shards or adding new shards after sharing (this is trivial to do from the maths but very few tools seem to have this pretty important feature). I talk about this in the LCA talk I did on paperback[1]. There are also some attacks against SSS that require workarounds and it seems to me they don't have any protections against them (in paperback's case, there are several measures to defend against forged shards -- one of which is that all shards are signed with an Ed25519 key whose private half is in the sharded secret). That being said, the underlying cryptography is quite old and there aren't too many new ways you can spin it -- the goal of paperback was to make it possible for paper backups to be done in a way that non-technical folks can understand the properties. How well it currently lives up to that goal is a different question, of course. I mainly wrote paperback because the existing SSS systems I could find at the time were all either very primitive, had serious security issues (I found two or three serious cryptographic vulnerabilities in the handful of existing tools at the time -- and I'm not a cryptographer by any stretch of the imagination), or were not usable as a paper backups system. There are more around now and it's possible I wouldn't have bothered with paperback if they'd existed back then. [1]: https://www.youtube.com/watch?v=GI9rKdM9rB8&t=1368 https://www.youtube.com/watch?v=GI9rKdM9rB8&t=1368
elliotec 3y ago
It’s the same but with a framework to share between people rather than just hiding pieces of paper around the world.

cyphar 3y ago

I really need to set aside some time to work on some kind of usable interface, graphical stuff has never been my strong suit. At the moment, all of the features work but you need to copy-paste the contents of the QR codes into the command-line. And I need to freeze the on-disk (on-paper?) format.