The digital ranging system that measured the distance to the Apollo spacecraft
The basic idea was to send a radio signal to the spacecraft and determine how long it takes to return. Since the signal traveled at the speed of light, the time delay gives the distance. The main problem is that due to the extreme distance to the spacecraft, a radar-like return pulse would be too weak. The ranging system solved this in two ways. First, a complex transponder on the spacecraft sent back an amplified signal. Second, instead of sending a pulse, the system transmitted a long pseudorandom bit sequence. By correlating this sequence over multiple seconds, a weak signal could be extracted from the noise.
In this blog post I explain this surprisingly-complex ranging system. Generating and correlating pseudorandom sequences was difficult with the transistor circuitry of the 1960s. The ranging codes had to be integrated with Apollo’s “Unified S-Band” communication system, which used high-frequency microwave signals. Onboard the spacecraft, a special frequency-multiplying transponder supported Doppler speed measurements. Finally, communicating with the spacecraft required a complex network of ground stations spanning the globe.
Changing std::sort at Google’s Scale and Beyond
We are changing std::sort in LLVM’s libcxx. That’s a long story of what it took us to get there and all possible consequences, bugs you might encounter with examples from open source. We provide some benchmarks, perspective, why we did this in the first place and what it cost us with exciting ideas from Hyrum’s Law to reinforcement learning. All changes went into open source and thus I can freely talk about all of them.
This article is split into 3 parts, the first is history with all details of recent (and not so) past of sorting in C++ standard libraries. Second part is about what it takes to switch from one sorting algorithm to another with various bugs. The final one is about the implementation we have chosen with all optimizations we have done.
The games Nintendo didn't want you to play: Tengen
Recently, I took a look at Nintendo’s MMC line of mappers, and some other boards. All boards for the NES’ western releases had to be manufactured by Nintendo, and so they generally met certain standards set by Nintendo. But these rules were enforced by technology, not by law. And the company that had previously killed the American game industry decided to break those rules. Madness? No. This… is Tengen.
Lots of custom cartridges here.
Some additional info: https://hackmii.com/2010/01/the-weird-and-wonderful-cic/
Harder Drive: Hard drives we didn't want or need
Dissecting Lemire’s nearly divisionless random
The idea was simple, I’ve always felt that code readability is undervalued so I figured I’d put cold hard cash up. I announced a $1,000 pot, divided into $500, $300, and $200 prizes for the most readable implementations of Daniel Lemire’s nearly divisionless algorithm for selecting a random number from an interval. I now have winners to announce and congratulate, and they’re in this blog post, but there’s more to this story.
'A Million Random Digits' Was a Number-Cruncher’s Bible. Now One Has Exposed Flaws in the Disorder.
A 1955 Rand Corp. book had a reputation as the go-to source for figures used by pollsters, analysts, researchers; engineer Gary Briggs has ruined it
I would say ruined is more than a bit strong, but good story.
Mr. Briggs hypothesized a technician dropped cards and put them back in the wrong order. He envisioned running computer simulations to re-create the error by moving a card or two out of place.
Another look at two Linux KASLR patches
In the end, this random number generator was quickly removed, and that was that. But one can still wonder—is this generator secure but unanalyzed, or would it have been broken just to prove a point?
The Linux CSPRNG Is Now Good!
Oceans of ink and hours on stage have been spent to convince the world that the best random number generator is /dev/urandom, the kernel one. And it is, and it’s always been. However, an uncomfortable truth was that the Linux CSPRNG really could have been better than it was. Userspace CSPRNGs couldn’t be better than the kernel one, so our advice was still valid, but that space for improvement always frustrated me.
Good news everyone! In recent years, the Linux CSPRNG got a number of great incremental improvements, and I can now say in good conscience that it’s not only the best, it’s also good.
On Linux's Random Number Generation
I have been asked about the usefulness of security monitoring of entropy levels in the Linux kernel. This calls for some explanation of how random generation works in Linux systems.
So, randomness and the Linux kernel. This is an area where there is longstanding confusion, notably among some Linux kernel developers, including Linus Torvalds himself.
OpenSSH Key Shielding
On June 21, 2019, support for SSH key shielding was introduced into the OpenBSD tree, from which the OpenSSH releases are derived. SSH key shielding is a measure intended to protect private keys in RAM against attacks that abuse bugs in speculative execution that current CPUs exhibit. This functionality has been part of OpenSSH since the 8.1 release. SSH private keys are now being held in memory in a shielded form; keys are only unshielded when they are used and re‐shielded as soon as they are no longer in active use. When a key is shielded, it is encrypted in memory with AES‐256‐CTR; this is how it works:
How a months-old AMD microcode bug destroyed my weekend
Unfortunately, unpatched Ryzen 3000 says “yes” to the CPUID 01H call, sets the carry bit indicating it has successfully created the most artisanal, organic high-quality random number possible... and gives you a 0xFFFFFFFF for the “random” number, every single time.
Unfortunately, after successfully applying the update and rebooting again, I realized my error—yes, Asus showed a later date for the BIOS, but the actual version was the same as the one I already had—3.2.0. My CPU still thought 0xFFFFFFFF was the randomest number ever, always, no matter what.
At this point, I began to get paranoid—systemd had already quietly worked around the bug. But with most applications just quietly ignoring the problem, how would I know if it ever had been patched? What if two years later, I was still vulnerable to stack-smashing that I shouldn’t have been, due to ASLR that wasn’t actually randomizing?
Another entry for the bad workarounds file.
Visual Information Theory
Information theory gives us precise language for describing a lot of things. How uncertain am I? How much does knowing the answer to question A tell me about the answer to question B? How similar is one set of beliefs to another? I’ve had informal versions of these ideas since I was a young child, but information theory crystallizes them into precise, powerful ideas. These ideas have an enormous variety of applications, from the compression of data, to quantum physics, to machine learning, and vast fields in between.
Unfortunately, information theory can seem kind of intimidating. I don’t think there’s any reason it should be. In fact, many core ideas can be explained completely visually!
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.