## no-std fdh

Full Domain Hash (FDH) for extending the size of a hash digest to an arbitrary length

### 13 releases(7 breaking)

 0.8.1 Jan 31, 2021 Nov 24, 2020 Aug 23, 2020 Jun 21, 2020 Mar 24, 2019

#659 in Cryptography

Used in 7 crates (via rsa-fdh)

MIT/Apache

235KB
508 lines

## Full Domain Hash

A Full Domain Hash (FDH) is a useful cryptographic construction that limits the domain of the digest of a hash function (for example ensuring the digest is less than modulus `n` in RSA). Secondarily, it can also be used to extend the size of a hash digest to an arbitrary length, turning a regular hash function into an XOF hash function.

We construct an FDH by computing a number of cycles where:

`cycles=(target length)/(digest length) + 1`

We then compute:

`FDH(M) = HASH(M||0) || HASH(M||1) || ... || HASH(M||cycles−1)`

Where `HASH` is any hash function, `M` is the message, `||` denotes concatenation, and numerical values are single-byte `u8`.

FDHs are usually used with an RSA signature scheme where the target length is the size of the key, and the domain is less than modulus `n`. See https://en.wikipedia.org/wiki/Full_Domain_Hash

This crate makes extensive use of the `digest` crate's cryptograhic hash traits, so most useful methods are implemented as part of `digest` traits. These traits are re-exported for convenience. See https://github.com/RustCrypto/hashes for a list of compatible hashes.

It should be noted that FDH is not constant-time in relation to the message. While the variable-time natue of a FDH cannot be used to recover the message (except in pathological cases), it can be used to eliminate certain values from the set of all possible values for the message.

## Example

``````  use sha2::Sha256;
use fdh::{FullDomainHash, VariableOutput, Input};

// Expand SHA256 from 256 bits to 1024 bits.
let output_bits = 1024;
let output_bytes = 1024 / 8;
let mut hasher = FullDomainHash::<Sha256>::new(output_bytes)?;
hasher.input(b"ATTACK AT DAWN");
let result = hasher.vec_result();
``````

## `no_std`

This crate also supports `no_std`, so it can be used in embedded or other settings with no allocation.

``````#![no_std]
use sha2::Sha256;

// Expand SHA256 from 256 bits to 512 bits (and beyond!), reading it in 16 byte chunks.
let mut hasher = FullDomainHash::<Sha256>::default();
hasher.input(b"ATTACK AT DAWN");
let mut read_buf = <[u8; 16]>::default();

// If we want, we can just keep going, reading as many bits as we want indefinitely.
``````

## Restricted Domain

This crate also supports getting a digest that is within a specific domain. It follows an algorithim like so:

``````fn digest_in_domain(message, iv):
digest = fdh(message, iv)
while not in_domain(digest):
iv++
digest = fdh(message, iv)
return digest, iv
``````

The method `results_in_domain()` is provided to accomplish this. The helper methods `results_between()`, `results_lt()`, `results_gt()` are provided for the common case where the digest must be in a certain range.

An example that produces a digest that is odd:

``````use sha2::Sha512;
use fdh::{FullDomainHash, Input, VariableOutput};
use num_bigint::BigUint;
use num_integer::Integer;

// Get a full domain hash that is odd
let mut hasher = FullDomainHash::<Sha512>::new(64).unwrap();
hasher.input(b"ATTACKATDAWN");

fn digest_is_odd(digest: &[u8]) -> bool {
BigUint::from_bytes_be(digest).is_odd()
}
let iv = 0;

let (digest, iv) = hasher.results_in_domain(iv, digest_is_odd).unwrap();
``````

## Contributors

1. Patrick Hayes (linkedin) (github) - Available for hire.

~290–495KB
~12K SLoC