Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family, 62212-62220 [E7-21581]

Agencies

• DEPARTMENT OF COMMERCE
• National Institute of Standards and Technology

[Federal Register Volume 72, Number 212 (Friday, November 2, 2007)]
[Notices]
[Pages 62212-62220]
From the Federal Register Online via the Government Printing Office [www.gpo.gov]
[FR Doc No: E7-21581]


-----------------------------------------------------------------------

DEPARTMENT OF COMMERCE

National Institute of Standards and Technology

[Docket No.: 070911510-7512-01]


Announcing Request for Candidate Algorithm Nominations for a New 
Cryptographic Hash Algorithm (SHA-3) Family

AGENCY: National Institute of Standards and Technology, Commerce.

ACTION: Notice and request for nominations for candidate hash 
algorithms.

-----------------------------------------------------------------------

SUMMARY: This notice solicits nominations from any interested party for 
candidate algorithms to be considered for SHA-3, and specifies how to 
submit a nomination package. It presents the nomination requirements 
and the minimum acceptability requirements of a ``complete and proper'' 
candidate algorithm submission. The evaluation criteria that will be 
used to appraise the candidate algorithms are also described.

DATES: Candidate algorithm nomination packages must be received by 
October 31, 2008. Further details are available in section 2.

ADDRESSES: Candidate algorithm submission packages should be sent to: 
Ms. Shu-jen Chang, Information Technology Laboratory, Attention: Hash 
Algorithm Submissions, 100 Bureau Drive--Stop 8930, National Institute 
of Standards and Technology, Gaithersburg, MD 20899-8930.

FOR FURTHER INFORMATION CONTACT: For general information, send e-mail 
to hash-function@nist.gov. For questions related to a specific 
submission package, contact Ms. Shu-jen Chang, National Institute of 
Standards and Technology, 100 Bureau Drive--Stop 8930, Gaithersburg, MD 
20899-8930; telephone: 301-975-2940 or via fax at 301-975-8670, e-mail: 
shu-jen.chang@nist.gov.

SUPPLEMENTARY INFORMATION: This notice contains the following sections:

1. Background
2. Requirements for Candidate Algorithm Submission Packages
    2.A Cover Sheet
    2.B Algorithm Specifications and Supporting Documentation
    2.C Optical Media
    2.D Intellectual Property Statements/Agreements/Disclosures
    2.E General Submission Requirements
    2.F Technical Contacts and Additional Information
3. Minimum Acceptability Requirements
4. Evaluation Criteria
    4.A Security
    4.B Cost
    4.C Algorithm and Implementation Characteristics
5. Initial Planning for the First SHA-3 Candidate Conference
6. Plans for the Candidate Evaluation Process
    6.A Overview
    6.B Round 1 Technical Evaluation
    6.C Round 2 Technical Evaluation
7. Miscellaneous

    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.

1. Background

    Modern, collision resistant hash functions were designed to create 
small, fixed size message digests so that a digest could act as a proxy 
for a possibly very large variable length message in a digital 
signature algorithm, such as RSA or DSA. These hash functions have 
since been widely used for many other ``ancillary'' applications, 
including hash-based message authentication codes, pseudo random number 
generators, and key derivation functions.
    A series of related hash functions have been developed, such as 
MD4, MD5, SHA-0, SHA-1 and the SHA-2 family, (which includes 224, 256, 
384 and 512-bit variants); all of these follow the Merkle-Damgard 
construct. NIST began the standardization of the SHA hash functions in 
1993, with a specification of SHA-0 in the Federal Information 
Processing Standards Publication (FIPS PUBS) 180, the Secure Hash 
Standard; subsequent revisions of the FIPS have replaced SHA-0 with 
SHA-1 and added the SHA-2 family in FIPS 180-1 and FIPS 180-2, 
respectively.
    Recently, cryptanalysts have found collisions on the MD4, MD5, and 
SHA-0 algorithms; moreover, a method for finding SHA-1 collisions with 
less than the expected amount of work has been published, although at 
this time SHA-1 collisions have not yet been demonstrated. Although 
there is no specific reason to believe that a practical attack on any 
of the SHA-2 family of hash functions is imminent, a successful 
collision attack on an algorithm in the SHA-2 family could have 
catastrophic effects for digital signatures.
    NIST has decided that it is prudent to develop a new hash algorithm 
to augment and revise FIPS 180-2. The new hash algorithm will be 
referred to as ``SHA-3'', and will be developed through a public 
competition, much like the development of the Advanced Encryption 
Standard (AES). NIST intends that SHA-3 will specify an unclassified, 
publicly disclosed algorithm(s), which is available worldwide without 
royalties or other intellectual property restrictions, and is capable 
of protecting sensitive information for decades. Following the close of 
the submission period, NIST intends to make all ``complete and proper'' 
(as defined in section 3) submissions publicly available for review and 
comment.
    NIST does not currently plan to withdraw SHA-2 or remove it from 
