Last visit was: Wed Dec 01, 2021 7:02 pm
It is currently Wed Dec 01, 2021 7:02 pm



 [ 12 posts ] 
 Hardware RNG discussion 
Author Message

Joined: Sun Jul 05, 2020 9:00 pm
Posts: 15
While RNGs can be done in software, there are times when hardware RNGs may make more sense. If you don't have a divider in your architecture, another way to generate them would be to use RAM entropy or read active memory regions.

Modern Intel CPUs have hardware RNGs, but they are very costly, still taking hundreds of cycles and being questionable in being cryptographically secure.

An interesting use for NOPs would be to use them to modify an internal register that could be used as part of hardware RNG. Maybe it could increment the hidden register or work it in nybbles and increment one on every nop and the other on every other NOP, with the roles changing every so many NOPs. That might have more use as an RNG seed or it could be used as part of further RNG processing.

Another hardware RNG idea is to fill a shift register by beating two clocks of differing, unrelated frequencies. So signal drift would generate bits. I am unsure of the best strategy for merging the clocks. One information source on this said to feed the signals into an ADC, but I think XOR could work. I think XOR would be the "fairest" since ANDing would average to the bit being one 1/4 the time, and ORing would have the opposite odds. That does not take the rate of deltas into account since when you are beating frequencies, the closer they are, the slower the drift. This seems easier to do in wired hardware, but I imagine it could be possible on FPGA, just that you'd need to violate the clock domain crossing rules to make sure things are messy.

I've considered using a LUT with rows of predefined random numbers that are rotated at different rates. The logic could rearrange the rows every so often too. Then their shift rates and order change. One trick here is to fill the table with bytes (or words, etc.) that are equally balanced in terms of 1's and 0's used. It likely should be run all the time since the usage frequency would also be a random factor.

The keyboard controller could be used as a random number source. One way would be to measure keystroke lengths. Or you could beat the keyboard clock with another clock and fill shift registers. However, neither method is a reliable source. Users do not type all the time, and an AT keyboard clock is only active when the keyboard is in use. If you use many RND operations, you could exhaust any RND cache.

Caching the random numbers would increase speed. RNG creation can be slow if you are building it from bits or using long division, so your dedicated circuitry could be creating them all the time and caching as they are built. Programs typically do not use them too often, so a cache should work just fine. If they are often being called in a tight loop so that the pool is exhausted, then having a fall-back or secondary RNG could be useful to return single-cycle results.

A precaution to take is not to create conflicts of interest when creating RNGs. Never use things that could use random numbers as their source. You likely would not want to use the program counter, screen locations, or sound clock. You would not want to use the program counter for creating random numbers since if you call the random instruction from within a loop, you will likely get the same number every time. Shifting the program counter at a fixed rate may increase the pool of numbers, but the results might still be of a limited range. The program counter might have some value as a seed. You wouldn't want to use pixel locations either since you could be plotting random dots to the screen and end up with only a straight line and not a proper fill. Likewise, you wouldn't want to use the sound divider as a random number source, particularly when generating random sounds or not using sound.


Last edited by BigEd on Sun Feb 28, 2021 8:15 pm, edited 2 times in total.

fix typo in title



Thu Feb 25, 2021 4:03 pm

Joined: Mon Oct 07, 2019 2:41 am
Posts: 273
If I remember right, a early computer used a noisy diode, to generate random binary bits in hardware.
One might consider two RNG's one for things like games and one for encoding things
Kunth's book #2 , The art of computer programing, covers I think everything about random numbers.
Ben.


Thu Feb 25, 2021 8:43 pm

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1647
I would, I think, distinguish perhaps as many as four cases
- casual random numbers, for games
- cryptographic random numbers, to protect arbitrarily important assets
- legally random numbers, for licensed trades such as gambling including lotteries
- adequately random numbers, that you can prove certain properties of, for purposes like cache replacement or monte carlo simulation

(The first rule of crypto, of course, is you don't invent your own. Even when you think you're able enough. Actually, especially then.)

Intel's intention, I think, was to satisfy all the above uses, which meant something pretty sophisticated and well-analysed. It's still problematic because the analysis is never finished, and yet the generator is already fixed into hardware.

For fun, though, which is mostly where we operate on this forum, you can cook up whatever scheme you like. My personal favourites are the linear feedback shift-registers - they are very simple in hardware, and pretty simple in software. Some people like to use multiplication or division, perhaps because they come from a world where those operations are cheap. I come from 6502, where they are not.

