\ arcfour.4th \ ARCFOUR - Alleged RC4 ( Neil Bawd 1997-05-25 2000-07-16 In 1987 Ron Rivest developed the RC4 cipher-system for RSA Data Security, Inc. It used a well-guarded proprietary trade secret. The system was popular and is used in several hundred commercial cryptography products, including Lotus Notes, Apple Computer's AOCE, and Oracle Secure SQL. It is part of the Cellular Digital Packet Data Specification, and is used by Internet Explorer, Netscape, and Adobe Acrobat. Seven years later, source code alleged to be equivalent to RC4 was published anonymously on the Cypherpunks mailing list. Users with legal copies of RC4 confirmed compatibility. The code is extremely simple and can be written by most programmers from the description. We have an array of 256 bytes, all different. Every time the array is used it changes - by swapping two bytes. The swaps are controlled by counters _i_ and _j_, each initially 0. To get a new _i_, add 1. To get a new _j_, add the array byte at the new _i_. Exchange the array bytes at _i_ and _j_. The code is the array byte at the sum of the array bytes at _i_ and _j_. This is XORed with a byte of the plaintext to encrypt, or the ciphertext to decrypt. The array is initialized by first setting it to 0 through 255. Then step through it using _i_ and _j_, getting the new _j_ by adding to it the array byte at _i_ and a key byte, and swapping the array bytes at _i_ and _j_. Finally, _i_ and _j_ are set to 0. All additions are modulo 256. The cipher key to be used when initializing can be up to 256 bytes, i.e., 2048 bits. It works best when it's shorter so the randomizing done at initialization can thoroughly shuffle the array. At most 64 bytes are recommended for the key. The name "RC4" is trademarked by RSA Data Security, Inc. So anyone who writes his own code has to call it something else. In 1997 I called it ARCIPHER. ARCFOUR has been since widely accepted as the name of the alleged RC4. It is popular because it is small, fast, and believed to be secure. It's a rare example of Cheap, Fast, and Good. For further information, see http://ciphersaber.gurus.com The following Standard Forth version uses Core words only. The number of fetches and stores in `ARCFOUR` has been minimized. There is no need to optimize `ARCFOUR-INIT`. ) \ Implementation dependency on 1 CHARS is 1. \ All arithmetic modulo 256. \ i = i + 1 \ j = j + S[i] \ temp = S[i]; S[i] = S[j]; S[j] = temp \ temp = S[S[i]+S[j]] \ return char xor temp \ Insignificant mods to Neil Bawd's code were made for \ use under kForth -- Krishna Myneni, 2002-04-26 \ Insignificant mods to Krishna Myneni's code were made for \ use under 4tH -- Hans Bezemer, 2003-03-26 VARIABLE &I VARIABLE &J 256 STRING &S \ @ and ! may be replaced by C@ and C!. : ARCFOUR ( c -- x ) \ All arithmetic modulo 256. \ i = i + 1 &I @ 1+ DUP &I ! 255 AND ( . i) \ j = j + S[i] &S + DUP C@ ( . &S[i] S[i]) DUP &J @ + 255 AND ( . &S[i] S[i] j) DUP &J ! \ temp = S[i]; S[i] = S[j]; S[j] = temp &S + DUP C@ ( . &S[i] S[i] &S[j] S[j]) >R OVER SWAP C! ( . &S[i] S[i])( R: S[j]) R@ ROT C! ( . S[i]) \ temp = S[i]; S[i] = S[j]; S[j] = temp R> + ( . S[i]+S[j])( R: ) 255 AND &S + C@ ( c x) \ return char xor temp XOR ( x) ; : ARCFOUR-INIT ( key len -- ) \ Set array to 0 through 255. 256 0 DO I DUP &S + C! LOOP 0 &J ! 256 0 DO ( key len) \ Get new j by adding array byte at i and a key byte. OVER OVER I SWAP MOD + C@ I &S + C@ + &J @ + 255 AND &J ! \ Swap array bytes at i and j. I &S + C@ &J @ &S + &J @ &S + C@ I &S + C! C! LOOP DROP DROP \ Set i and j to 0. 0 &I ! 0 &J ! ; ( To compete with the many appearances of RC4, a Forth version should be a CODE definition for speed. In this CODE definition, there is no stack movement. It is more than 4.5 times as fast as the colon version above. CREATE Arcfour-State 2 CELLS 256 CHARS + ALLOT : MACRO \ "name ccc" -- : CHAR PARSE POSTPONE SLITERAL POSTPONE EVALUATE POSTPONE ; IMMEDIATE ; MACRO &I " Arcfour-State " MACRO &J " Arcfour-State CELL+ " MACRO &S " Arcfour-State 2 CELLS + " CODE ARCFOUR \ char -- code \ RX i \ RY j \ R30 S[i] finally S[S[i]+S[j]] \ R31 S[j] \ R29 &i, then &S, then char, then code \ Save local registers. R31 -4 RRSP STWU, R30 -4 RRSP STWU, R29 -4 RRSP STWU, \ RTOS = Arcfour-State RTOS -4 RDSP STWU, \ . . ['] Arcfour-State info-find-token @infoDataOffset R29 LiteralToRegister, R29 RDBP ADD, \ To get a new i, add 1. RX 0 R29 LWZ, \ rx = i RX RX 1 ADDI, \ rx = rx + 1 RX 0 R29 STW, \ i = rx RX RX 255 ANDI., \ rx = rx mod 256 \ To get a new j, add the array byte at the new i. R29 R29 8 ADDI, \ rtos = &S R30 R29 RX LBZX, \ r30 = S[i] RY -4 R29 LWZ, \ ry = j RY RY R30 ADD, \ ry = ry + S[i] RY RY 255 ANDI., \ ry = ry mod 256 RY -4 R29 STW, \ j = ry \ Swap the array bytes at i and j. R31 R29 RY LBZX, R30 R29 RY STBX, R31 R29 RX STBX, \ The code is the array byte at the sum of the \ array bytes at i and j. R30 R31 ADD, R30 R30 255 ANDI., R30 R29 R30 LBZX, \ XOR with plaintext or ciphertext byte. RTOS R30 XOR, \ Restore local registers. R29 0 RRSP LWZ, R30 4 RRSP LWZ, R31 8 RRSP LWZ, RRSP 12 ADDI, NEXT, END-CODE \ Definition of ARCFOUR-INIT copied from above. ) ( This is one of many tests to validate the code. It works with any correct version of `ARCFOUR`. ) 64 STRING KEY: : !KEY ( c1 c2 ... cn n -- store the specified key of length n ) KEY: + DUP 0 SWAP C! KEY: 1- SWAP 1- ?DO I C! -1 +LOOP ; [HEX] HEX 61 8A 63 0D2 0FB DECIMAL 5 !KEY KEY: COUNT ARCFOUR-INIT CR HEX 0DC ARCFOUR . 0EE ARCFOUR . 04C ARCFOUR . 0F9 ARCFOUR . 02C ARCFOUR . DECIMAL CR .( Should be: F1 38 29 C9 DE ) \ CR .( Should be: Fox 1; 3 8; 2 9; Charlie 9; Dog Easy. ) \ End of ARCFOUR