Alternative Blake Padding

BLAKE is one of the SHA-3 finalists, and IMO the one most likely to win. So I’ve been looking into it, to see how well it fits my usecases.

I like the design of its compression function, but I don’t like how it handles padding. Its padding adds at least 9 bytes to each message, which can cause an additional compression function call. Most annoyingly for me, message sizes that are powers of two always cause this additional call. This is particularly annoying in tree-hashing, a binary tree with Blake256 in my case, where inner nodes have a size of 64 bytes, and leaves have a slightly bigger power-of-two size, such as 1024. Now without padding the overhead of tree-hashing is one compression function call per leaf. With the original padding it’s three calls, tripling the overhead from around 6% to around 19%.

Definition of the alternative Padding

I’ll suggest an alternative padding, that’s more efficient for certain message lengths, and IMO simpler. I’m not a good cryptographer, so it’s very well possible that this padding is totally insecure. If so, please tell me ;)

Blake256 uses a 64 bit counter variable, that counts the bits of the message up to the current block. Now my suggestion is turning this into a 62 bit counter that counts the bytes of the message and using the other two bits as flags. Bit 63 marks the final block and bit 62 on the final block indicates that bit padding was used.

For each block except the final block, set the counter to the number of bytes up to this point, i.e. to (i+1)*64. For the final block there are three different cases:

  1. If the message length is zero, set the block data to all zero, and the counter to 2^63. This is similar to case 2), except that the padding consists of 512 bits, instead of 0 bits.
  2. If the message length is an integral number of bytes, set the counter to 2^63 | MessageLengthInBytes and pad the message to the next multiple of 512 bits. No padding required if it’s already a multiple of 512 bits.
  3. If the message length isn’t an integral number of bytes, append a single 1 bit, set the counter to 2^63 | 2^62 | MessageLengthInBytes and pad the message to the next multiple of 512 bits. The partial byte counts as a full byte in MessageLengthInBytes.

Then hash the final block.

Consequences of the alternative Padding

  1. The counter values are still unique
  2. The final block is clearly tagged, preventing length extension
  3. The only case where more than Ceiling(MessageLength/BlockSize) compression function calls are needed is the empty message.
  4. The padding is simpler for the common case, where the message consists of bytes. Simply pad with zeros, and set a bit in the counter. It isn’t much more complicated in the bitstream case.
  5. The maximal message length is slightly larger, 2^62-1 bytes = 2^65-8 bits instead of 2^64-1 bits. That difference is irrelevant in practice, but it obviously still fulfills the NIST length requirement.

It’s trivial to transfer this padding to the 128 bit counter Blake512 uses. Just use a 126 bit byte-counter, and use bits 126 and 127 as the flags.