Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present 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.

DeleteCancel

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.

No, thanks

Hardware Testing of RNG

EE Master Thesis discussion
by

Daniele Antonioli

on 24 July 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Hardware Testing of RNG

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).
Full transcript