1
$\begingroup$

I'm trying to implement a (sort of) simple PRNG in hardware for fun. My idea would be to allow a user to enter a key using a keypad (or some dip switch settings that can be set and hidden) and to obtain a seed using photo, gyro and audio sensors feedback.

I understand I'll probably have to implement some form of modulo arithmetic in hardware. However, I thought up of a hardware-simple algorithm that would only need to use XOR gates. What are your opinions on it?

key = k bits taken from keypad entry
seed = k bits taken from environment sensors
while (true):
    seed << seed[3]             // rotate the seed if seed[3] is 1
    newSeed <- key XOR seed     // the new seed is XORed with the key
    output <- lsb(newSeed)      // output the lsb of the seed
    seed <- newSeed

It outputs the lsb of the newly calculated seed. I have no experience in algorithm design so I'm sure this is riddled with attacks. If the above is not sufficient for a PRNG, which should I use? Is there one which is known to be simpler for low-bit hardware?

$\endgroup$
  • $\begingroup$ by 'secure PRNG' do you mean a cryptographically secure PRNG such that the output is unrecognizable without a key, secure as in utilizing "real" physical entropy to seed a normal PRNG, or secure in the fact you just know it can't be tampered with without physical access? $\endgroup$ – John Meacham Dec 15 '14 at 23:58
  • $\begingroup$ @JohnMeacham Are all three viable together? $\endgroup$ – n0pe Dec 16 '14 at 20:17
  • 1
    $\begingroup$ Yes, choose a good CSPRNG, in general, good stream ciphers will be good CSPRNGs but be sure to check the literature. RC4 notoriously is not good in this regard. ChaCha would probably be a good choice. mix your sensor data into your key. you will have to estimate the amount of entropy of your sensors to be sure you got enough, but that shouldn't be an issue on a uC with analog inputs to pick up noise. just know a 16 bit sample doesn't count as 16 bits of entropy as most bits will be predictable but the noise will be in the last bit or two so it counts as just one or two bits. $\endgroup$ – John Meacham Dec 17 '14 at 0:13
2
$\begingroup$

First, you should not write your own CSPRNG - there are plenty of well vetted ones from which you may pick.

Second, your text and your pseudo code do not match (rotate key or rotate the seed).

Third, as I understand this algorithm it doesn't even give good randomness properties. For example:

Main> let seed = `0x82398eeaf74239 : [64]
Main> let key =  `0x8732754279249  : [64]
Main> let out = take `{256} (prng key seed)
Main> out
0x5555555555555555555555555555555555555555555555555555555555555555
$\endgroup$
  • $\begingroup$ Ah, I actually didn't copy down my algorithm correctly. It should only take the lsb of the seedNew without doing another XOR with the key. Basically just (1) shift seed, (2) XOR with key, (3) take lsb. $\endgroup$ – n0pe Dec 12 '14 at 22:29
  • $\begingroup$ OK, so that's one of the three immediate issues. What is random about this prng? The portion of the population that can't break it? $\endgroup$ – Thomas M. DuBuisson Dec 12 '14 at 22:44
  • $\begingroup$ To be fair, I came up with this in a few minutes without fully thinking it through. I know that designing your own algorithms in crypto is bad news, so I was looking around for some I could implement using only hardware. After more research it seems like I should do this on an Arduino or something and just use BBS or RC4. $\endgroup$ – n0pe Dec 12 '14 at 23:17
  • $\begingroup$ Yes! Basing it on a cipher is a great start. Consider implementing CTR DRBG from 800-90A using a cipher of your choice. $\endgroup$ – Thomas M. DuBuisson Dec 12 '14 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.