7862b1334984036548a02995199d5a3e74c34f81
[akaros.git] / kern / lib / crypto / 2rsa.c
1 /* Copyright (c) 2014 The Chromium OS Authors. All rights reserved.
2  * Use of this source code is governed by a BSD-style license that can be
3  * found in the LICENSE file.
4  */
5
6 /*
7  * Implementation of RSA signature verification which uses a pre-processed key
8  * for computation. The code extends Android's RSA verification code to support
9  * multiple RSA key lengths and hash digest algorithms.
10  */
11
12 #include "2sysincludes.h"
13 #include "2common.h"
14 #include "2rsa.h"
15 #include "2sha.h"
16
17 /**
18  * a[] -= mod
19  */
20 static void subM(const struct vb2_public_key *key, uint32_t *a)
21 {
22         int64_t A = 0;
23         uint32_t i;
24         for (i = 0; i < key->arrsize; ++i) {
25                 A += (uint64_t)a[i] - key->n[i];
26                 a[i] = (uint32_t)A;
27                 A >>= 32;
28         }
29 }
30
31 /**
32  * Return a[] >= mod
33  */
34 int vb2_mont_ge(const struct vb2_public_key *key, uint32_t *a)
35 {
36         uint32_t i;
37         for (i = key->arrsize; i;) {
38                 --i;
39                 if (a[i] < key->n[i])
40                         return 0;
41                 if (a[i] > key->n[i])
42                         return 1;
43         }
44         return 1;  /* equal */
45 }
46
47 /**
48  * Montgomery c[] += a * b[] / R % mod
49  */
50 static void montMulAdd(const struct vb2_public_key *key,
51                        uint32_t *c,
52                        const uint32_t a,
53                        const uint32_t *b)
54 {
55         uint64_t A = (uint64_t)a * b[0] + c[0];
56         uint32_t d0 = (uint32_t)A * key->n0inv;
57         uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
58         uint32_t i;
59
60         for (i = 1; i < key->arrsize; ++i) {
61                 A = (A >> 32) + (uint64_t)a * b[i] + c[i];
62                 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
63                 c[i - 1] = (uint32_t)B;
64         }
65
66         A = (A >> 32) + (B >> 32);
67
68         c[i - 1] = (uint32_t)A;
69
70         if (A >> 32) {
71                 subM(key, c);
72         }
73 }
74
75 /**
76  * Montgomery c[] = a[] * b[] / R % mod
77  */
78 static void montMul(const struct vb2_public_key *key,
79                     uint32_t *c,
80                     const uint32_t *a,
81                     const uint32_t *b)
82 {
83         uint32_t i;
84         for (i = 0; i < key->arrsize; ++i) {
85                 c[i] = 0;
86         }
87         for (i = 0; i < key->arrsize; ++i) {
88                 montMulAdd(key, c, a[i], b);
89         }
90 }
91
92 /**
93  * In-place public exponentiation. (65537}
94  *
95  * @param key           Key to use in signing
96  * @param inout         Input and output big-endian byte array
97  * @param workbuf32     Work buffer; caller must verify this is
98  *                      (3 * key->arrsize) elements long.
99  */
100 static void modpowF4(const struct vb2_public_key *key, uint8_t *inout,
101                     uint32_t *workbuf32)
102 {
103         uint32_t *a = workbuf32;
104         uint32_t *aR = a + key->arrsize;
105         uint32_t *aaR = aR + key->arrsize;
106         uint32_t *aaa = aaR;  /* Re-use location. */
107         int i;
108
109         /* Convert from big endian byte array to little endian word array. */
110         for (i = 0; i < (int)key->arrsize; ++i) {
111                 uint32_t tmp =
112                         (inout[((key->arrsize - 1 - i) * 4) + 0] << 24) |
113                         (inout[((key->arrsize - 1 - i) * 4) + 1] << 16) |
114                         (inout[((key->arrsize - 1 - i) * 4) + 2] << 8) |
115                         (inout[((key->arrsize - 1 - i) * 4) + 3] << 0);
116                 a[i] = tmp;
117         }
118
119         montMul(key, aR, a, key->rr);  /* aR = a * RR / R mod M   */
120         for (i = 0; i < 16; i+=2) {
121                 montMul(key, aaR, aR, aR);  /* aaR = aR * aR / R mod M */
122                 montMul(key, aR, aaR, aaR);  /* aR = aaR * aaR / R mod M */
123         }
124         montMul(key, aaa, aR, a);  /* aaa = aR * a / R mod M */
125
126
127         /* Make sure aaa < mod; aaa is at most 1x mod too large. */
128         if (vb2_mont_ge(key, aaa)) {
129                 subM(key, aaa);
130         }
131
132         /* Convert to bigendian byte array */
133         for (i = (int)key->arrsize - 1; i >= 0; --i) {
134                 uint32_t tmp = aaa[i];
135                 *inout++ = (uint8_t)(tmp >> 24);
136                 *inout++ = (uint8_t)(tmp >> 16);
137                 *inout++ = (uint8_t)(tmp >>  8);
138                 *inout++ = (uint8_t)(tmp >>  0);
139         }
140 }
141
142
143 static const uint8_t crypto_to_sig[] = {
144         VB2_SIG_RSA1024,
145         VB2_SIG_RSA1024,
146         VB2_SIG_RSA1024,
147         VB2_SIG_RSA2048,
148         VB2_SIG_RSA2048,
149         VB2_SIG_RSA2048,
150         VB2_SIG_RSA4096,
151         VB2_SIG_RSA4096,
152         VB2_SIG_RSA4096,
153         VB2_SIG_RSA8192,
154         VB2_SIG_RSA8192,
155         VB2_SIG_RSA8192,
156 };
157
158 /**
159  * Convert vb2_crypto_algorithm to vb2_signature_algorithm.
160  *
161  * @param algorithm     Crypto algorithm (vb2_crypto_algorithm)
162  *
163  * @return The signature algorithm for that crypto algorithm, or
164  * VB2_SIG_INVALID if the crypto algorithm or its corresponding signature
165  * algorithm is invalid or not supported.
166  */
167 enum vb2_signature_algorithm vb2_crypto_to_signature(uint32_t algorithm)
168 {
169         if (algorithm < ARRAY_SIZE(crypto_to_sig))
170                 return crypto_to_sig[algorithm];
171         else
172                 return VB2_SIG_INVALID;
173 }
174
175 uint32_t vb2_rsa_sig_size(enum vb2_signature_algorithm sig_alg)
176 {
177         switch (sig_alg) {
178         case VB2_SIG_RSA1024:
179                 return 1024 / 8;
180         case VB2_SIG_RSA2048:
181                 return 2048 / 8;
182         case VB2_SIG_RSA4096:
183                 return 4096 / 8;
184         case VB2_SIG_RSA8192:
185                 return 8192 / 8;
186         default:
187                 return 0;
188         }
189 }
190
191 uint32_t vb2_packed_key_size(enum vb2_signature_algorithm sig_alg)
192 {
193         uint32_t sig_size = vb2_rsa_sig_size(sig_alg);
194
195         if (!sig_size)
196                 return 0;
197
198         /*
199          * Total size needed by a RSAPublicKey buffer is =
200          *  2 * key_len bytes for the n and rr arrays
201          *  + sizeof len + sizeof n0inv.
202          */
203         return 2 * sig_size + 2 * sizeof(uint32_t);
204 }
205
206 /*
207  * PKCS 1.5 padding (from the RSA PKCS#1 v2.1 standard)
208  *
209  * Depending on the RSA key size and hash function, the padding is calculated
210  * as follows:
211  *
212  * 0x00 || 0x01 || PS || 0x00 || T
213  *
214  * T: DER Encoded DigestInfo value which depends on the hash function used.
215  *
216  * SHA-1:   (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H.
217  * SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H.
218  * SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H.
219  *
220  * Length(T) = 35 octets for SHA-1
221  * Length(T) = 51 octets for SHA-256
222  * Length(T) = 83 octets for SHA-512
223  *
224  * PS: octet string consisting of {Length(RSA Key) - Length(T) - 3} 0xFF
225  */
226 static const uint8_t sha1_tail[] = {
227         0x00,0x30,0x21,0x30,0x09,0x06,0x05,0x2b,
228         0x0e,0x03,0x02,0x1a,0x05,0x00,0x04,0x14
229 };
230
231 static const uint8_t sha256_tail[] = {
232         0x00,0x30,0x31,0x30,0x0d,0x06,0x09,0x60,
233         0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x01,
234         0x05,0x00,0x04,0x20
235 };
236
237 static const uint8_t sha512_tail[] = {
238         0x00,0x30,0x51,0x30,0x0d,0x06,0x09,0x60,
239         0x86,0x48,0x01,0x65,0x03,0x04,0x02,0x03,
240         0x05,0x00,0x04,0x40
241 };
242
243 int vb2_check_padding(const uint8_t *sig, const struct vb2_public_key *key)
244 {
245         /* Determine padding to use depending on the signature type */
246         uint32_t sig_size = vb2_rsa_sig_size(key->sig_alg);
247         uint32_t hash_size = vb2_digest_size(key->hash_alg);
248         uint32_t pad_size = sig_size - hash_size;
249         const uint8_t *tail;
250         uint32_t tail_size;
251         int result = 0;
252         int i;
253
254         if (!sig_size || !hash_size || hash_size > sig_size)
255                 return VB2_ERROR_RSA_PADDING_SIZE;
256
257         switch (key->hash_alg) {
258         case VB2_HASH_SHA1:
259                 tail = sha1_tail;
260                 tail_size = sizeof(sha1_tail);
261                 break;
262         case VB2_HASH_SHA256:
263                 tail = sha256_tail;
264                 tail_size = sizeof(sha256_tail);
265                 break;
266         case VB2_HASH_SHA512:
267                 tail = sha512_tail;
268                 tail_size = sizeof(sha512_tail);
269                 break;
270         default:
271                 return VB2_ERROR_RSA_PADDING_ALGORITHM;
272         }
273
274         /* First 2 bytes are always 0x00 0x01 */
275         result |= *sig++ ^ 0x00;
276         result |= *sig++ ^ 0x01;
277
278         /* Then 0xff bytes until the tail */
279         for (i = 0; i < pad_size - tail_size - 2; i++)
280                 result |= *sig++ ^ 0xff;
281
282         /*
283          * Then the tail.  Even though there are probably no timing issues
284          * here, we use vb2_safe_memcmp() just to be on the safe side.
285          */
286         result |= vb2_safe_memcmp(sig, tail, tail_size);
287
288         return result ? VB2_ERROR_RSA_PADDING : VB2_SUCCESS;
289 }
290
291 int vb2_rsa_verify_digest(const struct vb2_public_key *key,
292                           uint8_t *sig,
293                           const uint8_t *digest,
294                           const struct vb2_workbuf *wb)
295 {
296         struct vb2_workbuf wblocal = *wb;
297         uint32_t *workbuf32;
298         uint32_t key_bytes;
299         int sig_size;
300         int pad_size;
301         int rv;
302
303         if (!key || !sig || !digest)
304                 return VB2_ERROR_RSA_VERIFY_PARAM;
305
306         sig_size = vb2_rsa_sig_size(key->sig_alg);
307         if (!sig_size) {
308                 VB2_DEBUG("Invalid signature type!\n");
309                 return VB2_ERROR_RSA_VERIFY_ALGORITHM;
310         }
311
312         /* Signature length should be same as key length */
313         key_bytes = key->arrsize * sizeof(uint32_t);
314         if (key_bytes != sig_size) {
315                 VB2_DEBUG("Signature is of incorrect length!\n");
316                 return VB2_ERROR_RSA_VERIFY_SIG_LEN;
317         }
318
319         workbuf32 = vb2_workbuf_alloc(&wblocal, 3 * key_bytes);
320         if (!workbuf32) {
321                 VB2_DEBUG("ERROR - vboot2 work buffer too small!\n");
322                 return VB2_ERROR_RSA_VERIFY_WORKBUF;
323         }
324
325         modpowF4(key, sig, workbuf32);
326
327         vb2_workbuf_free(&wblocal, 3 * key_bytes);
328
329         /*
330          * Check padding.  Only fail immediately if the padding size is bad.
331          * Otherwise, continue on to check the digest to reduce the risk of
332          * timing based attacks.
333          */
334         rv = vb2_check_padding(sig, key);
335         if (rv == VB2_ERROR_RSA_PADDING_SIZE)
336                 return rv;
337
338         /*
339          * Check digest.  Even though there are probably no timing issues here,
340          * use vb2_safe_memcmp() just to be on the safe side.  (That's also why
341          * we don't return before this check if the padding check failed.)
342          */
343         pad_size = sig_size - vb2_digest_size(key->hash_alg);
344         if (vb2_safe_memcmp(sig + pad_size, digest, key_bytes - pad_size)) {
345                 VB2_DEBUG("Digest check failed!\n");
346                 if (!rv)
347                         rv = VB2_ERROR_RSA_VERIFY_DIGEST;
348         }
349
350         return rv;
351 }