PEP Crypto

Originally based on 2020 PEP blueprint.

Elements were also taken from "Verifiable Pseudonymization via Polymorphic Encryption using Zero-Knowledge Proofs" by Job Doesburg, which has currently not been published yet.

Authentication

Servers authenticated using TLS certificates
Messages are signed using PEP certificates and transmitted over the TLS connection
- PEP certificates are signed with server or user intermediate CA
  - Both intermediate CAs are renewed yearly and signed with PEP root certificate
- Server certificates
  - Subject CN/OU = server name
  - Renewed yearly
- User certificates
  - Subject CN = user name, OU = user group
  - Issued on enrollment by Key Server on presentation of OAuth token
    - User authenticates with variant of OAuth2 via Authserver in collaboration with Access Manager
      - Contains user name + user group + issuance & expiry
      - MACed using auth token secret
      - Prove identity to IdP, e.g. SURFconext
      - More details in #928
Tickets are used for access management to specific subjects & columns

Cell

Payload, encrypted using authenticated AES-GCM encryption
Metadata, partially encrypted
AES key, encrypted using ElGamal

Ellyptic Curve Crypto

Curve25519: \(\mathbb{E}\)
Coordinates in \(\mathbb{F}_{2^{255} - 19}\)
- Code: CurveScalar
Designated base point \(B\) generating large subgroup \(\mathbb{Z}B\)
- Code: CurvePoint
Small subgroup \(\mathbb{Z}Q\) of 8 elements (including \(\mathbf 0\))
Each element in \(\mathbb{E}\) is the sum of one in \(\mathbb{Z}B\) and \(\mathbb{Z}Q\) (including \(\mathbf 0\), which is in both)
Dangers:
- Point must lie on \(\mathbb{E}\)
- Point must be in \(\mathbb{Z}B\), because otherwise we can compute the logarithm (modulo 8)
Even point \(P\): \(P=2A\) for some \(A\)
- Even points: \(2\mathbb{E}\)
- \(\mathbb{Z}B\) are all even
Hence \(\mathbb{Z}B \cong \mathbb{E}/\mathbb{Z}Q \cong 2\mathbb{E}/2\mathbb{Z}Q\)
- Mod out (even) points from small subgroup
- Ristretto: \(\mathbb{R} := 2\mathbb{E}/2\mathbb{Z}Q\)
  - Each point has equivalence class of 4 points
  - Use extended coordinates to cache value and avoid inversions

ElGamal

Key pair: private \(x\), public \(xB\)
Encryption of \(M\): \(\operatorname{Enc}_{(xB),n}(M) = (nB, M+n \cdot (xB), (xB))\)
- Public key explicitly included for rerandomization operation below
- \(n\): random nonce
- Code: ElgamalEncryption
Decryption: \(\operatorname{Dec}_x (a,b,c) = b - xa = (M+nxB) - x \cdot (nB) = M\) if \(c = xB\)
Polymorphic operations (\(x\) not required):
- ReRandomize with \(r\): \((nB + \underline{rB}, M+nxB + \underline{r \cdot xB}, xB)\)
  - \(M\) stays intact and can be decrypted using same \(x\)
- ReShuffle with \(s\): \((\underline{s} \cdot nB, \underline{s} \cdot (M+nxB), xB)\)
  - \(M \mapsto sM\) but can be decrypted using same \(x\)
- ReKey with \(k\): \((\underline{k^{-1}} \cdot nB, M+nxB, \underline{k} \cdot xB)\)
  - \(M\) stays intact but can now be decrypted using \(sx\)
- Combined RSK: \((\underline{k^{-1}} \cdot \underline{s} \cdot (nB + \underline{rB}), \underline{s} \cdot (M+nxB + \underline{r \cdot xB}), \underline{k} \cdot xB)\)

Security concerns

Rerandomization is useful to produce two unlinkable ciphertexts that decrypt to the same plaintext, but that is not its only use. It's also important to combine it with the other operations in a client-server scenario, to mitigate attacks:

In a reshuffle/SK without rerandomization, a client can obtain \(s \cdot A\) for some point \(A\) by sending \((?, A, ?)\) as ciphertext
In a rekey without rerandomization, a client can obtain \(k \cdot A\) for some point \(A\) by sending \((?, ?, A)\) as ciphertext
In a rekey without rerandomization, a client can perform the reverse operation by sending a ciphertext with the first and third members swapped

When performing rerandomization, it's important to check that the public key is nonzero, because otherwise it will be a no-op.

Identifiers

Also see glossary.

Origin ID (randomly generated, human readable, e.g. POM1234567890)
- Polymorphic Pseudonym (encrypted Origin ID, can be randomized)
  - Local Pseudonym (32 bytes; variants: user, transcryptor, storage facility, access manager)
    - Brief Local Pseudonym (prefix + first (e.g. 10) characters of HEX representation of local pseudonym, e.g. POMU12345ABCDE)
