Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

On Melissa O’Neill’s PCG random number generator

lemire.me

Post reply on HN
Print view View original

81–90 of 90 posts

Re: On Melissa O’Neill’s PCG random number generator

#81

Post by MiceWithYaffle »

starmole wrote: post #79

As an engineer who switched to PCG: - PCG is not crypto, everybody should understand that. It's for simulation and rendering. - PCG mainly replaces Mersenne Twister which is in c++11. The Twister has a LOT more state and is a LOT slower for less randomness. - In rendering and simulation speed really matters, and PCG excels there. - Xorshift is another algorithm in the same class. I would really like to see an objecti…

Yeah, it's not for crypto. But I think it's for more than simulation and rendering. It's meant as a general purpose PRNG. It's just as good for randomized algorithms like picking the pivot in quicksort, or playing games, procedural content generation (PCG!), or whatever you want to use it for.

I think that the whole point of the prediction difficulty stuff is that a library (e.g., C++11's) with general purpose PRNGs can't know how they'll be used. Maybe some idiot write code for a gambling machine in C++ and use whatever PRNG is to hand. There was a story in the news the other week about people going around casinos predicting slot machines, so maybe this has already happened! PCG is trying to make your simulation and rendering code fast while trying to offer at least some defense against egregious misuse.

Basically PCG is trying to be a good all rounder. As you say, it's meant as a replacement for the Mersenne Twister.

Re: On Melissa O’Neill’s PCG random number generator

#82

Post by starmole »

MiceWithYaffle wrote: post #81
starmole wrote: post #79

As an engineer who switched to PCG: - PCG is not crypto, everybody should understand that. It's for simulation and rendering. - PCG mainly replaces Mersenne Twister which is in c++11. The Twister has a LOT more state and is a LOT slower for less randomness. - In rendering and simulation speed really matters, and PCG excels there. - Xorshift is another algorithm in the same class. I would really like to see an objecti…

Yeah, it's not for crypto. But I think it's for more than simulation and rendering. It's meant as a general purpose PRNG. It's just as good for randomized algorithms like picking the pivot in quicksort, or playing games, procedural content generation (PCG!), or whatever you want to use it for. I think that the whole point of the prediction difficulty stuff is that a library (e.g., C++11's) with general purpose PRNGs…

I found the story: https://www.wired.com/2017/02/russians-engineer-brilliant-sl...

And yes, PCG is harder to exploit in this way than the Twister, but you still really should not bet money on it!

Re: On Melissa O’Neill’s PCG random number generator

#83

Post by rockdoe »

MiceWithYaffle wrote: post #78
FabHK wrote: post #16

A few notes: The author writes "Meanwhile, at least one influential researcher (whose work I respect) had harsh words publicly for her result", and then quotes some of these words: Note that (smartly enough) the PCG author avoids carefully to compare with xorshift128+ or xorshift1024*. However, the author fails to note that said "influential researcher", Sebastiano Vigna, is the author of xorshift128+ and related PRN…

I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!) O'Neill has instructions on how to test with PractRand and with TestU01 on her blog ( http://www.pcg-random.org/blog/ ). I had a go with TestU01 on Vigna's generators, and when you test the low 32 bits reversed (for 64-bit PRNGs, you have to test the high 32, the low 32, both forwards and reversed), I found that all Vigna'…

I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!)

The code does explain exactly what the issue is, i.e. that the last bit isn't random:

   This generator passes the PractRand test suite
   up to (and included) 16TB, with the exception of binary rank tests,
   which fail due to the lowest bit being an LFSR; all other bits pass all
   tests. We suggest to use a sign test to extract a random Boolean value.
But I'm tempted to agree this isn't a desirable property for a generic RNG.

How many users of JavaScript know about this property? (it's the default RNG for most browser engines) Or does it not matter because they return 53-bit floats?

Re: On Melissa O’Neill’s PCG random number generator

#84

Post by FabHK »

PhasmaFelis wrote: post #55
lfowles wrote: post #29

Earlier quoted context omitted.

Hah. I used double asterisks, should have seen that coming in hindsight. Muphry's Law.

I've often been frustrated trying to put more than one asterisk (not italic tag) in an HN comment. Serious question, what happened to WYSIWYG? The Web has supported it for like 20 years, why have we standardized on clunky in-line markup for rich text entry, pretty much everywhere?

FWIW, you can indent text in a HN comment (by a few spaces), and you get

  a Blockquote like this, 
  and *asterisks* survive: 2**47

Re: On Melissa O’Neill’s PCG random number generator

#85

Post by FabHK »

tptacek wrote: post #34
dsacco wrote: post #21

Earlier quoted context omitted.

I disagree, I think the peer review functioned exactly as it was supposed to. Her paper doesn't pass the sniff test for me whatsoever when it comes to security analysis. She spent close to no time analyzing the primitives she introduced (and with no proofs or rigor!), meanwhile the thing is 58 pages because she takes the time to explain what "determinism" and "seeds" are to her audience. "Exposition" is, in my opinio…

It's not a security paper. Or at least, I think it isn't? It's not clear to me what journal it was submitted to.

ACM Transactions on Mathematical Software (TOMS)

Re: On Melissa O’Neill’s PCG random number generator

#86

Post by FabHK »

rockdoe wrote: post #83
MiceWithYaffle wrote: post #78

Earlier quoted context omitted.

I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!) O'Neill has instructions on how to test with PractRand and with TestU01 on her blog ( http://www.pcg-random.org/blog/ ). I had a go with TestU01 on Vigna's generators, and when you test the low 32 bits reversed (for 64-bit PRNGs, you have to test the high 32, the low 32, both forwards and reversed), I found that all Vigna'…

