So far in this 7 part (shocked I’ve made it through 7!) series on doing weird things with Ciphers on old computers we’ve:

• Reversed a string
• Shifted bits left and right (mostly right)
• Brute forced a known simple cipher
• Channeled our inner John Connor by cracking ATM machines
• Searched through a large number looking for matches
• Learned how to use XOR to recover data

Author’s Note:

This one stretched my skills quite a bit, but I kept it under 2000 words (by 89). I’m not sure when I started this I knew I’d be doing a Linear Congruential Generator on a 40 year old machine, but here we are ;-)

Pseudo Random

This our the first dive into creating randomness. It will require several explorations, and this isn’t THE discussion we’ll have about this. Several volumes could be written about this, so we’ll break it down a little at a time.

The Commodore SID random number method isn’t suitable for serious use at the time I’m writing this in mid 2021, but it’s perfectly serviceable to study how encryption works, and the fact that it’s insecure will actually help us to be able to demonstrate the insecurities in Pseudo random easier. Who wants to wait around a couple hundred years to break a SHA-512 key? Not this guy.

Much of what I knew about Commodore Random numbers before preparing to write this is from this article:

https://www.atarimagazines.com/compute/issue72/random_numbers.php

and this breakdown of the SID details:

http://www.oxyron.de/html/registers_sid.html

Many cryptographic algorithms require the use of one or more random numbers, typically to initialize a process with a seed, generate keys, create salts, or randomize something.

We use a mathematical function to generate a sequence of pseudo-random numbers. This is called a pseudo-random number generator (PRNG).

We seed the PRNG with a random number and then it recursively generates a deterministic set of numbers, always the same for a given seed.

A good pseudo-random number generator is awfully difficult to distinguish from a sequence of random numbers.

In our case, we’ll use a pretty good PRNG and seed it with the SID random number generator. This should be adequate for our purposes here.

Linear Congruential Generator (LCG)

The linear congruential generator (LCG) is a commonly used PRNG. It has a simple definition [^1] [^2]

Xn+1 = (m*xn + a) mod P
P >= 2 is an integer. P is the period of the PRNG.
The integer coefficient m is called the multiplier; m > 0 and m < P.
a is an additive integer constant where a > 0 and a < P.
The initial value of the generator x0 is the seed.
xn  is the nth pseudo-random number generated by the function.

An LCG is recursive and is both fast and pretty easy to implement in code. The statistical randomness of LCG is sensitive to the modulus value P and the seed used.

Let’s do a python version first

def generateLCG(multiplier, addr, period, seed,iterations):
    count = 0
    lastValue = seed
    while ct < iterations:
        lastValue = (multiplier*lastValue + addr) % period
        count += 1
        print(lastValue, ' ', hex(lastValue))
    
generateLCG(11, 37, 1000, 0, 10)

Results:
37    0x25
444   0x1bc
921   0x399
168   0xa8
885   0x375
772   0x304
529   0x211
856   0x358
453   0x1c5
20    0x14

It’s important to note that with the same parameters (seed included) this will always produce the same sequence, so choose your seeds wisely. Better yet, make them random.

Obviously in the above python code we’re just checking a sane example to make sure our Assembly version is working later. A more sensible use would be the GNU C library glibc’s standard:

glibc uses a period of 245, a multiplier value of 25,214,903,917 and a seed value of 11, in the specification of its LCG.

generateLCG(25214903917,37, 2**45, 11, 10)

Results:

277363943124     0x40942de6d4
12373672706153   0xb40f85dc069
16644769661658   0xf23699542da
25034216526583   0x16c4bb9552f7
31583928204624   0x1cb9b4d23d50
9976241847093    0x912c659fb35
6630739383222    0x607d6dd93b6
27812309592227   0x194b8ed568a3
17765547376524   0x10285d23ff8c
25722508515009   0x1764fcfb96c1

These period and multiplier values are pretty difficult on the Commodore at 1Mhz. As we’ve seen before, it takes a whole day for these machines to just count to 4 billion, let alone do a couple rounds of shifts and math to get there. If you want to give them a try, knock yourself out.

How is an LFSR different from an LCG and which is better?

The SID on the Commodore 64 uses a 23 bit LFSR. On shifting, bit 0 is filled with bit 22 EXOR bit 17.

An LFSR is different than a LCG in its approach: it does its shifting with Exclusive OR(usually) instead of integer addition and multiplication.

Neither is better and both suffer from different problems. Applied Cryptography: Protocols, Algorithms, and Source Code in C is a good resource to really get into the weeds on these two methods.

One “common” solution to generate better randomness is to use two PRNGs of different types, adding the results together. [^5]

We’ll do that here by seeding the LCG with a set of bytes from the Commodore SID Random number generator at $d41b, which is an LFSR.

Remember that these are probably not suitable for cryptography, especially with the limits of an 8 bit processor that can only address 64k of memory at a time. And by probably not suitable, I mean they are not suitable at all. We’re studying them as an evolution over a series. I promise there’s a point to the whole endeavor. Probably.

Getting the LCG on the Commodore

By far the easiest way to get this simple algorithm on the Commodore is to do it in BASIC. Just like the XOR post we are going to use Simons’ BASIC to get a mod function without having to implement it ourselves.

Basic Version

LCR in Assembly

I’ll be using Turbo Macro Pro as usual. Because I don’t use macros or scripting of any kind, this should port very easily to your assembler of choice.

Multiply and Divide

