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.
16	import Base
17	import bend-osdev-bytes@0.1.0.0/bytes.bend as B
18	import bend-osdev-word64@0.1.0.0/word64.bend as W
19	import ./legacy_ciphers.bend as L
20	
21	# BEGIN GENERATED by gen/tables.py: tables
22	# S0 (the FCrypt specification)
23	def 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)
58	def 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)
93	def 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)
128	def 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)
164	type LcFcTabs is Data:
165	  LcFcTabs{s0: L.LcTab, s1: L.LcTab, s2: L.LcTab, s3: L.LcTab}
166	
167	def 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)
171	type LcFcRk is Data:
172	  LcFcRk{w: U32, t: LcFcTabs}
173	
174	# F(R, W_i)
175	def 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
186	def 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
194	def 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	
197	def 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)
205	type LcFcryptKey is Data:
206	  LcFcryptKey{rks: List<&2, LcFcRk>}
207	
208	def 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)
218	def 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	
222	def 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	
227	def 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)