summaryrefslogtreecommitdiff
path: root/libavb/avb_rsa.c (plain)
blob: dcecc1697347e21917294bdebc62ff3d180854fb
1/*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Permission is hereby granted, free of charge, to any person
5 * obtaining a copy of this software and associated documentation
6 * files (the "Software"), to deal in the Software without
7 * restriction, including without limitation the rights to use, copy,
8 * modify, merge, publish, distribute, sublicense, and/or sell copies
9 * of the Software, and to permit persons to whom the Software is
10 * furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 * SOFTWARE.
23 */
24
25/* Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
26 * Use of this source code is governed by a BSD-style license that can be
27 * found in the LICENSE file.
28 */
29
30/* Implementation of RSA signature verification which uses a pre-processed
31 * key for computation. The code extends libmincrypt RSA verification code to
32 * support multiple RSA key lengths and hash digest algorithms.
33 */
34
35#include "avb_rsa.h"
36#include "avb_sha.h"
37#include "avb_util.h"
38#include "avb_vbmeta_image.h"
39
40typedef struct Key {
41 unsigned int len; /* Length of n[] in number of uint32_t */
42 uint32_t n0inv; /* -1 / n[0] mod 2^32 */
43 uint32_t* n; /* modulus as array (host-byte order) */
44 uint32_t* rr; /* R^2 as array (host-byte order) */
45} Key;
46
47Key* parse_key_data(const uint8_t* data, size_t length) {
48 AvbRSAPublicKeyHeader h;
49 Key* key = NULL;
50 size_t expected_length;
51 unsigned int i;
52 const uint8_t* n;
53 const uint8_t* rr;
54
55 if (!avb_rsa_public_key_header_validate_and_byteswap(
56 (const AvbRSAPublicKeyHeader*)data, &h)) {
57 avb_error("Invalid key.\n");
58 goto fail;
59 }
60
61 if (!(h.key_num_bits == 2048 || h.key_num_bits == 4096 ||
62 h.key_num_bits == 8192)) {
63 avb_error("Unexpected key length.\n");
64 goto fail;
65 }
66
67 expected_length = sizeof(AvbRSAPublicKeyHeader) + 2 * h.key_num_bits / 8;
68 if (length != expected_length) {
69 avb_error("Key does not match expected length.\n");
70 goto fail;
71 }
72
73 n = data + sizeof(AvbRSAPublicKeyHeader);
74 rr = data + sizeof(AvbRSAPublicKeyHeader) + h.key_num_bits / 8;
75
76 /* Store n and rr following the key header so we only have to do one
77 * allocation.
78 */
79 key = (Key*)(avb_malloc(sizeof(Key) + 2 * h.key_num_bits / 8));
80 if (key == NULL) {
81 goto fail;
82 }
83
84 key->len = h.key_num_bits / 32;
85 key->n0inv = h.n0inv;
86 key->n = (uint32_t*)(key + 1); /* Skip ahead sizeof(Key) bytes. */
87 key->rr = key->n + key->len;
88
89 /* Crypto-code below (modpowF4() and friends) expects the key in
90 * little-endian format (rather than the format we're storing the
91 * key in), so convert it.
92 */
93 for (i = 0; i < key->len; i++) {
94 key->n[i] = avb_be32toh(((uint32_t*)n)[key->len - i - 1]);
95 key->rr[i] = avb_be32toh(((uint32_t*)rr)[key->len - i - 1]);
96 }
97 return key;
98
99fail:
100 if (key != NULL) {
101 avb_free(key);
102 }
103 return NULL;
104}
105
106void free_parsed_key(Key* key) {
107 avb_free(key);
108}
109
110/* a[] -= mod */
111static void subM(const Key* key, uint32_t* a) {
112 int64_t A = 0;
113 uint32_t i;
114 for (i = 0; i < key->len; ++i) {
115 A += (uint64_t)a[i] - key->n[i];
116 a[i] = (uint32_t)A;
117 A >>= 32;
118 }
119}
120
121/* return a[] >= mod */
122static int geM(const Key* key, uint32_t* a) {
123 uint32_t i;
124 for (i = key->len; i;) {
125 --i;
126 if (a[i] < key->n[i]) {
127 return 0;
128 }
129 if (a[i] > key->n[i]) {
130 return 1;
131 }
132 }
133 return 1; /* equal */
134}
135
136/* montgomery c[] += a * b[] / R % mod */
137static void montMulAdd(const Key* key,
138 uint32_t* c,
139 const uint32_t a,
140 const uint32_t* b) {
141 uint64_t A = (uint64_t)a * b[0] + c[0];
142 uint32_t d0 = (uint32_t)A * key->n0inv;
143 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
144 uint32_t i;
145
146 for (i = 1; i < key->len; ++i) {
147 A = (A >> 32) + (uint64_t)a * b[i] + c[i];
148 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
149 c[i - 1] = (uint32_t)B;
150 }
151
152 A = (A >> 32) + (B >> 32);
153
154 c[i - 1] = (uint32_t)A;
155
156 if (A >> 32) {
157 subM(key, c);
158 }
159}
160
161/* montgomery c[] = a[] * b[] / R % mod */
162static void montMul(const Key* key, uint32_t* c, uint32_t* a, uint32_t* b) {
163 uint32_t i;
164 for (i = 0; i < key->len; ++i) {
165 c[i] = 0;
166 }
167 for (i = 0; i < key->len; ++i) {
168 montMulAdd(key, c, a[i], b);
169 }
170}
171
172/* In-place public exponentiation. (65537}
173 * Input and output big-endian byte array in inout.
174 */
175static void modpowF4(const Key* key, uint8_t* inout) {
176 uint32_t* a = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
177 uint32_t* aR = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
178 uint32_t* aaR = (uint32_t*)avb_malloc(key->len * sizeof(uint32_t));
179 if (a == NULL || aR == NULL || aaR == NULL) {
180 goto out;
181 }
182
183 uint32_t* aaa = aaR; /* Re-use location. */
184 int i;
185
186 /* Convert from big endian byte array to little endian word array. */
187 for (i = 0; i < (int)key->len; ++i) {
188 uint32_t tmp = (inout[((key->len - 1 - i) * 4) + 0] << 24) |
189 (inout[((key->len - 1 - i) * 4) + 1] << 16) |
190 (inout[((key->len - 1 - i) * 4) + 2] << 8) |
191 (inout[((key->len - 1 - i) * 4) + 3] << 0);
192 a[i] = tmp;
193 }
194
195 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */
196 for (i = 0; i < 16; i += 2) {
197 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
198 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */
199 }
200 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */
201
202 /* Make sure aaa < mod; aaa is at most 1x mod too large. */
203 if (geM(key, aaa)) {
204 subM(key, aaa);
205 }
206
207 /* Convert to bigendian byte array */
208 for (i = (int)key->len - 1; i >= 0; --i) {
209 uint32_t tmp = aaa[i];
210 *inout++ = (uint8_t)(tmp >> 24);
211 *inout++ = (uint8_t)(tmp >> 16);
212 *inout++ = (uint8_t)(tmp >> 8);
213 *inout++ = (uint8_t)(tmp >> 0);
214 }
215
216out:
217 if (a != NULL) {
218 avb_free(a);
219 }
220 if (aR != NULL) {
221 avb_free(aR);
222 }
223 if (aaR != NULL) {
224 avb_free(aaR);
225 }
226}
227
228/* Verify a RSA PKCS1.5 signature against an expected hash.
229 * Returns false on failure, true on success.
230 */
231bool avb_rsa_verify(const uint8_t* key,
232 size_t key_num_bytes,
233 const uint8_t* sig,
234 size_t sig_num_bytes,
235 const uint8_t* hash,
236 size_t hash_num_bytes,
237 const uint8_t* padding,
238 size_t padding_num_bytes) {
239 uint8_t* buf = NULL;
240 Key* parsed_key = NULL;
241 bool success = false;
242
243 if (key == NULL || sig == NULL || hash == NULL || padding == NULL) {
244 avb_error("Invalid input.\n");
245 goto out;
246 }
247
248 parsed_key = parse_key_data(key, key_num_bytes);
249 if (parsed_key == NULL) {
250 avb_error("Error parsing key.\n");
251 goto out;
252 }
253
254 if (sig_num_bytes != (parsed_key->len * sizeof(uint32_t))) {
255 avb_error("Signature length does not match key length.\n");
256 goto out;
257 }
258
259 if (padding_num_bytes != sig_num_bytes - hash_num_bytes) {
260 avb_error("Padding length does not match hash and signature lengths.\n");
261 goto out;
262 }
263
264 buf = (uint8_t*)avb_malloc(sig_num_bytes);
265 if (buf == NULL) {
266 avb_error("Error allocating memory.\n");
267 goto out;
268 }
269 avb_memcpy(buf, sig, sig_num_bytes);
270
271 modpowF4(parsed_key, buf);
272
273 /* Check padding bytes.
274 *
275 * Even though there are probably no timing issues here, we use
276 * avb_safe_memcmp() just to be on the safe side.
277 */
278 if (avb_safe_memcmp(buf, padding, padding_num_bytes)) {
279 avb_error("Padding check failed.\n");
280 goto out;
281 }
282
283 /* Check hash. */
284 if (avb_safe_memcmp(buf + padding_num_bytes, hash, hash_num_bytes)) {
285 avb_error("Hash check failed.\n");
286 goto out;
287 }
288
289 success = true;
290
291out:
292 if (parsed_key != NULL) {
293 free_parsed_key(parsed_key);
294 }
295 if (buf != NULL) {
296 avb_free(buf);
297 }
298 return success;
299}
300
generated by cgit at 2024-05-18 17:32:11 (GMT)