Making and Breaking Ciphers with a Commodore 64 - Part 5: Wargames
Let’s recap a little
So far we’ve:
- Reversed a string
- Shifted bits left and right (mostly right)
- Brute forced a known simple cipher
- Faked it, but then looking for a 4 digit known pin
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
“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:
- Generate random launch code hashes on each startup
- Search through these codes in a table to find the matches
- Stop the launch code for that hash and use as the launch code sequence
- 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
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
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