idnits 2.17.1
draft-ietf-tsvwg-tinymt32-02.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 214 has weird spacing: '...am seed a 32-...'
-- The document date (May 16, 2019) is 1807 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: November 17, 2019 V. Roca (Ed.)
6 E. Baccelli
7 INRIA
8 May 16, 2019
10 TinyMT32 Pseudo Random Number Generator (PRNG)
11 draft-ietf-tsvwg-tinymt32-02
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 November 17, 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 (2^^127 - 1) than MT. The merit of TinyMT is in
94 its small size of the internal state of 127 bits, far smaller than
95 the 19937 bits of MT. According to statistical tests (BigCrush in
96 TestU01 and
97 AdaptiveCrush ) the quality of the outputs of TinyMT seems pretty good in
99 terms of randomnes (in particular the uniformity of generated
100 numbers), taking the small size of the internal state into
101 consideration (see ). From this point of view, TinyMT32
103 represents a major improvement with respect to the Park-Miler Linear
104 Congruential PRNG (e.g., as specified in [RFC5170]) that suffers
105 several known limitations. However, neither TinyMT nor MT are meant
106 to be used for cryptographic applications.
108 The TinyMT32 PRNG initialization depends, among other things, on a
109 parameter set -- namely (mat1, mat2, tmat) -- that needs to be well
110 chosen (pre-calculated values are available in the official web
111 site). In order to facilitate the use of this PRNG and make the
112 sequence of pseudo-random numbers depend only on the seed value, this
113 specification requires the use of a specific parameter set (see
114 Section 3.1). This is a first difference with respect to the
115 implementation version 1.1 (2015/04/24) by Mutsuo Saito and Makoto
116 Matsumoto that leaves this parameter set unspecified. A second
117 difference is the removal of the tinymt32_init_by_array() alternative
118 initialization function, to only keep the simple initialisation
119 through a seed value (see Section 3.2).
121 Finally, the determinism of this PRNG, for a given seed, has been
122 carefully checked (see Section 3.3). It means that the same sequence
123 of pseudo-random numbers should be generated, no matter the target
124 execution platform and compiler, for a given initial seed value.
125 This determinism can be a key requirement as it the case with
126 [RLC-ID] that normatively depends on this specification.
128 2. Definitions
130 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
131 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
132 "OPTIONAL" in this document are to be interpreted as described in BCP
133 14 [RFC2119] [RFC8174] when, and only when, they appear in all
134 capitals, as shown here.
136 3. TinyMT32 PRNG Specification
138 3.1. TinyMT32 Source Code
140 The TinyMT32 PRNG requires to be initialized with a parameter set
141 that needs to be well chosen. In this specification, for the sake of
142 simplicity, the following parameter set MUST be used:
144 o mat1 = 0x8f7011ee = 2406486510
145 o mat2 = 0xfc78ff1f = 4235788063
146 o tmat = 0x3793fdff = 932445695
148 This parameter set is the first entry of the precalculated parameter
149 sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by Kenji Rikitake,
150 and available at .
151 This is also the parameter set used in [KR12].
153 The TinyMT32 PRNG reference implementation is reproduced in Figure 1,
154 with the following differences with respect to the original source
155 code:
157 o the original copyright and licence have been removed, in
158 accordance with BCP 78 and the IETF Trust's Legal Provisions
159 Relating to IETF Documents (http://trustee.ietf.org/license-info);
160 o the source code initially spread over the tinymt32.h and
161 tinymt32.c files has been merged;
162 o the unused parts of the original source code have been removed.
163 This is the case of the tinymt32_init_by_array() alternative
164 initialisation function;
165 o the unused constants TINYMT32_MEXP and TINYMT32_MUL have been
166 removed;
167 o the appropriate parameter set has been added to the initialization
168 function;
169 o the function order has been changed;
170 o certain internal variables have been renamed for compactness
171 purposes;
172 o the const qualifier has been added to the constant definitions.
174
175 /**
176 * Tiny Mersenne Twister only 127 bit internal state.
177 * Derived from the reference implementation version 1.1 (2015/04/24)
178 * by Mutsuo Saito (Hiroshima University) and Makoto Matsumoto
179 * (Hiroshima University).
180 */
181 #include
183 /**
184 * tinymt32 internal state vector and parameters
185 */
186 typedef struct {
187 uint32_t status[4];
188 uint32_t mat1;
189 uint32_t mat2;
190 uint32_t tmat;
191 } tinymt32_t;
192 static void tinymt32_next_state (tinymt32_t* s);
193 static uint32_t tinymt32_temper (tinymt32_t* s);
195 /**
196 * Parameter set to use for this IETF specification. Don't change.
197 * This parameter set is the first entry of the precalculated
198 * parameter sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by
199 * Kenji Rikitake, available at:
200 * https://github.com/jj1bdx/tinymtdc-longbatch/
201 * It is also the parameter set used:
202 * Rikitake, K., "TinyMT Pseudo Random Number Generator for
203 * Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
204 * September, 2012.
205 */
206 const uint32_t TINYMT32_MAT1_PARAM = UINT32_C(0x8f7011ee);
207 const uint32_t TINYMT32_MAT2_PARAM = UINT32_C(0xfc78ff1f);
208 const uint32_t TINYMT32_TMAT_PARAM = UINT32_C(0x3793fdff);
210 /**
211 * This function initializes the internal state array with a
212 * 32-bit unsigned integer seed.
213 * @param s pointer to tinymt internal state.
214 * @param seed a 32-bit unsigned integer used as a seed.
215 */
216 void tinymt32_init (tinymt32_t* s, uint32_t seed)
217 {
218 const uint32_t MIN_LOOP = 8;
219 const uint32_t PRE_LOOP = 8;
220 s->status[0] = seed;
221 s->status[1] = s->mat1 = TINYMT32_MAT1_PARAM;
222 s->status[2] = s->mat2 = TINYMT32_MAT2_PARAM;
223 s->status[3] = s->tmat = TINYMT32_TMAT_PARAM;
224 for (int i = 1; i < MIN_LOOP; i++) {
225 s->status[i & 3] ^= i + UINT32_C(1812433253)
226 * (s->status[(i - 1) & 3]
227 ^ (s->status[(i - 1) & 3] >> 30));
228 }
229 /*
230 * NB: the parameter set of this specification warrants
231 * that none of the possible 2^^32 seeds leads to an
232 * all-zero 127-bit internal state. Therefore, the
233 * period_certification() function of the original
234 * TinyMT32 source code has been safely removed. If
235 * another parameter set is used, this function will
236 * have to be re-introduced here.
237 */
238 for (int i = 0; i < PRE_LOOP; i++) {
239 tinymt32_next_state(s);
241 }
242 }
244 /**
245 * This function outputs a 32-bit unsigned integer from
246 * the internal state.
247 * @param s pointer to tinymt internal state.
248 * @return 32-bit unsigned integer r (0 <= r < 2^32).
249 */
250 uint32_t tinymt32_generate_uint32 (tinymt32_t* s)
251 {
252 tinymt32_next_state(s);
253 return tinymt32_temper(s);
254 }
256 /**
257 * Internal tinymt32 constants and functions.
258 * Users should not call these functions directly.
259 */
260 const uint32_t TINYMT32_SH0 = 1;
261 const uint32_t TINYMT32_SH1 = 10;
262 const uint32_t TINYMT32_SH8 = 8;
263 const uint32_t TINYMT32_MASK = UINT32_C(0x7fffffff);
265 /**
266 * This function changes the internal state of tinymt32.
267 * @param s pointer to tinymt internal state.
268 */
269 static void tinymt32_next_state (tinymt32_t* s)
270 {
271 uint32_t x;
272 uint32_t y;
274 y = s->status[3];
275 x = (s->status[0] & TINYMT32_MASK)
276 ^ s->status[1]
277 ^ s->status[2];
278 x ^= (x << TINYMT32_SH0);
279 y ^= (y >> TINYMT32_SH0) ^ x;
280 s->status[0] = s->status[1];
281 s->status[1] = s->status[2];
282 s->status[2] = x ^ (y << TINYMT32_SH1);
283 s->status[3] = y;
284 /*
285 * The if (y & 1) {...} block below replaces:
286 * s->status[1] ^= -((int32_t)(y & 1)) & s->mat1;
287 * s->status[2] ^= -((int32_t)(y & 1)) & s->mat2;
288 * The adopted code is equivalent to the original code
289 * but does not depend on the representation of negative
290 * integers by 2's complements. It is therefore more
291 * portable, but includes an if-branch which may slow
292 * down the generation speed.
293 */
294 if (y & 1) {
295 s->status[1] ^= s->mat1;
296 s->status[2] ^= s->mat2;
297 }
298 }
300 /**
301 * This function outputs a 32-bit unsigned integer from
302 * the internal state.
303 * @param s pointer to tinymt internal state.
304 * @return 32-bit unsigned pseudo-random number.
305 */
306 static uint32_t tinymt32_temper (tinymt32_t* s)
307 {
308 uint32_t t0, t1;
309 t0 = s->status[3];
310 t1 = s->status[0] + (s->status[2] >> TINYMT32_SH8);
311 t0 ^= t1;
312 t0 ^= -((int32_t)(t1 & 1)) & s->tmat;
313 return t0;
314 }
315
317 Figure 1: TinyMT32 Reference Implementation
319 3.2. TinyMT32 Usage
321 This PRNG MUST first be initialized with the following function:
323 void tinymt32_init (tinymt32_t * s, uint32_t seed);
325 It takes as input a 32-bit unsigned integer used as a seed (note that
326 value 0 is authorized by TinyMT32). This function also takes as
327 input a pointer to an instance of a tinymt32_t structure that needs
328 to be allocated by the caller but left uninitialized. This structure
329 will then updated by the various TinyMT32 functions in order to keep
330 the internal state of the PRNG. The use of this structure authorizes
331 several instances of this PRNG to be used in parallel, each of them
332 having its own instance of the structure.
334 Then, each time a new 32-bit pseudo-random unsigned integer between 0
335 and 2^32 - 1 inclusive is needed, the following function is used:
337 uint32_t tinymt32_generate_uint32 (tinymt32_t * s);
339 Of course, the tinymt32_t structure must be left unchanged by the
340 caller between successive calls to this function.
342 3.3. Specific Implementation Validation and Deterministic Behavior
344 PRNG determinism, for a given seed, can be a requirement (e.g., with
345 [RLC-ID]). Consequently, any implementation of the TinyMT32 PRNG in
346 line with this specification MUST comply with the following criteria.
347 Using a seed value of 1, the first 50 values returned by
348 tinymt32_generate_uint32(s) as 32-bit unsigned integers MUST be equal
349 to values provided in Figure 2. Note that these values come from the
350 tinymt/check32.out.txt file provided by the PRNG authors to validate
351 implementations of TinyMT32, as part of the MersenneTwister-Lab/
352 TinyMT Github repository.
354 2545341989 981918433 3715302833 2387538352 3591001365
355 3820442102 2114400566 2196103051 2783359912 764534509
356 643179475 1822416315 881558334 4207026366 3690273640
357 3240535687 2921447122 3984931427 4092394160 44209675
358 2188315343 2908663843 1834519336 3774670961 3019990707
359 4065554902 1239765502 4035716197 3412127188 552822483
360 161364450 353727785 140085994 149132008 2547770827
361 4064042525 4078297538 2057335507 622384752 2041665899
362 2193913817 1080849512 33160901 662956935 642999063
363 3384709977 1723175122 3866752252 521822317 2292524454
365 Figure 2: First 50 decimal values returned by
366 tinymt32_generate_uint32(s) as 32-bit unsigned integers, with a seed
367 value of 1.
369 In particular, the deterministic behavior of the Figure 1 source code
370 has been checked across several platforms: high-end laptops running
371 64-bits Mac OSX and Linux/Ubuntu; a board featuring a 32-bits ARM
372 Cortex-A15 and running 32-bit Linux/Ubuntu; several embedded cards
373 featuring either an ARM Cortex-M0+, a Cortex-M3 or a Cortex-M4 32-bit
374 microcontroller, all of them running RIOT [Baccelli18]; two low-end
375 embedded cards featuring either a 16-bit microcontroller (TI MSP430)
376 or a 8-bit microcontroller (Arduino ATMEGA2560), both of them running
377 RIOT.
379 This specification only outputs 32-bit unsigned pseudo-random numbers
380 and does not try to map this output to a smaller integer range (e.g.,
381 between 10 and 49 inclusive). If a specific use-case needs such a
382 mapping, it will have to provide its own function. In that case, if
383 PRNG determinism is also required, the use of floating point (single
384 or double precision) to perform this mapping should probably be
385 avoided, these calculations leading potentially to different rounding
386 errors across different target platforms. Great care should also be
387 put on not introducing biases in the randomness of the mapped output
388 (it may be the case with some mapping algorithms) incompatible with
389 the use-case requirements. The details of how to perform such a
390 mapping are out-of-scope of this document.
392 4. Security Considerations
394 The authors do not believe the present specification generates
395 specific security risks per se.
397 5. IANA Considerations
399 This document does not require any IANA action.
401 6. Acknowledgments
403 The authors would like to thank Belkacem Teibi with whom we explored
404 TinyMT32 specificities when looking to an alternative to the Park-
405 Miler Linear Congruential PRNG. The authors would like to thank
406 Stewart Bryant, Greg Skinner, the three TSVWG chairs, Wesley Eddy,
407 our shepherd, David Black and Gorry Fairhurst, as well as Spencer
408 Dawkins and Mirja Kuhlewind. Last but not least, the authors are
409 really grateful to the IESG members, in particular Benjamin Kaduk,
410 Eric Rescorla, and Adam Roach for their highly valuable feedbacks
411 that greatly contributed to improve this specification.
413 7. References
415 7.1. Normative References
417 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
418 Requirement Levels", BCP 14, RFC 2119,
419 DOI 10.17487/RFC2119, March 1997,
420 .
422 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
423 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
424 May 2017, .
426 7.2. Informative References
428 [Baccelli18]
429 Baccelli, E., Gundogan, C., Hahm, O., Kietzmann, P.,
430 Lenders, M., Petersen, H., Schleiser, K., Schmidt, T., and
431 M. Wahlisch, "RIOT: An Open Source Operating System for
432 Low-End Embedded Devices in the IoT", IEEE Internet of
433 Things Journal (Volume 5, Issue 6), DOI:
434 10.1109/JIOT.2018.2815038, December 2018.
436 [KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for
437 Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12),
438 September 14, 2012, Copenhagen, Denmark, DOI:
439 http://dx.doi.org/10.1145/2364489.2364504, September 2012.
441 [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity
442 Check (LDPC) Staircase and Triangle Forward Error
443 Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170,
444 June 2008, .
446 [RLC-ID] Roca, V. and B. Teibi, "Sliding Window Random Linear Code
447 (RLC) Forward Erasure Correction (FEC) Scheme for
448 FECFRAME", Work in Progress, Transport Area Working Group
449 (TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in
450 Progress), February 2019, .
453 Authors' Addresses
455 Mutsuo Saito
456 Hiroshima University
457 Japan
459 EMail: saito@math.sci.hiroshima-u.ac.jp
461 Makoto Matsumoto
462 Hiroshima University
463 Japan
465 EMail: m-mat@math.sci.hiroshima-u.ac.jp
467 Vincent Roca
468 INRIA
469 Univ. Grenoble Alpes
470 France
472 EMail: vincent.roca@inria.fr
473 Emmanuel Baccelli
474 INRIA
475 France
477 EMail: emmanuel.baccelli@inria.fr