Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm thinking about buying a USB TRNG. How do I evaluate its randomness? I'm sure some are better than others but which is which? Are thermal-noise better than radio-noise TRNGs?

share|improve this question
1  
Check the documentation. How has the manufacturer ensured that the output is unbiased? By using conditioning (using what method and with which security parameters), or by tuning the hardware to ensure the raw unconditioned output does not show any statistical bias (after how many requests)? –  Henrick Hellström May 20 '13 at 7:42
    
And how good are the documentations? –  user1028028 May 20 '13 at 7:50
    
entropykey.co.uk/tech is this good? –  user1028028 May 20 '13 at 7:52
1  
I think you are probably asking the wrong question for this forum; this is not the right place to ask for product recommendations. However, theoretical cryptography can tell how to use a not necessarily completely reliable TRNG for seeding a PRNG in such way that you at least do not make matters worse. –  Henrick Hellström May 20 '13 at 8:05
3  
I think the question, as stated, is a perfectly fine question. It's not asking for product recommendations; it is asking about how one can evaluate a range of products out there. Seems like a great question to me! (The follow-on questions in the comments about specific products, however, are not good questions: they do not belong on this site. Search for "shopping question" to learn more about why not.) –  D.W. May 22 '13 at 4:25
show 2 more comments

1 Answer

up vote 15 down vote accepted

Evaluating a TRNG device positively requires knowing its structure, both to evaluate the actual amount of entropy it produces, and the possibility to detect a field failure.

Some devices sold as TRNG are in fact a TRNG subsystem followed by a PRNG, which produces the output of the device. In that case, if the PRNG is any good, the output of the device may appear random even though the TRNG subsystem produces no or little entropy, opening the possibility of an attack (perhaps just by enumerating the possible outputs of the TRNG subsystem), especially for an attacker knowing enough about the PRNG.

