8 ms·

Horcrux: Split your file into encrypted fragments

497 points by rgbrgb 3y ago

schnorrkel5519 3y ago
We also maintain a shamirs CLI called horcrux here: https://gitlab.com/unit410/horcrux https://gitlab.com/unit410/horcrux We decided to use Hashicorp vault's implementation of Shamirs which was the most widely used / battle tested golang implementation we could find.
pottermoreXprt6 3y ago
y'all are not understanding the underlying principle: these things work holographically. Dumbledore even said that copying the soul fades it, when Harry was inquiring and specifically pondered the maximum number of times the soul could be copied. †
- pottermoreXprt6 3y ago
  Needless to say calling this project Horcrux is just silly: it should be named after some other fictional story which requires all of the pieces to be assembled (like the new Starfield story I think). A Horcrux is like a fax facsimile and loses a lot of information. The entire point of the story was that the gang had to destroy ALL instances of the Horcrux, because He could be revived even with just one (holographic) copy.
- pottermoreXprt6 3y ago
  Tom asked somebody how many times the soul could be copied, too.
- pottermoreXprt6 3y ago
  Harry himself being the final Horcrux so he had to be temporarily killed to clear it out.
owenpalmer 3y ago
Clever name
- pottermoreXprt6 3y ago
  [flagged]
pottermoreXprt6 3y ago
Boo that's not what a Horcrux is!
coppsilgold 3y ago
According to the FAQ it uses a Shamir Secret Sharing Scheme to split an encryption key. But you can actually use a Reed-Solomon scheme[1] and have no encryption key to achieve this objective. First, you process the input data with an all-or-nothing transform (AONT)[2]. Then you split it into Reed-Solomon shares. AONT is required due to Reed-Solomon being vulnerable to a distinguisher[3] and it will most likely leak information about its input. [1] <https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...> [2] <https://en.wikipedia.org/wiki/All-or-nothing_transform https://en.wikipedia.org/wiki/All-or-nothing_transform> [3] <https://en.wikipedia.org/wiki/Distinguishing_attack https://en.wikipedia.org/wiki/Distinguishing_attack>
- cyphar 3y ago
  Is that approach information-theoretically secure? Shamir Secret Sharing is, and the mathematics is very simple. Note that the encryption step is, strictly speaking, not necessary for Shamir either. But there are benefits to encrypting the secret and only using SSS for the key (I'm not sure if that's how Horcrux works, but that's how my fairly-similar tool Paperback[1] works). [1]: https://github.com/cyphar/paperback https://github.com/cyphar/paperback
  - coppsilgold 3y ago
    > Is that approach information-theoretically secure? No. But neither is SSS if an encryption key is involved - because the symmetric encryption step is not information-theoretically secure. Using SSS directly on the input will be information-theoretically secure but also multiply the size of the input. > and the mathematics is very simple. The mathematics of SSS and Reed-Solomon are virtually identical.
- coppsilgold 3y ago
  I was able to find a project which appears to do exactly this: <https://github.com/atbarker/AONT-RS https://github.com/atbarker/AONT-RS> Paper: <https://www.usenix.org/legacy/event/fast11/tech/full_papers/Resch.pdf https://www.usenix.org/legacy/event/fast11/tech/full_papers/...>
Thorrez 3y ago
It would be nice if the FAQ said how big the split files would be. If you're doing it with 3 of 5, will the split files each be ~1/3 the size of the original file?
fieldbob 3y ago
isnt this how you hide malware on a machine?
manbitesdog 3y ago
Maybe it's too naïve of a question, but why not just using XORs? Let's say we have a file that we want to split into 4 encrypted shards. We could just generate 3 random files, and make the fourth one be a bitwise XOR of the 3 files plus the original one. Then, doing a bitwise XOR of the 4 encrypted shards will return the original file. Assuming the PRNGs are unbiased, how would this method not be safe enough?
- deleted 3y ago
  [deleted]
- manbitesdog 3y ago
  In case this method makes sense, I'm already registering the EXOrDIA name for a python package: https://github.com/juancroldan/exordia https://github.com/juancroldan/exordia
- Kharacternyk 3y ago
  With XOR you need all the shards to restore the file. With SSS you can lose a predefined number of shards and still restore the file with the other shards.
l1am0 3y ago
For easier use I build a shamir secret sharing based web tool :) https://simon-frey.com/s4 https://simon-frey.com/s4 p.S. In style of "don't do your own crypto" it uses hashicorps implementation of Shamir
38 3y ago
[flagged]
- Traubenfuchs 3y ago
  Why?
gopkarthik 3y ago
Fun repo that uses the Shamir Secret Sharing Scheme to break a file into parts which can be recombined to get the original. From the README Who this is for: People who need to encrypt a big sensitive file like a diary and don't expect to remember any passwords years from now (but who paradoxically will be capable of remembering where they've hidden their horcruxes) People who want to transmit files across multiple channels to substantially reduce the ability for an attacker to intercept FAQ Q) This isn't really in line with how horcruxes work in the harry potter universe! A) It's pretty close! You can't allow any one horcrux to be used to resurrect the original file (and why would you that would be useless) but you can allow two horcruxes to do it (so only off by one). Checkmate HP fans.
- deleted 3y ago
  [deleted]
- xpe 3y ago
  And for people who are confident that the some compatible horcrux tool is still available.
  - kuchenbecker 3y ago
    Store it with the files
LanternLight83 3y ago
Recently learned that Clevis also supports Shamir Secret Sharing, and it's in fact the only way to configure multiple pins even if they're of the same type and authority (ie. the RAID0 of SSS): https://github.com/latchset/clevis#pin-shamir-secret-sharing https://github.com/latchset/clevis#pin-shamir-secret-sharing
davidjhall 3y ago
I thought this was neat and went to his repo - he's the lazygit/lazy docker person! Nice to see the prolificacy!
mmastrac 3y ago
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.
pedrodelfino 3y ago
This is one of the most badass names for a project I have seen in a while!
- chongli 3y ago
  It's inaccurate though. The whole point of horcruxes in the book is that Voldemort can always resurrect himself if one of them remains. This tool is the opposite: you need multiple parts to reconstruct the file.
  - sanex 3y ago
    Yeah but that's just copy paste. This is more fun.
  - deleted 3y ago
    [deleted]
  - danielvaughn 3y ago
    Horcrux would be a cool name for a database backup service
    - pottermoreXprt6 3y ago
      No because a Horcrux is a nasty lossy copy that involves somebody's death to be made. Any wholesome leader who is also a HP fan would not appreciate the name tbh.
  - natch 3y ago
    They already acknowledged this in the faq fwiw.
    - chongli 3y ago
      They acknowledged it but dismissed it with an incorrect statement, and then declared victory with "checkmate HP fans" despite actually being wrong.
