~/jendhub

fcrypt.bend

bend-osdev-legacy-ciphers@0.1.0.0 · 230 lines · 16 definitions

1# FCrypt (T. Anderson, "Specification of FCrypt: Encryption for AFS Remote
2# Procedure Calls", openafs-devel, December 2000): the 64-bit block cipher
3# of AFS's rxkad, with a 64-bit key (56 bits used). It has DES's sixteen
4# Feistel rounds (L, R) -> (R, L xor F(R, W_i)), with no initial or final
5# permutation, its own round function
6#   F(R, K) = (S0[T<7:0>] | S1[T<15:8>] | S3[T<31:24>] | S2[T<23:16>]) >>> 5,
7#   T = R xor K (S0's byte the most significant),
8# and its own key schedule: the key's 8 octets without their parity bits
9# (bit 0) form a 56-bit value V, K[0] the most significant; W_i is V's low 32
10# bits, then V is rotated right by 11.
11#
12# The rounds are legacy-ciphers.bend's Feistel rounds over F, so decryption
13# (the rounds undone last to first, the specification's decryption) undoes
14# encryption for every key and block whatever F is. The specification's
15# PCBC mode is crypto's CrPcbc over this cipher.
16import Base
17import bend-osdev-bytes@0.1.0.0/bytes.bend as B
18import bend-osdev-word64@0.1.0.0/word64.bend as W
19import bend-osdev-legacy-ciphers@0.1.0.0/legacy_ciphers.bend as L
20
21# BEGIN GENERATED by gen/tables.py: tables
22# S0 (the FCrypt specification)
23def fc.s0.list() -> List<&2, U32>:
24  [169, 42, 72, 81, 132, 126, 73, 226,
25    181, 183, 66, 51, 125, 93, 166, 18,
26    68, 72, 109, 40, 170, 32, 109, 87,
27    214, 107, 93, 114, 240, 146, 90, 27,
28    83, 128, 36, 112, 154, 204, 167, 102,
29    161, 1, 165, 65, 151, 65, 49, 130,
30    241, 20, 207, 83, 13, 160, 16, 204,
31    42, 125, 210, 191, 75, 26, 219, 22,
32    71, 246, 81, 54, 237, 243, 185, 26,
33    167, 223, 41, 67, 1, 84, 112, 164,
34    191, 212, 11, 83, 68, 96, 158, 35,
35    161, 24, 104, 79, 240, 47, 130, 194,
36    42, 65, 178, 66, 12, 237, 12, 29,
37    19, 58, 60, 110, 53, 220, 96, 101,
38    133, 233, 100, 2, 154, 63, 159, 135,
39    150, 223, 190, 242, 203, 229, 108, 212,
40    90, 131, 191, 146, 27, 148, 0, 66,
41    207, 75, 0, 117, 186, 143, 118, 95,
42    93, 58, 77, 9, 18, 8, 56, 149,
43    23, 228, 1, 29, 76, 169, 204, 133,
44    130, 76, 157, 47, 59, 102, 161, 52,
45    16, 205, 89, 137, 165, 49, 207, 5,
46    200, 132, 250, 199, 186, 78, 139, 26,
47    25, 241, 161, 59, 24, 18, 23, 176,
48    152, 141, 11, 35, 195, 58, 45, 32,
49    223, 19, 160, 168, 76, 13, 108, 47,
50    71, 19, 19, 82, 31, 45, 245, 121,
51    61, 162, 84, 189, 105, 200, 107, 243,
52    5, 40, 241, 22, 70, 64, 176, 17,
53    211, 183, 149, 73, 207, 195, 29, 143,
54    216, 225, 115, 219, 173, 200, 201, 169,
55    161, 194, 197, 227, 186, 252, 14, 37]
56
57# S1 (the FCrypt specification)
58def fc.s1.list() -> List<&2, U32>:
59  [240, 55, 36, 83, 42, 3, 131, 134,
60    209, 236, 80, 240, 66, 120, 47, 109,
61    191, 128, 135, 39, 149, 226, 197, 93,
62    249, 111, 219, 180, 101, 110, 231, 36,
63    200, 26, 187, 73, 181, 10, 125, 185,
64    232, 220, 183, 217, 69, 32, 27, 206,
65    89, 157, 107, 189, 14, 143, 163, 169,
66    188, 116, 166, 246, 127, 95, 177, 104,
67    132, 188, 169, 253, 85, 80, 233, 182,
68    19, 94, 7, 184, 149, 2, 192, 208,
69    106, 26, 133, 189, 182, 253, 254, 23,
70    63, 9, 163, 141, 251, 237, 218, 29,
71    109, 28, 108, 1, 90, 229, 113, 62,
72    139, 107, 190, 41, 235, 18, 25, 52,
73    205, 179, 189, 53, 234, 75, 213, 174,
74    42, 121, 90, 165, 50, 18, 123, 220,
75    44, 208, 34, 75, 177, 133, 89, 128,
76    192, 48, 159, 115, 211, 20, 72, 64,
77    7, 45, 143, 128, 15, 206, 11, 94,
78    183, 94, 172, 36, 148, 74, 24, 21,
79    5, 232, 2, 119, 169, 199, 64, 69,
80    137, 209, 234, 222, 12, 121, 42, 153,
81    108, 62, 149, 221, 140, 125, 173, 111,
82    220, 255, 253, 98, 71, 179, 33, 138,
83    236, 142, 25, 24, 180, 110, 61, 253,
84    116, 84, 30, 4, 133, 216, 188, 31,
85    86, 231, 58, 86, 103, 214, 200, 165,
86    243, 142, 222, 174, 55, 73, 183, 250,
87    200, 244, 31, 224, 42, 155, 21, 209,
88    52, 14, 181, 224, 68, 120, 132, 89,
89    86, 104, 119, 165, 20, 6, 245, 47,
90    140, 138, 115, 128, 118, 180, 16, 134]
91
92# S2 (the FCrypt specification)
93def fc.s2.list() -> List<&2, U32>:
94  [119, 20, 166, 254, 178, 94, 140, 62,
95    103, 108, 161, 13, 194, 162, 193, 133,
96    108, 123, 103, 198, 35, 227, 242, 137,
97    80, 156, 3, 183, 115, 230, 225, 57,
98    49, 44, 39, 159, 165, 105, 68, 214,
99    35, 131, 152, 125, 60, 180, 45, 153,
100    28, 31, 140, 32, 3, 124, 95, 173,
101    244, 250, 149, 202, 118, 68, 205, 182,
102    184, 161, 161, 190, 158, 84, 143, 11,
103    22, 116, 49, 138, 35, 23, 4, 250,
104    121, 132, 177, 245, 19, 171, 181, 46,
105    170, 12, 96, 107, 91, 196, 75, 188,
106    226, 175, 69, 115, 250, 201, 73, 205,
107    0, 146, 125, 151, 122, 24, 96, 61,
108    207, 91, 222, 198, 226, 230, 187, 139,
109    6, 218, 8, 21, 27, 136, 106, 23,
110    137, 208, 169, 193, 201, 112, 107, 229,
111    67, 244, 104, 200, 211, 132, 40, 10,
112    82, 102, 163, 202, 242, 227, 127, 122,
113    49, 247, 136, 148, 94, 156, 99, 213,
114    36, 102, 252, 179, 87, 37, 190, 137,
115    68, 196, 224, 143, 35, 60, 18, 82,
116    245, 30, 244, 203, 24, 51, 31, 248,
117    105, 16, 157, 211, 247, 40, 248, 48,
118    5, 94, 50, 192, 213, 25, 189, 69,
119    139, 91, 253, 188, 226, 92, 169, 150,
120    239, 112, 207, 194, 42, 179, 97, 173,
121    128, 72, 129, 183, 29, 67, 217, 215,
122    69, 240, 216, 138, 89, 124, 87, 193,
123    121, 199, 52, 214, 67, 223, 228, 120,
124    22, 6, 218, 146, 118, 81, 225, 212,
125    112, 3, 224, 47, 150, 145, 130, 128]
126
127# S3 (the FCrypt specification)
128def fc.s3.list() -> List<&2, U32>:
129  [234, 127, 178, 100, 157, 176, 217, 17,
130    205, 134, 134, 145, 10, 178, 147, 6,
131    14, 6, 210, 101, 115, 197, 40, 96,
132    242, 32, 181, 56, 126, 218, 159, 227,
133    210, 207, 196, 60, 97, 255, 74, 74,
134    53, 172, 170, 95, 43, 187, 188, 83,
135    78, 157, 120, 163, 220, 9, 50, 16,
136    198, 111, 102, 214, 171, 169, 175, 253,
137    59, 149, 232, 52, 154, 129, 114, 128,
138    156, 243, 236, 218, 159, 38, 118, 21,
139    62, 85, 77, 222, 132, 238, 173, 199,
140    241, 107, 61, 211, 4, 73, 170, 36,
141    11, 138, 131, 186, 250, 133, 160, 168,
142    177, 212, 1, 216, 112, 100, 240, 81,
143    210, 195, 167, 117, 140, 165, 100, 239,
144    16, 78, 183, 198, 97, 3, 235, 68,
145    61, 229, 179, 91, 174, 213, 173, 29,
146    250, 90, 30, 51, 171, 147, 162, 183,
147    231, 168, 69, 164, 205, 41, 99, 68,
148    182, 105, 126, 46, 98, 3, 200, 224,
149    23, 187, 199, 243, 63, 54, 186, 113,
150    142, 151, 101, 96, 105, 182, 246, 230,
151    110, 224, 129, 89, 232, 175, 221, 149,
152    34, 153, 253, 99, 25, 116, 97, 177,
153    182, 91, 174, 84, 179, 112, 255, 198,
154    59, 62, 193, 215, 225, 14, 118, 229,
155    54, 79, 89, 199, 8, 110, 130, 166,
156    147, 196, 170, 38, 73, 224, 33, 100,
157    7, 159, 100, 129, 156, 191, 249, 209,
158    67, 248, 182, 185, 241, 36, 117, 3,
159    228, 176, 153, 70, 61, 245, 209, 57,
160    114, 18, 246, 186, 12, 13, 66, 46]
161# END GENERATED: tables
162
163# The four S-boxes, built once per key (internal)
164type LcFcTabs is Data:
165  LcFcTabs{s0: L.LcTab, s1: L.LcTab, s2: L.LcTab, s3: L.LcTab}
166
167def fc.tables() -> LcFcTabs:
168  LcFcTabs{L.lc.tab(8n, fc.s0.list()), L.lc.tab(8n, fc.s1.list()), L.lc.tab(8n, fc.s2.list()), L.lc.tab(8n, fc.s3.list())}
169
170# A round key: W_i and the S-boxes (internal)
171type LcFcRk is Data:
172  LcFcRk{w: U32, t: LcFcTabs}
173
174# F(R, W_i)
175def fc.f(k: LcFcRk, r: U32) -> U32:
176  match k:
177    case LcFcRk{w, t}:
178      match t:
179        case LcFcTabs{s0, s1, s2, s3}:
180          +x = U32.xor(r, w)
181          L.lc.rotl(L.lc.be(L.lc.tab.get(8n, s0, L.lc.byte(x, 0n)), L.lc.tab.get(8n, s1, L.lc.byte(x, 1n)), L.lc.tab.get(8n, s3, L.lc.byte(x, 3n)), L.lc.tab.get(8n, s2, L.lc.byte(x, 2n))), 27n)
182
183# The key schedule
184
185# the 56-bit value of the key bytes xs (parity bits dropped), onto v
186def fc.v(xs: List<&2, U32>, v: W.W64) -> W.W64:
187  match xs:
188    case Nil{}:
189      v
190    case Con{x, t}:
191      fc.v(t, W.W64.or(W.W64.shl(v, 7n), W.W64.from_u32(U32.shrn(U32.and(255, x), 1n))))
192
193# v rotated right by 11 within 56 bits
194def fc.rot11(+v: W.W64) -> W.W64:
195  W.W64.and(W.W64.or(W.W64.shr(v, 11n), W.W64.shl(v, 45n)), W.W64.from_parts(16777215, 4294967295))
196
197def fc.rks(n: Nat, +t: LcFcTabs, +v: W.W64) -> List<&2, LcFcRk>:
198  match n:
199    case 0n:
200      Nil{}
201    case 1n+p:
202      Con{LcFcRk{W.W64.lo(v), t}, fc.rks(p, t, fc.rot11(v))}
203
204# An FCrypt key: the sixteen round keys (opaque; built by LcFcrypt.key)
205type LcFcryptKey is Data:
206  LcFcryptKey{rks: List<&2, LcFcRk>}
207
208def fc.key.pick(ok: Bool, +xs: List<&2, U32>) -> Result<&2, &2, L.LcError, LcFcryptKey>:
209  match ok:
210    case True{}:
211      Done{LcFcryptKey{fc.rks(16n, fc.tables(), fc.v(xs, W.W64.zero()))}}
212    case False{}:
213      Fail{L.LcBadKeyLength{B.len(xs)}}
214
215# The cipher
216
217# an 8-byte key (the parity bits are ignored)
218def LcFcrypt.key(o: B.Octets) -> Result<&2, &2, L.LcError, LcFcryptKey>:
219  +xs = B.Octets.to_list(o)
220  fc.key.pick(Nat.is_eq(B.len(xs), 8n), xs)
221
222def LcFcrypt.encrypt(k: LcFcryptKey, b: L.LcBlock64) -> L.LcBlock64:
223  match k:
224    case LcFcryptKey{rks}:
225      L.lc.fe.run(~LcFcRk, ~fc.f, rks, b)
226
227def LcFcrypt.decrypt(k: LcFcryptKey, b: L.LcBlock64) -> L.LcBlock64:
228  match k:
229    case LcFcryptKey{rks}:
230      L.lc.fe.unrun(~LcFcRk, ~fc.f, rks, b)