the revised Secure Hash Standard; however, it is intended that SHA-3 
can be directly substituted for SHA-2 in current applications, and will 
significantly improve the robustness of NIST's overall hash algorithm 
toolkit. Therefore, the submitted algorithms for SHA-3 must provide 
message digests of 224, 256, 384 and 512 bits to allow substitution for 
the SHA-2 family. The 160-bit hash value produced by SHA-1 is becoming 
too small to use for digital signatures, therefore, a 160-bit 
replacement hash algorithm is not contemplated.
    Many cryptographic applications that are currently specified in 
FIPS and NIST Special Publications require the use of a NIST-approved 
hash algorithm. These publications include:
     FIPS 186-2, Digital Signature Standard;
     FIPS 198, The Keyed-Hash Message Authentication Code 
(HMAC);
     SP 800-56A, Recommendation for Pair-Wise Key Establishment 
Schemes Using Discrete Logarithm Cryptography; and
     SP 800-90, Recommendation for Random Number Generation 
Using Deterministic Random Bit Generators (DRBGs).


[[Page 62213]]


The SHA-3 algorithm is expected to be suitable for these applications.

    Since SHA-3 is expected to provide a simple substitute for the SHA-
2 family of hash functions, certain properties of the SHA-2 hash 
functions must be preserved, including the input parameters; the output 
sizes; the collision resistance, preimage resistance, and second-
preimage resistance properties; and the ``one-pass'' streaming mode of 
execution. However, it is also desirable that the selected SHA-3 
algorithm offer features or properties that exceed, or improve upon, 
the SHA-2 hash functions. For example, the selected SHA-3 algorithm may 
offer efficient integral options, such as randomized hashing, that 
fundamentally improve security, or it may be parallelizable, more 
efficient to implement on some platforms, more suitable for certain 
applications, or may avoid some of the incidental ``generic'' 
properties (such as length extension) of the Merkle-Damgard construct 
that often result in insecure applications.
    NIST expects SHA-3 to have a security strength that is at least as 
good as the hash algorithms currently specified in FIPS 180-2, and that 
this security strength will be achieved with significantly improved 
efficiency. NIST also desires that the SHA-3 hash functions will be 
designed so that a possibly successful attack on the SHA-2 hash 
functions is unlikely to be applicable to SHA-3. The SHA-3 family 
should be suitably flexible for a wide variety of implementations, even 
though it may not operate with optimal efficiency in each and every 
potential application.
    For interoperability, NIST strongly desires a single hash algorithm 
family (that is, that different size message digests be internally 
generated in as similar a manner as possible) to be selected for SHA-3. 
However, if more than one suitable candidate family is identified, and 
each provides significant advantages, NIST may consider recommending 
more than one family for inclusion in the revised Secure Hash Standard.

2. Requirements for Candidate Algorithm Submission Packages

    Candidate algorithm nomination packages must be received by October 
31, 2008. Submission packages received before August 31, 2008 will be 
reviewed for completeness by NIST; the submitters will be notified of 
any deficiencies by September 30, 2008, allowing time for deficient 
packages to be amended by the submission deadline. No amendments to 
packages will be permitted after the submission deadline. Requests for 
the withdrawal of submission packages will only be honored until the 
submission deadline.
    Due to the specific requirements of the submission package such as 
Intellectual Property Statements / Agreements / Disclosures as 
specified in section 2.D, e-mail submissions will not be accepted for 
these statements or for the initial submission package. However, e-mail 
submissions of amendments to the initial submission package will be 
allowed prior to the submission deadline.
    ``Complete and proper'' submission packages received in response to 
this notice will be posted at https://www.nist.gov/hash-competition for 
inspection. To be considered as a ``complete'' submission package (and 
continue further in the hash algorithm consideration process), 
candidate algorithm submission packages must contain the following (as 
described in detail below):
     Cover Sheet.
     Algorithm Specifications and Supporting Documentation.
     Optical Media.
     Intellectual Property Statements/Agreements/Disclosures.
     General Submission Requirements.

Each of these items is discussed in detail below.

2.A Cover Sheet

    A cover sheet shall contain the following information:
     Name of the submitted algorithm.
     Principal submitter's name, e-mail address, telephone, 
fax, organization, and postal address.
     Name(s) of auxiliary submitter(s).
     Name of the algorithm inventor(s)/developer(s).
     Name of the owner, if any, of the algorithm. (normally 
expected to be the same as the submitter).
     Signature of the submitter.
     (optional) Backup point of contact (with telephone, fax, 
postal address, e-mail address).

2.B 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.

[[Page 62214]]

    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:
    1. Generate one message digest, and
    2. 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 https://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:
    i. 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: https://
www.nist.gov/CryptoToolkitExamples.
    ii. 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 
https://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:
    a. 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).
    b. 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.

2.C Optical Media

    All electronic data shall be provided on a single CD-ROM or DVD 
labeled with the submitter's name, and the algorithm name.
2.C.1 Reference Implementation
    A reference implementation shall be submitted in order to promote 
