Hardware Testing of RNG

Hardware Testing of

RNG

• Bottlenecks: erfc(x), gammainc(x,b,’upper’).
• Fix n and alpha.
• Compute the f(x) inverse:
• Shift pass/fail bit dependence from P-val to x:
• Avoid complex computation.
• Maintain test convergence.
• CDF and its inverse are monotonic functions.
• Change alpha:
• Only x changes.

Keywords

• Fully hardware:
• Counters, comparators, registers.
• Selection based on min sample, computation complexity and statistical convergence.
• Reduction of 6 out of 15 NIST SP800-22 tests.

• On-chip:
• Integrable in any RNG.
• Online testing capability.
• Reducing Test time.
• Attack detection.
• Monitoring/validation: temp, voltage, wear-out.

RSA Cryptosystem

• Low-Cost:
• Ultra-low power VLSI chip.
• Battery-powered device.
• Gating capability.

• (Re)configurable:
• Multi-DPP.
• Scalable: n, alpha.

• Parallel computing:
• Parallel-Testing.
• Throughput.
• Low additional storage.

On-chip reduced NIST test module

arginv.m

Security Engineering

Code Simulation

Online purchase.

Home banking transactions.

MIT 1977 by (R)ivest (S)hamir (A)ldeman.

Asymmetric scheme:

Public Key for Encryption.

Private Key for Decryption.

Two primes factorization problem.

Algorithm to solve classically: O(exp).

back_envelope.m

Hack

RUNS TEST

• Privacy.
• Data Integrity.
• Secrecy .

Keys

Randomness

LONGEST RUN OF 1s TEST

The Six Candidates

NON OVERLAPPING TEMPLATE TEST

BINARY MATRIX RANK TEST

• Fraud.
• ID Theft.
• Economic Fail.

• easy to fabricate
• easy to use
• how to test it ?

FTwB

FREQUENCY TEST WITHIN A BLOCK

BERNOULLI SP:

unbiased.

independent.

uniformly distributed in [0 1].

p=0.5 .

FREQUENCY MONOBIT TEST

http://www.random.org/coins/

Choose and flip a coin n times like these.

Synthesis

• Design: Verilog
• Synopsys Design Complier.45 nm SOI NCSU/OSU open-source std cell lib.Verification: ModelSim.
• n=128:
• Cycle time: 5 ns (2 GHz).
• Area: 1926 um.
• Active power: 3.75 mW
• Leakage power: 10.5 uW

• Explore additional tests:
• Cusum
• DIEHARD
• dieharder

FUTURE WORKS

• Second level testing:
• Repeat the same test using different inputs.
• Second level P-val (distribution of P-vals).

Thank you

Prof. Riccardo Rovatti

Prof. Wayne Burleson

Ing. Vikram Suresh

http://dilbert.com/strips/comic/2001-10-25/

• State of the art fifteen RNG STs battery (multiple authors):
• Used by FIPS to choose AES alg.
• TRNG and PRNG testing.
• Open-Source ANSI C framework.
• Each ST focus on a precise aspect of randomness:
• Examine distribution of 0s and 1s in some fashion.
• Study the harmonics using spectral methods (FFT).
• Detect patterns.
• NHs class statement: "under assumption of randomness".
• Complexity of the test increase with the min n required.
• Multiple P-Val capable.
• Alpha = 0.01 by default.

RNG TRADEOFFS

SP800-22

• Inputs:
• Test a Null Hypothesis: H0.
• Fix sample length n.
• Fix a significance level or critical value: alpha.

• Outputs:
• Compute the output: P-val.
• Compare alpha vs P-val.
• Reject or Accept H0 with a confidence of 1 – alpha.

• Area.
• Power.
• Throughput.

CLASSICAL:

+

SECURITY

Shannon Entropy

• Randomness
• Lossless compression
• Redundancy
• Information

METRICS

Intel

Bull Mountain

Hamming distance.

Metastable

Ring

Oscillator

STATISTICAL TEST (ST)

Chaotic

ADC

• Erfc based (Code E):
• de Moivre-Laplace Thm. (special case CLT).
• Bernoulli SP can be aprox with a Gaussian RV,
• P-val computed using: erfc(x).

COMPLEXITY

SHA-1

• True or Physical RNG.
• Exploits Non-Deterministic event.
• Return Aperiodic Sequences (non-reversible).
• Seed for any PRNG.
• Best feasible aprox of ideal RNG.
• E.g.
• Analog: Chaotic ADC.
• Digital: Meta-stable ring oscillators.
• Intel Ivy Bridge a.k.a Bull Mountain.

XOR filter

von Neumann corrector

Digital Post-Processing (DPP):

• von Neumann corrector.
• XOR filter.
• Secure Hash Alg. (SHA).

TRNG

• Chi-Square based (Code G):
• Chi-Squared test.
• Goodness of fit.
• P-val computed using: gammainc(a,z,'upper').

• Each ST, to make sense, starts from some assumptions that introduces unavoidable errors:
• Type I error: FALSE POSITIVE-alpha.
• Type II error: FALSE NEGATIVE-beta
• min(beta)=min(alpha,n).
• Randomness is a relative subject:
• NH dictates the meaning of the P-val.
• Interpret P-vals.

SP800-22

Entropy Source (ES):

• Thermal (Johnson-Nyquist) noise.
• Schottky (shot) noise.
• Brownian motion.
• Quantum photon reflection.
• Radioactive decay.

ES & DPP

Statistical Testing (ST)

STATISTICAL TEST (ST)

RNG

• Pseudo RNG.
• Exploits deterministic event or finite memory algorithm.
• Return Periodic Sequences (reversible).
• Hashing capability.
• E.g.
• Linear Feedback Shift Register (LFSR)
• Wolfram's CA: Rule 30

PRNG