## FiReBuG ODE Simulation## TheoryTwo distinct parts of the FiReBuG cycle are modeled: measure and charge (store). The parts of the cycle are shown in this portion of the FiReBuG flowchart. During the measure part of the cycle both capacitor voltages are relaxed toward their natural level by leakage while the measuring circuitry stabilizes. During the charge part of the cycle one capacitor (the measured one) continues to have its voltage relaxed by leakage, while the other is charged toward one of two potentials, based on the measurement and the simulated logic.This circuit is used to model leakage of both
capacitors during the measure part of the cycle, and one capacitor
during the charge part of the cycle. The resistors relax the
capacitor's potential toward a central value near half of the supply
potential. It remains to be determined if this is the natural behavior
of a CMOS capacitor, or if resistors must be added to approximate this
cenering behavior. The charge centering is one of the mechanisms that
prevent the FiReBuG system from entering a lock-up state where it would
produce a constant stream of 0's or 1's. Nominal values for R The circuit's ODE can be written
by inspection: V This circuit is used to model the capacitor
that is being charged. The leakage resistors are still present and the
charging potential V ## SimulationThe FiReBuG system as modeled by the ODE solution and appropriate timing and logic are simulated with the C language program ode_sim.c. The parameters used with this version of the simulation are
These parameters can be easily changed in the program to explore different circuit realizations. The program has settable options to produce either voltage traces through the cycles, voltages at the end of each Charge, or just the random bits that are produced by the generator. All will be explored here. ## ResultsThe capacitor voltages traces were recorded during simulation of 12 cycles of the FiReBuG system and the results are plotted here.When the capacitor voltage at the
end of a Charge is plotted versus with the subsequent value for the
other capacitor over a simulation of 2 The same 2 Here are some images of random bits with 1's represented by white pixels and 0's as black pixels. An equivalent image produced with output of a Blum-Blum-Shub (BBS) Pseudo Random Number Generator (PRNG) is given for comparison. A BBS PRNG is provably pseudo-random in an information theoretic sense.
Another way to experience random bits is to listen to sounds produced when the bits are treated as samples and converted to audio signals. These files produce stereo sound with 44,100 16-bit samples per second.
Numerous statistical tests are
available for testing Random Bit Generators. The raw FiReBuG output can
be expected to fail many of these due to the capacitor leakage and
other lock-up prevention mechanisms. Leakage particularly has the
effect of preventing long runs of 0's (gaps) and 1's (blocks) and this
is very clear in a Runs Test (Handbook of Applied
Cryptography, 1996). Here are the results of a runs test on 2 File: ode_sim_bits.bin, 4194304
bytes
There are less long runs that expected and consequently more short runs of both 0's and 1's. This results in less that full entropy in the raw bitstream. An estimate of 7.78 bits of entropy per byte of data was obtained using the public domain ENT program. A body of theory and practice is
available for condensing less-than-full-entropy streams into
full-entropy streams. A common example is the /dev/random mechanism in
Linux which uses an entropy pool into which data is stirred, and out of
which full-entropy random bits are extracted by way of a cryptographic
hash function. Such a method could be used in conjunction with FiReBuG
if a statistically perfect bitstream is desired. Copyright (C) 2001 APA Consulting, a sole proprietorship of A. Peter Allan. All Rights Reserved. Confidential. |