ANSI ASC X9 X9.82-3-2007 Random Number Generation Part 3 Deterministic Random Bit Generators.pdf

1、 ASC X9, Inc. 2007 All rights reserved American National Standard for Financial Services ANS X9.82: Part 32007 Random Number Generation Part 3: Deterministic Random Bit Generators Accredited Standards Committee X9, Incorporated Financial Industry Standards Date Approved: American National Standards

2、Institute American National Standards, Technical Reports and Guides developed through Accredited Standards Committee X9, Inc. are copyrighted. Copying these documents for personal or commercial use outside X9 membership agreements is prohibited without express written permission of the Accredited St

3、andards Committee X9, Inc. For additional information, please contact ASC X9, Inc., 1212 West Street, Suite 200, Annaplis, Maryland 21401 ANS X9.82, Part 3 - 2007 ii ASC X9 Inc., 2007 All rights reservedContents Foreword vii Introduction viii 1 Scope . 1 2 Conformance . 1 3 Normative References 2 4

4、Terms and Definitions. 2 5 Abbreviations and Symbols . 5 6 General Discussion and Organization. 7 7 Functional Model. 9 7.1 General Discussion . 9 7.2 Functional Model Components . 9 7.2.1 Entropy Input 9 7.2.2 Other Inputs 10 7.2.3 The Internal State . 10 7.2.4 The DRBG Mechanism Functions 10 8. DR

5、BG Mechanism Concepts and General Requirements . 11 8.1 Introduction 11 8.2 DRBG Mechanism Functions and a DRBG Instantiation 11 8.2.1 DRBG Mechanism Functions . 11 8.2.2 DRBG Instantiations. 11 8.2.3 Internal States 11 8.2.4 Security Strengths Supported by an Instantiation 12 8.3 DRBG Mechanism Bou

6、ndaries . 13 8.4 Seeds 14 8.4.1 General Discussion 14 8.4.2 Generation and Handling of Seeds 15 8.5 Other Inputs to the DRBG Mechanism 17 8.5.1 Discussion 17 8.5.2 Personalization String. 17 8.5.3 Additional Input. 18 ANS X9.82, Part 3 2007 ASC X9 Inc., 2007 All rights reserved iii8.6 Prediction Res

7、istance and Backtracking Resistance 18 9 DRBG Mechanism Functions . 19 9.1 General Discussion . 19 9.2 Instantiating a DRBG. 19 9.3 Reseeding a DRBG Instantiation 22 9.4 Generating Pseudorandom Bits Using a DRBG . 24 9.4.1 The Generate Function. 25 9.4.2 Reseeding at the End of the Seedlife. 27 9.4.

8、3 Handling Prediction Resistance Requests . 28 9.5 Removing a DRBG Instantiation . 28 10 DRBG Algorithm Specifications 30 10.1 Overview . 30 10.2 Deterministic RBG Based on Hash Functions 30 10.2.1 Discussion 30 10.2.2 HMAC_DRBG. 31 10.2.2.1 Discussion 31 10.2.2.2 Specifications . 32 10.2.2.2.1 HMAC

9、DRBG Internal State 32 10.2.2.2.2 The Update Function (CTR_DRBG_Update) . 32 10.2.2.2.3 Instantiation of HMAC_DRBG 33 10.2.2.2.4 Reseeding an HMAC_DRBG Instantiation 34 10.2.2.2.5 Generating Pseudorandom Bits Using HMAC_DRBG 34 10.3 DRBG Mechanisms Based on Block Ciphers . 36 10.3.1 Discussion 36 1

10、0.3.2 CTR_DRBG 36 10.3.2.1 CTR_DRBG Description 36 10.3.2.2 Specifications . 38 10.3.2.2.1 CTR_DRBG Internal State. 38 10.3.2.2.2 The Update Function (CTR_DRBG_Update) 39 10.3.2.2.3 Instantiation of CTR_DRBG. 39 10.3.2.2.4 Reseeding a CTR_DRBG Instantiation . 41 10.3.2.2.5 Generating Pseudorandom Bi

