17 January 2011

Simplifying Keccak's padding rule for round 3

For the third round of the SHA-3 competition, we decided to shorten and simplify the padding rule used in Keccak. We also took the opportunity to provide a fresh new structure in our documentation, in particular for a clean split between general sponge-related aspects and Keccak-specific ones, and between implementation-related aspects and cryptographic ones.

We made the following changes to the Keccak specifications.

  • We shortened and simplified the padding rule. The new padding rule is the pad10*1 rule, which is suitable for a family of sponge functions sharing the same permutation with different rate-capacity pairs. It is simpler to describe and to implement than the previous padding rule. It is also more efficient, as it appends a minimum of 2 bits instead of 25. For long messages, the gain is negligible, but short messages can be 3 bytes longer for the same number of calls to Keccak-f. This aspect is especially relevant when using the duplex construction.
  • We removed the diversifier parameter d. All the fixed-output-length candidates have different bitrates, which already provides diversification between them, hence making d redundant in this case. Diversification between functions using the same bitrate is still possible using more general mechanisms that we describe in our documentation.
  • We removed the restriction on the bitrate r. Previously, the bitrate could only take values that are multiple of 8 bits. Now all the values between 1 and the permutation width are supported. Although a bitrate multiple of 8 bits is a natural choice to avoid undesirable intra-byte bit shuffling on the input blocks, schemes making use of the duplex construction can take advantage of this to propose round-sized input blocks to the application level and put frame bits in a few extra bits.

Note that no changes have been made to Keccak-f.

With this new version, we make the following documents available on our web page.

  • The Keccak reference is the main document that specifies and analyzes the Keccak sponge function family.
  • The Keccak SHA-3 submission is the entry document of the SHA-3 submission, with our proposals for the standard.
  • Keccak implementation overview gives an overview of the implementation aspects, in software and hardware, with or without protection against side-channel attacks.
  • Cryptographic sponge functions gathers our definitions and analysis related to the sponge construction, on which Keccak is based.

And obviously, the implementation packages have been updated and are available for download.