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 */
20static 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 */
34int 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 */
50static 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 */
78static 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 */
100static 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
143static 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 */
167enum 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
175uint32_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
191uint32_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 */
226static 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
231static 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
237static 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
243int 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
291int 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		return VB2_ERROR_RSA_VERIFY_WORKBUF;
322
323	modpowF4(key, sig, workbuf32);
324
325	vb2_workbuf_free(&wblocal, 3 * key_bytes);
326
327	/*
328	 * Check padding.  Only fail immediately if the padding size is bad.
329	 * Otherwise, continue on to check the digest to reduce the risk of
330	 * timing based attacks.
331	 */
332	rv = vb2_check_padding(sig, key);
333	if (rv == VB2_ERROR_RSA_PADDING_SIZE)
334		return rv;
335
336	/*
337	 * Check digest.  Even though there are probably no timing issues here,
338	 * use vb2_safe_memcmp() just to be on the safe side.  (That's also why
339	 * we don't return before this check if the padding check failed.)
340	 */
341	pad_size = sig_size - vb2_digest_size(key->hash_alg);
342	if (vb2_safe_memcmp(sig + pad_size, digest, key_bytes - pad_size)) {
343		VB2_DEBUG("Digest check failed!\n");
344		if (!rv)
345			rv = VB2_ERROR_RSA_VERIFY_DIGEST;
346	}
347
348	return rv;
349}
350