Advanced Security and Privacy Features

Dr. Greg Bernstein

September 3rd, 2024

VC Advanced Security and Privacy Features

Outline

  1. Attacks on Credentials
  2. Public Key based Holder Binding
  3. Anonymous Holder Binding
    1. Commitments
    2. ZKPs of commitments
    3. Application: Signal Usernames
    4. Blind BBS Signing

Me and My VC Work

* W3C “Invited Expert”, semi-retired, website: Grotto Networking

Credential Attacks

Evil Issuers and Verifiers

Previous we talked about tracking

It’s evil when done without our knowledge and/or consent.

Stolen Credential Use

Using a verifiable credential without the holders consent or knowledge.

Stealing Credentials

  • Credential intercepted between issuer and holder, or holder and verifier
  • Credential obtained via data breach at issuer, holder, or verifier

Complicit Credential Abuse

Illicit use of a credential with complicity of the credential’s holder, i.e., somebody other than the intended holder is using the credential with the holder’s knowledge.

Common Examples of Credential Abuse

  • Account sharing (beyond contracted limits) – multi device and access, app and browser.
  • Restriction evasions – age limits, qualification requirements, etc.
  • Unlinkability can make this abuse easier => Per verifier ids (pseudonyms) helps mitigate

Forging Credentials

This is extremely difficult if the cryptography implemented correctly and signing key kept secret. This is what cryptographic papers are all about!

Mitigating Stolen Credential Use

Verifier Challenge in VCs

Verifier Challenge Data Flow

Verifier Challenge Issue

Holder has to get issuer involved in providing a “fresh” credential to satisfy verifier.

BBS Presentation Header (PH)

BBS Three Party Model (Review)

  • Issuer <-> Holder: Sign(SK, PK, header, messages) and Verify(PK, signature, header, messages)
  • Holder <-> Verifier: ProofGen(PK, signature, header, ph, messages, disclosed_indexes) and ProofVerify(PK, proof, header, ph, disclosed_messages, disclosed_indexes)
  • header info must be shared with all parties, ph must be shared between Holder and Verifier.

BBS PH based Anti-Replay Flow

Note issuer is not involved

Public Key Based Holder Binding

Public Key Based Holder Binding I

Holder Binding based on Public Key Cryptography

  1. Holder generates a public/private key pair for creating digital signatures, such as for ECDSA signatures.
  2. The public key is sent to the issuer for inclusion in the credential that is sent to the holder.

Public Key Based Holder Binding II

  1. When requesting the credential the verifier also includes a message acting as a test. The holder signs this message with their private key and includes it with the credential sent to verifier.
  2. The verifier then validates the signature on the test message with the holder’s public key contained in the VC and it verifies the signed credential with the issuer’s public key.

Public Key Based Holder Binding Flow

Public Key Based Holder Binding Properties

  • Pros: Prevents anyone else from using the credential without the holder’s consent. As strong as the ability of the holder to keep their private key secret.

  • Cons: Holder public key in VC is a unique identifer for the holder and allows tracking on every credential use.

Protecting Private Keys

  • Put it someplace really safe, so know one can steal it
  • Only use it in a really safe place, so know one and learn it
  • This gets us into trusted computing such as Trusted Execution Environments, and TPMs

Hardware Based Roots of Trust I

From Wikipedia: TPM, older TPM 1.1, new TPM 2.0 includes Elliptic Curve Cryptography

Hardware Based Roots of Trust II

Hardware Based Roots of Trust III

Key secure element features used By Public Key Holder Binding:

  • Key Pair Generation (public/private keys)
  • Private Keys never leave secure element (unless they are encrypted – AKA key wrapping)
  • Signature generation

Caveats

  • Security is more than the hardware root of trust. Adversaries will go around it or try to gain control of it. Though they cannot extract the private keys!
  • How do apps get fair access to such devices without worrying about compromise?
  • Hardware can be slow to evolve. Current ECC support is limited to P-256 and ECSDSA.

