E7-927. Announcing the Development of New Hash Algorithm(s) for the Revision of Federal Information Processing Standard (FIPS) 180-2, Secure Hash Standard

AGENCY:

National Institute of Standards and Technology, Commerce.

ACTION:

Notice and request for comments.

SUMMARY:

A process to develop and standardize one or more new hash algorithms  to augment and revise FIPS 180-2, Secure Hash Standard, is being initiated by the National Institute of Standards and Technology (NIST). As a first step in this process, NIST is publishing draft minimum acceptability requirements, submission requirements, and evaluation criteria for candidate algorithms to solicit public comment. It is intended that the revised hash function standard will specify one or more additional unclassified, publicly disclosed hash algorithms that are available royalty-free worldwide, and are capable of protecting sensitive government information well into the foreseeable future.

The purpose of this notice is to solicit comments on the draft minimum acceptability requirements, submission requirements, and evaluation criteria of candidate algorithms from the public, the cryptographic community, academic/research communities, manufacturers, voluntary standards organizations, and Federal, state, and local government organizations so that their needs can be considered in the process of developing the augmented and revised hash function standard.

DATES:

Comments must be received on or before April 27, 2007.

ADDRESSES:

Written comments should be sent to Mr. William Burr, Attn: Hash Algorithm Requirements and Evaluation Criteria, National Institute of Standards and Technology, 100 Bureau Drive, Stop 8930, Gaithersburg, MD 20899-8930.

Electronic comments should be sent to [e-mail] with a subject line of “Hash Algorithm Requirements and Evaluation Criteria”.

Comments received in response to this notice will be made part of the public record and will be available for inspection on the Web site: http://www.nist.gov/​hash-function.

FOR FURTHER INFORMATION CONTACT:

For general information, contact: Shu-jen Chang, National Institute of Standards and Technology, Stop 8930, Gaithersburg, MD 20899-8930; telephone [phone] or via fax at 301-975-8670.

Technical inquiries regarding the proposed draft acceptability requirements, submission requirements, and evaluation criteria should be sent electronically to [e-mail], or addressed to William Burr, National Institute of Standards and Technology, Stop 8930, Gaithersburg, MD 20899-8930; telephone [phone] or via fax at 301-975-8670 (Attn: Hash Algorithm Requirements and Evaluation Criteria). Answers to germane questions will be posted at http://www.nist.gov/​hash-function. Questions and answers that are not pertinent to this announcement may not be posted.

NIST will endeavor to answer all questions in a timely manner.

SUPPLEMENTARY INFORMATION:

A hash function takes binary data, called the message, and produces a condensed representation, called the message digest. A cryptographic hash function is a hash function that is designed to achieve certain security properties. The Federal Information Processing Standard 180-2, Secure Hash Standard specifies algorithms for computing four cryptographic hash functions—SHA-1, SHA-256, SHA-384, and SHA-512. FIPS 180-2 was issued in August, 2002, superseding FIPS 180-1.

In recent years, several of the non-NIST approved cryptographic hash functions have been successfully attacked, and serious attacks have been published against SHA-1. In response, NIST held two public workshops on cryptographic hash functions, on Oct. 31-Nov. 1, 2005 and Aug. 24-25, 2006, to assess the status of its approved hash functions and to solicit public input on its cryptographic hash function policy and standard. As a result of these workshops, NIST has decided to develop one or more additional hash functions through a public competition, similar to the development process for the Advanced Encryption Standard (AES).

To begin the competition process, NIST has drafted the following minimum acceptability requirements, submission requirements, and evaluation criteria for candidate algorithms. NIST seeks comments on these draft minimum acceptability requirements, submission requirements, and evaluation criteria, as well as suggestions for other criteria and for the relative importance of each individual criterion in the evaluation process. Since neither the submission requirements nor the evaluation criteria have been finalized, and may evolve over time as a result of the public comments that NIST receives, candidate algorithms should NOT be submitted at this time.

Authority: This work is being initiated pursuant to NIST's responsibilities under the Federal Information Security Management Act (FISMA) of 2002, Public Law 107-347.

A. Proposed Draft Minimum Acceptability Requirements for Candidate Algorithms

The draft minimum acceptability requirements for candidate hash algorithms are:

A.1 The algorithm must be publicly disclosed and available on a worldwide, non-exclusive, royalty-free basis.

A.2 The algorithm must be implementable in a wide range of hardware and software platforms.

