Progressive hashing PoC
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
vendor/golang.org/x
.gitignore
.travis.yml
Gopkg.lock
Gopkg.toml
README.md
progressiveHash.go
progressiveHash_test.go

README.md

Progressive hashing

Traditional password stretching functions such as PBKDF2, Scrypt, Bcrypt and Argon2 compute a fixed-length digest from a variable length, low-entropy input. These functions are intentionally slow, possibly with large memory requirements, in order to mitigate dictionary attacks.

The flipside is that in order to verify that an input matches a previously computed hash, the whole computation has to be performed again. This requires significant resources, even if the input doesn't happen to match the expected hash.

This package implements a proof of concept of a progressive hash function, a PBKDF2 variant that can detect a mismatching hash for a given input while doing the computation, and thus return early instead of performing the full computation.

The first output bits of this function are computed as follows:

H(x): BLAKE2B-512(x)
G(r, x): r recursive iterations of H(x)
o: output
N: number of progressive bits in the output
M: total output length
seed: application-specific seed
B(b, x): bit b of x
R0: initial number of iterations
C <- 2

h <- H(seed || pad || in)

r <- R0
h <- G(r, h)
B(0, o) <- B(0, h)

r <- r * C
h <- G(r, h)
B(1, o) <- B(0, h)

...

r <- r * C
h <- G(r, h)
B(n, o) <- B(0, h)

Individual bits of the prefix are computed sequentially and the work factor doubles after every bit.

Finally, the remaining M-N bits are copied from bits of h at the same position.

Computing a full new hash requires a full computation.

However, the verification function can compute the first bit, stop early if it doesn't match, compute the next one only if it does and repeat the process until N bits have been accumulated.

M should be large enough to avoid collisions. The maximum output length is 512 bits.

On the other hand, N should be short enough to produce collisions during the fast part of the computation.

Usage

seed := []byte("test application")
in := []byte("input string")

h, err := progessiveHash.Hash(in, seed, 50000, 8, 256)
if err != nil {
	panic(err)
}

err = progessiveHash.Verify(in, seed, 50000, 8, 256, h)
if err != nil {
	panic(err)
}

// This is unlikely to require a full computation
badIn := []byte("wrong input")
err = progessiveHash.Verify(badIn, seed, 50000, 8, 256, h)
if err != nil {
	panic("verification shouldn't have passed")
}