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