the understanding of how the candidate algorithm may be implemented. 
This implementation shall consist of source code written in ANSI C; 
appropriate comments should be included in the code, and the code 
should clearly map to the algorithm description included under section 
2.B.1. Since this implementation is intended for reference purposes, 
clarity in programming is more important than efficiency.
    The reference implementation shall be capable of fully 
demonstrating the operation of the candidate algorithm. The reference 
implementation shall support all message digest sizes specified in 
section 3. Additionally, it must support all other message digest sizes 
that are claimed to be supported by the algorithm.
    NIST will specify a set of cryptographic service calls, namely a 
cryptographic API, for the ANSI C implementations, which will be made 
available at https://www.nist.gov/hash-competition. All ANSI C 
submissions shall implement that API so that the

[[Page 62215]]

NIST test system can be compatible with all the submissions.
    Separate source code for implementing the required KATs with the 
reference implementation shall also be included. This code shall be 
able to process input specified in the format indicated by NIST (on the 
web site as referred to under section 2.B.3) and run the required 
tests.
    The reference implementation shall be provided in a directory 
labeled: \Reference Implementation.
2.C.2 Optimized Implementations
    Two optimized implementations of the candidate algorithm shall be 
submitted--one implementation that is optimized for a 32-bit platform, 
and another for a 64-bit platform. The optimized implementations shall 
be specified in the ANSI C programming language. These implementations 
will be evaluated on 32- and 64-bit platforms.
    General Requirements for Both Optimized Implementations:
     Both of the optimized implementations shall support the 
message digest sizes specified in section 3.
     Separate source code for implementing the required KATs 
and MCTs with the optimized implementations shall also be included. 
This code shall be able to process the input specified in the format 
indicated by NIST (on the Web site as referred to under section 2.B.3) 
and run the required tests.
     The submitter shall provide the optimized implementations 
in two separate directories labeled:

[cir] \Optimized--32 bit
[cir] \Optimized--64 bit

respectively.
     Additionally, submitters may, at their discretion, submit 
revised optimized implementations (for both the 32- and 64-bit 
implementations) for use in the Round 2 evaluation process, allowing 
additional time for improvements. These must be received prior to the 
beginning of the Round 2 evaluation; submitters will be notified of the 
specific deadline, as appropriate. Note that the optimized 
implementations on file with NIST at the close of the initial 
submission period will be the ones used by NIST in the Round 1 
evaluation.
2.C.3 Test Values--Known Answer Tests and Monte Carlo Tests
    The files on the CD-ROM or DVD shall contain all of the test values 
required under section 2.B.3 of this announcement. That section 
includes descriptions of the required tests, as well as a list of the 
values that must be provided.
    The required format for the test vectors will be specified by NIST 
at https://www.nist.gov/hash-competition.
    The test values shall be provided in a directory labeled: \KAT--
MCT.
2.C.4 Supporting Documentation
    To facilitate the electronic distribution of submissions to all 
interested parties, copies of all written materials must also be 
submitted in electronic form in PDF. Submitters are encouraged to use 
the thumbnail and bookmark features, to have a clickable table of 
contents (if applicable), and to include other links within the PDF as 
appropriate.
    This electronic version of the supporting documentation shall be 
provided in a directory labeled: [bs]Supporting 
Documentation.
2.C.5 General Requirements for Optical Media
    For the portions of the submissions that may be provided 
electronically, the information shall be provided on a single CD-ROM or 
DVD using the ISO 9660 format. This disc shall have the following 
structure:
     [bs]README.
     [bs]Reference Implementation.
     [bs]Optimized--32 bit.
     [bs]Optimized--64 bit.
     [bs]KAT--MCT.
     [bs]Supporting Documentation.

    The ``README'' file shall list all files that are included on this 
disc with a brief description of each.

    All optical media presented to NIST must be free of viruses or 
other malicious code. The submitted media will be scanned for the 
presence of such code. If malicious code is found, NIST will notify the 
submitter and ask that a clean version of the optical media be re-
submitted.
    NIST will define a set of cryptographic service calls for the ANSI 
C implementations. These calls will be used by the NIST test software 
to make appropriate calls to the optimized and reference 
implementations, so that the test software does not have to be 
rewritten for each submitted algorithm. Therefore, both the optimized 
and reference implementations are required to conform to these specific 
calls. The implementations shall be supplied in source code so that 
NIST can compile and link them appropriately with the test software. 
The two selected sets of required calls will be available at the 
following location: https://www.nist.gov/hash-competition. NIST intends 
to make these available within three months after publication of this 
notice.

2.D Intellectual Property Statements/Agreements/Disclosures

    Each submitted algorithm must be available worldwide on a royalty 