Reference ID (mapping, human readable for uploaders, e.g. POM1PL1234549)

Pseudonyms

Pseudonyms are encrypted with ElGamal.

Master pseudonym encryption key of the system
- Private: \(x_\mathrm{p} = x_{\mathrm{p},\mathrm{AM}} x_{\mathrm{p},\mathrm{T}}\)
- Public: \(x_\mathrm{p}B\)
- Split between Access Manager and Transcryptor
On enrollment, party \(p\) obtains local pseudonym encryption key \(k_{p,\mathrm{p},\mathrm{AM}} k_{p,\mathrm{p},\mathrm{T}} x_\mathrm{p}\)
- Obtained from AM & T in key components \(k_{p,\mathrm{p},\mathrm{AM}} x_{\mathrm{p},\mathrm{AM}}\) & \(k_{p,\mathrm{p},\mathrm{T}} x_{\mathrm{p},\mathrm{T}}\)
- Pseudonym encryption key factor
  \(k_{p,\mathrm{p},z} = \operatorname{hmac-sha512}(\kappa_{\mathrm{p},z}, \operatorname{sha256}(\textnormal{00 00 00 01 00 00 00}\ t \parallel p))\)
  - \(\kappa_{\mathrm{p},z}\): pseudonym encryption key factor secret (symmetric key) known by server \(z\) (AM/T)
  - \(p\): PEP certificate (differs each enrollment) for users, or server name for servers
  - \(t\): facility type like above
For Participant ID \(a\) we have participant point \(M_a\)
- \(M_a = \operatorname{elligator2}(\operatorname{sha512}(a))\)
Polymorphic pseudonym: \(\operatorname{Enc}_{x_\mathrm{p}B, n}(M_a)\)
- \(n\): Random

Pseudonyms are shuffled to obtain different local pseudonyms.

Pseudonymisation key for access group \(p\): \(s_{p,\mathrm{AM}} s_{p,\mathrm{T}}\)
- Pseudonymisation key factor
  \(s_{p,z} = \operatorname{hmac-sha512}(\sigma_z, \operatorname{sha256}(\textnormal{00 00 00 01 00 00 00}\ t \parallel p))\)
  - \(p\): access group or server name
  - \(t\): facility type (\(01\) = users, \(02\)-\(05\) = SF, AM, T, RS), corresponds to \(b\)
  - \(\sigma_z\): pseudonymisation key factor secret (symmetric key) known by server \(z\) (AM/T)
