ISO/IEC 18031:2005

INTERNATIONAL ISO/IEC
STANDARD 18031
First edition
2005-11-01


Information technology — Security
techniques — Random bit generation
Technologies de l'information — Techniques de sécurité — Génération
de bits aléatoires





Reference number
ISO/IEC 18031:2005(E)
©
ISO/IEC 2005

---------------------- Page: 1 ----------------------
ISO/IEC 18031:2005(E)
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's licensing policy, this file may be printed or viewed but
shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In
downloading this file, parties accept therein the responsibility of not infringing Adobe's licensing policy. The ISO Central Secretariat
accepts no liability in this area.
Adobe is a trademark of Adobe Systems Incorporated.
Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation
parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In
the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below.


©  ISO/IEC 2005
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland

ii © ISO/IEC 2005 – All rights reserved

---------------------- Page: 2 ----------------------
ISO/IEC 18031:2005(E)
Contents Page
Foreword. vi
Introduction . vii
1 Scope. 1
2 Normative references. 1
3 Terms and definitions. 2
4 Symbols. 5
5 Overarching objectives and requirements of a random bit generator. 5
5.1 Required properties of randomness. 6
5.2 Backward and forward secrecy. 6
5.3 Top-level objectives and requirements for a random bit generator (RBG) output . 7
5.4 Top-level objectives and requirements for RBG operation. 7
5.5 Random bit generator functional requirements .8
6 General functional model for random bit generation. 8
6.1 Basic components. 8
6.1.1 Entropy source. 9
6.1.2 Additional inputs. 10
6.1.3 Internal state. 10
6.1.4 Internal state transition functions. 11
6.1.5 Output generation function . 12
6.1.6 Support functions. 13
7 Types of random bit generators. 14
7.1 Non-deterministic random bit generators (NRBGs). 14
7.2 Deterministic random bit generators (DRBGs). 15
7.3 The RBG spectrum . 15
8 Overview and requirements for a non-deterministic random bit generator. 16
8.1 Overview. 16
8.2 Functional model of a non-deterministic random bit generator. 16
8.2.1 Overview of the model. 16
8.3 Entropy sources. 18
8.3.1 Primary entropy source. 18
8.3.2 Physical entropy sources. 20
8.3.3 Non-physical entropy sources . 21
8.3.4 Additional entropy sources . 21
8.3.5 Hybrid non-deterministic random bit generators.22
8.4 Additional inputs. 23
8.4.1 Overview. 23
8.4.2 Mandatory requirements. 23
8.5 Internal state. 23
8.5.1 Overview. 23
8.5.2 Mandatory requirements. 24
8.5.3 Optional requirements. 24
8.6 Internal state transition functions. 25
8.6.1 Overview. 25
8.6.2 Mandatory requirements. 26
8.6.3 Optional requirements. 26
8.7 Output generation function . 26
8.7.1 Overview. 26
8.7.2 Mandatory requirements. 26
© ISO/IEC 2005 – All rights reserved iii