free basis during the period of the hash function competition. In order 
to ensure this and minimize any intellectual property issues, the 
following series of signed statements are required for a submission to 
be considered complete: Statement by the Submitter, Statement by Patent 
(and Patent Application) Owner(s) (if applicable), and Statement by 
Reference/Optimized Implementations' Owner(s). Note for the last two 
statements, separate statements must be completed if multiple 
individuals are involved.
2.D.1 Statement by the Submitter
    I, -------- (print submitter's full name) do hereby declare that, 
to the best of my knowledge, the practice of the algorithm, reference 
implementation, and optimized implementations that I have submitted, 
known as -------- (print name of algorithm), may be covered by the 
following U.S. and/or foreign patents: -------- (describe and enumerate 
or state ``none'' if appropriate).
    I do hereby declare that I am aware of no patent applications that 
may cover the practice of my submitted algorithm, reference 
implementation or optimized implementations.--OR--I do hereby declare 
that the following pending patent applications may cover the practice 
of my submitted algorithm, reference implementation or optimized 
implementations:-------- (describe and enumerate).
    I do hereby understand that my submitted algorithm may not be 
selected for inclusion in the Secure Hash Standard. I also understand 
and agree that after the close of the submission period, my submission 
may not be withdrawn from public consideration for SHA-3. I further 
understand that I will not receive financial compensation from the U.S. 
Government for my submission. I certify that, to the best of my 
knowledge, I have fully disclosed all patents and patent applications 
relating to my algorithm. I also understand that the U.S. Government 
may, during the course of the lifetime of the SHS or during the FIPS 
public review process, modify the algorithm's specifications (e.g., to 
protect against a newly discovered vulnerability). Should my submission 
be selected for SHA-3, I hereby agree not to place any restrictions on 
the use of the algorithm, intending it to be available on a

[[Page 62216]]

worldwide, non-exclusive, royalty-free basis.
    I do hereby agree to provide the statements required by Sections 
2.D.2 and 2.D.3, below, for any patent or patent application identified 
to cover the practice of my algorithm, reference implementation or 
optimized implementations and the right to use such implementations for 
the purposes of the SHA-3 evaluation process.
    I understand that NIST will announce the selected algorithm(s) and 
proceed to publish the draft FIPS for public comment. If my algorithm 
(or the derived algorithm) is not selected for SHA-3 (including those 
that are not selected for the second round of public evaluation), I 
understand that all rights, including use rights of the reference and 
optimized implementations, revert back to the submitter (and other 
owner[s], as appropriate). Additionally, should the U.S. Government not 
select my algorithm for SHA-3 at the time NIST ends the competition, 
all rights revert to the submitter (and other owner[s] as appropriate).

Signed:
Title:
Dated:
Place:
2.D.2 Statement by Patent (and Patent Application) Owner(s)
    If there are any patents (or patent applications) identified by the 
submitter, including those held by the submitter, the following 
statement must be signed by each and every owner of the patent and 
patent applications above identified.
    I, -------- (print full name), of -------- (print full postal 
address), am the owner or authorized representative of the owner (print 
full name, if different than the signer) of the following patent(s) and 
or patent application(s): -------- (enumerate), and do hereby agree to 
grant to any interested party if the algorithm known as -------- (print 
name of algorithm) is selected for SHA-3, an irrevocable nonexclusive 
royalty-free license to practice the referenced algorithm, reference 
implementation or the optimized implementations. Furthermore, I agree 
to grant the same rights in any other patent application or patent 
granted to me or my company that may be necessary for the practice of 
the referenced algorithm, reference implementation, or the optimized 
implementations.

Signed:
Title:
Dated:
Place:

    Note that the U.S. Government may conduct research as may be 
appropriate to verify the availability of the submission on a royalty 
free basis worldwide.
2.D.3 Statement by Reference/Optimized Implementations' Owner(s)
    The following must also be included:
    I,--------(print full name), am the owner of the submitted 
reference implementation and optimized implementations and hereby grant 
the U.S. Government and any interested party the right to use such 
implementations for the purposes of the SHA-3 evaluation process, 
notwithstanding that the implementations may be copyrighted.

Signed:
Title:
Dated:
Place:

2.E General Submission Requirements

    NIST welcomes both domestic and international submissions; however, 
in order to facilitate analysis and evaluation, it is required that the 
submission packages be in English. This requirement includes the cover 
sheet, algorithm specification and supporting documentation, source 
code, and intellectual property information. Any required information 
that is submitted in a language other than English shall render the 
submission package ``incomplete.'' Optional supporting materials (e.g., 
journal articles) in another language may be submitted.
    Classified and/or proprietary submissions will not be accepted.

2.F Technical Contacts and Additional Information

    For technical inquiries, send e-mail to hash-function@nist.gov, or 
contact Mr. William Burr, National Institute of Standards and 
Technology, 100 Bureau Drive--Stop 8930, Gaithersburg, MD 20899-8930; 
telephone: 301-975-2914 or via fax at 301-975-8670, e-mail: 
william.burr@nist.gov (Attn: Hash Algorithm Competition Questions).
    Answers to germane questions will be posted at https://www.nist.gov/
hash-competition. 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.

3. Minimum Acceptability Requirements

    Those packages that are deemed to be ``complete'' will be evaluated 