I think Vigna's claim is that if you ignore the PractRand tests that fail, it passes. (Really!) The code does explain exactly what the issue is, i.e. that the last bit isn't random: This generator passes the PractRand test suite up to (and included) 16TB, with the exception of binary rank tests, which fail due to the lowest bit being an LFSR; all other bits pass all tests. We suggest to use a sign test to extract a r…

In the comment section to the V8 JavaScript blog post [1], Vigna writes:

  - Technically, it would be better if you used the upper
  52 bits, rather than the lower 52 bits, to generate a
  double. The lowest bit of a xorshift128+ generator is an
  LSFR, and while people has been happy using LSFR for
  decades, it is slightly inferior in quality to all other
  bits. This is really OCD, as computational errors makes
  the lowest bit almost irrelevant, but now you know.
I don't know whether that's been implemented, but the maintainer replied:

  Thanks for the suggestions! I will definitely revisit the 
  current implementation with your tips in mind.
[1] https://v8project.blogspot.nl/2015/12/theres-mathrandom-and-...

Re: On Melissa O’Neill’s PCG random number generator

#87

Post by tptacek »

MiceWithYaffle wrote: post #77
dsacco wrote: post #46

Earlier quoted context omitted.

That's a fair point; it was mostly the presence of the random crypto that annoyed me :)

O'Neill recently mentioned the crypto aspects of PCG in an comment on another post by John D. Cook. I'll just quote it below. But it looks to me like she thought that any analysis she did on the prediction difficulty of PCG wouldn't be well regarded. Also, I notice that lots of people seem to think her paper was too long, but they also claim that it doesn't say enough about their favorite topic. That seems to be happ…

I think we've surrendered some of the "clarity" argument with the sentences in that paper describing which exact instantiation of the non-cryptographic RNG to select for "sensitive" applications.

Even here, in this comment, it's really hard to follow what you're saying. For instance, you've taken the time to compare the "prediction difficulty" of the PCG PRNG to that of a ChaCha20-based DRBG. But ChaCha20 is a stream cipher, a cryptographic primitive. To be competitive with it at producing uncorrelated bits is to be yourself a cryptographic primitive; that is, to argue that an LCG and a trivial mixer is all we ever needed to encrypt data. That would be... newsworthy?

Also: if you're making an appeal to the cryptographic literature, there are better people to cite than Bruce Schneier.

Re: On Melissa O’Neill’s PCG random number generator

#88

Post by tptacek »

MiceWithYaffle wrote: post #80
tptacek wrote: post #15

Earlier quoted context omitted.

It's a weird paper. It's quite long and takes an eternity to reach this simple point. It's also littered with "security concerns" which are confusing at best and misleading at worst; in reality, none of the generators it discusses are suitable for "sensitive applications", even in the corner-case scenario it discusses of needing permutations of all the b-bit integers, a problem we already have cryptographic tools to…

> But I'll confess to not really understanding what all the fuss is about insecure generators. Based on things she's said on her site and in comments on John D. Cook's blog, it's all about algorithmic complexity attacks on randomized algorithms. In other words, if you're doing quicksort on external input with a random pivot, and someone knows the PRNG state, they can make a pathological input that'll trigger quadrati…

And we addressed it with actual cryptography: SipHash. Since cryptographic random number generators are generated with very similar primitives, why wouldn't SipHash be the answer to those problems as well?

Re: On Melissa O’Neill’s PCG random number generator

#89

Post by mathperson »

dsacco wrote: post #27
lowmagnet wrote: post #4

I like this because she is a professor at Harvey Mudd. They took steps to make CS more inclusive, with great results. I appreciate her attitude on accessibility, which is in keeping with that institution's philosophy. That she ran into a paper wall doesn't bother her because she's openly publishing is even better.

Regardless of her attitude on academic accessibility, it is inappropriate for a paper introducing a novel primitive with proposed security considerations to spend the time explaining why determinism is a concern in functions dealing with randomness. This paper could have been 10 pages. If you want to make your research more accessible, there are ways to do that without assuming that your reader is coming in from a de…

I am not sure why you are being downvoted. I think this is clearly true.

An easy way to make research accessible is to write a monograph!

Re: On Melissa O’Neill’s PCG random number generator

#90

Post by hpcjoe »

dsacco wrote: post #37
tptacek wrote: post #35

Earlier quoted context omitted.

Just to be clear: it's not a cryptography paper, is it? Did you figure out what journal it was submitted to?

She submitted it to ACM Transactions on Mathematical Software. I would personally consider it a cryptography paper, for three reasons: 1. She purports to introduce a novel result that bridges "medium-grade" performance characteristics and security characteristics in one primitive. In fact, if you look at the PCG Random website (pcg-random.org), she very clearly compares and emphasizes both performance and security ch…

TOMS has a long and storied history, mostly on numerical codes. I was looking through it in grad school in the late 80s/early 90s for better saner methods in numerical software.

Better PRNGs for simulation is definitely in its bailiwick. Crypto ... maybe less so.

Post reply on HN