11、ts Using CTR_DRBG 43 ANS X9.82, Part 3 - 2007 iv ASC X9 Inc., 2007 All rights reserved10.4 DRBG Mechanisms Based on Number Theoretic Problems 47 10.4.1 Discussion 47 10.4.2 Dual Elliptic Curve Deterministic RBG (Dual_EC_DRBG). 47 10.4.2.1 Discussion 47 10.4.2.2 Specifications . 49 10.4.2.2.1 Dual_EC

12、DRBG Internal State 49 10.4.2.2.2 Instantiation of Dual_EC_DRBG 50 10.4.2.2.3 Reseeding of a Dual_EC_DRBG Instantiation 51 10.4.2.2.4 Generating Pseudorandom Bits Using Dual_EC_DRBG 51 10.5 Auxiliary Functions 54 10.5.1 Discussion 54 10.5.2 Derivation Function Using a Hash Function (Hash_df) 54 10.

13、5.3 Derivation Function Using a Block Cipher Algorithm (Block_Cipher_df) . 55 10.5.4 BCC Function . 57 11 Assurance 58 11.1 Overview . 58 11.2 Minimal Documentation Requirements . 58 11.3 Implementation Validation Testing 59 11.4 Health Testing . 59 11.4.1 Overview 59 11.4.2 Known-Answer Testing. 60

14、 11.4.3 Testing the Instantiate Function . 60 11.4.4 Testing the Generate Function. 60 11.4.5 Testing the Reseed Function 61 11.4.6 Testing the Uninstantiate Function. 61 11.4.7 Error Handling 61 11.4.7.1 General Discussion 61 11.4.7.2 Errors Encountered During Normal Operation. 61 11.4.7.3 Errors E

15、ncountered During Health Testing 62 Annex A: (Normative) Application-Specific Constants 63 A.1 Constants for the Dual_EC_DRBG . 63 A.1.1 Curves over Prime Fields . 63 ANS X9.82, Part 3 2007 ASC X9 Inc., 2007 All rights reserved vA.1.1.1 Curve P-256 63 A.1.1.2 Curve P-384 64 A.1.1.3 Curve P-521 64 A.

16、2 Using Alternative Points in the Dual_EC_DRBG() 65 A.2.1 Generating Alternative P,Q 65 A.2.2 Additional Self-testing Required for Alternative P,Q. 66 ANNEX B : (Normative) Conversion and Auxiliary Routines. 67 B.1 Bitstring to an Integer 67 B.2 Integer to a Bitstring 67 B.3 Integer to a Byte String

17、 67 B.4 Byte String to an Integer 68 Annex C: (Informative) Security Considerations 69 C.1 Extracting Bits in the Dual_EC_DRBG (.) . 69 C.1.1 Potential Bias Due to Modular Arithmetic for Curves Over Fp69 C.1.2 Adjusting for the Missing Bit(s) of Entropy in the x Coordinates. . 69 ANNEX D: (Informati

18、ve) DRBG Mechanism Selection . 73 D.1 Choosing a DRBG Algorithm 73 D.2 HMAC_DRBG . 73 D.3 CTR_DRBG. 74 D.4 DRBGs Based on Hard Problems. 75 D.5 Summary for DRBG Selection 76 ANNEX E: (Informative) Example Pseudocode for Each DRBG Mechanism . 77 E.1 Preliminaries 77 E.2 HMAC_DRBG Example 77 E.2.1 Dis

19、cussion 77 E.2.2 Instantiation of HMAC_DRBG 78 E.2.3 Generating Pseudorandom Bits Using HMAC_DRBG. 79 E.3 CTR_DRBG Example Using a Derivation Function 81 E.3.1 Discussion 81 E.3.2 The CTR_DRBG_Update Function 82 E.3.3 Instantiation of CTR_DRBG Using a Derivation Function 82 ANS X9.82, Part 3 - 2007

20、vi ASC X9 Inc., 2007 All rights reservedE.3.4 Reseeding a CTR_DRBG Instantiation Using a Derivation Function 84 E.3.5 Generating Pseudorandom Bits Using CTR_DRBG 85 E.4 CTR_DRBG Example Without a Derivation Function . 87 E.4.1 Discussion 87 E.4.2 The CTR_DRBG_Update Function 88 E.4.3 Instantiation o

