Making and Breaking Ciphers with a Commodore 64 - Part 5: Wargames

Making and Breaking Ciphers with a Commodore 64 - Part 5: Wargames

Let's recap a little

So far we've:

What we need next in our toolbox is to be able to search through a large number of values to look for something. This will build on the previous skills and also reinforce working with tables and 24 bit math on an 8Bit Processor.

I think Joshua can help us with this.

Wargames

Do you think Ally Sheedy had to do a lot of studying for the line "What are they for?". I love this movie but that line is ridiculous. 

"It's sending random numbers to the silos"

Joshua starts to brute force try all of the possible combinations. If the programmer had limited the number of failed tries allowed...

"At this rate the computer will have the codes in 5.3 minutes."

This is an interesting scene to implement in our Cipher  series because we can build upon the Terminator pin cracker which just did some random stuff before running down 10000 decimals to find a pre coded pin.

For the Wargames demo we'll:

  1. Generate random launch code hashes on each startup
  2. Search through these codes in a table to find the matches
  3. Stop the launch code for that hash and use as the launch code sequence
  4. Launch the missiles, therefore making a mess of earth

The idea of the series is to keep building toolsets so we can do "real" cracking later. Whatever "real" cracking is. I've now watched this movie twice this week in preparation for this article and what we're doing here might not be too far off from what Joshua (the computer) would have had to do to get the launch codes.

Generate Randomness

Generating random numbers on the Commodore is pretty simple, we'll continue to use the method from Compute! magazine. There IS a strange caveat:  it only generates a new random byte every so many CPU cycles, so we actually need to delay a bit to keep from getting a couple in a row. Robin explores this in depth here

genlaunchcodes
         .block
         ldx #31
loop     lda $d41b
         sta launchhash,x
         dex
         bne loop
         rts
         .bend

Without it, we get some repeats:

Adding some NOPs here helps, even if it feels wasteful. We only need to do it once during the setup, so don't get too bent out of shape over a handful of wasted cycles.

genlaunchcodes
         .block
         ldx #31
loop     nop
         nop
         nop
         nop
         nop
         lda $d41b
         sta launchhash,x
         dex
         bne loop
         rts
         .bend

launchhash 
         .byte 0,0,0,0,0,0,0,0
         .byte 0,0,0,0,0,0,0,0
         .byte 0,0,0,0,0,0,0,0
         .byte 0,0,0,0,0,0,0,0
Much more randomerer 

Great, so now we use these random bytes as the encoded codes to guess and store them in a table called launchhash. We'll work on them in groups of three, so there's going to be some 24 bit math to do. Don't worry, it's not that difficult.

24 bits gives us 2563 (16777216) total possible numbers to search through. The Commodore runs at roughly 0.43 MIPS (Millions of instructions per second) at the 1Mhz clock cycle, so this can actually take a while.

Poor randomness

Btw, this is not remotely close to being random enough for anything serious in 2021 (or 2001 for that matter), but it's random enough for games and demos to be useful and it's easy to implement.

Needs to take 5 minutes

"At this rate the computer will have the codes in 5.3 minutes."

Going back to the movie scene, it would be nice to be able to get this code in a similar amount of time. Maybe a little faster so we don't have to sit and watch it for 5.3 minutes right?

NAH! Let's assume the 24 bits which seems more realistic for a 1983 set of codes for a missile launch. Plus we need to work 24 bit math into this series, so this is a good place to do it. 32 bits and up is the same thing we do here, just more times to loop.

24 bit "codes" to crack

We're looking to match the launchcode with the generated launchhash which represents the encrypted passcodes for launch. $F8CF71 is 16306033

We need to search through 16,777,216 combinations 10 times (one for each of the launch code digits).

getlaunch
         .block
loop
         clc
         lda launchcode,x
         adc #1
         sta launchcode,x
         bcc aheadc
         lda launchcode+1,x
         adc #0
         sta launchcode+1,x
         bcc aheadc
         lda launchcode+2,x
         adc #0
         sta launchcode+2,x
aheadc
         lda launchcode+2,x
         cmp launchhash+2,x
         bne ahead
         lda launchcode+1,x
         cmp launchhash+1,x
         bne ahead
         lda launchcode,x
         cmp launchhash,x
         beq done
ahead
         jmp loop

done
	rts
        .bend

We want to call this routine as fast as we can while allowing the screen updates to happen slower.

A simple way to time screen updates is to wait for a raster line in a wait loop. Some variation of:

loop	lda $d012
	cmp #$f0
        bne loop
        rts
        
This will pause until we get to raster line $f0 or 240 in decimal

Update the screen launch codes

zp1 = $fc
guesses  = 1479
		
         lda #10
         sta zp1
         
guesscodes
         .block
         lda zp1
         bne skipframe
         ldx #9
loop     lda skipguess,x
         beq skip
         lda guesses,x
         clc
         adc #1
         cmp #27
         bcc ahead
         cmp #48
         bcs ahead1
         lda #48
ahead1   cmp #58
         bcc ahead
         lda #1
ahead    sta guesses,x
skip     dex
         bpl loop
         lda #5
         sta zp1

skipframe
         dec zp1
         rts
         .bend
         
skipguess .byte 1,1,1,1,1,1,1,1,1,1
;mark these as 0 once we find a match for the hash and codes
We're storing these 10 launch code digits in the screen location starting at 1479

This update runs  slowly to match the movie speed that Joshua is guessing the numbers at (apparently, it's fake of course). If we just wait for a raster line to update the screen rotations, we effectively halt all of the other routines while it's waiting. On an NTSC machine, 60 calculations per second to count to 16,777,216 10 times will take longer than we need it to.  And we can certainly count much faster than +1 per frame. In fact, we NEED to, it would take more then 770 hours to count to the maximum at this rate!

IRQ the screen update

Let's move the screen update to an IRQ and leave the "cracker" routine running in the main loop. This way we only get interrupted on the IRQ calls to update the screen. This dramatically speeds up the background calculations. Don't worry if you're not sure about this routine at the moment, we'll go over it in detail later in the series.

irqsetup
         sei
         ldy #$7f
         sty $dc0d
         sty $dc0d
         lda $dc0d
         lda $dd0d

         lda #$01
         sta $d01a

         lda #<irq
         ldx #>irq
         sta $0314
         stx $0315

         lda #100
         sta $d012

         cli
         
;---- below is what gets called when we get to raster line 100 now
irq
         .block
         dec $d019
         beq skip
         jsr guesscodes
skip
         jmp $ea81

         rts
         .bend
         

Fake but not fake

Since we're doing a real match on a random set of bytes we generate every time we run this, the chances of us getting the same launch code as the one in the movie are, well, pretty slim.

Because we're matching on a random number, ours will stop on each digit when it stops.

Results

This turned out really well. I added a few (pretty sloppy) routines to randomize the digits at startup and the order in which the found hashes match and we get a real time movie effect.

It actually takes between 3.5 and 4 hours to get all 10 of them. MUCH better than the 770 hours (that's 32 days) it was going to take before moving the screen into the IRQ routine. Not bad for a 1983 Computer you could buy at Toys-R-Us for $299. Or $149 two years later. A bargain!

Impatient version

Here it is sped up to complete in less than a minute via the magic of video editing. This took 3.7 hours this time. It will take a different amount each time since we're generating the hashes to find randomly.

Are there improvements that can be made? For certain. Does it work and look pretty cool? It does.

Extra credit

  • use a table to randomize the starting positions of each of the 10 launch code characters like my version shows
  • create a python version of this routine and compare the speed