[ILUG] serious Debian/Ubuntu security hole found

[Michael Watterson]

Timothy Murphy wrote:
> On Saturday 17 May 2008 12:13:07 pm paul at clubi.ie wrote:
>
>   
>>> Are you an expert on Zener diodes, or are you taking the word
>>> of someone who is?
>>>       
>> And are you? Also, mathematics is a wide field - are you an expert on
>> random numbers and PRNGs? ;)
>>     
>
> I'm certainly not an expert on Zener diodes,
> in fact my knowledge on the subject is 0, to a first approximation.
>
> I am reasonably knowledgeable about random numbers
> (having given a course on Algorithmic Information Theory).
> In particular, I know what "random" means (in the sense of Kolmogorov).
> which I suspect no-one else here does.
> (But I'd be pleased to find I'm wrong in this belief.)
>
>   
>> At the end of the day, engineers have to use their reasoning and
>> experience to figure out how to best apply the results from the
>> physical, mathematical and computational sciences - and not always
>> with ful understanding of the theory that lead to those results. My
>> understanding is that best practice at the moment is to try mix*
>> empirical entropy together with a cryptographic PRNG**, to try get
>> the best of both worlds - so knowledge of both inputs is required to
>> know the output**.
>>     
>
> Sorry to be mean, but I wish you wouldn't use the word "entropy" in this way.
> I can well believe that it is used by computer scientists in this area,
> but to me its use is slightly off-putting,
> as the word has a perfectly precise mathematical meaning
> (as developed by Clausius, Boltzmann, Shannon and Komogorov/Chaitin)
> and it is not clear to me how it is being applied here.
>
>   
>> I'm curious why people here should favour your arguments and ignore
>> best-practice in computer engineering. If your arguments should be so
>> convincing then surely we should we be reading of them in a paper in
>> a peer-reviewed journal? :)
>>     
>
> I think the views I've expressed are more or less standard
> among mathematicians and mathematical physicists.
> Eg Monte Carlo methods (which depend on random input) are very widely used
> and I never heard of anyone using a physical device of your kind
> to get random numbers for this.
>
> As to experts expressing this view,
> I mentioned that David Epstein made a remark along the same lines
> (that there is no practical method at present of using quantum effects
> to produce random numbers) in a recent talk I heard,
> and I am sure it would appear in his written work.
> He would be one of the leading mathematical experts in this area.
> (He is currently working on Monte Carlo methods in medical imaging.)
>
> Equally, if you look at any work in Lattice QCD
> (a subject that has attracted an absurdly large amount of money)
> I think you will find that the use of mathematical random number generators
> is simply the standard technique.
>
> But I don't like arguments by authority.
>
> Basically, I believe that pseudo random number generators
> are perfectly reliable for the purposes they are intended for.
> The fact that they are not truly random (in the sense of Kolmogorov)
> is completely irrelevant,
> and anyone trying to sell a black box on these grounds should be avoided.
>
> Actually, virtually any mathematical function, say f:N -> [1,m]
> (where N denotes the natural numbers),
> will be pseudo random, unless there is some simple reason
> why it is not.
> Eg take the digits in e or pi, or any irrational number like that.
> It is conceivable that there might be some pattern in these sequences,
> eg there might be more 0's than 1's in the digital expression for pi,
> but the chances of this are infinitesimally small, in my view.
>
>
>
>
>
>   
Using an irrational number is like using your girfriend's or pet's 
name.  Analysis would reveal which one it is. They are not much use in 
RNG / PRNG

Google HW RNG -linux -patch -kernel

The popularity of software (mathmatical) prng is twofold:
1) An interesting problem, to see how good you can get it, basically the 
vast literature is because in the past they are failures.
2) It costs nothing.

A HW RNG has several problems
1) It may not exist on an existing OS / Platform, hence you need prng 
techniques.
2) It costs money
3) It can fail. However if a prng "fails" in sense of a flaw realised, 
then it at that point has failed everywhere (Debian and SSL). If a HW 
RNG fails, it is a single instance that failed.

