~stef/blog/

Oblivious Pseudo-Random Functions

In my previous SPHINX post I hand-waved away how the SPHINX oracle learns neither the input nor the output password. The mechanism behind this is a less well known cryptographic primitive, that is very nifty. Let's start with what is a pseudo-random function (PRF)? According to Boneh - Shoup Graduate Course in Applied Crypto:

A pseudo-random function (PRF) F is a deterministic algorithm that has two inputs: a key k and an input data block x; its output y := F(k, x) is called an output data block. Intuitively, our notion of security for a pseudo-random function says that for a randomly chosen key k, the function F(k, ·) should — for all practical purposes — “look like” a random function...

... that maps the input blocks to the output blocks in a way that no attacker can distinguish if the output blocks are computed using a PRF or if are the output of a random oracle that always returns the same output for the same input.

Some block ciphers can be considered PRFs, for example:

output_block := AES(key, input_block)

This is it, this is not about encryption, or decryption, it's simply the deterministic mapping of two-blocks. The PRF doesn't have to be reversible, there is no encrypt paired with a decrypt.

Another example of a PRF could be the scalar multiplication of a point X on an elliptic curve:

Y := X * k

In this case the point X is the input block, the scalar k is the key, and Y is the output block.

Oblivious PRFs are PRFs where two parties are computing a PRF in a way, where one party knows the input block, and the other one knows the key, and neither learns anything about the other, while one of them learns the output block. Constructing an OPRF on elliptic curves is only possible if the curve is a prime-order group. For example the basic ed25519 does not qualify, but a slight mutation of it - ristretto255 - qualifies. In which case an OPRF can be constructed as follows:

Alice generates a random blinding factor r, which is a scalar, and multiplies her input block with this r:

alpha := input_block * r

She sends alpha over to Bob, who has the key k and wants to keep it secret, so Bob calculates beta from alpha and the key:

beta := alpha * k

And then sends back beta to Alice, who then can then unblind the result, by multiplying beta with 1/r:

output_block := beta * 1/r

if we expand the last calculation we can see how r is eliminated by 1/r:

output_block := input_block * r * k * 1/r

and by cancelling out r and 1/r we get:

output_block := input_block * k

The whole magic is in the application of the blinding factor r, because of that Bob doesn't learn anything about Alice's input nor output block. And for some fundamental reason related to elliptic curves in general Alice does not learn anything about Bobs key. You could say that the application of the blinding factor r is a kind of encryption of both the input and the output block.

And this is a simplified explanation of how an OPRF works. And it is also exactly how it is used in the SPHINX protocol to "store" your passwords, in SPHINX the input block is the hash of your input password mapped to a point on the ristretto255 curve. And the output block is further hashed with your input password again and the host name and username of the account the output password belongs to, and then a memory hard password hash function is applied so that any kind of brute-force attack is slowed down and requires significant amount of memory. The final result without the OPRF steps is then the following:

rwd := blake2(pwd||ristretto255_fromhash(blake2(pwd))*k)

salt := blake2(hostname||username, client_key)

binary_password := argon2i(rwd, salt)

Other OPRFs

The above OPRF has been extended into VOPRFs where the V stands for Verifiable. A VOPRF ensures clients can verify that the server used a specific private key during the execution of the protocol. A VOPRF can also be partially-oblivious, called a POPRF. A POPRF allows clients and servers to provide public input to the PRF computation. For me the most exciting extension of the OPRF concept is a threshold OPRF, where a user interacts with t-out-of-n servers to calculate the OPRF.

Conclusion

OPRFs are a nifty crypto primitive that is useful in many different scenarios, besides SPHINX, I also have an implementation of the OPAQUE protocol which also has an OPRF as it main enabling cryptographic primitive. More on OPAQUE soon, here.

This project was funded through the NGI0 PET Fund, a fund established by NLnet with financial support from the European Commission's Next Generation Internet programme, under the aegis of DG Communications Networks, Content and Technology under grant agreement No 825310.