Horcrux: Split your file into encrypted fragments

My blind stab at it is this encryption always produces an output that's not validated to be what was originally encrypted and it does so in a way you could even intentionally damage a specific portion of the data without needing to know how to decrypt it.

Curious to see how wrong I am :).

Modes like OFB effectively produce a keystream(not unlike a stream cipher) which is then XOR'd with the plaintext to produce the ciphertext.

To decrypt, the same keystream is XOR'd with the ciphertext to produce the plaintext.

If there is no integrity on the ciphertext, you can simply start flipping bits in the ciphertext, and arbitrarily change what the resulting XOR with the keystream will be.

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.

It’s the same but with a framework to share between people rather than just hiding pieces of paper around the world.

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

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.

And the answer is...

> 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.

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.

Except that there are problems with the emergency scenario on both sides:

- In an actual urgent emergency, getting in touch with the 3 people and getting the data might be difficult and take days/weeks. One is on vacation, another is going to take a couple of days to try to remember where they stored the USB key...

- And nothing limits it to emergencies. The 3 people can just get together immediately and examine the valuable information inside, whether it's account numbers, crypto keys, a will, etc.

So the only value here is in not having to remember a separate password. But I expect it's just as likely for people to lose the files entirely as much as it is for them to lose passwords. If you share a password-encrypted file with 5 friends, I wouldn't be surprised if 10 years later, only 1 of them still had it. In that case, better to store file+password per-person, rather than require 3 of them to keep it.

> 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...

To be fair, the creator of HP is a crazy conservative. So, the idea of "Whore crux" being an attempt of fighting promiscuity isn't surprising.

I don't recall reading anything about lessening the soul, maybe as a byproduct of the process but not something that was intentional.

Horcrux was to backup the soul and I believe any one fragment is enough to allow for recovery.

I don't think these concepts occurred in Harry Potter or Lord of the Rings.

Is it possible you maybe you made these up?

Tolkien fell in love with his future wife when he was 16 and they were so close they were buried together under one gravestone.

> 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".

That’s an interpretation I’ve never encountered before. That’s not a canonical interpretation.

Yeah but that's just copy paste. This is more fun.

Horcrux would be a cool name for a database backup service

They already acknowledged this in the faq fwiw.

He could not resurrect himself. He needed someone in not-ghost form, to collect some special items and perform a magical ritual. Some of the special items were also one-time use iirc.

Perhaps, this tool needs to additionally encrypt some of the pieces with the dna of one's father or whatever.

Not mine, but http://point-at-infinity.org/ssss/ is another good one, with Debian packages.

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.g...

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.

Seems no different than if all N parties with the key were lost. Is there a backup strategy in case the key people are all wiped out simultaneously? How does ICANN handle it?

There was a recent story[0] about a crypto company where everyone "lost" the keys (I assume inside job).

[0] https://news.ycombinator.com/item?id=37268750

Yes, if you plan for it. There are several mitigation strategies for this.

The simple approach, if you have enough people you fully trust, is to just have a larger number of participating signers / distributed key-splits than you need, such that you don't actually need a majority of the key-splits to be used, to achieve a signing quorum. (E.g., instead of 2-of-3 signing, you'd use 2-of-4 or 2-of-5 signing.)

In this setup, usually there's a "core" of signers who are active participants in the system, where the required quorum size does constitute a majority of the "core" of signers; and then there are other "backup" signers, who aren't normally participants in signing as part of their job duties, but who can be called upon to act as additional signers in an emergency — usually just to participate in a "handover of power" (activation of new keys) for new signers (e.g. if the CIO and COO die, and you hire a new CIO and COO.)

These signers should not be anyone who any of the "core" signers has power over — not any of their reports, not anyone they can fire, and not their own friends or family. (Personal acquaintances from outside the company do make good "backup" signers, though — an officer's personal accountant is a frequent choice.)

Also, ideally, there should not be enough such "backup" signers that a single "active" signer could collude with the "backup" signers to embezzle funds. The signing configuration should still always imply the need for at least two "active" signers. (So 2-of-4 / 2-of-5 are actually bad configurations; a minimal ideal configuration would be more like 3-of-5 (with one backup signer), or 4-of-7 (with two backup signers); and you don't get both "not a majority" + "at least two active" together until 4-of-9 (2 backup) signing.)

A more expensive version of this approach, but one which could be considered more secure and with less required trust, is to give the extra signing key splits needed to achieve a signing quorum to one or more law firms, under contract to only release those key-splits upon a legal notice of demand from all still-living members of the signing group. The law firm must then verify for itself that 1. enough people are dead that the signing quorum condition can indeed no longer be met without first activating one of the offline'd keys; and 2. exactly all remaining living members of the signing quorum really want the keys released (probably this would be done through in-person individual interviews and notarizations.)

Also, to prevent this arrangement from acting as a https://en.wikipedia.org/wiki/Tontine (in the sense that it incentivizes murdering your co-officers), usually there would be a line in this contract stipulating that the keys won't be handed over while the still-living signers are under suspicion of directly or indirectly murdering the dead signers; and that the keys will only be handed over after a 60–90-day delay (which gives time for such a suspicion to arise, if relevant.)

Another mitigation strategy, that works well in combination with either of the above, is for officers with signing keys to leave their password-locked hardware signing device (smart card, crypto wallet, etc.) with a trusted coworker whenever they're going somewhere potentially dangerous; and to leave the password to unlocking said signing device with the executor of their will, only to be released upon their death. In this setup, people who travel are temporarily unable to sign (the person they've entrusted their signing device to doesn't have its password, and so cannot sign for them); so travel scheduling + signing configuration must be planned together to ensure that a signing quorum is always possible to achieve.

Store it with the files