tonmoy 3y ago
My understanding of modern cryptography is limited. Can someone explain if someone gets my horcrux files, would they be able to decrypt the original? If so, then what is the benefit of this tool?
- usea 3y ago
  Hiding the fragments is like hiding your password. Of course they get the original if they have the fragments. That's the purpose. You could always encrypt the file before splitting it.
- uobytx2 3y ago
  Yeah, so this is best thought of as a backup tool in which the files are kept separately from each the, more than just a different way to encrypt a file. If you give a plaintext file to a friend for safe keeping, the friend can see the file. You could encrypt the file, but encrypting a file requires a key or password, which you could forget or lose. The idea here is: split the file into three parts. Give one part to the bank deposit box, one to a friend, and put one in a safe at home. Now, if you want to restore the original, nobody can restore without getting (for example) two of the three pieces. This is nice because your friend and the bank can’t do anything with their copies alone, and won’t trust each other with their copy normally. But if you lose your piece, you can still ask the friend and the bank for theirs.
- chaxor 3y ago
  I would imagine if you're worried you could just split the files with this, and of you think the encryption is 'weak' you could encrypt again with another tool. Probably not a bad idea.
Luc 3y ago
This brings to mind parity files on Usenet. Large archives would be uploaded split into smaller files and a number of parity files. You could then recreate the original archive using any (for example) n-3 out of n files. https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive
forty 3y ago
> Q) This isn't really in line with how horcruxes work in the harry potter universe! > A) It's pretty close! You can't allow any one horcrux to be used to resurrect the original file (and why would you that would be useless) but you can allow two horcruxes to do it (so only off by one). Checkmate HP fans. Well the whole point of hurcruxes is to have backup in several places. This tool to backup your backups in several places is a much better use of the name https://github.com/chrispoole643/horcrux https://github.com/chrispoole643/horcrux. Checkmate jesseduffield ;)
- sdwr 3y ago
  Yes, but no! Technically, horcruxes were backups, but the emotional weight of the concept came from splitting your soul, lessening your essence as you hedge against danger. Partial backups follow the spirit of the idea better. As an aside, I read the concept as an attack on promiscuity. "Whore crux". Contrast to Lord of the Rings' assault on marriage, where wearing the ring makes you invisible and slowly fade into nothingness, "like butter being scraped over too much bread".
  - johnchristopher 3y ago
    > Contrast to Lord of the Rings' assault on marriage, where wearing the ring makes you invisible and slowly fade into nothingness, "like butter being scraped over too much bread". Wait, what ? Eh...
    - tigerlily 3y ago
      Well, I think that's ostensible, as any reading of the author's biography can attest.
      - rndmwlk 3y ago
        I couldn't disagree more. You can easily twist his letters to his son to create this narrative. If you read it as a whole his message isn't at all anti-marriage, he was a devout Christian who believed wholeheartedly in marriage. His message was that marriage takes sacrifice, faith, and a conscious effort (in his opinion specifically on the side of the man). It's a bit Kierkegaardian.
natch 3y ago
>horcrux. Looks like somebody beat me to both the name and concept, however this repo doesn't support thresholds of horcruxes "this repo" I wonder if they mean "that repo." I realize it can be read both ways, but that is a bug, not a feature, in this readme. If the author is here can you please clarify?
tomasreimers 3y ago
There was a post about shamir secret sharing recently by levchin (and chaos that it caused at paypal): https://max.levch.in/post/724289457144070144/shamir-secret-sharing-its-3am-paul-the-head-of https://max.levch.in/post/724289457144070144/shamir-secret-s... This is 100% one of my favorite algorithms, but I have to say I've started to wonder if I just have an academic fascination with it and the practical use cases are more limited (limiting?) than I think
- j2kun 3y ago
  > I've started to wonder if I just have an academic fascination with it and the practical use cases are more limited (limiting?) than I think I'm currently writing an entire book based on this concern: pmfpbook.org
  - obeavs 3y ago
    And the answer is...
- UncleMeat 3y ago
  Shamir's Secret Sharing is basically perfect for nerdsniping. It is simple enough to understand without hardly any crypto background or advanced math. You basically just need a bit of algebra. It is surprising that it is possible at all. It has a clearly visible concrete use case (at least at first). It is something that you can implement yourself (though there are still footguns). This, IMO, leads to its wild overrepresentation in discussion forums and even overrepresentation in industry solutions.
