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”→
Gosh, the fun we had when digital calculators became affordable enough that mere grade school students could bring one to class. The discovery that the numbers could be construed as the letters of various dirty words when viewed upside down was the source of endless mirth. They were simpler times.
This four-letter-word “clock” aims to recreate that whimsical time a bit, except with full control over the seven-segment displays and no need to look at it upside down. This descends from a word clock [WhiskeyTangoHotel] made previously and relies on a library of over 1000 four-letter words that can be reasonably displayed using seven-segment displays, most of them SFW but some mildly not. A PICAXE is used to select two of the four-letter words to display every second or so, making this a clock only by the loosest of definitions. Word selection is pseudorandom, seeded by noise from a floating ADC pin, but some of the word pairings in the video below seem to belie a non-random sense of humor. As is, there are over a million pairings possible; it might be fun to add in the full set of two- and three-letter words as well and see what sort of merriment ensues.
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.)
Let’s start off with one of my favorite quotes from John von Neumann: “Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.”
What von Neumann is getting at is that the “pseudo” in pseudorandom number generator (PRNG) is really a synonym for “not at all”. Granted, if you come in the middle of a good PRNG sequence, guessing the next number is nearly impossible. But if you know, or can guess, the seed that started the PRNG off, you know all past and future values nearly instantly; it’s a purely deterministic mathematical function. This shouldn’t be taken as a rant against PRNGs, but merely as a reminder that when you use one, the un-guessability of the numbers that it spits out is only as un-guessable as the seed. And while “un-guessability” isn’t a well-defined mathematical concept, or even a real word, entropy is.
That’s why entropy matters to you. Almost anything that your computer wants to keep secret will require the generation of a secret random number at some point, and any series of “random” numbers that a computer generates will have only as much entropy, and thus un-guessability, as the seed used. So how does a computer, a deterministic machine, harvest entropy for that seed in the first place? And how can you make sure you’ve got enough? And did you know that your Raspberry Pi can be turned into a heavy-duty source of entropy? Read on!
One of the standout talks at the 33rd Chaos Communications Congress concerned pseudo-random-number generators (PRNGs). [Vladimir Klebanov] (right) and [Felix Dörre] (left) provided a framework for making sure that PRNGs are doing what they should. Along the way, they discovered a flaw in Libgcrypt/GNUPG, which they got fixed. Woot.
Cryptographically secure random numbers actually matter, a lot. If you’re old enough to remember the Debian OpenSSL debacle of 2008, essentially every Internet service was backdoorable due to bad random numbers. So they matter. [Vladimir] makes the case that writing good random number generators is very, very hard. Consequently, it’s very important that their output be tested very, very well.
How can you generate random bits? Some people think it’s not easy, others will tell you that it’s pretty damn hard, and then there are those who wonder if it is possible at all. Of course, it is easy to create a very long pseudorandom sequence in software, but even the best PRNG (Pseudorandom Number Generator) needs a good random seed, as we don’t want to get the same sequence each time we switch on the unit, do we? That’s why we need a TRNG (True Random Number Generator), but that requires special hardware.
Some high-end microprocessors are equipped with an internal hardware TRNG, but it is, unfortunately, not true for most low-cost microcontrollers. There are a couple of tricks hackers use to compensate. They usually start the internal free running counter and fetch its contents when some external event occurs (user presses a button, or so). This works, but not without disadvantages. First, there is the danger of “locking” those two events, as a timer period may be some derivative of input scan routine timing. Second, the free running time (between switching on and the moment the unit requests a random number) is often too short, resulting in the seed being too close to the sequence start, and thus predictable. In some cases even, there is no external input before the unit needs a random seed!
Despite what has already been discussed, microcontrollers do have a source of true randomness inside them. While it might not be good enough for crypto applications, it still generates high enough entropy for amusement games, simulations, art gadgets, etc.
Most toolchains for embedded system include support for random number generation. But if you’ve read the manual you’ll know that this is really just pseudo random number generation (PRNG). When calling this function the same numbers will always return in the same order unless a different random number seed is supplied in advance. [Gardner] put together a simple and cheap solution for deriving better random number seeds. He reads a voltage from a 555 timer using the ADC on the microcontroller. At first glance it may not seem like a great source of randomness, but he performed some testing and the results look quite promising.
The project is aimed at Arduino-based circuits, but any chip with an ADC will work. The 555 timer is used as a free running oscillator. We know that this not be very stable when compared to even the worst of crystal oscillators, but that’s what makes it work so well as a random seed source. Add to this the low parts count and small size of the additional circuitry and you’ve got a winning combination. So keep this in mind when you need a random number but don’t necessarily need rock solid entropy.