In studying Electronic Design and Computer Science/Programming and 
Mathematics for over 30 years, this thread is 1st time I've heard any 
suggestion that algorithmic (mathematical) PRNG is better and more 
reliable than a well designed HW RNG.

So for me this is an interesting thread, to hear a viewpoint expounded 
I've never heard before. I may learn something valuable.

The two oscillators approach to HW RNG is ideally suited to IC 
fabrication with no analogue circuits. Analogue IC design are awkward, 
expensive and understood  by fewer designers and  don't lend themselves 
to FPGA or CPU as easily.  A resistor is awkward because the noise is 
small and any amplication needed prior to ADC could be unreliable. Using 
a cheap One Eur  Microchip  Inc  PIC  ADC  &  I2C or USB to host  
interface, you would use two similar zener diodes, one for the Vref and 
the other the input signal. This means any periodic noise not fully 
filtered from the supply rail would cancel out. Or read two zeners via 
ADC and correlate to remove any periodic interference or supply rail 
noise. Unlike a resistor the noise level of a Zener is very high, thus 
in practice even a simple ADC and one zener is found to give very good 
results.

Noise Spectrum.
Devices may have a non-flat noise spectrum. (i.e pink or bluish noise 
rather than white). Checking on a 3.3V 400mW zener amplified by an MAR6+ 
IC, the spectrum appears to simply match the frequency response of the 
circuit and the MAR6 (6dB per octave slope at low frequencies due to 
coupling capacitors, but  DC coupling would be used on our hypothetical 
ADC). The high frequencies start dropping above 800MHz due to 
capacitance of diode, inductances and the 2GHz limit of the MAR6. (18GHz 
Spectrum Analyser used).

Any RNG algorithm can compensate for any known bias in the source 
numbers. The literature explains how this is done. Since the numbers are 
still random, although biased, this is not a problem.  Since we sample 
the source, any frequency distribution (spectrum) is affected since the 
sample frequency is a mixing component. The aliasing of sampling acts as 
downconverter, with  the higher frequency components overlaying our DC 
to 1/2 sample frequency.  Hence  since  these are also random,  there is 
no need  for a low  pass  filter  to avoid components above the nyquist 
frequency. If the  noise spectrum is M Mhz, and the sampling rate is S, 
we get 2 x M/S times the amount of noise there would be if we had a 
"brick wall" filter at the nyquist frequency.

For mathematical reasons, adding two white noise  components adds the 
average not the RMS value.

Lies for Children (this is simplified).
If you release H2S stink in a room, cochineal dye in water etc, it 
spreads and mixes exactly. But if you look closely you can't predict 
which molecule is O2, N2, C02, H2O or H2S. It won't even stay the same. 
It doesn't change at absolute zero and it changes faster at higher 
temperatures.

Noise in resistors or Zeners is electrons or "holes" jiggling with 
kinetic energy just like gas or liquids diffusing fast or slowly. The 
resistor has uniform construction so the electrical noise is very 
small.  
http://www.physics.ucdavis.edu/Classes/Physics122/Phys122_Johnson_Noise.pdf  
Modern metal film resistors are much quieter than old carbon composition 
resistors.

Zeners have Avalanche, Shot and Johnston Thermal noise (all random). 
http://www.ciphersbyritter.com/RES/NOISE.HTM



        Quote:


        Verification