- scubbo 3y ago
  Great story, thank you! > I've started to wonder if I just have an academic fascination with it and the practical use cases are more limited (limiting?) than I think I don't think the linked post should prompt such wondering? (It's not clear if you are drawing a causal link between the two) It was an issue with the interface _to_ the algorithm, not with the algorithm itself.
derefr 3y ago
I was just thinking about something like this problem. At $work, we use multi-signature signing to move cryptocurrency around, so that at least N of M officers of the company need to sign, to prove that "the company" actually intends a movement of funds to happen. This ensures that no single officer can embezzle funds; and it also ensures that an attacker would have to do some kind of multi-target simultaneous coordinated rubber-hose attack (rather than just waiting to kidnap one of us when we go on vacation) to get access to the funds. I was trying to think of a way to extend that kind of security to the encryption of data — specifically the encryption of low-level root-account passwords (like an AWS account's root password). Shamir's Secret Sharing is the obvious first step... but you'd also then want two additional properties: 1. the decrypted secret should not be held even temporarily by any of the parties, but rather should be held by — and used "through" — a neutral system, so that the secret is reusable rather than needing to be burned the first time it's revealed 2. the neutral system — despite being likely owned by a third party! — should have no ability to exfiltrate the password into the hands of the third party. I think this can be workable in the specific case of wanting to use the root password as an HMAC, by doing SSS decryption inside a single-shot non-durable abstract machine with homomorphically-encrypted memory, wrapped in a network daemon: the network daemon spins up a copy of the abstract machine; receives each SSS key split from its owner, feeding each as it receives it directly into the abstract machine; the abstract machine, after receiving sufficient key splits, signals to the daemon that it is now "empowered" to sign; and the daemon can then use the abstract machine to HMAC arbitrary plaintexts sent to it, until it exits, and the abstract machine's state is lost. The real trick, though, would be making this work for HTTP Basic Auth over TLS, by delegating the generation of exactly one TLS frame — the one containing the Authorization header — to the abstract machine; where the network daemon would then act as an HTTP proxy, inserting this Authentication header into requests made through it. Having something like this could really improve security around the use of a lot of sensitive control-plane APIs! --- Of course, in a corporate context, you probably have a third party you can trust with the plaintext — e.g. an Enterprise Password Manager service — so you can relax property 2. In such a case, you don't need a fancy abstract machine; you can just ask said service to build a feature allowing secrets to be configured to require N-of-M confirmations by ACLed team-members to unlock them; and to build another feature for "opaque secrets" that are never revealed to anyone, but instead are injected into an HTTP Authorization Proxy that the Enterprise Password Manager service spin up themselves on their backend. But it's still fun to think about the case where your secret is so secret that you need to hide the plaintext from literally everyone but your co-conspiriators. :)
harel 3y ago
This is broadly how StorJ works. I've used them before and it's a pretty cool storage solution (https://www.storj.io https://www.storj.io)
rraval 3y ago
No mention of libgfshare, which comes with utilities `gfsplit` and `gfcombine`: https://manpages.ubuntu.com/manpages/trusty/man1/gfsplit.1.html https://manpages.ubuntu.com/manpages/trusty/man1/gfsplit.1.h... We use it in production to pregenerate a pool of certificate requests for SSL key pinning. Rotating a key requires m-of-n cooperation.
mdip 3y ago
I can think of several ways to "take a password encrypted file and split it up in such a way that you can re-assemble it without all of its parts" but being able to do so without a password is where it's piqued my interest. This is one of those things that looks interesting to me as someone who enjoys security topics, algorithms and the like. I can see digging into the source code/reading about the techniques involved because I want to know how it was done. But I am struggling to figure out where something like this would be useful -- is there a threat model where this would be useful as a "layer in the onion" of things protecting sensitive data or a way in which this would be superior for a use case that isn't already solved better by something else? Even the author kind of jokes about an old diary password vs remembering enough hiding places. I think the latter would be a much bigger problem from personal experience and would require having fewer parts and more hiding places, eroding the provided security in the process[0]. :) Multi-sig comes to mind, but my only exposure to that is "having to participate in it" by "putting a USB key in and running a program along with two of my coworkers" in order to push the one update we ever pushed with that tooling. I remember we all had to provide our keys and "if I was out sick, no update was going out" but I'm not sure if that was a limitation of what we were using or if we just set them up that way because it was "alpha" at the time. None-the-less, very interesting! [0] I can imagine, though, that "under the mattress" would be the equivalent security to setting your password to "password".
- hmottestad 3y ago
  What about using it to share information with people for them to use in an emergency. Data is stored in multiple locations, but only someone with access to 3 of them would be able to read the data. The existing physical access controls would be the actual safety mechanism. A thief would have to break into 3 locations in order to get the data. We could just encrypt the data and then split the password into three pieces and store those in different locations, but then you would have to store both the data and the password.
  - mjevans 3y ago
    Step 1 : Create a compressed (must not 'store') archive split into small-ish sections of size N/K. Step 2 : Run par2 against the archive sections and create as much parity as possible. Step 3 : Distribute any middle (not the start of the archive, and not the incomplete end piece) segments of the archive and a 'correct' number of parity / recovery packets. If a complete count of the archive and parity pieces are brought together, par2 can recover the remaining pieces of the archive and extraction will be possible. The hashes only (no recovery data) par2 file should be distributed with all copies.
k__ 3y ago
Does this use a mix of striping with oarity and public key cryptography?
user8501 3y ago
Cool name
highwaylights 3y ago
Does anyone know of a tool like this that’s maintained? I actually would like to use this for a fairly out there use case but it hasn’t been updated in 3 years and it doesn’t look like the author has even been active on GitHub since that time.
- matthewtse 3y ago
  That was the problem for me too. There are many implementations of Shamir Secret Sharing out there, but they're all idiosyncratic and impossible to vet unless you have a background in cryptographic security, and like you said nearly all are not actively maintained. The types of things you would go to the trouble of Shamir Secret Sharing, are also the types of things that might surface decades later (e.g. crypto keys). Imagine going on a treasure hunt to retrieve 2 shards, and then needing to go on an additional internet archaeological hunt for the specific GitHub repository used to generate the shards. Unless someone solves this issue, I can't see Shamir Secret Sharing becoming any more mainstream.
  - d-z-m 3y ago
    The author of this tool basically took the Shamir code from Hashicorp Vault, which is pretty mainstream. If you're looking for a solid implementation, I would start there[0]. I wouldn't use the Shamir code from this repo, as it's an old version of the vault code using field arithmetic that doesn't run in constant time. [0]: https://github.com/hashicorp/vault/blob/main/shamir/shamir.go https://github.com/hashicorp/vault/blob/main/shamir/shamir.g...
marzell 3y ago
What's the practical benefit over just sharding a decryption key and handing out multiple shards to each person?
- armada651 3y ago
  1. You need all the shards of the key to decrypt the text instead of just reaching a threshold. 2. The full encrypted text is available to each person, making it vulnerable to a brute force attack at some point in the far future. I'm not entirely sure if this implementation actually covers that second point though. It could be including the entire encrypted text with each copy. But it would theoretically be possible to protect against brute force attacks in that way.
  - marzell 3y ago
    The second point, yeah that's relevant. On the first point, just give each person n-1 shards, each missing a different one. Then any 2 can decrypt. Or configure it for however many participants there are and they minimum number needed to encrypt.
    - d-z-m 3y ago
      The key part about Shamir is that having any number of shards short of the threshold doesn't reveal anything about the secret. Let's say you split your 256 bit encryption key into 4 64-bit pieces with each person getting 3 of the 4. Each person now knows 3/4 of the secret. Now any one person simply has to brute force the remaining 64 bits of the key in order to decrypt.
ubj 3y ago
Very cool! Now what would be really interesting is combining this with steganography techniques to hide the horcrux fragments inside totally unrelated-looking files.
- alchemist1e9 3y ago
  That would be neat. A printed set of family pictures for example. Digital steganography is well known but I’ve never personal come across tools for physical images, however I guess I haven’t ever looked.
skylar10 3y ago
[flagged]
skylar10 3y ago
[flagged]
- pjerem 3y ago
  i’m totally a hacker, i hack things
skylar10 3y ago
I was just thinking about something like this problem. At $work, we use multi-signature signing to move cryptocurrency around, so that at least N of M officers of the company need to sign, to prove that "the company" actually intends a movement of funds to happen. This ensures that no single officer can embezzle funds; and it also ensures that an attacker would have to do some kind of multi-target simultaneous coordinated rubber-hose attack (rather than just waiting to kidnap one of us when we go on vacation) to get access to the funds. I was trying to think of a way to extend that kind of security to the encryption of data — specifically the encryption of low-level root-account passwords (like an AWS account's root password). Shamir's Secret Sharing is the obvious first step... but you'd also then want two additional properties: 1. the decrypted secret should not be held even temporarily by any of the parties, but rather should be held by — and used "through" — a neutral system, so that the secret is reusable rather than needing to be burned the first time it's revealed 2. the neutral system — despite being likely owned by a third party! — should have no ability to exfiltrate the password into the hands of the third party. I think this can be workable in the specific case of wanting to use the root password as an HMAC, by doing SSS decryption inside a single-shot non-durable abstract machine with homomorphically-encrypted memory, wrapped in a network daemon: the network daemon spins up a copy of the abstract machine; receives each SSS key split from its owner, feeding each as it receives it directly into the abstract machine; the abstract machine, after receiving sufficient key splits, signals to the daemon that it is now "empowered" to sign; and the daemon can then use the abstract machine to HMAC arbitrary plaintexts sent to it, until it exits, and the abstract machine's state is lost. The real trick, though, would be making this work for HTTP Basic Auth over TLS, by delegating the generation of exactly one TLS frame — the one containing the Authorization header — to the abstract machine; where the network daemon would then act as an HTTP proxy, inserting this Authentication header into requests made through it. Having something like this could really improve security around the use of a lot of sensitive control-plane APIs! --- Of course, in a corporate context, you probably have a third party you can trust with the plaintext — e.g. an Enterprise Password Manager service — so you can relax property 2. In such a case, you don't need a fancy abstract machine; you can just ask said service to build a feature allowing secrets to be configured to require N-of-M confirmations by ACLed team-members to unlock them; and to build another feature for "opaque secrets" that are never revealed to anyone, but instead are injected into an HTTP Authorization Proxy that the Enterprise Password Manager service spin up themselves on their backend. But it's still fun to think about the case where your secret is so secret that you need to hide the plaintext from literally everyone but your co-conspiriators,
akomtu 3y ago
No idea what algorithm it uses, but if you want to be fancy, pass each fragment of the encrypted file thru a DFT, and save each k-th frequency into a separate file. Such a file will appear as an image with a curious pattern, or an audio file, so if anyone asks, that "4 wav" is music. What's interesting is that 1.wav and 2.wav (and other k.wav) will be nearly identical, so they can be put together into a 7.1ch audio stream (if splitting into 8 pieces). Bonus points: apply flac encoding on top.
franky47 3y ago
Since we're sharing implementations, here's mine: https://francoisbest.com/horcrux https://francoisbest.com/horcrux
- deleted 3y ago
  [deleted]
- sowbug 3y ago
  And here's mine: https://github.com/sowbug/b39tools https://github.com/sowbug/b39tools This is specifically for an SSSS-based distributed physical backup of a BIP-39 wallet seed and passphrase.
  - fragmede 3y ago
    Not mine, but http://point-at-infinity.org/ssss/ http://point-at-infinity.org/ssss/ is another good one, with Debian packages.
tanepiper 3y ago
Huh I threw together something like this a few weeks ago using asymmetric keys - pass a file and key and it output as smaller encrypted files. Only way to decrypt them - have all the files and the key. Didn't think it was that useful but seems similar to the functionality, but I like that you don't need to share a key here.
- conradludgate 3y ago
  The difference here is that with Shamir secret sharing, each file also has a portion of the key and you only need a subset of the files to decrypt. In the example in the readme you can decrypt with at least 3 parts. This means you can lose 2 and still decrypt
Obscurity4340 3y ago
Literally made this comment and been surprised with the notion of Shamir Secret Sharing! Check my comments
fredliu 3y ago
Isn't fountain code doing something similar? Albeit for slightly different purpose?
d-z-m 3y ago
Caution, this tool uses AES in OFB mode[0] to encrypt/decrypt the file, without any guarantee of the ciphertext integrity(no MAC). [0]: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Output_feedback_(OFB) https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation...
- byteknight 3y ago
  That wiki went over my (fairly) technical head. Care to ELI5?
  - msm_ 3y ago
    My attempt of explanation with a (hopefully) relatable example: imagine that you store all your backup files encrypted, then restore the backup on your machine. The backup is stored on untrusted NAS but it's OK since it's encrypted, right? With OFB (and CTR, and any other unauthenticated cipher basically), no. Ciphers guarantee confidentiality, but nothing else. This means that the attacker can alter one of your encrypted backed-up files. It's not a hypothetical attack. For example your backed up /bin/ls file likely starts with something like (hexencoded): 7f454c4602010100000000000000000002003e000100 .ELF..............>... Let's assume attacker wants to trick you into running "echo hacked" on your system. They may achieve this by altering your backed up /bin/ls such that it decrypts to something like this: 23212f62696e2f73680a6563686f206861636b65640a #!/bin/sh\necho hacked\n And it's really easy! Stream ciphers work by XORing input plaintext with keystream: ciphertext = plaintext ^ generate_keystream(key) plaintext = ciphertext ^ generate_keystream(key) If you look closely at the equations, it's apparent that one can flip a byte in decrypted plaintext by flipping a byte in the ciphertext. To drive the point home, a small demonstration in Python (I'll use CTR instead of OFB but it's the same): >>> from Crypto.Cipher import AES >>> def xor(a, b): return bytes([ac ^ bc for ac, bc in zip(a, b)]) >>> aes_enc = AES.new(b"mysupersecretkey", AES.MODE_CTR) >>> plaintext = open("/bin/ls", "rb").read(32) >>> ciphertext = aes_enc.encrypt(plaintext) >>> known_plaintext = bytes.fromhex("7f454c4602010100000000000000000002003e000100") >>> wanted_plaintext =bytes.fromhex("23212f62696e2f73680a6563686f206861636b65640a") >>> flip = xor(known_plaintext, wanted_plaintext) >>> flipped_ciphertext = xor(flip, ciphertext) >>> aes_dec = AES.new(b"mysupersecretkey", AES.MODE_CTR, nonce=aes_enc.nonce) >>> aes_dec.decrypt(flipped_ciphertext) b'#!/bin/sh\necho hacked\n\\d\xc3\xd9\*o.sh\n' In this example attacker can change the first 22 bytes of file to arbitrary payload by abusing the predictable header of the ELF file. No knowledge of the key is necessary.
IndigoIncognito 3y ago
Someone check this mans hard drive
dang 3y ago
Related (at least by name - I think there is more than one project here). Others? Horcrux: Split your file into encrypted fragments - https://news.ycombinator.com/item?id=29395575 https://news.ycombinator.com/item?id=29395575 - Nov 2021 (11 comments) Show HN: Horcrux, a Playground for Shamir Secret Sharing - https://news.ycombinator.com/item?id=26256726 https://news.ycombinator.com/item?id=26256726 - Feb 2021 (40 comments) Horcrux Encrypted Messaging - https://news.ycombinator.com/item?id=24322069 https://news.ycombinator.com/item?id=24322069 - Aug 2020 (93 comments) I made an app that lets you split a file into horcruxes - https://news.ycombinator.com/item?id=24026445 https://news.ycombinator.com/item?id=24026445 - Aug 2020 (80 comments) You can now make horcruxes out of your confidential files - https://news.ycombinator.com/item?id=21933983 https://news.ycombinator.com/item?id=21933983 - Jan 2020 (17 comments)
eightysixfour 3y ago
I have always wanted a cloud storage client which spread my files in chunks out among OneDrive, GDrive, etc. Essentially cloud raid to make it harder to put things back together.
- seigel 3y ago
  You and me both!!! If you ever find that, please remember this and point me to it as well. My thoughts were: use all the free capacity of the drives you mentioned to make a filesystem like HDFS which distributes blocks all over the place.. :)
zamadatix 3y ago
The note on not being able to allow only one horcrux to resurrect the original file feels unintuitive. I mean I get it'd be a pretty useless thing to do (as you'd effectively have just used an extremely complicated method of copying a file in a way it could still be read by anyone who gets a copy) but it seems odd you couldn't actually do it.
Mistletoe 3y ago
The name alone guarantees this program will live on. Sometimes I think a good name is 50-80% of the success of a product or person.
Levitating 3y ago
This is called Shamir's Secret Sharing and I once found this interesting guide for implementing it in Rust: https://gendignoux.com/blog/2021/11/01/horcrux-1-math.html https://gendignoux.com/blog/2021/11/01/horcrux-1-math.html

497 points by rgbrgb 3y ago

We also maintain a shamirs CLI called horcrux here: https://gitlab.com/unit410/horcrux https://gitlab.com/unit410/horcrux We decided to use Hashicorp vault's implementation of Shamirs which was the most widely used / battle tested golang implementation we could find.

pottermoreXprt6 3y ago

y'all are not understanding the underlying principle: these things work holographically. Dumbledore even said that copying the soul fades it, when Harry was inquiring and specifically pondered the maximum number of times the soul could be copied. †

pottermoreXprt6 3y ago
Needless to say calling this project Horcrux is just silly: it should be named after some other fictional story which requires all of the pieces to be assembled (like the new Starfield story I think). A Horcrux is like a fax facsimile and loses a lot of information. The entire point of the story was that the gang had to destroy ALL instances of the Horcrux, because He could be revived even with just one (holographic) copy.
pottermoreXprt6 3y ago
Tom asked somebody how many times the soul could be copied, too.
pottermoreXprt6 3y ago
Harry himself being the final Horcrux so he had to be temporarily killed to clear it out.

owenpalmer 3y ago

Clever name

pottermoreXprt6 3y ago
[flagged]

pottermoreXprt6 3y ago

Boo that's not what a Horcrux is!

coppsilgold 3y ago

According to the FAQ it uses a Shamir Secret Sharing Scheme to split an encryption key. But you can actually use a Reed-Solomon scheme[1] and have no encryption key to achieve this objective. First, you process the input data with an all-or-nothing transform (AONT)[2]. Then you split it into Reed-Solomon shares. AONT is required due to Reed-Solomon being vulnerable to a distinguisher[3] and it will most likely leak information about its input. [1] <https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...> [2] <https://en.wikipedia.org/wiki/All-or-nothing_transform https://en.wikipedia.org/wiki/All-or-nothing_transform> [3] <https://en.wikipedia.org/wiki/Distinguishing_attack https://en.wikipedia.org/wiki/Distinguishing_attack>

cyphar 3y ago
Is that approach information-theoretically secure? Shamir Secret Sharing is, and the mathematics is very simple. Note that the encryption step is, strictly speaking, not necessary for Shamir either. But there are benefits to encrypting the secret and only using SSS for the key (I'm not sure if that's how Horcrux works, but that's how my fairly-similar tool Paperback[1] works). [1]: https://github.com/cyphar/paperback https://github.com/cyphar/paperback
- coppsilgold 3y ago
  > Is that approach information-theoretically secure? No. But neither is SSS if an encryption key is involved - because the symmetric encryption step is not information-theoretically secure. Using SSS directly on the input will be information-theoretically secure but also multiply the size of the input. > and the mathematics is very simple. The mathematics of SSS and Reed-Solomon are virtually identical.
coppsilgold 3y ago
I was able to find a project which appears to do exactly this: <https://github.com/atbarker/AONT-RS https://github.com/atbarker/AONT-RS> Paper: <https://www.usenix.org/legacy/event/fast11/tech/full_papers/Resch.pdf https://www.usenix.org/legacy/event/fast11/tech/full_papers/...>

Thorrez 3y ago

It would be nice if the FAQ said how big the split files would be. If you're doing it with 3 of 5, will the split files each be ~1/3 the size of the original file?

fieldbob 3y ago

isnt this how you hide malware on a machine?

manbitesdog 3y ago

Maybe it's too naïve of a question, but why not just using XORs? Let's say we have a file that we want to split into 4 encrypted shards. We could just generate 3 random files, and make the fourth one be a bitwise XOR of the 3 files plus the original one. Then, doing a bitwise XOR of the 4 encrypted shards will return the original file. Assuming the PRNGs are unbiased, how would this method not be safe enough?

deleted 3y ago
[deleted]
manbitesdog 3y ago
In case this method makes sense, I'm already registering the EXOrDIA name for a python package: https://github.com/juancroldan/exordia https://github.com/juancroldan/exordia
Kharacternyk 3y ago
With XOR you need all the shards to restore the file. With SSS you can lose a predefined number of shards and still restore the file with the other shards.

l1am0 3y ago

For easier use I build a shamir secret sharing based web tool :) https://simon-frey.com/s4 https://simon-frey.com/s4 p.S. In style of "don't do your own crypto" it uses hashicorps implementation of Shamir

38 3y ago

[flagged]

Traubenfuchs 3y ago
Why?

gopkarthik 3y ago

Fun repo that uses the Shamir Secret Sharing Scheme to break a file into parts which can be recombined to get the original. From the README Who this is for: People who need to encrypt a big sensitive file like a diary and don't expect to remember any passwords years from now (but who paradoxically will be capable of remembering where they've hidden their horcruxes) People who want to transmit files across multiple channels to substantially reduce the ability for an attacker to intercept FAQ Q) This isn't really in line with how horcruxes work in the harry potter universe! A) It's pretty close! You can't allow any one horcrux to be used to resurrect the original file (and why would you that would be useless) but you can allow two horcruxes to do it (so only off by one). Checkmate HP fans.

