29
$\begingroup$

Obviously, if you need a random number for cryptography, your code should use an api that gets it from hardware. However, not all hardware has a SRNG available. If you are working on a security critical application, and hardware RNG is not available then the appropriate course of action is to abort execution.

BUT, not every application would be deemed security critical. That is to say, while you want security, you are not worried about overly complex attacks because, 1. your application is not worth the effort of being cracked by sophisticated hackers 2. none of your data is considered strictly confidential (you don't want it breached, but it would not be the end of the world).

Assuming a none security critical application, running on a machine without hardware RNG or ECC Memory, would it be viable to allocate a very large amount of memory (perhaps in a long loop) and use the errors that eventually occur as a source of randomness? Would this be more secure than PRNG?

$\endgroup$
11
  • 52
    $\begingroup$ My assumption would be that if you have memory that would have errors often enough to make it a usable source of entropy, well, you probably have problems running any program reliably...If you're talking about deliberately shutting off the dynamic memory refresh, and waiting a while for the memory capacitors to partially discharge, well, that has been proposed before; it wasn't well received (IIRC)... $\endgroup$
    – poncho
    Nov 7 '17 at 20:22
  • 1
    $\begingroup$ @poncho well, you would have to do something like, for example, allocate 2GB of memory and checking it for errors 100000 times, or something along those lines. $\endgroup$ Nov 7 '17 at 20:25
  • 7
    $\begingroup$ What is your definition of "not security critical?" /dev/urandom is good enough for 99.9999% of not-security-critical numbers by my definition of that term. $\endgroup$
    – Cort Ammon
    Nov 8 '17 at 15:58
  • 1
    $\begingroup$ the problem with defining an application as non-security-critical is you can't predict how people will use it and how much trust they will place on it. that's part of why HTTPS is being pushed universally even though some devs would argue their app doesn't need it. i do think it's a worthwhile question whether you can derive good quality entropy from memory errors for secuity-critical applications, but i don't like the idea of saying something as fundamental as an RNG is "good enough" for some security applications and not others. $\endgroup$
    – user371366
    Nov 8 '17 at 17:50
  • 3
    $\begingroup$ @TheCatWhisperer, I ran a RAM test on a newly-built computer last week. A 24-hour memtest run did the equivalent of your checking 2GB for errors 100,000 times, and found nothing. $\endgroup$
    – Mark
    Nov 8 '17 at 22:15
49
$\begingroup$

(..) would it be viable to allocate a very large amount of memory (perhaps in a long loop) and use the errors that eventually occur as a source of randomness?

No. Practical use of memory errors as a source of randomness would require manipulation of DRAM timing parameters, as envisioned in this answer and it's reference.

The rate of memory error in a correctly working computer at ground level is very low; anything larger than one error detected per week (as reported by machine with ECC logging) is reason for maintenance [#]. Hence the proposed method requires a terminally impractical delay to get any entropy, or an unreliable computer; and for one well built, that mostly happens at altitude (especially in the South Atlantic Anomaly). Plus, if the machine has ECC, errors are hard to detect portably (reporting of ECC errors tends to be a proprietary mess); and if it is not, and there are sizably many errors, it is to fear one will eventually prevent the program from running as intended.

More practical sources of entropy include

  • Audio or video input; more generally output of an ADC.
  • Time of events measured to high accuracy relative to CPU clock (e.g. by way of a performance counter as obtained by RDTSC instruction or API to that). Sources include:
    • key presses (value gives extra entropy)
    • mouse/pointing device movement (position gives extra entropy)
    • arrival of network packets
    • availability of data from a spinning hard disk
    • change of second in a real-time clock IC with independent crystal (low entropy rate, but quite reliably entropic)

Extracting the entropy is relatively easy: essentially, hash anything entropic you can get. The one extremely difficult thing is asserting a reliable lower bound of how much entropy was really gathered. Be extremely conservative, and don't assume that something that holds, will. Things change unexpectedly, especially when there's an active adversary, as we assume in crypto.


[#] Reliability studies on DRAM give widely varying estimates. However we are talking like 100 FIT par DRAM IC within a factor of 100, where Failure In Time is the expected number of failures per 109 device⋅hour. Taking the upper extreme 104 FIT, a computer with 4 DIMMs each with 18 DRAM ICs (enough for 32 GiB with ECC using DDR4 mainstream by late 2017), we get 1.2 expected failures per week.

My limited field experience with servers is that when there are ECC alarms more often than once per week, there's a cause, most often a mismatch in memory specs or settings (for new machines only) or a particular bit in one particular IC of a particular DIMM that's marginal (or worn out, for machines that have been humming quietly for some time). The error log's main virtue is to help identifying such condition, and what DIMM to replace rather than scrapping the whole lot.

There are techniques to purposely increase the rate of occurrence of DRAM errors; including lowering the refresh rate much below manufacturer specs, and/or using a RowHammer read/write pattern. However that's extremely dependent on DRAM model. Doing this reliably, portably and within an OS is very difficult; there's a reason MemTest wants to own as much of the machine as feasible.

$\endgroup$
16
  • $\begingroup$ I second the idea of using an audio input, when it's disconnected from anything. A disconnected audio input will pick up a lot of noise at a fairly low level - switch the input to "microphone" rather than "line-in" mode to activate the built-in preamp and you'll have a useful source of electrical noise that's probably about as random as any HRNG based on the principal of electrical noise. Be aware though that an attacker can of course record the same audio input as you and thus have access to the same random data. $\endgroup$ Nov 8 '17 at 7:50
  • 3
    $\begingroup$ @Simone No you're misunderstanding. I'm not suggesting to use a microphone to record the sound, I'm suggesting to use a disconnected microphone input as a source of electrical noise (a disconnected input will always have noise and this noise is amplified by the internal pre-amp). An attacker who has malicious software running on the same computer as the target application could record the same audio input as the target application, and thus have access to the same noise source. $\endgroup$ Nov 8 '17 at 8:35
  • 3
    $\begingroup$ @Simone I imagine that some hardware random number generators will isolate access between different applications. For that matter, a hardware random number generator's value is always changing, so two applications can never query and get the exact same value because they're querying at different points in time. An audio input is always recorded into a buffer (however small) and the same data may quite easily be captured at one point in time and then placed into multiple buffers if multiple applications are recording at the same time. $\endgroup$ Nov 8 '17 at 8:49
  • 4
    $\begingroup$ @TheCatWhisperer: uh, the servers I use most do not have audio input. They do have Intel's RDRAND. $\endgroup$
    – fgrieu
    Nov 8 '17 at 14:11
  • 2
    $\begingroup$ @Simone When using RNGs, it's typically not obvious how those numbers will be used. In fact, that's a major design factor for RNGs. You don't know what aspects of the noise will be important in the end use. Thus, the goal is to minimize the likelyhood of anyone being able to emulate the stream, and typically that is done to a level far beyond the level of entropy that would be truly required, just in case it turns out that your estimator of entropy was very far off. Better safe than sorry. $\endgroup$
    – Cort Ammon
    Nov 8 '17 at 15:56
11
$\begingroup$

It is hard to imagine that you could afford enormous quantities of RAM for your system, but can't afford a hardware RNG, such as a cheap model costing 0.25 USD, or down to 0.01 USD at the cost of some ergonomics, available in internationalized varieties in other countries too. You might even have one in your pocket.

But let's suppose you used ECC RAM which reported to your operating system the count of error events, which in turn you could query easily from your operating system. Consider a Poisson-distributed count of error events at a rate of one per week, as @fgrieu suggested as an upper bound on the rate before you throw it all out and buy new RAM. What is the entropy you attain from the count of errors over the course of a week? The probability of a count $k$ at rate $\lambda$ is $$\operatorname{Poisson}(k; \lambda) = \frac{\lambda^k e^{-\lambda}}{k!}.$$ There's no really nice closed form expression for the entropy of a Poisson-distributed variable, but we can use the series $$\lambda \cdot (1 - \log \lambda) + e^{-\lambda} \sum_{k = 0}^\infty \frac{\lambda^k \log k!}{k!}.$$ If we fix $\lambda = 1$, meaning we measure for a week, this simplifies to $$1 - \log 1 + e^{-1} \sum_{k = 0}^\infty \frac{\log k!}{k!} \approx 1.3\;\mathrm{nat} \approx 1.9\;\mathrm{bit}$$ if I did my calculation correctly.

That is, you get just under two bits of entropy by waiting around twiddling your thumbs for a week—thumbs you could have used to flip coins instead during a much shorter time for much greater entropy. And that's Shannon entropy, not min-entropy like cryptographers use! The min-entropy is exactly $1\;\mathrm{nat} \approx 1.4\;\mathrm{bit}$.

Exercise for the reader: Suppose you could measure the inter-arrival times at some clock resolution (say, days, hours, minutes, seconds), rather than the count at the end—maybe you get hardware interrupt on an event, or you just poll every minute/second/etc. What is the (Shannon, min-) entropy in that case?

$\endgroup$
9
  • 3
    $\begingroup$ Wouldn't you get an entropy from where an error happened? Assuming it is uniformly distributed you get 32 bit (assuming you have 4 GiB of RAM) - significantly more than from timing. $\endgroup$ Nov 8 '17 at 4:14
  • 3
    $\begingroup$ @MaciejPiechotka Right -- and you could improve that further by incorporating information about when the error happened. If you're constantly scrubbing for errors, there's no reason you shouldn't be able to pin this down to the second (DDR4-2400 can manage a throughput of 76 GB/s, way more than you'd need) and so that's another ~19 bits or so, depending on how far you push it. $\endgroup$
    – Charles
    Nov 8 '17 at 7:32
  • 4
    $\begingroup$ In fairness I should mention that the energy costs of scrubbing high-speed RAM constantly will far outweigh the cost of a hardware RNG. $\endgroup$
    – Charles
    Nov 8 '17 at 7:33
  • $\begingroup$ @Charles given the existance of rdrandr the cost might be 0. The point was more that it's incredibly slow (bits/week). $\endgroup$ Nov 8 '17 at 17:41
  • $\begingroup$ @MaciejPiechotka Right, and it remains slow if you add timing information. $\endgroup$
    – Charles
    Nov 8 '17 at 17:55
10
$\begingroup$

I'm assuming that you actually mean memory errors and not initial power up state.

It wouldn't work an iota. There are no memory errors. I say again, there are no memory errors. Modern RAM is pretty good. Just like microprocessors, it either works or doesn't. I've run MemTest86 loads of times. There are three scenarios I've found:

  1. Memory passes with zero failures after running all night.
  2. Memory fails with loads of errors. Remove memory cards, polish /sand the connectors with sandpaper + screwdriver or file and retest. Contact oxidation is a PITA. Go to 1 virtually every time.
  3. Memory fails with a smidgen of errors. Chuck chip away and/or get a refund.

Scenario 3 happens very rarely. That's why most computers (statistically speaking) run non ECC chips. Also Intel doesn't allow consumer ECC and most desktops run okay. Your phone, laptop or tablet won't have it either. And they work most of the time don't they? I have non ECC servers with 365+ days up time. I don't think that a long loop would find any. So it makes AMD's support for ECC rather questionable as a competitive strategy.

The following graph is an extract from a paper titled Memory Errors in Modern Systems. It's only one paper from many, so make of it what you will:-

FIT graph

In summary, the graph shows a monthly error rate for largish computers. You can see that per DRAM chip, the error rate is small. In one day, they got a maximum of 30 FITs /chip /month but that rate decreases with time. A single FIT is a single failure in 1 billion hours of a single device's operation. It is not 30 failures per day. So it only really matters in the exoscale machines they analysed. As your phone proves.

The upshot is that you cannot rely on errors as an entropy source as there aren't any statistically significant amounts. And if you do find some, that's an error and can't be relied upon, so you can't release code to exploit them for entropy distillation. You would have no indication of which machine had errors or how many there were. It seems from Revisiting Memory Errors in Large-Scale Production Data Centers: Analysis and Modeling of New Trends from the Field that it's very difficult to identify a machine that might be suitable for DRAM entropy extraction. They studied the entire Facebook server estate for over a year. Their findings indicate that:-

  1. Errors are very concentrated on specific individual computers. 1% of servers were responsible for 97.8% of the errors. Fix those servers, and you have virtually no entropy. So on the flip side there's a 99% probability that the server you're pointing to at random produces virtually no errors.

  2. It depends on what the machine is doing specifically. Workload type can influence server failure rate by up to 6.5 times.

  3. The majority of errors (unspecified %age) are actually caused by the memory controller and not the DRAM cells.

  4. A final good result from the hypothesis' perspective is that there is a clear correlation between error rate and cell and CPU density. We can all look forward to much less reliable memory (and more entropy) in the future.

Finally as an exercise, how would you use memory errors? It's not possible. MemTest can find them as it's a tiny application running exclusively on a machine. Coming across a randomly located error doesn't crash MemTest. I guess that errors could happen within its program space, but you'd never know as it would just crash and not report it. On a multi-tasking operating system with virtual machines and massive IO, the whole thing might just crash if significant errors occurred. I don't think that you could have the situation where memory errors only occurred in convenient and accessible areas of the memory map.

There are better ways to get entropy from a computer.

$\endgroup$
10
  • 1
    $\begingroup$ I remember reading some where that if you transfer enough data from a hard drive, over the bus, something on the order of several TB you are going to get errors, which makes working with extremely large files difficult. $\endgroup$ Nov 8 '17 at 13:53
  • $\begingroup$ @TheCatWhisperer: You're not going to get errors merely from shuffling data around, not even terabytes of it. (If that were the case, just backing up a significant amount of data would be next to impossible.) It's just that if you already have flaky hardware, long periods of hard work increase the chance it'll flake out. $\endgroup$
    – cHao
    Nov 8 '17 at 16:19
  • $\begingroup$ @cHao: Filesystem developers (especially of ZFS which checksums your data) do say that scrubbing disks is useful. blogs.oracle.com/7000tips/disk-scrub-why-and-when. I'm really not sure whether undetected errors over SATA and memory buses are a thing in non-broken desktops, though, or if this is mostly just to detect data corruption early from hardware that's getting flaky, before it corrupts all your files. $\endgroup$ Nov 8 '17 at 18:40
  • 2
    $\begingroup$ @cHao: also: en.wikipedia.org/wiki/… says that in one year, there's about a 1/3rd chance that any given computer will suffer a memory error. If it doesn't use ECC memory, it will be a real error. It only takes hours or days to copy terabytes, not a year, so I agree that it's generally safe to copy around your data. It's not a bad idea to store checksums (or even a small amount of par2 forward error correction data), though. $\endgroup$ Nov 8 '17 at 18:49
  • 1
    $\begingroup$ @Peter: Don't get it twisted: Wikipedia is a secondary source. It says that a study claimed that in one year, yada yada. Other studies gave different results. It also says a number of studies reported that most errors were "hard" errors (ie: due to flaky hardware rather than, say, cosmic rays). $\endgroup$
    – cHao
    Nov 8 '17 at 19:22
6
$\begingroup$

Not from memory errors, no.

The other answers cover this in detail.

But there's at least a paper that discusses the idea of using SRAM memory contents of RFID chips just after power-on to obtain both a fingerprint of the device and some random bits.

The summary is that the SRAM cells are symmetric structures of 6 transistors, which are meta-stable at one of two configurations, 0 or 1. At power-on, the two sides of the SRAM cell compete for dominance. Which one wins depends on small intrinsic differences between the transistors, and on noise.

In some cells, these manufacturing differences dominate, and the cell reliably powers up as 0, or 1. These can be used to derive a fingerprint.

In other cells, these differences are so small that noise dominates the outcome, and these cells may power up as either value. These can be used to obtain some entropy.

This an image from the paper. On the left, 0/1 skew drawn as a diagram. On the right, a visual representation of a memory area. Black cells are bits that reliably initialize to 0; white cells reliably initialize to 1; and the gray cells may initialize to either state:

diagram from the paper

The paper is Initial SRAM State as a Fingerprint and Source of True Random Numbers for RFID Tags, by Daniel E. Holcomb, Wayne P. Burleson, and Kevin Fu.

It focuses on RFID tags (which often lack the hardware for proper RNG), but I imagine it should be viable on many other platforms. It also targets SRAM, because of its symmetrical structure. I'm not sure if the technique generalizes to DRAM or other memory types, but many computing devices contain some SRAM somewhere that may be used for this (e.g.: processor caches).

$\endgroup$
1
  • $\begingroup$ DRAM works by storing bits in capacitors. These discharge over time. In other words, the bits naturally reset. That is why DRAM needs a periodic refresh. Given a low-enough hardware access, you could stall the refresh and determine which bits are the fastest to reset. $\endgroup$
    – MSalters
    Nov 9 '17 at 12:52
4
$\begingroup$

It has already been pointed out that the memory errors are too infrequent to be useful. There's another problem, though--memory errors due to imperfections in the chip (as opposed to being in the path of a cosmic ray) aren't very random. They're the result of data bleeding somewhere. Your keys will show a very non-random distribution and anyone attacking it will probably know that and prioritize which keys to try first.

Besides, if you need randomness without a high security situation, bang on the keyboard or wiggle the mouse.

$\endgroup$
2
  • $\begingroup$ I don't think that's a problem. Obviously you'd whiten the entropy with a hash or similar. $\endgroup$ Nov 8 '17 at 10:21
  • 2
    $\begingroup$ @MartinBonner That's actually a huge problem, depending on how the error is used. For example if the position of the error is used (as proposed in another answer), and the actual errors only happen at a few certain positions, then the real entropy is much, much lower than estimated - and hashing can not increase entropy (no deterministic algorithm can). $\endgroup$
    – tylo
    Nov 8 '17 at 12:22
4
$\begingroup$

No, as already indicated, waiting for memory errors is not a good idea. First of all, you would very much rely on the specific memory type. If somebody would replace the memory with Error Checking & Correcting (ECC) memory then you would already run into problems. The number of memory errors would be minimal to non-existent on modern computers, and allocating/scanning the entire memory would be very CPU and memory bandwidth consuming. The number of memory errors may also be environmentally sensitive. An attacker could, for instance, lower the temperature to try to minimize the entropy generated by memory errors.

What is sometimes performed is to allocate memory and read it out without wiping it, reading back any info that might be present in such memory. This needs to be an OS function because the OS could very well wipe the memory itself. This is usually only performed to add a bit of entropy to the RNG, not as the main source. Furthermore, it has been proven dangerous: the Debian and Ubuntu Linux distributions were immediately affected when a static code analysis tool discovered the reading of uninitialized memory and a developer removed this source of entropy - unfortunately including with all the other entropy sources.


Using small timing differences (in nano-seconds if a good timer is available) seems to be one of the best ways to collect entropy if a good True Random Generator isn't available. It still has some problems such as running in a headless environment or VM though. Obviously with the SSD's becoming prevalent using HDD's characteristics for a random source is not such a good idea anymore.

$\endgroup$
3
  • $\begingroup$ Can you actually get ns timing information on DRAM? I know of no way to actually get to the DRAM timers outside of a controller. When we make ICs, we have access to these because we need to blow the rows on bad DRAM blocks; however, I don't know of anyone ever doing late latching. Do you have a good reference for this? $\endgroup$
    – b degnan
    Nov 7 '17 at 23:22
  • 1
    $\begingroup$ @bdegnan: I believe that the idea is to look at the cycle counter on the CPU; that is, small differences in how long it takes the DRAM to respond will show up as delta in the number of CPU cycles... $\endgroup$
    – poncho
    Nov 7 '17 at 23:39
  • $\begingroup$ I think you got the "uninitialized memory read" explanation wrong. As I recall it, the risk was that the compiler spotted an uninitialized memory read, and propagated that to the RNG state itself. The problem there was, from an optimizer viewpoint<uninitialized> XOR 1 = <uninitialized>, so the XOR can be safely removed. $\endgroup$
    – MSalters
    Nov 9 '17 at 13:20
2
$\begingroup$

Yes, this is possible, see for example this paper from ETH Zurich and Carnegie Mellon University.

We propose D-RaNGe, a mechanism for extracting true random numbers with high throughput from unmodied commodity DRAM devices on any system that allows ma- nipulation of DRAM timing parameters in the memory con- troller. D-RaNGe harvests fully non-deterministic random numbers from DRAM row activation failures, which are bit errors induced by intentionally accessing DRAM with lower latency than required for correct row activation.

It can provide sustained MB/s of randomness, if a large amount of RAM is used (the amount used can be changed on the fly, it doesn't interfere with the rest of the RAM) even hundreds of MB/s.

$\endgroup$
5
  • $\begingroup$ Meta-stability is commonly leveraged for TRNGs, but do you think that D-RaNGe can be made to run on standardised kit rather than via FPGAs? $\endgroup$
    – Paul Uszak
    Mar 5 at 13:20
  • $\begingroup$ @PaulUszak I added a quote from the conclusion section of the paper that should answer your question. So some systems would need to be changed, but it's small cheap changes that don't require an FPGA per se. $\endgroup$
    – Nobody
    Mar 5 at 13:24
  • $\begingroup$ @PaulUszak I just realized that my own summary of the technique was actually wrong, which is why I deleted it in favour of the quote. They actually reduce latency, not increase it, which is also why such high bandwidths can be attained. They don't give the sense amplifiers enough time to work, that's where the randomness comes from. They don't let charge dissipate so that the sense amplifiers randomly go either way, even though that might also work. $\endgroup$
    – Nobody
    Mar 5 at 13:36
  • $\begingroup$ The catch is "on any system that allows manipulation of DRAM timing parameters in the memory controller". How realistic is this for the practitionner? $\endgroup$
    – fgrieu
    Mar 5 at 13:46
  • 1
    $\begingroup$ @fgrieu I think it's more targetted at developers of SoC/chipsets/CPUs. They can easily enable such a function. A consumer likely cannot. $\endgroup$
    – Nobody
    Mar 5 at 13:49
1
$\begingroup$

I'm not sure about memory errors, but I did successfully write a shuffling algorithm using the unknown execution order of parallel computing. I would move cards(ints) from one deck(list) to another by simultaneously passing every card to different threads and had all the threads 'race' to reinsert them back into another deck. When performed repeatedly, constantly for a few seconds, the deck seems completely shuffled and I never got the same result twice even though I was running the same code. over and over even in the same computer and same environment. But I guess it heavily depends on the environment its executing in whether it's random enough.

$\endgroup$
3
  • 1
    $\begingroup$ I would be very concerned with using this for entropy... The OS that is scheduling the threads is still deterministic. I suspect that the entropy generated by this technique would be quite low $\endgroup$ Nov 9 '17 at 14:33
  • $\begingroup$ @TheCatWhisperer I'm not so sure. I've been playing with the same thing. Whilst the instruction to instruction steps are deterministic, given the billions of ops and branches & interrupts, there's a certain level of unpredictable chaotic behaviour at the macroscopic scale. And Java's SecureRandom uses this method to self seed when necessary. It might be usable entropy. $\endgroup$
    – Paul Uszak
    Nov 9 '17 at 21:38
  • $\begingroup$ @TheCatWhisperer Actually it's surprisingly high and pretty much confirmed. I've proved it with jitter in Java's nanotime(), Shipilёv has, and there is the Haveged daemon which really boosts /dev/random. It's called deterministic chaos. $\endgroup$
    – Paul Uszak
    Mar 5 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.