idnits 2.17.1 draft-ietf-tsvwg-tinymt32-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 212 has weird spacing: '...am seed a 32-...' -- The document date (June 17, 2019) is 1774 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 TSVWG M. Saito 3 Internet-Draft M. Matsumoto 4 Intended status: Standards Track Hiroshima University 5 Expires: December 19, 2019 V. Roca (Ed.) 6 E. Baccelli 7 INRIA 8 June 17, 2019 10 TinyMT32 Pseudo Random Number Generator (PRNG) 11 draft-ietf-tsvwg-tinymt32-05 13 Abstract 15 This document describes the TinyMT32 Pseudo Random Number Generator 16 (PRNG) that produces 32-bit pseudo-random unsigned integers and aims 17 at having a simple-to-use and deterministic solution. This PRNG is a 18 small-sized variant of Mersenne Twister (MT) PRNG. The main 19 advantage of TinyMT32 over MT is the use of a small internal state, 20 compatible with most target platforms that include embedded devices, 21 while keeping a reasonably good randomness that represents a 22 sigificant improvement compared to the Park-Miller Linear 23 Congruential PRNG. However, neither the TinyMT nor MT PRNG are meant 24 to be used for cryptographic applications. 26 Status of This Memo 28 This Internet-Draft is submitted in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF). Note that other groups may also distribute 33 working documents as Internet-Drafts. The list of current Internet- 34 Drafts is at https://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 This Internet-Draft will expire on December 19, 2019. 43 Copyright Notice 45 Copyright (c) 2019 IETF Trust and the persons identified as the 46 document authors. All rights reserved. 48 This document is subject to BCP 78 and the IETF Trust's Legal 49 Provisions Relating to IETF Documents 50 (https://trustee.ietf.org/license-info) in effect on the date of 51 publication of this document. Please review these documents 52 carefully, as they describe your rights and restrictions with respect 53 to this document. Code Components extracted from this document must 54 include Simplified BSD License text as described in Section 4.e of 55 the Trust Legal Provisions and are provided without warranty as 56 described in the Simplified BSD License. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 61 2. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 3 62 3. TinyMT32 PRNG Specification . . . . . . . . . . . . . . . . . 3 63 3.1. TinyMT32 Source Code . . . . . . . . . . . . . . . . . . 3 64 3.2. TinyMT32 Usage . . . . . . . . . . . . . . . . . . . . . 7 65 3.3. Specific Implementation Validation and Deterministic 66 Behavior . . . . . . . . . . . . . . . . . . . . . . . . 8 67 4. Security Considerations . . . . . . . . . . . . . . . . . . . 9 68 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 69 6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9 70 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 9 71 7.1. Normative References . . . . . . . . . . . . . . . . . . 10 72 7.2. Informative References . . . . . . . . . . . . . . . . . 10 73 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 75 1. Introduction 77 This document specifies the TinyMT32 PRNG, as a specialization of the 78 reference implementation version 1.1 (2015/04/24) by Mutsuo Saito and 79 Makoto Matsumoto, from Hiroshima University, that can be found at 80 [TinyMT-web] (TinyMT web site) and [TinyMT-dev] (Github site). This 81 specialisation aims at having a simple-to-use and deterministic PRNG, 82 as explained below. However, the TinyMT32 PRNG is not meant to be 83 used for cryptographic applications. 85 TinyMT is a new small-sized variant introduced in 2011 of the 86 Mersenne Twister (MT) PRNG [MT98]. This document focusses on the 87 TinyMT32 variant (rather than TinyMT64) of the TinyMT PRNG, which 88 outputs 32-bit unsigned integers. 90 The purpose of TinyMT is not to replace Mersenne Twister: TinyMT has 91 a far shorter period (2^^127 - 1) than MT. The merit of TinyMT is in 92 the small size of the internal state of 127 bits, far smaller than 93 the 19937 bits of MT. The outputs of TinyMT satisfy several 94 statistical tests for non-cryptographic randomness, including 95 BigCrush in TestU01 [TestU01] and AdaptiveCrush [AdaptiveCrush], 96 leaving it well-placed for non-cryptographic usage, especially given 97 the small size of its internal state (see [TinyMT-web]). From this 98 point of view, TinyMT32 represents a major improvement with respect 99 to the Park-Miller Linear Congruential PRNG (e.g., as specified in 100 [RFC5170]) that suffers several known limitations (see for instance 101 [PTVF92], section 7.1, p. 279, and [RLC-ID], Appendix B). 103 The TinyMT32 PRNG initialization depends, among other things, on a 104 parameter set, namely (mat1, mat2, tmat). In order to facilitate the 105 use of this PRNG and make the sequence of pseudo-random numbers 106 depend only on the seed value, this specification requires the use of 107 a specific parameter set (see Section 3.1). This is a major 108 difference with respect to the implementation version 1.1 109 (2015/04/24) that leaves this parameter set unspecified. 111 Finally, the determinism of this PRNG, for a given seed, has been 112 carefully checked (see Section 3.3). It means that the same sequence 113 of pseudo-random numbers should be generated, no matter the target 114 execution platform and compiler, for a given initial seed value. 115 This determinism can be a key requirement as it the case with 116 [RLC-ID] that normatively depends on this specification. 118 2. Definitions 120 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 121 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 122 "OPTIONAL" in this document are to be interpreted as described in BCP 123 14 [RFC2119] [RFC8174] when, and only when, they appear in all 124 capitals, as shown here. 126 3. TinyMT32 PRNG Specification 128 3.1. TinyMT32 Source Code 130 The TinyMT32 PRNG requires to be initialized with a parameter set 131 that needs to be well chosen. In this specification, for the sake of 132 simplicity, the following parameter set MUST be used: 134 o mat1 = 0x8f7011ee = 2406486510 135 o mat2 = 0xfc78ff1f = 4235788063 136 o tmat = 0x3793fdff = 932445695 138 This parameter set is the first entry of the precalculated parameter 139 sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by Kenji Rikitake, 140 and available at [TinyMT-params]. This is also the parameter set 141 used in [KR12]. 143 The TinyMT32 PRNG reference implementation is reproduced in Figure 1. 144 This is a C language implementation, written for C99 [C99]. This 145 reference implementation differs from the original source code as 146 follows: 148 o the original copyright and license have been removed by the 149 original authors who are now authors of this document, in 150 accordance with BCP 78 and the IETF Trust's Legal Provisions 151 Relating to IETF Documents (http://trustee.ietf.org/license-info); 152 o the source code initially spread over the tinymt32.h and 153 tinymt32.c files has been merged; 154 o the unused parts of the original source code have been removed. 155 This is the case of the tinymt32_init_by_array() alternative 156 initialisation function. This is also the case of the 157 period_certification() function after having checked it is not 158 required with the chosen parameter set; 159 o the unused constants TINYMT32_MEXP and TINYMT32_MUL have been 160 removed; 161 o the appropriate parameter set has been added to the initialization 162 function; 163 o the function order has been changed; 164 o certain internal variables have been renamed for compactness 165 purposes; 166 o the const qualifier has been added to the constant definitions; 167 o the code that was dependant on the representation of negative 168 integers by 2's complements has been replaced by a more portable 169 version; 171 172 /** 173 * Tiny Mersenne Twister only 127 bit internal state. 174 * Derived from the reference implementation version 1.1 (2015/04/24) 175 * by Mutsuo Saito (Hiroshima University) and Makoto Matsumoto 176 * (Hiroshima University). 177 */ 178 #include 180 /** 181 * tinymt32 internal state vector and parameters 182 */ 183 typedef struct { 184 uint32_t status[4]; 185 uint32_t mat1; 186 uint32_t mat2; 187 uint32_t tmat; 188 } tinymt32_t; 190 static void tinymt32_next_state (tinymt32_t* s); 191 static uint32_t tinymt32_temper (tinymt32_t* s); 193 /** 194 * Parameter set to use for this IETF specification. Don't change. 195 * This parameter set is the first entry of the precalculated 196 * parameter sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by 197 * Kenji Rikitake, available at: 198 * https://github.com/jj1bdx/tinymtdc-longbatch/ 199 * It is also the parameter set used: 200 * Rikitake, K., "TinyMT Pseudo Random Number Generator for 201 * Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), 202 * September, 2012. 203 */ 204 const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee); 205 const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f); 206 const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff); 208 /** 209 * This function initializes the internal state array with a 210 * 32-bit unsigned integer seed. 211 * @param s pointer to tinymt internal state. 212 * @param seed a 32-bit unsigned integer used as a seed. 213 */ 214 void tinymt32_init (tinymt32_t* s, uint32_t seed) 215 { 216 const uint32_t MIN_LOOP = 8; 217 const uint32_t PRE_LOOP = 8; 218 s->status[0] = seed; 219 s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM; 220 s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM; 221 s->status[3] = s->tmat = TINYMT32_TMAT_PARAM; 222 for (int i = 1; i < MIN_LOOP; i++) { 223 s->status[i & 3] ^= i + UINT32_C(1812433253) 224 * (s->status[(i - 1) & 3] 225 ^ (s->status[(i - 1) & 3] >> 30)); 226 } 227 /* 228 * NB: the parameter set of this specification warrants 229 * that none of the possible 2^^32 seeds leads to an 230 * all-zero 127-bit internal state. Therefore, the 231 * period_certification() function of the original 232 * TinyMT32 source code has been safely removed. If 233 * another parameter set is used, this function will 234 * have to be re-introduced here. 235 */ 236 for (int i = 0; i < PRE_LOOP; i++) { 237 tinymt32_next_state(s); 238 } 240 } 242 /** 243 * This function outputs a 32-bit unsigned integer from 244 * the internal state. 245 * @param s pointer to tinymt internal state. 246 * @return 32-bit unsigned integer r (0 <= r < 2^32). 247 */ 248 uint32_t tinymt32_generate_uint32 (tinymt32_t* s) 249 { 250 tinymt32_next_state(s); 251 return tinymt32_temper(s); 252 } 254 /** 255 * Internal tinymt32 constants and functions. 256 * Users should not call these functions directly. 257 */ 258 const uint32_t TINYMT32_SH0 = 1; 259 const uint32_t TINYMT32_SH1 = 10; 260 const uint32_t TINYMT32_SH8 = 8; 261 const uint32_t TINYMT32_MASK = UINT32_C(0x7fffffff); 263 /** 264 * This function changes the internal state of tinymt32. 265 * @param s pointer to tinymt internal state. 266 */ 267 static void tinymt32_next_state (tinymt32_t* s) 268 { 269 uint32_t x; 270 uint32_t y; 272 y = s->status[3]; 273 x = (s->status[0] & TINYMT32_MASK) 274 ^ s->status[1] 275 ^ s->status[2]; 276 x ^= (x << TINYMT32_SH0); 277 y ^= (y >> TINYMT32_SH0) ^ x; 278 s->status[0] = s->status[1]; 279 s->status[1] = s->status[2]; 280 s->status[2] = x ^ (y << TINYMT32_SH1); 281 s->status[3] = y; 282 /* 283 * The if (y & 1) {...} block below replaces: 284 * s->status[1] ^= -((int32_t)(y & 1)) & s->mat1; 285 * s->status[2] ^= -((int32_t)(y & 1)) & s->mat2; 286 * The adopted code is equivalent to the original code 287 * but does not depend on the representation of negative 288 * integers by 2's complements. It is therefore more 289 * portable, but includes an if-branch which may slow 290 * down the generation speed. 291 */ 292 if (y & 1) { 293 s->status[1] ^= s->mat1; 294 s->status[2] ^= s->mat2; 295 } 296 } 298 /** 299 * This function outputs a 32-bit unsigned integer from 300 * the internal state. 301 * @param s pointer to tinymt internal state. 302 * @return 32-bit unsigned pseudo-random number. 303 */ 304 static uint32_t tinymt32_temper (tinymt32_t* s) 305 { 306 uint32_t t0, t1; 307 t0 = s->status[3]; 308 t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8); 309 t0 ^= t1; 310 /* 311 * The if (t1 & 1) {...} block below replaces: 312 * t0 ^= -((int32_t)(t1 & 1)) & s->tmat; 313 * The adopted code is equivalent to the original code 314 * but does not depend on the representation of negative 315 * integers by 2's complements. It is therefore more 316 * portable, but includes an if-branch which may slow 317 * down the generation speed. 318 */ 319 if (t1 & 1) { 320 t0 ^= s->tmat; 321 } 322 return t0; 323 } 324 326 Figure 1: TinyMT32 Reference Implementation 328 3.2. TinyMT32 Usage 330 This PRNG MUST first be initialized with the following function: 332 void tinymt32_init (tinymt32_t* s, uint32_t seed); 334 It takes as input a 32-bit unsigned integer used as a seed (note that 335 value 0 is permitted by TinyMT32). This function also takes as input 336 a pointer to an instance of a tinymt32_t structure that needs to be 337 allocated by the caller but left uninitialized. This structure will 338 then be updated by the various TinyMT32 functions in order to keep 339 the internal state of the PRNG. The use of this structure admits 340 several instances of this PRNG to be used in parallel, each of them 341 having its own instance of the structure. 343 Then, each time a new 32-bit pseudo-random unsigned integer between 0 344 and 2^32 - 1 inclusive is needed, the following function is used: 346 uint32_t tinymt32_generate_uint32 (tinymt32_t * s); 348 Of course, the tinymt32_t structure must be left unchanged by the 349 caller between successive calls to this function. 351 3.3. Specific Implementation Validation and Deterministic Behavior 353 PRNG determinism, for a given seed, can be a requirement (e.g., with 354 [RLC-ID]). Consequently, any implementation of the TinyMT32 PRNG in 355 line with this specification MUST have the same output as that 356 provided by the reference implementation of Figure 1. In order to 357 increase the compliancy confidence, this document proposes the 358 following criteria. Using a seed value of 1, the first 50 values 359 returned by tinymt32_generate_uint32(s) as 32-bit unsigned integers 360 are equal to values provided in Figure 2, to be read line by line. 361 Note that these values come from the tinymt/check32.out.txt file 362 provided by the PRNG authors to validate implementations of TinyMT32, 363 as part of the MersenneTwister-Lab/TinyMT Github repository. 365 2545341989 981918433 3715302833 2387538352 3591001365 366 3820442102 2114400566 2196103051 2783359912 764534509 367 643179475 1822416315 881558334 4207026366 3690273640 368 3240535687 2921447122 3984931427 4092394160 44209675 369 2188315343 2908663843 1834519336 3774670961 3019990707 370 4065554902 1239765502 4035716197 3412127188 552822483 371 161364450 353727785 140085994 149132008 2547770827 372 4064042525 4078297538 2057335507 622384752 2041665899 373 2193913817 1080849512 33160901 662956935 642999063 374 3384709977 1723175122 3866752252 521822317 2292524454 376 Figure 2: First 50 decimal values (to be read per line) returned by 377 tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a seed 378 value of 1. 380 In particular, the deterministic behavior of the Figure 1 source code 381 has been checked across several platforms: high-end laptops running 382 64-bits Mac OSX and Linux/Ubuntu; a board featuring a 32-bits ARM 383 Cortex-A15 and running 32-bit Linux/Ubuntu; several embedded cards 384 featuring either an ARM Cortex-M0+, a Cortex-M3 or a Cortex-M4 32-bit 385 microcontroller, all of them running RIOT [Baccelli18]; two low-end 386 embedded cards featuring either a 16-bit microcontroller (TI MSP430) 387 or a 8-bit microcontroller (Arduino ATMEGA2560), both of them running 388 RIOT. 390 This specification only outputs 32-bit unsigned pseudo-random numbers 391 and does not try to map this output to a smaller integer range (e.g., 392 between 10 and 49 inclusive). If a specific use-case needs such a 393 mapping, it will have to provide its own function. In that case, if 394 PRNG determinism is also required, the use of floating point (single 395 or double precision) to perform this mapping should probably be 396 avoided, these calculations leading potentially to different rounding 397 errors across different target platforms. Great care should also be 398 put on not introducing biases in the randomness of the mapped output 399 (it may be the case with some mapping algorithms) incompatible with 400 the use-case requirements. The details of how to perform such a 401 mapping are out-of-scope of this document. 403 4. Security Considerations 405 The authors do not believe the present specification generates 406 specific security risks per se. However, neither the TinyMT nor MT 407 PRNG are meant to be used for cryptographic applications. 409 5. IANA Considerations 411 This document does not require any IANA action. 413 6. Acknowledgments 415 The authors would like to thank Belkacem Teibi with whom we explored 416 TinyMT32 specificities when looking to an alternative to the Park- 417 Miller Linear Congruential PRNG. The authors would like to thank 418 Carl Wallace, Stewart Bryant, Greg Skinner, Mike Heard, the three 419 TSVWG chairs, Wesley Eddy, our shepherd, David Black and Gorry 420 Fairhurst, as well as Spencer Dawkins and Mirja Kuhlewind. Last but 421 not least, the authors are really grateful to the IESG members, in 422 particular Benjamin Kaduk, Eric Rescorla, Adam Roach, Roman Danyliw, 423 Barry Leiba, Martin Vigoureux, Eric Vyncke for their highly valuable 424 feedbacks that greatly contributed to improve this specification. 426 7. References 427 7.1. Normative References 429 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 430 Requirement Levels", BCP 14, RFC 2119, 431 DOI 10.17487/RFC2119, March 1997, 432 . 434 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 435 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 436 May 2017, . 438 7.2. Informative References 440 [AdaptiveCrush] 441 Haramoto, H., "Automation of statistical tests on 442 randomness to obtain clearer conclusion", Monte Carlo and 443 Quasi-Monte Carlo Methods 2008, 444 DOI:10.1007/978-3-642-04107-5_26, November 2009, 445 . 448 [Baccelli18] 449 Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P., 450 Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and 451 M. Wahlisch, "RIOT: An Open Source Operating System for 452 Low-End Embedded Devices in the IoT", IEEE Internet of 453 Things Journal (Volume 5, Issue 6), DOI: 454 10.1109/JIOT.2018.2815038, December 2018. 456 [C99] "Programming languages - C: C99, correction 3:2007", 457 International Organization for Standardization, ISO/IEC 458 9899:1999/Cor 3:2007, November 2007. 460 [KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for 461 Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), 462 September 14, 2012, Copenhagen, Denmark, DOI: 463 http://dx.doi.org/10.1145/2364489.2364504, September 2012. 465 [MT98] Matsumoto, M. and T. Nishimura, "Mersenne Twister: A 466 623-dimensionally equidistributed uniform pseudorandom 467 number generator", ACM Transactions on Modeling and 468 Computer Simulation (TOMACS), Volume 8 Issue 1, Jan. 1998, 469 pp.3-30, January 1998, DOI:10.1145/272991.272995, January 470 1998. 472 [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, 473 "Numerical Recipies in C; Second Edition", Cambridge 474 University Press, ISBN: 0-521-43108-5, 1992. 476 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity 477 Check (LDPC) Staircase and Triangle Forward Error 478 Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, 479 June 2008, . 481 [RLC-ID] Roca, V. and B. Teibi, "Sliding Window Random Linear Code 482 (RLC) Forward Erasure Correction (FEC) Scheme for 483 FECFRAME", Work in Progress, Transport Area Working Group 484 (TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in 485 Progress), February 2019, . 488 [TestU01] L'Ecuyer, P. and R. Simard, "TestU01: A C Library for 489 Empirical Testing of Random Number Generators", ACM 490 Transactions on Mathematical Software, Vol. 33, article 491 22, 2007, 2007, 492 . 494 [TinyMT-dev] 495 Saito, M. and M. Matsumoto, "Tiny Mersenne Twister 496 (TinyMT) github site", 497 . 499 [TinyMT-params] 500 Rikitake, K., "TinyMT pre-calculated parameter list github 501 site", . 503 [TinyMT-web] 504 Saito, M. and M. Matsumoto, "Tiny Mersenne Twister 505 (TinyMT) web site", 506 . 508 Authors' Addresses 510 Mutsuo Saito 511 Hiroshima University 512 Japan 514 EMail: saito@math.sci.hiroshima-u.ac.jp 516 Makoto Matsumoto 517 Hiroshima University 518 Japan 520 EMail: m-mat@math.sci.hiroshima-u.ac.jp 521 Vincent Roca 522 INRIA 523 Univ. Grenoble Alpes 524 France 526 EMail: vincent.roca@inria.fr 528 Emmanuel Baccelli 529 INRIA 530 France 532 EMail: emmanuel.baccelli@inria.fr