--- 1/draft-ietf-tsvwg-tinymt32-02.txt 2019-05-27 03:13:10.293355686 -0700 +++ 2/draft-ietf-tsvwg-tinymt32-03.txt 2019-05-27 03:13:10.317356292 -0700 @@ -1,49 +1,48 @@ TSVWG M. Saito Internet-Draft M. Matsumoto Intended status: Standards Track Hiroshima University -Expires: November 17, 2019 V. Roca (Ed.) +Expires: November 28, 2019 V. Roca (Ed.) E. Baccelli INRIA - May 16, 2019 + May 27, 2019 TinyMT32 Pseudo Random Number Generator (PRNG) - draft-ietf-tsvwg-tinymt32-02 + draft-ietf-tsvwg-tinymt32-03 Abstract This document describes the TinyMT32 Pseudo Random Number Generator (PRNG) that produces 32-bit pseudo-random unsigned integers and aims at having a simple-to-use and deterministic solution. This PRNG is a - small-sized variant of Mersenne Twister (MT) PRNG, also designed by - M. Saito and M. Matsumoto. The main advantage of TinyMT32 over MT - is the use of a small internal state, compatible with most target - platforms including embedded devices, while keeping a reasonably good - randomness. + small-sized variant of Mersenne Twister (MT) PRNG [MT98]. The main + advantage of TinyMT32 over MT is the use of a small internal state, + compatible with most target platforms including embedded devices, + while keeping a reasonably good randomness. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." - This Internet-Draft will expire on November 17, 2019. + This Internet-Draft will expire on November 28, 2019. Copyright Notice Copyright (c) 2019 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents @@ -69,48 +68,44 @@ 7.1. Normative References . . . . . . . . . . . . . . . . . . 9 7.2. Informative References . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10 1. Introduction This document specifies the TinyMT32 PRNG, as a specialization of the reference implementation version 1.1 (2015/04/24) by Mutsuo Saito and Makoto Matsumoto, from Hiroshima University: - o Official web site: - o Official github site and reference implementation: - + o Official web site [TinyMT-web] + o Official github site and reference implementation [TinyMT-dev] This specialisation aims at having a simple-to-use and deterministic PRNG, as explained below. - TinyMT is a new small-sized variant of Mersenne Twister (MT) - introduced by Mutsuo Saito and Makoto Matsumoto in 2011. This - document focusses on the TinyMT32 variant (rather than TinyMT64) of - the PRNG, which outputs 32-bit unsigned integers. + TinyMT is a new small-sized variant introduced by Mutsuo Saito and + Makoto Matsumoto in 2011 of the Mersenne Twister (MT) PRNG [MT98]. + This document focusses on the TinyMT32 variant (rather than TinyMT64) + of the TinyMT PRNG, which outputs 32-bit unsigned integers. The purpose of TinyMT is not to replace Mersenne Twister: TinyMT has a far shorter period (2^^127 - 1) than MT. The merit of TinyMT is in its small size of the internal state of 127 bits, far smaller than the 19937 bits of MT. According to statistical tests (BigCrush in - TestU01 and - AdaptiveCrush ) the quality of the outputs of TinyMT seems pretty good in - terms of randomnes (in particular the uniformity of generated - numbers), taking the small size of the internal state into - consideration (see ). From this point of view, TinyMT32 - represents a major improvement with respect to the Park-Miler Linear - Congruential PRNG (e.g., as specified in [RFC5170]) that suffers - several known limitations. However, neither TinyMT nor MT are meant - to be used for cryptographic applications. + TestU01 and AdaptiveCrush), the quality of the outputs of TinyMT + seems pretty good in terms of randomnes (in particular the uniformity + of generated numbers), taking the small size of the internal state + into consideration (see [TinyMT-web]). From this point of view, + TinyMT32 represents a major improvement with respect to the Park- + Miler Linear Congruential PRNG (e.g., as specified in [RFC5170]) that + suffers several known limitations (see for instance [PTVF92], section + 7.1, p. 279, and [RLC-ID], Appendix B). However, neither the TinyMT + nor MT PRNG are meant to be used for cryptographic applications. The TinyMT32 PRNG initialization depends, among other things, on a parameter set -- namely (mat1, mat2, tmat) -- that needs to be well chosen (pre-calculated values are available in the official web site). In order to facilitate the use of this PRNG and make the sequence of pseudo-random numbers depend only on the seed value, this specification requires the use of a specific parameter set (see Section 3.1). This is a first difference with respect to the implementation version 1.1 (2015/04/24) by Mutsuo Saito and Makoto Matsumoto that leaves this parameter set unspecified. A second @@ -140,22 +135,22 @@ The TinyMT32 PRNG requires to be initialized with a parameter set that needs to be well chosen. In this specification, for the sake of simplicity, the following parameter set MUST be used: o mat1 = 0x8f7011ee = 2406486510 o mat2 = 0xfc78ff1f = 4235788063 o tmat = 0x3793fdff = 932445695 This parameter set is the first entry of the precalculated parameter sets in file tinymt32dc/tinymt32dc.0.1048576.txt, by Kenji Rikitake, - and available at . - This is also the parameter set used in [KR12]. + and available at [TinyMT-params]. This is also the parameter set + used in [KR12]. The TinyMT32 PRNG reference implementation is reproduced in Figure 1, with the following differences with respect to the original source code: o the original copyright and licence have been removed, in accordance with BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info); o the source code initially spread over the tinymt32.h and tinymt32.c files has been merged; @@ -385,37 +382,38 @@ avoided, these calculations leading potentially to different rounding errors across different target platforms. Great care should also be put on not introducing biases in the randomness of the mapped output (it may be the case with some mapping algorithms) incompatible with the use-case requirements. The details of how to perform such a mapping are out-of-scope of this document. 4. Security Considerations The authors do not believe the present specification generates - specific security risks per se. + specific security risks per se. However, neither the TinyMT nor MT + PRNG are meant to be used for cryptographic applications. 5. IANA Considerations This document does not require any IANA action. 6. Acknowledgments The authors would like to thank Belkacem Teibi with whom we explored TinyMT32 specificities when looking to an alternative to the Park- - Miler Linear Congruential PRNG. The authors would like to thank - Stewart Bryant, Greg Skinner, the three TSVWG chairs, Wesley Eddy, - our shepherd, David Black and Gorry Fairhurst, as well as Spencer - Dawkins and Mirja Kuhlewind. Last but not least, the authors are - really grateful to the IESG members, in particular Benjamin Kaduk, - Eric Rescorla, and Adam Roach for their highly valuable feedbacks - that greatly contributed to improve this specification. + Miler Linear Congruential PRNG. The authors would like to thank Carl + Wallace, Stewart Bryant, Greg Skinner, the three TSVWG chairs, Wesley + Eddy, our shepherd, David Black and Gorry Fairhurst, as well as + Spencer Dawkins and Mirja Kuhlewind. Last but not least, the authors + are really grateful to the IESG members, in particular Benjamin + Kaduk, Eric Rescorla, and Adam Roach for their highly valuable + feedbacks that greatly contributed to improve this specification. 7. References 7.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . @@ -431,34 +429,58 @@ M. Wahlisch, "RIOT: An Open Source Operating System for Low-End Embedded Devices in the IoT", IEEE Internet of Things Journal (Volume 5, Issue 6), DOI: 10.1109/JIOT.2018.2815038, December 2018. [KR12] Rikitake, K., "TinyMT Pseudo Random Number Generator for Erlang", ACM 11th SIGPLAN Erlang Workshop (Erlang'12), September 14, 2012, Copenhagen, Denmark, DOI: http://dx.doi.org/10.1145/2364489.2364504, September 2012. + [MT98] Matsumoto, M. and T. Nishimura, "Mersenne Twister: A + 623-dimensionally equidistributed uniform pseudorandom + number generator", ACM Transactions on Modeling and + Computer Simulation (TOMACS), Volume 8 Issue 1, Jan. 1998, + pp.3-30, January 1998, DOI:10.1145/272991.272995, January + 1998. + + [PTVF92] Press, W., Teukolsky, S., Vetterling, W., and B. Flannery, + "Numerical Recipies in C; Second Edition", Cambridge + University Press, ISBN: 0-521-43108-5, 1992. + [RFC5170] Roca, V., Neumann, C., and D. Furodet, "Low Density Parity Check (LDPC) Staircase and Triangle Forward Error Correction (FEC) Schemes", RFC 5170, DOI 10.17487/RFC5170, June 2008, . [RLC-ID] Roca, V. and B. Teibi, "Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) Scheme for FECFRAME", Work in Progress, Transport Area Working Group (TSVWG) draft-ietf-tsvwg-rlc-fec-scheme (Work in Progress), February 2019, . -Authors' Addresses + [TinyMT-dev] + Saito, M. and M. Matsumoto, "Tiny Mersenne Twister + (TinyMT) github site", + . + + [TinyMT-params] + Rikitake, K., "TinyMT pre-calculated parameter list github + site", . + + [TinyMT-web] + Saito, M. and M. Matsumoto, "Tiny Mersenne Twister + (TinyMT) web site", + . +Authors' Addresses Mutsuo Saito Hiroshima University Japan EMail: saito@math.sci.hiroshima-u.ac.jp Makoto Matsumoto Hiroshima University Japan