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:

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
;;; ----------------------------------------------------------------------
;;; 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.