[Cryptography] Real-world crypto/PRNG problem: Bridge

[Jon Callas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256


> On Aug 23, 2016, at 1:37 AM, Jerry Leichter <leichter at lrw.com> wrote:
> 
> [A couple of posts factoring the multiplier]
> The quality of a LCG (for appropriate use, which this is not) does *not* require a prime multiplier.  (That was the advice many, many years ago before anyone really did a proper analysis.  There are bad primes and good non-primes.)

Yeah, I was irritated at the tone in which they said that they used the "large prime" because to my intuition, I might consider a prime that you'd use in secure-ish integer RSA/DH to be the bare minimum of "large" -- at least 2-3Kb. If I can paste it into a web page to check primality, it isn't large.

And well, these days an LCG just isn't appropriate for anything, because of how many better solutions there are.

The first suggestion should be /dev/random. Why not use it? It's within epsilon of a true random number generator for many epsilon. It's also darned easy to use. The major reason to go elsewhere is repeatability / audit which can be argued on either side. The argument that asks, "If we used physical decks of cards, you'd have to just trust us that we shuffled them enough, so why does this bug you?" is pretty good.

Past that, there are three basic paradigms. A cipher in counter mode (or equivalent), an iterated hash function, or something like the Mersenne Twister are all great. The choice of suitable PRP/PRFs is wide. 

I go for the iterated hash function because it's the most easy to set up and use. You can throw anything you want into the seed. Have your seed be some catchphrase like "The reign in Spain is plainly offensive to the Catalunyans" and you're good. If you don't think you're good, throw in the data and time to a hundredth of a second (like the ACBL was doing). Sure. No problem. Heck, pull 256 bits off of /dev/random, print them in hexidecimal, and publish the *whole* thing as the verifiable starting seed. Sure. Have at it. It's robust enough that you can do post-processing like toss all the bytes that aren't in [1->52] if that floats your boat. You can also pick your function accordingly. If you don't like SHA-256, use SHA-512 (which is *faster* than SHA-256 on a 64bit machine), don't like those, use Skein-1024, which is even faster than SHA-512. If you don't like that, well, there's Mersenne Twister.

	Jon




-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.3.0 (Build 9060)
Charset: us-ascii

wsBVAwUBV7zNIvaTaG6hZJn9AQizPAf8CaK+D6xF+ewBIzPvlWzj+jhQgajq6xJB
hlXjOhsxvYn2UvSLz2sfwUxkzKhH9dUE2ivw+PMq7hLbbBUGx81wKG2lUq15J71U
WHgdPr4gwKwIQFMSWoOqvoJ4VjGS9zK/XoU4sYS5G+IkfDwIUg9RmIr4cfRHxBZM
2SaKoM5QrnZwJ8l7fgur5A+b+5VOW+0MFyBdcGXx4dBWpGF2Fw67RQHWuQooEU4x
zsw/zTd3sbCfo67FFZjyoX5N5HjjasFz4vYiWR4Q70EUiVKecyGD/iempuvzTXXT
HM24Ql52K0x/vg/ljI8tZXdXnEDpZRxSdH4+uYJuZNFsfh+Nddv1aQ==
=TuB2
-----END PGP SIGNATURE-----