for the inclusion of a ``proper'' candidate algorithm. To be considered 
as a ``proper'' candidate algorithm submission (and continue further in 
the SHA-3 Development Process), a candidate hash algorithm shall meet 
the following minimum acceptability requirements:
    1. The algorithm shall be publicly disclosed and available 
worldwide without royalties or any intellectual property restrictions.
    2. The algorithm shall be implementable in a wide range of hardware 
and software platforms.
    3. The candidate algorithm shall be capable of supporting message 
digest sizes of 224, 256, 384, and 512 bits, and shall support a 
maximum message length of at least 2\64\-1 bits. Submitted algorithms 
may support other message digest sizes and maximum message lengths, and 
such features will be taken into consideration during the analysis and 
evaluation period.

(End of minimum acceptability requirements).

    A candidate algorithm submission package that is complete (as 
defined above) and whose algorithm meets the minimum acceptability 
requirements (as defined immediately above) will be deemed to be a 
``complete and proper'' submission. A submission that is deemed 
otherwise at the close of the submission period will receive no further 
consideration. Submissions that are ``complete and proper'' will be 
posted at https://www.nist.gov/hash-competition for public review.

4. Evaluation Criteria

    In order to provide a basis for the analysis and evaluation of hash 
algorithms submitted to be considered for SHA-3, evaluation criteria 
will be used to review candidate algorithms. NIST will form an internal 
selection panel composed of NIST employees to analyze the candidate 
algorithms; the evaluation process will be discussed in section 6. All 
of NIST's analysis results will be made publicly available.
    Although NIST will be performing its own analyses of the candidate 
algorithms, NIST strongly encourages public evaluation and publication 
of the results, including any complete or partial analysis of a 
candidate algorithm or component of an algorithm (e.g., the compression 
function or iterative structure), and whether the result is positive or 
negative. NIST will take into account its own analysis, as well as the 
public comments that are received in response to the posting of the 
``complete and proper'' submissions, to make its decision on the 
selection of SHA-3.
    Candidate algorithms with submission packages deemed to be 
``complete and proper'' will be compared, based on the following

[[Page 62217]]

factors (ranked in the order of relative importance):

 4.A Security

    The security provided by an algorithm is the most important factor 
in the evaluation. Algorithms will be judged on the following factors:
 i. Applications of the Hash Functions
    Algorithms having the same hash length will be compared for the 
security that may be provided in a wide variety of cryptographic 
applications, including digital signatures (FIPS 186-2), key derivation 
(NIST Special Publication 800-56A), hash-based message authentication 
codes (FIPS 198), deterministic random bit generators (SP 800-90), and 
additional applications that may be brought up by NIST or by the public 
during the evaluation process. Claimed applications of the hash 
functions will be evaluated for their practical importance if this 
evaluation is necessary for comparing the submitted hash algorithms.
ii. Specific Requirements When Hash Functions Are Used To Support HMAC, 
Pseudo Random Functions (PRFs), and Randomized Hashing
    NIST requires that the selected SHA-3 support HMAC, PRFs, and 
randomized hashing. Each candidate algorithm must have at least one 
construction to support HMAC as a PRF; it may have additional 
constructions for other, non-HMAC based PRFs, or for use in a 
randomized hashing scheme. The following criteria will be used to 
evaluate each candidate algorithm of message digest size n in such 
constructions.
     When the candidate algorithm is used with HMAC to 
construct a PRF as specified in the submitted package, that PRF must 
resist any distinguishing attack that requires much fewer than 
2n/2 queries and significantly less computation than a 
preimage attack.
     Any additional PRF constructions specified for use with 
the candidate algorithm must provide the security that is claimed in 
the submission document.
     If a construct is specified for the use of the candidate 
algorithm in a randomized hashing scheme, the construct must, with 
overwhelming probability, provide n bits of security against the 
following attack: The attacker chooses a message, M1. The specified 
construct is then used on M1 with a randomization value r1 that has 
been randomly chosen without the attacker's control after the attacker 
has supplied M1. Given r1, the attacker then attempts to find a second 
message M2 and randomization value r2 that yield the same randomized 
hash value.
 iii. Additional Security Requirements of the Hash Functions
    In addition to the specific requirements mentioned above, NIST 
expects the SHA-3 algorithm of message digest size n to meet the 
following security requirements at a minimum. These requirements are 
believed to be satisfiable by fairly standard hash algorithm 
constructions; any result that shows that the candidate algorithm does 
not meet these requirements will be considered to be a serious attack.
     Collision resistance of approximately n/2 bits,
     Preimage resistance of approximately n bits,
     Second-preimage resistance of approximately n-k bits for 
any message shorter than 2k bits,
     Resistance to length-extension attacks, and
     Any m-bit hash function specified by taking a fixed subset 
of the candidate function's output bits is expected to meet the above 
requirements with m replacing n. (Note that an attacker can choose the 
m-bit subset specifically to allow a limited number of precomputed 
message digests to collide, but once the subset has been chosen, 
finding additional violations of the above properties is expected to be 
as hard as described above.)
    Increasing the second preimage resistance property and resistance 