21、f CTR_DRBG Without a Derivation Function. 88 E.4.4 Reseeding a CTR_DRBG Instantiation Without a Derivation Function . 88 E.4.5 Generating Pseudorandom Bits Using CTR_DRBG 89 E.5 Dual_EC_DRBG Example. 89 E.5.1 Discussion 89 E.5.2 Instantiation of Dual_EC_DRBG 90 E.5.3 Reseeding a Dual_EC_DRBG Instant

22、iation.Error! Bookmark not defined. E.5.4 Generating Pseudorandom Bits Using Dual_EC_DRBG . 91 ANNEX F: (Informative) DRBG Provision of RBG Security Properties. 94 F.1 Introduction 94 F.2 Security Strengths. 94 F.3 Entropy and Min-Entropy.94 F.4 Backtracking Resistance and Prediction Resistance 94 F

23、5 Indistinguishability and Unpredictability 94 F.6 Desired RBG Output Properties 94 F.7 Desired RBG Operational Properties 95 ANNEX G:. 97 G.1 Overview . 97 G.2 HMAC_DRBG 97 G.3 CTR_DRBG. 97 G.4 Dual_EC_DRBG 98 Bibliography 101 ANS X9.82, Part 3 2007 ASC X9 Inc., 2007 All rights reserved viiForewor

24、d The Accredited Standards Committee on Financial Services (ASC X9) has developed several cryptographic standards to protect financial information. Many of these standards require the use of Random Number Generators to generate random and unpredictable cryptographic keys and other critical security

25、parameters. This Standard, Random Number Generation, defines techniques for the generation of random numbers that are used when other ASC standards require the use of random numbers for cryptographic purposes. While the techniques specified in this Standard are designed to generate random numbers, t

26、he Standard does not guarantee that a particular implementation is secure. It is the responsibility of the financial institution to put an overall process in place with the necessary controls to ensure that the process is securely implemented. Furthermore, the controls should include the application

27、 with appropriate validation tests in order to verify compliance with this Standard. Approval of an American National Standard requires verification by ASC that the requirements for due process, consensus, and other criteria for approval have been met by the standards developer. Consensus is establi

28、shed when, in the judgment of the ASC Board of Standards Review, substantial agreement has been reached by directly and materially affected interests. Substantial agreement means much more than a simple majority, but not necessarily unanimity. Consensus requires that all views and objections be cons

29、idered, and that a concerted effort be made toward their resolution. The use of American National Standards is completely voluntary; their existence does not in any respect preclude anyone, whether he has approved the standards or not from manufacturing, marketing, purchasing, or using products, pro

30、cesses, or procedures not conforming to the standards. The American National Standards Institute does not develop standards and will in no circumstances give an interpretation of any American National Standard. Moreover, no person shall have the right or authority to issue an interpretation of an Am

31、erican National Standard in the name of the American National Standards Institute. Requests for interpretations should be addressed to the secretariat or sponsor whose name appears on the title page of this Standard. CAUTION NOTICE: This American National Standard may be revised or withdrawn at any

32、time. The procedures of the American National Standards Institute require that action be taken to reaffirm, revise, or withdraw this Standard no later than five years from the date of approval. Published by Accredited Standards Committee X9 Incorporated Financial Industry standards P.O. Box 4035 Ann

33、apolis, MD 21403 USA X9 Online http:/www.x9.org Copyright 2007 ASC X9, Inc. All rights reserved. No part of this publication may be reproduced in any form, in an electronic retrieval system or otherwise, without prior written permission of the publisher. Published in the United States of America. AN

34、S X9.82, Part 3 - 2007 viii ASC X9 Inc., 2007 All rights reservedIntroduction This Standard defines techniques for the generation of random numbers that shall be used whenever ASC X9 Standards require the use of a random number or bitstring for cryptographic purposes. The Standard consists of four p

35、arts: Part 1: Overview and Basic Principles Part 2: Entropy Sources Part 3: Deterministic Random Bit Generator Mechanisms Part 4: Random Bit Generator Construction This part of ANS X9.82 (Part 3) defines mechanisms for the generation of random bits using deterministic methods. NOTE The users attenti