Those well-versed in theory can stack up generator primitives in a meaningful way, to make a more sophisticated and in some sense better generator. But it's not wise to do this casually. Consider those who apply rot13 twice, for extra security!

When you have several sources, there are techniques for mixing in the entropy from each, in such a way that it doesn't matter if some of the sources are low-quality, compromised, or broken (predictable.) But this is a bit expensive. To my level of understanding, cryptographic hash functions are a mixing primitive. I recall that the RNG in the linux kernel used to try to account for remaining entropy, and stall when there was insufficient entropy remaining. But I've a feeling this approach was criticised, and possibly is no longer in use.

https://en.wikipedia.org/wiki/Linear-fe ... t_register
https://en.wikipedia.org/wiki/Linear_co ... _generator
https://en.wikipedia.org/wiki/Mersenne_Twister
https://en.wikipedia.org/wiki/Cryptogra ... _generator
https://research.nccgroup.com/2019/12/1 ... eneration/
https://lwn.net/Articles/590378/


Fri Feb 26, 2021 10:33 am

Joined: Sat Feb 02, 2013 9:40 am
Posts: 1531
Location: Canada
Quote:
If I remember right, a early computer used a noisy diode, to generate random binary bits in hardware.


I used the following article to come up with a hardware random number generator based on reversed biased transistor noise.
https://makezine.com/projects/really-really-random-number-generator/
It is slow, but could be used to seed a faster generator.

_________________
Robert Finch http://www.finitron.ca


Sat Feb 27, 2021 4:00 am WWW

Joined: Sun Jul 05, 2020 9:00 pm
Posts: 15
Yes, these are important considerations. Before attempting to use something cryptographically, you'd want to run a port of the Monte Carlo software or other extensive random number evaluation test suites to look for weaknesses.

A usage case not mentioned would be more scientific. A difference here is that you likely need to use the same random numbers each time. That is why seeding is a thing, to be able to have a predictable pool of "random" numbers. For instance, if you are doing hard drive benchmarking, you'd want to "randomly" seek the same places across the various drives.

The more I think about it, using different logical operators to merge bits would make more sense in different use cases. If you know for a fact that one of your values is always "1," then either do AND or use the other source directly. For instance, the clock you are using to perform the read of the other signal would have to be high or you wouldn't be doing the operation. So reading that other source directly might just make the most sense (and hopefully it enters the "undefined" zone on occasion where it sometimes might count as on or as off). Now if you are reading 2 clocks (unrelated to what is driving the query), then sure, I'd use XOR.


Last edited by Sugarplum on Mon Mar 01, 2021 2:40 am, edited 1 time in total.



Sun Feb 28, 2021 5:32 pm

Joined: Wed Nov 20, 2019 12:56 pm
Posts: 76
Sugarplum wrote:
A usage case not mentioned would be more scientific. A difference here is that you likely need to use the same random numbers each time. That is why seeding is a thing, to be able to have a predictable pool of "random" numbers. For instance, if you are doing hard drive benchmarking, you'd want to "randomly" seek the same places across the various drives.


Another example is actually FPGA place-and-route software - Quartus employs Monte Carlo methods, yet each run is repeatable since the seed is fixed (and user-definable) and the process is driven with a pseudo-RNG. Thus if we're using the same version of the software, we should be able to produce equivalent binaries from the same codebase.

Quote:
So reading that other source directly might just make the most sense (and hopefully it enters the "undefined" zone on occasion where it sometimes might count as on or as off).


Deliberately violating setup and hold timing in order to provoke metastability is a really interesting idea - it piqued my curiosity, and I came across this:
https://people.csail.mit.edu/devadas/pu ... random.pdf


Sun Feb 28, 2021 8:00 pm

Joined: Wed Jan 09, 2013 6:54 pm
Posts: 1647
Great what you can do with feedback!

On the topic of biased random sources, non other than von Neumann himself has his name to a technique of correction: it takes pairs of bits as inputs but outputs a bit only when the two bits differ.


Sun Feb 28, 2021 8:17 pm

Joined: Mon Oct 07, 2019 2:41 am
Posts: 273
I use Quartus (9) and hate the routing. There is about a 75% chance of the routing working for me.
I use say 10% of FPGA and I can't even find where the problem lies. They must add another variable to the
random seed somewhere as I wait a day or two and the problem goes away. This even happens when I just
change data in some on chip ROM like bios patch.
I use 9 because that was when bought a new computer with windows 7
and any thing newer does not support the FPGA I am using. Quartus for unix is big money so I am stuck with
windows.
Ben.