We need to be able to multiply and divide larger numbers for the rest of this series, so let’s work on routines for that. These are pretty well known routines so I didn’t try to reinvent the wheel. Both Codebase64 and 6502 assembly language programming by Lance Leventhal can help you explore these further.

Let’s start with a multiplier that can handle 32 bit results (232 or 4,294,967,296)

multiply16
         .block
         lda #0
         sta product+2
         sta product+3

         ldx #16
shiftr
         lsr multiplier+1
         ror multiplier
         bcc rotater
         lda product+2
         clc
         adc multiplicand
         sta product+2
         lda product+3
         adc multiplicand+1

rotater
         ror a
         sta product+3
         ror product+2
         ror product+1
         ror product
         dex
         bne shiftr
         rts
         .bend
         
;multiply16
multiplier .byte $ff,$ff
multiplicand .byte $ff,$ff
product  .byte 0,0,0,0

And now a 24 bit divider

divide24
         ;dividend/divisor
         .block
         lda #0
         sta remainder
         sta remainder+1
         sta remainder+2
         ldx #24 ;every bit

loop
         asl dividend
         rol dividend+1
         rol dividend+2
         rol remainder
         rol remainder+1
         rol remainder+2
         lda remainder
         sec
         sbc divisor
         tay
         lda remainder+1
         sbc divisor+1
         sta zp1
         lda remainder+2
         sta divisor+2
         bcc skip

         sta remainder+2
         lda zp1
         sta remainder+1
         sty remainder
         inc answer
skip
         dex
         bne loop
         rts

         .bend



;divide24
remainder .byte 0,0,0
dividend .byte 0,0,0
divisor  .byte 0,0,0

answer   = dividend

The LCG

Just a reminder, this is written for clarity over efficiency. I’d love to hear how you’d optimize. Definitely some bytes and cycles could be saved here at a cost of readability.

dolcg
         .block
loop
         lda multip
         sta multiplier
         lda lastvalue
         sta multiplicand
         lda lastvalue+1
         sta multiplicand+1
         jsr multiply16
         lda product
         clc
         adc addr
         sta dividend
         lda product+1
         adc #0
         sta dividend+1
         lda period
         sta divisor
         lda period+1
         sta divisor+1
         jsr divide24
         lda remainder
         sta lastvalue
         lda remainder+1
         sta lastvalue+1
printresult
         lda lastvalue+1
         jsr printbyte
         lda lastvalue
         jsr printbyte
         lda #13
         jsr $ffd2
         inc count
         lda count
         cmp iterations
         bne loop
         
         rts
         .bend
         
;lcg
count    .byte 0

multip   .byte 11
addr     .byte 37
period   .byte $e8,$03
seed     .byte 0,0,0
lastvalue = seed
iterations .byte 10
lcgvalue .byte 0,0

A couple of these label locations could definitely go in zero page to save some cycles. Have fun experimenting with that.

Run it

Remember from our Python and BASIC proof of concepts above we’re expecting the hex values:

0x25
0x1bc
0x399
0xa8
0x375
0x304
0x211
0x358
0x1c5
0x14

It works! I definitely did a little dance move when I ran this the first time because it actually worked the first time without any bugs. I can’t remember ever having a first run that didn’t have at least something that needed to be adjusted.

Combine the LCG and LFSR

This is all great, but how are we going to get random numbers out of it in a more reasonable fashion?

We know we can get a random value from $d41b via the SID’s 23 Bit LFSR, so if we seed the LCR with the SID’s LFSR, we’re now combining two methods to produce more random results. I almost said results to make cryptographers and mathematicians happy, but let’s be honest, those two groups of people make the world better because they’re NEVER happy with the results.

Even without increasing the multiplier and period dramatically (glibc uses 1103515245 as the multiplier) seeding this VERY simple example does make this much more random than just the SID LFSR on it’s own.

Linear Feedback Shift Register (LFSR) in Assembly

Since I know someone will ask, here’s an example Linear Feedback Shift Register from Codebase64 [^3].

random
        asl random
        rol random+1
        rol random+2
        rol random+3
        bcc nofeedback
        lda random
        eor #$B7
        sta random
        lda random+1
        eor #$1D
        sta random+1
        lda random+2
        eor #$C1
        sta random+2
        lda random+3
        eor #$04
        sta random+3
nofeedback
        rts

random: .byte $FF,$FF,$FF,$FF

Extra Credit

• Change these routines to handle the very large periods common in PRNGs
• Optimize the routines to run faster

Side project

As a side project I’ve been working on trying to find the repeat period for the Commodore SID 23 Bit LFSR in real life (find the repeat point). Counting and storing to 223 requires an REU and I’ve not quite cracked it yet.

But here’s some code running that shows the distribution of each of the possible 256 random bytes over 500k samples.

Baby steps, this takes about 30 seconds to actually run, so we skip the blank screen part.

Footnotes

[^1] Excerpt From: Karan Singh Garewal. “Practical Blockchains and Cryptocurrencies.” Apple Books. p 65

[^2] https://en.wikipedia.org/wiki/Linear_congruential_generator

[^3] https://en.wikipedia.org/wiki/Linear-feedback_shift_register

[^4] https://codebase64.org/doku.php?id=base:32bit_galois_lfsr

[^5] https://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRC-32_algorithm

[^6] Direct from the LFSR Wikipedia page

• C64
• Code
• Commodore
• Crypto
• How-To
• Retro
• Security