CHOAM: The Chaum-Pedersen Orbital Authentication Machine

Introduction⌗

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 it is 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. It’s 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 and then 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 a challenge, the verifier calculates an new number with their challenge number and then sends back the answer. Armed with that answer, the prover calcualtes 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 published their secret information, unlike in other authentication schemes where a password must be sent at least once to the verifier for later checks. In the Chaum-Pedersen protocol and other zero-knowledge protocols, no secret information is leaked at any point in the process.

Simulation & Zero-Knowledge⌗

Zero knowledge is the ability to prove that you know some number, x, without ever revealing x, and to a convincing amount that you can hide if you even really know x, aka the “plausible deniability” factor provided by the above described indistinguishable transcripts. A key property of zero-knowledge protocols is that their transcripts can be “simulated” which is defined as being indistinguishable from a fake or a real prover generating a possible solution for the secret. Indistinguishable transcripts ensures that “zero knowledge” actually is leaked. The simulation protocol run transcripts must be indistinguishable to an outside observer from real or fake protocol runs.

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. But for now, it remains unresolved.

To generate a very large prime number, use opeenssl to generate one.

openssl prime -generate -bits 2048

Generators⌗

If you paid close attention, there was mention of a generator as being necessary to start the Chaum-Pedersen exchange. A generator is a cryptography term that refers to a specific finite group of numbers that can all be represented as g^K for some integer K. There is a lot of thought and design that goes into choosing generator numbers in production cryptography code, but 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. In a single script for demonstration purposes, it looks like this in Rust.

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

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

    // first, set a very large prime number 
    let _p BigUint::parse_bytes(b"29681414807193618078300503894496900591389075175848196575852013250824428361350773898226570528483777365493346325763613640645922124183625513419110102886887985133189255562298626741602809789062309223691579812700352910367842967695657459861851531211067775969455525985867918262546293597343901574119146998553353507903456640060371193924396346542093123090019460491060682335047691431322399204447393320168687318900159478464378155315345832828943811843048146020195167770547183961910489837004875712120862996001092849872095792202183089679972549487934485916851744727433705020777679383830220041324931819169629506145568195857141649730651", 10).unwrap();

    // then declare a generator.
    // let's use 2 for simplicity but normally generators have more thought put into them.
    // generator must not be a multiple of _p.
    let _g = BigUint::from(2u32);

    // x will actually be our "password", or our secret information 
    let _x: BigUint = BigUint::from(42u32);
    
    // Now the prover has their logarithm _h = g^x mod p
    let _h = _g.modpow(&_x, &_p);
    
    // Next, the prover picks a random _r for use in computing a public "key" _t later
    let _r = BigUint::from(rand::thread_rng().gen_range(1u32..100));

    // remember: _g and _p are public information here. _r is the prover's challenge.
    // prover generates a new _t from their previous _r
    // > note: t is what one would save as the _verifier_(server), sent from the _prover_(client) at "sign up time".
    let _t: BigUint = _g.modpow(&_r, &_p);

    // now, verifier (server) would send a random challenge, c 
    let _challenge = BigUint::from(rand::thread_rng().gen_range(0u32..10));

    // prover now takes the challenge and computes an answer from 
    // their own previous _r and the challenge _c
    let _answer = &_r + &_challenge * &_x;
    println!("answer: {}", _answer);

    // next, the verifier checks the answer: 
    let left = _g.modpow(&_answer, &_p);
    let right = (&_t * &_h.modpow(&_challenge, &_p)) % &_p; 

    // left is the prover(client), right is the verifier(server)
    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 pretty similar approach:

  • Select a very large prime p
  • select a generator g that is not a multiple of p
  • Create a commitment - the h in our example above, I believe.
  • Create a challenge - prover sends t to the verifier who then sends back a challenge c
  • Response - the the prover computes the response s = r + cx and sends it to the verifier
  • Verification - the verifier checks if g^s = t * y ^ c mod p is true.

The “logarithm” that you’re proving that you know is h.

gRPC Auth Service & Implementation⌗

Since this is a gRPC service, a protobuf file must be defined and then generated in the code. The Auth service is just three functions - registration, challenge request, and challenge verification. Once challenge verification is successful, the verifier knows that the client is who they say they are and can issue the AuthenticationAnswer which contains the JWT token with appropriate client permissions.

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) {}
}

And the corresponding stubbed out server code looks like this:

use auth::zkp_auth::{auth_server::{Auth, AuthServer}, RegisterResponse, RegisterRequest, AuthenticationChallengeRequest, AuthenticationChallengeResponse, AuthenticationAnswerRequest, AuthenticationAnswerResponse};
use tonic::{transport::Server, Status, Result, Response};

mod auth;

pub struct AuthService {}

#[tonic::async_trait]
impl Auth for AuthService {
    async fn register(&self, request: tonic::Request<RegisterRequest>) -> Result<Response<RegisterResponse>, Status> {
        panic!("TODO")
    }
    async fn create_authentication_challenge(&self, request: tonic::Request<AuthenticationChallengeRequest>) -> Result<Response<AuthenticationChallengeResponse>, Status> {
        panic!("TODO")
    }
    async fn verify_authentication(&self, request: tonic::Request<AuthenticationAnswerRequest>) -> Result<Response<AuthenticationAnswerResponse>, Status>{
        panic!("TODO")
    }
}


#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>>{
    let addr = "[::1]:50051".parse()?;
    let svc = AuthService{ };
    Server::builder()
        .add_service(AuthServer::new(svc))
        .serve(addr)
        .await?;
    Ok(())
}

Conclusions⌗

Overall, this was a cool protocol to learn that has some interesting properties. This was actually the first non-trivial Rust project I have attempted, and it was a great way to learn several production aspects of Rust. Tokio’s gRPC tooling feels intuitive to use and lets you write test with a high degree of confidence that your code is working once they pass. 100% test coverage is easily achievable between cURL commands and gRPC tests, and the iteration loop is fast.

The rest of the code is on Github if you wanna check it out.

The spice must flow.

References⌗