ICMC18: SP800-90B Testing Process, Result Bounds and Current Issues

SP800-90B: Testing Process, Result Bounds, and Current Issues (G11c) Joshua Hill, Information Security Scientist, UL, United States

We started out with just hand waving  for evaluating entropy - now, after several iterations, we have NISTs SP800-90B final - YAY! But, I had to submit 20 pages of comments.

Major comments: High-entropy noise sources fail the Restart Sanity Check much more than expected. Entropy and noise sources are required to have the same entropy rate across all process characteristic's and all environmental conditions and required to be stationary!
By more than expected... 60x more frequently than expected! There's a statistical test problem

No noise/entropy source behaves the same way across variations or temperature or voltage changes - nobody could comply!

We need to characterize what are the entropy-relevant parameters and asses appropriately.

We also have issues with noise source definition - output can be the XOR of the output of multiple copies of the same physical noise source. Think of deterministic ring oscillators - fixed period. ... get a nice flat, low entropy. Statistically looks good, but not in reality. (don't do that!)

We've constructed various simulated noise sources and models - the work is a larger scale version of DJ Johnston's 2017 work using NIST's reference python implementation. This testing occurred using only the full set of non-IID tests. First pass - looks much better!

Set up a bunch of other models, including one where you might have bad grounding, etc. (Narrow Gaussian noise source, 8-bit ADC, Sinusoidal Bias), and an idealized ring oscillator.

The models are somewhat complicated, and can return a range of entropy values for each parameter set. The lower end off the modeled range is the value that out to be used in our assessments.

It's vital to test only raw data, and to filter out extraneous signals. Don't perform statistical testing on conditional data!

ICMC15: SP800-90B: Analysis of Linux /dev/random

Stephan Mueller, Principal Consultant and Evaluator, atsec information security

Not only does Mr. Mueller work at atsec, but he also is a Linux kernel developer in his spare time. 

How do we define the noise sources for /dev/random:

• Disk I/O
• Block device number + 0x100 ||Jiffies || High-Resolution Timer
• Noise derived from access times to spinning platters

•  Human Interface Devices (HID)
•  Interrupts
• fast_pool: 4 32-bit words filled with 
• Jiffies 
• high resolution timer
• IRQ number
•  64 bit Instruction pointer of the CPU.

The output function is a SHA1 hash run over the output and put in the output pool.

How do we condition? The conditioner mixes data into input-pool, a non-approved mechanism according to SP800-90B. LFSR for 128 * 32-bit pool with full rank polynomial.  The goal is for bias reduction. The Disk/HID: bias added due to structure of data to be mixed into input_ool with MSB with rather static data (event numbers), middle bits with low entropy data (jiffies) and LSB with high-entropy data (high resolution timer.

There is a health test, but it is not compliant with SP800-90B.  they measure disk/HID and derivation of event time in jiffies. Minimum of all derivation is estimated entropy of event.  Limitation to 11 bits maximum per event. There is a claim that one bit of input data has less than one bit of entropy.  So, this covers continuous health test requirement and repetition count requirement (even though, again, it's not the test SP800-90B actually asks for).

All of these derivations are applied to all events, including startup - so, we kind of have a start up test.

Interrupts: implicit, without interrupt handling there is no live Linux kernel :-) 

There is no adaptive proportion test - entropy measurement considered equivalent.

The goal of identifying failures is met.

How to observe noise sources and LFSR/input_pool in a live Linux kernel, and unchanged Linux kernel and not ipact entropy calculation - answer: SystemTap! Though Heisenberg's uncertainty still applies, as it's changing timing by adding additional code paths. Akin to executing Linux on a slower system, therefor no impact on entropy estimates. [Note: I'm not sure I agree with that theory.]

Their test results:
General: Chi-Square for IID cannot be calculated and Chi-Square Goodness Fit cannot be calculated. For Disk/HID, only high-resolution timer tested due to main entropy source - other items were zero or close to zero entropy. But, when using lower 11 bits of timer, data is almost IID.  Looking at interrupts, each 32-bit word is tested individually. About half of IID test fail -> non-IID. 

General conditioner of IID: collision tests N/A due to no collisions, and all sanity checks always pass. 

Is the /dev/random on Linux good enough? Noise sources: using the min entorpy values for events and considering the maximum of 11 bits of entropy estimated per event, we pass SP800-90B. Additonal testing beyond SP800-90B shows that more than 6% of events are estimated to have 0 bits of entropy. About 20% of events are estimated to have 1 bit of entropy. Massive underestimation of entropy in noise sources.  For the conditioner: no change from noise sources. With entropy estimator enforced when obtaining random values - preventing random number output when there is too little noise. The passing of the noise source implies passing of the entire random number generator. Other pools feeding /dev/random and /dev/urandom are DRNGs!

Assumption of a certain structure of an entopy source. Straigh data path from noise source to output, and it's difficult to apply to noise sources maintaining an entropy pool

Post by Valerie Fenwick, syndicated from Security, Beer, Theater and Biking!

ICMC15: Improved Approaches to Online Health Testing in SP800-90 RNGs

David Johnston, Hardware Security Architect, Intel

There are two basic types of RNGs: big and fast, small and slow.

You need to do online testing to be sure things are actually random, like a statistical test for nondeterministic part. Also need a logic integrity test for the deterministic part : BIST, SCAN, KAT

You can only test for a broken state - strong bias or a strong serial correlation coefficient (SCC).

Min entropy tests are too slow and data hungry to do online. All patterns are equally likely (even all zeros).  But, some patterns are characteristic of a broken state: strong bias or a strong serial correlation coefficient (SCC).

A nice test or "broken - maybe" Note the binomial distribution of short and long patterns in a number of fully random bits. Set bounds for each, then measure each over sample and check they are wall within the bounds. If outside, tag as unhealthy.  The bounds determine the false positive rate.

The advantage - it's cheap. A shift register, 6 comparators and 6 counters.  Spots all repeating patterns up to 6 bits in length and detects bias and correlation. Highly bimodal with stationary data of some bias and auto correlation. Intel CPUs do this over 256 bit samples and aims for 1% false positive.

For an entropy source OHT, what's an error when all patterns are equally likely?

The lower false positive rate means you'll like have a high false negative rate.  how do you know if this is really broken or not?

There's a basic principal: never throw away entropy. - Margaret Salter. If you discard the unhealthy tagged samples, you reduce the entropy. If you accept unhealthy tagged samples, you risk false negatives.  Simple: extract with output = MAC (last_output || MAC(Xi || ... || Xi+r), where n is the number of samples and  is the number of samples that contain the necessary number of healthy tagged samples. Also, mixed in are the unhealthy samples that aren't counted.  Suspicous of MACing over variable field length? See his references (#7).

Over many samples, remember just the 1 bit tag per samples, allos a test over lots of data without huge amounts of memory.  Count the N Healthy:Unhealthy ratio in the last M samples.  Intel CPUS have M=256 -> so the history statistic is over 64Kibit of data..

If it drops below the threshold of goodness, detect and offline.  Ideally, it never happens.

What makes pool feedback good? E.G. Intel's CPUs demand 768 bits of healthy entropy, MACed to 256 its of full entropy, but all intervening unhealthy samples are mixed in, so no entropy is thrown away and occasional false positives don't raise error response.

What's wrong with SP800-90C?

The ENRBG output offers a superset of the DRBG's cryptographic properties. Full entropy vs prediction computational complexity respectively So, a general purpose RNG needs both: DRBG for performance and ENRGBG for arbitrary strength keys and seeding..

The oversampling construction kills performance of DRBG output by forcing intervening reseeds. Unless you put in two DRBGs, doubling the area, doubling the failure rate...

You can add a BIW extractor, and a DRBG for XOR construction.

We wnat better reliability and performance without DRBG. A modern ful entropy ES+Extracot has higher bits/clock/um^2 than an AES-CTR-DRBG.  Best case of 128/10 clocks/31K gate equivalents = 4.13E-4bits per clock per gate (asymptotic as the gen:update ration -> 1.0).

And then we have FIPS 140-2, which has required tests that go beyond SP 800-90A. If you follow 4.9.2, which includes a data modifying test and throwing away data. This yields a radom stream trivially distinguishable from random. No 16 bit equal pairs in 1MByte data = Definitely not random, 16 are expected. It creates algebraic invariates Xi != Xi+1 for all output values, reducing entropy and helping algebraic attacks.

Intel refused to put this in its silicon because it may be a back door. The risk to Intel of having a back door is greater than the cost of not being FIPS compliant.

ISO 19790-2012 removed this test - so, let's hurry up with FIPSf 140-3.

But, still source constrained devices can't have hardware FIPS compliant RNGs because of the DRBG requirement.

Pool structures that use health tagging allow appropriate adaptive responses to entropy source failure and degrdation behaviour and instantaneous response to instantaneous ES failure.

The DRBG requirements of SP800-90C lead to a reduction in reliability and/or efficiency of RNGs and prevent SP800-90 compliant full entropy hardwar RNGs in resource constrained situations. FIPS 140-2 makes this worse.

Johnston has seen systems getting when to block flipped - that is , blocking when they have high entropy and not blocking when their entropy is low.  This is not a good plan, and has led to published papers.

The kernel's job is to do the mixing. While he knows that Intel's entropy source doesn't have a back door, but not everyone else knows that - or know that about their other sources - so, mixing is good.
Post by Valerie Fenwick, syndicated from Security, Beer, Theater and Biking!

ICMC: Entropy Sources - Recommendations fo a Scalable, Repeatable and Comprehensive Evaluation Process

Sonu Shankar, Software Engineer, Cisco Systems
Alicia Squires, Manager, Global Certifications Team, Cisco
Ashit Vora, Lab Director and Co-Fonder, Acumen Security


When you're evaluating entropy your process has to be scalable, repeatable and comprehensive... well, comprehensive in a way that doesn't outweigh the assurance level you're going for. Ideally, the method used for the evaluation would be valid for FIPS-140 and Common Criteria.

Could we have the concept of a "module" certificate for entropy sources?

Let's think about the process for how we'd get here. we'd have to look at the Entropy Source: covering min-entropy estimation, review of built-in health tests, built-in oversampling, and a high-level design review.

There are several schemes that cover entropy and how to test it. You need to have a well documented description of the entropy source design, and leverage tools for providing statistical analysis of raw entropy.  It would be good to add statistical testing and heuristic analysis - but will vendors have the expertise to do this correctly?

How do you test for this?  First, you have to collect from raw entropy - disabling all of the conditioners (no hashing, LFSR, etc) - not always possible, as many chips also do the conditioning, so you cannot get the raw entropy. If you can't get the raw entropy, then it's not worth testing - as long as you've got good conditioning, it will  look like good entropy.

In order to run this test, you need to have at least one file of entropy contiaing 1 million symbols and the file has to be in binary format.

When it comes time to look at the results, the main metric is min-entropy.

You need to be careful, though, to not over sample from your entropy source and drain it. You need to be aware of how much entropy it can provide and use it appropriately. [* Not sure if I caught this correctly, as what I heard and saw didn't quite sync, and the slide moved away too quickly]

When it comes to reviewing noise source health test - need to catch catastrophic errors and reductions in entropy quality This is your first line of defense against side channel attacks. This may be implemented in software pre-DRBG or built-in to source.

Ideally, these entropy generators could have their own certificate, so that 3rd parties could use someone else's hardware for an entropy source - w/out having to worry difficult vendor NDA issues.

ICMC: Entopy: A FIPS and Common Criteria Perspective Including SP 800-90B (G22A)

Gary Granger, AT&E Technical Director, Leidos

Random values are required for applications using cryptography (such as for crypto keys, nonces, etc)

There are two basic strategies for generating random bits - non deterministic random bit generator (NDRBG) and deterministic random bit generator (DRBG) .  Both strategies depend on unpredictability.

Entropy source is covered in NIST SP 800-90B (design and testing requirements).  Entropy source model: Noise source, conditioning component, and health tests.

How do we measure entropy? A noise source sample represents a discrete random variable. There are several measures of entropy based on a random variable's probability distribution line Shannon Entropy or Min-Entropy.  NIST SP 800-90B specifies requirements using min-entropy (conservative estimate that facilitates entropy estimation).
 
FIPS has additional implications for RNG in their implementation guidance, specifically IG 7.11. It defines non-deterministic random number generators (NDRNG), identifies FIPS 140 requirements for tests, etc.

IG 7.13 covers cryptographic key strength modified by an entropy estimate  For example, the entropy has to have at least 112 bits of security strength or the associated algorithm and key shall not be used in the approved mode of operation.

But the basic problem - entropy standards and test methods do not yet exist. How can a vendor determine and document estimate of their entropy? How do we back up our claims?

There are also different concerns to consider if you are using an internal (to your boundary) source of entropy or an external (to your boundary) source for entropy.

ICMC: Random Thoughts - Is True Randomness an Illusion?

Helmut Kurth, Chief Scientist, atsec information security

Illusions can be fun ... if we know they are an illusion.  They can make us feel good... even if they are bad.  They can make us think something is okay... when it's really broken.

There are some illusions we like in technology, like virtualization! The illusion is that we have more resources than we really have.  We can save money - that's good, right?  Some people think that virtualization provides more security - but does it really?  Vendors claim their virtualized systems are just like a real hardware box... but are they? Often not exactly. Something has to give, we should understand this.

How is entropy impacted once you virtualized the system?  Virtualizaion can change the timing, it may just behave differently. Either way, are we getting the same entropy on these systems?

Often, we make incorrect assumptions about things like timing and the similarity of a virtualized system to its true hardware counterpart.

For example, if you're using time as your entropy source - you may assume the lowest order bits are changing most frequently and will provide more actual entropy. But, what if this is not the true timer? What if a hypervisor is intercepting and interpreting the concept of "time" - what if the hypervisor should not be trusted?

Shouldn't you be able to trust your hypervisor?  Once someone has breached the hypervisor, they can do all kinds of evil things underneath your VM and you won't be able to easily detect it (as your OS will be unchanged).

For example, the RDRAND instruction can be intercepted by a hypervisor. This is a "feature" documented by Intel.  So, as a user of the VM, you think you're getting some pretty good entropy from RDRAND - but you're really getting poor entropy from your hypervisor. How could you detect this?   Intel's RDRAND is often used as the sole source of randomness with no DRNG postprocessing (like in OpenSSL), regardless if the "randomness" is being used for generating nonces or for generating cryptographic key material.

Assuming a compromised hypervisor, the bad guy can have the key used to generate the "random" sequences used in the RDRAND emulation.  He can use this to generate the different random streams.  He is able to get the nonce, which is transmitted in the clear.

Launching the attack requires installation of a hypervisor or the modification of a running hypervisor. Just one flaw that allows the execution of privileged code is all it takes.  The hacker, this this case, may have the session key even before the communicating parties have it! At this point, it doesn't matter what algorithm you're using - communications are essentially in the clear.

This attack is not that easy - it requires taking over the hypervisor (not easy), and once you have the hypervisor, you can do anything you want!  But, this isn't about taking down the machine, this is about eavesdropping undetected for any length of time.

This is a sneaky attack - virus scanner and host-based IDS will tell you everything is okey dokey!  It is independent of the OS or ay applications (as many rely on RDRAND) .

How can you protect yourself?  The basic solution is diversification - do not use a single source of entropy.  Use a different RNG for nonce generation and generation of key material, and use RDRAND for seeding (with other sources) rather than directly for generating critical security parameters.  Read the hardware documentation carefully - make sure you understand what you're getting.

Intel isn't going to fix this, as this isn't a bug... it's a feature!

Entropy analysis isn't just about the mathematical entropy analysis - be aware of how you procure the numbers and how they are used in your system.

...

As a side note, we (in Solaris land) are aware that this is a tough problem and hard to get right and we've already implemented counter measures. Darren Moffat did a great write up on Solaris randomness and how we use it in the Solaris Cryptographic Framework, describing the counter measures we already have in place.