36、on is called to the possibility that compliance with this Standard may require use of an invention covered by patent rights. By publication of this Standard, no position is taken with respect to the validity of this claim or of any patent rights in connection therewith. The patent holder has, howeve

37、r, filed a statement of willingness to grant a license under these rights on reasonable and nondiscriminatory terms and conditions to applicants desiring to obtain such a license. Details may be obtained from the standards developer. Suggestions for the improvement or revision of this Standard are w

38、elcome. They should be sent to the X9 Committee Secretariat, Accredited Standards Committee X9, Inc., Financial Industry Standards, P.O. Box 4035, Annapolis, MD 21403 USA. This Standard was processed and approved for submittal to ANSI by the Accredited Standards Committee on Financial Services, X9.

39、Committee approval of the Standard does not necessarily imply that all the committee members voted for its approval. The X9 committee had the following members: James Shaffer, X9 Chairman Vincent DeSantis, X9 Vice-Chairman Cynthia Fuller, Executive Director Susan Yashinskie, Managing Director Organi

40、zation Represented Representative ACI Worldwide James Shaffer American Bankers Association C. Diane Poole American Express Company John Allen American Financial Services Association Mark Zalewski Bank of America Daniel Welch Capital One Scott Sykes Certicom Corporation Daniel Brown Citigroup, Inc. M

41、ike Halpern Clarker American Checks, Inc. John W. McCleary CUSIP Service Bureau James Taylor Deluxe Corporation John Fitzpatrick Diebold, Inc. Bruce Chapa Discover Financial Services Katie Howser Federal Reserve Bank Dexter Holt First Data Corporation Elizabeth Lynn Fiserv Skip Smith FSTC, Financial

42、 Services Consortium Daniel Schutzer ANS X9.82, Part 3 2007 ASC X9 Inc., 2007 All rights reserved ixHewlett Packard Larry Hines Hypercom Scott Spiker IBM Corporation Todd Arnold Ingenico John SpenceIntuit, Inc. Jana Hocker iStream Imaging Bank of Kenney Ken Biel JP Morgan Chase Parts 2 and 4 of this

43、 Standard provide further requirements for the design of an RBG. Part 3 includes: 1. A model for a deterministic random bit generator (DRBG), 2. Requirements for DRBG mechanisms, 3. Specifications for DRBG mechanisms that are based on hash functions or block ciphers, or are based on number theoretic

44、 problems, 4. Implementation issues, and 5. Assurance considerations. A DRBG is based on a DRBG mechanism as specified in this part of the Standard and includes a source of entropy input. Part 3 specifies several diverse DRBG mechanisms, all of which provided acceptable security when this Standard w

45、as approved. However, in the event that new attacks are found on a particular class of mechanisms, a diversity of approved mechanisms will allow a timely transition to a different class of DRBG mechanism. Random number generation does not require interoperability between two entities, e.g., communic

46、ating entities may use different DRBG mechanisms without affecting their ability to communicate. Therefore, an entity may choose a single appropriate DRBG mechanism for its applications; see Annex D for a discussion of DRBG selection. The precise structure, design and development of a random bit gen

47、erator is outside the scope of this Standard. 2 Conformance An implementation of a DRBG mechanism may claim conformance with ANS X9.82 if it implements the mandatory provisions of Part 1 and the mandatory requirements of one or more of the DRBG mechanisms specified in this part of the Standard. An i

48、mplementation of a DRBG may claim conformance with ANS X9.82 as an RBG if the following are implemented: the mandatory provisions of Part 1, the mandatory requirements of one or more of the DRBG mechanisms specified in this part of the Standard, an entropy source from Part 2 and the appropriate mand

49、atory requirements of Part 4. ANS X9.82, Part 3 - 2007 2 ASC X9 Inc., 2007 All rights reservedIt is expected that conformance may be assured by a testing laboratory associated with the Cryptographic Module Validation Program (CMVP) (see http:/csrc.nist.gov/cryptval). Although an implementation may claim conformance with the Standard apart from such testing, implementation testing through the CMVP is strongly recommended. 3 Normative References The following referenced documents are indispensable for the application of this Standard. For dated referenc