Making and Breaking Ciphers with a Commodore 64 - Part 6: XOR is Magical - Data recovery

Making and Breaking Ciphers with a Commodore 64 - Part 6: XOR is Magical - Data recovery


So far we've:

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

I just picked this data at random, or did I?

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)
    	jmp loop

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)
    	jmp loop

And BAM. Simple, efficient disk recovery.


In Part 7 we're going to create better random numbers.