against other attacks, such as multicollision attacks, will be viewed 
positively by NIST; however, this could also have performance 
implications. Submitters should be prepared to argue for their overall 
security/performance trade-offs.
iv. Evaluations Relating to Attack Resistance
    Hash algorithms will be evaluated against attacks or observations 
that may threaten existing or proposed applications, or demonstrate 
some fundamental flaw in the design, such as exhibiting nonrandom 
behavior and failing statistical tests.
    Claimed attacks will be evaluated for their practicality and for 
their impact on applications. Attacks that violate the security of an 
existing FIPS or NIST Special Publication's use of a hash function will 
be given more weight than attacks that violate the security of other 
applications; and attacks on rare or obscure applications may be given 
relatively little weight.
    Hash algorithms will be evaluated not only for their resistance 
against previously known attacks, but also for their resistance against 
attacks discovered during the evaluation process, and for their 
likelihood of resistance against future attacks.
 v. Other Consideration Factors
    In addition to the evaluation factors mentioned above, the quality 
of the security arguments/proofs, the clarity of the documentation of 
the algorithm, the quality of the analysis on the algorithm performed 
by the submitters, the simplicity of the algorithm, and the confidence 
of NIST and the cryptographic community in the algorithm's long-term 
security may all be considered.

4.B Cost

    As described in section 2.C.2, submitters of hash algorithms may 
submit revised optimized implementations for use in the Round 2 
evaluation process. In the following discussion, it should be noted 
that all technical evaluations are performed either on the optimized 
implementations that are received initially, or on the revised 
implementations that are received before the beginning of Round 2.
    i. Computational efficiency: The evaluation of the computational 
efficiency of the candidate algorithms will be applicable to both 
hardware and software implementations. The Round 1 analysis by NIST 
will focus primarily on software implementations; hardware 
implementations will be addressed more thoroughly during the Round 2 
analysis.
    Computational efficiency essentially refers to the speed of the 
algorithm. The computational efficiency will be analyzed using each 
submission's optimized implementations on a variety of platforms as 
specified in Section 6.B, and for a variety of input message lengths. 
The data in the submission packages and public comments on each 
algorithm's efficiency (particularly for various platforms and 
applications) will also be taken into consideration by NIST.
    ii. Memory requirements: The memory required to implement a 
candidate algorithm--for both hardware and software implementations of 
the algorithm--will also be considered during the evaluation process. 
The Round 1 analysis will focus primarily on software implementations; 
hardware implementations will be addressed more thoroughly during Round 
2.
    Memory requirements will include such factors as gate counts for 
hardware implementations, and code size and RAM requirements for 
software implementations.

[[Page 62218]]

    Testing will be performed by NIST using the optimized 
implementations provided by the submitters. Memory requirement 
estimates (for different platforms and environments) that are included 
in the submission package or the revised optimization package will also 
be taken into consideration by NIST. Input from the public evaluations 
of each algorithm's memory requirements (particularly for various 
platforms and applications) will also be taken into consideration by 
NIST.

4.C Algorithm and Implementation Characteristics

    i. Flexibility: Candidate algorithms with greater flexibility will 
meet the needs of more users than less flexible algorithms, and 
therefore, are preferable. However, some extremes of functionality are 
of little practical use (e.g., extremely short message digest 
lengths)--for those cases, preference will not be given.
    Some examples of ``flexibility'' may include (but are not limited 
to) the following:
    a. The algorithm has a tunable parameter which allows the selection 
of a range of possible security/performance tradeoffs.
    b. The algorithm can be implemented securely and efficiently on a 
wide variety of platforms, including constrained environments, such as 
smart cards.
    c. Implementations of the algorithm can be parallelized to achieve 
higher performance efficiency.
    ii. Simplicity: A candidate algorithm will be judged according to 
its relative design simplicity.

5. Initial Planning for the First SHA-3 Candidate Conference

    An open public conference will be held shortly after the end of the 
submission period, at which the submitter of each complete and proper 
submission package will be invited to publicly discuss and explain 
their candidate algorithm. The documentation for these candidate 
algorithms will be made available at the Conference. Details of the 
conference will be posted at https://www.nist.gov/hash-competition.

6. Plans for the Candidate Evaluation Process

    NIST plans to form an internal selection panel composed of NIST 
employees for the technical evaluations of the candidate algorithms. 
This panel will analyze the submitted algorithms, review public 
comments that are received in response to the posting of the ``complete 
and proper'' submissions, and all presentations, discussions and 
technical papers presented at the SHA-3 Candidate Conferences, as well 
as other pertinent papers and presentations made at other cryptographic 
research conferences and workshops. NIST will issue a report on each 
SHA-3 Candidate Conference, make a final selection and document the 
technical rationale for that selection in a final report, as NIST did 
in the selection of AES. The following is an overview of the envisioned 
SHA-3 candidate review process.

