Mechanical generation of random bit sequences
Mok-Kong Shen
In sci.crypt.random-numbers I recently expressed my humble opinion
that for a 'normal' (average) user of security software -- who is
likely to be a layman in cryptology and also not very knowledgeable
in hardware/software to be in a position of always doing technically
correctly in the diverse procedures proposed or available for
collecting random bits from computer hardware and similar sources
of 'natural' randomness -- it seems to be desirable, if some simple
and easy to handle mechanical devices be available for rapidly
and conveniently generating small amounts of good quality random
bits as may be needed e.g. as keys or initialization vectors for
encryption algorithms.
Tossing coins to get even a very small number of bits is rather
tedious. Although throwing dice is generally more efficient, one
has to convert the result from base 6 to base 2 and the procedure
is also not too convenient in practice in my humble view. I like
therefore to solicit in this thread construction ideas that
eventually could be picked up by some interested manufacturers to
produce mechanical devices for sale on the market so that anyone could
with a little expense buy one to comfortably obtain some small
quantities of good quality random bits he needs at any time. (With
adequate tools skilled persons could perhaps even make such devices
themselves.)
Let me start for discussion and critiques with a proposal of my own
which is based on a device that I happen to possess for randomly
choosing 6 numbers from [1, 49] (used for fun in playing lottery,
being a gift of the German Federal Lottery to its customers many
years ago). I'll at fisrt describe this device and later indicate
modifications needed for our purpose. The said device is a tiny
thin flat box of 40*40*6 mm (more exactly, the thickness is tapered
from centre of 6 mm to the boundary of 4 mm), made of plastic so
that one can see the content when the device lies horizontally. The
hollow space inside is 30*30*2 mm. The upper one third of this is
free space as such (a chamber), while the lower two thirds of the
space is occupied largely by platic material in such a way that
there remain five parallel (to the sides of the box) grooves
(channels) of 20*2*2 mm with outlets to the upper space, with one
groove being shorter, of only 18 mm long. Alongside the grooves are
randomly ordered (though this is clearly unessential for the purpose)
printed numerals 1..49 can be seen. Inside the box there are 49 tiny
platic balls, a little bit smaller than 2 mm in diameter, 6 of which
are coloured red, while the rest are white. Now if a user first tilts
the box such that all balls are in the upper space and shakes the box
so the the balls are well mixed with one another and subsequently
tilts the box back while also shaking it a little bit, the balls will
fill the five channels and the numerals opposite to the red balls are
then read out to be the 6 desired random numbers in the range [1, 49].
(The box has a hook for attaching it to one's key bundle and thus can
be conveniently carried around.)
The modification for our purpose would be straightforward. We could
have the five channels equally long so as to accomodate 50 balls
(instead of 49), with 25 coloured white and the rest black. Then the
constellation of the balls in the channels after having been well
mixed in the upper chamber would give us a random bit sequence of
length 50.
As you may have surely noticed, there is however one very serious
deficiency in this design. Since there are 25 white and 25 black
balls in the box, in any sequence of length 50 thus generated the
frequency of white or black is exactly 0.5 and that's evidently no
good. A viable remedy, I suppose, could be to have, instead of
50 balls, 100 balls, with 50 being white and 50 black. Now there
will be 50 balls not falling down into the channels but these we'll
simply ignore. This way, the reading from the five channels would
not have the frequency problem depicted above. Equivalently we
could have 100 balls and 10 channels, with all balls filling the
channels but we ignore the reading from half of the (say, last 5)
channels. Of course, with the additional balls the box would have
to be enlarged a little bit with respect to the dimensions given
above. It may be preferable also to generate bit sequences of
length 64 instead of 50, in order to better suit what is commonly
required by block encryption algorithms like AES, which has key
lengths of 128/256 bits.
Of course, all mechanical devices are not perfect. Anyway, randomness
collected from them could hardly be expected to able to compete with
that e.g. from radioactive decay using sophisticated instruments. But
I suppose there is in practice always a general trade-off between
perfection and affordable cost (including time etc.). Thus I employed
above the term 'good' quality, not 'extremely high' quality, let
alone perfect quality (which would be needed for the theoretical 'one
time pad'). On the other hand, better quality, if desired, could be
achieved through post-processing, e.g. XOR-ing two sequences, etc.
Certainly, the balls in lottery or the dice in the casinos are
carefully maintained by technicians to eliminate bias as far as
possible (or at least most people 'believe' in that), while such is
not available for the class of very primitively manufactured devices
envisaged above. Nonetheless it seems not clear in the particular
case of the device I mentioned above how the imperfection of the
balls could 'as a whole' essentially negatively affect the quality
of the result. For, in contrast to the case of using one or a few
number of dice, one has in our case 100 balls, such that their
'individual' imperfection would in a sense be averaged out in my
humble view.
Thanks,
M. K. Shen
Maaartin
> Hi,
>
> In sci.crypt.random-numbers I recently expressed my humble opinion
> that for a 'normal' (average) user of security software -- who is
> likely to be a layman in cryptology and also not very knowledgeable
> in hardware/software to be in a position of always doing technically
> correctly in the diverse procedures proposed or available for
> collecting random bits from computer hardware and similar sources
> of 'natural' randomness -- it seems to be desirable, if some simple
> and easy to handle mechanical devices be available for rapidly
> and conveniently generating small amounts of good quality random
> bits as may be needed e.g. as keys or initialization vectors for
> encryption algorithms.
Any mechanical device is nowadays probably much more expensive than an
electronic one.
> Tossing coins to get even a very small number of bits is rather
> tedious. Although throwing dice is generally more efficient, one
> has to convert the result from base 6 to base 2 and the procedure
> is also not too convenient in practice in my humble view.
This is surely no problem as any good hash function helps and is more
than milion times faster than you throwing dice or typing in the
results.
> The modification for our purpose would be straightforward. We could
> have the five channels equally long so as to accomodate 50 balls
> (instead of 49), with 25 coloured white and the rest black. Then the
> constellation of the balls in the channels after having been well
> mixed in the upper chamber would give us a random bit sequence of
> length 50.
>
> As you may have surely noticed, there is however one very serious
> deficiency in this design. Since there are 25 white and 25 black
> balls in the box, in any sequence of length 50 thus generated the
> frequency of white or black is exactly 0.5 and that's evidently no
> good.
The entropy gained is about 47 bits (or less in case the throwing is
not random). Using a hash function solves all your problems here.
> A viable remedy, I suppose, could be to have, instead of
> 50 balls, 100 balls, with 50 being white and 50 black. Now there
> will be 50 balls not falling down into the channels but these we'll
> simply ignore.
By using more balls you can get more entropy. Throwing a part of it
away by ignoring some balls makes no sense since it's better to use a
hash.
> This way, the reading from the five channels would
> not have the frequency problem depicted above.
Yes but you do NOT get 50 bits of entropy!
> Equivalently we
> could have 100 balls and 10 channels, with all balls filling the
> channels but we ignore the reading from half of the (say, last 5)
> channels. Of course, with the additional balls the box would have
> to be enlarged a little bit with respect to the dimensions given
> above. It may be preferable also to generate bit sequences of
> length 64 instead of 50, in order to better suit what is commonly
> required by block encryption algorithms like AES, which has key
> lengths of 128/256 bits.
You'd better use more colors. With 4 colors and only 36 balls you can
get 100 bits.
> Of course, all mechanical devices are not perfect. Anyway, randomness
> collected from them could hardly be expected to able to compete with
> that e.g. from radioactive decay using sophisticated instruments. But
> I suppose there is in practice always a general trade-off between
> perfection and affordable cost (including time etc.). Thus I employed
> above the term 'good' quality, not 'extremely high' quality, let
> alone perfect quality (which would be needed for the theoretical 'one
> time pad'). On the other hand, better quality, if desired, could be
> achieved through post-processing, e.g. XOR-ing two sequences, etc.
Xoring may help, but using a strong hash is here virtually for free
and surely better.
> Certainly, the balls in lottery or the dice in the casinos are
> carefully maintained by technicians to eliminate bias as far as
> possible (or at least most people 'believe' in that),
I do believe it since any bias could be used againt the casino.
> while such is
> not available for the class of very primitively manufactured devices
> envisaged above. Nonetheless it seems not clear in the particular
> case of the device I mentioned above how the imperfection of the
> balls could 'as a whole' essentially negatively affect the quality
> of the result.
In another thread here, somebody adviced a use of carefully chosen
dice for password generation. But it's easy to find out that a bias of
let say 10% (I mean a completelly crappy dice which could ruin your
day when used in a board game; or your life when used in casino) is
quite harmless (you only need to throw it some more times to get the
same entropy).
me13013
> ... I'll at fisrt describe this [German Federal Lottery] device and later indicate
> modifications needed for our purpose. The said device is ...
I'm not trying to be negative, but a picture would be worth more than
all those words.
Bob H
Joseph Ashwood
news:hd40ab$gne$02$2...@news.t-online.com...
> it seems to be desirable, if some simple
> and easy to handle mechanical devices be available for rapidly
> and conveniently generating small amounts of good quality random
> bits as may be needed e.g. as keys or initialization vectors for
> encryption algorithms.
> [general description]
Unfortunately, such a box can hide very sizable biases, the effect of even
slightly different balls weights is notable. in fact in all the
lottery/keno/similar games such biases become noticable.
> The modification for our purpose would be straightforward. [description
> removed]
The modification doesn't help. The likely difference in weight between the
two pigments is enough to bias the system, and increasing the number of
inputs doesn't change too much. Not to mention being a large physical object
it has difficulties in usage.
As for why the lottery and keno systems tolerate such biases, there are
actually good reasons. For lottery systems the money coming in is split
according to fixed rules, no randomness is involved so the biases really
don't matter. Keno systems are setup very much the same as roulette, the
odds of hitting on roulette are 1/37 or 1/38, but the payout is 35/1 or
lower, multiple these together and the casino actually has a surprising
advantage to absorb any flaws in the wheel. The same applies to the Keno
machines, the payout is calculated according to the worst case entropy and
also a house advantage, any better case for the casino is just extra money.
That's why these systems don't work very well for cryptography, for a 1/37
odds, we'd be looking for a
36.9999999999999999999999999999999999999999999999999999999999999999999999999:1
payout or better.
A better idea would be to use electronics, no normal person is going to be
qualified to build a high quality lottery machine, a normal person likely
can't weigh anything except with a bathroom scale anyway, far too imprecise
for entropy collection. Using a small electronic device it is relatively
easy to build a small device with a switch, pressure pad, and an entropy
system from thermal noise in resistors. use the pressure pad to clock the
measurement, every time the slope of the pressure over time changes take a
measurement, any of the simple series elimination systems will work nicely.
Since a human muscle actually twitches hundreds of times a second, and
everyone's muscles twitch slightly differently (along with additional human
factors entering) there is a small amount of entropy in the clocking cycle,
this addresses some cyclic problems that happen in thermal noise in
resistors. The device will be far from perfect (100 bits of output may have
as much as 30 bits of entropy, probably less) but the attacker apparent
randomness will be very high.
Joe
Robert Scott
>A better idea would be to use electronics,....an entropy
>system from thermal noise in resistors...
The electronic systems are not trivial to build properly either. A device that
senses thermal noise in resistors is also likely to be affected by power line
interference or EMI, which degrades entropy.
Regardless of which system is used to generate raw random data (mechanical or
electronic), the entropy can be improved by oversampling the raw data and
reducing the data with a good cryptographic hash. If you start with 1000 bits
of raw data and reduce it to 100 with a hash, the effects of any bias in the
1000 bits will be masked. Here is the real advantage of an electronic system:
it is not that the bits are so much better quality, it is that the bits are so
much easier to sample, so that gross oversampling becomes feasible. If you had
to sample 10 times as many bits as you really wanted in a mechanical system, it
might become too much effort.
Bob Scott
Ypsilanti, Michigan
Mok-Kong Shen
> Mok-Kong Shen wrote:
[snip]
>> A viable remedy, I suppose, could be to have, instead of
>> 50 balls, 100 balls, with 50 being white and 50 black. Now there
>> will be 50 balls not falling down into the channels but these we'll
>> simply ignore.
>> This way, the reading from the five channels would
>> not have the frequency problem depicted above.
>
> Yes but you do NOT get 50 bits of entropy!
Could you please explain why?
Thanks,
M. K. Shen
Robert Scott
wrote:
Imagine betting on color of the last ball. If you really had 50 bits of
entropy, then seeing the first 49 balls gives you no advantage in betting on the
color of the 50th ball. But suppose I see the first 49 balls and they are 40
blacks and 9 whites. Now I know that the last ball must be chosen from 10
blacks and 41 whites. I think I will bet that the 50th ball is white. And I
would be right much more than 50% of the time. So the entropy is obviously not
perfect.
Bob Scott
Ypsilanti, Michigan
Mok-Kong Shen
> A better idea would be to use electronics, no normal person is going to
> be qualified to build a high quality lottery machine, a normal person
> likely can't weigh anything except with a bathroom scale anyway, far too
> imprecise for entropy collection. Using a small electronic device it is
> relatively easy to build a small device with a switch, pressure pad, and
> an entropy system from thermal noise in resistors. use the pressure pad
> to clock the measurement, every time the slope of the pressure over time
> changes take a measurement, any of the simple series elimination systems
> will work nicely. Since a human muscle actually twitches hundreds of
> times a second, and everyone's muscles twitch slightly differently
> (along with additional human factors entering) there is a small amount
> of entropy in the clocking cycle, this addresses some cyclic problems
> that happen in thermal noise in resistors. The device will be far from
> perfect (100 bits of output may have as much as 30 bits of entropy,
> probably less) but the attacker apparent randomness will be very high.
But the problem is that no such devices are available on the market
for a normal user to buy and to use (hopefully without difficulties by
a layman).
M. K. Shen
Mok-Kong Shen
But you have to consider that the 100 balls are all competing to
enter the five channels. If the balls have been well mixed, the
chance of a white ball or a black ball entering a channel is the
same, isn't it?
M. K. Shen
Robert Scott
wrote:
>
>But you have to consider that the 100 balls are all competing to
>enter the five channels. If the balls have been well mixed, the
>chance of a white ball or a black ball entering a channel is the
>same, isn't it?
Yes, the chance of any one ball being black or white is exactly 50%. But when
evaluating entropy, you also have to take into account the conditional
probabiltiy of a ball being a certain color given the knowledge of what other
balls are. Couldn't you say the same thing about the original proposal that
used 25 black and 25 white balls? They were also throroughly mixed, and the
chance of a white or black ball entering a channel is the same. Yet you realize
that this method is flawed because after you see the first 49 balls, you know
with exact certainty what color the last ball is before you see it. Well, the
defect in that proposal just gets watered down a little by adding 50 more balls.
But the defect does not ever get completely eliminated. It still detracts from
the ideal 50 bits of entropy. Maybe it is just 48 bits. I don't know. But it
is definitely not 50 bits.
Bob Scott
Ypsilanti, Michigan
Mok-Kong Shen
No. The flaw with 50 balls is different. Note, for example, this:
In a random sequence there is a certain probability that in a
sequence of length 100 all bits may be 0, and this is not the
case with 50 balls in the device.
M. K. Shen
Mok-Kong Shen
> No. The flaw with 50 balls is different. Note, for example, this:
> In a random sequence there is a certain probability that in a
> sequence of length 100 all bits may be 0, and this is not the
> case with 50 balls in the device.
Sorry, typo. Please read 50 for 100 above.
M. K. Shen
Robert Scott
wrote:
>No. The flaw with 50 balls is different. Note, for example, this:
>In a random sequence there is a certain probability that in a
>sequence of length 100 all bits may be 0, and this is not the
>case with 50 balls in the device.
The 100 balls have a similar flaw, just to a lesser degree. In a perfectly
random uncorrelated sequence of 50 bits, the probability that they are all 0 is
exactly 2^(-50). But when choosing 50 balls from 100, the probability that all
50 chosen balls are black is 50! * 50!* / 100!. I leave it as an exercise to
verify that these two numbers are not the same.
Bob Scott
Ypsilanti, Michigan
Mok-Kong Shen
> Mok-Kong Shen wrote:
>
>> No. The flaw with 50 balls is different. Note, for example, this:
>> In a random sequence there is a certain probability that in a
>> sequence of length 100 all bits may be 0, and this is not the
>> case with 50 balls in the device.
>
> The 100 balls have a similar flaw, just to a lesser degree. In a perfectly
> random uncorrelated sequence of 50 bits, the probability that they are all 0 is
> exactly 2^(-50). But when choosing 50 balls from 100, the probability that all
> 50 chosen balls are black is 50! * 50!* / 100!. I leave it as an exercise to
> verify that these two numbers are not the same.
Being layman, I am confused. Let's simplify the scenario so that
there is only one channel with capacity of 2 and there are four balls,
2 white and 2 black. What is the probability of 2 black balls getting
into the channel?
Thanks,
M. K. Shen
Mok-Kong Shen
I see in the meantime why my way of thinking is incorrect.
M. K. Shen
Mok-Kong Shen
If on the other hand one has two channels of capacity 1 instead,
then the chance of having both channels filled black is 1/4.
Is that right?
Thanks,
M. K. Shen
Mok-Kong Shen
> If on the other hand one has two channels of capacity 1 instead,
> then the chance of having both channels filled black is 1/4.
> Is that right?
I am mistaken. Apology for the several useless posts from me.
M. K. Shen
Spinner
Folks, y'all are making the fix too complicated. Lets say you are
going to draw 10 balls from a cloud of 100 black (50/50 each). There
is also a reservoir of 20 balls (10 each) in storage.
Then you drop a ball into a channel. The box reads the color and puts
another ball into the cloud of the same color from the reservoir. Mix
the cloud and drop another ball. This way every single draw into the
channel has precisely the same starting conditions and all's well.
Tada!
And if you want simple random noise, put an unshielded microphone on a
stick and let the wind blow past it. Play with the gain and clipping a
bit and you get a nice collection of white noise (amplitude).
If you're really fancy and handy with electronics, point a telescope
at a star and figure out a way to capture the dance as the atmosphere
moves the the image around. There's not a lot short of quantum
mechanics that is more random than those little atmospheric
microdisturbances - you're looking thru 100 miles of progressively
thinning thermally randomized wiggling air. It's an exercise for the
mechanic to filter out ground vibrations. (I suspect you might not
want to, however.)
--
2+2!=5 even for extremely large values of 2
Joseph Ashwood
news:rksff55nikfvhei9i...@4ax.com...
> Folks, y'all are making the fix too complicated. Lets say you are
> going to draw 10 balls from a cloud of 100 black (50/50 each). There
> is also a reservoir of 20 balls (10 each) in storage.
>
> Then you drop a ball into a channel. The box reads the color and puts
> another ball into the cloud of the same color from the reservoir. Mix
> the cloud and drop another ball. This way every single draw into the
> channel has precisely the same starting conditions and all's well.
>
> Tada!
Unfortunately, that is not as good as you think. There will be a bias for
each ball color, and an additional bias for each individual ball. While it
would seem to be a perfect solution, all you've done is build a more
complicated device, but have failed to improve any of the failure modes.
You'll notice that the amount of entropy withdrawn continually drops until
the system delivers very little entropy per pull. It would be better to look
at the actual statistics from a lottery system (they don't actually care,
but the systems are surprisingly good) you'll find the same numbers hit over
and over.
> And if you want simple random noise, put an unshielded microphone on a
> stick and let the wind blow past it. Play with the gain and clipping a
> bit and you get a nice collection of white noise (amplitude).
This has almost 0 entropy. What sounds random to humans very often isn't.
The wind has a strong bias to continue to blow at close to the same rate
from the same direction, and the turbulence are highly predictable.
> If you're really fancy and handy with electronics, point a telescope
> at a star and figure out a way to capture the dance as the atmosphere
> moves the the image around. There's not a lot short of quantum
> mechanics that is more random than those little atmospheric
> microdisturbances - you're looking thru 100 miles of progressively
> thinning thermally randomized wiggling air.
You're also looking at the same air as the attacker, the level of entropy is
effectively 0.
That's the problem, things that seem random, very often have little entropy.
Joe
Joseph Ashwood
They aren't, but there are no dependable devices that deliver high entropy
output on the market. Either way the device will have to be built. In terms
of use, about the only assumption I made was that a layman can press and
hold a button.
Joe
Joseph Ashwood
news:4af6ddbe...@news.eternal-september.org...
> On Sun, 8 Nov 2009 04:21:46 -0800, "Joseph Ashwood" <ash...@msn.com>
> wrote:
>
>>A better idea would be to use electronics,....an entropy
>>system from thermal noise in resistors...
>
> The electronic systems are not trivial to build properly either. A device
> that
> senses thermal noise in resistors is also likely to be affected by power
> line
> interference or EMI, which degrades entropy.
I had a assumed a reasonable design, typically encased in metal or a
metallic paint building a farraday cage, just like your cellphone already
has.
>
> Regardless of which system is used to generate raw random data (mechanical
> or
> electronic), the entropy can be improved by oversampling the raw data
Actually it very often reduces the entropy. Take a simple sin curve,
sampling randomly gives random numbers, oversampling gives a higher
precision sin curve, the same applies with disk seem timings, thread
scheduling, many of the best sources of entropy available, and the entropy
level in the resistor drops with too much over sampling (the more you know
about it, the less is unknown). Entropy is not limitless, trying to sample
too frequently you very quickly reach the limit of entropy that can be
pulled, sampling beyond that is problematic at best.
Joe
Unruh
>"Joseph Ashwood" <ash...@msn.com> wrote:
??? I do not think youread his post at all. If eveytime any black ball has 3
times the chance of dropping asn any white, your comments will not help.
That he is taling about 1.003 times as much is irrelevant.
>Then you drop a ball into a channel. The box reads the color and puts
>another ball into the cloud of the same color from the reservoir. Mix
>the cloud and drop another ball. This way every single draw into the
>channel has precisely the same starting conditions and all's well.
>Tada!
>And if you want simple random noise, put an unshielded microphone on a
>stick and let the wind blow past it. Play with the gain and clipping a
>bit and you get a nice collection of white noise (amplitude).
And it is liable to be strongly biased because the wind is highly correlated.
>If you're really fancy and handy with electronics, point a telescope
>at a star and figure out a way to capture the dance as the atmosphere
>moves the the image around. There's not a lot short of quantum
>mechanics that is more random than those little atmospheric
>microdisturbances - you're looking thru 100 miles of progressively
Again, they are correlated in time.
>thinning thermally randomized wiggling air. It's an exercise for the
>mechanic to filter out ground vibrations. (I suspect you might not
>want to, however.)
And most of the wiggling of the stars occurs in the first 20 meters of the
atmosphere ( which is why they build domes high).
Mok-Kong Shen
[snip]
> ........... to have, instead of
> 50 balls, 100 balls, with 50 being white and 50 black. Now there
> will be 50 balls not falling down into the channels but these we'll
> .......... On the other hand, better quality, if desired, could be
> achieved through post-processing, e.g. XOR-ing two sequences, etc.
> number of dice, one has in our case 100 balls, such that their
> 'individual' imperfection would in a sense be averaged out in my
> humble view.
I like to thank Robert Scott for showing that the sequence generated
by such a device is biased. This naturally leads to thinking of applying
unbiasing schemes, of which the one of von Neumann (00,11 -> ignore,
10 -> 1, 01 -> 0) seems to be the most practical one for convenient
application by laypeople. Further possibilities are interleaving of
bits of two sequences and XOR-ing two sequences and even simultaneous
and multiple applications of these schemes. It is my humble conviction
that more complicated processing should be left to those users that
are knowledgeable and normal (average) users should only be trusted to
do simple and straightforward operations. For otherwise there could be
very undesirable consequneces out of their mistakes. So I would think
that, before good and easy to handle hardware bit generators based on
electronics etc. are on the market, devices of the sort I mentioned
could be a viable 'interim' solution satisfying the practical needs of
random bit sequences. I like thus to once again solicit design ideas
of mechanical random bit generators from interested readers of this
thread.
Thanks,
M. K. Shen
Unruh
>Mok-Kong Shen wrote:
>[snip]
>> ........... to have, instead of
>> 50 balls, 100 balls, with 50 being white and 50 black. Now there
>> will be 50 balls not falling down into the channels but these we'll
>> simply ignore. ........
>> .......... On the other hand, better quality, if desired, could be
>> achieved through post-processing, e.g. XOR-ing two sequences, etc.
>> ........ in contrast to the case of using one or a few
>> number of dice, one has in our case 100 balls, such that their
>> 'individual' imperfection would in a sense be averaged out in my
>> humble view.
>[snip]
>I like to thank Robert Scott for showing that the sequence generated
>by such a device is biased. This naturally leads to thinking of applying
>unbiasing schemes, of which the one of von Neumann (00,11 -> ignore,
>10 -> 1, 01 -> 0) seems to be the most practical one for convenient
While that gets rid of independent biases it does not cure correlations.
>application by laypeople. Further possibilities are interleaving of
>bits of two sequences and XOR-ing two sequences and even simultaneous
>and multiple applications of these schemes. It is my humble conviction
>that more complicated processing should be left to those users that
>are knowledgeable and normal (average) users should only be trusted to
>do simple and straightforward operations. For otherwise there could be
click on a window and read off the number. Is that difficult? Ie, elecgtronic (
eg based on /dev/urandom) are easier, and far better than any of your mechanical
schemes.
>very undesirable consequneces out of their mistakes. So I would think
>that, before good and easy to handle hardware bit generators based on
>electronics etc. are on the market, devices of the sort I mentioned
>could be a viable 'interim' solution satisfying the practical needs of
>random bit sequences. I like thus to once again solicit design ideas
Aand where is this pent up need in the population at large for "random number
sequences"?
Robert Scott
>> Regardless of which system is used to generate raw random data (mechanical
>> or
>> electronic), the entropy can be improved by oversampling the raw data
>
>Actually it very often reduces the entropy. Take a simple sin curve,
>sampling randomly gives random numbers, oversampling gives a higher
>precision sin curve, the same applies with disk seem timings, thread
>scheduling, many of the best sources of entropy available, and the entropy
>level in the resistor drops with too much over sampling (the more you know
>about it, the less is unknown). Entropy is not limitless, trying to sample
>too frequently you very quickly reach the limit of entropy that can be
>pulled, sampling beyond that is problematic at best.
I agree. The sampling rate has to be limited to a rate appropriate to the
source. And when I suggested oversampling, I also assumed a "reasonable
design". If you find yourself sampling faster than the source is uncorrelated,
then you have to sample slower and deliver fewer random bits per second, and
just take more time. This is a real problem for the mechanical balls method
because it takes so long to mix the balls and select. It is less of a problem
with the thermal noise of resistors method because that noise is wideband and
can be sampled quite fast without exposing too much correlation in the samples.
In either case, some bit-reduction with a cryptographic hash is the best way to
remove what little useable correlation or bias might remain.
Bob Scott
Ypsilanti, Michigan
Mok-Kong Shen
> Mok-Kong Shen writes:
>
>> Mok-Kong Shen wrote:
>> [snip]
>>> ........... to have, instead of
>>> 50 balls, 100 balls, with 50 being white and 50 black. Now there
>>> will be 50 balls not falling down into the channels but these we'll
>>> simply ignore. ........
>>> .......... On the other hand, better quality, if desired, could be
>>> achieved through post-processing, e.g. XOR-ing two sequences, etc.
>>> ........ in contrast to the case of using one or a few
>>> number of dice, one has in our case 100 balls, such that their
>>> 'individual' imperfection would in a sense be averaged out in my
>>> humble view.
>> [snip]
>
>> I like to thank Robert Scott for showing that the sequence generated
>> by such a device is biased. This naturally leads to thinking of applying
>> unbiasing schemes, of which the one of von Neumann (00,11 -> ignore,
>> 10 -> 1, 01 -> 0) seems to be the most practical one for convenient
>
> While that gets rid of independent biases it does not cure correlations.
In my humble view, generation with hardware (including mechanics)
tends to have by nature lesser degree of problems with correlations.
Anyway, XOR-ing sequences would reduce correlations, if I don't err.
>> application by laypeople. Further possibilities are interleaving of
>> bits of two sequences and XOR-ing two sequences and even simultaneous
>> and multiple applications of these schemes. It is my humble conviction
>> that more complicated processing should be left to those users that
>> are knowledgeable and normal (average) users should only be trusted to
>> do simple and straightforward operations. For otherwise there could be
>
> click on a window and read off the number. Is that difficult? Ie, elecgtronic (
> eg based on /dev/urandom) are easier, and far better than any of your mechanical
> schemes.
Use of primitive generation methods has an (of course arguable depending
on one's standpoint) advantage that it is far less subject to malicious
manipulations in my humble view, i.e. you know what you have.
>> very undesirable consequneces out of their mistakes. So I would think
>> that, before good and easy to handle hardware bit generators based on
>> electronics etc. are on the market, devices of the sort I mentioned
>> could be a viable 'interim' solution satisfying the practical needs of
>> random bit sequences. I like thus to once again solicit design ideas
>
> Aand where is this pent up need in the population at large for "random number
> sequences"?
Because that up to now there are no good hardware generators that
layman could buy and easily use, the normal users simply can do anything
in this direction. This certainly doesn't mean that there is therefore
no need. The situation is the same, I would say, with encryption
of SMS. Because the mobile phone products up to now are not provided
by the producers adequate features for encryption, there is no SMS
security for the general public. (According to a follow-up in a thread
intiated by me, the mobile phone of the president of US does however
have encryption, I suppose including voice encryption.) That does not
mean that general users have no desire/need of privacy of their SMS.
Personally I have even the suspicion (you might call it fantacy
if you perfer) that this is somehow influenced by politics. (To support
that, let me tell that to my personal knowledge in the eighties of the
last century the UNIX computer systems delivered to Europe had one
subtle difference to those run in America in that the DES module was
removed. That was clearly a result of influence from politics in my
conviction.)
M. K. Shen
Mok-Kong Shen
One simple idea that trivially comes to mind would be to have a tiny
device working on the same principle as a roulette, producing in one
spinning 4 or maybe more bits. Though we know that even big routlettes
may be imperfect, in our humble context extreme perfection seems
unnecessary. As I wrote previously, such devices are valuable as an
'interim' solution before technically sophisticated and much more
satisfying devices based on electronics, that are suitable for handling
by laypeople and are above all inexpensive, become available on the
market for the general public. The possibility of some simple
post-procesing of the bits obtained, if desired, may be mentioned here
once again.
BTW, there has been a German made device for generating random numbers
named 'Violine'. See Fig.2.9.3 on p.172 of K. Schmeh, Codeknacker gegen
Codemaker, 2007. There a number of small balls were used in a device
having the shape of a violine. You can access part of the book with:
http://books.google.de/books?id=cz9Fclgref4C
Thanks,
M. K. Shen
Unruh
>Unruh wrote:
>> Mok-Kong Shen writes:
>>
>>> Mok-Kong Shen wrote:
>>> [snip]
>>>> ........... to have, instead of
>>>> 50 balls, 100 balls, with 50 being white and 50 black. Now there
>>>> will be 50 balls not falling down into the channels but these we'll
>>>> simply ignore. ........
>>>> .......... On the other hand, better quality, if desired, could be
>>>> achieved through post-processing, e.g. XOR-ing two sequences, etc.
>>>> ........ in contrast to the case of using one or a few
>>>> number of dice, one has in our case 100 balls, such that their
>>>> 'individual' imperfection would in a sense be averaged out in my
>>>> humble view.
>>> [snip]
>>
>>> I like to thank Robert Scott for showing that the sequence generated
>>> by such a device is biased. This naturally leads to thinking of applying
>>> unbiasing schemes, of which the one of von Neumann (00,11 -> ignore,
>>> 10 -> 1, 01 -> 0) seems to be the most practical one for convenient
>>
>> While that gets rid of independent biases it does not cure correlations.
>In my humble view, generation with hardware (including mechanics)
>tends to have by nature lesser degree of problems with correlations.
>Anyway, XOR-ing sequences would reduce correlations, if I don't err.
Generation with mechanical systems tends to have more correlations, not less.
(correlations are what the physical world is all about.It is what allows one
create laws of physics).
>>> application by laypeople. Further possibilities are interleaving of
>>> bits of two sequences and XOR-ing two sequences and even simultaneous
>>> and multiple applications of these schemes. It is my humble conviction
>>> that more complicated processing should be left to those users that
>>> are knowledgeable and normal (average) users should only be trusted to
>>> do simple and straightforward operations. For otherwise there could be
>>
>> click on a window and read off the number. Is that difficult? Ie, elecgtronic (
>> eg based on /dev/urandom) are easier, and far better than any of your mechanical
>> schemes.
>Use of primitive generation methods has an (of course arguable depending
>on one's standpoint) advantage that it is far less subject to malicious
>manipulations in my humble view, i.e. you know what you have.
As has been pointed out loaded dice are almost impossible to detect but very
effective.
>>> very undesirable consequneces out of their mistakes. So I would think
>>> that, before good and easy to handle hardware bit generators based on
>>> electronics etc. are on the market, devices of the sort I mentioned
>>> could be a viable 'interim' solution satisfying the practical needs of
>>> random bit sequences. I like thus to once again solicit design ideas
>>
>> Aand where is this pent up need in the population at large for "random number
>> sequences"?
>Because that up to now there are no good hardware generators that
>layman could buy and easily use, the normal users simply can do anything
>in this direction. This certainly doesn't mean that there is therefore
You have not given any evidence that there is a need for such a generator.
Go onto the street and ask 10 people how much they would pay for a random number
genrator.
>no need. The situation is the same, I would say, with encryption
>of SMS. Because the mobile phone products up to now are not provided
>by the producers adequate features for encryption, there is no SMS
>security for the general public. (According to a follow-up in a thread
>intiated by me, the mobile phone of the president of US does however
>have encryption, I suppose including voice encryption.) That does not
>mean that general users have no desire/need of privacy of their SMS.
So? Just because there is a need for butter does not mean that there is need for
left handed toenail twisters.
>Personally I have even the suspicion (you might call it fantacy
>if you perfer) that this is somehow influenced by politics. (To support
>that, let me tell that to my personal knowledge in the eighties of the
>last century the UNIX computer systems delivered to Europe had one
>subtle difference to those run in America in that the DES module was
>removed. That was clearly a result of influence from politics in my
>conviction.)
No. It was the result of a law which limited the distribution of encryption.
>M. K. Shen
Mok-Kong Shen
> Mok-Kong Shen wrote:
>
>> In my humble view, generation with hardware (including mechanics)
>> tends to have by nature lesser degree of problems with correlations.
>> Anyway, XOR-ing sequences would reduce correlations, if I don't err.
>
> Generation with mechanical systems tends to have more correlations, not less.
> (correlations are what the physical world is all about.It is what allows one
> create laws of physics).
Comment on what is in the parentheses: So according to you, quantum
cryptography is nothing, right?
>> Use of primitive generation methods has an (of course arguable depending
>> on one's standpoint) advantage that it is far less subject to malicious
>> manipulations in my humble view, i.e. you know what you have.
>
> As has been pointed out loaded dice are almost impossible to detect but very
> effective.
As I said previously, in the case of a large number of tiny balls
imperfections would average out, even if you decidedly manufacture
'loaded' spherical balls.
>> Because that up to now there are no good hardware generators that
>> layman could buy and easily use, the normal users simply can do anything
>> in this direction. This certainly doesn't mean that there is therefore
>
> You have not given any evidence that there is a need for such a generator.
> Go onto the street and ask 10 people how much they would pay for a random number
> genrator.
Ask them how much they would pay, 'if' their e-mails, telephone
conversations, SMS would be secure against all ubiquitous attacks.
Would $10 be too much?
>> no need. The situation is the same, I would say, with encryption
>> of SMS. Because the mobile phone products up to now are not provided
>> by the producers adequate features for encryption, there is no SMS
>> security for the general public. (According to a follow-up in a thread
>> intiated by me, the mobile phone of the president of US does however
>> have encryption, I suppose including voice encryption.) That does not
>> mean that general users have no desire/need of privacy of their SMS.
>
> So? Just because there is a need for butter does not mean that there is need for
> left handed toenail twisters.
Sorry, I don't understand your analogy. Please give another more
simple one.
>> Personally I have even the suspicion (you might call it fantacy
>> if you perfer) that this is somehow influenced by politics. (To support
>> that, let me tell that to my personal knowledge in the eighties of the
>> last century the UNIX computer systems delivered to Europe had one
>> subtle difference to those run in America in that the DES module was
>> removed. That was clearly a result of influence from politics in my
>> conviction.)
>
> No. It was the result of a law which limited the distribution of encryption.
Any judicial law is determined from politics, or are you unaware of this
plain fact?
M. K. Shen
Robert Scott
wrote:
>Ask them how much they would pay, 'if' their e-mails, telephone
>conversations, SMS would be secure against all ubiquitous attacks.
>Would $10 be too much?
A random number generator is not a necessary component of a secure SMS system.
Using random numbers can be useful for seeding IV's, but there are other ways to
seed IV's that are just as good.
Bob Scott
Ypsilanti, Michigan
Mok-Kong Shen
What I mean in this thread is that, if one needs to encrypt a message
(SMS is only a special case) using AES or other algorithms, one would
need random stuffs for keys and/or IVs, and for that some simple
devices that can be well handled by laypeople seem desirable.
M. K. Shen
Unruh
>On Tue, 10 Nov 2009 16:43:40 +0100, Mok-Kong Shen <mok-ko...@t-online.de>
>wrote:
>>Ask them how much they would pay, 'if' their e-mails, telephone
>>conversations, SMS would be secure against all ubiquitous attacks.
>>Would $10 be too much?
And you would use a mechanical random number generator to secure a computer
program? Weird. I would not pay anything. I would charge for having had my time
wasted by being asked the question.
>A random number generator is not a necessary component of a secure SMS system.
>Using random numbers can be useful for seeding IV's, but there are other ways to
>seed IV's that are just as good.
And there are better ways of generating random numbers than a mechanical
generator.
>Bob Scott
>Ypsilanti, Michigan
Unruh
>Unruh wrote:
>> Mok-Kong Shen wrote:
>>
>>> In my humble view, generation with hardware (including mechanics)
>>> tends to have by nature lesser degree of problems with correlations.
>>> Anyway, XOR-ing sequences would reduce correlations, if I don't err.
>>
>> Generation with mechanical systems tends to have more correlations, not less.
>> (correlations are what the physical world is all about.It is what allows one
>> create laws of physics).
>Comment on what is in the parentheses: So according to you, quantum
>cryptography is nothing, right?
No it is something. But one must work hard to make sure that correlations are not
generated. But all of the mechanical systems which were suggested and I commented
on had nothing to do with quantum mechanics.
>>> Use of primitive generation methods has an (of course arguable depending
>>> on one's standpoint) advantage that it is far less subject to malicious
>>> manipulations in my humble view, i.e. you know what you have.
>>
>> As has been pointed out loaded dice are almost impossible to detect but very
>> effective.
>As I said previously, in the case of a large number of tiny balls
>imperfections would average out, even if you decidedly manufacture
>'loaded' spherical balls.
No, they would not.
>>> Because that up to now there are no good hardware generators that
>>> layman could buy and easily use, the normal users simply can do anything
>>> in this direction. This certainly doesn't mean that there is therefore
>>
>> You have not given any evidence that there is a need for such a generator.
>> Go onto the street and ask 10 people how much they would pay for a random number
>> genrator.
>Ask them how much they would pay, 'if' their e-mails, telephone
>conversations, SMS would be secure against all ubiquitous attacks.
>Would $10 be too much?
>>> no need. The situation is the same, I would say, with encryption
>>> of SMS. Because the mobile phone products up to now are not provided
>>> by the producers adequate features for encryption, there is no SMS
>>> security for the general public. (According to a follow-up in a thread
>>> intiated by me, the mobile phone of the president of US does however
>>> have encryption, I suppose including voice encryption.) That does not
>>> mean that general users have no desire/need of privacy of their SMS.
>>
>> So? Just because there is a need for butter does not mean that there is need for
>> left handed toenail twisters.
>Sorry, I don't understand your analogy. Please give another more
>simple one.
You are advising the sale of mechanical random number generators to help with the
privacy of their SMS. They are as much use as left handed toenail twisters are to
someone who needs butter.
>>> Personally I have even the suspicion (you might call it fantacy
>>> if you perfer) that this is somehow influenced by politics. (To support
>>> that, let me tell that to my personal knowledge in the eighties of the
>>> last century the UNIX computer systems delivered to Europe had one
>>> subtle difference to those run in America in that the DES module was
>>> removed. That was clearly a result of influence from politics in my
>>> conviction.)
>>
>> No. It was the result of a law which limited the distribution of encryption.
>Any judicial law is determined from politics, or are you unaware of this
>plain fact?
"the influence of politics" as an idiom has nothing to do with "the ouput of a
political process" except using some of the same words. You need to understand
English idioms before using them ( except I suspect you do and are now trying to
be cute").
>M. K. Shen
Unruh
Yes, we understood what you meant. And it is wrong. It would not be of use or
desirable.
>M. K. Shen
Mok-Kong Shen
> Mok-Kong Shen wrote:
>> What I mean in this thread is that, if one needs to encrypt a message
>> (SMS is only a special case) using AES or other algorithms, one would
>> need random stuffs for keys and/or IVs, and for that some simple
>> devices that can be well handled by laypeople seem desirable.
>
> Yes, we understood what you meant. And it is wrong. It would not be of use or
> desirable.
Then please argue instead of categorically denying without support.
M. K. Shen
Mok-Kong Shen
>> Mok-Kong Shen <mok-ko...@t-online.de>
>> wrote:
>
>>> Ask them how much they would pay, 'if' their e-mails, telephone
>>> conversations, SMS would be secure against all ubiquitous attacks.
>>> Would $10 be too much?
>
> And you would use a mechanical random number generator to secure a computer
> program? Weird. I would not pay anything. I would charge for having had my time
> wasted by being asked the question.
Do you consider keys and IVs are needed to let encrpytion algorithms
work properly? The generators simply supply that, they do 'nothing' more.
M. K. Shen
Mok-Kong Shen
> Mok-Kong Shen wrote:
>> As I said previously, in the case of a large number of tiny balls
>> imperfections would average out, even if you decidedly manufacture
>> 'loaded' spherical balls.
>
> No, they would not.
Note there are 100 balls (not just a couple of dice), their large number
gives rise to the averaging effect. BTW, this is also why in statistics
the mean value has a sense and is important. The 'individual'
non-perfection doesn't matter much. I suppose such averaging effects are
well-known, since they are ubiquitous (including such fields that are
very far removed from the present context as e.g. in voting, where one's
individual vote's influence as such is entirely negligible).
M. K. Shen
Maaartin
> On Mon, 9 Nov 2009 04:15:30 -0800, "Joseph Ashwood" <ashw...@msn.com> wrote:
> >> Regardless of which system is used to generate raw random data (mechanical
> >> or
> >> electronic), the entropy can be improved by oversampling the raw data
>
> >Actually it very often reduces the entropy.
I disagree. Assuming the oversampling contains all samples of the
original, there can't be less entropy which is easy to see: Just drop
all extraneous samples, this surely generates no entropy.
> > Take a simple sin curve,
> >sampling randomly gives random numbers, oversampling gives a higher
> >precision sin curve,
Yes, but here not the sin curve but here the sampling trigger is the
entropy source.
Replacing it by regular higher rate sampling looses all entropy.
Replacing it by appropriate irregular higher rate sampling make gain
nothing because of limited precission.
With oversampling the entropy per second may only increase, but the
entropy per sample decreases and you have more data to process by a
hash function.
Unruh
>Unruh wrote:
I use electronic generators (eg /dev/urandom) which are much much much
better than any mechanical generator. But then I have said this before,
and have not had any impact on you.
>M. K. Shen
Unruh
Hm. I wonder why the casinos do not allow you to use your own dice.
After all there are hundreds of dice throws. Should all average out even
if you are using a loaded dice! Must just be ornariness on their part.
>M. K. Shen
Spinner
>"Spinner" <nos...@nospam.net> wrote in message
>news:rksff55nikfvhei9i...@4ax.com...
>
>> Folks, y'all are making the fix too complicated. Lets say you are
>> going to draw 10 balls from a cloud of 100 black (50/50 each). There
>> is also a reservoir of 20 balls (10 each) in storage.
>>
>> Then you drop a ball into a channel. The box reads the color and puts
>> another ball into the cloud of the same color from the reservoir. Mix
>> the cloud and drop another ball. This way every single draw into the
>> channel has precisely the same starting conditions and all's well.
>>
>> Tada!
>
>Unfortunately, that is not as good as you think. There will be a bias for
>each ball color, and an additional bias for each individual ball. While it
>would seem to be a perfect solution, all you've done is build a more
>complicated device, but have failed to improve any of the failure modes.
>You'll notice that the amount of entropy withdrawn continually drops until
>the system delivers very little entropy per pull. It would be better to look
>at the actual statistics from a lottery system (they don't actually care,
>but the systems are surprisingly good) you'll find the same numbers hit over
>and over.
>
Why is there a bias for each ball color? If there are exactly 50/50
of each color in the pool from which a ball is drawn each time, how is
it that draw 2 is different in any form from draw 1 ? There is an
infinite supply of replacement balls..and the replacement is precisely
identical to the one drawn - returning the pool to its exact initial
state. So the chances of pulling one color from a selection of 50 each
is exactly .5. Every single time.
>> And if you want simple random noise, put an unshielded microphone on a
>> stick and let the wind blow past it. Play with the gain and clipping a
>> bit and you get a nice collection of white noise (amplitude).
>
>This has almost 0 entropy. What sounds random to humans very often isn't.
>The wind has a strong bias to continue to blow at close to the same rate
>from the same direction, and the turbulence are highly predictable.
>
Put an oscilloscope on a microphone, and turn the gain way up. I
don't know where you come from, but the wind is EXTREMELY inconstant
at the 100ths meter/s leverl - there are micro variations in speed,
density, and humidity (ask any meteorologist .. it really mucks up the
stats.). An anemometer wont pick it up, but something very sensitive
to velocity does .. which is why all wind measurements are averages.
>> If you're really fancy and handy with electronics, point a telescope
>> at a star and figure out a way to capture the dance as the atmosphere
>> moves the the image around. There's not a lot short of quantum
>> mechanics that is more random than those little atmospheric
>> microdisturbances - you're looking thru 100 miles of progressively
>> thinning thermally randomized wiggling air.
>
>You're also looking at the same air as the attacker, the level of entropy is
>effectively 0.
>
You are obviously not an astronomer. Two scopes side by side looking
at the same star will see completely different variations. And they
change millisecond by millisecond. Unless my 'attacker" is looking
through MY scope at MY star, I absolutely guarantee they will not see
the variations in position and intensity that I do. I also guarantee
that its thermally random and collecting a nice set of those
variations would make a nifty one time pad. Atmospheric
microdistortions do not repeat - even a little.
>That's the problem, things that seem random, very often have little entropy.
> Joe
The atmosphere is the definitive random environment - even measuring
temperature to the nearest 1/100 degree 100x/sec should return
variations. People don't realize how 'lumpy' air is. But ask an
astronomer looking thru a column of air a foot wide and 100 miles
long, or for that matter, a qualified sniper, looking through an air
column a mile long and 6 inches wide. There is a lot of variation,
and it is all (repeat all) driven by thermal effects. Get the sample
rate and resolution high enough, and thermal is driven by quantum
level effects and randomness.
Throwing around the word entropy without a definition, by the way, is
not terribly useful if you are going to dispute that random events
have none.
Unruh
>"Joseph Ashwood" <ash...@msn.com> wrote:
a) No mechanical device has an infinite number of balls.
b) lets say the black balls are steel, and the white ones plystyrene. The black
ones will settle to the bottom when you shake the thing, and thus the next ball
will almost allways be black. Clearly a bias.
>>> And if you want simple random noise, put an unshielded microphone on a
>>> stick and let the wind blow past it. Play with the gain and clipping a
>>> bit and you get a nice collection of white noise (amplitude).
>>
>>This has almost 0 entropy. What sounds random to humans very often isn't.
>>The wind has a strong bias to continue to blow at close to the same rate
>>from the same direction, and the turbulence are highly predictable.
>>
>Put an oscilloscope on a microphone, and turn the gain way up. I
>don't know where you come from, but the wind is EXTREMELY inconstant
>at the 100ths meter/s leverl - there are micro variations in speed,
>density, and humidity (ask any meteorologist .. it really mucks up the
>stats.). An anemometer wont pick it up, but something very sensitive
>to velocity does .. which is why all wind measurements are averages.
And that average is non-zero usually and consistant. This morning for an hour the
wind here was about 60km/hr. Now it is about 10. Huge long time correlations in
the wind. Those will produce huge long term correlations in the ouput of that
microphone.
>>> If you're really fancy and handy with electronics, point a telescope
>>> at a star and figure out a way to capture the dance as the atmosphere
>>> moves the the image around. There's not a lot short of quantum
>>> mechanics that is more random than those little atmospheric
>>> microdisturbances - you're looking thru 100 miles of progressively
>>> thinning thermally randomized wiggling air.
>>
>>You're also looking at the same air as the attacker, the level of entropy is
>>effectively 0.
>>
>You are obviously not an astronomer. Two scopes side by side looking
>at the same star will see completely different variations. And they
No they will not. Some of the variation will be different some similar. There are
correlations in the density fluctuations in the atmosphere(which produce the star
fluctuations)-- some very long range, some short down to about a metre.
>change millisecond by millisecond. Unless my 'attacker" is looking
>through MY scope at MY star, I absolutely guarantee they will not see
>the variations in position and intensity that I do. I also guarantee
>that its thermally random and collecting a nice set of those
>variations would make a nifty one time pad. Atmospheric
>microdistortions do not repeat - even a little.
>>That's the problem, things that seem random, very often have little entropy.
>> Joe
>The atmosphere is the definitive random environment - even measuring
>temperature to the nearest 1/100 degree 100x/sec should return
>variations. People don't realize how 'lumpy' air is. But ask an
>astronomer looking thru a column of air a foot wide and 100 miles
>long, or for that matter, a qualified sniper, looking through an air
>column a mile long and 6 inches wide. There is a lot of variation,
>and it is all (repeat all) driven by thermal effects. Get the sample
>rate and resolution high enough, and thermal is driven by quantum
>level effects and randomness.
Hardly. The atmosphere has some fluctuations but it is clear that if the density
here is 1.4001kg/m^3 the density where you are 10m away will also be 1.4001kg/m^3.
Yes, there will be fluctuations around that at both places, some correlated, some
uncorrelated.
Spinner
Why cant they be plastic both? Second, I dont need infinite. If i
draw a ball and its white, i put a white one in the pool for the next
draw. If black, same with black. After i've drawn say 100 balls, i
put them all back in the pool and start the draw again.
I repeat, on every drop of the gate to select a ball, there are 100 in
the pool, 50 of each. Sorry but basic math says if my initial
conditions are precisely the same (50/50) each time then the odds of a
result are also the same.
Example: 1pm 100 balls, 50 each. Draw one.
Look at ball. Ball is white. Write that down. Put white ball in pool
2pm. Draw a ball. Note that still 100 balls, 50 of each. Odds of
any given color is the same at 2pm as it was at 1 pm.
>
>>>> And if you want simple random noise, put an unshielded microphone on a
>>>> stick and let the wind blow past it. Play with the gain and clipping a
>>>> bit and you get a nice collection of white noise (amplitude).
>>>
>>>This has almost 0 entropy. What sounds random to humans very often isn't.
>>>The wind has a strong bias to continue to blow at close to the same rate
>>>from the same direction, and the turbulence are highly predictable.
>>>
>>Put an oscilloscope on a microphone, and turn the gain way up. I
>>don't know where you come from, but the wind is EXTREMELY inconstant
>>at the 100ths meter/s leverl - there are micro variations in speed,
>>density, and humidity (ask any meteorologist .. it really mucks up the
>>stats.). An anemometer wont pick it up, but something very sensitive
>>to velocity does .. which is why all wind measurements are averages.
>
>And that average is non-zero usually and consistant. This morning for an hour the
>wind here was about 60km/hr. Now it is about 10. Huge long time correlations in
>the wind. Those will produce huge long term correlations in the ouput of that
>microphone.
>
Buy a microphone, hook it up. Put the output on a scope. You will see
a LOT of high frequency noise that is essentially random. The low
frequency noise (wind speed) you just ignore. I have seen it (try to
record something quiet on a breezy day with an unshielded mic.)
Wrong. The density in an air column 3 inches wide and 50 miles long
varies GREATLY - and you are looking through the sum of every single
density, wind, humidity and temperature permutation in that entire
column. You are telling me that an adjacent column (say 100 meters
away - we can probably keep our spy that far off) has precisely the
same characteristics as mine? Thats completely absurd. Star
distortion has high and low frequency components, and if the star
covers more than a couple ccd cells, you get a nice wiggly output
which, if not random (it is) is certainly unrepeatable (it is by
definition changing as the earth rotates and the atmosphere heats up
if nothing else). An unpredictable and non-repeating sequence will
work fine as random. Record two hours of star wiggle on two nights.
Now record 2 hours the third night. Take 3 of the 4 hours of data, and
use the algorithm of your choice to predict what the last hour will
look like. Thats what it would take to 'break' a one time pad based
on twinkle, the ability to predict the fourth section of key (noise)
based on any random collection of prior bits If you can't .. then
it's random isnt it?
The name of the game is random (unpredictable) sequences. There is no
"bias" in tuesday nights 3" x 50 mile air column that will let you
predict any part of wednesday night's column.
Don't confuse unpredictability with randomness. Pi is extremely
predictable, and any given sequence of digits meets the requirement
for randomness at the same time.. unless you happen to know it's Pi.
Star twinkle, wind noise may not be random, but they are most
certainly unpredictable.. and thats what you want for a key, something
that no amount of prior key gives you any hint as to what the next bit
is.
Unruh
>Unruh <unruh...@physics.ubc.ca> wrote:
I am pointing out that, contrary to what was said, the large number of
balls does not cancel out all biases.
>draw a ball and its white, i put a white one in the pool for the next
>draw. If black, same with black. After i've drawn say 100 balls, i
>put them all back in the pool and start the draw again.
>I repeat, on every drop of the gate to select a ball, there are 100 in
>the pool, 50 of each. Sorry but basic math says if my initial
>conditions are precisely the same (50/50) each time then the odds of a
>result are also the same.
>Example: 1pm 100 balls, 50 each. Draw one.
Black balls are different from white. that difference can make them more
readily fall down the chute.
>Look at ball. Ball is white. Write that down. Put white ball in pool
>2pm. Draw a ball. Note that still 100 balls, 50 of each. Odds of
>any given color is the same at 2pm as it was at 1 pm.
Not necessarily. It depends on how you draw them. For example if I look
intothe bag and always pick out a black ball, I always get black balls.
The process of picking need not be agnostic about the colour of the
ball, either through user procedure or through mechanical
characteristics. And just because I have 100 balls that does not change
this fact.
>>
>>>>> And if you want simple random noise, put an unshielded microphone on a
>>>>> stick and let the wind blow past it. Play with the gain and clipping a
>>>>> bit and you get a nice collection of white noise (amplitude).
>>>>
>>>>This has almost 0 entropy. What sounds random to humans very often isn't.
>>>>The wind has a strong bias to continue to blow at close to the same rate
>>>>from the same direction, and the turbulence are highly predictable.
>>>>
>>>Put an oscilloscope on a microphone, and turn the gain way up. I
>>>don't know where you come from, but the wind is EXTREMELY inconstant
>>>at the 100ths meter/s leverl - there are micro variations in speed,
>>>density, and humidity (ask any meteorologist .. it really mucks up the
>>>stats.). An anemometer wont pick it up, but something very sensitive
>>>to velocity does .. which is why all wind measurements are averages.
>>
>>And that average is non-zero usually and consistant. This morning for an hour the
>>wind here was about 60km/hr. Now it is about 10. Huge long time correlations in
>>the wind. Those will produce huge long term correlations in the ouput of that
>>microphone.
>>
>Buy a microphone, hook it up. Put the output on a scope. You will see
>a LOT of high frequency noise that is essentially random. The low
>frequency noise (wind speed) you just ignore. I have seen it (try to
>record something quiet on a breezy day with an unshielded mic.)
Of course I have seen it. Now do a correlation analyisis ( a simply
first order correlation functions Sum_t S(t) S(t+delta t). and do a
fourier analysis. While it probably falls off at higher frequencies, it
does not go to zero.) There are other higher order correlations as well.
Sorry, but it does not very "greatly" unless you call 1/100 of a percent
"greatly"
>density, wind, humidity and temperature permutation in that entire
>column. You are telling me that an adjacent column (say 100 meters
And averaging over them. Also almost all of the important fluctuations
occur in the first 10m. that is why telescope domes these days are high.
This was discovered by accident when the CFH Telescope was built. It had
a high base ( cannot remember why) and they found that the atmospheric
fluctuations were far lower than expected. They had before then thought
that the fluctuations were due to the whole air column but discovered
and understood that they were primarily due to turbulence induced by the
interaction between the wind and the ground, and fall of relatively
rapidly with height.
>away - we can probably keep our spy that far off) has precisely the
>same characteristics as mine? Thats completely absurd. Star
>distortion has high and low frequency components, and if the star
>covers more than a couple ccd cells, you get a nice wiggly output
>which, if not random (it is) is certainly unrepeatable (it is by
>definition changing as the earth rotates and the atmosphere heats up
>if nothing else). An unpredictable and non-repeating sequence will
>work fine as random. Record two hours of star wiggle on two nights.
>Now record 2 hours the third night. Take 3 of the 4 hours of data, and
>use the algorithm of your choice to predict what the last hour will
>look like. Thats what it would take to 'break' a one time pad based
>on twinkle, the ability to predict the fourth section of key (noise)
>based on any random collection of prior bits If you can't .. then
>it's random isnt it?
And there are many features I could predict of those sequences. Yes,
there are unpredictable portions. you have to be careful because there
are correlations especially within any one of those sequences. You would
be ill advised to use one of those sequences raw as you cryptographic
pad. Now if you took say 100 bytes and hashed them down to 16 bytes, you
would probably be OK. Ie, there is probably more than 16 bytes of
randomness in that 100 bytes of noise. However there probably is not 50
bytes worth.
>The name of the game is random (unpredictable) sequences. There is no
>"bias" in tuesday nights 3" x 50 mile air column that will let you
>predict any part of wednesday night's column.
Sure there is. A nice high pressure system settles over your telescope
located on a snow field and the wind drops to 2mph, your "randomness"
will drop precipitously.
>Don't confuse unpredictability with randomness. Pi is extremely
>predictable, and any given sequence of digits meets the requirement
>for randomness at the same time.. unless you happen to know it's Pi.
>Star twinkle, wind noise may not be random, but they are most
>certainly unpredictable.. and thats what you want for a key, something
>that no amount of prior key gives you any hint as to what the next bit
>is.
And again, wind noise has a predictable component.
Mok-Kong Shen
> I use electronic generators (eg /dev/urandom) which are much much much
> better than any mechanical generator. But then I have said this before,
> and have not had any impact on you.
I did mention the aspect of security. What if your computer had
a Trojan or such stuff?
M. K. Shen
Mok-Kong Shen
> Hm. I wonder why the casinos do not allow you to use your own dice.
> After all there are hundreds of dice throws. Should all average out even
> if you are using a loaded dice! Must just be ornariness on their part.
You ignored also the context. What I mean is a device that is mass
fabricated and not specially produced in a couple of numbers (unless
you manufacture one for your own crypto use, but then you wouldn't
intentionally do adverse manipulations). So there is no incentive of
the manufacturer to make 'loaded' balls. Anyway, a 'loaded' ball
does not have in our case the same effect as a loaded die. For a die
'lands' on one face, while a ball in the device I described 'rolls' into
the channel.
As an aside, I mentioned about SMS needing privacy protection. There
are apparently products on the market for spying on mobile phone
communications. I saw a web site
http://www.flexispy.com/products_flexispy_pro.htm
Does anyone know of their performance in practice (and what are the
defenses against them)?
M. K. Shen
Spinner
I only need a few balls (just to keep things easier) half white half
black in a box. Open the gate, shake the box, ball falls out into a
glass. How in hell can there be "bias" if each ball is exactly the
same.
Plus nobody said the large number of balls has a a damn thing to do
with anything -- you seem to have a fixation on quantity. All that
matters is the initial conditions being the same. You only need TWO
balls .. reach into the bag with your eyes closed and pick one. Now
put it back. Now do it again. I guarantee the odds of getting any
given color is exactly the same both times. Or a trillion balls. It
doesnt matter, just as long as you put back the one you took out to
return the sytem to its original state.
You are obviously not getting the simple point that restoring any
system to its original state also returns any of your so called biases
to that state - there is on accumulation of bias or anything else.
Example: coin. flip coin. read side. flip again. same chances each
time (including bias of person flipping) and condition.. the point is
the NUMBER of flips has nothing to do with the result. Neither does
the number of ball extractions as long as you keep putting the
extracted ball back. This is basic statistics 101.
Another simple mechanical generator is a bag of coins. Shake and drop
contents on a domed object (big enough to make them bounce.) Now,
count head and tails (any sequence you like). Tada.. nice collection
of random 1s and 0s. Especially if you dont look first and just
randomly pick what order you push coins out of the pile on the floor
to look at. To repeat and get more, you put the coins in the bag,
and do it again. Please note, this device works equally well with one
coin in the bag, or a trillion. Its just a lot more work at either
extreme. The number of coins has nothing whatsoever to do with the
randomness of the result, or its "entropy".
Unruh
>Unruh wrote:
they you are screwed anyway, the computer can read the key you type in on that
computer.
>M. K. Shen
Mok-Kong Shen
> Mok-Kong Shen writes:
>> I did mention the aspect of security. What if your computer had
>> a Trojan or such stuff?
>
> they you are screwed anyway, the computer can read the key you type in on that
> computer.
You may use the bits from the mechnical device (without using
your PC) and use them e.g. for encrypting your SMS (assuming
you have AES on your mobile phone), no?
M. K. Shen
Maaartin
> Unruh <unruh-s...@physics.ubc.ca> wrote:
>
> I only need a few balls (just to keep things easier) half white half
> black in a box. Open the gate, shake the box, ball falls out into a
> glass. How in hell can there be "bias" if each ball is exactly the
> same.
What use of drawing one of identical balls?
Or can you tell apart one ball from another when they're exactly the
same?
Or are they not because you painted them in different colors?
But then, what about the weight and friction etc. of the colors?
There may surely be a small bias. OTOH you probably get more than
0.999 bits per ball, so it's fine if used correctly.
> Another simple mechanical generator is a bag of coins. Shake and drop
> contents on a domed object (big enough to make them bounce.) Now,
> count head and tails (any sequence you like). Tada.. nice collection
> of random 1s and 0s. Especially if you dont look first and just
> randomly pick what order you push coins out of the pile on the floor
> to look at. To repeat and get more, you put the coins in the bag,
> and do it again. Please note, this device works equally well with one
> coin in the bag, or a trillion. Its just a lot more work at either
Having a bag with one trillion coins would make me work less not more,
at least for a while (I think I could use some holiday). Probably even
if the coins were the smallest units of the most inferior currency.
Sure, carrying the bag could be quite hard. :D:D
Bernhard Kuemel
> Hi,
>
> In sci.crypt.random-numbers I recently expressed my humble opinion
> that for a 'normal' (average) user of security software -- who is
> likely to be a layman in cryptology and also not very knowledgeable
> in hardware/software to be in a position of always doing technically
> correctly in the diverse procedures proposed or available for
> collecting random bits from computer hardware and similar sources
> of 'natural' randomness --
There are not many ways I can imagine someone doing technically incorrectly:
* Holding a key instead of hitting many keys. The key repeat events
should be easily detected and ignored by the software.
* Not hitting any keys or not moving the mouse at all.
Software can be communicate the error to the user and any user who would
otherwise use mechanical devices to generate entropy should have the
physical and intellectual capabilities to either hit keys or move the mouse.
> it seems to be desirable, if some simple
> and easy to handle mechanical devices be available for rapidly
> and conveniently generating small amounts of good quality random
> bits as may be needed e.g. as keys or initialization vectors for
> encryption algorithms.
I doubt the required entropy will be produced quicker, easier or more
reliable if a layman used such simple mechanical devices.
Or do you mean a layman might want to resort to mechanical RNGs because
he does not trust the computers RNG? A realistic situation. But I can
hardly imagine a software author implementing a user interface asking
for some random numbers instead of just asking for some random key
strokes or mouse movements.
Rather I believe in 5-10 years most PCs will have a built in hardware
RNG. They are dirt cheap to produce. A simple avalanche diode can make
noise up to hundreds of MHz. Slower hardware RNGs can be expanded to
faster and secure random streams by software. Then there will be no more
asking for numbers, keystrokes or mouse movements.
If a layman worries about weak random numbers nowadays he should also
worry about other flaws in crypto software and other ways to break security.
Bernhard
Unruh
REcent ( last 5 years or so) Intel cpus already have a hardware random
number generator on the cpu AFAIK. It tends not to get used.
Mok-Kong Shen
> REcent ( last 5 years or so) Intel cpus already have a hardware random
> number generator on the cpu AFAIK. It tends not to get used.
Do you know why it tends not to get used?
Thanks,
M. K. Shen
Mok-Kong Shen
> Mok-Kong Shen wrote:
If I understand you correctly, you favour collecting randomness
through user's typing on keyboard or mouse movements. I don't know
what's exactly with mouse movements, but in the case of keystrokes
I guess that the randomness might be questionable. My thinking on
this comes from the fact that typing on keyboard could be employed
to identify a user. There is namely a German software named Psylock,
developed by D. Bartmann, that does this through asking the user
to type in some text and it can even improve its performance with
experience. It is reported to work well e.g. in a case for enabling
students to automatically regain access to campus computers if
they forget their passwords. (Source: Staat & IT, 10.6.2009).
> If a layman worries about weak random numbers nowadays he should also
> worry about other flaws in crypto software and other ways to break security.
Being a layman, I have accordingly initiated in sci.crypt a thread
entitled "Security of crypto security measures". I should appreciate
it very much, if you would kindly give your valued comments there.
Thanks,
M. K. Shen
Mok-Kong Shen
If my memory is right, several years ago in sci.crypt somebody hinted
in this connection at the possibility of the hardware being bugged.
The old unsettled rumour about bugging by a prominent crypto machine
company of their own products apparently also affected the psychology
of people having skeptism on that topic. I am not sure that the state
of affairs has principally changed now.
M. K. Shen
Bernhard Kuemel
> If I understand you correctly, you favour collecting randomness
> through user's typing on keyboard or mouse movements.
I favor in order:
0) a combination of the following (such as /dev/random)
1) a dedicated, and hopefully trusted hardware RNG
2) various random events in a computer such as fluctiations in hard disk
head positioning and rotational speed, network traffic, drift of
independend timers, webcam, microphone, etc.
3) user input (keyboard, mouse, webcam, microphone)
4) If there is not enough entropy a cryptographically secure
pseudorandom number generator such as /dev/urandom or Fortuna.
> I don't know
> what's exactly with mouse movements, but in the case of keystrokes
> I guess that the randomness might be questionable. My thinking on
> this comes from the fact that typing on keyboard could be employed
> to identify a user.
Users do have individual typing patterns. But what we are focusing on
here are the random fluctuations in these patterns. The human body is a
very complex system and it is impossible to predict the exact delays
between keystrokes. Even if someone tried to repeat a key at a very
constant rate, the fluctuations would still be greater than the
resolution with which the computer can measure the delays (micro oder
nanoseconds). Say, the fluctuations are at least 10ms and the computer
measures key stroke delays with microsecond resolution then every key
stroke yields about log_2(10e-3/1e-6)=13 random bits. I just typed 147
keys in 10s, which, if my figures are correct, are 1911 random bits -
with no further hardware or reading and entering numbers. Just fiddling
with the keyboard.
How much work and time does a mechanical device method take? 50 or 100
bits in one run through shaking and entering 6 to 25 numbers? Do that 19
(or 38?) times to get 1900 bits. I prefer the keyboard fiddling for 10s.
>> If a layman worries about weak random numbers nowadays he should also
>> worry about other flaws in crypto software and other ways to break
>> security.
>
> Being a layman, I have accordingly initiated in sci.crypt a thread
> entitled "Security of crypto security measures". I should appreciate
> it very much, if you would kindly give your valued comments there.
I'm not a crypto expert. Searching the web will sure give you some
results. Flaws in crypto implementation, hard/software keyloggers, legal
or illegal force, spying out passwords with eyes or cameras, monitor or
keyboard radiation, brute force, dictionary attacks, social engineering,
phishing, written down passwords, same password for different
applications, transmitting clear text passwords over the internet,
passwords in swap, ... Passwords/keys in memory can sometimes be read,
if they are stored in the same location long enough, even after the
memory is erased or powered down for some time. If memory is cooled down
(e.g. with dry ice or liquid nitrogen) the remnants of the content may
be readable longer (2 weeks?).
Bernhard
Mok-Kong Shen
> ........... I just typed 147
> keys in 10s, which, if my figures are correct, are 1911 random bits -
> with no further hardware or reading and entering numbers. Just fiddling
> with the keyboard.
Fine. If you are of this opinion, I wonder why you would still consider
all the other types of obtaining randomness with hardware in the context
I mentioned, namely for use as keys and/or IVs, where not much quantity
of bits are required each time by the user.
M. K. Shen
Bernhard Kuemel
Keyboard fiddling might be ok for some users, even though it might be a
little awkward if your web browser asked you to fiddle the keyboard a
little every time it makes an https connection. But there are more
occasions where randomness is used. Even non encrypted TCP connections
use random sequence numbers to prevent malicious packets to be injected
by another computer. While /dev/random collects and accumulates
randomness from every key stroke (I believe) of normal user input so
they don't have to fiddle the keyboard extra for IV/key generation,
there are servers that need a lot of randomness and don't have a
keyboard or mouse and a user sitting in front of them at all. Think of
your banks internet banking servers which need to make a lot of https
TCP connections. So /dev/random collects whatever randomness it can get
and since this often does not suffice, there is /dev/urandom.
Bernhard
Mok-Kong Shen
I was not questioning on the diverse usages of randomness. I was
questioning whether the 1911 bits that you generate in 10s are to be
considered sufficiciently random. Certainly the requirements of
different applications may be different. On the other hand, I suppose
flipping coins and throwing dice (disregarding efficiency issue) are
generally considered to be acceptable for usages of interest to readers
of sci.crypt. I very much doubt that your suggestion of employing typing
in your way (each keystroke of yours resulted in 13 random bits!!)
would be considered satisfactory by the majority of the readers in the
group.
M. K. Shen
Bernhard Kuemel
> I was not questioning on the diverse usages of randomness. I was
> questioning whether the 1911 bits that you generate in 10s are to be
> considered sufficiciently random.
I can't find your post containing this question. But I'll try to answer
it anyways.
> Certainly the requirements of
> different applications may be different. On the other hand, I suppose
> flipping coins and throwing dice (disregarding efficiency issue) are
> generally considered to be acceptable for usages of interest to readers
> of sci.crypt. I very much doubt that your suggestion of employing typing
> in your way (each keystroke of yours resulted in 13 random bits!!)
> would be considered satisfactory by the majority of the readers in the
> group.
Let's start with a simplified example. Say we have a random variable, be
it the time between events. Say, it takes random values from 0ms and
100ms. We measure the intervals with ms resolution. We will not be able
to predict bit 0 since there is no preference of even or odd intervals
as measured in ms. The same is true for intervals measured in 2ms
resolution. Still true for 4ms resolution. This goes on until at 64ms
resolution bit 6 has a bias towards 0 as there are 64 possibilities for
it to be 0 and only 36 to be 1. All higher bits are always 0. Actually
some lower bits are also biased towards 0 because 100 is not a multiple
of their respective resolution, but the bias gets lower the lower the
bit is. log_2(100)=6,6 and we have 7 random bits (0-6) where bit 6 has a
serious bias.
Or a more practical approach: Take a 20 bit (bits 0-19) timer running at
1us resolution. The bits are connected to LEDs. Your goal is to halt the
timer with a key with as many LEDs lit as possible. Easy for bit 19 - it
changes only every 524ms. Still no big problem with bit 18 - 262ms. Bit
17 - 131ms - may be doable with some practice, but the lower 17 bits are
pretty much out of your control. They are random.
Fiddling the keyboard is more complex. There are different speeds and
patterns. Someone might manage to press 30 keys almost simultaneously
(and have a keyboard which can detect that) and repeat that 3 times per
second. There will be little time between keystrokes and consequently
the timer reaches lower values which translates to fewer bits/key.
Someone trying to move all his fingers randomly will yield very
different intervals, short and long which gives much randomness. Someone
hitting only a single key might do so very regularly and if he did that
perfectly (as might be the case if a key was repeated automatically)
that might get the timer to use a good number of bits each time, but
they would be all equal each time and thus contain no randomness at all.
Unless someone used smart algorithms to evaluate typing patterns it
would be wise to assign conservative amounts of randomness to each key
event.
One way might be:
Measure the time between keystrokes.
Discard leading zeros and the highest 1 bit (since that's always 1).
Only use the bits that are needed to count to about 10ms. This should
discard any bits that might be influenced by regular typing patterns
(extreme example: hitting a key every 10s).
This translates pretty much to the same 13 bits/key as in my previous
post. It appears, though, that /dev/random takes only about 2.3 bits/key.
I hope this is of any help.
Bernhard
Mok-Kong Shen
> Mok-Kong Shen wrote:
>> I was not questioning on the diverse usages of randomness. I was
>> questioning whether the 1911 bits that you generate in 10s are to be
>> considered sufficiciently random.
>
> I can't find your post containing this question. But I'll try to answer
> it anyways.
Sorry, you wrote quite a lot, but I am afraid we yet misunderstood each
other in essential points. I wrote:
If I understand you correctly, you favour collecting randomness
through user's typing on keyboard or mouse movements. I don't know
what's exactly with mouse movements, but in the case of keystrokes
I guess that the randomness might be questionable. My thinking on
this comes from the fact that typing on keyboard could be employed
to identify a user.
You countered this with:
I just typed 147 keys in 10s, which, if my figures are correct, are
1911 random bits - with no further hardware or reading and entering
numbers. Just fiddling with the keyboard.
and further:
Keyboard fiddling might be ok for some users, even though it might
be a little awkward if your web browser asked you to fiddle the
keyboard a little every time it makes an https connection.
Don't these together mean that you do think that it is possible that
someone (and you in particular) can generate good quality random bits
at the rate of 13 bits per keystroke?
M. K. Shen
Bernhard Kuemel
> Don't these together mean that you do think that it is possible that
> someone (and you in particular) can generate good quality random bits
> at the rate of 13 bits per keystroke?
Yes. Under favorable conditions (slow typing) even more, see the example
with the 20 bit counter with LEDs. Any objections?
Bernhard
Mok-Kong Shen
Sorry, I simply can't believe that anybody with a single keystroke
could give rise to 13 or 20 bits of entropy. Sorry.
M. K. Shen
robert...@yahoo.com
It's the *timing* of the single keystroke that yields a bunch of
entropy, not what's typed.
Bernhard Kuemel
It's better to know, than to believe, especially in cryptography. Maybe
you can understand it this way:
Say you have a RNG which gives you numbers from 0-7. You can translate
these numbers to 3 random bits. Now, I haven't told you, how you get the
numbers from the RNG. It produces a random voltage in the range of 0-8V.
You measure the voltage and assign each interval of 1V to a number from
0-7. Now you could also use 16 intervals of 0.5 V. This way you can get
4 bits. If you use 0.25 V intervals you get 5 bits, and so on. The finer
your resolution, the more bits you get per sample. A sound card can
digitize voltage 48000 times per second with 16 bit resolution.
Now instead of digitizing a random analog voltage you could also
digitize a random analog time interval between key strokes. Take a 3 bit
timer with 1 us resolution. If there is no keystroke within 8 us just
restart the timer. Typically the timer will restart many times until
suddenly there comes a key stroke and tada, you have 3 bits. Are they
random? Well, of course humans typically don't hit a keyboard randomly.
Mostly they intentionally type text and have individual typing
patterns. But if you analyze the timings between each two consecutive
characters of the same word, you will find that they are not constant,
but fluctuating. I have written the (lower case) word 'the' several
times now. The timing between the keys t and h in the word 'the' is not
constant, but fluctuating. The range might be something like 35-45 ms
[1] (on my dvorak keyboard t and h are next to each other and very easy
and quickly to type.) No matter how hard I try, it just won't be
constant. I am not intentionally controlling these fluctuations. They
are influenced by my inherent imprecision, how tired I am, how
distracted I am by thinking, etc. Really, my body has a huge state (as
compared to the internal state of a pseudo RNG) and quite likely there
are lots of absolutely random quantum events going on as well (which
probably contribute to human creativity, free will, etc.). Now this 10
ms fluctuation (of the 35-45 ms range between t and h) is random.
[1]
Incidentally I have written a stopwatch program that displays timings
between keystrokes. It shows quite consistently 28, 29, 56, 57 *or* 58
ms. So in this case the resolution is not 1us but rather something like
28 ms. That might depend on the way the program measures time, task
switching or the keyboard sending the key strokes. With some refinement
it might be possible to get better resolution (e.g. taking a higher
resolution time in the kernel interrupt receiving the key strokes). But
maybe this is not done or possible in my case and that's one of the
reasons why my /dev/random accumulates only about 2.3 bits/keystroke.
Mok-Kong Shen
I was simply astonished about the extraordinary large rate of the
entropy generation he claimed to be achievable with his methodology.
Much like I would greatly wonder, if a researcher in agriculture
would claim that he had succeeded to grow apples each weighing more
than 3 kg. I don't know, but maybe indeed nothing is impossible under
the sun :-)
M. K. Shen
Bernhard Kuemel
It's better to know, than to believe, especially in cryptography. Maybe
ms fluctuation (of the 35-45 ms range between t and h) is random. The 3
bit timer will restart every 8 us and stop at a random time somewhere
between 35,000 us and 45,000 us. There is probably a bell shaped
distribution of the probability of the time when h is pressed after t.
That is, it will be more likely to be 40,000 us and less likely 35,000
us or 45,000 us. But even if the probability is not the same for all
values, there are a lot of even and odd numbers among the more likely
values and so bit 0 (which decides about even or odd) is random. There
are also very many intervals of 2 us where bit 1 is alternatingly off or
on. One will be picked randomly. This goes on for several bits. Bit 10
changes every 1024 us or about 10 times in the 10,000 us range. It can
be considered a pretty good random bit.
But eventually the intervals in which higher order bits remain constant
will be large enough so there are very few of them in the 10,000 us
range where the timer will be stopped. The chance for a bit to be on or
off will no longer be equal. Bit 13 changes every 8192 us. If the center
of the probability bell curve where at 8192*5=40960 then bit 13 would be
random. It would be on or off depending if the timer was stopped before
or after 40960 us. But if the 10,000 us range were to be centered around
a 8192 us "on" interval then there would be 8192 timer values where the
bit came out "on" while the remaining 1808 values which are not only
fewer but also less likely would mean a much lower probability for bit
13 to be "off". So bit 13 will likely have a significant bias. Even
higher order bits will mostly be constant and only change with very
unusual keystroke timings.
If the fluctuations in keystroke timing are higher, then you can get a
few more bits per keystroke, or less, if they are smaller. Also, a
faster timer will yield more bits.
Bernhard
[1]
Incidentally I have written a stopwatch program that displays timings
between keystrokes. It shows quite consistently 28, 29, 56, 57 *or* 58
ms if I type 'th'. So in this case the resolution is not 1us but rather
Mok-Kong Shen
That seems all highly magnificent, though I personally couldn't
believe that in 10 seconds one could via keystroke generate 1911 bits
of entropy. As I said, if this is so, then one wouldn't have to bother
to consider other means of getting entropy, which, very interestingly,
you yourself also die consider in the posts. (I questioned in a post
why you nonetheless consider these.)
I suppose that you know that one has since long time employed
radioactive decay to get entropy for, among others, the onetime pads,
which have importance in certain classes of encryptions. Now your
technology, if indeed it had a performance as you claimed, would
evidently be highly economically competitive to such alternatives.
And maybe you could even have, through an appropriate formulation
of your theoretical and technical reasoning, applied for a European
patent (an office site in Germany is in Munich). Try and do this and
let people of the groups admire/astonish your success! Meanwhile I,
as layman, continue to stubbonly mistrust your feat just like I wrote
in the other post that I wouldn't trust an (hypothetical) argricultural
researcher who claim to be able to grow apples heavier than 3 kg each
(even though I know that the genetic engineering is extremely
performant).
M. K. Shen
--------------------------------------------
P.S. In order to conserve bandwidth of the groups, this is the last post
from me as far as your extremely spectacular entropy generation
technology is concerned.
Spinner
Gimme a break a and stop being a troll. You know what he meant, so be
civil.
Imagine a 1GHz counter thats 20 bits wide. run the counter. stop the
counter when i hit a key. Lots of entropy here based on interval.
(since it resets every millisecond.. you cant get two 'numbers' out of
any single cycle).
Spinner
robert...@yahoo.com
It’s trivial to get nanosecond-scale resolution timings on many
processors. On (semi-modern) x86, for example, you can read the time
stamp counter, which basically gives you a 64 bit number of clock
ticks since the CPU was powered on. So on a 2GHz process, each count
is half a nanosecond.
Simply looking at the low bits of that time captures a great deal of
randomness in the jitter between the arrival of the keystrokes.
While there are some possible objections to using _getch() (you really
want as low level a function as possible to avoid any biasing from the
OS’s processing of the stream – and we’d really need to have a
thorough look at the way keyboard input happens on a particular
machine), but consider the following for Windows:
#include <stdio.h>
int main(void)
{
int i;
for (i=0; i<50; i++)
{
_getch();
printf("%05x\n", (int)(__rdtsc() & 0xfffff));
}
return 0;
}
On a 1GHz processor each iteration would return the fraction of a
millisecond of the time of the keystroke, and is set up to return 20
bits per keystroke. You’d need to process this some before using it
(like any hardware source), but there’s clearly a lot of entropy
there.
robert...@yahoo.com
> Incidentally I have written a stopwatch program that displays timings
> between keystrokes. It shows quite consistently 28, 29, 56, 57 *or* 58
> ms if I type 'th'. So in this case the resolution is not 1us but rather
> something like 28 ms. That might depend on the way the program measures
> time, task switching or the keyboard sending the key strokes. With some
> refinement it might be possible to get better resolution (e.g. taking a
> higher resolution time in the kernel interrupt receiving the key
> strokes). But maybe this is not done or possible in my case and that's
> one of the reasons why my /dev/random accumulates only about 2.3
> bits/keystroke.
It sounds like you're using the wrong timer to measure the interval
between keystrokes. The 56/57/58 numbers sound like you may be
picking up something with timing based on the old DOS 18.2Hz timer,
the 28/29 sounds like half that for some reason. At least the former
were the defaults for all DOS, Win3.x and Win9x, and that effectively
show up in the output of GetTickCount(), and the like. In some cases,
you might be getting some biasing from the USB handling of the
keyboard.
Assuming we're talking about Windows, at least set up the resolution
of the interval timer with timeBeginePeriod(), but that won't do
better than millisecond resolution. Better to use a performance
counter or the time stamp counter.
Unruh
>On Nov 25, 4:23=A0am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>> robertwess...@yahoo.com wrote:
>> > Mok-Kong Shen wrote:
>> >> Bernhard Kuemel wrote:
>> >>> Mok-Kong Shen wrote:
>> >>>> Don't these together mean that you do think that it is possible that
>> >>>> someone (and you in particular) can generate good quality random bit=
>s
>> >>>> at the rate of 13 bits per keystroke?
>> >>> Yes. Under favorable conditions (slow typing) even more, see the exam=
>ple
>> >>> with the 20 bit counter with LEDs. Any objections?
>> >> Sorry, I simply can't believe that anybody with a single keystroke
>> >> could give rise to 13 or 20 bits of entropy. Sorry.
>>
>> > It's the *timing* of the single keystroke that yields a bunch of
>> > entropy, not what's typed.
>>
>> I was simply astonished about the extraordinary large rate of the
>> entropy generation he claimed to be achievable with his methodology.
>> Much like I would greatly wonder, if a researcher in agriculture
>> would claim that he had succeeded to grow apples each weighing more
>> than 3 kg. I don't know, but maybe indeed nothing is impossible under
>> the sun :-)
>It=92s trivial to get nanosecond-scale resolution timings on many
>processors. On (semi-modern) x86, for example, you can read the time
>stamp counter, which basically gives you a 64 bit number of clock
>ticks since the CPU was powered on. So on a 2GHz process, each count
>is half a nanosecond.
So what? That does not mean that that the system has nanosecond resolution. You
could put that time into a 128 byte word, and get a resolution of atoseconds. But
the reading of the clock does not give you that accuracy. Ie if you get nanosecond
resultion but the clock always gives 1 second accuracy, that extra 30 bits are
irrelevant and provide no extra entropy.
>Simply looking at the low bits of that time captures a great deal of
>randomness in the jitter between the arrival of the keystrokes.
No, because those low order bits could for example always be 0.
For example ntp uses the gettime function to return the time but then tests it and
usually on a good system finds that the times only have microsecond accuracy.
Those extra bits carry 0 entropy.
>While there are some possible objections to using _getch() (you really
>want as low level a function as possible to avoid any biasing from the
>OS=92s processing of the stream =96 and we=92d really need to have a
>thorough look at the way keyboard input happens on a particular
>machine), but consider the following for Windows:
>#include <stdio.h>
>int main(void)
>{
> int i;
> for (i=3D0; i<50; i++)
> {
> _getch();
> printf("%05x\n", (int)(__rdtsc() & 0xfffff));
> }
> return 0;
>}
>On a 1GHz processor each iteration would return the fraction of a
>millisecond of the time of the keystroke, and is set up to return 20
>bits per keystroke. You=92d need to process this some before using it
So what. Of those 20 bits only 2 could be relevant and carry any entropy.
>(like any hardware source), but there=92s clearly a lot of entropy
>there.
robert...@yahoo.com
Yes it does. On x86 the hardware timestamp counter is specifically
defined to be a count of the CPU's clock ticks. So a 1GHz processor
will increment the TSC on billion time each second. And it's
specifically defined *not* to do what you suggest, which is to add a
larger quantity at longer intervals.
It's actually a bit more complex than that. Back in the Pentium 4
days, it actually was one increment per CPU clock tick, and the
effective rate changed as CPUs changed frequency due to power saving
mode changes. This caused some problems, and more recent CPUs
increment the TSC at a constant rate, one that's approximately related
to the maximum frequency of the CPU (so a 2Ghz CPU that's throttled
down to 1GHz for power savings still has the TSC incrementing at
2GHz).
There some additional complexities when the CPU is halted or sleeping.
But for the purposes we're discussing, on a 1GHz CPU, the TSC
basically increments approximately one billion times per second.
> >Simply looking at the low bits of that time captures a great deal of
> >randomness in the jitter between the arrival of the keystrokes.
>
> No, because those low order bits could for example always be 0.
See above.
> For example ntp uses the gettime function to return the time but then tests it and
> usually on a good system finds that the times only have microsecond accuracy.
> Those extra bits carry 0 entropy.
And I specifically mentioned the TSC, and *not* the various OS
functions. gettimeofday(), GetTickCount() or similar almost never
provide that kind of resolution, and often produce considerable less
resolution than their nominal returned data type would suggest (for
example, Win3.x and Win9x often based all their timings on the 18.2Hz
DOS interval timer, leading to an effective resolution of about 55ms,
despite the result of GetTickCount() being defined in milliseconds).
Which is why I *didn't* suggest them.
On a semi-related subject, the CPU's clock tends to be fairly poorly
related to real time, and apparent errors of several percent are not
uncommon using the raw TSC values (IOW, the nominal 1GHz processor is
really running at some rate between .98 and 1.02GHz, with the same
effect on the number of TSC ticks per real second). This doesn't make
the TSC values impossible to use for real (aka wall clock) timing, but
does require a calibration/correction step.
Note that other CPUs have different schemes. For example S/370
defines a clock such that bit position 51 (counting from bit zero at
the high end, per S/370 conventions) increments once every microsecond
(thus providing a consistent time base), but the *actual* resolution
is always proportional to the CPU's instruction execution rate (thus a
1 MIPS CPU might actually increment bit position 51 1,000,000 times
per second, while a 500 MIPS CPU might increment bit position 60
512,000,000 times per second). PPC has a Time Base register whose
exact speed is not defined, but it increments at a modest multiple of
the CPU cycle time on all implementation (one TB increment for every
4-32 CPU clocks, or thereabouts). It also provides a mechanism for
the system to notify the OS when the TBs input frequency changes.
Gordon Burditt
>defined to be a count of the CPU's clock ticks. So a 1GHz processor
>will increment the TSC on billion time each second. And it's
>specifically defined *not* to do what you suggest, which is to add a
>larger quantity at longer intervals.
Does it really matter whether the counter on the PC is running at
1GHz, when the keyboard characters on an AT-style keyboard are
clocked in at a frequency more like 20-30KHz? A single character
(scan code) is 11 bits, although some keystrokes are more than one
character. (This may not be an issue on USB keyboards, or maybe
the arrival of characters is just linked to a clock that's a bit
faster.)
robert...@yahoo.com
A PS/2 style keyboard/mouse UART runs asynchronously from the CPU.
And you're measuring the nanosecond arrival of the keystroke at the
program, which depends on exactly when the key is hit by the user,
when the keystroke is sent by the keyboard, when the keystroke is
received by the UART, when the interrupt is received by the CPU, when
the keystroke is retrieved by the OS, and when the keystroke is
delivered to the application. At the ns level, there's a huge amount
of jitter.
Try the program I posted.
Bernhard Kuemel
> On Nov 25, 5:39 am, Bernhard Kuemel <bernh...@bksys.at> wrote:
>> Incidentally I have written a stopwatch program that displays timings
>> between keystrokes. It shows quite consistently 28, 29, 56, 57 *or* 58
>> ms if I type 'th'. So in this case the resolution is not 1us but rather
>> something like 28 ms. That might depend on the way the program measures
>> time, task switching or the keyboard sending the key strokes. With some
>> refinement it might be possible to get better resolution (e.g. taking a
>> higher resolution time in the kernel interrupt receiving the key
>> strokes). But maybe this is not done or possible in my case and that's
>> one of the reasons why my /dev/random accumulates only about 2.3
>> bits/keystroke.
>
>
> It sounds like you're using the wrong timer to measure the interval
> between keystrokes.
I use gettimeofday(&tv_t,NULL); on Linux. I could try ...
struct timespec {
long tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
"Some code calls select() with all three sets empty, nfds zero, and a
non-NULL timeout as a fairly portable way to sleep with subsecond
precision."
That would however be unsuitable for a stopwatch program. Because I want
to display the time elapsed since program start at every key stroke and
not only between 2 keystrokes.
But as I said, timing for randomness collection should be done in the
interrupt receiving the keystrokes to avoid time quantizations such as
task switching.
Bernhard
Maaartin
I'm afraid you're right. While using the RDTSC works good, the
hardware in the keyboard and in the ports (PS2, USB) and probably the
software make the resolution much worse. You loose most of the
information this way and maybe get some entropy from the jitter
between the CPU clock and the keyboard clock (or whatever).
You'd need a selfdesigned keyboard, maybe just one button wired to the
NMI (non-maskable interrupt) of the CPU or to some card having good
time resolution. Maybe using an old pentium for the button could be a
good solution, but you'd still need something for communication. I'd
have look at some microcontrollers (they have some build-in links and
timers as well).
robert...@yahoo.com
> robertwess...@yahoo.com wrote:
> > On Nov 25, 5:39 am, Bernhard Kuemel <bernh...@bksys.at> wrote:
> >> Incidentally I have written a stopwatch program that displays timings
> >> between keystrokes. It shows quite consistently 28, 29, 56, 57 *or* 58
> >> ms if I type 'th'. So in this case the resolution is not 1us but rather
> >> something like 28 ms. That might depend on the way the program measures
> >> time, task switching or the keyboard sending the key strokes. With some
> >> refinement it might be possible to get better resolution (e.g. taking a
> >> higher resolution time in the kernel interrupt receiving the key
> >> strokes). But maybe this is not done or possible in my case and that's
> >> one of the reasons why my /dev/random accumulates only about 2.3
> >> bits/keystroke.
>
> > It sounds like you're using the wrong timer to measure the interval
> > between keystrokes.
>
> I use gettimeofday(&tv_t,NULL); on Linux. I could try ...
>
> struct timespec {
> long tv_sec; /* seconds */
> long tv_nsec; /* nanoseconds */
> };
>
> "Some code calls select() with all three sets empty, nfds zero, and a
> non-NULL timeout as a fairly portable way to sleep with subsecond
> precision."
gettimeofday() and whatever goes into select(), will both typically be
driven off the interval timer, and will not resolve times less than
whatever that's set to. In some environments, that resolution can
change (Windows’s timeBeginPeriod(), for example).
> But as I said, timing for randomness collection should be done in the
> interrupt receiving the keystrokes to avoid time quantizations such as
> task switching.
Agreed. Using all (not just keyboard) interrupts, plus the local
equivalent of RDTSC, is commonly used as a main source for many OS's
random number generator (/dev/random, CryptGenRandom(), etc.). But
you can still do a useful job purely at the application level, it’s
just less efficient.