search

lancaster-university / microbit-dal

http://lancaster-university.github.io/microbit-docs
Other
258 stars 131 forks source link

Suspected non-randomness of RNG #313

Open DavidWhaleMEF opened 7 years ago

DavidWhaleMEF commented 7 years ago

Spotted this on twitter... @finneyj care to comment? it looks quite 'periodic' to the user:

https://twitter.com/alynnafoxie/status/898597401132400641

DavidWhaleMEF commented 7 years ago

From customer:

Micropython. I started getting better results from getrandbits() than randint(). Makes me wonder if their implementations are different..

DavidWhaleMEF commented 7 years ago

MicroPython implementation is here:

https://github.com/bbcmicrobit/micropython/blob/a11ce23fd20c6bdc8f33e3c1cf7a268c00cc6281/source/microbit/modrandom.cpp

DavidWhaleMEF commented 7 years ago

MP uses the dal RND under the bonnet....

define randbelow(n) (MicroBit_random(n))

finneyj commented 7 years ago

@DavidWhaleIET We are using a very lightweight "just about good enough" random generator - a LFSR. This was really just to keep codesize down, very early in the project when we were highly concerned about memory footprint. It's certainly not appropriate for any crypto use etc.

LFSR generators are somewhat periodic, but they are simple to compute - documented here with thinks for those interested:https://github.com/lancaster-university/microbit-dal/blob/5746eb94a8fbe944f474c89c3edd237731cb0f0a/source/core/MicroBitDevice.cpp#L270

It shouldn't be that periodic though (32 bit cycle), and seeded by a crypto grade generator... A little surprised if it's noticeable by typical end users. If it becomes an issue we could consider just using the libc rand() implementation which would give more entropy.