Simple encryption for people on a byte budget Overview

Your goal is to implement RC4 encryption. RC4 encryption, invented by Ron Rivest (of RSA fame), was designed to be secure, yet simple enough to be implemented from memory by military soldiers on the battlefield. Today, there are several attacks on RC4, but it's still used in many places today.  

Your program should accept a single string with both a key and some data. It will be presented in this format.

\x0Dthis is a keythis is some data to encrypt


The first byte represents how long the key is. It can be assumed the key will no longer than 255 bytes, and no shorter than 1 byte. The data can be arbitrarily long.

Your program should process the key, then return the encrypted data. RC4 encryption and decryption are identical, so using the same key to "encrypt" the ciphertext should return the original plaintext.

How RC4 Works

Initialization

Initialization of RC4 is quite simple. A state array of 256 bytes is initialized to all bytes from 0 to 255.  

S = [0, 1, 2, 3, ..., 253, 254, 255]


Key processing

Values in the state are swapped around based on the key.

j = 0
for i from 0 to 255
    j = (j + S[i] + key[i mod keylength]) mod 256
    swap S[i] and S[j]


Encryption

Encryption is accomplished by using the state to generate pseudo-random bytes, which are then XOR'd to the data. Values in the state are swapped around constantly.

i = j = 0
for each byte B in data
    i = (i + 1) mod 256
    j = (j + S[i]) mod 256
    swap S[i] and S[j]
    K = S[(S[i] + S[j]) mod 256]
    output K XOR B


Expected inputs and outputs

Non-printable characters will be shown in \xAB format.

Input: \x01\x00\x00\x00\x00\x00\x00
Output: \xde\x18\x89A\xa3
Output(hex): de188941a3

