Crate bromberg_sl2

This is an implementation of the Tillich-Zémor-style hash function presented in the paper "Navigating in the Cayley Graph of SL₂(𝔽ₚ)" by Bromberg, Shpilrain, and Vdovina.

Warning

This module is not produced by cryptography experts, but by some random guy. Furthermore, the algorithm was published in 2017, and is itself not at all battle-tested. Only use this library if you either (a) know what you're doing and have read and understood our code, and/or (b) are building something that does not rely heavily on the cryptographic properties of the hash function.

If you are a cryptography expert, we welcome any bug reports or pull requests! We also welcome them if you're not a cryptography expert; this library is quite simple, and should be easy to grok over a coffee with a copy of the paper linked above in hand.

What is this library for?

This library implements a putatively-strong hash function H with the useful property that it gives a monoid homomorphism. This means there is a cheap operation * such that given strings s1 and s2, H(s1 ++ s2) = H(s1) * H(s2).

This property is especially useful for applications where some very long string may be constructed via many different routes, but you'd nonetheless like to be able to quickly rule out unequal strings.

It also allows you to hash parts of your data as you acquire them, and then merge them later in whatever order is convenient. This allows for very flexible hashing schemes.

H has some other cool properties, and is in some limited but potentially-useful sense "provably secure". See Bromberg et al. for details.

How to use this library

This library provides the means to construct HashMatrixes, using hash, which takes a slice of bytes. These hashes can be compared, or serialized to hex strings using to_hex.

use bromberg_sl2::*;
assert_eq!(hash("hello, world!".as_ref()).to_hex(),
  "21fe256b03546bdbc5b1c879d47ff7363df56837eb1782ebbc4bb3f9247a4ddb40679d4b5f4a057767f7147e252e4f5b0fa5");

Hashes may also be composed, using the * operator:

use bromberg_sl2::*;
assert_eq!(
  hash("hello, ".as_ref()) * hash("world!".as_ref()),
  hash("hello, world!".as_ref())
);

Technical Details

We use the A(2) and B(2) matrices as generators, and p = 2^127 - 1 as our prime order, for fast modular arithmetic.

We have not yet attempted to seriously optimize this library, and performance is a secondary goal. As of right now our procedure is about 1/3 as fast as SHA3-512.

We needed an architecture-agnostic cryptographic hash procedure with a monoid homomorphism respecting string concatenation, written in a low-level language. While there are a few implementations of related algorithms, e.g. the venerable but broken Tillich-Zémor hash, from "Hashing with SL₂" , none of them fulfill these desiderata.

Structs

HashMatrix

The type of hash values. Takes up 512 bits of space. Can be created only by composition of the provided BrombergHashable instances, since not all 512-bit sequences are valid hashes (in fact, fewer than 1/4 of them will be valid).

Statics

I

Traits

BrombergHashable

Things that can be hashed using this crate.

Functions

constmatmul	Identical results to the * operator, but slower. Exposed to provide a const version in case you'd like to compile certain hashes into your binaries.
hash	The main export of this library: Give me a byte stream and I'll give you a hash.
hash_strict	This procedure implements the same hash function as hash(), but with a different performance tradeoff. The first time it's invoked, hash computes a 4MiB table of all the hashes for every pair of bytes, which are then used to double hashing speed. For applications that need to do a lot of hashing, this is nearly twice as fast as hash(), but it also requires much more memory and initialization time. As a rule of thumb, if you're going to hash less than 100KiB during your program's execution, you should probably use hash_strict.