On-chip randomness (V4FX)

Hi,

I'm working on a V4FX design that contains cryptographic primitives.

To secure the system against an expected threat, it is necessary to
produce a different seed for every session. The seed doesn't have to be
random nor unpredictable, but the same seed should never be used more
than once.

The system contains non-volatile storage for the purpose of generating
a non-repeating seed.  However the storage is external to the V4FX. An
attacker could isolate the V4FX and make it repeat a seed by replaying
the external stimulus (as recorded from a previous session).

To counter this threat, I wish to mix the externally acquired seed with
on-chip generated "randomness". That would result in a different seed
even during a stimulus replay attack. I know that chips are designed to
behave as repeatable as possible, and I'm asking for quite the
opposite. But at least I want to try, given that even a small amount of
entropy can discourage an attack.

For example I'm thinking about an oscillating combinatorial loop,
sampled during the regular clock events. I expect the output would vary
(at least a little bit) with temperature, supply voltage and perhaps
moon phase.

What other V4FX resources could be (mis)used for this purpose? I'd like
to use two or three unrelated methods.

If you have any suggestion or experience, I'd highly appreciate your
input.

Regards,
Marc

<jetmarc@hotmail.com> wrote in message 
news:1169720137.703620.129880@a75g2000cwd.googlegroups.com...

>
> For example I'm thinking about an oscillating combinatorial loop,
> sampled during the regular clock events. I expect the output would vary
> (at least a little bit) with temperature, supply voltage and perhaps
> moon phase.
>
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 mention "session", if the user can do several session without
power down / power up, you can use local BRAM to store a seed. That
will at least protect during one power cycle. And making a lot of try
with powerup / powerdown is gonna take some time ...

On Jan 25, 11:15 am, jetm...@hotmail.com wrote:
> Hi,
>
> I'm working on a V4FX design that contains cryptographic primitives.
>
> To secure the system against an expected threat, it is necessary to
> produce a different seed for every session. The seed doesn't have to be
> random nor unpredictable, but the same seed should never be used more
> than once.
>
> The system contains non-volatile storage for the purpose of generating
> a non-repeating seed.  However the storage is external to the V4FX. An
> attacker could isolate the V4FX and make it repeat a seed by replaying
> the external stimulus (as recorded from a previous session).
>
> To counter this threat, I wish to mix the externally acquired seed with
> on-chip generated "randomness". That would result in a different seed
> even during a stimulus replay attack. I know that chips are designed to
> behave as repeatable as possible, and I'm asking for quite the
> opposite. But at least I want to try, given that even a small amount of
> entropy can discourage an attack.
>
> For example I'm thinking about an oscillating combinatorial loop,
> sampled during the regular clock events. I expect the output would vary
> (at least a little bit) with temperature, supply voltage and perhaps
> moon phase.
>
> What other V4FX resources could be (mis)used for this purpose? I'd like
> to use two or three unrelated methods.
>
> If you have any suggestion or experience, I'd highly appreciate your
> input.
> 
> Regards,
> Marc

Hi,

On 25 Jan., 11:15, jetm...@hotmail.com wrote:
> For example I'm thinking about an oscillating combinatorial loop,
> sampled during the regular clock events. I expect the output would vary
> (at least a little bit) with temperature, supply voltage and perhaps
> moon phase.
>
> What other V4FX resources could be (mis)used for this purpose? I'd like
> to use two or three unrelated methods.

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

jetmarc@hotmail.com wrote:

> Hi,
> 
> I'm working on a V4FX design that contains cryptographic primitives.
> 
> To secure the system against an expected threat, it is necessary to
> produce a different seed for every session. The seed doesn't have to be
> random nor unpredictable, but the same seed should never be used more
> than once.
> 
> The system contains non-volatile storage for the purpose of generating
> a non-repeating seed.  However the storage is external to the V4FX. An
> attacker could isolate the V4FX and make it repeat a seed by replaying
> the external stimulus (as recorded from a previous session).
> 
> To counter this threat, I wish to mix the externally acquired seed with
> on-chip generated "randomness". That would result in a different seed
> even during a stimulus replay attack. I know that chips are designed to
> behave as repeatable as possible, and I'm asking for quite the
> opposite. But at least I want to try, given that even a small amount of
> entropy can discourage an attack.
> 
> For example I'm thinking about an oscillating combinatorial loop,
> sampled during the regular clock events. I expect the output would vary
> (at least a little bit) with temperature, supply voltage and perhaps
> moon phase.
> 
> What other V4FX resources could be (mis)used for this purpose? I'd like
> to use two or three unrelated methods.
> 
> If you have any suggestion or experience, I'd highly appreciate your
> input.
> 
> Regards,
> Marc
> 


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:

http://www.xilinx.com/xlnx/xweb/xil_tx_display.jsp?iLanguageID=1&category=&sGlobalNavPick=&sSecondaryNavPick=&multPartNum=1&sTechX_ID=alsd_random

or

http://tinyurl.com/2qk77z

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

"Austin Lesea" <austin@xilinx.com> wrote in message 
news:epamfl$vv5@cnn.xsj.xilinx.com...
> Marc,
>
> See:
>
> http://www.xilinx.com/xlnx/xweb/xil_tx_display.jsp?iLanguageID=1&category=&sGlobalNavPick=&sSecondaryNavPick=&multPartNum=1&sTechX_ID=alsd_random
>
> or
>
> http://tinyurl.com/2qk77z
>
> 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:- http://www.faqs.org/rfcs/rfc4086.html 

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

On Jan 25, 2:15 am, jetm...@hotmail.com wrote:
> Hi,
>
> I'm working on a V4FX design that contains cryptographic primitives.
>
> To secure the system against an expected threat, it is necessary to
> produce a different seed for every session. The seed doesn't have to be
> random nor unpredictable, but the same seed should never be used more
> than once.
>
> The system contains non-volatile storage for the purpose of generating
> a non-repeating seed.  However the storage is external to the V4FX. An
> attacker could isolate the V4FX and make it repeat a seed by replaying
> the external stimulus (as recorded from a previous session).
>
> To counter this threat, I wish to mix the externally acquired seed with
> on-chip generated "randomness". That would result in a different seed
> even during a stimulus replay attack. I know that chips are designed to
> behave as repeatable as possible, and I'm asking for quite the
> opposite. But at least I want to try, given that even a small amount of
> entropy can discourage an attack.
>
> For example I'm thinking about an oscillating combinatorial loop,
> sampled during the regular clock events. I expect the output would vary
> (at least a little bit) with temperature, supply voltage and perhaps
> moon phase.
>
> What other V4FX resources could be (mis)used for this purpose? I'd like
> to use two or three unrelated methods.
>
> If you have any suggestion or experience, I'd highly appreciate your
> input.
> 
> Regards,
> Marc

Thomas Stanka wrote:
> Hi,
> 
> On 25 Jan., 11:15, jetm...@hotmail.com wrote:
>> For example I'm thinking about an oscillating combinatorial loop,
>> sampled during the regular clock events. I expect the output would vary
>> (at least a little bit) with temperature, supply voltage and perhaps
>> moon phase.
>>
>> What other V4FX resources could be (mis)used for this purpose? I'd like
>> to use two or three unrelated methods.
> 
> 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.
> 
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.]

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.

	-hpa