deleted 3y ago
[deleted]
xpe 3y ago
And for people who are confident that the some compatible horcrux tool is still available.
- kuchenbecker 3y ago
  Store it with the files

LanternLight83 3y ago

Recently learned that Clevis also supports Shamir Secret Sharing, and it's in fact the only way to configure multiple pins even if they're of the same type and authority (ie. the RAID0 of SSS): https://github.com/latchset/clevis#pin-shamir-secret-sharing https://github.com/latchset/clevis#pin-shamir-secret-sharing

davidjhall 3y ago

I thought this was neat and went to his repo - he's the lazygit/lazy docker person! Nice to see the prolificacy!

mmastrac 3y ago

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.

pedrodelfino 3y ago

This is one of the most badass names for a project I have seen in a while!

chongli 3y ago
It's inaccurate though. The whole point of horcruxes in the book is that Voldemort can always resurrect himself if one of them remains. This tool is the opposite: you need multiple parts to reconstruct the file.
- sanex 3y ago
  Yeah but that's just copy paste. This is more fun.
- deleted 3y ago
  [deleted]
- danielvaughn 3y ago
  Horcrux would be a cool name for a database backup service
  - pottermoreXprt6 3y ago
    No because a Horcrux is a nasty lossy copy that involves somebody's death to be made. Any wholesome leader who is also a HP fan would not appreciate the name tbh.