Anonymous Holder Binding

Public Key Holder Binding Concepts

  • The giving the verifier the holder’s public key allows the holder to “prove” that they know a secret, i.e., the private part of the key pair.
  • The public key is “bound” to the private key part of the key pair.
  • But the public key is linked to the secret key and doesn’t “hide” the holder

Holder Commits to a Secret

From Wikipedia: Commitment Scheme

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding.

Commitment Scheme Properties

A Graduate Course in Applied Cryptography, Dan Boneh and Victor Shoup, section 8.12

  1. Binding: Once a commitment c is generated, Alice can only open it to a single message.” => No changing the message/value after the commitment has been made.
  2. Hiding: The commitment string c should reveal no information about the committed message” => this is true even if the message set is under the control of the adversary.

Example: Hash Based Commitment Scheme

  1. Let m be the value/message being committed
  2. Choose r randomly
  3. Compute the commitment \(c = H(m || r)\) where H() is a hash function
  4. Send \((c, r)\)
  5. Verification on reveal of m by checking \(c = H(m || r)\).

Example: Pedersen Commitment

  1. Let g and h be generators of the same (prime) group
  2. Let x be a number (message) to be committed
  3. Let r be a random number (blinding factor)
  4. Compute the commitment as \(c = g^x h^r\)

But if we reveal the secret…

  • If the holder reveals the secret they can be impersonated.
  • If the holder uses the same commitment more than once they can be tracked
  • The holder needs to prove to the issuer and verifier that they know the secret without revealing it.

Zero Knowledge Proofs I

From ZKProof Community Reference

A ZKP system is a specification of how a prover and verifier can interact for the prover to convince the verifier that the statement is true. The proof system must be complete, sound and ZK.

Zero Knowledge Proofs II

From ZKProof Community Reference

  • Complete: If the statement is true and both prover and verifier follow the protocol; the verifier will accept.
  • Sound: If the statement is false, and the verifier follows the protocol; the verifier will not be convinced. You can’t fool me!
  • Zero-knowledge: If the statement is true and the prover follows the protocol; the verifier will not learn any confidential information from the interaction with the prover but the fact the statement is true.

Proofs vs. arguments

From ZKProof Community Reference

The theory of ZKPs distinguishes between proofs and arguments, as related to the computational power of the prover and verifier. Proofs need to be sound even against computationally unbounded provers, whereas arguments only need to preserve soundness against computationally bounded provers.

Typically the term proof is used unless more precision is needed.

More ZKP References and Terminology

BBS and ZKPs I

  • The BBS proof provided by a holder to a verifier is a zero knowledge proof of knowledge of the BBS signature and the BBS messages. Proof can’t be linked to signature.
  • Each BBS proof generated uses a set of cryptographic random numbers and hence different proofs cannot be linked to each other.

BBS and ZKPs II

  • BBS proofs are based on a much older (20+ years) ZKP approach known as Sigma Protocols.
  • Very efficient in terms of space, creation and verification computation. Limited to relations among discrete logarithms.
  • See Chapter 19: Identification and signatures from sigma protocols of Boneh and Shoup online cryptography textbook
  • A recent proposal to standardize sigma protocols

Example: Signal Private Messaging

Signal, secure, open source messaging app

Signal is the world’s most widely used truly private messaging app, and our cryptographic technologies provide extra layers of privacy beyond the Signal app itself. Since launching in 2013, the Signal Protocol—our end-to-end encryption technology—has become the de facto standard for private communication, protecting the contents of billions of conversations in WhatsApp, Google Messages, and many others. Signal also continues to invest in research and development in the pursuit of extending communications privacy.

Example: Signal User Names I

Example: Signal User Names II

