1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3 * Implementation of POLYVAL using ARMv8 Crypto Extensions.
4 *
5 * Copyright 2021 Google LLC
6 */
7 /*
8 * This is an efficient implementation of POLYVAL using ARMv8 Crypto Extensions
9 * It works on 8 blocks at a time, by precomputing the first 8 keys powers h^8,
10 * ..., h^1 in the POLYVAL finite field. This precomputation allows us to split
11 * finite field multiplication into two steps.
12 *
13 * In the first step, we consider h^i, m_i as normal polynomials of degree less
14 * than 128. We then compute p(x) = h^8m_0 + ... + h^1m_7 where multiplication
15 * is simply polynomial multiplication.
16 *
17 * In the second step, we compute the reduction of p(x) modulo the finite field
18 * modulus g(x) = x^128 + x^127 + x^126 + x^121 + 1.
19 *
20 * This two step process is equivalent to computing h^8m_0 + ... + h^1m_7 where
21 * multiplication is finite field multiplication. The advantage is that the
22 * two-step process only requires 1 finite field reduction for every 8
23 * polynomial multiplications. Further parallelism is gained by interleaving the
24 * multiplications and polynomial reductions.
25 */
26
27 #include <linux/linkage.h>
28 #define STRIDE_BLOCKS 8
29
30 KEY_POWERS .req x0
31 MSG .req x1
32 BLOCKS_LEFT .req x2
33 ACCUMULATOR .req x3
34 KEY_START .req x10
35 EXTRA_BYTES .req x11
36 TMP .req x13
37
38 M0 .req v0
39 M1 .req v1
40 M2 .req v2
41 M3 .req v3
42 M4 .req v4
43 M5 .req v5
44 M6 .req v6
45 M7 .req v7
46 KEY8 .req v8
47 KEY7 .req v9
48 KEY6 .req v10
49 KEY5 .req v11
50 KEY4 .req v12
51 KEY3 .req v13
52 KEY2 .req v14
53 KEY1 .req v15
54 PL .req v16
55 PH .req v17
56 TMP_V .req v18
57 LO .req v20
58 MI .req v21
59 HI .req v22
60 SUM .req v23
61 GSTAR .req v24
62
63 .text
64
65 .arch armv8-a+crypto
66 .align 4
67
68 .Lgstar:
69 .quad 0xc200000000000000, 0xc200000000000000
70
71 /*
72 * Computes the product of two 128-bit polynomials in X and Y and XORs the
73 * components of the 256-bit product into LO, MI, HI.
74 *
75 * Given:
76 * X = [X_1 : X_0]
77 * Y = [Y_1 : Y_0]
78 *
79 * We compute:
80 * LO += X_0 * Y_0
81 * MI += (X_0 + X_1) * (Y_0 + Y_1)
82 * HI += X_1 * Y_1
83 *
84 * Later, the 256-bit result can be extracted as:
85 * [HI_1 : HI_0 + HI_1 + MI_1 + LO_1 : LO_1 + HI_0 + MI_0 + LO_0 : LO_0]
86 * This step is done when computing the polynomial reduction for efficiency
87 * reasons.
88 *
89 * Karatsuba multiplication is used instead of Schoolbook multiplication because
90 * it was found to be slightly faster on ARM64 CPUs.
91 *
92 */
93 .macro karatsuba1 X Y
94 X .req \X
95 Y .req \Y
96 ext v25.16b, X.16b, X.16b, #8
97 ext v26.16b, Y.16b, Y.16b, #8
98 eor v25.16b, v25.16b, X.16b
99 eor v26.16b, v26.16b, Y.16b
100 pmull2 v28.1q, X.2d, Y.2d
101 pmull v29.1q, X.1d, Y.1d
102 pmull v27.1q, v25.1d, v26.1d
103 eor HI.16b, HI.16b, v28.16b
104 eor LO.16b, LO.16b, v29.16b
105 eor MI.16b, MI.16b, v27.16b
106 .unreq X
107 .unreq Y
108 .endm
109
110 /*
111 * Same as karatsuba1, except overwrites HI, LO, MI rather than XORing into
112 * them.
113 */
114 .macro karatsuba1_store X Y
115 X .req \X
116 Y .req \Y
117 ext v25.16b, X.16b, X.16b, #8
118 ext v26.16b, Y.16b, Y.16b, #8
119 eor v25.16b, v25.16b, X.16b
120 eor v26.16b, v26.16b, Y.16b
121 pmull2 HI.1q, X.2d, Y.2d
122 pmull LO.1q, X.1d, Y.1d
123 pmull MI.1q, v25.1d, v26.1d
124 .unreq X
125 .unreq Y
126 .endm
127
128 /*
129 * Computes the 256-bit polynomial represented by LO, HI, MI. Stores
130 * the result in PL, PH.
131 * [PH : PL] =
132 * [HI_1 : HI_1 + HI_0 + MI_1 + LO_1 : HI_0 + MI_0 + LO_1 + LO_0 : LO_0]
133 */
134 .macro karatsuba2
135 // v4 = [HI_1 + MI_1 : HI_0 + MI_0]
136 eor v4.16b, HI.16b, MI.16b
137 // v4 = [HI_1 + MI_1 + LO_1 : HI_0 + MI_0 + LO_0]
138 eor v4.16b, v4.16b, LO.16b
139 // v5 = [HI_0 : LO_1]
140 ext v5.16b, LO.16b, HI.16b, #8
141 // v4 = [HI_1 + HI_0 + MI_1 + LO_1 : HI_0 + MI_0 + LO_1 + LO_0]
142 eor v4.16b, v4.16b, v5.16b
143 // HI = [HI_0 : HI_1]
144 ext HI.16b, HI.16b, HI.16b, #8
145 // LO = [LO_0 : LO_1]
146 ext LO.16b, LO.16b, LO.16b, #8
147 // PH = [HI_1 : HI_1 + HI_0 + MI_1 + LO_1]
148 ext PH.16b, v4.16b, HI.16b, #8
149 // PL = [HI_0 + MI_0 + LO_1 + LO_0 : LO_0]
150 ext PL.16b, LO.16b, v4.16b, #8
151 .endm
152
153 /*
154 * Computes the 128-bit reduction of PH : PL. Stores the result in dest.
155 *
156 * This macro computes p(x) mod g(x) where p(x) is in montgomery form and g(x) =
157 * x^128 + x^127 + x^126 + x^121 + 1.
158 *
159 * We have a 256-bit polynomial PH : PL = P_3 : P_2 : P_1 : P_0 that is the
160 * product of two 128-bit polynomials in Montgomery form. We need to reduce it
161 * mod g(x). Also, since polynomials in Montgomery form have an "extra" factor
162 * of x^128, this product has two extra factors of x^128. To get it back into
163 * Montgomery form, we need to remove one of these factors by dividing by x^128.
164 *
165 * To accomplish both of these goals, we add multiples of g(x) that cancel out
166 * the low 128 bits P_1 : P_0, leaving just the high 128 bits. Since the low
167 * bits are zero, the polynomial division by x^128 can be done by right
168 * shifting.
169 *
170 * Since the only nonzero term in the low 64 bits of g(x) is the constant term,
171 * the multiple of g(x) needed to cancel out P_0 is P_0 * g(x). The CPU can
172 * only do 64x64 bit multiplications, so split P_0 * g(x) into x^128 * P_0 +
173 * x^64 * g*(x) * P_0 + P_0, where g*(x) is bits 64-127 of g(x). Adding this to
174 * the original polynomial gives P_3 : P_2 + P_0 + T_1 : P_1 + T_0 : 0, where T
175 * = T_1 : T_0 = g*(x) * P_0. Thus, bits 0-63 got "folded" into bits 64-191.
176 *
177 * Repeating this same process on the next 64 bits "folds" bits 64-127 into bits
178 * 128-255, giving the answer in bits 128-255. This time, we need to cancel P_1
179 * + T_0 in bits 64-127. The multiple of g(x) required is (P_1 + T_0) * g(x) *
180 * x^64. Adding this to our previous computation gives P_3 + P_1 + T_0 + V_1 :
181 * P_2 + P_0 + T_1 + V_0 : 0 : 0, where V = V_1 : V_0 = g*(x) * (P_1 + T_0).
182 *
183 * So our final computation is:
184 * T = T_1 : T_0 = g*(x) * P_0
185 * V = V_1 : V_0 = g*(x) * (P_1 + T_0)
186 * p(x) / x^{128} mod g(x) = P_3 + P_1 + T_0 + V_1 : P_2 + P_0 + T_1 + V_0
187 *
188 * The implementation below saves a XOR instruction by computing P_1 + T_0 : P_0
189 * + T_1 and XORing into dest, rather than separately XORing P_1 : P_0 and T_0 :
190 * T_1 into dest. This allows us to reuse P_1 + T_0 when computing V.
191 */
192 .macro montgomery_reduction dest
193 DEST .req \dest
194 // TMP_V = T_1 : T_0 = P_0 * g*(x)
195 pmull TMP_V.1q, PL.1d, GSTAR.1d
196 // TMP_V = T_0 : T_1
197 ext TMP_V.16b, TMP_V.16b, TMP_V.16b, #8
198 // TMP_V = P_1 + T_0 : P_0 + T_1
199 eor TMP_V.16b, PL.16b, TMP_V.16b
200 // PH = P_3 + P_1 + T_0 : P_2 + P_0 + T_1
201 eor PH.16b, PH.16b, TMP_V.16b
202 // TMP_V = V_1 : V_0 = (P_1 + T_0) * g*(x)
203 pmull2 TMP_V.1q, TMP_V.2d, GSTAR.2d
204 eor DEST.16b, PH.16b, TMP_V.16b
205 .unreq DEST
206 .endm
207
208 /*
209 * Compute Polyval on 8 blocks.
210 *
211 * If reduce is set, also computes the montgomery reduction of the
212 * previous full_stride call and XORs with the first message block.
213 * (m_0 + REDUCE(PL, PH))h^8 + ... + m_7h^1.
214 * I.e., the first multiplication uses m_0 + REDUCE(PL, PH) instead of m_0.
215 *
216 * Sets PL, PH.
217 */
218 .macro full_stride reduce
219 eor LO.16b, LO.16b, LO.16b
220 eor MI.16b, MI.16b, MI.16b
221 eor HI.16b, HI.16b, HI.16b
222
223 ld1 {M0.16b, M1.16b, M2.16b, M3.16b}, [MSG], #64
224 ld1 {M4.16b, M5.16b, M6.16b, M7.16b}, [MSG], #64
225
226 karatsuba1 M7 KEY1
227 .if \reduce
228 pmull TMP_V.1q, PL.1d, GSTAR.1d
229 .endif
230
231 karatsuba1 M6 KEY2
232 .if \reduce
233 ext TMP_V.16b, TMP_V.16b, TMP_V.16b, #8
234 .endif
235
236 karatsuba1 M5 KEY3
237 .if \reduce
238 eor TMP_V.16b, PL.16b, TMP_V.16b
239 .endif
240
241 karatsuba1 M4 KEY4
242 .if \reduce
243 eor PH.16b, PH.16b, TMP_V.16b
244 .endif
245
246 karatsuba1 M3 KEY5
247 .if \reduce
248 pmull2 TMP_V.1q, TMP_V.2d, GSTAR.2d
249 .endif
250
251 karatsuba1 M2 KEY6
252 .if \reduce
253 eor SUM.16b, PH.16b, TMP_V.16b
254 .endif
255
256 karatsuba1 M1 KEY7
257 eor M0.16b, M0.16b, SUM.16b
258
259 karatsuba1 M0 KEY8
260 karatsuba2
261 .endm
262
263 /*
264 * Handle any extra blocks after full_stride loop.
265 */
266 .macro partial_stride
267 add KEY_POWERS, KEY_START, #(STRIDE_BLOCKS << 4)
268 sub KEY_POWERS, KEY_POWERS, BLOCKS_LEFT, lsl #4
269 ld1 {KEY1.16b}, [KEY_POWERS], #16
270
271 ld1 {TMP_V.16b}, [MSG], #16
272 eor SUM.16b, SUM.16b, TMP_V.16b
273 karatsuba1_store KEY1 SUM
274 sub BLOCKS_LEFT, BLOCKS_LEFT, #1
275
276 tst BLOCKS_LEFT, #4
277 beq .Lpartial4BlocksDone
278 ld1 {M0.16b, M1.16b, M2.16b, M3.16b}, [MSG], #64
279 ld1 {KEY8.16b, KEY7.16b, KEY6.16b, KEY5.16b}, [KEY_POWERS], #64
280 karatsuba1 M0 KEY8
281 karatsuba1 M1 KEY7
282 karatsuba1 M2 KEY6
283 karatsuba1 M3 KEY5
284 .Lpartial4BlocksDone:
285 tst BLOCKS_LEFT, #2
286 beq .Lpartial2BlocksDone
287 ld1 {M0.16b, M1.16b}, [MSG], #32
288 ld1 {KEY8.16b, KEY7.16b}, [KEY_POWERS], #32
289 karatsuba1 M0 KEY8
290 karatsuba1 M1 KEY7
291 .Lpartial2BlocksDone:
292 tst BLOCKS_LEFT, #1
293 beq .LpartialDone
294 ld1 {M0.16b}, [MSG], #16
295 ld1 {KEY8.16b}, [KEY_POWERS], #16
296 karatsuba1 M0 KEY8
297 .LpartialDone:
298 karatsuba2
299 montgomery_reduction SUM
300 .endm
301
302 /*
303 * Perform montgomery multiplication in GF(2^128) and store result in op1.
304 *
305 * Computes op1*op2*x^{-128} mod x^128 + x^127 + x^126 + x^121 + 1
306 * If op1, op2 are in montgomery form, this computes the montgomery
307 * form of op1*op2.
308 *
309 * void pmull_polyval_mul(u8 *op1, const u8 *op2);
310 */
311 SYM_FUNC_START(pmull_polyval_mul)
312 adr TMP, .Lgstar
313 ld1 {GSTAR.2d}, [TMP]
314 ld1 {v0.16b}, [x0]
315 ld1 {v1.16b}, [x1]
316 karatsuba1_store v0 v1
317 karatsuba2
318 montgomery_reduction SUM
319 st1 {SUM.16b}, [x0]
320 ret
321 SYM_FUNC_END(pmull_polyval_mul)
322
323 /*
324 * Perform polynomial evaluation as specified by POLYVAL. This computes:
325 * h^n * accumulator + h^n * m_0 + ... + h^1 * m_{n-1}
326 * where n=nblocks, h is the hash key, and m_i are the message blocks.
327 *
328 * x0 - pointer to precomputed key powers h^8 ... h^1
329 * x1 - pointer to message blocks
330 * x2 - number of blocks to hash
331 * x3 - pointer to accumulator
332 *
333 * void pmull_polyval_update(const struct polyval_ctx *ctx, const u8 *in,
334 * size_t nblocks, u8 *accumulator);
335 */
336 SYM_FUNC_START(pmull_polyval_update)
337 adr TMP, .Lgstar
338 mov KEY_START, KEY_POWERS
339 ld1 {GSTAR.2d}, [TMP]
340 ld1 {SUM.16b}, [ACCUMULATOR]
341 subs BLOCKS_LEFT, BLOCKS_LEFT, #STRIDE_BLOCKS
342 blt .LstrideLoopExit
343 ld1 {KEY8.16b, KEY7.16b, KEY6.16b, KEY5.16b}, [KEY_POWERS], #64
344 ld1 {KEY4.16b, KEY3.16b, KEY2.16b, KEY1.16b}, [KEY_POWERS], #64
345 full_stride 0
346 subs BLOCKS_LEFT, BLOCKS_LEFT, #STRIDE_BLOCKS
347 blt .LstrideLoopExitReduce
348 .LstrideLoop:
349 full_stride 1
350 subs BLOCKS_LEFT, BLOCKS_LEFT, #STRIDE_BLOCKS
351 bge .LstrideLoop
352 .LstrideLoopExitReduce:
353 montgomery_reduction SUM
354 .LstrideLoopExit:
355 adds BLOCKS_LEFT, BLOCKS_LEFT, #STRIDE_BLOCKS
356 beq .LskipPartial
357 partial_stride
358 .LskipPartial:
359 st1 {SUM.16b}, [ACCUMULATOR]
360 ret
361 SYM_FUNC_END(pmull_polyval_update)
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.