SHA-3 SUBMISSION REQUIREMENTS

For full details of the SHA-3 Submission Requirements,
see the Federal Register Notice (November 2, 2007).

Algorithm Specifications and Supporting Documentation

2.B.1 A complete written specification of the algorithm shall be included, consisting of all necessary mathematical operations, equations, tables, diagrams, and parameters that are needed to implement the algorithm. The document shall include design rationale (e.g., the rationale for choosing the specific number of rounds for computing the hashes) and an explanation for all the important design decisions that are made. It should also include 1) any security argument that is applicable, such as a security reduction proof, and 2) a preliminary analysis, such as possible attack scenarios for collision-finding, first-preimage-finding, second-preimage-finding, length-extension attack, multicollision attack, or any cryptographic attacks that have been considered and their results.

In addition, the submitted algorithm may include a tunable security parameter, such as the number of rounds, which would allow the selection of a range of possible security/performance tradeoffs. If such a parameter is provided, the submission document must specify a recommended value for each digest size specified in Section 3, with justification. The submission should also provide any bounds that the designer feels are appropriate for the parameter, including a bound below which the submitter expects cryptanalysis to become practical. The tunable parameter may be used to produce weakened versions of the submitted algorithm for analysis, and permit NIST to select a different security/performance tradeoff than originally specified by the submitter, in light of discovered attacks or other analysis, and in light of the alternative algorithms that are available. NIST will consult with the submitter of the algorithm if it plans to select that algorithm for SHA-3, but with a different parameter value than originally specified by the submitter. Submissions that do not include such a parameter should include a weakened version of the submitted algorithm for analysis, if at all possible.

NIST is open to, and encourages, submissions of hash functions that differ from the traditional Merkle-Damgard model, using other structures, chaining modes, and possibly additional inputs. However, if a submitted algorithm cannot be used directly in current applications of hash functions as specified in FIPS or NIST Special Publications, the submitted algorithm must define a compatibility construct with the same input and output parameters as the SHA hash functions such that it can replace the existing SHA functions in current applications without any loss of security. The replacement of all SHA functions in any standardized application by this compatibility construct shall require no additional modification of the standard application beyond the alteration of any algorithm specific parameters already present in the standard, such as algorithm name and message block length. Submissions may optionally define other variants, constructs, or iterated structures for specific useful applications.

It should be noted that standards which refer to a block length are generally designed with the Merkle-Damgard model in mind, and a number of applications make additional assumptions – for example HMAC implicitly assumes that the message block length is larger than the message digest size. This is not to say that NIST requires the candidate algorithm to satisfy these assumptions, but in cases where the appropriate choice for a parameter such as message block length is not obvious, the submission package must specify a value that will preserve the security properties and functionality of any of the current standard applications.

2.B.2  A statement of the algorithm’s estimated computational efficiency and memory requirements in hardware and software across a variety of platforms shall be included.  At a minimum, the submitter shall state efficiency estimates for the “NIST SHA-3 Reference Platform” (specified in Section 6.B) and for 8-bit processors.  (Efficiency estimates for other platforms may be included at the submitters’ discretion.)  These estimates shall each include the following information, at a minimum:

a. Description of the platform used to generate the estimate, in sufficient detail so that the estimates could be verified in the public evaluation process (e.g., for software running on a PC, include information about the processor, clock speed, memory, operating system, etc.).  For hardware estimates, a gate count (or estimated gate count) should be included.

b. Speed estimate for the algorithm on the platform specified in Section 6.B.  At a minimum, the number of clock cycles required to:

• generate one message digest, and
• set up the algorithm (e.g., build internal tables)

shall be specified for each message digest size required in the Minimum Acceptability Requirements section (Section 3) of this announcement.

c. Any available information on tradeoffs between speed and memory.

2.B.3 A series of Known Answer Tests (KATs) and Monte Carlo Tests (MCTs) shall be included as specified below.  All of these KAT and MCT values shall be submitted electronically, in separate files, on a CD-ROM or DVD as described in Section 2.C.3 .  Each file shall be clearly labeled with header information listing:

1. Algorithm name,
2. Test name,
3. Description of the test, and
4. Message digest size being tested.

All values within the file shall be clearly labeled (e.g., message, message digest, etc.), and shall be in the exact format specified by NIST at http://www.nist.gov/hash-competition.

a. All applicable KATs shall be included that can be used to exercise various features of the algorithm.  A set of KATs shall be included for each message digest size specified in Section 3.  Required KATs include:
 

1. If the candidate algorithm calculates intermediate values (e.g., internal rounds) for a message digest computation, then the submitter shall include known answers for those intermediate values for a 1-block and a 2-block message digest computation for each of the required message digest sizes. Examples of providing such intermediate values for the SHA family of hash functions are available at http://csrc.nist.rip/groups/ST/toolkit/examples.html .
2. If tables are used in the algorithm, then a set of KAT vectors shall be included to exercise every table entry.

Note:  The submitter is encouraged to include any other KATs that exercise different features of the algorithm (e.g., for permutation tables, etc.).  The purposes of these tests shall be clearly described in the file containing the test values.

b. Four MCTs, to be specified at the web site indicated below, shall be included, with message and message digest values, for each of the message digest sizes specified in Section 3.

A link to a description of the required tests will be available at http://www.nist.gov/hash-competition .  Required submission data for the MCTs will also be found at that location.

 2.B.4 A statement of the expected strength (i.e., work factor) of the algorithm shall be included, along with any supporting rationale, for each of the security requirements specified in Sections 4.A.ii and 4.A.iii, and for each message digest size specified in Section 3.

2.B.5 An analysis of the algorithm with respect to known attacks (e.g., differential cryptanalysis) and their results shall be included.

To prevent the existence of possible “trap-doors” in an algorithm, the submitter shall explain the provenance of any constants or tables used in the algorithm, with justification of why these were not chosen to make some attack easier.

The submitter shall provide a list of known references to any published materials describing or analyzing the security of the submitted algorithm.  The submission of copies of these materials (accompanied by a waiver of copyright or permission from the copyright holder for the SHA-3 public evaluation purposes) is encouraged.

2.B.6 A statement that lists and describes the advantages and limitations of the algorithm shall be included.  Such advantages and limitations may address the ability to:

1. implement the algorithm in various environments, including - but not limited to: 8-bit processors (e.g., smartcards), voice applications, satellite applications, or other environments where low power, constrained memory, or limited real-estate are factors.  To demonstrate the efficiency of a hardware implementation of the algorithm, the submitter may include a specification of the algorithm in a nonproprietary Hardware Description Language (HDL).
2. use the algorithm with message digest sizes other than those specified in Section 3.

If the submitter believes that the algorithm has certain features that are deemed advantageous, then these should be listed and described, along with supporting rationale.  Some examples of these features might include, for example: mathematically (rather than empirically) designed tables, statistical basis for inter-round mixing, etc.