6.A Overview

    Following the close of the call for candidate algorithm submission 
packages, NIST will review the received packages to determine which are 
``complete and proper,'' as described in sections 2 and 3 of this 
notice. NIST will post all ``complete and proper'' submissions at 
https://www.nist.gov/hash-competition for public inspection. To help 
inform the public, the First SHA-3 Candidate Conference will be held at 
the start of the public comment process to allow submitters to publicly 
explain and answer questions regarding their submissions.
    Round 1 will consist of a twelve-month public review of the first 
round candidate algorithms. During the Round 1 public review, NIST 
intends to evaluate the candidate algorithms as outlined in Section 
6.B. NIST will review the public evaluations of the candidate 
algorithms' cryptographic strengths and weaknesses, and will use these 
to narrow the candidate pool for more careful study and analysis during 
Round 2.
    Because of limited resources, and also to avoid moving evaluation 
targets (i.e., modifying the submitted algorithms undergoing public 
review), NIST will NOT accept modifications to the submitted algorithms 
during Round 1.
    For informational and planning purposes, near the end of the Round 
1 public evaluation process, NIST intends to hold the Second SHA-3 
Candidate Conference. Its purpose will be to publicly discuss the SHA-3 
candidate algorithms, and to provide NIST with information for 
narrowing the field of algorithms to be considered for SHA-3.
    NIST plans to narrow the field of candidates to approximately five 
candidate algorithms for further analysis during Round 2, based upon 
its own analysis, public comments, and all other available information. 
It is envisioned that this narrowing will be done primarily on 
security, efficiency, and intellectual property considerations. For 
those candidate algorithms not selected for Round 2, the rights to use 
the algorithms will be returned to their respective submitters.
    Before the start of the Round 2 evaluation period, the submitters 
of the Round 2 candidate algorithms will have the option of providing 
updated optimized implementations for use during the second phase of 
evaluation. During the course of the Round 1 evaluations, it is 
conceivable that some small deficiencies may be identified in even some 
of the most promising candidates. Therefore, for the Round 2 
evaluations, small modifications to the submitted algorithms will be 
permitted for either security or efficiency purposes. Submitters may 
submit minor changes (no substantial redesigns), along with a 
supporting explanation/justification that must be received by NIST 
prior to the beginning of Round 2. (Submitters will be notified by NIST 
of the exact deadline.) NIST will determine whether or not the proposed 
modification would significantly affect the design of the algorithm, 
requiring a major re-evaluation; if such is the case, the modification 
will not be accepted. If modifications are submitted, new reference and 
optimized implementations and written descriptions shall be provided by 
the start of Round 2. This will allow a public review of the modified 
algorithms during the entire course of the Round 2 evaluation.

    Note: All proposed changes for Round 2 must be proposed by the 
submitter; no proposed changes (to the algorithm or implementations) 
will be accepted from a third party.

    Round 2 will consist of a twelve to fifteen month public review of 
the Round 2 candidate algorithms. During the public review, NIST will 
evaluate the candidate algorithms as outlined in the two sections 
below. After the end of the public review period, NIST intends to hold 
the Third SHA-3 Candidate Conference. (The exact date is to be 
scheduled.)
    Following the Third SHA-3 Candidate Conference, NIST will select 
the algorithm(s) for SHA-3. The selected algorithm(s) will be 
incorporated into a draft FIPS, which will be announced in the Federal 
Register for public comment.
    It should be noted that this schedule for the SHA-3 development is 
somewhat tentative, depending upon the type, quantity, and quality of 
the submissions. Specific conference dates and public comment periods 
will be announced at appropriate times in the future.

[[Page 62219]]

6.B Round 1 Technical Evaluation

    NIST will invite public comments on all complete and proper 
submissions. NIST's Round 1 analysis is intended, at a minimum, to be 
performed as follows:
    i. Correctness check: The KAT and MCT values included with the 
submission will be used to test the correctness of the reference and 
optimized implementations, once they are compiled. (It is more likely 
that NIST will perform this check of the reference code--and possibly 
the optimized code as well--even before accepting the submission 
package as ``complete and proper.'')
    ii. Efficiency testing: Using the submitted optimized 
implementations, NIST intends to perform various computational 
efficiency tests, including the calculation of the time required to 
compute message digests for various length messages.
    iii. Other testing: Other features of the candidate algorithms may 
be examined by NIST.
Platform and Compilers
    The above tests will initially be performed by NIST with the 
following tools, at a minimum.
    i. NIST Reference Platform: Wintel personal computer, with an Intel 
Core 2 Duo Processor, 2.4GHz clock speed, 2GB RAM, running Windows 
Vista Ultimate 32-bit (x86) and 64-bit (x64) Edition.
    ii. Compiler (Note that the selection of this compiler is for use 
by NIST in Rounds 1 and 2, and does not constitute a direct or implied 
endorsement by NIST.): The ANSI C compiler in the Microsoft Visual 
Studio 2005 Professional Edition.
    At a minimum, NIST intends to perform an efficiency analysis on the 