Input: \x0Dthis is a keythis is some data to encrypt
Output: \xb5\xdb?i\x1f\x92\x96\x96e!\xf3\xae(!\xf3\xeaC\xd4\x9fS\xbd?d\x82\x84{\xcdN
Output(hex): b5db3f691f9296966521f3ae2821f3ea43d49f53bd3f6482847bcd4e  

Input: \x0dthis is a key\xb5\xdb?i\x1f\x92\x96\x96e!\xf3\xae(!\xf3\xeaC\xd4\x9fS\xbd?d\x82\x84{\xcdN
Input(hex): 0d746869732069732061206b6579b5db3f691f9296966521f3ae2821f3ea43d49f53bd3f6482847bcd4e
Output: this is some data to encrypt  

Input: Sthis is a rather long key because the value of S is 83 so the key length must matchand this is the data to be encrypted
Output: \x96\x1f,\x8f\xa3%\x9b\xa3f[mk\xdf\xbc\xac\x8b\x8e\xfa\xfe\x96B=!\xfc;\x13`c\x16q\x04\x11\xd8\x86\xee\x07
Output(hex): 961f2c8fa3259ba3665b6d6bdfbcac8b8efafe96423d21fc3b13606316710411d886ee07
138 bytes, machine code (16-bit x86)

000000 88 9f 00 02 fe c3 75 f8 b9 01 00 89 fa b4 3f cd
000010 21 86 0d ba 00 03 b4 3f cd 21 89 dd 01 f6 02 9e
000020 00 03 8a 04 00 c3 86 87 00 02 88 04 46 45 39 cd
000030 75 02 31 ed 81 fe 00 03 75 e4 81 ee 00 01 31 db
000040 31 d2 ff c6 81 fe 00 03 75 04 81 ee 00 01 8a 04
000050 00 c3 88 c2 86 87 00 02 88 04 00 c2 89 d7 81 c7
000060 00 02 8a 15 89 d7 89 dd 31 db ba 00 03 b9 01 00
000070 b8 00 3f cd 21 87 fa 30 15 85 c0 74 0b 87 fa 43
000080 b4 40 cd 21 89 eb eb b8 cd 20


Running: save to codegolf.com, dosbox:

codegolf.com &lt; input.bin



I don't know if this gonna count as an entry, but I've decided to do it
manually using hex editors. No compilers were used to do this.

ht editor actually has assembler, but honestly I did not know about this until
I was finished ¯\_(ツ)_/¯

Why &amp; how

Why: mostly cause I wanted to check if I'm able to do this.

How: I've started with creating byte filled with NOPs and following with
a simple part: trying to write first loop that fills State with 0..255 values.
I switched to python and quickly wrote python version, just to have something to test against.
Next I was simplifying  python code into pseudo code / pseudo assembly.
Then I I was trying to write small pieces.
I decided it'll be easiest to read from stdin, so I started with something
small that will read single byte, then I added password reading and
key initialization. Figuring out what registers to pick took me some time.

I though adding de/encryption loop will be easy, but first I actually got
single byte decode and added whole loop afterwards.

Last step was getting rid of additional nops that I've left between
instructions when writing it (ofc that required fixing jumps as well).

You can see small gallery that I tried to make while progressing here.

Dissection

The program relies on some initial values after startup (see resources below).

00000000 889f0002                  mov         [bx+0200], bl
00000004 fec3                      inc         bl
00000006 75f8                      jnz         0x0


fill in State (at 0x200)

00000008 b90100                    mov         cx, 0x1
0000000b 89fa                      mov         dx, di
0000000d b43f                      mov         ah, 0x3f
0000000f cd21                      int         0x21
00000011 860d                      xchg        [di], cl
00000013 ba0003                    mov         dx, 0300
00000016 b43f                      mov         ah, 0x3f
00000018 cd21                      int         0x21


read length, read password, store password at ds:0x300

0000001a 89dd                      mov         bp, bx
0000001c 01f6                      add         si, si
0000001e 029e0003                  add         bl, [bp+0300]
00000022 8a04                      mov         al, [si]
00000024 00c3                      add         bl, al
00000026 86870002                  xchg        [bx+0200], al
0000002a 8804                      mov         [si], al
0000002c 46                        inc         si
0000002d 45                        inc         bp
0000002e 39cd                      cmp         bp, cx
00000030 7502                      jnz         0x34
00000032 31ed                      xor         bp, bp
00000034 81fe0003                  cmp         si, 0300
00000038 75e4                      jnz         0x1e


initialize State with a key (BP is used to traverse key, SI is used to
traverse State)

0000003a 81ee0001                  sub         si, 0100
0000003e 31db                      xor         bx, bx
00000040 31d2                      xor         dx, dx
00000042 ffc6                      inc         si
00000044 81fe0003                  cmp         si, 0300
00000048 7504                      jnz         0x4e
0000004a 81ee0001                  sub         si, 0100
0000004e 8a04                      mov         al, [si]
00000050 00c3                      add         bl, al
00000052 88c2                      mov         dl, al
00000054 86870002                  xchg        [bx+0200], al
00000058 8804                      mov         [si], al
0000005a 00c2                      add         dl, al
0000005c 89d7                      mov         di, dx
0000005e 81c70002                  add         di, 0200
00000062 8a15                      mov         dl, [di]


generate pseudo random value (in DL, DH is 0 thx to xor at 0x140)

00000064 89d7                      mov         di, dx      
00000066 89dd                      mov         bp, bx      
00000068 31db                      xor         bx, bx      
0000006a ba0003                    mov         dx, 0300    
0000006d b90100                    mov         cx, 0x1     
00000070 b8003f                    mov         ax, 3f00    
00000073 cd21                      int         0x21        
00000075 87fa                      xchg        dx, di      
00000077 3015                      xor         [di], dl    
00000079 85c0                      test        ax, ax      
0000007b 740b                      jz          0x88        
0000007d 87fa                      xchg        dx, di      
0000007f 43                        inc         bx          
00000080 b440                      mov         ah, 0x40    
00000082 cd21                      int         0x21        
00000084 89eb                      mov         bx, bp      
00000086 ebb8                      jmp         0x40        
00000088 cd20                      int         0x20        



store values that we need to preserve (SI - ints won't touch it, BX)
read char from input, xor it
quit if end of stream
output decoded char
restore values
loop to 0x40 (reuse xor on DX)


P.S. This probably could be even shorter, but this took 4 evenings, so not sure if I want to spend another one...

Tools and resources


ht editor - it has 16-bit disasm
hexplorer - mostly for it's mouse based copy/paste + insert/overwrite
dosbox - for debugging
X86 Opcode and Instruction Reference 1.12 and invaluable 16-bit ModR/M Byte
DOS INT 21h - DOS Function Codes
80386 Instruction Set note this is 386, but that's more than enough
Register values at DOS .COM startup