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