LilyVM - RC4 Cryptography Example
To test the existing functionality of LilyVM and its assembler, I decided to implement a simple, well-known cryptography algorithm, RC4. It's not the kind that anyone should use today, because it's got a lot of known effective attacks against it, but it's an easy real-world example of a simple algorithm to play with.
I also like to use it as a random number generator.
Lessons learned tonight:
-
Some more addressing modes to handle things like de-reference pointers without separate load/store instructions would make things MUCH more concise. I think I can add more addressing modes without any overhead.
-
I thought about adding a "swap" instruction because it's done twice in this example. Still not sure about this one.
-
I need better debugging tools! (You'd think inspecting the state of your own VM would be easy.)
-
The code is getting a bit messy and needs a cleanup pass.
-
I really really really need a way to define arbitrary data. In this example I used instructions in place of data just so I had data to work with on the algorithm. Something to just occupy a block of some number of Words, literal numbers, and possibly literal strings would go a long way here.
-
Emacs's asm-mode is barely suitable for this. Maybe I just need to get used to it.
-
I ended up using the stack as though it was just a big series of registers. I guess it's how local variables really would be used normally, so maybe it's not so bad.
-
Being able to create labels that map to arbitrary values instead of just memory locations could have replaced a lot of the arbitrarily-numbered stack positions.
-
I lack sufficient error handling. I want to avoid excessive error checking, and I want to run in places where exceptions are disabled. (I'm looking at you, Unreal 4.) I might have to resort to the evil black magic that is setjmp()/longjmp().
-
I have need function calls. I have no kind of calling convention or anything. There was only a little bit of duplicated code here, though.
Here's the RC4 implementation I made a long time ago that I tested it against.
The actual code follows below. Excuse the lack of syntax highlighting. I guess I need to make the syntax a little more like some common assembler syntax to use an off-the-shelf syntax highlighter.
This code probably will not work for much longer because the assembler and VM are both works in progress. Not that it matters, because I still haven't actually put the source code out anywhere yet. This is mostly a message to any future users (and myself) that this code is not a good example to use.
Final disclaimer: There may be lots of bugs in this implementation.
;;; ----------------------------------------------------------------------
;;; Code section
;;; ----------------------------------------------------------------------
start:
;;; ----------------------------------------------------------------------
;;; Initialize state array and i, j variables
mov 256 $0
cryptoFillLoop:
add $0 -1 $0
add $0 rc4_cryptostate $1
store $0 $1
brnz $0 cryptoFillLoop
;; null can be used instead of zero here, and the entire mov
;; instruction will omit the parameter Word for that.
mov null *rc4_j ; j = 0
mov null *rc4_i ; i = 0
;;; ----------------------------------------------------------------------
;;; Take the key and use it to initialize the state array
setKeyLoop:
;; Key length is hardcoded here until I have a better way to
;; specify it.
div *rc4_i 8 null $4 ; keyval = key[i % 8] (8 is key length)
add key $4 $4
load $4 $4
div $4 256 null $4 ; keyval %= 256
add rc4_cryptostate *rc4_i $5
load $5 $5
add *rc4_j $5 *rc4_j ; j += state[i]
add *rc4_j $4 *rc4_j ; j += keyval
div *rc4_j 256 null *rc4_j ; j %= 256
;; Swap state[i] and state[j]
add rc4_cryptostate *rc4_j $5
add rc4_cryptostate *rc4_i $6
load $5 $7
load $6 $8
store $7 $6
store $8 $5
;; i++
add *rc4_i 1 *rc4_i
;; loop if i != 256
add *rc4_i -256 $3
brnz $3 setKeyLoop
;;; ----------------------------------------------------------------------
;;; Get ready to encrypt
;; Reset i, j
mov null *rc4_j
mov null *rc4_i
;; Loop counter
mov 0 $10
;;; ----------------------------------------------------------------------
;;; Encryption loop
encryptLoop:
;; i = (i + 1) % 256;
add *rc4_i 1 *rc4_i
div *rc4_i 256 null *rc4_i
;; j = (j + state[i]) % 256;
add rc4_cryptostate *rc4_i $6 ; $6 = &state[i]
load $6 $6 ; $6 = *$6
add *rc4_j $6 *rc4_j ; j += $6
div *rc4_j 256 null *rc4_j ; j %= 256
;; Swap state[i] and state[j]
add rc4_cryptostate *rc4_j $5
add rc4_cryptostate *rc4_i $6
load $5 $7
load $6 $8
store $7 $6
store $8 $5
add $7 $8 $9 ; $9 = state[i] + state[j]
div $9 256 null $9 ; $9 %= 256
;; $9 = state[$9]
add rc4_cryptostate $9 $9
load $9 $9
;; At this point we have our byte of randomness from RC4, and
;; can go ahead and encrypt another byte with a xor.
add $10 plaintext $11 ; Get a plaintext byte
load $11 $12
xor $12 $9 $12 ; XOR it
store $12 $11 ; Store it right back to the same
; buffer.
;; $10++
add $10 1 $10
;; loop if $10 != 8
add $10 -8 $11
brnz $11 encryptLoop
;;; ----------------------------------------------------------------------
;;; Done!
stop
;;; ----------------------------------------------------------------------
;;; Some empty space
invalid
invalid
invalid
invalid
invalid
invalid
invalid
invalid
;;; ----------------------------------------------------------------------
;;; Static variables
;;; ----------------------------------------------------------------------
;; The assembler lacks features to declare bytes or volumes of
;; space directly, so we're cheating for now and using
;; instructions with known opcode values to fill space.
;; Plaintext is just 8 Words of zero right now.
.export plaintext
plaintext:
invalid
invalid
invalid
invalid
invalid
invalid
invalid
invalid
;; Can't declare words or bytes, so the machine code generated
;; from this snippet of assembly will be our key because I'm a
;; horrible person. It's 8 words long.
.export key
key: add 1 2 3
add 4 5 6
;; rc4_j and rc4_i are the i and j variables from the RC4
;; algorithm.
.export rc4_i
rc4_i: invalid
.export rc4_j
rc4_j: invalid
.export rc4_cryptostate
rc4_cryptostate:
invalid
;; I guess the crypto state is the rest of memory.
It'll probably take a while before I get all the fixes and changes done I mentioned here. So I'm not sure when the next time I'll post is going to be.
Posted: 2016-07-20
