The history of Tetris randomizers
> In Tetris, a randomizer is a function which returns a randomly chosen piece. Over the years, the rules of how pieces are chosen has evolved, affecting gameplay and actual randomness.
> Several of them have been reversed engineered and documented. I’ve curated a list of ones that I believed to be important and show how the state of Tetris has changed over the years.
The Synchronization of Periodic Routing Messages
> The paper considers a network with many apparently-independent periodic processes and discusses one method by which these processes can inadvertently become synchronized. In particular, we study the synchronization of periodic routing messages, and offer guidelines on how to avoid inadvertent synchronization. Using simulations and analysis, we study the process of synchronization and show that the transition from unsynchronized to synchronized traffic is not one of gradual degradation but is instead a very abrupt ‘phase transition’: in general, the addition of a single router will convert a completely unsynchronized traffic stream into a completely synchronized one. We show that synchronization can be avoided by the addition of randomization to the traffic sources and quantify how much randomization is necessary. In addition, we argue that the inadvertent synchronization of periodic processes is likely to become an increasing problem in computer networks.
Cache Attacks on CTR_DRBG
> This post presents results from our paper “Pseudorandom Black Swans: Cache Attacks on CTR_DRBG”. We illustrate how omissions in the threat model of a U.S government’s standard lead to a practical, end-to-end attack on the most popular generator contained within.
OpenSSH Taking Minutes To Become Available, Booting Takes Half An Hour ... Because Your Server Waits For A Few Bytes Of Randomness
> Basically as of now the entropy file saved as /var/lib/systemd/random-seed will not - drumroll - add entropy to the random pool when played back during boot. Actually it will. It will just not be accounted for. So Linux doesn’t know. And continues blocking getrandom(). This is obviously different from SysVinit times2 when /var/lib/urandom/random-seed (that you still have lying around on updated systems) made sure the system carried enough entropy over reboot to continue working right after enough of the system was booted.
And then... it just kinda keeps getting worse. The problem is understandable, the inability to resolve it less so.
Looking for Entropy in All the Wrong Places
> Imagine we’re writing a C program and we need some random numbers.
Ethercombing: Finding Secrets in Popular Places
> In this paper we examine how, even when faced with this statistical improbability, ISE discovered 732 private keys as well as their corresponding public keys that committed 49,060 transactions to the Ethereum blockchain. Additionally, we identified 13,319 Ethereum that was transferred to either invalid destination addresses, or wallets derived from weak keys that at the height of the Ethereum market had a combined total value of $18,899,969. In the process, we discovered that funds from these weak-key addresses are being pilfered and sent to a destination address belonging to an individual or group that is running active campaigns to compromise/gather private keys and obtain these funds. On January 13, 2018, this “blockchainbandit” held a balance of 37,926 ETH valued at $54,343,407.
> In an experiment, we picked a private key of 1, for no reason other than that it is the lower bound of a possible private key for secp256k1 and it also lies within the 1 to 232-1 range of a 32-bit truncated key. We use the private key 0x0000000000000000000000000000000000000000000000000000000000000001 to derive the public Ethereum address 0x7e5f4552091a69125d5dfcb7b8c2659029395bdf.
> Proof of work algorithm based on random code execution
How to generate uniformly random points on n-spheres and n-balls
> For many Monte Carlo methods, such as those in graphical computing, it is critical to uniformly sample from $d$-dimensional spheres and balls. This post describes over twenty different methods to uniformly random sample from the (surface of) a $d$-dimensional sphere or the (interior of) a $d$-dimensional ball.
TLS: 64bit-ish Serial Numbers & Mass Revocation
> During a recent discussion about the DarkMatter CA on a Mozilla mailing list, it was found that their 64-bit serial numbers weren’t actually 64 bits, and it opened a can of worms. It turns out that the serial number was effectively 63 bits, which is a violation of the CA/B Forum Baseline Requirements that state it must contain 64 bits of output from a secure random number generator (CSPRNG). As a result of this finding, 2,000,000 certificates or more may need to be replaced by Google, Apple, GoDaddy and others.
Probability and the Real World
> What aspects of the real world involve chance? What does mathematical probability tell about about those aspects? What concepts from mathematical probability can be illustrated by interesting contemporary real data? This web site records my efforts to articulate some answers to such questions. It is aimed at readers who have either read some “popular science” style account of probability, or taken a college course involving probability. So I won’t explain very basic stuff, and I mostly avoid discussing material easily found elsewhere.
A Survey of $RANDOM
> Most Bourne shell clones support a special RANDOM environment variable that evaluates to a random value between 0 and 32,767 (e.g. 15 bits). Assigment to the variable seeds the generator. This variable is an extension and did not appear in the original Unix Bourne shell. Despite this, the different Bourne-like shells that implement it have converged to the same interface, but only the interface. Each implementation differs in interesting ways. In this article we’ll explore how $RANDOM is implemented in various Bourne-like shells.
wump: incorrect wumpus movement probability
> The computation of wumpus movement probability in games/wump/wump.c has a parenthesis problem that causes it not to work the way it evidently is meant to.
Running from the past
> Functional programming encourages us to program without mutable state. Instead we compose functions that can be viewed as state transformers. It’s a change of perspective that can have a big impact on how we reason about our code. But it’s also a change of perspective that can be useful in mathematics and I’d like to give an example: a really beautiful technique that alows you to sample from the infinite limit of a probability distribution without needing an infinite number of operations.
The following candidates are listed in a randomly-selected order.
Prove it isn’t random...
Guarder: A Tunable Secure Allocator
> Due to the on-going threats posed by heap vulnerabilities, we design a novel secure allocator --- Guarder --- to defeat these vulnerabilities. Guarder is different from existing secure allocators in the following aspects. Existing allocators either have low/zero randomization entropy, or cannot provide stable security guarantees, where their entropies vary by object size classes, execution phases, inputs, or applications. Guarder ensures the desired randomization entropy, and provides an unprecedented level of security guarantee by combining all security features of existing allocators, with overhead that is comparable to performance-oriented allocators.
Source doesn’t appear live yet: https://github.com/UTSASRG/Guarder
Caught Up in the Captcha
> The code which popped up was “S i u x q F b j NaN 4”. He hit the “new code” button, and got “T o A 0 J V s L NaN a”. In fact, “NaN” showed up in the penultimate position in every code.
Fact of the day:
> Calling ++ on a string assigns NaN to the variable.
A Pseudorandom Generator
> Mathematicians: Hold my Borel sets..
When generating a random password, the result must still be a valid string
> A customer had a problem with auto-generated random passwords. Their password generator generated a string by choosing each character randomly with a code unit from U+0001 to U+FFFF. (They avoided U+0000 because that is the string terminator.) They didn’t mind that the resulting passwords were untypeable, because the passwords were going to be entered programmatically.
And then, oops.
Fast Random Integer Generation in an Interval
> Pseudo-random values are usually generated in words of a fixed number of bits (e.g., 32 bits, 64 bits) using algorithms such as a linear congruential generator. We need functions to convert such random words to random integers in an interval ([0,s)) without introducing statistical biases. The standard functions in programming languages such as Java involve integer divisions. Unfortunately, division instructions are relatively expensive. We review an unbiased function to generate ranged integers from a source of random words that avoids integer divisions with high probability.