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 */
18static 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 */
29static 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 */
40static 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 */
65static 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 */
81static 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 */
130int 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