To illustrate: consider an hypothetical Smart Card with an RNG amounting to a TRNG subsystem followed by an LFSR-based PRNG, which task is to hide any small imperfection of the TRNG subsystem. In case of total failure of the TRNG subsystem, perhaps induced by very cold temperature (as obtained non-destructively by evaporation of a liquefied gas poured on the card), it is easy to guess future output from past one (if the PRNG has few state bits, the output has a short period; even with many state bits, the full state is known after that many bits have been output, with knowledge of the LFSR feedback; even when that's unknown, Berlekamf-Massey allows an efficient attack). There might be less obvious failure modes at different temperatures. If the PRNG is fair (e.g. based on the ASG and enough state bits) but secret, only those in the know of the PRNG design are in a good position to detect the failure, or exploit it.

To avoid this, a modern Smart Card RNG may keep the same basic structure, but with hardware to detect total failure of the TRNG subsystem (e.g. when it outputs constant 0 or constant 1), with some access by the software to the output of the TRNG, to enable testing and certification. Any cryptographic TRNG should have some monitoring system able to detect its failures. In the case of a USB RNG, mere accidental under-voltage could cause the source to fail; and USB ports fuses, hubs and their power supply do fail! Monitoring is a must in contexts where an adversary is in a position induce failure. The monitoring system can be hardware or software, internal or external.

This is a requirement in the AIS31 scheme for common-criteria security evaluation of TRNG (index in German, linking to documents in English; see also how French authorities have been using AIS31 method, including some reservation in section 5). This the best such methodology I've used, although I find it much more complex than necessary to the point of being confusing, and not free from error especially in the examples. My advice if you want to assess by yourself the soundness of a TRNG (rather than delegate that to security certification) is to follow the principles behind AIS31, which I can loosely outline as:

  • the structure of the RNG must be known and it must guide the evaluation;
  • the TRNG hardware source must be modeled in some way;
  • there should be some access to the output of that TRNG hardware source, allowing to check experimentally that the model is sound;
  • some system must monitor and detect possible failures of the TRNG hardware source, and in that event prevent operation (such monitoring system typically uses the output of the TRNG hardware source);
  • the model of the TRNG hardware source must support the effectiveness of that monitoring system;
  • before actual use as key material, the output of the TRNG hardware source must be post-processed by a PRNG, preferably a cryptographically strong PRNG;
  • the model of the TRNG hardware source must support that comfortably more entropy is fed in the (CS)PRNG than is necessary for security of the output of the (CS)PRNG in any situation where the monitoring system allows operation;
  • the false alarm rate of the monitoring system should be functionally tolerable (that one tends to be hard to demonstrate).

With access to a raw bit stream produced by a TNRG hardware source, at a point amounting to the output of an analog comparator followed by sampling with a clock, one could do worse than experimentally evaluating the entropy in sub-samples of say 4 to 16 bits (depending on RAM resources and time allowance) by frequency counting, computing experimental entropy from that; doing this as monitoring, with some threshold comfortably below the experimental value; assuming the real entropy is a small fraction of what the threshold supports; and post-processing the whole output with a CSPRNG.


A note on thermal noise vs "radio noise" TRNG sources: I've never met the later, and suspect that it is hard to prove that an attacker can't beam some RF signal towards the TRNG source, strong enough to turn its output into a square wave under the attacker's control.

Thermal noise TRNGs are more classic. They are known to be susceptible to temperature variations; in theory, the colder the less entropy; but high temperatures can introduce undesirable effects in the detector following the source. This might need to be considered (it is very relevant in a Smart Card, not much to something hooked to a PC operated in a trusted environment).

My limited understanding of physics make me see thermal noise as having its origin in quantum noise. I'm equally confident in either as a source of unguessable bits for cryptographic purposes. In my opinion, what matters more than the quantum vs thermal origin of the noise is how it is extracted and converted to bits, and the robustness of that with respect to failure modes and external influence.

This is one area where CSPRNG post-processing helps: in a cryptographic context, it insures that an attacker must have near perfect control of the TRNG source to gain an advantage. As soon as about 160 bits (give or take a factor of two) of actual entropy has been fed into the CSPRNG (without the output being observable by the adversary meanwhile, as rightly pointed by @CodesInChaos), and baring any attack on its design or implementation, the output is indistinguishable from random for any practical purpose (that's even though any CSPRNG using finite memory and no more seeding has a finite period; we are considering computationally bounded adversaries).

The output of any TRNG can't be better than that! On the contrary, in my experience, the unconditioned output of a TRNG source is never free from some detectable bias. If a stream of bits of arbitrary length has odds of 0 vs 1 passing a basic chi-squared test (and especially when that stands taking the effect of temperature and device variation into consideration), this is strong indication that it is not the output of an unconditioned TRNG. And again, any post-processing of the TRNG source must be known and taken into account (in addition to the nature of the source) when assessing the TRNG, and especially the effectiveness of its monitoring.

share|improve this answer
    
I have seen that some TRNGs claim to use quantum effects to generate randomness. This seem the best ... Why does the output needs to be post-processed by a CSPRNG? Isn't the raw output better than the output of a prng? After debiasing it should be more random... –  user1028028 May 23 '13 at 23:45
    
I don't really agree with your last statement. Any PRNG whether cryptographically secure or not works by taking an input (seed) and generating a bit stream from that seed in a strictly deterministic way. That bit stream is guaranteed to be periodic, whether the period is high (crypto secure) or not is irrelevant. A random walk generated form a PSEUDO (means false) random sequence will always repeat itself with a certain period. A TRUE random generator should never fall in this type of repetitive pattern ever. So if you just feed 160 entropy bits, that just gives 2^160 patterns... –  user1028028 May 24 '13 at 12:03
3  
@user1028028: actually, it's not true that a determanistic PRNG must be periodic; it's easy to make a nonperiodic PRNG by expanding the state over time (and besides, we don't care about repeats after (say) 2^256 outputs; we never come even close to that; and we usually reseed the PRNG periodically anyways). In any case, fgrieu answered why postprocessing the TRNG output through a PRNG is useful, in his experience (and mine, however my experience is more modest), "the unconditioned output of a TRNG source is never free from some detectable bias". Is that contrary to your experience? –  poncho May 24 '13 at 18:25
2  
@user1028028 Why does it matter if a PRNG is periodic? The universe will be barren and cold long before any computer finishes a whole period. –  CodesInChaos May 25 '13 at 7:36
3  
There is one important pitfall about "injecting 160 bits is enough". You need to inject them all at once, without the attacker being able to observe the output of the PRNG in between. –  CodesInChaos May 25 '13 at 7:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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