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