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

Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

nakedsecurity.sophos.com

Post reply on HN
Print view View original

121–128 of 128 posts

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#121

Post by aortega »

damarquis wrote: post #119
aortega wrote: post #22

Earlier quoted context omitted.

You are dangerously fooling yourself by minimizing the importance of those bugs. Cryptography software is not like regular software. It is critical software, like the kind used to run planes or nuclear power plants: People's lives depends on it. People with no programming experience should be literally banned by law from writing critical software. You should take those bugs way more seriously. PS: I have seen a progr…

Cryptography software is usually critical but I think unlike the code for planes and nuclear power plants it doesn't necessarily have to be. Typically cryptography software is advertised as secure against an adversary has unlimited resources. However, the designers of the software can choose whatever threat model they want as long as they make that clear to their users. I am thinking of a disclaimer like "We believe…

I agree this is a much saner way to think about it.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#122

Post by foobarqux »

IsThisObvious wrote: post #49
foobarqux wrote: post #44

Earlier quoted context omitted.

The problem is no one would volunteer to write crypto code under those constraints.

I know people who write crypto software that must conform to formal verification of the algorithm, requires detailed design documentation before a single line of code, etc.

I meant volunteer to mean "not get paid".

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#123

Post by foobarqux »

IsThisObvious wrote: post #118
z-factor wrote: post #91

Earlier quoted context omitted.

Funny thing is that code is then compiled with a compiler was not formally verified, so it's still a 'fingers crossed' situation.

The code generator we use (at my job; not crypto) was written in Coq and formally verified to generate code with certain properties, given properties of the input. I assume that the crypto group I know, who developed most of the code generator I use, takes similar measures to make sure that their verified "theorems" translate correctly to code. The unverified stage is actually the hardware, which is an open problem.

I think in many regulated industries Coq itself would also need to be certified.

What industry is this?

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#124

Post by billforsternz »

axman6 wrote: post #78
billforsternz wrote: post #50

Earlier quoted context omitted.

It's not the most elegant code I've ever seen - but I don't otherwise see a red flag. What's your problem with it ? I don't think the worry that a semi-infinite string of legitimate values >250 is going to come out of randomSalsaByte() is a real, practical problem. You may as well worry that the complete works of Shakespeare asciified might come out of the PRNG. In theory it could happen. In practice, it won't happen…

The issue isn't the potentially infinite loop, it's the fact it creates an uneven distribution of values, giving 0 a 1/250 greater chance of being selected, and thus makes the results of the PRNG more predictable. The article makes this pretty clear...

What part of "ignoring the off by one error" in the parent don't you get ? Edit: Sorry, unnecessarily snarky, and I could have made my (now uneditable) post clearer by saying ">=250" rather than ">250".

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#125

Post by marshray »

tptacek wrote: post #101
marshray wrote: post #61

Earlier quoted context omitted.

Yep. Plus, MT uses a huge amount of memory. I don't see any reason to use it any more now that modern stream ciphers have gotten so fast.

It is the unfortunate de facto standard for built-in noncryptographic RNGs in high-level languages. PHP, Python, and Ruby all rely on MT generators (all 3 have real CSPRNGs too).

Quick, somebody start the NoTwister movement.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#126

Post by IsThisObvious »

foobarqux wrote: post #123
IsThisObvious wrote: post #118

Earlier quoted context omitted.

The code generator we use (at my job; not crypto) was written in Coq and formally verified to generate code with certain properties, given properties of the input. I assume that the crypto group I know, who developed most of the code generator I use, takes similar measures to make sure that their verified "theorems" translate correctly to code. The unverified stage is actually the hardware, which is an open problem.

I think in many regulated industries Coq itself would also need to be certified. What industry is this?

Pressure equipment, specifically sort of mid-scale items for laboratory and small-batch use.

Our low level code (ie, directly controlling machines) is written in the SPARK environment. This code tends not to get updated often, and has a high level of verification to it. It's what actually handles the pressure cut-offs (ie, hard limits on the machine), turning vales, etc.

Our middleware code is based on a specially developed VM that gets code generated for it in Coq, to ensure that it doesn't choke or become unresponsive. However, it's not directly responsible for safety control and has somewhat laxer restrictions.

Coq is useful for demonstrating that the middleware analytics will complete in a given time profile and not crash out the server on erroneous input.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#127

Post by Jach »

eterm wrote: post #88
Jach wrote: post #86

Earlier quoted context omitted.

Even for RPG games, any given PRNG can often be too random for a game. You can make a lot more realistic and enjoyable behaviors by grabbing your random values from a distribution other than uniform 0.0-1.0. (Like a Gaussian distribution, which is everywhere in models of random things that are the sum of many other individual random processes.)

random and uniform are different things. a PRNG isn't "too random", that doesn't make sense. If it's too uniform, sample from other distributions, but to do so usually requires taking output from a PRNG. Indeed using the inverse CDF of any distribution is a map from (0,1) to the desired sample space, following the distribution. As for which PRNG for RPG games, MT is very good because while it isn't cryptographically…

By "too random" I mean that for games, one often wants "predictable randomness" rather than unpredictable randomness, and a stock PRNG or MT can be too unpredictable. (Which is generally good, but not always for games. Or for candy; the colors of M&M's aren't distributed equally.) Picking your random values from a distribution is one way to make them predictable and more life-like. e.g. if you have a target shooting AI, using a built-in rand() function to select an angle and radius on the target is probably okay for the angle, but using it on the radius will give you a bad-looking spread. Whereas a Gaussian-selected radius will look more natural with most of the shots clustered close to the center, and it lets you easily fine-tune the AI's accuracy by adjusting parameters of the Gaussian.

Alternatively, some sets of random values don't look random to humans, so as a game developer you might need to tweak it and make it appear more random to the player. e.g. these are some truly random bits from Hotbits (not a PRNG: https://www.fourmilab.ch/hotbits/secure_generate.html): '001101010011001011001000010100011010011111000001111101010011000111010000111000001011111000111011'. My pattern-matching human brain is annoyed by runs longer than 3 or 4 times, and patterns like 000111 and 111000. If you take time to filter out 'annoyances' you can make the player like your game more, and if you're careful you can do it without decreasing the entropy bits per byte too much.

Re: Anatomy of a pseudorandom number generator – visualising Cryptocat's buggy PRNG

#128

Post by adobriyan »

nikic wrote: post #74
speeder wrote: post #47

I don't understand much of crypto... But I am game developer, and game developers (specially RPG fans) love random numbers. Some games of mine, I suspected something was off with the PRNG, and did something like they did on the ending, I used the random number generator to draw pictures. Biased generators were quite obvious, because they made obvious patterns (one of the worst offenders was C default random function…

MT is not suitable for crypto because after observing 637 values you can predict all further values. 637 is the size of MTs internal state vector and the output of MT are basically just values from that state vector run through a tempering function. That tempering function is invertible, thus by looking at 637 values you get the full state vector, at which point you can generate the next values as usual.

624 values are enough.
Post reply on HN