1 /* Copyright (c) 2011 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 /* Implementation of RSA signature verification which uses a pre-processed
7 * key for computation. The code extends Android's RSA verification code to
8 * support multiple RSA key lengths and hash digest algorithms.
9 */
10
11 #include "sysincludes.h"
12
13 #include "cryptolib.h"
14 #include "vboot_api.h"
15 #include "utility.h"
16
17 /* a[] -= mod */
subM(const RSAPublicKey * key,uint32_t * a)18 static void subM(const RSAPublicKey *key, uint32_t *a) {
19 int64_t A = 0;
20 uint32_t i;
21 for (i = 0; i < key->len; ++i) {
22 A += (uint64_t)a[i] - key->n[i];
23 a[i] = (uint32_t)A;
24 A >>= 32;
25 }
26 }
27
28 /* return a[] >= mod */
geM(const RSAPublicKey * key,uint32_t * a)29 static int geM(const RSAPublicKey *key, uint32_t *a) {
30 uint32_t i;
31 for (i = key->len; i;) {
32 --i;
33 if (a[i] < key->n[i]) return 0;
34 if (a[i] > key->n[i]) return 1;
35 }
36 return 1; /* equal */
37 }
38
39 /* montgomery c[] += a * b[] / R % mod */
montMulAdd(const RSAPublicKey * key,uint32_t * c,const uint32_t a,const uint32_t * b)40 static void montMulAdd(const RSAPublicKey *key,
41 uint32_t* c,
42 const uint32_t a,
43 const uint32_t* b) {
44 uint64_t A = (uint64_t)a * b[0] + c[0];
45 uint32_t d0 = (uint32_t)A * key->n0inv;
46 uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A;
47 uint32_t i;
48
49 for (i = 1; i < key->len; ++i) {
50 A = (A >> 32) + (uint64_t)a * b[i] + c[i];
51 B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A;
52 c[i - 1] = (uint32_t)B;
53 }
54
55 A = (A >> 32) + (B >> 32);
56
57 c[i - 1] = (uint32_t)A;
58
59 if (A >> 32) {
60 subM(key, c);
61 }
62 }
63
64 /* montgomery c[] = a[] * b[] / R % mod */
montMul(const RSAPublicKey * key,uint32_t * c,uint32_t * a,uint32_t * b)65 static void montMul(const RSAPublicKey *key,
66 uint32_t* c,
67 uint32_t* a,
68 uint32_t* b) {
69 uint32_t i;
70 for (i = 0; i < key->len; ++i) {
71 c[i] = 0;
72 }
73 for (i = 0; i < key->len; ++i) {
74 montMulAdd(key, c, a[i], b);
75 }
76 }
77
78 /* In-place public exponentiation. (65537}
79 * Input and output big-endian byte array in inout.
80 */
modpowF4(const RSAPublicKey * key,uint8_t * inout)81 static void modpowF4(const RSAPublicKey *key,
82 uint8_t* inout) {
83 uint32_t* a = (uint32_t*) VbExMalloc(key->len * sizeof(uint32_t));
84 uint32_t* aR = (uint32_t*) VbExMalloc(key->len * sizeof(uint32_t));
85 uint32_t* aaR = (uint32_t*) VbExMalloc(key->len * sizeof(uint32_t));
86
87 uint32_t* aaa = aaR; /* Re-use location. */
88 int i;
89
90 /* Convert from big endian byte array to little endian word array. */
91 for (i = 0; i < (int)key->len; ++i) {
92 uint32_t tmp =
93 (inout[((key->len - 1 - i) * 4) + 0] << 24) |
94 (inout[((key->len - 1 - i) * 4) + 1] << 16) |
95 (inout[((key->len - 1 - i) * 4) + 2] << 8) |
96 (inout[((key->len - 1 - i) * 4) + 3] << 0);
97 a[i] = tmp;
98 }
99
100 montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */
101 for (i = 0; i < 16; i+=2) {
102 montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */
103 montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */
104 }
105 montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */
106
107
108 /* Make sure aaa < mod; aaa is at most 1x mod too large. */
109 if (geM(key, aaa)) {
110 subM(key, aaa);
111 }
112
113 /* Convert to bigendian byte array */
114 for (i = (int)key->len - 1; i >= 0; --i) {
115 uint32_t tmp = aaa[i];
116 *inout++ = (uint8_t)(tmp >> 24);
117 *inout++ = (uint8_t)(tmp >> 16);
118 *inout++ = (uint8_t)(tmp >> 8);
119 *inout++ = (uint8_t)(tmp >> 0);
120 }
121
122 VbExFree(a);
123 VbExFree(aR);
124 VbExFree(aaR);
125 }
126
127 /* Verify a RSA PKCS1.5 signature against an expected hash.
128 * Returns 0 on failure, 1 on success.
129 */
RSAVerify(const RSAPublicKey * key,const uint8_t * sig,const uint32_t sig_len,const uint8_t sig_type,const uint8_t * hash)130 int RSAVerify(const RSAPublicKey *key,
131 const uint8_t *sig,
132 const uint32_t sig_len,
133 const uint8_t sig_type,
134 const uint8_t *hash) {
135 uint8_t* buf;
136 const uint8_t* padding;
137 int padding_len;
138 int success = 1;
139
140 if (!key || !sig || !hash)
141 return 0;
142
143 if (sig_len != (key->len * sizeof(uint32_t))) {
144 VBDEBUG(("Signature is of incorrect length!\n"));
145 return 0;
146 }
147
148 if (sig_type >= kNumAlgorithms) {
149 VBDEBUG(("Invalid signature type!\n"));
150 return 0;
151 }
152
153 if (key->len != siglen_map[sig_type] / sizeof(uint32_t)) {
154 VBDEBUG(("Wrong key passed in!\n"));
155 return 0;
156 }
157
158 buf = (uint8_t*) VbExMalloc(sig_len);
159 if (!buf)
160 return 0;
161 Memcpy(buf, sig, sig_len);
162
163 modpowF4(key, buf);
164
165 /* Determine padding to use depending on the signature type. */
166 padding = padding_map[sig_type];
167 padding_len = padding_size_map[sig_type];
168
169 /* Even though there are probably no timing issues here, we use
170 * SafeMemcmp() just to be on the safe side. */
171
172 /* Check pkcs1.5 padding bytes. */
173 if (SafeMemcmp(buf, padding, padding_len)) {
174 VBDEBUG(("In RSAVerify(): Padding check failed!\n"));
175 success = 0;
176 }
177
178 /* Check hash. */
179 if (SafeMemcmp(buf + padding_len, hash, sig_len - padding_len)) {
180 VBDEBUG(("In RSAVerify(): Hash check failed!\n"));
181 success = 0;
182 }
183 VbExFree(buf);
184
185 return success;
186 }
187