Specification of FCrypt: Encryption for AFS Remote Procedure Calls[0] INTRODUCTION This is a prose description of the FCrypt enciphering algorithm used by Rx, the AFS remote procedure call (RPC) system, to provide packet authentication and privacy. It is intended that it be complete enough to enable an interoperable implementation of FCrypt to be constructed without reference to the proprietary, export-restricted AFS source code. However, it does not describe Rx or rxkad or how they make use of FCrypt to protect network packets. The FCrypt algorithm is a secret key block cipher with a 64-bit key size and a 64-bit block size. The cipher has the same 16 round Feistel structure[9,10] as DES[1]. The key is provided as an array of octets, the least significant bit of which gives the parity of the remaining seven bits. This format matches that of DES keys, however, FCrypt ignores the parity bits. The input and output blocks are each treated as an array of eight octets. NOTATION All values in the following description are treated as fixed length bitstrings. The symbol "|" indicates bit catenation and "^" indicates bitwise exclusive-or (XOR). The notation V selects bits from a value, V, to produce a smaller bitstring whose length is (a-b+1) bits. The value V<1:0> is equivalent to V<1>|V<0>. Octets are bitstrings of length eight, whose unsigned numerical value is interpreted in little-endian fashion. Thus, V<0> is the least significant bit, and a value of 0x21 is 0|0|1|0|0|0|0|1, namely all zero bits, except V<0> and V<5>, are one. The symbol ">>>" indicates a right rotate, so, rotating a 56 bit value, V, by 11 bits produces V<10:0>|V<55:11>. Array elements are specified using square brackets. The "swap" operator exchanges the values of its two arguments. The "expr; v = x..y" notation indicates an iteration which evaluates "expr" repeatedly with "v" set to each value in the sequence between "x" and "y", inclusively. KEY SCHEDULING The input key block is first processed into a key schedule which consists of an array of sixteen 32-bit words, one for each round. To generate the schedule the parity bits are removed from each of the eight key octets, K, to produce a 56-bit intermediate key, V. The low 32 bits of this intermediate key is copied to each word of the schedule, W, followed by an 11 bit right rotate of the 56-bit intermediate key. S(K) { V<(7-i)*7+6:(7-i)*7> = K[i]<7:1>; i = 0..7 W[i] = V<31:0>, V = V >>> 11; i = 0..15 } BLOCK ENCRYPTION AND DECRYPTION As is traditional with balanced Feistel algorithms, the eight octets of the input block, B, are mapped into two 32-bit halves, left and right, called, L and R. The mapping of octets to 32-bit values uses "network byte order". In the encryption function, E(), each round applies a non-linear function, F(), to the right half and the corresponding 32-bit word of the key schedule, W, and XORs the result to the left half, then swaps the two halves. Decryption, D(), just reverses this process. The roles of the left and right halves are reversed and the key schedule words are used backwards. E(B, W) { L = B[0] | B[1] | B[2] | B[3] R = B[4] | B[5] | B[6] | B[7] L = L ^ F(R, W[i]), swap(L, R); i = 0..15 return (L<31:24>, L<23:16>, L<15:8>, L<7,0>, R<31:24>, R<23:16>, R<15:8>, R<7,0>) } D(B, W) { L = B[0] | B[1] | B[2] | B[3] R = B[4] | B[5] | B[6] | B[7] R = R ^ F(L, W[15-i]), swap(L, R); i = 0..15 return (L<31:24>, L<23:16>, L<15:8>, L<7,0>, R<31:24>, R<23:16>, R<15:8>, R<7,0>) } The F() function takes two 32-bit inputs and returns a 32-bit result. The two inputs are XORed together, T, then split into four octets, a|b|c|d. Each octet is used to index into a different vector of 256 octets. These four vectors, S0, S1, S2, and S3, are called the sboxes, following DES nomenclature. The resulting octets are catenated in the order S0[d] | S1[c] | S3[a] | S2[b], to produce a 32-bit value which is rotated right five bits to produce the output of the F() function. F(R, K) { T = K ^ R T = S0[T<7:0>] | S1[T<15:8>] | S3[T<31:24>] | S2[T<23:16>] return T >>> 5 } The sboxes were constructed from a randomly generated bit stream. They are given here as pairs of hexadecimal digits. S[0, 0..255] = ( A9 2A 48 51 84 7E 49 E2 B5 B7 42 33 7D 5D A6 12 44 48 6D 28 AA 20 6D 57 D6 6B 5D 72 F0 92 5A 1B 53 80 24 70 9A CC A7 66 A1 01 A5 41 97 41 31 82 F1 14 CF 53 0D A0 10 CC 2A 7D D2 BF 4B 1A DB 16 47 F6 51 36 ED F3 B9 1A A7 DF 29 43 01 54 70 A4 BF D4 0B 53 44 60 9E 23 A1 18 68 4F F0 2F 82 C2 2A 41 B2 42 0C ED 0C 1D 13 3A 3C 6E 35 DC 60 65 85 E9 64 02 9A 3F 9F 87 96 DF BE F2 CB E5 6C D4 5A 83 BF 92 1B 94 00 42 CF 4B 00 75 BA 8F 76 5F 5D 3A 4D 09 12 08 38 95 17 E4 01 1D 4C A9 CC 85 82 4C 9D 2F 3B 66 A1 34 10 CD 59 89 A5 31 CF 05 C8 84 FA C7 BA 4E 8B 1A 19 F1 A1 3B 18 12 17 B0 98 8D 0B 23 C3 3A 2D 20 DF 13 A0 A8 4C 0D 6C 2F 47 13 13 52 1F 2D F5 79 3D A2 54 BD 69 C8 6B F3 05 28 F1 16 46 40 B0 11 D3 B7 95 49 CF C3 1D 8F D8 E1 73 DB AD C8 C9 A9 A1 C2 C5 E3 BA FC 0E 25) S[1, 0..255] = ( F0 37 24 53 2A 03 83 86 D1 EC 50 F0 42 78 2F 6D BF 80 87 27 95 E2 C5 5D F9 6F DB B4 65 6E E7 24 C8 1A BB 49 B5 0A 7D B9 E8 DC B7 D9 45 20 1B CE 59 9D 6B BD 0E 8F A3 A9 BC 74 A6 F6 7F 5F B1 68 84 BC A9 FD 55 50 E9 B6 13 5E 07 B8 95 02 C0 D0 6A 1A 85 BD B6 FD FE 17 3F 09 A3 8D FB ED DA 1D 6D 1C 6C 01 5A E5 71 3E 8B 6B BE 29 EB 12 19 34 CD B3 BD 35 EA 4B D5 AE 2A 79 5A A5 32 12 7B DC 2C D0 22 4B B1 85 59 80 C0 30 9F 73 D3 14 48 40 07 2D 8F 80 0F CE 0B 5E B7 5E AC 24 94 4A 18 15 05 E8 02 77 A9 C7 40 45 89 D1 EA DE 0C 79 2A 99 6C 3E 95 DD 8C 7D AD 6F DC FF FD 62 47 B3 21 8A EC 8E 19 18 B4 6E 3D FD 74 54 1E 04 85 D8 BC 1F 56 E7 3A 56 67 D6 C8 A5 F3 8E DE AE 37 49 B7 FA C8 F4 1F E0 2A 9B 15 D1 34 0E B5 E0 44 78 84 59 56 68 77 A5 14 06 F5 2F 8C 8A 73 80 76 B4 10 86); S[2, 0..255] = ( 77 14 A6 FE B2 5E 8C 3E 67 6C A1 0D C2 A2 C1 85 6C 7B 67 C6 23 E3 F2 89 50 9C 03 B7 73 E6 E1 39 31 2C 27 9F A5 69 44 D6 23 83 98 7D 3C B4 2D 99 1C 1F 8C 20 03 7C 5F AD F4 FA 95 CA 76 44 CD B6 B8 A1 A1 BE 9E 54 8F 0B 16 74 31 8A 23 17 04 FA 79 84 B1 F5 13 AB B5 2E AA 0C 60 6B 5B C4 4B BC E2 AF 45 73 FA C9 49 CD 00 92 7D 97 7A 18 60 3D CF 5B DE C6 E2 E6 BB 8B 06 DA 08 15 1B 88 6A 17 89 D0 A9 C1 C9 70 6B E5 43 F4 68 C8 D3 84 28 0A 52 66 A3 CA F2 E3 7F 7A 31 F7 88 94 5E 9C 63 D5 24 66 FC B3 57 25 BE 89 44 C4 E0 8F 23 3C 12 52 F5 1E F4 CB 18 33 1F F8 69 10 9D D3 F7 28 F8 30 05 5E 32 C0 D5 19 BD 45 8B 5B FD BC E2 5C A9 96 EF 70 CF C2 2A B3 61 AD 80 48 81 B7 1D 43 D9 D7 45 F0 D8 8A 59 7C 57 C1 79 C7 34 D6 43 DF E4 78 16 06 DA 92 76 51 E1 D4 70 03 E0 2F 96 91 82 80) S[3, 0..255] = ( EA 7F B2 64 9D B0 D9 11 CD 86 86 91 0A B2 93 06 0E 06 D2 65 73 C5 28 60 F2 20 B5 38 7E DA 9F E3 D2 CF C4 3C 61 FF 4A 4A 35 AC AA 5F 2B BB BC 53 4E 9D 78 A3 DC 09 32 10 C6 6F 66 D6 AB A9 AF FD 3B 95 E8 34 9A 81 72 80 9C F3 EC DA 9F 26 76 15 3E 55 4D DE 84 EE AD C7 F1 6B 3D D3 04 49 AA 24 0B 8A 83 BA FA 85 A0 A8 B1 D4 01 D8 70 64 F0 51 D2 C3 A7 75 8C A5 64 EF 10 4E B7 C6 61 03 EB 44 3D E5 B3 5B AE D5 AD 1D FA 5A 1E 33 AB 93 A2 B7 E7 A8 45 A4 CD 29 63 44 B6 69 7E 2E 62 03 C8 E0 17 BB C7 F3 3F 36 BA 71 8E 97 65 60 69 B6 F6 E6 6E E0 81 59 E8 AF DD 95 22 99 FD 63 19 74 61 B1 B6 5B AE 54 B3 70 FF C6 3B 3E C1 D7 E1 0E 76 E5 36 4F 59 C7 08 6E 82 A6 93 C4 AA 26 49 E0 21 64 07 9F 64 81 9C BF F9 D1 43 F8 B6 B9 F1 24 75 03 E4 B0 99 46 3D F5 D1 39 72 12 F6 BA 0C 0D 42 2E) MODES OF OPERATION Encryption of arbitrary data, such as an RPC packet, is accomplished using Propagating Cipher Block Chaining (PCBC), as in Kerberos V4[2,3]. With PCBC the input plaintext is treated as an array of blocks, each consisting of eight octets. The input is padded with zero octets to a multiple of eight, if necessary. Each output block of ciphertext is computed by encrypting the XOR of the corresponding block of plaintext, the previous block of plaintext and the previous block of ciphertext[4]. This mode requires an eight octet initialization vector (IV); Rx uses the session key as the IV for each packet. An array of plaintext blocks, P, of length N blocks and an initialization vector, I, is transformed into an array of ciphertext blocks, C, by the following algorithm. C[i] = E(I ^ P[i], W), I = P[i] ^ C[i]; i = 0..N-1 Decryption is the reverse. P[i] = I ^ D(C[i], W), I = P[i] ^ C[i]; i = 0..N-1 TEST CASES Key = 00 00 00 00 00 00 00 00 Plaintext = 00 00 00 00 00 00 00 00 Ciphertext = 0E 09 00 C7 3E F7 ED 41 Key = 11 44 77 AA DD 00 33 66 Plaintext = 12 34 56 78 9A BC DE F0 Ciphertext = D8 ED 78 74 77 EC 06 80 Key = 31 41 59 26 53 58 97 93 IV = 27 18 28 18 28 45 90 45 Message = "this is a test" = 74 68 69 73 20 69 73 20 61 20 74 65 73 74 Cipher = AD 51 30 BD 80 9D C8 4F 08 D6 6E CB 10 24 46 54 CRYPTANALYSIS Differential and Linear Cryptanalysis In 1995 I investigated the resistance of FCrypt to differential[6] and linear[8] cryptanalysis. According to Don Coppersmith at IBM, these techniques were known to the designers of DES, however they weren't rediscovered by open cryptographic community until Eli Biham and Adi Shamir published their work starting in 1990[5,6,7]. Inspection of the difference tables for the FCrypt sboxes shows that the worst case one round characteristics are better than DES, which is due to the wider 8-bit sboxes used by FCrypt. However, the best attack on DES uses a a two round characteristic, iterated six times and DES's worst two round characteristic has a probability of 1/234. Using the same model for attacking FCrypt, can take advantage of a two round characteristic whose probability is a disappointing 12/256. Since the number of chosen plaintexts required scales as p^6, this means that an attack against FCrypt would require 2^26.5 plaintexts while the equivalent DES attack requires 2^47.2. One reason for this poor resistance to differential cryptanalysis is that the FCrypt sboxes do not form a permutation. If they had been, then the expected one round probability of a random permutation would have been about 2.3%, while DES's is about 6.5%. When I designed FCrypt, I didn't realize that DES sboxes were composed of permutations. The FCrypt design followed a minimum perturbation from the DES module; making changes specifically to improve software performance. If I had known at the time about permutations, I very likely would have done the same with FCrypt. Applying linear cryptanalysis to FCrypt involves computing a linearized approximation to the sboxes and looking for highly linear entries. DES actually has a few outliers in its linearization, the worst of which has a bias of 20/64, while the worst entry in the FCrypt sboxes is only 36/256. The probable explanation for this relatively poor performance by DES (compared to the random sboxes in FCrypt) is, again, according to Coppersmith, that resistance to linear cryptanalysis was not part of the DES sbox selection criteria. Weak Keys Because of the similarity to DES, FCrypt also suffers from weak keys. However, there are fewer because FCrypt's key schedule has no left/right symmetry. weak 0x0000000000000000 0xffffffffffffffff semi-weak 0xaa55aa55aa55aa55 0x55aa55aa55aa55aa Note that since FCrypt includes a L/R swap after the last round, the words have to be exchanged to observe the identity. Assume X is a function that exchanges the left and right halves of its 64-bit argument, K_w is a key consisting of all zero or all one bits, and K_s1 is one of the semi-weak keys, and K_s2 is the other. P = X(E(X(E(P, K_w)), K_w)) and P = X(E(X(E(P, K_s1)), K_s2)) There are also possibly weak keys which exhibit repeating patterns in the key schedule, which aren't as easy to exploit as weak and semi-weak keys but would probably simplify cryptanalysis: weak_4 0xcc663298cc663298 and 3 rotations 0xee76badcee76badc and 3 rotations 0x8844221088442210 and 3 rotations weak_8 0xf0783c1e0f87c3e1 and 239 others. The similarities to DES also mean that FCrypt has the key complementation property. Namely, that ~E(~P, ~K) = E(P, K) Modes of Operation An easy attack on PCBC[12] is to exchange two 64-bit blocks in the ciphertext. Upon decryption, the resulting plaintext is corrupted only between the two affected blocks, earlier and later blocks are unaffected. Thus it fails to provide the message authentication properties that PCBC was its original purpose. In Kerberos 5 this problem was addressed by including explicit checksums. Very recent developments[11] suggest that it is possible to combine authentication with encryption with little overhead, thought clearly the problem was much harder than the designers of PCBC realized. Summary FCrypt was designed in 1988, before the differential technique was widely known, so it is no real surprise that it's resistance to these attacks is spotty. Even so these approaches remain largely theoretical and are not likely to pose a serious practical threat. On the other hand, I should have known that developing a cryptographic system without submitting it to intensive public analysis was not a good idea. The argument at the time was that DES was just too slow, but in hindsight this was not a good decision. Ted Anderson ota at polyonymo dot us (née ota@transarc.com, ota@surfvi.com) REFERENCES [0] http://ota.polyonymo.us/fcrypt-paper.txt [1] http://www.itl.nist.gov/fipspubs/fip46-2.htm [2] http://web.mit.edu/kerberos/www [3] ftp://athena-dist.mit.edu/pub/kerberos/doc/techplan.txt [4] Bruce Schneier, "Applied Cryptography, 2nd Ed", Wiley, 1996. [5] Biham & Shamir, "Differential cryptanalysis of DES-like cryptosystems", http://www.cs.technion.ac.il/~biham/Reports/Weizmann/cs90-16.ps.gz [6] E. Biham and A. Shamir, "Differential Cryptanalysis of the Data Encryption Standard", Springer-Verlag, 1993. [7] Biham & Shamir, "Differential Cryptanalysis of the Full 16-Round DES", http://www.cs.technion.ac.il/~biham/Reports/cs708.ps.gz [8] Biham, "On Matsui's Linear Cryptanalysis", http://www.cs.technion.ac.il/~biham/Reports/cs813.ps.gz [9] Bruce Schneier, "Applied Cryptography, 2nd Ed", pg 347. [10] http://www.io.com/~ritter/GLOSSARY.HTM#FeistelConstruction [11] http://www.cs.ucdavis.edu/~rogaway/papers/ocb.pdf [12] http://imailab-www.iis.u-tokyo.ac.jp/limit/Papers/Crypto_Eurocrypt/HTML/PDF/C89/35.PDF