---------------------- Page: 3 ----------------------
ISO/IEC 18031:2005(E)
8.7.3 Optional requirement. 27
8.8 Health tests. 27
8.8.1 Overview. 27
8.8.2 General health test requirements. 27
8.8.3 Health test on deterministic components . 28
8.8.4 Health tests on entropy sources . 28
8.8.5 Health tests on random output. 29
8.9 Component interaction. 31
8.9.1 Overview. 31
8.9.2 Mandatory requirements. 31
8.9.3 Optional requirements. 32
9 Overview and requirements for a deterministic random bit generator . 32
9.1 Overview. 32
9.2 Functional model of DRBG . 33
9.2.1 Overview of the model. 33
9.3 Entropy source. 35
9.3.1 Primary entropy source. 35
9.3.2 Generating seed values. 37
9.3.3 Additional entropy sources. 37
9.3.4 Hybrid deterministic random bit generator. 38
9.4 Additional inputs. 38
9.5 Internal state. 38
9.6 Internal state transition function . 39
9.7 Output generation function. 40
9.7.1 Overview. 40
9.8 Support functions . 40
9.8.1 Overview. 40
9.8.2 Self test. 40
9.8.3 Deterministic algorithm test. 41
9.8.4 Software/Firmware integrity test . 41
9.8.5 Critical functions test . 41
9.8.6 Software/Firmware load test . 41
9.8.7 Manual key entry test. 41
9.8.8 Continuous random bit generator test . 42
9.9 Additional DRBG functional requirements. 42
9.9.1 Keys. 42
Annex A (normative) Combining random bit generators . 44
Annex B (normative) Conversion methods . 45
B.1 Random number generation . 45
B.1.1 The simple discard method. 45
B.1.2 The complex discard method . 45
B.1.3 The simple modular method . 46
B.1.4 The complex modular method. 46
B.2 Extracting bits in the Dual_EC_DRBG . 47
B.2.1 Potential bias in an elliptic curve over a prime field F . 47
p
B.2.2 Adjusting for the missing bit(s) of entropy in the x coordinates . 48
B.2.3 Values for E. 49
B.2.4 Observations. 51
Annex C (normative) Deterministic random bit generators . 52
C.1 Introduction . 52
C.2 Deterministic RBGs based on a hash-function. 52
C.2.1 Hash-function DRBG (Hash_DRBG) . 52
C.3 DRBG based on block ciphers. 60
C.3.1 CTR_DRBG. 61
C.3.2 OFB_DRBG (…). 70
C.4 Deterministic RBGs based on number theoretic problems. 72
C.4.1 Dual Elliptic Curve DRBG (Dual_EC_DRBG). 72
C.4.2 Micali Schnorr DRBG (MS_DRBG) . 81
iv © ISO/IEC 2005 – All rights reserved

---------------------- Page: 4 ----------------------
ISO/IEC 18031:2005(E)
Annex D (normative) Application specific constants. 91
D.1 Constants for the Dual_EC_DRBG. 91
D.1.1 Curves over Prime Fields. 91
D.1.2 Curves over binary fields. 94
D.2 Default moduli for the MS_DRBG (…). 103
D.2.1 Default modulus n of size 1024 bits. 103
D.2.2 Default modulus n of size 2048 bits. 103
D.2.3 Default modulus n of size 3072 bits. 104
D.2.4 Default modulus n of size 7680 bits. 104
D.2.5 Default modulus n of size 15360 bits. 105
Annex E (informative) Non-deterministic random bit generator examples. 107
E.1 Canonical coin tossing example. 107
E.1.1 Overview. 107
E.1.2 Description of basic process. 107
E.1.3 Relation to standard NRBG components. 107
E.1.4 Optional variations . 108
E.1.5 Peres unbiasing procedure . 108
E.2 Hypothetical noisy diode example. 109
E.2.1 Overview. 109
E.2.2 General structure. 109
E.2.3 Details of operation . 110
E.2.4 Failsafe design consequences. 114
E.2.5 Modified example. 114
E.3 Mouse movement example . 115
Annex F (informative) Security considerations. 116
F.1 Attack model. 116
F.2 The security of hash-functions . 116
F.3 Algorithm and key size selection . 116
F.3.1 Equivalent algorithm strengths. 117
F.3.2 Selection of appropriate DRBGs. 118
F.4 The security of block cipher DRBGS. 119
F.5 Conditioned entropy sources and the derivation function . 119
Annex G (informative) Discussion on the estimation of entropy . 120
Annex H (informative) Random bit generator assurance. 121
Annex I (informative) Random bit generator boundaries. 122
Bibliography . 124

© ISO/IEC 2005 – All rights reserved v

---------------------- Page: 5 ----------------------
ISO/IEC 18031:2005(E)
Foreword
ISO (the International Organization for Standardization) and IEC (International Electrotechnical Commission)
form the specialized system for worldwide standardization. National bodies that are members of ISO and IEC
participate in the development of International Standards through technical committees established by the
respective organization to deal with particular fields of technical activity. ISO and IEC technical committees
collaborate in fields of mutual interest. Other international organizations, governmental and non-governmental,
in liaison with ISO and IEC, also take part in the work. In the field of information technology, ISO and IEC have
established a joint technical committee, ISO/IEC JTC 1.
International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2.
The main task of the joint technical committee is to prepare International Standards. Draft International
Standards adopted by the technical committees are circulated to the member bodies for voting. Publication as
an International Standard requires approval by at least 75 % of the member bodies casting a vote.
Attention is drawn to the possibility that some of the elements of this document may be the subject of patent
rights. ISO shall not be held responsible for identifying any or all such patent rights.
ISO/IEC 18031 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 27, IT Security techniques.
vi © ISO/IEC 2005 – All rights reserved

