Security Engineering Keys RNG TRNG On-chip reduced NIST test module Keywords Statistical Testing (ST) 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. STATISTICAL TEST (ST) 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. 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. 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). http://dilbert.com/strips/comic/2001-10-25/ STATISTICAL TEST (ST) SP800-22 SP800-22 PRNG Hardware Testing of

RNG 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. 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 Entropy Source (ES):

Thermal (Johnson-Nyquist) noise.

Schottky (shot) noise.

Brownian motion.

Quantum photon reflection.

Radioactive decay. Digital Post-Processing (DPP):

von Neumann corrector.

XOR filter.

Secure Hash Alg. (SHA). ES & DPP METRICS Shannon Entropy

Randomness

Lossless compression

Redundancy

Information RNG TRADEOFFS Area.

Power.

Throughput. + Chaotic

ADC Metastable

Ring

Oscillator Intel

Bull Mountain Chi-Square based (Code G):

Chi-Squared test.

Goodness of fit.

P-val computed using: gammainc(a,z,'upper'). Hack Code Simulation Synthesis 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. 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. 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. The Six Candidates RUNS TEST FREQUENCY MONOBIT TEST LONGEST RUN OF 1s TEST FREQUENCY TEST WITHIN A BLOCK NON OVERLAPPING TEMPLATE TEST BINARY MATRIX RANK TEST Randomness RSA Cryptosystem Privacy.

Data Integrity.

Secrecy . 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). Online purchase.

Home banking transactions. Fraud.

ID Theft.

Economic Fail. easy to fabricate

easy to use

how to test it ? http://www.random.org/coins/

Choose and flip a coin n times like these. BERNOULLI SP:

unbiased.

independent.

uniformly distributed in [0 1].

p=0.5 . von Neumann corrector XOR filter SHA-1 COMPLEXITY Hamming distance. SECURITY CLASSICAL: Thank you Prof. Riccardo Rovatti Prof. Wayne Burleson

Ing. Vikram Suresh FTwB back_envelope.m arginv.m 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 FUTURE WORKS Explore additional tests:

Cusum

DIEHARD

dieharder Second level testing:

Repeat the same test using different inputs.

Second level P-val (distribution of P-vals).

### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start remote presentation- Invited audience members
**will follow you**as you navigate and present - People invited to a presentation
**do not need a Prezi account** - This link expires
**10 minutes**after you close the presentation - A maximum of
**30 users**can follow your presentation - Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

### Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.

You can change this under Settings & Account at any time.

# Hardware Testing of RNG

EE Master Thesis discussion

by

Tweet