Random numbers from POKEY

[morelenmir]

I used to be quite interested in cryptography back in the nineties - BEFORE I might add Simon Singh briefly made the topic cool! Good cryptography requires good randomness, which can be surprizingly expensive. 'True' randomness is VERY hard to achieve. I was once told that supposedly GCHQ count cosmic rays passing through an area of sky above Cheltenham... I doubt that somewhat for any number of reasons, but still it is an amusing idea and may be workable.

 

At one point I became obsessed with using one-time pads to encipher and decipher emails between my pal and I. So long as your key material is longer than your plaintext you end up with a truly unbreakable ciphertext - IF you throw your one-time pad away after each message and IF the pad is TRULY random... Very few people, even among professional programmers realize that random number routines provided in most programming languages are nothing of the sort - just 'pseudo' random and work by seeding the reference point along a fairly long-sequence number series, often with the current time. Against a serious adversary in the age of quantum computers that sort of system is trivial to beat. To get at a pretty productive source of 'reasonably true' randomness I built a simple circuit that sampled the difference between junction-noise across a pair of noisy transistors, hashed the result in a micro controller and then connected it to the PC for delivery over RS232. Sadly I can take absolutely none of the credit for this device as it was a circuit I found on the internet - and no doubt seeded by the NSA for exactly the purpose of catching unwary would-be-napoleons of cipher-crime in a net of false confidence... Still, I was pretty chuffed with the set-up at the time.

 

ANYWAY. Thinking about all this again I wonder if anyone knows how good the randomness is of the hardware random number generator in the POKEY chip? How is it come by? Have any of you chaps ever tried any A8-based cryptography projects of your own?

[Rybags]

Pokey uses a LFSR to generate random numbers.

 

They are repeating and predictable (good emulation reproduces it perfectly). So, not really random and even ignoring the repeating the distribution isn't necessarily random either.

 

Pokey random numbers repeat every 131,000 or so cycles - if 9-bit Poly noise is enabled then it's every 512 cycles.

 

Since 6502 execution and Antic cycle stealing isn't aligned or at a perfect pattern usually, the random numbers you would read mean that some in the sequence are skipped. This helps to increase the randomness and in many cases makes the repeating nature less obvious.

[morelenmir]

Most interesting. Have you ever had a try at doing cryptography with POKEY rybags?

[Bryan]

It's a nice feature since most computers perform random number generation by much simpler software means. POKEY appears to be completely random in most instances because you rarely know how many cycles have passed since POKEY was initialized, and you usually only need to read it again after an unknown number of cycles have passed.

[phaeron]

The random number generator in POKEY is very poor by cryptographic standards. It is a 17-bit linear feedback shift register (LFSR) with a known configuration, and there are algorithms available to determine the current pattern offset based on a handful of random bytes in the sequence. I actually use this technique in some of my tests in order to measure cycle counts. The classic way to combat this works as usual, though: ask the user for input before reading the PRNG.

[NRV]

The random number generator in POKEY is very poor by cryptographic standards. It is a 17-bit linear feedback shift register (LFSR) with a known configuration, and there are algorithms available to determine the current pattern offset based on a handful of random bytes in the sequence. I actually use this technique in some of my tests in order to measure cycle counts. The classic way to combat this works as usual, though: ask the user for input before reading the PRNG.

 

Probably a noob question, but.. x)

If I do:

LDA RANDOM

LDX RANDOM

 

do I get different numbers of the random sequence?.. or.. does the sequence change every machine cycle?

[Bryan]

do I get different numbers of the random sequence?.. or.. does the sequence change every machine cycle?

The number changes every cycle. You cannot read the register fast enough to read the sequence in order.

[phaeron]

You can't, but you can read the RANDOM register fast enough for there to be undesirable correlations between the values returned. The 17-bit LFSR only shifts one bit per cycle, so reading it four cycles apart as in NRV's example guarantees that four bits of the first value will match four bits of the second.

 

As an example, here's a plot of 10,000 points determined by LDX RANDOM / LDY RANDOM. Notice that there is a distinctive 16:1 slant to the points. This is due to four bits often being in common between X and Y. Playfield and refresh DMA are still active, though, so it isn't always four cycles in between the reads.

 

Adding two NOPs between the reads produces better results, because there are no longer bits guaranteed to be the same:

[Xuel]

As an example, here's a plot of 10,000 points determined by LDX RANDOM / LDY RANDOM.

 

Interesting. Those plots seem sparse. Is there a reason that 0 bits are being favored over 1 bits?

[Xuel]

Never mind. I get it now. You are plotting the x,y coordinates. I thought you were using the RANDOM values as bitmap data.

[phaeron]

They're putpixel(x,y) plots against a cleared surface, so the on pixel density is going to be at most 1/6, and lower because of duplicated points or points discarded due to y>=192.