Horcrux: Split your file into encrypted fragments

Harry himself being the final Horcrux so he had to be temporarily killed to clear it out.

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.

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

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

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.