356 lines
17 KiB
JavaScript
356 lines
17 KiB
JavaScript
/**
|
|
* RFC 9497: Oblivious Pseudorandom Functions (OPRFs) Using Prime-Order Groups.
|
|
* https://www.rfc-editor.org/rfc/rfc9497
|
|
*
|
|
|
|
OPRF allows to interactively create an `Output = PRF(Input, serverSecretKey)`:
|
|
|
|
- Server cannot calculate Output by itself: it doesn't know Input
|
|
- Client cannot calculate Output by itself: it doesn't know server secretKey
|
|
- An attacker interception the communication can't restore Input/Output/serverSecretKey and can't
|
|
link Input to some value.
|
|
|
|
## Issues
|
|
|
|
- Low-entropy inputs (e.g. password '123') enable brute-forced dictionary attacks by the server
|
|
(solveable by domain separation in POPRF)
|
|
- High-level protocol needs to be constructed on top, because OPRF is low-level
|
|
|
|
## Use cases
|
|
|
|
1. **Password-Authenticated Key Exchange (PAKE):** Enables secure password login (e.g., OPAQUE)
|
|
without revealing the password to the server.
|
|
2. **Private Set Intersection (PSI):** Allows two parties to compute the intersection of their
|
|
private sets without revealing non-intersecting elements.
|
|
3. **Anonymous Credential Systems:** Supports issuance of anonymous, unlinkable credentials
|
|
(e.g., Privacy Pass) using blind OPRF evaluation.
|
|
4. **Private Information Retrieval (PIR):** Helps users query databases without revealing which
|
|
item they accessed.
|
|
5. **Encrypted Search / Secure Indexing:** Enables keyword search over encrypted data while keeping
|
|
queries private.
|
|
6. **Spam Prevention and Rate-Limiting:** Issues anonymous tokens to prevent abuse
|
|
(e.g., CAPTCHA bypass) without compromising user privacy.
|
|
|
|
## Modes
|
|
|
|
- OPRF: simple mode, client doesn't need to know server public key
|
|
- VOPRF: verifiable mode. It lets the client verify that the server used the
|
|
secret key corresponding to a known public key
|
|
- POPRF: partially oblivious mode, VOPRF + domain separation
|
|
|
|
There is also non-interactive mode (Evaluate), which creates Output
|
|
non-interactively with knowledge of the secret key.
|
|
|
|
Flow:
|
|
- (once) Server generates secret and public keys, distributes public keys to clients
|
|
- deterministically: `deriveKeyPair` or just random: `generateKeyPair`
|
|
- Client blinds input: `blind(secretInput)`
|
|
- Server evaluates blinded input: `blindEvaluate` generated by client, sends result to client
|
|
- Client creates output using result of evaluation via 'finalize'
|
|
|
|
* @module
|
|
*/
|
|
/*! noble-curves - MIT License (c) 2022 Paul Miller (paulmillr.com) */
|
|
import { abytes, asciiToBytes, bytesToNumberBE, bytesToNumberLE, concatBytes, numberToBytesBE, randomBytes, validateObject, } from "../utils.js";
|
|
import { pippenger, validatePointCons } from "./curve.js";
|
|
import { _DST_scalar } from "./hash-to-curve.js";
|
|
import { getMinHashLength, mapHashToField } from "./modular.js";
|
|
const _DST_scalarBytes = /* @__PURE__ */ asciiToBytes(_DST_scalar);
|
|
// welcome to generic hell
|
|
/**
|
|
* @param opts - OPRF ciphersuite options. See {@link OPRFOpts}.
|
|
* @returns OPRF helper namespace.
|
|
* @example
|
|
* Instantiate an OPRF suite from curve-specific hashing hooks.
|
|
*
|
|
* ```ts
|
|
* import { createOPRF } from '@noble/curves/abstract/oprf.js';
|
|
* import { p256, p256_hasher } from '@noble/curves/nist.js';
|
|
* import { sha256 } from '@noble/hashes/sha2.js';
|
|
* const oprf = createOPRF({
|
|
* name: 'P256-SHA256',
|
|
* Point: p256.Point,
|
|
* hash: sha256,
|
|
* hashToGroup: p256_hasher.hashToCurve,
|
|
* hashToScalar: p256_hasher.hashToScalar,
|
|
* });
|
|
* const keys = oprf.oprf.generateKeyPair();
|
|
* ```
|
|
*/
|
|
export function createOPRF(opts) {
|
|
validateObject(opts, {
|
|
name: 'string',
|
|
hash: 'function',
|
|
hashToScalar: 'function',
|
|
hashToGroup: 'function',
|
|
});
|
|
// Cheap constructor-surface sanity check only: this verifies the generic static hooks/fields that
|
|
// OPRF consumes, but it does not certify point semantics like BASE/ZERO correctness.
|
|
validatePointCons(opts.Point);
|
|
const { name, Point, hash } = opts;
|
|
const { Fn } = Point;
|
|
const hashToGroup = (msg, ctx) => opts.hashToGroup(msg, {
|
|
DST: concatBytes(asciiToBytes('HashToGroup-'), ctx),
|
|
});
|
|
const hashToScalarPrefixed = (msg, ctx) => opts.hashToScalar(msg, { DST: concatBytes(_DST_scalarBytes, ctx) });
|
|
const randomScalar = (rng = randomBytes) => {
|
|
// RFC 9497 §2.1 defines RandomScalar as nonzero; blind inversion and generated public keys
|
|
// both rely on keeping this helper in the `1..n-1` range.
|
|
const t = mapHashToField(rng(getMinHashLength(Fn.ORDER)), Fn.ORDER, Fn.isLE);
|
|
// We cannot use Fn.fromBytes here, because field
|
|
// can have different number of bytes (like ed448)
|
|
return Fn.isLE ? bytesToNumberLE(t) : bytesToNumberBE(t);
|
|
};
|
|
const msm = (points, scalars) => pippenger(Point, points, scalars);
|
|
const getCtx = (mode) => concatBytes(asciiToBytes('OPRFV1-'), new Uint8Array([mode]), asciiToBytes('-' + name));
|
|
const ctxOPRF = getCtx(0x00);
|
|
const ctxVOPRF = getCtx(0x01);
|
|
const ctxPOPRF = getCtx(0x02);
|
|
function encode(...args) {
|
|
const res = [];
|
|
for (const a of args) {
|
|
if (typeof a === 'number')
|
|
res.push(numberToBytesBE(a, 2));
|
|
else if (typeof a === 'string')
|
|
res.push(asciiToBytes(a));
|
|
else {
|
|
abytes(a);
|
|
res.push(numberToBytesBE(a.length, 2), a);
|
|
}
|
|
}
|
|
// No wipe here, since will modify actual bytes
|
|
return concatBytes(...res);
|
|
}
|
|
const inputBytes = (title, bytes) => {
|
|
abytes(bytes, undefined, title);
|
|
// RFC 9497 §1.2 limits PrivateInput/PublicInput to 2^16 - 1 bytes because these values are
|
|
// length-prefixed with two bytes before use throughout the protocol.
|
|
if (bytes.length > 0xffff)
|
|
throw new Error(`"${title}" expected Uint8Array of length <= 65535, got length=${bytes.length}`);
|
|
return bytes;
|
|
};
|
|
const hashInput = (...bytes) => hash(encode(...bytes, 'Finalize'));
|
|
function getTranscripts(B, C, D, ctx) {
|
|
const Bm = B.toBytes();
|
|
const seed = hash(encode(Bm, concatBytes(asciiToBytes('Seed-'), ctx)));
|
|
const res = [];
|
|
for (let i = 0; i < C.length; i++) {
|
|
const Ci = C[i].toBytes();
|
|
const Di = D[i].toBytes();
|
|
const di = hashToScalarPrefixed(encode(seed, i, Ci, Di, 'Composite'), ctx);
|
|
res.push(di);
|
|
}
|
|
return res;
|
|
}
|
|
function computeComposites(B, C, D, ctx) {
|
|
const T = getTranscripts(B, C, D, ctx);
|
|
const M = msm(C, T);
|
|
const Z = msm(D, T);
|
|
return { M, Z };
|
|
}
|
|
function computeCompositesFast(k, B, C, D, ctx) {
|
|
const T = getTranscripts(B, C, D, ctx);
|
|
const M = msm(C, T);
|
|
// RFC 9497 §2.2.1 ComputeCompositesFast derives weights from both C and D in getTranscripts(),
|
|
// then uses the server shortcut Z = k * M instead of a second MSM over D.
|
|
const Z = M.multiply(k);
|
|
return { M, Z };
|
|
}
|
|
function challengeTranscript(B, M, Z, t2, t3, ctx) {
|
|
const [Bm, a0, a1, a2, a3] = [B, M, Z, t2, t3].map((i) => i.toBytes());
|
|
return hashToScalarPrefixed(encode(Bm, a0, a1, a2, a3, 'Challenge'), ctx);
|
|
}
|
|
function generateProof(ctx, k, B, C, D, rng) {
|
|
const { M, Z } = computeCompositesFast(k, B, C, D, ctx);
|
|
const r = randomScalar(rng);
|
|
const t2 = Point.BASE.multiply(r);
|
|
const t3 = M.multiply(r);
|
|
const c = challengeTranscript(B, M, Z, t2, t3, ctx);
|
|
const s = Fn.sub(r, Fn.mul(c, k)); // r - c*k
|
|
return concatBytes(...[c, s].map((i) => Fn.toBytes(i)));
|
|
}
|
|
function verifyProof(ctx, B, C, D, proof) {
|
|
abytes(proof, 2 * Fn.BYTES);
|
|
const { M, Z } = computeComposites(B, C, D, ctx);
|
|
const [c, s] = [proof.subarray(0, Fn.BYTES), proof.subarray(Fn.BYTES)].map((f) => Fn.fromBytes(f));
|
|
const t2 = Point.BASE.multiply(s).add(B.multiply(c)); // s*G + c*B
|
|
const t3 = M.multiply(s).add(Z.multiply(c)); // s*M + c*Z
|
|
const expectedC = challengeTranscript(B, M, Z, t2, t3, ctx);
|
|
if (!Fn.eql(c, expectedC))
|
|
throw new Error('proof verification failed');
|
|
}
|
|
function generateKeyPair() {
|
|
const skS = randomScalar();
|
|
const pkS = Point.BASE.multiply(skS);
|
|
return { secretKey: Fn.toBytes(skS), publicKey: pkS.toBytes() };
|
|
}
|
|
function deriveKeyPair(ctx, seed, info) {
|
|
// RFC 9497 §3.2.1 defines `seed[32]`; reject other sizes here because this public API already
|
|
// documents a 32-byte seed instead of generic input keying material.
|
|
abytes(seed, 32, 'seed');
|
|
info = inputBytes('keyInfo', info);
|
|
const dst = concatBytes(asciiToBytes('DeriveKeyPair'), ctx);
|
|
const msg = concatBytes(seed, encode(info), Uint8Array.of(0));
|
|
for (let counter = 0; counter <= 255; counter++) {
|
|
msg[msg.length - 1] = counter;
|
|
const skS = opts.hashToScalar(msg, { DST: dst });
|
|
if (Fn.is0(skS))
|
|
continue; // should not happen
|
|
return {
|
|
secretKey: Fn.toBytes(skS),
|
|
publicKey: Point.BASE.multiply(skS).toBytes(),
|
|
};
|
|
}
|
|
throw new Error('Cannot derive key');
|
|
}
|
|
const wirePoint = (label, bytes) => {
|
|
const point = Point.fromBytes(bytes);
|
|
// RFC 9497 §3.3 says applications MUST reject group-identity Elements received over the wire
|
|
// after deserialization, even if the suite decoder itself accepts the identity encoding.
|
|
if (point.equals(Point.ZERO))
|
|
throw new Error(label + ' point at infinity');
|
|
return point;
|
|
};
|
|
function blind(ctx, input, rng = randomBytes) {
|
|
input = inputBytes('input', input);
|
|
const blind = randomScalar(rng);
|
|
const inputPoint = hashToGroup(input, ctx);
|
|
if (inputPoint.equals(Point.ZERO))
|
|
throw new Error('Input point at infinity');
|
|
const blinded = inputPoint.multiply(blind);
|
|
return { blind: Fn.toBytes(blind), blinded: blinded.toBytes() };
|
|
}
|
|
function evaluate(ctx, secretKey, input) {
|
|
input = inputBytes('input', input);
|
|
const skS = Fn.fromBytes(secretKey);
|
|
const inputPoint = hashToGroup(input, ctx);
|
|
if (inputPoint.equals(Point.ZERO))
|
|
throw new Error('Input point at infinity');
|
|
const unblinded = inputPoint.multiply(skS).toBytes();
|
|
return hashInput(input, unblinded);
|
|
}
|
|
const oprf = Object.freeze({
|
|
generateKeyPair,
|
|
deriveKeyPair: (seed, keyInfo) => deriveKeyPair(ctxOPRF, seed, keyInfo),
|
|
blind: (input, rng = randomBytes) => blind(ctxOPRF, input, rng),
|
|
blindEvaluate(secretKey, blindedPoint) {
|
|
const skS = Fn.fromBytes(secretKey);
|
|
const elm = wirePoint('blinded', blindedPoint);
|
|
return elm.multiply(skS).toBytes();
|
|
},
|
|
finalize(input, blindBytes, evaluatedBytes) {
|
|
input = inputBytes('input', input);
|
|
const blind = Fn.fromBytes(blindBytes);
|
|
const evalPoint = wirePoint('evaluated', evaluatedBytes);
|
|
const unblinded = evalPoint.multiply(Fn.inv(blind)).toBytes();
|
|
return hashInput(input, unblinded);
|
|
},
|
|
evaluate: (secretKey, input) => evaluate(ctxOPRF, secretKey, input),
|
|
});
|
|
const voprf = Object.freeze({
|
|
generateKeyPair,
|
|
deriveKeyPair: (seed, keyInfo) => deriveKeyPair(ctxVOPRF, seed, keyInfo),
|
|
blind: (input, rng = randomBytes) => blind(ctxVOPRF, input, rng),
|
|
blindEvaluateBatch(secretKey, publicKey, blinded, rng = randomBytes) {
|
|
if (!Array.isArray(blinded))
|
|
throw new Error('expected array');
|
|
const skS = Fn.fromBytes(secretKey);
|
|
const pkS = wirePoint('public key', publicKey);
|
|
const blindedPoints = blinded.map((i) => wirePoint('blinded', i));
|
|
const evaluated = blindedPoints.map((i) => i.multiply(skS));
|
|
const proof = generateProof(ctxVOPRF, skS, pkS, blindedPoints, evaluated, rng);
|
|
return { evaluated: evaluated.map((i) => i.toBytes()), proof };
|
|
},
|
|
blindEvaluate(secretKey, publicKey, blinded, rng = randomBytes) {
|
|
const res = this.blindEvaluateBatch(secretKey, publicKey, [blinded], rng);
|
|
return { evaluated: res.evaluated[0], proof: res.proof };
|
|
},
|
|
finalizeBatch(items, publicKey, proof) {
|
|
if (!Array.isArray(items))
|
|
throw new Error('expected array');
|
|
const pkS = wirePoint('public key', publicKey);
|
|
const blindedPoints = items.map((i) => wirePoint('blinded', i.blinded));
|
|
const evalPoints = items.map((i) => wirePoint('evaluated', i.evaluated));
|
|
verifyProof(ctxVOPRF, pkS, blindedPoints, evalPoints, proof);
|
|
return items.map((i) => oprf.finalize(i.input, i.blind, i.evaluated));
|
|
},
|
|
finalize(input, blind, evaluated, blinded, publicKey, proof) {
|
|
return this.finalizeBatch([{ input, blind, evaluated, blinded }], publicKey, proof)[0];
|
|
},
|
|
evaluate: (secretKey, input) => evaluate(ctxVOPRF, secretKey, input),
|
|
});
|
|
// NOTE: info is domain separation
|
|
const poprf = (info) => {
|
|
info = inputBytes('info', info);
|
|
const m = hashToScalarPrefixed(encode('Info', info), ctxPOPRF);
|
|
const T = Point.BASE.multiply(m);
|
|
return Object.freeze({
|
|
generateKeyPair,
|
|
deriveKeyPair: (seed, keyInfo) => deriveKeyPair(ctxPOPRF, seed, keyInfo),
|
|
blind(input, publicKey, rng = randomBytes) {
|
|
input = inputBytes('input', input);
|
|
const pkS = wirePoint('public key', publicKey);
|
|
const tweakedKey = T.add(pkS);
|
|
if (tweakedKey.equals(Point.ZERO))
|
|
throw new Error('tweakedKey point at infinity');
|
|
const blind = randomScalar(rng);
|
|
const inputPoint = hashToGroup(input, ctxPOPRF);
|
|
if (inputPoint.equals(Point.ZERO))
|
|
throw new Error('Input point at infinity');
|
|
const blindedPoint = inputPoint.multiply(blind);
|
|
return {
|
|
blind: Fn.toBytes(blind),
|
|
blinded: blindedPoint.toBytes(),
|
|
tweakedKey: tweakedKey.toBytes(),
|
|
};
|
|
},
|
|
blindEvaluateBatch(secretKey, blinded, rng = randomBytes) {
|
|
if (!Array.isArray(blinded))
|
|
throw new Error('expected array');
|
|
const skS = Fn.fromBytes(secretKey);
|
|
const t = Fn.add(skS, m);
|
|
// "Hence, this error can be a signal for the server to replace its
|
|
// private key". We throw inside; this should be impossible.
|
|
const invT = Fn.inv(t);
|
|
const blindedPoints = blinded.map((i) => wirePoint('blinded', i));
|
|
const evalPoints = blindedPoints.map((i) => i.multiply(invT));
|
|
const tweakedKey = Point.BASE.multiply(t);
|
|
const proof = generateProof(ctxPOPRF, t, tweakedKey, evalPoints, blindedPoints, rng);
|
|
return { evaluated: evalPoints.map((i) => i.toBytes()), proof };
|
|
},
|
|
blindEvaluate(secretKey, blinded, rng = randomBytes) {
|
|
const res = this.blindEvaluateBatch(secretKey, [blinded], rng);
|
|
return { evaluated: res.evaluated[0], proof: res.proof };
|
|
},
|
|
finalizeBatch(items, proof, tweakedKey) {
|
|
if (!Array.isArray(items))
|
|
throw new Error('expected array');
|
|
const inputs = items.map((i) => inputBytes('input', i.input));
|
|
const evalPoints = items.map((i) => wirePoint('evaluated', i.evaluated));
|
|
verifyProof(ctxPOPRF, wirePoint('tweakedKey', tweakedKey), evalPoints, items.map((i) => wirePoint('blinded', i.blinded)), proof);
|
|
return items.map((i, j) => {
|
|
const blind = Fn.fromBytes(i.blind);
|
|
const point = evalPoints[j].multiply(Fn.inv(blind)).toBytes();
|
|
return hashInput(inputs[j], info, point);
|
|
});
|
|
},
|
|
finalize(input, blind, evaluated, blinded, proof, tweakedKey) {
|
|
return this.finalizeBatch([{ input, blind, evaluated, blinded }], proof, tweakedKey)[0];
|
|
},
|
|
evaluate(secretKey, input) {
|
|
input = inputBytes('input', input);
|
|
const skS = Fn.fromBytes(secretKey);
|
|
const inputPoint = hashToGroup(input, ctxPOPRF);
|
|
if (inputPoint.equals(Point.ZERO))
|
|
throw new Error('Input point at infinity');
|
|
const t = Fn.add(skS, m);
|
|
const invT = Fn.inv(t);
|
|
const unblinded = inputPoint.multiply(invT).toBytes();
|
|
return hashInput(input, info, unblinded);
|
|
},
|
|
});
|
|
};
|
|
const res = { name, oprf, voprf, poprf, __tests: Object.freeze({ Fn }) };
|
|
return Object.freeze(res);
|
|
}
|
|
//# sourceMappingURL=oprf.js.map
|