---------------------- Page: 6 ----------------------
ISO/IEC 18031:2005(E)
Introduction
This International Standard sets out specific requirements that when met will result in the development of a
random bit generator that may be applicable to cryptographic applications.
Numerous cryptographic applications require the use of random bits. These cryptographic applications include
the following:
• random keys and initialisation values (IVs) for encryption;
• random keys for keyed MAC algorithms;
• random private keys for digital signature algorithms;
• random values to be used in entity authentication mechanisms;
• random values to be used in key establishment protocols;
• random PIN and password generation;
• nonces.
The purpose of this International Standard is to establish a conceptual model, terminology, and requirements
related to the building blocks and properties of systems used for random bit generation in or for cryptographic
applications.
In general terms, it is possible to categorize random bit generators into two types depending on whether their
source of entropy varies or is fixed. This International Standard identifies the two types as non-deterministic
and deterministic random bit generators.
A non-deterministic random bit generator can be defined as a random bit generating mechanism that uses a
source of entropy to generate a random bit stream.
A deterministic random bit generator can be defined as a bit generating mechanism that uses deterministic
mechanisms, such as cryptographic algorithms on a source of entropy, to generate a random bit stream. In
this type of bit stream generation, there is a specific input (normally called a seed) and perhaps some optional
input, which, depending on its application may or may not be publicly available. The seed is processed by a
function which provides an output.

© ISO/IEC 2005 – All rights reserved vii

---------------------- Page: 7 ----------------------
INTERNATIONAL STANDARD ISO/IEC 18031:2005(E)

Information technology — Security techniques — Random bit
generation
1 Scope
This International Standard specifies a conceptual model for a random bit generator for cryptographic
purposes, together with the elements of this model.
This International Standard also includes the following:
• the description of the main elements required for a non-deterministic random bit generator;
• the description of the main elements required for a deterministic random bit generator;
• their characteristics;
• their security requirements.
Where there is a requirement to produce sequences of random numbers from random bit strings, Annex B
provides guidance on how this can be performed.
Techniques for statistical testing of random bit generators for the purposes of independent verification or
validation, and detailed designs for such generators, are outside the scope of this International Standard.
2 Normative references
The following referenced documents are indispensable for the application of this document. For dated
references, only the edition cited applies. For undated references, the latest edition of the referenced
document (including any amendments) applies.
ISO/IEC 10116, Information technology — Security techniques — Modes of operation for an n-bit block cipher
ISO/IEC 10118-3:2004, Information technology — Security techniques — Hash-functions — Part 3: Dedicated
hash-functions
ISO/IEC 18032:2004, Information technology — Security techniques — Prime number generation
ISO/IEC 18033-3:2005, Information technology — Security techniques — Encryption algorithms — Part 3:
Block ciphers
ISO/IEC 19790, Information technology — Security techniques — Security requirements for cryptographic
1)
modules

1) To be published.
© ISO/IEC 2005 – All rights reserved 1

---------------------- Page: 8 ----------------------
ISO/IEC 18031:2005(E)
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
algorithm
clearly specified mathematical process for computation; a set of rules that, if followed, will give a prescribed
result.
3.2
backward secrecy
assurance that previous values cannot be determined from the current value or subsequent values.
3.3
biased source
source of bit strings (or numbers) from a sample space is said to be biased if some bit string(s) (or number(s))
are more likely than some other bit string(s) (or number(s)) to be chosen. Equivalently, if the sample space
consists of r elements, some elements will occur with probability different from 1/r.
cf. unbiased source
3.4
bit stream
continuous output of bits from a device or mechanism
3.5
bit string
finite sequence of ones and zeros.
3.6
black box
idealized mechanism that accepts inputs and produces outputs, but is designed such that an observer cannot
see inside the box or determine exactly what is happening inside that box.
cf. glass box
3.7
block cipher
symmetric encipherment system with the property that the encryption operates on a block of plaintext, i.e., a
string of bits of a defined length, to yield a block of ciphertext. [ISO/IEC 18033-1]
3.8
cryptographic boundary
explicitly defined continuous perimeter that establishes the physical bounds of a crypt
...