Is there a KDF that can be computed in an untrusted environment?

Question

I'm looking for a Key Derivation Function, kind of like PBKDF2 or Scrypt, but which can be computed by a machine you don't trust. Some way to give it a derivative of the source password, such that the key can be computed from the derivative but the derivative is opaque and otherwise useless to the untrusted machine. Also, I should be able to verify that machine actually performed the KDF and didn't just throw back a random key.

For the first part, protecting the password, I imagined the system would have to be something like:

s = random()
P = F(s,password)
I = KDF(P)
K = G(s,I)

Where s is some random number, and F and G are some kind of functions such that K is always the same given the same password, regardless of s.

Basically, some way to "encrypt" the password into an opaque value that the KDF can generate an incomplete key from, and then we can use the secret from that encryption to get the real key. We then throw away s. Later, to regenerate K from just the password, we can just pick another random s.

I don't know if any such combination of F, KDF, and G exist. I also don't know how to approach the proof requirement; that we can prove the KDF was executed correctly.

And of course this needs to be practical. I'm sure you could accomplish all of this using general homomorphic encryption to implement scrypt, but that would be intolerably slow.

Answer 1

Also, I should be able to verify that machine actually performed the KDF and didn't just throw back a random key.

This is actually kinda hard, but can be worked-around by carrying out the very first computation of the hash function yourself. Then store this hash for the later verification with delegation or use it to derive your key to encrypt data. You will then verify that the returned result being correct by being able to successfully decrypt the data or by verifying that the "trusted" and the untrusted hash match.

I'm looking for a [Password-based] Key Derivation Function [...], but which can be computed by a machine you don't trust. Some way to give it a derivative of the source password, such that the key can be computed from the derivative but the derivative is opaque and otherwise useless to the untrusted machine.

This functionality is precisely why our ursine overlord's Makwa has received a special recognition at the end of the Password-Hashing Competition (PHC). However it's has a somewhat "steep" baseline price. Namely you must perform about 300 (normal) modular exponentiations in an modular ring (ie modulo an RSA-like modulus) at setup time, additionally to finding a composite number similar to an RSA modulus. I will sketch the idea of it here, but I strongly urge you to read either the provided C / Java code or the specification (PDF). There are also other methods described / implemented there that will offer information-theoretic security instead of "mere" computational security if your psychology needs that.

To setup the things at your client, delegating the hashing do the following once at system-steup:

1. Pick a work-factor $w$, values of the form $\delta\in\mathbb N,\gamma\in\{2,3\}: w=\gamma\cdot2^\delta$ are recommended, with usual values being around $\delta=20$
2. Pick two primes $p,q$ such that it is infeasible to factor $n=pq$ (ie $p,q$ should be around 1024-bit long) and ensure that $p\equiv q\equiv 3\pmod 4$, store $n$ and keep $p,q$ for now
3. Pick an integer $m$ such that $2^{m/2}$ operations are infeasible, for example $m=300$
4. Pick $m$ random integers $r_i< n$, compute $\alpha_i=r_i^2\bmod n$ for each of them, compute $\alpha_i'=\alpha_i^{2^w}\bmod n$, use your knowledge of $p,q$ to reduce $2^w\bmod{\varphi(n)}$ first, where $\varphi(n)=(p-1)(q-1)$. Now compute $\beta_i=\alpha_i^{-1}\bmod n$ and store all $m$ pairs of $(\alpha_i,\beta_i)$, you don't need to keep these values secret
5. Discard $p,q$

To verify / derive the password hash (skip steps 5 and 7 and increase $w$ by one for your initial, trusted run):

1. Optionally pre-hash the password using HMAC-DRBG
2. Run the salt and the password through HMAC-DRBG to get $s_b$
3. Concatenate $s_b$, the password and the password-length to get $\chi$
4. Pick $m$ random bits $b_i$ using a CSPRNG
5. For all $j$ for which $b_j$ happens to be $1$: Compute $z=\chi^2\cdot \prod_j\alpha_j$, ie multiply the square of $\chi$ with all $\alpha_i$ where $b_i=1$
6. Send $n,w,z$ to the untrusted machine, let it compute $z'=z^{2^w}$, ie $w$-repeated-squarings and receive $z'$
7. Compute $y=z\cdot\prod_j \beta_j$ the same way as in step 5
8. Use $y$ as your output, which you may want to hash using any ordinary hash function if you intend to use it as a cryptographic key (because some bits won't have probability $\frac12$ of being $0$ or $1$) or if it is simply too large for you (with 256 bytes)