[Cryptech Tech] Entropy source delivered

[Fredrik Thulin]

On Wednesday, August 20, 2014 10:55:47 PM Bernd Paysan wrote:
> Am Mittwoch, 20. August 2014, 19:54:31 schrieb Fredrik Thulin:
> > For example, it seems his (and others) circuit deliver around 20 kbit/s of
> > entropy, while mine currently only delivers 4700 bits/s (extracted from
> > 130,000 edges/s - a lot of them thrown away to decrease correlation).
> 
> Hm, can you dump and make available the raw edges, i.e. in a form of (n
> cycles high/m cycles low) for analysis why you have to throw away so many?

Sure, I'd really appreciate help analyzing that.

My MCU has somewhat limited resources though. It isn't fast enough to actually 
export the counter values before the next edge (I only look at rising edges 
for now), and only have 512 byte memory.

What I did was to implement a command that stores 64 consecutive (unless a 
pulse is too fast for my ISR) counter values in memory, and then send those to 
me using the SPI interface. The data is in the format "iteration counter" 
where iteration is the "batch". There should be 64 values for each iteration. 
Example:

  43 0x29f9
  43 0x2a9c
  ...
  43 0x51e4
  43 0x528f

So for iteration 43, the counter moved from 0x29f9 (first edge) to 0x528f 63 
edges later. At 16 MHz, 10390 steps would be about .649 ms, which if I 
calculate it correctly would translate to about 100kbit/s - in the right 
ballpark.

The data is not checksummed, so there might be bit errors in there :(. Anyone 
have a suggestion for a CRC algorithm that is fast and easy to implement in 
both MCU and FPGA?

I can't think of a good server to host the data file right now, so I'll send it 
to you (and anyone else interested) in private e-mail.

I was discarding edges using this code in my ISR:

      /* Copy the current counter value into RAM, for use in entropy 
extraction. */
      entropy_ctr = TA1R;

      /* Decorrelate by ignoring some small random number of edges */
      ignore_edges = (entropy_ctr & 0x7) + 1;

the more bits from entropy_ctr I use, the longer it takes for 'ent' to give me 
bad Chi square numbers (and of course, the lower the output speed is). The 
data collected over night gave Chi square 0.1 nevertheless, so I don't think 
ignoring edges is the right way to remove the correlation or whatever it is.

I'm going to look more at these counter values I've collected too, but as I 
said I *really* appreciate any help in analyzing this.

> With 130k- edges/s and taking only 1 bit per edge, feeding into a von
> Neumann extractor should still give you ~60-70kbit/s.  Benedict takes 1 bit
> per every 4th edge (due to microcontroller limitations), so that's why he
> ends up with 20kbit/s after the von Neumann extractor.

I see. I removed my von Neumann extractor on the theory that the LSB of my 
timer really flips every clock cycle anyways and if I'm strictly interrupt 
driven (as opposed to busy-loop waiting for an input to go high) there 
shouldn't be any bias anyways (but this is just an experiment, I'll verify 
that!). I also removed all the edge ignoring so I would use them as fast as I 
can see them.

I then looked at the noise as well as debug pin-output from my entropy bit 
extractor code using a logic analyzer. It turns out the entropy source is 
really giving >> 130k bits per second (manual estimate 130 * 5). The 130k/s is 
the amount my MCU detects (should get a STM32, eh).

It is clear that a big part of this low speed is due to overhead on account of 
the SPI request/responses. I use SPI to request 128 bits of entropy at once, 
and a total gathering+exchange takes ~8.6 ms. Then there is a gap of 1.6 ms 
while my Raspberry Pi fiddles with those 128 bits.

The actual extraction of the 128 bits account for 2.31 ms of those 8.6. That 
should mean I would get around 55 kbit/s at full speed - much better number!

/Fredrik