How to develop a random number generation device

[John Devereux]

On Sep 10, 10:55 am, John Devereux <[email protected]>
wrote:
[....]

They have, of course - not many people use C to write applications for
desktop machines any more. They use C#, java, all sorts of other
languages and frameworks that do most or all of what you are asking.

I disagree. Many programs today are written using MFC which ensures
that it is a hopeless morass of bugs.

Well yes (although that's C++, not C). And in fairness to Microsoft,
they have been trying to phase out MFC for the last 5 years. I was
making the point that people *have* been working on desktop
development systems designed to fix exactly the problems John Larkin
was complaining about.

 

[Archimedes' Lever]

It is *NOT* possible to calculate a random number sequence; any such
foolish attempt will result in a (perhaps long) repeating sequence.
Even a "short" (say 1-10%) sample of a loooong sequence will fail one
test of a truly random sequence of the same length.

Generate 25 separate psuedo-random numbers.

Then randomly add or subtract 5 randomly chosen results of that set of
them from each other. The result will be more random than anything you
get from a single generation sequence.

 

[ChairmanOfTheBored]

If you want random, start with (or re-seed from) a table of random
numbers, similar to what was used by the military ages ago.
Or..take a tested random process (eg: nuclear decay, brownian
motion), digitize that for either random values or a "lookup table".
Oh...you were asking about one of those tests?
Any given value can and will repeat - - - randomly!

A good test of that would be to examine whether ANY of the state
lotteries have generated a 6 pull number that matched a previous pull.

The odds are far higher that a pull would repeat than any good PR
generator.

Now see if they were pulled in the same order.

Likely in the 3+ billion to one realm there.

 

[Martin Brown]

Well, that's bad code. The point of coding in state machines, or at
least thinking in them, is that all possible cases are accounted for.

Sometimes you don't see the one that will get you. The only remaining
thread executing correctly maintained the watchdog timer. The main
program counter on a memory mapped register architecture had found
itself in ROM due to an electrical glitch. Another wierd one the RTI
instruction of a certain CPU didn't always do what it said on the tin.

Balanced loop paths are a lot easier to check for correctness. I was a
fan of Nassi Schniedermann diagrams once upon a time. Modern tools
would probably make them usuable today.

http://en.wikipedia.org/wiki/Nassi-Shneiderman_diagram

C doesn't encourage subroutines that have multiple entry and multiple
exit points. Pity.

It allows a bit too much jumping around to be healthy. And dropping
through in switch case statements.

I's occurred to me, more than once, that C was invented to run on a
PDP-11, and that a $400 Dell has 10,000 times the memory and a
thousand times the speed of an 11. So why doesn't somebody invent a
language (and a methodology) that produces/forces reliable code and
requires less debugging, and does rudimentary stuff like data and code
separation, at some expense in runtime resources?

It doesn't even need any expense of runtime resources. Any of the
strongly typed languages are capable of rigidly enforcing disciplined
engineering practices. Although some like Ada designed by committee
became so large and bloated that safety critical work tends to be done
in a verified and validated subset. The sad thing is you can still
write unmaintainable code in any language - you just have to try
harder in some of them.

McCabes CCI index provides a useful sanity check on the code
complexity. Basically if something is too complicated and like
spagetti then it will almost certainly harbour undetected bugs.

Nicklaus Wirths Modula-2 from ETH Zurich was about the simplest
minimalist strongly type language. There are static analysis tools for
it that can find certain classes of bugs without executing the code.

http://freepages.modula2.org/downl.html

A sort of Pascal with independent module compilation and rigidly
enforcable version checking. Logitech (the same one as is now famous
for popularising the mouse) were the original distributors of the ETH
M2 PC compiler which at the time came with an overlay manager, runtime
and post-mortem debugger that had features still not surpassed by
modern PC tools. Code generator was crude and archaic but then all PC
compilers were like that in the 80's. Provided you kept the the linker
map you could find the failing line of code and see events leading up
to failure.

Z & VDM have tried to do the same thing for formal software
specifications, with some success. But commercially code hacked out of
the solid and a ship it and be damned policy has unfortunately become
the norm

Regards,
Martin Brown

 

[John Larkin]

On Sep 10, 10:55 am, John Devereux <[email protected]>
wrote:
[....]

They have, of course - not many people use C to write applications for
desktop machines any more. They use C#, java, all sorts of other
languages and frameworks that do most or all of what you are asking.

I disagree. Many programs today are written using MFC which ensures
that it is a hopeless morass of bugs.

Well yes (although that's C++, not C). And in fairness to Microsoft,
they have been trying to phase out MFC for the last 5 years. I was
making the point that people *have* been working on desktop
development systems designed to fix exactly the problems John Larkin
was complaining about.

Cool. When can we expect buffer overrun exploits to be impossible
under Windows?

John

 

[John Larkin]

Generate 25 separate psuedo-random numbers.

Then randomly add or subtract 5 randomly chosen results of that set of
them from each other. The result will be more random than anything you
get from a single generation sequence.

Adding will change the probability distribution towards Gaussian.
XORing is better. Hell, XOR all 25 of them.

In a modest FPGA, one could do hundreds of long, say 256-bit,
pseudo-random shift registers of different sequence lengths. And it
would be easy to add some ring oscillators, or go out/in on pins to
make a lot of flakey one-shots, to garble the states of each of the
shift registers in an unpredictable way. The result would be as random
as anything gets.

John

 

[Vladimir Vassilevsky]

John Larkin wrote:

Adding will change the probability distribution towards Gaussian.
XORing is better. Hell, XOR all 25 of them.

In a modest FPGA, one could do hundreds of long, say 256-bit,
pseudo-random shift registers of different sequence lengths. And it
would be easy to add some ring oscillators, or go out/in on pins to
make a lot of flakey one-shots, to garble the states of each of the
shift registers in an unpredictable way. The result would be as random
as anything gets.

Utter nonsense. I won't even comment on that.

If you want the recipes for the good pseudorandom generators without
getting into much theory, go read Knuth or Schneier.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

 

[John Larkin]

John Larkin wrote:



Utter nonsense. I won't even comment on that.

There's probably a world of things you can't comment on.

John

 

[Vladimir Vassilevsky]

There's probably a world of things you can't comment on.

Certainly. I am not John Larkin.

VLV

 

[John Larkin]

Certainly. I am not John Larkin.

VLV

Google "Xilinx random number generator." There are lots of papers and
articles. Some first-page hits are...


ring oscillators:
https://www.cosic.esat.kuleuven.be/publications/article-790.pdf

using intrinsic jitter:
http://portal.acm.org/citation.cfm?id=968292

ring oscillators whacking LFSR's:
http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/prng_cdt07.pdf

pll jitter:
http://www.best.tuke.sk/simka/download/pub/fis_dru_sim_cel_04.pdf

very cool, colorful paper, ring oscillators again:
http://ece.gmu.edu/courses/Crypto_r.../Kohlbrenner/Kohlbrenner_Fall_2003_slides.pdf



I like the idea of making a one-shot by actively pulling a pin or pins
down, and using a weak pullup to pull it up, and timing how long it
takes to look high again. That, done right, will include enough
physical randomness to nicely scramble the state sequences of a long
(like, age of the universe) pseudo-random shift register. Do that a
few dozen times, add some ring oscillators, and mash up the results,
and it will be random.

John

 

[Nobody]

Cool. When can we expect buffer overrun exploits to be impossible
under Windows?

When it stops letting you run arbitrary machine code.

Nothing the OS does can prevent machine code from overrunning a buffer.
The only thing that the OS can do in this regard is to either restrict
what machine code you can run (e.g. cryptographic signing), and/or run
untrusted code in a heavily-restricted environment so that a buffer
overrun cannot be "exploited".

Given that:

a) this would make Windows totally incompatible with most existing
software, and
b) about the only thing that Windows has in its favour is the mass of
existing Windows software,

I don't expect this to happen any time soon.

 

[Vladimir Vassilevsky]

John Larkin wrote:

ring oscillators:
https://www.cosic.esat.kuleuven.be/publications/article-790.pdf

using intrinsic jitter:
http://portal.acm.org/citation.cfm?id=968292

ring oscillators whacking LFSR's:
http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/prng_cdt07.pdf

pll jitter:
http://www.best.tuke.sk/simka/download/pub/fis_dru_sim_cel_04.pdf

very cool, colorful paper, ring oscillators again:
http://ece.gmu.edu/courses/Crypto_r.../Kohlbrenner/Kohlbrenner_Fall_2003_slides.pdf

Amateurish stuff. They don't even bother with oscillators mode locking,
power supply influence and the statistical weakness of the higher
order. None of the attempts to prove anything theoretically either.

I like the idea of making a one-shot by actively pulling a pin or pins
down, and using a weak pullup to pull it up, and timing how long it
takes to look high again.

Been there, done that. One pin is basically a thermometer; several pins
are correlated to each other. There is some randomness though: may be a
few bits per minute.

That, done right, will include enough
physical randomness to nicely scramble the state sequences of a long
(like, age of the universe) pseudo-random shift register.

LSFR is extremely weak random generator regardless of the length. So is
a logical function or a multiplex of several LSFRs.

Do that a
few dozen times, add some ring oscillators, and mash up the results,
and it will be random.

The real question is how much dollars would you bet on that randomness.


VLV

 

[Nobody]

I like the idea of making a one-shot by actively pulling a pin or pins
down, and using a weak pullup to pull it up, and timing how long it
takes to look high again. That, done right, will include enough
physical randomness to nicely scramble the state sequences of a long
(like, age of the universe) pseudo-random shift register. Do that a
few dozen times, add some ring oscillators, and mash up the results,
and it will be random.

If you do it wrong, you could end up reducing the randomness rather than
increasing it. The result can easily be affected by the behaviour of the
chip (e.g. EMI, or the pull-down impedance being affected by the current
draw of nearby circuitry), causing a feedback loop which biases the RNG
towards certain states.

 

[John Devereux]

On Sep 10, 10:55 am, John Devereux <[email protected]>
wrote:
[....]
They have, of course - not many people use C to write applications for
desktop machines any more. They use C#, java, all sorts of other
languages and frameworks that do most or all of what you are asking.

I disagree. Many programs today are written using MFC which ensures
that it is a hopeless morass of bugs.

Well yes (although that's C++, not C). And in fairness to Microsoft,
they have been trying to phase out MFC for the last 5 years. I was
making the point that people *have* been working on desktop
development systems designed to fix exactly the problems John Larkin
was complaining about.

Cool. When can we expect buffer overrun exploits to be impossible
under Windows?

I still program in C and C++... but as I understand it C# and the
other .net languages run as "managed" code where buffer overrun
exploits should not be possible.

But if you still want to run your old software then buffer overruns
will continue to be a problem. Newer versions of windows limit the
amount of damage they can do. But vista doesn't work with the things I
would need to run on it.

 

[John Larkin]

When it stops letting you run arbitrary machine code.

Nothing the OS does can prevent machine code from overrunning a buffer.

Ancient computers, PDP-11 and VAX certainly, had memory management
hardware that separated I and D space, where I space was read-only,
and D space could not be executed. And the OS's enforced those rules.
It was common to have many users running the exact same code, but
mapped into different data spaces.

Problem is, neither Intel nor Microsoft was in the mainstream of
computing when they kluged up x86 and Windows.

John

 

[John Larkin]

John Larkin wrote:




Amateurish stuff. They don't even bother with oscillators mode locking,
power supply influence and the statistical weakness of the higher
order. None of the attempts to prove anything theoretically either.


Been there, done that. One pin is basically a thermometer; several pins
are correlated to each other. There is some randomness though: may be a
few bits per minute.



LSFR is extremely weak random generator regardless of the length. So is
a logical function or a multiplex of several LSFRs.

It's not weak if a randomizing process, applied *internally* to the
register (ie, xor some noise into its guts) causes it to hop all over
its state space randomly. In that case, there will be no un-boogered
sequences long enough to identify the nature of the register.

John

 

[John Fields]

I have many customers. Sometimes I conferr with them as regards
product performance or interface; I almost never discuss internal
design issues with them. Few of them ever see schematics or source
code.

---
I wasn't referring to the nitty-gritty of it, of which your clients
would certainly not be aware unless they asked for your design
documentation, I was referring to getting the widgets to do what
they're supposed to do within your contractual cost constraints.

For example, let's say that for $1M a hit you could guarantee that
one tenth of the ten million dollar fighters on which your equipment
was mounted wouldn't be shot down because of failures in your stuff,
but for $2M a hit you could guarantee ten times better than that.

You present your figures to your customer and let _them_ make the
choice.

 

[Nobody]

Ancient computers, PDP-11 and VAX certainly, had memory management
hardware that separated I and D space, where I space was read-only,
and D space could not be executed. And the OS's enforced those rules.
It was common to have many users running the exact same code, but
mapped into different data spaces.

Problem is, neither Intel nor Microsoft was in the mainstream of
computing when they kluged up x86 and Windows.

W^X (write or execute but not both) is available on current systems, but
that doesn't necessarily cure all buffer overflow exploits. It prevents an
attacker from injecting new code, but it doesn't stop them from calling
existing code with their own data.

The latter may be just as good as the former if some form of "Swiss army
knife" function (e.g. execute arbitrary VB/C#/JS/etc code) is present in
the code space. Actually, system() is almost certain to be there, and
there isn't much you can't do by passing it the right string.

 

[krw]

And my point is that it shouldn't "accidentally" get into a broken
state, any more than the program counter of a CPU should accidentally
find itself in never-never land.

---
It shouldn't, but it can [get into a "broken" state] if that broken
state is allowed to exist. For instance, a glitch on a power supply
rail can cause any number of problems, including putting a shift
register in a prohibited state and causing a circuit to hang.

Without trying to get into the middle of this harangue...

If you look at state transition diagrams of incompletely described
state machines, illegal "islands" can be formed that once entered can
never be exited. These "islands" can be single states feeding back
on themselves. To guarantee that there are no such "islands" in a
design, synthesis tools have "safe" options that will cause illegal
states to be detected and control transferred to valid states.

My circuit (Not "mine" in the sense that I invented it; I didn't.)
side-steps the problem by forcing the potentially problematical
normally prohibited state to be part of the sequence.

Yes, all possible states should be accounted for to make sure this
doesn't happen. "Invalid" states should be decoded also.

<snip>

 

[John Larkin]

W^X (write or execute but not both) is available on current systems, but
that doesn't necessarily cure all buffer overflow exploits. It prevents an
attacker from injecting new code, but it doesn't stop them from calling
existing code with their own data.

The latter may be just as good as the former if some form of "Swiss army
knife" function (e.g. execute arbitrary VB/C#/JS/etc code) is present in
the code space. Actually, system() is almost certain to be there, and
there isn't much you can't do by passing it the right string.

It sounds to me like C compilers/linkers tend to allocate memory to
code, buffers, and stack sort of anywhere they like. So a buffer can
overflow into code space. Why can't at least the compilers be fixed so
that they put all the stacks first, then the code, then all the
buffers? So a stack overflow or a buffer overflow will memory fault
but can't crunch the code.

As it is, a "malformed header" in a packet or even an image file can
result in it being copied into a buffer space that's too small for the
actual data+trojans, and the malware overflows into the next code
block, where it eventually gets executed. And the fix is apparently to
carefully check the headers!

John