Crate raffle

A non-cryptographic “vouching” system.

The raffle library offers functionality similar to public key signatures, except without any pretense of cryptographic strength. It lets us pass CheckingParameters to modules so that they can check whether a value looks like it was generated by code with access to the corresponding VouchingParameters, while making it implausibly hard for these checking modules to accidentally generate valid Vouchers for arbitrary values.

Internally, the implementation relies on modular multiplicative inverses, with added asymmetry to catch some misuse (e.g., swapped vouching and checking parameters). Both the vouching function and the checking function are add-multiply (mod 2**64) permutations; for a matching pair of vouching and checking functions, check(vouch(x)) = K - x, where K is u64::from_le_bytes(*b"Vouch!OK").

It’s easy to write code that’ll find the vouching parameters from a set of checking parameters, but the library doesn’t have that functionality, not even in the vouching-to-checking direction. The internal parameter generation code in generate.rs accepts the multiplier for the vouching function and the addend for the checking function, and fills in the blanks for both the vouching and the checking parameters. Any code to extract vouching parameters from checking parameters will hopefully stick out in review, if only because of the large integer constants involved.

The internal modular add-multiply transformation gives us decent bounds on collisions: each instance of the VouchingParameters function is a permutation over the u64s, so we’ll never accept a Voucher generated from the correct VouchingParameters (i.e., whence our CheckingParameters came) but for the wrong u64 value. Otherwise, if two VouchingParameters differ, they’re both affine functions, and thus match for at most one input-output pair… or we could have accidentally generated the same parameters independently, but the parameter space is pretty large (more than 125 bits). All in all, the probability that we’ll accept a Voucher generated from the wrong VouchingParameters is less than 2**-60, assuming the parameters were generated randomly and independently of the vouched value.

That’s far from cryptographic levels of difficulty, but rare enough that any erroneous match is much more likely a sign of hardware failure or deliberate action than just bad luck.

Sample usage

First, generate a Voucher

const VOUCHING_PARAMETERS : VouchingParameters = VouchingParameters::parse_or_die("VOUCH-...");
let value = ...;
let voucher = VOUCHING_PARAMETERS.vouch(digest(&value));
// pass around (voucher, value)

and, on the read side, validate a Voucher with

const CHECKING_PARAMETERS : CheckingParameters = CheckingParameters::parse_or_die("CHECK-...");
let (voucher, value) = ...;
if CHECKING_PARAMETERS.check(digest(&value), voucher) {
    // work with a validated `value`.
}

Validation only tells us that the value was most likely generated by a module with access to the VOUCHING_PARAMETERS that correspond to CHECKING_PARAMETERS. The Voucher could well have been generated for a different message or recipient.

We’re not looking for cryptographic guarantees here, and only want to make it hard for code to accidentally generate valid vouchers when that code should only be able to check them for validity. In most cases, it’s probably good enough to generate fresh parameters at runtime, or to hardcode the parameters in the source, with strings generated by examples/generate_raffle_parameters.

If you need more than that… it’s always possible to load parameters at runtime, but maybe you want real signatures.

Generating parameters

When everything stays in the same process, it’s probably good enough to generate VouchingParameters by passing a (P)RNG to VouchingParameters::generate.

use rand::Rng;
#[derive(Debug)]
enum Never {}

let mut rng = rand::rngs::OsRng {};
VouchingParameters::generate(|| Ok::<u64, Never>(rng.gen())).unwrap();

Otherwise, you can generate parameter strings with the generate_raffle_parameters binary:

$ cargo build --examples
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
$ target/debug/examples/generate_raffle_parameters
VOUCH-ecf8c191680e5394-a0474d8e2618d059-9bf723a6b538fe4a-1dddb95caa81d852
CHECK-9bf723a6b538fe4a-1dddb95caa81d852

The first line is the string representation for a set of VouchingParameters, suitable for VouchingParameters::parse, or, more ergonomically for const values, VouchingParameters::parse_or_die. The second line is the string representation for the corresponding CheckingParameters, suitable for CheckingParameters::parse or CheckingParameters::parse_or_die.

Each invocation of generate_raffle_parameters with no argument gets fresh random bits from the operating system, and is thus expected to generate different parameters. When there are command line arguments, the parameters are instead derived deterministically from these arguments, with BLAKE3:

$ target/debug/examples/generate_raffle_parameters test seed
VOUCH-13df39ed9cd4e2c9-97b5007485c16f9b-76d12fb42cb03d2d-2952336c44217bb8
CHECK-76d12fb42cb03d2d-2952336c44217bb8
$ target/debug/examples/generate_raffle_parameters test seed
VOUCH-13df39ed9cd4e2c9-97b5007485c16f9b-76d12fb42cb03d2d-2952336c44217bb8
CHECK-76d12fb42cb03d2d-2952336c44217bb8

The parameter strings always have the same fixed-width format, so should be easy to grep for. The VOUCHing parameters also include the CHECKing parameters as a suffix, so we can grep for the hex digits to find matching pairs.

Structs

CheckingParameters

CheckingParameters carry enough information to confirm whether a Voucher was generated from a given u64 value using the unknown VouchingParameters associated with the CheckingParameters.

Voucher

A Voucher is a very weakly one-way-transformed value for an arbitrary u64.

VouchingParameters

VouchingParameters let us convert an arbitrary u64 value to a Voucher that can later be checked as matching the initial u64 value, given only the CheckingParameters associated with the VouchingParameters.