- natch 3y ago
  They already acknowledged this in the faq fwiw.
  - chongli 3y ago
    They acknowledged it but dismissed it with an incorrect statement, and then declared victory with "checkmate HP fans" despite actually being wrong.

tonmoy 3y ago

My understanding of modern cryptography is limited. Can someone explain if someone gets my horcrux files, would they be able to decrypt the original? If so, then what is the benefit of this tool?

usea 3y ago
Hiding the fragments is like hiding your password. Of course they get the original if they have the fragments. That's the purpose. You could always encrypt the file before splitting it.
uobytx2 3y ago
Yeah, so this is best thought of as a backup tool in which the files are kept separately from each the, more than just a different way to encrypt a file. If you give a plaintext file to a friend for safe keeping, the friend can see the file. You could encrypt the file, but encrypting a file requires a key or password, which you could forget or lose. The idea here is: split the file into three parts. Give one part to the bank deposit box, one to a friend, and put one in a safe at home. Now, if you want to restore the original, nobody can restore without getting (for example) two of the three pieces. This is nice because your friend and the bank can’t do anything with their copies alone, and won’t trust each other with their copy normally. But if you lose your piece, you can still ask the friend and the bank for theirs.
chaxor 3y ago
I would imagine if you're worried you could just split the files with this, and of you think the encryption is 'weak' you could encrypt again with another tool. Probably not a bad idea.