Tue Mar 02, 2021 10:42 am

Joined: Wed Nov 20, 2019 12:56 pm
Posts: 76
oldben wrote:
I use Quartus (9) and hate the routing. There is about a 75% chance of the routing working for me.
I use say 10% of FPGA and I can't even find where the problem lies.


Interesting, I can't say I've ever had such difficulties with Quartus - but then I think the earliest version I used was 11 or 12. (ISE is another story, though!)

Quote:
They must add another variable to the random seed somewhere as I wait a day or two and the problem goes away.
This even happens when I just change data in some on chip ROM like bios patch.


Oh yes, any change to the project will re-roll the dice - I don't know whether there's some kind of global hash, or whether it's simply that any change to the working set changes how the Monte Carlo stuff selects candidate solutions. But as long as nothing changes, the outcome is (or should be!) deterministic. The random seed is just a way of adding a little extra salt to the P&R process which can sometimes help it find a better solution.

Quote:
I use 9 because that was when bought a new computer with windows 7
and any thing newer does not support the FPGA I am using.


Their habit of removing support for older devices is annoying - I'm lucky in that two versions, 13.0sp1 and 18.1 are sufficient to cover all the devices I target - Cyclone II being the oldest. 13.0sp1 is also the oldest version that's still available for download.

Which device are you targetting?

Quote:
Quartus for unix is big money so I am stuck with windows.
Ben.


Hmmm - I have free versions of 13.0sp1 and 18.1 running here on Linux, and I gather people have managed to massage it into running on BSD too. (I believe the latest Windows versions are in fact the Linux version running under Windows Subsystem for Linux!) As I say, it's no longer possible to download anything older than 13.0sp, though.

(Makes a mental note download a spare copy for both platforms while I still can...)


Tue Mar 02, 2021 6:54 pm

Joined: Mon Oct 07, 2019 2:41 am
Posts: 273
Quote:
Their habit of removing support for older devices is annoying - I'm lucky in that two versions, 13.0sp1 and 18.1 are sufficient to cover all the devices I target - Cyclone II being the oldest. 13.0sp1 is also the oldest version that's still available for download.

Which device are you targetting?

Cyclone II (early version). Altera DE1 (orginal version).
For now it works, I don't dare change anyting do to a low end computer and low speed internet.
I plan to emuate TTL / 2901 /PAL 22v10's / roms with the fpga, before I build a LS TTL computer of the same
design. The current architecture is a retro design with no MMU to compete with DEC's PDP11 as a simple 32
bit computer., rather than a complex 16 bitter.
.
Ben.


Tue Mar 02, 2021 10:33 pm

Joined: Wed Nov 20, 2019 12:56 pm
Posts: 76
oldben wrote:
Cyclone II (early version). Altera DE1 (orginal version).


Ah, yes - I like the DE1. I'd still use it regularly if it had more block RAM. I still include it as a target for some of my projects.

Quote:
For now it works, I don't dare change anyting do to a low end computer and low speed internet.


Very wise!

Quote:
I plan to emuate TTL / 2901 /PAL 22v10's / roms with the fpga, before I build a LS TTL computer of the same
design. The current architecture is a retro design with no MMU to compete with DEC's PDP11 as a simple 32
bit computer., rather than a complex 16 bitter.


Ah, I see - nice project! (I imagine accidentally creating combinational loops would be a hazard when emulating discrete logic chips? I can see how that kind of thing could cause Quartus to struggle. As well as being useful in generating random numbers!)


Wed Mar 03, 2021 3:02 pm

Joined: Mon Oct 07, 2019 2:41 am
Posts: 273
Quote:
I see - nice project! (I imagine accidentally creating combinational loops would be a hazard when emulating discrete logic chips? I


You can have set/reset latches from nand/ nor gates, say for switch debouncing.

Did the early FPGA's have both preset and clear
on flipflops? You can have one or the other with todays flip/flops.
Don't forget reset is needed for RNG's, not just a clear.
Ben.


Thu Mar 04, 2021 12:58 am
 [ 12 posts ] 

Who is online

Users browsing this forum: CCBot and 0 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  
Powered by phpBB® Forum Software © phpBB Group
Designed by ST Software