[OpenAFS-devel] FCrypt Spec for AFS rxkad
Ted Anderson
ota@transarc.com
Mon, 18 Dec 2000 15:40:32 -0500 (EST)
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<a:b> 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)
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@transarc.com
REFERENCES
[0] http://www.transarc.com/~ota/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