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

Download as PDF 62212 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices Preliminary Determination by the ITC The ITC will preliminarily determine, within 25 days after the date on which it receives notice of the initiation, whether there is a reasonable indication that imports of subsidized LWTP from the PRC are causing material injury, or threatening to cause material injury, to a U.S. industry. See section 703(a)(2) of the Act. A negative ITC determination will result in the investigation being terminated; otherwise, the investigation will proceed according to statutory and regulatory time limits. This notice is issued and published pursuant to section 777(i) of the Act. Dated: October 29, 2007. Stephen J. Claeys, Acting Assistant Secretary for Import Administration. [FR Doc. E7–21616 Filed 11–1–07; 8:45 am] BILLING CODE 3510–DS–S 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 National Institute of Standards and Technology, Commerce. ACTION: Notice and request for nominations for candidate hash algorithms. pwalker on PROD1PC71 with NOTICES AGENCY: 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 VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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: shujen.chang@nist.gov. This notice contains the following sections: SUPPLEMENTARY INFORMATION: 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. PO 00000 Frm 00009 Fmt 4703 Sfmt 4703 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). E:\FR\FM\02NON1.SGM 02NON1 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices pwalker on PROD1PC71 with NOTICES 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 ‘‘onepass’’ 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 VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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, email 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 PO 00000 Frm 00010 Fmt 4703 Sfmt 4703 62213 proof, and 2) a preliminary analysis, such as possible attack scenarios for collision-finding, first-preimage-finding, second-preimage-finding, lengthextension 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 MerkleDamgard 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. E:\FR\FM\02NON1.SGM 02NON1 pwalker on PROD1PC71 with NOTICES 62214 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices It should be noted that standards which refer to a block length are generally designed with the MerkleDamgard 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 VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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. PO 00000 Frm 00011 Fmt 4703 Sfmt 4703 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/hashcompetition. All ANSI C submissions shall implement that API so that the E:\FR\FM\02NON1.SGM 02NON1 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices 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 pwalker on PROD1PC71 with NOTICES 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: Æ \Optimized_32 bit Æ \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 VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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: \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: • \README. • \Reference Implementation. • \Optimized_32 bit. • \Optimized_64 bit. • \KAT_MCT. • \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 resubmitted. 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 PO 00000 Frm 00012 Fmt 4703 Sfmt 4703 62215 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, llll (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 llll (print name of algorithm), may be covered by the following U.S. and/or foreign patents: llll (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:llll (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 E:\FR\FM\02NON1.SGM 02NON1 62216 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices pwalker on PROD1PC71 with NOTICES 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, llll (print full name), of llll (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): llll (enumerate), and do hereby agree to grant to any interested party if the algorithm known as llll (print name of algorithm) is selected for SHA– 3, an irrevocable nonexclusive royaltyfree 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 VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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,llll(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/hashcompetition. 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 PO 00000 Frm 00013 Fmt 4703 Sfmt 4703 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 264–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/hashcompetition 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 E:\FR\FM\02NON1.SGM 02NON1 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices factors (ranked in the order of relative importance): and randomization value r2 that yield the same randomized hash value. 4.A 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. 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. pwalker on PROD1PC71 with NOTICES 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 VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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 PO 00000 Frm 00014 Fmt 4703 Sfmt 4703 62217 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. E:\FR\FM\02NON1.SGM 02NON1 62218 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices 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. pwalker on PROD1PC71 with NOTICES 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, VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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 twelvemonth 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 PO 00000 Frm 00015 Fmt 4703 Sfmt 4703 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. E:\FR\FM\02NON1.SGM 02NON1 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices 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.). pwalker on PROD1PC71 with NOTICES 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. VerDate Aug<31>2005 15:58 Nov 01, 2007 Jkt 214001 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. PO 00000 Frm 00016 Fmt 4703 Sfmt 4703 62219 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. E:\FR\FM\02NON1.SGM 02NON1 62220 Federal Register / Vol. 72, No. 212 / Friday, November 2, 2007 / Notices 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 National Oceanic and Atmospheric Administration RIN 0648–XD70 North Pacific Fishery Management Council; Notice of Plan Team Meetings National Marine Fisheries Service (NMFS), National Oceanic and Atmospheric Administration (NOAA), Commerce. ACTION: Meetings. AGENCY: SUMMARY: The North Pacific Fishery Management Council’s Gulf of Alaska (GOA) and Bering Sea/Aleutian Islands (BS/AI) groundfish plan teams will meet in Seattle. DATES: November 13–16, 2007. The meetings will begin at 9 a.m. on Tuesday, November 13, and continue through Friday November 16. ADDRESSES: Alaska Fisheries Science Center, 7600 Sand Point Way N.E., Building 4, Observer Training Room (GOA Plan Team) and Traynor Room (BS/AI Plan Team), Seattle, Washington. Council address: North Pacific Fishery Management Council, 605 W. 4th Ave., Suite 306, Anchorage, AK 99501–2252. FOR FURTHER INFORMATION CONTACT: Jane DiCosimo or Diana Stram, NPFMC, 907– 271–2809. SUPPLEMENTARY INFORMATION: Agenda Principal business is to prepare and review the stock assessments for groundfish fisheries in the BSAI and GOA and recommend catch specifications for 2008/2009. Agenda posted on website at: https:// www.fakr.noaa.gov/npfmc/ pwalker on PROD1PC71 with NOTICES Special Accommodations These meetings are physically accessible to people with disabilities. Requests for sign language interpretation or other auxiliary aids should be directed to Gail Bendixen, 907–271–2809, at least 5 working days prior to the meeting date. 15:58 Nov 01, 2007 Jkt 214001 of the formats specified above. Comments will be posted to NTIA’s website at https://www.ntia.doc.gov/ ntiahome/domainname/ jpamidtermreview.html. BILLING CODE 3510–22–S FOR FURTHER INFORMATION CONTACT: DEPARTMENT OF COMMERCE National Telecommunications and Information Administration [Docket No. 071023616–7617–01] DEPARTMENT OF COMMERCE VerDate Aug<31>2005 Dated: October 29, 2007. Tracey L. Thompson, Acting Director, Office of Sustainable Fisheries, National Marine Fisheries Service. [FR Doc. E7–21543 Filed 11–1–07; 8:45 am] The Continued Transition of the Technical Coordination and Management of the Internet’s Domain Name and Addressing System: Midterm Review of the Joint Project Agreement National Telecommunications and Information Administration, U.S. Department of Commence ACTION: Notice of Inquiry AGENCY: SUMMARY: The United States Department of Commerce’s National Telecommunications and Information Administration (NTIA) seeks comments on the continued transition to the private sector of the technical coordination and management of the Internet’s domain name and addressing system (DNS). NTIA and the Internet Corporation for Assigned Names and Numbers (ICANN) signed a Joint Project Agreement (JPA) on September 29, 2006. It called for a midpoint review of ICANN’s progress towards becoming a more stable organization with greater transparency and accountability in its procedures and decision making. The Department of Commerce seeks comment regarding the progress achieved on the Responsibilities identified in the JPA. DATES: Comments are due on or before February 15, 2008. ADDRESSES: Written comments may be submitted by mail to Suzanne R. Sene, Office of International Affairs, National Telecommunications and Information Administration, 1401 Constitution Avenue, N.W., Room 4701, Washington, DC 20230. Paper submissions should include a three and one-half inch computer diskette in HTML, ASCII, Word or WordPerfect format (please specify version). Diskettes should be labeled with the name and organizational affiliation of the filer, and the name of the word processing program used to create the document. Alternatively, comments may be submitted electronically to JPAMidTermReview@ntia.doc.gov. Comments provided via electronic mail should also be submitted in one or more PO 00000 Frm 00017 Fmt 4703 Sfmt 4703 For questions about this Notice contact: Suzanne R. Sene, National Telecommunications and Information Administration, U.S. Department of Commerce, 1401 Constitution Avenue, N.W., Room 4701, Washington, DC 20230; telephone: (202) 482–3167; or email: ssene@ntia.doc.gov Please direct media inquiries to the Office of Public Affairs, NTIA, at (202) 482–7002. SUPPLEMENTARY INFORMATION: Background: A July 1, 1997 Executive Memorandum directed the Secretary of Commerce to privatize the domain name system (DNS) in a manner that increases competition and facilitates international participation in its management.1 In order to fulfill this Presidential directive, the Department of Commerce in June 1998, issued a statement of policy on the privatization of the Internet Domain Name System (DNS), known as the DNS White Paper.2 This document articulated four primary functions for global DNS coordination and management: 1. To set policy for and direct the allocation of IP number blocks; 2. To oversee the operation of the Internet root server system; 3. To oversee policy for determining the circumstances under which new top level domains (TLDs) would be added to the root server system; and 4. To coordinate the assignment of other technical protocol parameters as needed to maintain universal connectivity on the Internet. In the DNS White Paper, the Department of Commerce concluded that these functions were relevant to the state of the DNS and should be primarily performed through private sector management. To this end, the Department of Commerce stated that it was prepared to enter into agreement with a new not-for-profit corporation formed by private sector Internet stakeholders. Private sector interests formed the Internet Corporation for Assigned Names and Numbers (ICANN) for this purpose. In the fall of 1998, the Department of Commerce entered into a Memorandum of Understanding (MOU) with ICANN, a California non-profit corporation, to transition technical DNS 1 Memorandum on Electronic Commerce, 2 Pub. Papers 898 (July 1, 1997). 2 Management of Internet Names and Addresses, 63 Fed. Reg. 31,741 (June 10, 1998). E:\FR\FM\02NON1.SGM 02NON1

Agencies

[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