On-chip randomness (V4FX)

Hi Marc, This is difficult. Ring oscillators are prone to resonate with other on-chip clocks. Also, Xilinx have spent a lot of effort fixing other things you could use like SEUs (see Austin's posts) or Metastability resolution (see Peter's posts). (The metastability thing isn't very random anyway.) If only you could incorporate the actual ISE software into your design; it produces random errors with consummate ease! I suggest you use the built in Vbatt driven solution with a secret number kept alive by a Li coin cell. Apparently, it's good enough for the Feds. Not much help, sorry. Syms.

I think using on board oscillator you should be able to produce some bits of entropy indeed. You just have to design you circuit so that even two very close frequency would lead to very different answer.

Maybe you can use external stimuli as source of entropy as well ?

Also, you menti> Hi,

What about multiplying clock with the DCM as fast as possible and clock a counter (designed to be as slow as possible) with that clock? Best solutions should be achieved before the DCM is locked ;). This approach wont give you true random numbers but the vary should be nondeterministic enough to be useable as seed generator for a lfsr.

bye Thomas

V4 has an oscillator built in that isn't advertised. I forget the name of it at the moment, but you can find it by looking at the Xilinx DCM workaround for the NBTI issues, as the tools connect unused DCMs to that oscillator. You could beat that against an external clock using a counter to get random seeds. In order to avoid the oscillator syncing up to the external clock, you should take the seed sample once as soon as practical after start-up, and use that to seed a PN generator. I am aware of someone working on a master's thesis regarding evaluation of randomness of randoms generated in various ways in an FPGA. I believe she was using Spartan3's for her work, and much of it revolved around using ring oscillators. I think she found that ring oscillators beating against one another worked well as long as the seed was generated right after startup and the ring oscillators were located far apart on the die.

Marc,

See:

or

There are actually rules for use of ring oscillators to generate random numbers, unclassified, for official use only, from the NSA. I am sure you can find it (since it is unclassified) somewhere. The caveat is: whatever you do, you must then test it.

Austin

Hmm, this is interesting:-

I would be careful using an un-locked PLL as a source. I tried that about 20 years ago, using discretes, & gave it up. It proved highly non-random. [Part of my Master's thesis: I was using a 74S124 VCO, with a sampling-type phase detector running from a sinusoidal reference. VCO frequency about 4MHz, reference 132kHz.]

I have, more often, seen the ring-oscillator(s) sampled onto a common clock before XORing together and feeding into an LFSR. It's a little bit bigger due to the synchronizers, but has the nice effect that the bulk of the logic is all synchronous to the system clock.

-hpa

In article , "H. Peter Anvin" writes: |> Peter Alfke wrote: |> > I suggest an on-chip LFSR pseudo-random sequence generator, clocked by |> > a ring-oscillator (or equivalent) clock source and timed out by a fixed |> > delay, derived from the xtal oscillator. That's all very simple, takes |> > only a few CLBs, when the SRL16 is used for the LFSR. |> > Peter Alfke, Xilinx |> |> I have, more often, seen the ring-oscillator(s) sampled onto a common |> clock before XORing together and feeding into an LFSR. It's a little |> bit bigger due to the synchronizers, but has the nice effect that the |> bulk of the logic is all synchronous to the system clock.

XAPP 780 contains a random bit stream generator with ring-oscillators and some "metastability" logic.

onto a common

(snip)

I remember hearing about the 74S124 about 30 years ago. If it is the one I remember, it is actually a dual VCO, except that it is supposed to be impossible to use both without them phase locking. It might be, then, they it could also phase lock to an external source.

-- glen

Hi Georg, Thanks for that link, it's interesting. Of course, the method described in this XAPP note only protects the design from cloning. It's not going to be impossible to reverse engineer the configuration bit stream and find the secret key in the FPGA. In fact, doesn't this method of attack defeat the random number generator thing in all application? If an attacker has physical access to the design, I think the Vbatt RSA key thing is the only 'secure' way to go, otherwise your configuration bitstream is there to see. Thanks, Syms.

Thank you for all follow-ups.

It seems to me that ring-oscillators and meta-stability are the "best" sources for weak (but true) on-chip randomness.

I greatly appreciate the pointer to the XAPP780 appnote, and would like to add one that I found after Austins and Peters comments. Here's another ring-oscillator example source code:

So thanks again for all the valuable input!

Regards, Marc

That's a start ;-)

Well, with some code modification you can put the secret into LUTs and/or "random" logic. Then it's getting harder to find it. It should be also possible to decrypt the picoblaze instructions "online", so it's not that easy to find the BRAM that contains the code. After all, you (as the attacker) need to know where the SHA-stuff is done to start the attack. Using XAPP780 without modifications is not very clever...

Spartans have no Vbatt :-(