Making and Breaking Ciphers with a Commodore 64 - Part 6: XOR is Magical - Data recovery
Review
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
- Searched through a large number looking for matches
We now have most of the basic skills in Assembly to start doing some real work. Let’s tackle what is arguably the most important of the bitwise operators for ciphers and encryption: The exclusive OR. (XOR/EOR)
EOR , XOR or what?
There is a little confusion on the origin and usage of EOR and XOR. They are the same thing.
Commodore BASIC 2.0 doesn’t have an XOR/EOR, but Simon’s BASIC and BASIC 7 on the Commodore 128 both do. To add to the confusion they both call it EXOR.
Sheesh. Let’s just say XOR for the rest of this article because that’s what most modern languages call it. Except when we’ll need to call it EXOR or EOR.
Clear as mud right?
Getting the number back
If you take two bytes and XOR them together you can then XOR either one with the result and get the other number.
In other words: You can reconstruct data if you have 2 parts of the the 3 bytes of information.
Commodore BASIC 2.0 on the VIC 20 and 64 don’t have an XOR token so we’ll use Simon’s BASIC extension to illustrate this:
If you have access to a Commodore 128, BASIC version 7 does include an XOR function.
The real magic of XOR is that if you XOR two numbers together, the result can be XORed with either of the other numbers to get the missing. It’s useful not only in cryptography, but in disk storage. Let’s explore the disk storage this time. We’ll tackle making stream ciphers in Part 7.
At a very basic level, a RAID (redundant array of independent disks) might contain 3 disks. 2 data disks and a 3rd to hold the parity data.
In this primitive example, we have a byte of 12 on disk 1 and byte 2 on disk 2. These two XORed is 14 which we’ll store on disk3.
If we were to lose disk 2, we can then rebuild the data on that disk by taking the parity byte and XORing it with the byte on disk 1 to get the missing byte from disk 2.
It’s a little like magic.
Let’s program it
Two disks that are 5 whole bytes long (simple example remember?). We need to terminate it with something, so I used 0 here. You can either choose a delimiter, or pre fix the length, it’s up to you.
disk1 .byte $44,$f5,$16,$a0,$03,0
disk2 .byte $2a,$52,$b1,$86,$8c,0
.parity .byte 0,0,0,0,0,0
Now to get the parity data, we just EOR(XOR) the bytes with each other and store in the parity table.
ldy #0
loop lda disk1,y
beq ahead
eor disk2,y
sta parity,y
lda #32 ; look for a space ($20)
iny
jmp loop
ahead
Great, now we’ve got some parity data saved.
Disk 1 dies
Well it’s just my luck, disk1 is experiencing click death. Our precious photos are gone forever!
Do the same loop as before with disk2 and the parity:
ldy #0
loop lda disk2,y
beq ahead
eor parity,y
sta disk1,y
lda #32 ; look for a space ($20)
iny
jmp loop
ahead
And BAM. Simple, efficient disk recovery.
Next
In Part 7 we’re going to create better random numbers.