From Signal’s Usernames and Ristretto Hashes

  • Usernames consist of a nickname (text), and a discriminator (a number) e.g., WindCadet.1117
  • A commitment to the username is computed as: C = sha512(nickname,discriminator)∗G1​ + nickname∗G2​ + discriminator∗G3. This is sent to signal by owner of username.
  • To connect with another user, you must know their username. From that you compute the commitment and compute a sigma protocol based ZKP that you know the username.

Anonymous Holder Binding: Proving a Pedersen Commitment Setup

  • Holder and verifier know \(g, h \in \mathbb{G}\) (generators)
  • Holder knows: \(\alpha\) and \(\beta\), computes \(u = g^\alpha h^\beta\)
  • Holder gives \(u\) to the verifier and wants to prove they know \(\alpha\) and \(\beta\)
  • where \(\alpha\) is the “secret” and \(\beta\) is the “hiding factor”

Interactive Proof Overview

From A Graduate Course in Applied Cryptography

Interactive Proof Procedure

  1. The prover selects random values \(\alpha_t\) and \(\beta_t\) and computes \(u_t = g^{\alpha_t} h^{\beta_t}\). This value is sent to the verifier.
  2. The verifier selects a random value \(c\) and sends it to the prover.
  3. The prover computes \(\alpha_z = \alpha_t + \alpha c\) and \(\beta_z = \beta_t + \beta c\) and sends them to the prover.
  4. The verifier checks if \(g^{\alpha_z}h^{\beta_z} = u_t \cdot u^c\). If so the proof is accepted.

Proof of Correctness

See A Graduate Course in Applied Cryptography for special soundness and HVZK.

\[\begin{array}{rcl} g^{\alpha_z}h^{\beta_z} & = & g^{\alpha_t + \alpha c}h^{\beta_t + \beta c} \\ & = & g^{\alpha_t} h^{\beta_t} \cdot (g^\alpha h^\beta)^c \\ & = & u_t \cdot u^c \end{array}\]

Blind Signatures 1

From Wikipedia: Blind Signatures

In cryptography a blind signature is a form of digital signature in which the content of a message is disguised (blinded) before it is signed. The resulting blind signature can be publicly verified against the original, unblinded message in the manner of a regular digital signature.

Blind Signatures 2

From Wikipedia: Blind Signatures

Blind signatures are typically employed in privacy-related protocols where the signer and message author are different parties. Examples include cryptographic election systems and digital cash schemes.

BBS Blind Signatures

From BBS Blind Signatures

The BBS digital signature scheme can be extended to support blind signatures functionality. In a blind signatures setting, the user (called the Prover in the context of the BBS scheme) will request a signature on a list of messages, without revealing those messages to the Signer (who can optionally also include messages of their choosing to the signature).

BBS Blind Signature API

  • BlindSign(SK, PK, commitment_with_proof, header, messages, signer_blind), Blind BBS signatures work with a commitment and its proof (from holder).
  • messages are from the issuer
  • BlindProofGen(PK,signature, header, ph, messages, committed_messages, disclosed_indexes, disclosed_commitment_indexes, secret_prover_blind, signer_blind)

BBS Blind Signatures: Formula

From Blind BBS Signatures

  • Commitment formula (Holder computation): commit = Q_2 * secret_prover_blind + J_1 * msg_1 + ... + J_M * msg_M where J_1 to J_M are generators for the holder’s secret (blind) messages
  • Signing Formula 1 (Issuer): B = P1 + Q_1 * domain + H_1 * msg_1 + ... + H_L * msg_L + commit where commit comes from holder
  • Signing Formula 2 (Issuer): A = B * (1 / (SK + e)) where A and e form the final signature.

Anonymous Holder Binding Flow

Final Note: ZKPs for Existing Signatures?

  • Hardware roots of trust and infrastructure currently support ECDSA type signatures
  • Would like to be able to make existing signatures unlinkable
  • How: Come up with a ZKP for ECDSA signatures. This isn’t easy, but new techniques are emerging. Watch this space