A serious problem with many noise-based generators is that the analog 
noise is buried deep inside and cannot be seen or measured by the user. 
This is a problem because what we want from such a generator is a 
guarantee that the output depends upon unpredictable quantum events. If 
we were satisfied with random source that merely passed tests, we could 
easily use any one of the many deterministic statistical random number 
generators (RNG's) designed to pass such tests. What we want and expect 
is beyond what can be tested externally.

What is needed is the ability to turn off the quantum source, and see 
the output change. If we cannot do that, we cannot be sure that the 
particular device we have really does depend upon quantum information.

To verify correct operation of the noise source we might collect and 
verify either or both Gaussian amplitude and Poisson pulse-count 
distributions during normal operation. (This is in addition to some 
hardware check to verify that the detected noise is produced by the 
expected source.)



        AVALANCHE NOISE (largest component in a Zener)

"When a barrier region is subjected to reverse bias the electric field 
may reach the order of 10^5 V/cm or greater, and at these fields there 
occur phenomena which cause a rapid increase of current and eventual 
breakdown; it has furthermore been observed that the current is 'noisy' 
in this region, becoming increasingly impulsive as breakdown is 
approached."

"In silicon junctions McKay^14 observed that at the onset of breakdown 
there appears a distinctive form of impulsive noise consisting of a 
*random* sequence of rectangular current pulses of variable duration but 
constant amplitude." "It is possible that the inevitable inhomogeneity 
of the semiconductor in the neighbourhood of the junction gives rise to 
small regions (or 'weak spots') in which breakdown occurs for lower 
applied voltage than elsewhere and this localized breakdown will switch 
from an 'off' to an 'on' condition and back again, triggered by random 
fluctuation."


        SHOT NOISE

"The term 'shot noise' was originally applied to the fluctuations of 
current in a saturated vacuum diode due to the randomness of electron 
emission from the cathode." "At low frequencies such that the electron 
transit time /t/ is small compared with (1 / w), the /[ Fourier ]/ 
transform /F(f) ~ e/ and the spectral density assumes the simple form (2 
e I). The concept of *randomness* of rate of emission implies that the 
process is determined by a stationary Poisson distribution."

"Another important instance of shot noise arises in the other extreme 
from a uniform semiconductor, namely the motion of carriers across a 
high-field transition region, e.g. at a metallic contact or at a /p-n/ 
junction. Normally the carrier velocities in such a region would be of 
the order of 10^7 cm/s and the width of the region would lie in the 
range of 10^-5 to 10^-3 cm so that the transit time would be negligible 
except at the highest microwave frequencies. Furthermore it may be 
readily shown that since the change in quasi-Fermi level for the 
carriers across the transition region is very nearly equal to the 
applied voltage, the effect of each electron transit is effectively to 
induce a current impulse /ed(t)/, and thus full shot noise may be 
attributed to the flow."


        4.4 JUNCTION BREAKDOWN

"In all real diodes there is a limiting value of reverse voltage beyond 
which the reverse current increases greatly without significant increase 
of reverse voltage." (p. 63)

"The abrupt breakdown of silicon and well-cooled germanium types has a 
useful non-destructive range [...]. Such diodes are widely used as 
voltage regulators, and devices intended for this service are called 
/Zener diodes/ or /breakdown diodes/. (p. 64)


        Johnson Noise

"The first source of noise which we consider is Johnson noise, the 
thermal noise from a resistor. The engineering fact is that a resistor 
of resistance R acts like a noise generator."

   V^2  = 4 k T R B
   I^2  = 4 k T G B = 4 k T B / R

   R = resistance, ohms
   G = 1/R = conductance, mhos
   B = bandwidth, Hz
   k = Boltzmann's constant, 1.380E-23 joules / deg. K
   T = temperature in deg. K, or deg. C + 273

"What is the source of Johnson noise? In an ordinary resistor, it is a 
summation of the effects of the very short current pulses of many 
electrons as they travel between collisions, each pulse individually 
having a flat spectrum. In this case the noise is a manifestation of the 
Brownian movement of the electrons in the resistor."

END QUOTE
Johnson noise is caused by the exact same thing as Gas or Liquids 
mixing. or Pollen jiggling randomly on a beaker of water.



Noise in electronic devices (including resistors) has been studied for  
maybe  over 100 years.  Never  has anyone  suggested that it is not random.

PRNG algorithms have their origin in the mathematics of ciphers. It's 
always been beleived that if you either know which function is used or 
have enough history you can predict the series. They all lack the 
ultimate test of randomness,  the  ability  to predict the  next  item. 
(Pi  and e you can always calculate (predict) more digits. They are 
irrational, not random).





-- 
Mike