Translate polymorphic pseudonym \(\operatorname{Enc}_{x_\mathrm{p}B, n}(M_a)\) for party \(p\):
- RSK by AM:
  - ReRandomize: \(\operatorname{Enc}_{x_\mathrm{p}B, \underline{n}}(M_a)\)
  - ReShuffle: \(\operatorname{Enc}_{x_\mathrm{p}B, \underline{n'}}(\underline{s_{p,\mathrm{AM}}} M_a)\)
  - ReKey: \(\operatorname{Enc}_{\underline{k_{p,\mathrm{p},\mathrm{AM}}} x_\mathrm{p}B, \underline{n''}}(s_{p,\mathrm{AM}} M_a)\)
- Then same RSK by T:
  \(\operatorname{Enc}_{\underline{k_{p,\mathrm{p},\mathrm{T}}} k_{p,\mathrm{p},\mathrm{AM}} x_\mathrm{p}B, \underline{n'''}}(\underline{s_{p,\mathrm{T}}} s_{p,\mathrm{AM}} M_a)\)
- \(\mathrm{Enc}_{k_{p,\mathrm{p},\mathrm{T}} k_{p,\mathrm{p},\mathrm{AM}} x_\mathrm{p}B, n}(s_{p,\mathrm{T}} s_{p,\mathrm{AM}} M_a)\) is the encrypted local pseudonym
- Local pseudonym \(s_{p,\mathrm{AM}} s_{p,\mathrm{T}} M_a\) obtained by decrypting with the local pseudonym encryption key \(k_{p,\mathrm{p},\mathrm{AM}} k_{p,\mathrm{p},\mathrm{T}} x_\mathrm{p}\) (above)

Data

Master data encryption key of the system
- Private: \(x_\mathrm{d} = x_{\mathrm{d},\mathrm{AM}} x_{\mathrm{d},\mathrm{T}}\)
- Public: \(x_\mathrm{d}B\)
On enrollment, client obtains local data encryption key \(k_{\mathrm{d},\mathrm{AM}} k_{\mathrm{d},\mathrm{T}} x_\mathrm{d}\)
- Data encryption key factor
  \(k_{\mathrm{d},c} = \operatorname{hmac-sha512}(\kappa_{\mathrm{d},c}, \operatorname{sha256}(\textnormal{00 00 00 02 00 00 00}\ t \parallel p))\)
  - Data encryption key factor secret \(\kappa_{\mathrm{d},c}\) (symmetric key) known by server \(c\)
  - \(t,p\): like above
Cells are encrypted using AES key \(\operatorname{sha256}(K)\)
- \(K\) is a curve point
- Additional Authenticated Data (old versions were different): page number
- Generated by uploading client, ElGamal-encrypted with master data encryption key to obtain polymorphic encryption key
- Key is 'blinded' by AM while ElGamal-encrypted: \(b^{-1} K\) (old versions were different)
  - Blinding key \(b = \operatorname{hmac-sha512}(\beta, 3 \parallel \textnormal{timestamp} \parallel \textnormal{tag} \parallel s_{\mathrm{AM},\mathrm{AM}} s_{\mathrm{AM},\mathrm{T}} M_a \parallel \textnormal{binded metadata})\)
    - \(\beta\): blinding key secret (symmetric key) known to AM
    - \(s_{\mathrm{AM},\mathrm{AM}} s_{\mathrm{AM},\mathrm{T}} M_a\): AM's local pseudonym for \(a\)

The blinding key is there to prevent the following attack. A malicious Storage Facility colludes with a user U to download cell C1 that U does not have access to. U requests a ticket for another cell C2 that they do have access to. The Storage Facility then actually returns C1 to U. U now RSKs the encrypted cell via AM & TS and can decrypt C1. The blinding key prevents this, because if the ticket does not match the cell, the derived blinding key will be wrong and scramble the ciphertext. Note that AEAD (AES-GCM) encryption is not a solution to this, as that check only happens client-side.

Proofs

Schnorr's identification protocol

Zero Knowledge Proof that you know logarithm \(x\) of \(X = xB\).

Prover chooses secret random nonce \(r\)
Sends commitment \(R = rB\) to verifier
Verifier sends random challenge \(c\)
Prover sends \(z = r + cx\)
Verifier checks \(zB \overset?= R + cX\)

Non-Interactive variant

Transformed using Fiat-Shamir heuristic to use cryptographic hash for challenge.

Prover chooses secret random nonce \(r\)
Computes commitment \(R = rB\)
Computes challenge \(c = h(X,R)\)
Computes \(z = r + cx\)
Publishes \(R,z\) besides \(X\)
Verifier also computes challenge \(c = h(X,R)\)
Checks \(zB \overset?= R + cX\)

Scalar multiplication

Prove that you know scalar \(x\) in \(N = xM\) without giving \(x\).

Chaum-Pedersen protocol + Fiat-Shamir heuristic, similar to Schnorr NI-ZKP:

Prover chooses secret random nonce \(r\)
Computes commitments \(R_B = rB\) & \(R_M = rM\)
Computes challenge \(c = h(M,N,R_B,R_M)\)
Computes \(z = r + cx\)
Publishes \(R_B,R_M,z, X=xB\) besides \(M,N\)
Verifier also computes challenge \(c = h(M,N,R_B,R_M)\)
Checks \(zB \overset?= R_B + cX\)
Checks \(zM \overset?= R_M + cN\)

We also add \(X\) in the challenge hash, although this is redundant.

Inverse

Prove that \(X^{-1} = x^{-1}B\) for secret \(x\).

Prover constructs scalar multiplication proof for \(B = x^{-1} \cdot X\)
Publishes \(X\) and scalar multiplication proof (includes \(X^{-1}\))
Verifier checks scalar multiplication proof

RSK proof

Remember combined RSK (see above): \((\underline{k^{-1}} \cdot \underline{s} \cdot (nB + \underline{rB}), \underline{s} \cdot (M+nxB + \underline{r \cdot xB}), \underline{k} \cdot xB)\)

For this, you need 3 multiplication proofs:

\(\underline{sk^{-1}} \cdot (nB + rB)\)
\(\underline{s} \cdot (M+nxB + rxB)\)
\(\underline{r} \cdot xB\)

Check multiplication proofs using additional info dependent on just reshuffle & rekey factors:

Rekeyed public key \(kxB\) (check that public key is as expected)
\(sB\) (for proof 2)
\(sk^{-1}B\) (for proof 1)

This way, transcryptors enforce use of consistent scalars \(s_{p,z}, k_{p,\mathrm{p}}\) for reshuffling & rekeying pseudonyms.

Note that \(rB\) and \(rxB\) to verify proof 3 are attached with the proof.

In PEP

In PEP, the Access Manager proves to the Transcryptor that it performed the RSKs correctly: with consistent factors, starting at the same polymorphic pseudonym. The Transcryptor can then log the consistent set of pseudonyms for auditing.