| |
 has
a simple circuit consisting of an 8-bit microcontroller and a resistor.
The features of the PIC microcontroller are essential to the ORB. More
information, including a datasheet, is available for the PIC12C67X
Family. ORB is defined by the circuit above and the GPL licensed
software programmed in its one-time programmable memory. In the description
that follows, necessary simplifications may lead to differences between
the described and the actual operation of the ORB. In that case, the behavior
defined by the circuit and the software prevail.
Right-click here and choose "Save as..." to download the
ORB Release 1 Software
Or just browse the source code here.
Interface
The interface is designed for simple connection to a variety of host systems.
ORB signals that a random bit is available by raising the BAvail line.
The host system requests the bit by raising the BReq line. ORB responds
by putting the output on the Bit line and dropping the BAvail line. The
Bit line returns to low when the host drops the BReq line. The process
then repeats. This scheme does not depend on any host timing, and does
not require tri-state lines. For security in multitasking systems, the
random bit is not present on the Bit line until it is requested, and it
is cleared as soon as the host acknowledges reading it. A timing diagram
shows this sequence graphically:
The time t1 is required for the chip to initialize and generate
internal entropy. The ORB then awaits a bit request, and enters a standby
state to conserve power. After the bit is requested, t2 elapses
before the bit is presented. The ORB then awaits the signal that the bit
has been read, an will not enter the standby state. Time
t3 is required for the next bit to become available. Internally
the ORB generates random bits in rounds with 64 bits output per
round. After each 64 bits are read, a long t3 period is required
for the next block to be generated. The ORB uses an internal RC clock that
is subject to process variation and temperature/voltage dependence. The
typical times and their expected range is shown in this table.
| Parameter |
Condition |
Typ |
Min |
Max |
| t1 |
|
2.23 s |
2.09 s |
2.54 s |
| t2 |
|
26.5 ms |
23.0 ms |
32.5 ms |
| t3,1 |
Bits 0-62 |
15.5 ms |
12.4 ms |
17.2 ms |
| t3,2 |
Bit 63 |
53.8 ms |
51.5 ms |
60.3 ms |
The theoretical ORB bit-rate for a fast host system can be calculated
from r = 64 / (64 t2 + 63 t3,1 + t3,2).
This yields r = 1133 bits/sec in the typical case, without any host delays.
Tested through the ISA bus on a 100 MHz Pentium PC, a bit-rate of 1050
bits/sec was typical.
Two quirks in the ORB's behavior should be considered when designing
an interface with the ORB. First, during the time that the ORB waits for
BReq to be raised, it will enter a standby mode after about 1.5 ms.
If Breq is raised by the host at the exact moment that ORB enters standby,
ORB will fail to respond. The host should then toggle BReq low and high
again to wake the ORB. Second, a single instruction drops the BAvail line
and puts the bit on the Bit line. Depending on lead lengths and capacitances,
the logic state of the Bit line may not have changed when the falling edge
of BAvail is detected. It is prudent to wait a short time before reading
the Bit line.
See the Application Examples for more interface
information.
Entropy Generation
ORB generates entropy by repeatedly charging or discharging the sample-and-hold
capacitor in the PIC microcontroller through the external resistor according
to the contents of a bitstream. The voltage on the capacitor is then measured
using the PIC's internal 8-bit A/D convertor. A simplified circuit shows
the relevant components:
During each round (64 bits output) of the ORB's operation, the circuit
is stimulated 261 times. For each stimulus, the sampling switch is closed,
then one of the MOSFETs (P or N) is closed for about 1 ms
depending on the corresponding bit in the bitstream. The sampling switch
is then re-opened, and the A/D process begins. Only the least significant
bit (LSB) of the A/D result is used.
During each round, 261 bits are processed through the circuit. The 261
bits used to determine the stimulus defy description in plain english,
and the following notation will be used:
Bits ri, i = 1...256 are the residual data from
the MD2 hash function
Bits ui, i = 1...128 are the unique ID number of the chip
Bits si, i = 1...261 are the stimulus bitstream
Bits di, i = 1...261 are the resulting LSBs from the A/D
Bits ei, i = 1...248 are the entropy pool
Symbol Å denotes the XOR function
The stimulus bitstream is obtained as follows:
s1 = 1, s2 = 0, s3 = 1, s4
= 0, s5 = 1
si = ri-5 Å di-1,
i = 6...261
The first five stimulus bits have the effect of centering the capacitor
voltage, with a slight charging bias. The remaining bits are "white" or
uncorrelated.
The last 248 A/D result LSBs are XOR'ed into the entropy pool:
ei = ei Å di+13,
i = 1...248
Absent any noise, and with perfect theoretical components, the voltage
on the capacitor would change as follows in response to a stimulus.
The centering effect of the 10101 stimulus sequence is shown as illustration.
The distribution of voltages on the capacitor in response to a random
stimulus stream has not been analytically determined, but a simulation
gives the following distributions for three resistor values. This motivates
the choice of the 100K value, because it "explores" a wide range of charge
states but does not spend much time at the extremes, where entropy generation
would be reduced.
For a real ORB (modified to output A/D results) with noise, the following
state change diagram was measured. In character it is similar to the theoretical
diagram above, but the lines are now collections or points, with two or
three subsequent states resulting from the same prior state and stimulus.
It also appears that the capacitor cannot be fully charged enough to produce
the highest A/D results. This may be a function of the charging circuit
or the A/D circuit.
The distribution of states, as measured from a real ORB is also similar
to the theoretical result above. The distribution of states is not however
continuous. This is not fully explained yet, but may result from A/D convertor
steps of differing width.
The essential fact is that for a given bitstream and initial capacitor
charge, the process will result in different sequences of LSBs when it
is run repeatedly. Measurement of the quantity of entropy created during
each run is difficult, but a conservative estimate is that it is about
30 bits. There are multiple sources for this entropy. Johnson noise in
the resistor, shot noise in the semiconductor components, and temperature
variations in the component values contribute. Oscillator jitter varies
the time during which the capacitor is charged or discharged. Power supply
noise varies the charging rate and the A/D transition points. External
electromagnetic interference also contributes. This, combined with the
unique ID (presumably unknown) and process variations in components, make
the process very difficult to model with accuracy sufficient to predict
its output.
Data Flow
The entropy generation process described above is actually the last thing
that happens in a round. It is described first because it is the most important.
Some additional bit quantities are defined here:
Bits hi, i = 1...128 are the MD2 hash result
Bits ci, i = 1...32 are a rounds counter
Bits ti, i = 1...8 are the PIC's internal TMR0 timer
Note that the TMR0 timer increments on every instruction executed by the
PIC, about every 1 ms, except when
the chip is in standby mode. During each round the following steps occur:
1) The entropy pool is hashed using MD2 producing both the hash h
and the residual data r. The MD2 hash was chosen because it is simple
and compact enough to be implemented on the PIC12C67X, and despite considerable
effort since 1992, it has not been "broken." It also has the nice property
of producing the residual data (normally discarded) which is nominally
white. Symbolically:
[h,r] = MD2(e)
2) The unique ID and its complement are XOR'ed into the residual data.
This step is one last hurdle to modeling the ORB's process if the unique
ID is unknown. Symbolically:
ri = ri Å ui,
i = 1...128
ri = ri Å (~ui-128),
i = 129...256
3) The rounds counter c is incremented. This counter functions
to reduce the likelihood of cycles in the process. In continuous use at
1000 bits/sec output. The rounds counter will overflow every 8.7 years.
Symbolically:
c = c + 1 mod 232
4) The hash is XOR'ed into the entropy pool. This feedback process forms
a basic pseudo random number generator (PRNG) which is modified by the
other processes to introduce non-determinism and reduce the likelihood
of cycles. Symbolically:
ei = ei Å hi,
i = 1...128
5) The timer is XOR'ed 7 times into the entropy pool. This reduces the
likelihood of cycles and introduces a little additional entropy due to
the timing variability of the host I/O process. Symbolically:
e128+i+8j = e128+i+8j Å
ti,
i = 1...8, j = 0...6
6) The rounds counter is XOR'ed twice into the entropy pool. This further
reduces the likelihood of cycles. Symbolically:
e184+i+32j = e184+i+32j Å
ci,
i = 1...32, j = 0...1
7) The entropy generation process, as described above, is executed.
When the chip is first powered up, the entropy pool is initialized to
the unique ID and the first 120 bits of its complement. The rounds counter
is initialized to zero. Steps 1) through 7) above are then repeated 40
times to accumulate entropy. After that the first 64 bits of the hash result
are sent to the host before each round.
Design Objectives
ORB is designed to produce bits that are indistinguishable from a "true"
statistically perfect random bit generator. Proving otherwise would require
a computable test, that operates on a reasonable length sequence of random
bits, and produces an ORB/random decision correctly with probability >
50%. No such test has been found.
ORB is not designed to be physically secure. For example, most of the
entropy generation can be thwarted by grounding Pin 7. A user
requiring physical security would need to take additional appropriate measures.
Through Release 0 (licensed chips) and Release 1 (Open Source) the design
has been thoroughly tested and appears to meet its objectives.
|
|