Computers are known to be precise and — usually — repeatable. That’s why it is so hard to get something that seems random out of them. Yet random things are great for games, encryption, and multimedia. Who wants the same order of a playlist or slide show every time?
It is very hard to get truly random numbers, but for a lot of cases, it isn’t that important. Even better, if you programming or using a scripting language, there are lots of things that you can use to get some degree of randomness that is sufficient for many purposes. Continue reading “Linux Fu: The Linux Shuffle”→
Need a random number? Sure, you could just roll a die, but if you do, you might invite laughter from nearby quantum enthusiasts. If it’s truly, unpredictably random numbers you need, look no farther than the background radiation constantly bombarding us from the safety of its celestial hideout.
In a rare but much appreciated break from the Nixie tube norm of clock making, [Alpha-Phoenix] has designed a muon-powered random number generator around that warm, vintage glow. Muons are subatomic particles that are like electrons, but much heavier, and are created when pions enter the atmosphere and undergo radioactive decay. The Geiger-Müller tube, mainstay of Geiger counters the world over, detects these incoming muons and uses them to generate the number.
Inside the box, a 555 in astable mode drives a decade counter, which outputs the numbers 0-9 sequentially on the Nixie via beefy transistors. While the G-M tube waits for muons, the numbers just cycle through repeatedly, looking pretty. When a muon hits the tube, a second 555 tells the decade counter to stop immediately. Bingo, you have your random number! The only trouble we can see with this method is that if you need a number right away, you might have to go get a banana and wave it near the G-M tube.
Whether this all makes sense or not, you should check out [Alpha-Phoenix]’s project video, which is as entertaining as it is informative. He’s planning a follow-up video focused on the randomness of the G-M tube, so look out for that.
Many languages feature a random number generator library for help with tasks like rolling a die or flipping a coin. Why, you may ask, is this necessary when humans are perfectly capable of randomly coming up with values?
The data from gathered from running the script with 200 pseudo-random inputs 100,000 times resulted in a distribution of correct guess approximately normal (µ=50% and σ=3.5%). The probability of the script correctly guessing the user’s input is >57% from calculating µ+2σ. The result? Humans aren’t so good at being random after all.
It’s almost intuitive why this happens. Finger presses tend to repeat certain patterns. The script already has a database of all possible combinations of five presses, with a counter for each combination. Every time a key is pressed, the latest five presses is updated and the counter increases for whichever combination of five presses this falls under. Based on this data, the script is able to make a prediction about the user’s next press.
In a follow-up statistic analysis, [ex-punctis] notes that with more key presses, the accuracy of the script tended to increase, with the exception of 1000+ key presses. The latter was thought to be due to the use of a psuedo random number generator to achieve such high levels of engagement with the script.
Some additional tests were done to see if holding shorter or longer sequences in memory would account for more accurate predictions. While shorter sequences should theoretically work, the risk of players keeping a tally of their own presses made it more likely for the longer sequences to reduce bias.
There’s a lot of literature on behavioral models and framing effects for similar games if you’re interested in implementing your own experiments and tricking your friends into giving you some cash.
A truly random number is something that is surprisingly difficult to generate. A typical approach is to generate the required element of chance from a natural and unpredictable source, such as radioactive decay or thermal noise. By contrast it is extremely easy to generate numbers that look random but in fact follow a predictable sequence. A shift register with feedback through an XOR of its output and one of its stages will produce a continuous stream of pseudo-random bits that repeat after a set period.
[KK99] has created the simplest possible pseudo-random binary sequence generator, using a three-bit shift register. It’s realised on a pleasingly retro piece of perfboard, with a CD4047 as clock generator and a 74HC164 shift register doing the work. Unusually the XOR gate is made from discrete transistors, 2N3053s in bulky TO39 packages, and for a particularly old-fashioned look a vintage HP LED display shows the currently generated number. A relatively useless pseudo-random sequence with a period of seven bits is the result, but the point of this circuit is to educate rather than its utility. You can see it in operation in the video below the break.
We had a demonstration of the dangers of using a pseudo-random sequence back in 2016. The German military cipher nicknamed “Tunny” by British codebreakers relied upon a mechanical sequence generator, and the tale of its being cracked led to the development of Colossus, the first stored-program electronic computer.
Twitter is kind of a crazy place. World leaders doing verbal battle, hashtags that rise and fall along with the social climate, and a never ending barrage of cat pictures all make for a tumultuous stream of consciousness that runs 24/7. What exactly we’re supposed to do with this information is still up to debate, as Twitter has yet to turn it into a profitable service after over a decade of operation. Still, it’s a grand experiment that offers a rare glimpse into the human hive-mind for anyone brave enough to dive in.
One such explorer is a security researcher who goes by the handle [x0rz]. He’s recently unveiled an experimental new piece of software that grabs Tweets and uses them as a “noise” to mix in with the Linux urandom entropy pool. The end result is a relatively unpredictable and difficult to influence source of random data. While he cautions his software is merely a proof of concept and not meant for high security applications, it’s certainly an interesting approach to introducing humanity-derived chaos into the normally orderly world of your computer’s operating system.
This hack is made possible by the fact that Twitter offers a “sample” function in their API, which effectively throws a randomized collection of Tweets at anyone who requests it. There are some caveats here, such as the fact that if multiple clients request a sample at the same time they will both receive the same Tweets. It’s also worth mentioning that some characters are unusually likely to make an appearance due to the nature of Twitter (emoticons, octothorps pound signs, etc), but generally speaking it’s not a terrible way to get some chaotic data on demand.
On its own, [x0rz] found this data to be a good but not great source of entropy. After pulling a 500KB sample, he found it had an entropy of 6.5519 bits per byte (random would be 8). While the Tweets weren’t great on their own, combining the data with the kernel’s entropy pool at /dev/urandom provided something that looked a lot less predictable.
The greatest weakness of using Twitter as a source of entropy is, of course, the nature of Twitter itself. A sufficiently popular hashtag on the rise might be just enough to sink your entropy. It’s even possible (though admittedly unlikely) that enough Twitter spam bots could ruin the sample. But if you’re at the point where you think hinging your entropy pool on a digital fire hose of memes and cat pictures is sufficient, you’re probably not securing any national secrets anyway.
(Editor’s note: The way the Linux entropy pool mixes it together, additional sources can only help, assuming they can’t see the current state of your entropy pool, which Twitter cats most certainly can’t. See article below. Also, this is hilarious.)
[Kevin Darrah] recently went out to dinner at a restaurant that was using some cheap LED candles (yuck) instead of the real thing. And in the true spirit of a hacker, he started to notice the patterns programmed into the fake flame repeat over and over again. And like any hacker might, his mind started to devise a better way.
Now’s the time where some of us lazy hackers might grab a microcontroller, and copy and paste in some pseudo-random number generating code you found on the Internet, but not [Kevin]. The basics of his hack uses two shift registers tied together that are fed a single clock signal, and also a latch signal that is slightly delayed version of the same signal made by a RC-time circuit.
The randomness of the output is created is by feeding back the outputs of the shift registers to an XOR gate. If you want to learn more about this, the technique it’s called a “linear feedback shift register“. It’s commonly used as a poor-man’s random number generator, although it’s not technically truly random, statistically it does a very good job. You can see the results in the video after the break where [Kevin] describes the circuit. He wraps up the hack with a battery and solar charging circuit as well to make a completed project.
[Walter] created the entropy library for AVRs for a reliable source of true random numbers. It works by using the watchdog timer’s natural jitter; not fast by any means but most sources of entropy aren’t that fast anyway. By sampling a whole lot of AVR chips and doing a few statistical tests, it turns out this library is actually a pretty good source of randomness, at least as good as a pair of dice.
The circuit itself uses two 8×8 LED matrices from Adafruit, an Arduino, and a pair of buttons. The supported modes are 2d6, 2d4, 2d8, 2d10, 1d12, 1d20, a deck of cards, a single hex number, a single 8-bit binary number, or an eight character alphanumeric password. It’s more than enough for D&D or when you really need an unguessable password. Video demo below.