[old] key recovery using untrusted machines

Below is a recovered post from 2019-09-08 that I found in my backups. (There are 2 other posts, but neither are worth preserving. This one isn’t either, really, but it’s interesting).

Yes it’s probably broken. I will not be changing the text. I might do it again but in a newer post, and work on making that one actually secure.

Apple did a nice talk about how they handle security, and they did a bit on how key recovery works. (https://www.youtube.com/watch?v=BLGFriOKz6U?t=1496 24:56).

They use groups of 5 hardware security modules, each with an internal counter that counts down from 10 on every try, with a mechanism to prevent partitioning attacks (One module is isolated from others, 10 attempts are made against it, then the next one is isolated, 10 more attempts, in total you can make n times more attempts, where n is the number of HSM's used for redundancy).

But you still need to trust that this is actually what Apple does. There is no way to, from the software side, prove that your keys are only on a HSM and that they only have 10 attempts.

Can we do better?

Definitions

Let S be your secret. This is a series of bytes indistinguishable from random data.

Let P be your password. This does not need to be high entropy, a 6 digit 0-9 PIN still makes attacks unlikely.

Let H(D, K) be a cryptographically secure keyed hash function that hashes data D with key K.

Scheme

Randomly generate a 32 byte secret key K, and store it in the recovery file.

Split your secret S into shares S1 .. Sn where n is the number of servers you want to split across. In this example, we're using 15. The threshold is t, which in this example is 10.

Pick n (15) random servers from a pool of servers contributing to this scheme.

Pair up each share S1..Sn to a server V1..Vn.

Let S be a unique server identifier for the server you're working with. The server name, or even just the index in the list of servers will do.

Let HP = H(P, H(K, S))

Encrypt each transformed share using HP. Send the encrypted share to the server, along with a request count RC.

The request count will be the number of times the key is allowed to be attempted. This should be the same for every server.

When you are requesting a key recovery, you will go to every server in your list, and give them your HP. (The hash is keyed to prevent the server recovering P from HP, and S is included in order to prevent the server going to other servers and using your HP to recover shares).

The server will then decrement the counter, and return the result of decrypting the encrypted share with HP.

This way, the server itself doesn't know if the password is correct, nor does the requestor. You are required to request at least t (10 in this example) shares for the same password in order to try to recover a share.

This prevents an attacker from trying to extend the attempts too much. (TODO can you do any clever stuff with the counter to prevent share re-use across different counters? This would completely block extending as long as the share amount is more than 50%). Complete prevention of a re-use through partial contact is possible when n-t < rc (TODO prove this).

After you have gotten your list of decrypted shares, you then recombine them to get your secret back, and then you can then recover your data.

Additions

With this mechanism as is, an attacker could slowly attack each machine in turn, and get your key.

We could rotate keys between devices. Every month or so, redo the entire scheme for a new random set of servers.

You also need a mechanism to expire shares. Say a share expires after 3 months. Every server completely forgets its share after 3 months.

A few servers being hostile and remembering their shares is not an issue, even if you rotate your keys very often. The shares would need to be from the same set in order to be useful, therefore in this example 10 out of the 15 servers would need to be hostile.

Vulns

Counter extending

By an attacker only talking to a subset of the machines on every attempt, they can extend the attempt count.

You could combat this by requiring the servers know about every other server and co-ordinate their counters, but this can leak information (Namely, the number of servers involved in the scheme and their names).

This is not an issue with a small number of servers and a small attempt count.

There MIGHT be some cryptographic way to include the counter in the algorithm in such a way that you need t shares that have all been decrypted with the same counter value.

Sybil attack

If an attacker has control of t servers that you've chosen, they can easily find your secret.

Nothing we can do here. Tor suffers from the same vulnerability.