Hacker News Reader

Comment by fizx | Hacker News Reader

I want an independent write-up of Red October! Sounds really cool.

I'm not an expert, so take this speculation with a grain of salt, but I'd guess this is how it encrypts something in such a way as to require two people:

1. Generate a key, and use it to encrypt and sign your payload. Nothing fancy here; just plain old symmetric encryption and authentication.

2. Use Shamir's Secret Sharing to split the key into pieces. You need any two pieces to reconstruct the key. This is where the magic happens:

http://en.wikipedia.org/wiki/Shamir's_Secret_Sharing

3. Encrypt-and-sign each piece with a secret key derived from its owner's password/passphrase using a secure KDF like scrypt.

4. Throw away the keys, and put those encrypted pieces on disk.

Now you need passwords from any two people to decrypt the secret payload. Cool, right?

Thanks for the link to SSS. I'd never seen it before, and it's a really, really cool algorithm. One of those things that as soon as you see it you think "of course!"

We're building something similar for https://harrow.io/ which acts as the secret store, it's a Redis API compatible database with a strong auditing layer, and baked in crypto, it requires a single key to start and unlock the server, but we didn't know how to split the key to keep the secrets out of a single dev's hands. Now that we do, we'll build something based on the SSS algorithm and YubiKeys (which we use for all other tokens)

For millions of secrets and tens of people holding those secrets, there's a much more space-efficient solution. There's an added benefit that hiding each secret is plain vanilla RSA encryption.

Victor Shoup discovered a relatively straight forward way to take an RSA private key and apply Shamir secret sharing in a way that commutes with RSA public key operations. Just like Shamir secret sharing, each of the N shares of the secret is a point on a random polynomial on a finite ring (in this case, the set of quadratic residues modulo the key's public exponent). Each of the N secret holders, using their secret share, can generate a public share. Any T of the N public shares can be used to invert the RSA public key operation.

Shoup's threshold RSA signature scheme (http://www.shoup.net/papers/thsig.pdf) when used for RSA encryption caries all of the caveats that using the raw RSA algorithm entails (use OAEP, etc.)

I'm really surprised Shoup-Cramer encryption is more famous than Shoup's threshold RSA algorithm.

Reply on news.ycombinator.com