reference platform; however, NIST invites the public to conduct similar 
tests and compare results on additional platforms (e.g., 8-bit 
processors, Digital Signal Processors, dedicated CMOS, etc.).

    Note: Any changes to the intended platform/compiler will be 
noted on https://www.nist.gov/hash-competition.

6.C Round 2 Technical Evaluation

    At the end of the Round 1 technical evaluation and the Second SHA-3 
Candidate Conference, NIST intends to narrow the field of candidate 
algorithms to approximately five candidates, in order to focus the 
remaining efforts of both NIST and the public. NIST intends to perform 
its own analysis of the submissions, and make that information publicly 
available. NIST's Round 2 analysis will, at a minimum, be performed as 
follows.

    Note: The same platform and compilers from Round 1 will be used 
for Round 2 unless indicated on https://www.nist.gov/hash-
competition.

    i. Message digest sizes: Round 2 testing by NIST will be performed 
on the required message digest sizes as specified in section 3. Note: 
If the submitter chooses to submit updated optimized implementations 
prior to the beginning of Round 2, then some of the tests performed in 
Round 1 may be performed again using the new optimized implementations. 
This will be done to obtain updated measurements.
    ii. Efficiency testing: Using the submitted optimized 
implementations, NIST intends to perform various computational 
efficiency tests for the minimum message digest sizes specified in 
section 3, including the calculation of the time required to compute 
message digests for various length messages.
    NIST welcomes comments regarding the efficiency of the candidate 
algorithms when implemented in hardware. NIST may specify the finalist 
algorithms using a Hardware Description Language, to compare the 
estimated hardware efficiency of the candidate algorithms.
    NIST may perform efficiency testing using additional platforms. 
NIST welcomes public input regarding efficiency testing on additional 
platforms.
    iii. Other testing: Other features of the candidate algorithms may 
be examined by NIST. If appropriate, analyses from the Second SHA-3 
Candidate Conference and the public evaluation during Round 1 may 
warrant the testing of specific features.

7. Miscellaneous

    This section is intended to address some of the questions/comments 
raised in the review of the draft evaluation criteria.
     When evaluating algorithms, NIST will make every effort to 
obtain public input and will encourage the review of the candidate 
algorithms by outside organizations; however, the final decision as to 
which algorithm(s) will be selected for SHA-3 is the responsibility of 
NIST.
     NIST intends to develop a validation program for hash 
algorithm conformance testing, with the goal of having testing 
available by the time SHA-3 is incorporated into the revised Secure 
Hash Standard.
     NIST does NOT have a fixed timetable for the completion of 
the hash function competition. NIST reserves the right to extend the 
length of the technical review period for each round. If necessary, 
NIST may also insert additional rounds of such technical evaluations.
     NIST does not intend to select a wholly distinct algorithm 
for each of the minimally required message digest sizes. It is strongly 
recommended that no submission be so constructed.
     NIST will not target a specific application or platform 
for implementing the candidate hash algorithms, as the evaluation of 
candidate algorithms takes place. One factor that will be taken into 
consideration for each candidate algorithm is its flexibility--the 
ability to implement the algorithm securely and efficiently on a wide 
variety of platforms and applications (see Section 4.C).
     Since SHA-3 is intended to augment the existing NIST-
approved hash algorithm toolkit, which includes the SHA-2 family of 
hash functions, NIST does not intend to select an additional ``backup'' 
hash algorithm for SHA-3. If circumstances arise (e.g., a discovery of 
a significant security flaw) that could not be satisfactorily addressed 
by modifying the selected SHA-3 algorithm, NIST would likely consider 
the other finalist algorithms. If a significant period of time has 
elapsed since the hash algorithm selection, NIST would likely examine 
other algorithms that may have been developed in the intervening 
period.
     Exportability decisions regarding submissions and, 
eventually, products implementing the selected SHA-3 algorithm(s) will 
be made by the appropriate U.S. Government regulatory authorities. NIST 
is a non-regulatory agency of the U.S. Department of Commerce.
     If no appropriate algorithms are submitted in response to 
this call, NIST expressly reserves the right to cease this process and 
examine other possible courses of action.
     Submitters are strongly encouraged to submit only one 
algorithm each (presumably the one in which the submitter has the 
greatest confidence). The submission of similar, yet distinct, 
algorithms by the same submitter may delay the public evaluation 
process and may well raise public questions as to the submitter's level 
of confidence in his/her candidates.
     For conference and resource allocation planning purposes, 
it would be appreciated if those planning to submit candidates could 
notify the individuals listed in the FOR FURTHER INFORMATION CONTACT 
Section as soon as possible.

[[Page 62220]]

Appreciation

    NIST extends its appreciation to all submitters and those providing 
public comments during the SHA-3 development process.

    Dated: October 29, 2007.
Richard F. Kayser,
Acting Deputy Director, NIST.
[FR Doc. E7-21581 Filed 11-1-07; 8:45 am]
BILLING CODE 3510-13-P