Luc 3y ago

This brings to mind parity files on Usenet. Large archives would be uploaded split into smaller files and a number of parity files. You could then recreate the original archive using any (for example) n-3 out of n files. https://en.wikipedia.org/wiki/Parchive https://en.wikipedia.org/wiki/Parchive

forty 3y ago

> Q) This isn't really in line with how horcruxes work in the harry potter universe! > A) It's pretty close! You can't allow any one horcrux to be used to resurrect the original file (and why would you that would be useless) but you can allow two horcruxes to do it (so only off by one). Checkmate HP fans. Well the whole point of hurcruxes is to have backup in several places. This tool to backup your backups in several places is a much better use of the name https://github.com/chrispoole643/horcrux https://github.com/chrispoole643/horcrux. Checkmate jesseduffield ;)

sdwr 3y ago
Yes, but no! Technically, horcruxes were backups, but the emotional weight of the concept came from splitting your soul, lessening your essence as you hedge against danger. Partial backups follow the spirit of the idea better. As an aside, I read the concept as an attack on promiscuity. "Whore crux". Contrast to Lord of the Rings' assault on marriage, where wearing the ring makes you invisible and slowly fade into nothingness, "like butter being scraped over too much bread".
- johnchristopher 3y ago
  > Contrast to Lord of the Rings' assault on marriage, where wearing the ring makes you invisible and slowly fade into nothingness, "like butter being scraped over too much bread". Wait, what ? Eh...
  - tigerlily 3y ago
    Well, I think that's ostensible, as any reading of the author's biography can attest.
    - rndmwlk 3y ago
      I couldn't disagree more. You can easily twist his letters to his son to create this narrative. If you read it as a whole his message isn't at all anti-marriage, he was a devout Christian who believed wholeheartedly in marriage. His message was that marriage takes sacrifice, faith, and a conscious effort (in his opinion specifically on the side of the man). It's a bit Kierkegaardian.

natch 3y ago

>horcrux. Looks like somebody beat me to both the name and concept, however this repo doesn't support thresholds of horcruxes "this repo" I wonder if they mean "that repo." I realize it can be read both ways, but that is a bug, not a feature, in this readme. If the author is here can you please clarify?

tomasreimers 3y ago

There was a post about shamir secret sharing recently by levchin (and chaos that it caused at paypal): https://max.levch.in/post/724289457144070144/shamir-secret-sharing-its-3am-paul-the-head-of https://max.levch.in/post/724289457144070144/shamir-secret-s... This is 100% one of my favorite algorithms, but I have to say I've started to wonder if I just have an academic fascination with it and the practical use cases are more limited (limiting?) than I think

j2kun 3y ago
> I've started to wonder if I just have an academic fascination with it and the practical use cases are more limited (limiting?) than I think I'm currently writing an entire book based on this concern: pmfpbook.org
- obeavs 3y ago
  And the answer is...
