Send the link below via email or IMCopy
Present to your audienceStart 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?
You can change this under Settings & Account at any time.
Hardware Testing of RNG
Transcript of Hardware Testing of RNG
Test a Null Hypothesis: H0.
Fix sample length n.
Fix a significance level or critical value: alpha.
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
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).
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.
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).
Linear Feedback Shift Register (LFSR)
Wolfram's CA: Rule 30 Entropy Source (ES):
Thermal (Johnson-Nyquist) noise.
Schottky (shot) noise.
Quantum photon reflection.
Radioactive decay. Digital Post-Processing (DPP):
von Neumann corrector.
Secure Hash Alg. (SHA). ES & DPP METRICS Shannon Entropy
Information RNG TRADEOFFS Area.
Throughput. + Chaotic
Bull Mountain Chi-Square based (Code G):
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.
Integrable in any RNG.
Online testing capability.
Reducing Test time.
Monitoring/validation: temp, voltage, wear-out. Low-Cost:
Ultra-low power VLSI chip.
Scalable: n, alpha.
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.
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.
Secrecy . MIT 1977 by (R)ivest (S)hamir (A)ldeman.
Public Key for Encryption.
Private Key for Decryption.
Two primes factorization problem.
Algorithm to solve classically: O(exp). Online purchase.
Home banking transactions. Fraud.
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:
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.
Cycle time: 5 ns (2 GHz).
Area: 1926 um.
Active power: 3.75 mW
Leakage power: 10.5 uW FUTURE WORKS Explore additional tests:
dieharder Second level testing:
Repeat the same test using different inputs.
Second level P-val (distribution of P-vals).