Which hash algorithms support binary input of arbitrary bit length?

Question

Background

In theory, hash functions produce a binary number having bounded (often fixed) length from binary data of arbitrary length.

In practice, specifications and implementations constrain the input length to be a multiple of 8. This is reasonable because, in practice, the binary data that clients hash is represented in chunks of bytes (not bits).

Suppose that we want to use hash algorithms in a context that cannot assume the input binary data is chunked into bytes.

For example, we want to compute a hash for a 13-bit data stream 0101111101111.

Further, assume that the value intended by any binary fragment of a length indivisible by 8 is unambiguously distinct from any padded byte-divisible representation.

For example, our system requires that the 13-bit 0101111101111 means something fundamentally different from any 16-bit value (such as the left-padded 0000101111101111 or right-padded 0101111101111000). Consequently, their hashes should be distinct.

Question

• What established hash algorithms are compatible with input binary data of arbitrary bit length?

• What prior work and implementations exist that directly address this limitation of many common algorithms and libraries?

Note

I recognize that the distinction between truncated arbitrary-length binary data and padded byte-chunks could be retrofitted into byte-divisible input by tagging the padded input data with a byte-divisible representation of its truncated length. If a less redundant approach is available, it would seem preferable.

Answer 1

What established hash algorithms are compatible with input binary data of arbitrary bit length?

The specifications of many hash algorithms include provisions for input of binary data of length not a multiple of 8 bits. That includes the sponge-based SHA-3 (SHA3-512, SHA3-384, SHA3-256, SHA3-224) and Merkle-Damgård constructions SHA-2 (SHA-512, SHA-384, SHA-512/256 SHA-512/224, SHA-256, SHA-224), RIPEMD-160 and broken predecessors SHA-1, SHA(-0), MD5, MD4.

Note: of these, only SHA-3 supports truly arbitrary bit length. Others have an upper size limit: 2¹²⁸-1 bits for SHA-512, SHA-384, SHA-512/256 SHA-512/224; or 2⁶⁴-1 bits for SHA-256, SHA-224, RIPEMD-160, SHA-1, SHA(-0), MD5, MD4. Such limit has no practical consequence: reaching 2⁶⁴ bits would require over 17 years of continuous hashing at a rate of 2³² rounds per second, which would require a dedicated ASIC. Parallelization allows faster hash rates but is irrelevant because these hashes are inherently sequential.

However, most implementations and APIs only support byte-sized messages.

What prior work and implementations exist that directly address this limitation of many common algorithms and libraries?

There is no way to build a conformant bit-aware implementation on top of an existing implementation or API that is not. However that's a relatively easy modification of the source code. As illustration, the end of this answer describes C source code for SHA3-512, SHA3-384, SHA3-256, SHA3-224 with bit-sized input. It's a compact single function, portable, passes NIST tests vectors, and is competitively fast. It's main limitation is that the input must be consecutive in memory.

An even easier and secure option is to create a non-standard variant of a hash by using a padding scheme that turns any bitstring into a bytestring in an injective way; then hash the outcome. The most common such padding method is to append a 1 bit, then just as many 0 bits as necessary (possibly none) to reach a multiple of 8 bits. This increases messages size by 1 to 8 bits, the first of which is a 1. That's optimum.

For example, the 10-bit message 0001000010 would become the 16-bit 00010000101100000, which would be the two bytes 10_h 60_h per big-endian convention or 08_h 06_h per little-endian convention (with the bytes expressed in the usual big-endian hexadecimal).

Answer 2

Most common hash algorithms support arbitrary bit strings as input (up to a very large maximum length: $2^{64}-1$ bits or more). This includes MD5, SHA-1, the SHA-2 family, the SHA-3 family, etc.

Working with arbitrary bit strings tends to come naturally for hash functions, since they generally work on words (often 32 bits or 64 bits) but want to support messages that aren't a sequence of words. With such a design, it's not much harder to support arbitrary bit lengths than arbitrary byte lengths.

The Merkle-Damgård construction pads the input to a whole number of blocks. The padding includes the input length in bits.

Finding active support for non-byte-aligned inputs is another matter. Even specifications that allow arbitrary bit-lengths tend to provide only sample vectors that are a whole number of bytes. Reference implementations may or may not support non-byte-aligned inputs. For SHA-3, the simple FIPS interface only supports byte strings (even though FIPS 202 allows arbitrary bit strings), but the general interface for Keccak supports bit strings.

Answer 3

The following general method would work:

1. Append $0$ bits until the length of the bitstream is a multiple of 8. Call the number of bits you had to append $N$. Thus $N$ will be between $0$ and $7$.
2. Append the value of $N$ as a single byte.
3. The result of 1 and 2 is an integral number of bytes.
4. Use whatever hash algorithm you want on these bytes.

To take your example:

0101111101111 would have 000 appended and then 03 appended, making 010111110111100000000011.

0101111101111000 would have nothing appended and then 00 appended, making 010111110111100000000000.

There are many other ways of taking this kind of approach. Use whichever is most convenient.

Answer 4

What established hash algorithms are compatible with input binary data of arbitrary bit length?

Actually, most of them.

All SHA-3 hashes are well defined for any finite bit string, be it 1 bit, 42 bits or $2^{1024}$ bits in length (although the latter might take a while to compute).

SHA-2 is the same, except for a length limit - SHA-256 is defined only for strings of $2^{64}-1$ bits or less; SHA-512 is defined for bit strings of $2^{128}-1$ bits or less. Assuming that you can live within these length limitations, they also meet your requirements.

What prior work and implementations exist that directly address this limitation of many common algorithms and libraries?

The algorithms are not limited - common implementations (libraries) are. Implementations without this limitation are termed "bit-oriented" (as opposed to "byte-oriented").

A quick search of existing SHA-256 libraries didn't come up with one which was 'bit-oriented (however, it would not be that difficult to modify one to make it accept arbitrary bit lengths)

Answer 5

These algorithms take bit strings as input:

• MD4/5/6, SHA-0/1/2/3
• GOST, RIPEMD, Streebog, Tiger, Whirlpool
• Unless NIST screwed up, all 51 first-round SHA-3 candidates, since one requirement was that they work as drop-in replacements for SHA-2 in all applications. This includes BLAKE, CubeHash, ECOH, FSB, Fugue, Grøstl, JH, LANE, Shabal, SIMD, Skein, SWIFFTX.

These algorithms only seem to support byte strings:

• MD2
• BLAKE2/3

MD2 is byte-oriented and was designed for 8-bit CPUs. I can't find any logic behind the dropping of support for arbitrary bit lengths in BLAKE2, when BLAKE had it. The design document at blake2.net says

The counter t counts bytes rather than bits. This simplifies implementations and reduce the risk of error, since target applications measure data volumes in bytes rather than bits. This change increases the amount of data that can be processed by 8 times, compared to BLAKE.

Really, this will just confuse implementors, since every other algorithm uses a bit counter. The increase in maximum message length matters only if you need to hash a message with a length between 2 and 16 exbibytes, and you only have a 32-bit processor to do it on, since the 64-bit version of the hash uses a 128-bit counter.