Suggestions for a small progmem 256 bit entropy function

Arduboy
#1

I am looking for suggestions to create a truly random 256 bit integer in the smallest possible progmem space. Here is what I currently have. I am using the generateRandomSeed() function from the Arduboy library plus 8 button presses on any of the four black keys. The highest byte of generateRandomSeed() is not random, because ADC only has 10 bits, and the lowest two bits are always zero, because micros() is always a multiple of 4 on the Arduboy. I fix the least significant bits by adding two bits based on which button was pressed. I fix the highest byte by calling generateRandomSeed() a second time, shift it up by 8 bits and xor it with the rest. From a randomness point of view I do think this is pretty good, but I am sure it can be made smaller in terms of progmem use.

uint32_t x[8];
rand256(x);

void rand256(uint32_t* a) {
  int8_t i=0;
  while (i < 8) {//8 button presses are turned into 32 bytes of entropy
    arduboy.pollButtons();
    if (arduboy.justPressed(UP_BUTTON) | arduboy.justPressed(DOWN_BUTTON) | arduboy.justPressed(LEFT_BUTTON) | arduboy.justPressed(RIGHT_BUTTON)){
      a[i] = arduboy.generateRandomSeed();
      if (arduboy.justPressed(DOWN_BUTTON)) {a[i] += 1;}
      if (arduboy.justPressed(RIGHT_BUTTON)) {a[i] += 2;}
      if (arduboy.justPressed(LEFT_BUTTON)) {a[i] += 3;}
      a[i] ^= arduboy.generateRandomSeed() << 8; //introduce entropy at highest byte
      i++;
    }
  }
}
#2

I’m no expert on the subject, but surely relying on user input defeats the idea of ‘true randomness’?

I think you’d be best off trying to identify other unconnected pins to draw noise from, and perhaps other sources of fluctuating data.
For example, including the battery charge may be of use because although it can be influenced to a degree it’s probably not possible to have fine-grained control over it.

If your goal is solely reducing code size,

Either way, I strongly advise either using a template to capture the array’s size or restricting the function to an array of a specific size. In most cases there ought to be no extra cost because type checking is a compile-time operation and the generated machine code should be more or less the same (if not more optimal).

// Array of size 8 only
void rand256(uint32_t (& array)[8])

// Infer size
template<size_t size>
void rand256(uint32_t (& array)[size])
#3

Depends on how it is done. In the case of the above routine it is a mix of three sources of entropy. One is fully under user control (which of the four buttons is pressed; contributes only 16 bits of the 256 bits in total), one is user input but not sufficiently controllable by a user (time in microseconds it takes to press a button), and the third are the 8 least significant bits from the ADC of a floating pin (128 bits in total). I think this is pretty much as good as one can make it on the Arduboy. Instead of ADC a floating pin one could probe other things with the ADC on the Arduboy, but a floating pin is likely more noisy than other pins.

1 Like
#4

This an interesting read:
https://www.avrfreaks.net/sites/default/files/forum_attachments/Stochastic%20processes%20in%20embedded%20systems%20–%20Random%20number%20generation.pdf

I’ve been make some notes on the entropy from ADC

Section 24.

  • 10-bit successive approximation ADC

  • ±2LSB Absolute Accuracy

  • One Differential amplifier providing gain of 1x - 10x - 40x - 200x

  • Temperature sensor

  • If 1x, 10x, or 40x gain is used, 8-bit resolution can be expected. If 200x gain is used, 7-bit resolution can be expected.

  • The ADC generates a 10-bit result which is presented in the ADC Data Registers, ADCH and ADCL. ADCL must be read first, then ADCH.
  • If a lower resolution than 10 bits is needed, the input clock frequency to the ADC can be higher than 200kHz to get a higher sample rate.

You can most likely just use the LSB of the ADC. Just put several readings together to get the required number of bytes.

It normally helps if you set up some poor settings, such as a fast ADC clock or other stuff that will give naturally noisy readings. See: https://www.avrfreaks.net/comment/2617116#comment-2617116

I think for the Arduboy we should actually log and statistically evaluate the noise collected off the ADC…

1 Like
#5

Thanks for the link to the article. Characterizing the randomness of the ADC in the Arduboy would certainly be a valuable thing to do. Right now I am using the lowest 8 bits of the ADC, but from the article I get that only 4 bits are truly random. I have seen others reduce with xor one ADC reading to one random bit, and then they take 256 readings. That is probably overkill, but folding it into 4 bits per reading would make sense.

But I do not like to use only one source of entropy. Just relying on the ADC is not the best choice. Adding entropy from a timer and/or user input makes it more reliable against problems in one of the entropy sources.