UncleMeat 3y ago
Shamir's Secret Sharing is basically perfect for nerdsniping. It is simple enough to understand without hardly any crypto background or advanced math. You basically just need a bit of algebra. It is surprising that it is possible at all. It has a clearly visible concrete use case (at least at first). It is something that you can implement yourself (though there are still footguns). This, IMO, leads to its wild overrepresentation in discussion forums and even overrepresentation in industry solutions.
scubbo 3y ago
Great story, thank you! > I've started to wonder if I just have an academic fascination with it and the practical use cases are more limited (limiting?) than I think I don't think the linked post should prompt such wondering? (It's not clear if you are drawing a causal link between the two) It was an issue with the interface _to_ the algorithm, not with the algorithm itself.

derefr 3y ago

I was just thinking about something like this problem. At $work, we use multi-signature signing to move cryptocurrency around, so that at least N of M officers of the company need to sign, to prove that "the company" actually intends a movement of funds to happen. This ensures that no single officer can embezzle funds; and it also ensures that an attacker would have to do some kind of multi-target simultaneous coordinated rubber-hose attack (rather than just waiting to kidnap one of us when we go on vacation) to get access to the funds. I was trying to think of a way to extend that kind of security to the encryption of data — specifically the encryption of low-level root-account passwords (like an AWS account's root password). Shamir's Secret Sharing is the obvious first step... but you'd also then want two additional properties: 1. the decrypted secret should not be held even temporarily by any of the parties, but rather should be held by — and used "through" — a neutral system, so that the secret is reusable rather than needing to be burned the first time it's revealed 2. the neutral system — despite being likely owned by a third party! — should have no ability to exfiltrate the password into the hands of the third party. I think this can be workable in the specific case of wanting to use the root password as an HMAC, by doing SSS decryption inside a single-shot non-durable abstract machine with homomorphically-encrypted memory, wrapped in a network daemon: the network daemon spins up a copy of the abstract machine; receives each SSS key split from its owner, feeding each as it receives it directly into the abstract machine; the abstract machine, after receiving sufficient key splits, signals to the daemon that it is now "empowered" to sign; and the daemon can then use the abstract machine to HMAC arbitrary plaintexts sent to it, until it exits, and the abstract machine's state is lost. The real trick, though, would be making this work for HTTP Basic Auth over TLS, by delegating the generation of exactly one TLS frame — the one containing the Authorization header — to the abstract machine; where the network daemon would then act as an HTTP proxy, inserting this Authentication header into requests made through it. Having something like this could really improve security around the use of a lot of sensitive control-plane APIs! --- Of course, in a corporate context, you probably have a third party you can trust with the plaintext — e.g. an Enterprise Password Manager service — so you can relax property 2. In such a case, you don't need a fancy abstract machine; you can just ask said service to build a feature allowing secrets to be configured to require N-of-M confirmations by ACLed team-members to unlock them; and to build another feature for "opaque secrets" that are never revealed to anyone, but instead are injected into an HTTP Authorization Proxy that the Enterprise Password Manager service spin up themselves on their backend. But it's still fun to think about the case where your secret is so secret that you need to hide the plaintext from literally everyone but your co-conspiriators. :)

harel 3y ago

This is broadly how StorJ works. I've used them before and it's a pretty cool storage solution (https://www.storj.io https://www.storj.io)

rraval 3y ago

No mention of libgfshare, which comes with utilities `gfsplit` and `gfcombine`: https://manpages.ubuntu.com/manpages/trusty/man1/gfsplit.1.html https://manpages.ubuntu.com/manpages/trusty/man1/gfsplit.1.h... We use it in production to pregenerate a pool of certificate requests for SSL key pinning. Rotating a key requires m-of-n cooperation.

mdip 3y ago

I can think of several ways to "take a password encrypted file and split it up in such a way that you can re-assemble it without all of its parts" but being able to do so without a password is where it's piqued my interest. This is one of those things that looks interesting to me as someone who enjoys security topics, algorithms and the like. I can see digging into the source code/reading about the techniques involved because I want to know how it was done. But I am struggling to figure out where something like this would be useful -- is there a threat model where this would be useful as a "layer in the onion" of things protecting sensitive data or a way in which this would be superior for a use case that isn't already solved better by something else? Even the author kind of jokes about an old diary password vs remembering enough hiding places. I think the latter would be a much bigger problem from personal experience and would require having fewer parts and more hiding places, eroding the provided security in the process[0]. :) Multi-sig comes to mind, but my only exposure to that is "having to participate in it" by "putting a USB key in and running a program along with two of my coworkers" in order to push the one update we ever pushed with that tooling. I remember we all had to provide our keys and "if I was out sick, no update was going out" but I'm not sure if that was a limitation of what we were using or if we just set them up that way because it was "alpha" at the time. None-the-less, very interesting! [0] I can imagine, though, that "under the mattress" would be the equivalent security to setting your password to "password".

hmottestad 3y ago
What about using it to share information with people for them to use in an emergency. Data is stored in multiple locations, but only someone with access to 3 of them would be able to read the data. The existing physical access controls would be the actual safety mechanism. A thief would have to break into 3 locations in order to get the data. We could just encrypt the data and then split the password into three pieces and store those in different locations, but then you would have to store both the data and the password.
- mjevans 3y ago
  Step 1 : Create a compressed (must not 'store') archive split into small-ish sections of size N/K. Step 2 : Run par2 against the archive sections and create as much parity as possible. Step 3 : Distribute any middle (not the start of the archive, and not the incomplete end piece) segments of the archive and a 'correct' number of parity / recovery packets. If a complete count of the archive and parity pieces are brought together, par2 can recover the remaining pieces of the archive and extraction will be possible. The hashes only (no recovery data) par2 file should be distributed with all copies.

k__ 3y ago

Does this use a mix of striping with oarity and public key cryptography?

user8501 3y ago

Cool name

highwaylights 3y ago

Does anyone know of a tool like this that’s maintained? I actually would like to use this for a fairly out there use case but it hasn’t been updated in 3 years and it doesn’t look like the author has even been active on GitHub since that time.

matthewtse 3y ago
That was the problem for me too. There are many implementations of Shamir Secret Sharing out there, but they're all idiosyncratic and impossible to vet unless you have a background in cryptographic security, and like you said nearly all are not actively maintained. The types of things you would go to the trouble of Shamir Secret Sharing, are also the types of things that might surface decades later (e.g. crypto keys). Imagine going on a treasure hunt to retrieve 2 shards, and then needing to go on an additional internet archaeological hunt for the specific GitHub repository used to generate the shards. Unless someone solves this issue, I can't see Shamir Secret Sharing becoming any more mainstream.
- d-z-m 3y ago
  The author of this tool basically took the Shamir code from Hashicorp Vault, which is pretty mainstream. If you're looking for a solid implementation, I would start there[0]. I wouldn't use the Shamir code from this repo, as it's an old version of the vault code using field arithmetic that doesn't run in constant time. [0]: https://github.com/hashicorp/vault/blob/main/shamir/shamir.go https://github.com/hashicorp/vault/blob/main/shamir/shamir.g...

marzell 3y ago

What's the practical benefit over just sharding a decryption key and handing out multiple shards to each person?

armada651 3y ago
1. You need all the shards of the key to decrypt the text instead of just reaching a threshold. 2. The full encrypted text is available to each person, making it vulnerable to a brute force attack at some point in the far future. I'm not entirely sure if this implementation actually covers that second point though. It could be including the entire encrypted text with each copy. But it would theoretically be possible to protect against brute force attacks in that way.
- marzell 3y ago
  The second point, yeah that's relevant. On the first point, just give each person n-1 shards, each missing a different one. Then any 2 can decrypt. Or configure it for however many participants there are and they minimum number needed to encrypt.
  - d-z-m 3y ago
    The key part about Shamir is that having any number of shards short of the threshold doesn't reveal anything about the secret. Let's say you split your 256 bit encryption key into 4 64-bit pieces with each person getting 3 of the 4. Each person now knows 3/4 of the secret. Now any one person simply has to brute force the remaining 64 bits of the key in order to decrypt.

ubj 3y ago

Very cool! Now what would be really interesting is combining this with steganography techniques to hide the horcrux fragments inside totally unrelated-looking files.

alchemist1e9 3y ago
That would be neat. A printed set of family pictures for example. Digital steganography is well known but I’ve never personal come across tools for physical images, however I guess I haven’t ever looked.

skylar10 3y ago

[flagged]

skylar10 3y ago

[flagged]

pjerem 3y ago
i’m totally a hacker, i hack things

skylar10 3y ago

akomtu 3y ago

No idea what algorithm it uses, but if you want to be fancy, pass each fragment of the encrypted file thru a DFT, and save each k-th frequency into a separate file. Such a file will appear as an image with a curious pattern, or an audio file, so if anyone asks, that "4 wav" is music. What's interesting is that 1.wav and 2.wav (and other k.wav) will be nearly identical, so they can be put together into a 7.1ch audio stream (if splitting into 8 pieces). Bonus points: apply flac encoding on top.

franky47 3y ago

Since we're sharing implementations, here's mine: https://francoisbest.com/horcrux https://francoisbest.com/horcrux

deleted 3y ago
[deleted]
sowbug 3y ago
And here's mine: https://github.com/sowbug/b39tools https://github.com/sowbug/b39tools This is specifically for an SSSS-based distributed physical backup of a BIP-39 wallet seed and passphrase.
- fragmede 3y ago
  Not mine, but http://point-at-infinity.org/ssss/ http://point-at-infinity.org/ssss/ is another good one, with Debian packages.

tanepiper 3y ago

Huh I threw together something like this a few weeks ago using asymmetric keys - pass a file and key and it output as smaller encrypted files. Only way to decrypt them - have all the files and the key. Didn't think it was that useful but seems similar to the functionality, but I like that you don't need to share a key here.

conradludgate 3y ago
The difference here is that with Shamir secret sharing, each file also has a portion of the key and you only need a subset of the files to decrypt. In the example in the readme you can decrypt with at least 3 parts. This means you can lose 2 and still decrypt

Obscurity4340 3y ago

Literally made this comment and been surprised with the notion of Shamir Secret Sharing! Check my comments

fredliu 3y ago

Isn't fountain code doing something similar? Albeit for slightly different purpose?

d-z-m 3y ago

Caution, this tool uses AES in OFB mode[0] to encrypt/decrypt the file, without any guarantee of the ciphertext integrity(no MAC). [0]: https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Output_feedback_(OFB) https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation...

byteknight 3y ago
That wiki went over my (fairly) technical head. Care to ELI5?
- msm_ 3y ago
  My attempt of explanation with a (hopefully) relatable example: imagine that you store all your backup files encrypted, then restore the backup on your machine. The backup is stored on untrusted NAS but it's OK since it's encrypted, right? With OFB (and CTR, and any other unauthenticated cipher basically), no. Ciphers guarantee confidentiality, but nothing else. This means that the attacker can alter one of your encrypted backed-up files. It's not a hypothetical attack. For example your backed up /bin/ls file likely starts with something like (hexencoded): 7f454c4602010100000000000000000002003e000100 .ELF..............>... Let's assume attacker wants to trick you into running "echo hacked" on your system. They may achieve this by altering your backed up /bin/ls such that it decrypts to something like this: 23212f62696e2f73680a6563686f206861636b65640a #!/bin/sh\necho hacked\n And it's really easy! Stream ciphers work by XORing input plaintext with keystream: ciphertext = plaintext ^ generate_keystream(key) plaintext = ciphertext ^ generate_keystream(key) If you look closely at the equations, it's apparent that one can flip a byte in decrypted plaintext by flipping a byte in the ciphertext. To drive the point home, a small demonstration in Python (I'll use CTR instead of OFB but it's the same): >>> from Crypto.Cipher import AES >>> def xor(a, b): return bytes([ac ^ bc for ac, bc in zip(a, b)]) >>> aes_enc = AES.new(b"mysupersecretkey", AES.MODE_CTR) >>> plaintext = open("/bin/ls", "rb").read(32) >>> ciphertext = aes_enc.encrypt(plaintext) >>> known_plaintext = bytes.fromhex("7f454c4602010100000000000000000002003e000100") >>> wanted_plaintext =bytes.fromhex("23212f62696e2f73680a6563686f206861636b65640a") >>> flip = xor(known_plaintext, wanted_plaintext) >>> flipped_ciphertext = xor(flip, ciphertext) >>> aes_dec = AES.new(b"mysupersecretkey", AES.MODE_CTR, nonce=aes_enc.nonce) >>> aes_dec.decrypt(flipped_ciphertext) b'#!/bin/sh\necho hacked\n\\d\xc3\xd9\*o.sh\n' In this example attacker can change the first 22 bytes of file to arbitrary payload by abusing the predictable header of the ELF file. No knowledge of the key is necessary.

IndigoIncognito 3y ago

Someone check this mans hard drive

dang 3y ago

Related (at least by name - I think there is more than one project here). Others? Horcrux: Split your file into encrypted fragments - https://news.ycombinator.com/item?id=29395575 https://news.ycombinator.com/item?id=29395575 - Nov 2021 (11 comments) Show HN: Horcrux, a Playground for Shamir Secret Sharing - https://news.ycombinator.com/item?id=26256726 https://news.ycombinator.com/item?id=26256726 - Feb 2021 (40 comments) Horcrux Encrypted Messaging - https://news.ycombinator.com/item?id=24322069 https://news.ycombinator.com/item?id=24322069 - Aug 2020 (93 comments) I made an app that lets you split a file into horcruxes - https://news.ycombinator.com/item?id=24026445 https://news.ycombinator.com/item?id=24026445 - Aug 2020 (80 comments) You can now make horcruxes out of your confidential files - https://news.ycombinator.com/item?id=21933983 https://news.ycombinator.com/item?id=21933983 - Jan 2020 (17 comments)

eightysixfour 3y ago

I have always wanted a cloud storage client which spread my files in chunks out among OneDrive, GDrive, etc. Essentially cloud raid to make it harder to put things back together.

seigel 3y ago
You and me both!!! If you ever find that, please remember this and point me to it as well. My thoughts were: use all the free capacity of the drives you mentioned to make a filesystem like HDFS which distributes blocks all over the place.. :)

zamadatix 3y ago

The note on not being able to allow only one horcrux to resurrect the original file feels unintuitive. I mean I get it'd be a pretty useless thing to do (as you'd effectively have just used an extremely complicated method of copying a file in a way it could still be read by anyone who gets a copy) but it seems odd you couldn't actually do it.

Mistletoe 3y ago

The name alone guarantees this program will live on. Sometimes I think a good name is 50-80% of the success of a product or person.

Levitating 3y ago

This is called Shamir's Secret Sharing and I once found this interesting guide for implementing it in Rust: https://gendignoux.com/blog/2021/11/01/horcrux-1-math.html https://gendignoux.com/blog/2021/11/01/horcrux-1-math.html