A.3 The algorithm must support 224, 256, 384, and 512-bit message digests, and must support a maximum message length of at least 264 bits.

B. Proposed Draft Submission Requirements

In order to provide for an orderly, fair, and timely evaluation of candidate algorithms, submission requirements will specify the procedures and supporting documentation necessary to submit a candidate algorithm. The submission package must include the following:

B.1 A complete written specification of the algorithm, including any applicable mathematical equations, tables, and parameters that are needed to implement the algorithm. The documentation must include design rationale; an explanation for all the important design decisions; any security argument that is applicable, such as a security reduction proof; and a preliminary analysis, such as possible attack scenarios for collision-finding, second-preimage-finding, or any cryptographic attacks that have been considered and their results.

In addition, the documentation should suggest one or more parameters of the algorithm that can be modified, or suggest other modification techniques, to enhance the security of the design. A supporting rationale should also be provided. For example, for SHA-1 the number of rounds is a natural parameter to modify to increase the security of the design.

B.2 An ANSI C source language reference implementation and an optimized implementation. The optimized code will be used to compare software performance and memory requirements to the implementations of other submitted algorithms.

B.3 A statement of the estimated computational efficiency and memory requirements in hardware and software across a variety of platforms, including 8-, 32-, and 64-bit platforms.

B.4 A hashing example that maps a specified message into its message digest.

B.5 A statement of issued or pending patents that the submitter believes may be infringed by implementations of this algorithm.

B.6 A statement of advantages and limitations of the submitted algorithm. If the submitter believes that the algorithm has certain advantageous features, then these should be listed and described, along with supporting rationale.

Should NIST later decide to add such features to the evaluation criteria, submitters of candidate algorithms may be asked to provide additional information with respect to these new criteria.

(End of draft submission requirements)

C. Proposed Draft Evaluation Criteria of Candidate Algorithms

Candidate algorithms that meet the minimum acceptability requirements and the submission requirements will be compared, based on the following factors:

• Security,
• Computational efficiency,
• Memory requirements,
• Hardware and software suitability,
• Simplicity,
• Flexibility, and
• Licensing requirements.

With the exception of self-explanatory items in the above list, these evaluation criteria are described below.

C.1 Security

Algorithms will be judged on the following factors:

• The actual security provided by the algorithm as compared to other submitted algorithms (of the same hash length), including (but not limited to) first and second preimage resistance, collision resistance, and resistance to generic attacks (e.g., length extension).
• The extent to which the algorithm output is indistinguishable from a random oracle.
• The soundness of the mathematical basis for the algorithm's security.
• Other security factors raised by the public during the evaluation process, including any attacks which demonstrate that the actual security of the algorithm is less than the strength claimed by the submitter.

Claimed attacks will be evaluated for practicality.

C.2 Cost

C.2.1 Computational efficiency: The evaluation of computational efficiency will be applicable to both hardware and software implementations.

Computational efficiency essentially refers to the throughput of an implementation. NIST will use the optimized software of each submission (discussed in B.2 above) on a variety of platforms and analyze their computation efficiency for a variety of message lengths. The data in the submission packages and any public comments on computational efficiency will also be taken into consideration.

C.2.2 Memory requirements: The memory required for hardware and software implementations of the candidate algorithm will be considered during the evaluation process.

Memory requirements will include such factors as gate counts for hardware implementations, and code size and RAM requirements for software implementations.

NIST will use the optimized software of each submission (discussed in B.2 above) on a variety of platforms and test their memory requirements for a variety of message lengths. The data in the submission packages and any public comments on memory requirements will also be taken into consideration.

C.3 Algorithm and Implementation Characteristics

C.3.1 Flexibility: Candidate algorithms with greater flexibility that meet the needs of more users are preferable. Some examples of “flexibility” include (but are not limited to) the following:

i. The algorithm is parameterizable, e.g. can accommodate additional rounds.

ii. Implementations of the algorithm can be parallelized to achieve higher performance efficiency.

iii. The algorithm can be implemented securely and efficiently in a wide variety of platforms, including constrained environments such as smart cards.

C.3.2 Simplicity: A candidate algorithm will be judged according to relative simplicity of design.

Dated: January 16, 2007.

James E. Hill,

Acting Deputy Director.

Footnotes

1.  In this announcement, the term “has function” and “hash algorithm” are used interchangeably.