Entries Tagged "random numbers"

Page 1 of 5

Coin Flips Are Biased

Experimental result:

Many people have flipped coins but few have stopped to ponder the statistical and physical intricacies of the process. In a preregistered study we collected 350,757 coin flips to test the counterintuitive prediction from a physics model of human coin tossing developed by Persi Diaconis. The model asserts that when people flip an ordinary coin, it tends to land on the same side it started—Diaconis estimated the probability of a same-side outcome to be about 51%.

And the final paragraph:

Could future coin tossers use the same-side bias to their advantage? The magnitude of the observed bias can be illustrated using a betting scenario. If you bet a dollar on the outcome of a coin toss (i.e., paying 1 dollar to enter, and winning either 0 or 2 dollars depending on the outcome) and repeat the bet 1,000 times, knowing the starting position of the coin toss would earn you 19 dollars on average. This is more than the casino advantage for 6 deck blackjack against an optimal-strategy player, where the casino would make 5 dollars on a comparable bet, but less than the casino advantage for single-zero roulette, where the casino would make 27 dollars on average. These considerations lead us to suggest that when coin flips are used for high-stakes decision-making, the starting position of the coin is best concealed.

Boing Boing post.

Posted on October 16, 2023 at 7:06 AM • View Comments

Bounty to Recover NIST’s Elliptic Curve Seeds

This is a fun challenge:

The NIST elliptic curves that power much of modern cryptography were generated in the late ’90s by hashing seeds provided by the NSA. How were the seeds generated? Rumor has it that they are in turn hashes of English sentences, but the person who picked them, Dr. Jerry Solinas, passed away in early 2023 leaving behind a cryptographic mystery, some conspiracy theories, and an historical password cracking challenge.

So there’s a $12K prize to recover the hash seeds.

Some backstory:

Some of the backstory here (it’s the funniest fucking backstory ever): it’s lately been circulating—though I think this may have been somewhat common knowledge among practitioners, though definitely not to me—that the “random” seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string “Give Jerry a raise”.

At the time, the “pass a string through SHA1” thing was meant to increase confidence in the curve seeds; the idea was that SHA1 would destroy any possible structure in the seed, so NSA couldn’t have selected a deliberately weak seed. Of course, NIST/NSA then set about destroying its reputation in the 2000’s, and this explanation wasn’t nearly enough to quell conspiracy theories.

But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he’d forgotten the string he used!

If you’re a true conspiracist, you’re certain nobody is going to find a string that generates any of these seeds. On the flip side, if anyone does find them, that’ll be a pretty devastating blow to the theory that the NIST P-curves were maliciously generated—even for people totally unfamiliar with basic curve math.

Note that this is not the constants used in the Dual_EC_PRNG random-number generator that the NSA backdoored. This is something different.

Posted on October 12, 2023 at 7:09 AM • View Comments

On the Randomness of Automatic Card Shufflers

Many years ago, Matt Blaze and I talked about getting our hands on a casino-grade automatic shuffler and looking for vulnerabilities. We never did it—I remember that we didn’t even try very hard—but this article shows that we probably would have found non-random properties:

…the executives had recently discovered that one of their machines had been hacked by a gang of hustlers. The gang used a hidden video camera to record the workings of the card shuffler through a glass window. The images, transmitted to an accomplice outside in the casino parking lot, were played back in slow motion to figure out the sequence of cards in the deck, which was then communicated back to the gamblers inside. The casino lost millions of dollars before the gang were finally caught.

Stanford mathematician Persi Diaconis found other flaws:

With his collaborator Susan Holmes, a statistician at Stanford, Diaconis travelled to the company’s Las Vegas showroom to examine a prototype of their new machine. The pair soon discovered a flaw. Although the mechanical shuffling action appeared random, the mathematicians noticed that the resulting deck still had rising and falling sequences, which meant that they could make predictions about the card order.

New Scientist article behind a paywall. Slashdot thread.

Posted on October 24, 2022 at 6:37 AM • View Comments

Breaking RSA through Insufficiently Random Primes

Basically, the SafeZone library doesn’t sufficiently randomize the two prime numbers it used to generate RSA keys. They’re too close to each other, which makes them vulnerable to recovery.

There aren’t many weak keys out there, but there are some:

So far, Böck has identified only a handful of keys in the wild that are vulnerable to the factorization attack. Some of the keys are from printers from two manufacturers, Canon and Fujifilm (originally branded as Fuji Xerox). Printer users can use the keys to generate a Certificate Signing Request. The creation date for the all the weak keys was 2020 or later. The weak Canon keys are tracked as CVE-2022-26351.

Böck also found four vulnerable PGP keys, typically used to encrypt email, on SKS PGP key servers. A user ID tied to the keys implied they were created for testing, so he doesn’t believe they’re in active use.

Posted on March 16, 2022 at 11:35 AM • View Comments

Vulnerability in the Kaspersky Password Manager

A vulnerability (just patched) in the random number generator used in the Kaspersky Password Manager resulted in easily guessable passwords:

The password generator included in Kaspersky Password Manager had several problems. The most critical one is that it used a PRNG not suited for cryptographic purposes. Its single source of entropy was the current time. All the passwords it created could be bruteforced in seconds. This article explains how to securely generate passwords, why Kaspersky Password Manager failed, and how to exploit this flaw. It also provides a proof of concept to test if your version is vulnerable.

The product has been updated and its newest versions aren’t affected by this issue.

Stupid programming mistake, or intentional backdoor? We don’t know.

More generally: generating random numbers is hard. I recommend my own algorithm: Fortuna. I also recommend my own password manager: Password Safe.

EDITED TO ADD: Commentary from Matthew Green.

Posted on July 6, 2021 at 9:27 AM • View Comments

1 2 3 … 5

Sidebar photo of Bruce Schneier by Joe MacInnis.