CHOAM is a custom zero-knowledge proof implementation of the Chaum-Pedersen protocol, a challenge-and-response Sigma protocol, for acquiring authentication tokens. It’s written in Rust and distributes a JWT (JSON web token) upon a successful authentication response to the provided challenge.

Zero-knowledge protocols have interesting and even counter-intuitive properties that show up in even simpler exchanges like Chaum-Pedersen. The Chuam-Pedersen protocol, though relatively straightforward, is a powerful primitive that can be applied in many useful ways.

Chaum-Pedersen Primer#

The Chaum-Pedersen protocol is a Sigma protocol. Its major drawback in most applications is that it requires a challenge and response process for any authentication, which adds additional request latency and overhead.

First, two public values, a generator and a very large prime, are agreed upon by two parties. Then, the prover and verifier each calculate a value (referred to in the papers as g and h respectively) based on those two numbers. They choose a random seed value and calculate a second number, their challenge number, referred to as C in the code.

Whenever the verifier (the authentication server) is requested for a challenge, it calculates a new number with their challenge number and then sends back the answer. Armed with that answer, the prover calculates a new challenge response and sends it to the verifier. The verifier can check that the supplied answer is correct without knowing the initial secret value. This is how the protocol operates on zero-knowledge: The prover never publishes their secret information, unlike in other authentication schemes where a password must be sent at least once to the verifier for later checks.

Simulation & Zero-Knowledge#

Zero knowledge is the ability to prove that you know some number, x, without ever revealing x. A key property of zero-knowledge protocols is that their transcripts can be simulated, meaning they must be indistinguishable from a fake or real prover generating a possible solution for the secret.

Very Large Prime Numbers#

The security of modern cryptography is built on the difficulty of factoring very large prime numbers. If a solution is ever discovered to this problem, there will be massive social implications.

To generate a very large prime number, use OpenSSL:

openssl prime -generate -bits 2048

Generators#

A generator in cryptography refers to a specific finite group of numbers that can all be represented as g^K for some integer K. For our purposes, 2 is a perfectly good choice for a generator number.

The Code#

Now that we have our prime number and a generator, the rest of the protocol is just a sequence of exponent and modulo operations. Here’s an example in Rust:

use num_bigint::BigUint;
use rand::Rng;

fn main() {
    println!("** Chaum-Pedersen Sigma Protocol **");

    let p = BigUint::parse_bytes(b"296814148071936180783...", 10).unwrap();
    let g = BigUint::from(2u32);
    let x = BigUint::from(42u32);
    let h = g.modpow(&x, &p);
    let r = BigUint::from(rand::thread_rng().gen_range(1u32..100));
    let t = g.modpow(&r, &p);
    let challenge = BigUint::from(rand::thread_rng().gen_range(0u32..10));
    let answer = &r + &challenge * &x;

    let left = g.modpow(&answer, &p);
    let right = (&t * &h.modpow(&challenge, &p)) % &p;
    if left == right {
        println!("authentication successful: {} == {}", left, right);
    } else {
        println!("authentication failed");
    }
}

Schnorr Protocol#

The Chaum-Pedersen protocol is essentially two passes of the Schnorr protocol setup between the prover and verifier. The Schnorr protocol follows a similar approach:

  • Select a very large prime p
  • Select a generator g that is not a multiple of p
  • Create a commitment (h)
  • Create a challenge (t sent from prover to verifier, verifier responds with c)
  • Response: prover computes s = r + cx and sends it to verifier
  • Verification: verifier checks if g^s = t * y ^ c mod p is true

gRPC Auth Service & Implementation#

Since this is a gRPC service, a protobuf file must be defined and then generated. The Auth service has three functions: registration, challenge request, and challenge verification. Upon successful verification, the verifier issues the AuthenticationAnswer, which contains the JWT token.

syntax = "proto3";
package zkp_auth;

message RegisterRequest {
    string user = 1;
    int64 y1 = 2;
    int64 y2 = 3;
}
message RegisterResponse {}

message AuthenticationChallengeRequest {
    string user = 1;
    int64 r1 = 2;
    int64 r2 = 3;
}
message AuthenticationChallengeResponse {
    string auth_id = 1;
    int64 c = 2;
}

message AuthenticationAnswerRequest {
    string auth_id = 1;
    int64 s = 2;
}
message AuthenticationAnswerResponse {
    string session_id = 1;
}

service Auth {
    rpc Register(RegisterRequest) returns (RegisterResponse);
    rpc CreateAuthenticationChallenge(AuthenticationChallengeRequest) returns (AuthenticationChallengeResponse);
    rpc VerifyAuthentication(AuthenticationAnswerRequest) returns (AuthenticationAnswerResponse);
}

Conclusions#

This was a cool protocol to learn, showcasing extremely interesting properties of simple logarithms. This was actually my first non-trivial Rust project, and it was a great way to learn several production aspects of Rust. Tokio’s gRPC tooling feels intuitive and allows for high confidence in testing. The full code is available on GitHub.

The spice must flow.

References#