1 // SPDX-License-Identifier: GPL-2.0+ 2 /* 3 * Copyright (c) 2013, Google Inc. 4 */ 5 6 #ifndef USE_HOSTCC 7 #include <common.h> 8 #include <fdtdec.h> 9 #include <asm/types.h> 10 #include <asm/byteorder.h> 11 #include <linux/errno.h> 12 #include <asm/types.h> 13 #include <asm/unaligned.h> 14 #else 15 #include "fdt_host.h" 16 #include "mkimage.h" 17 #include <fdt_support.h> 18 #endif 19 #include <u-boot/rsa.h> 20 #include <u-boot/rsa-mod-exp.h> 21 22 #define UINT64_MULT32(v, multby) (((uint64_t)(v)) * ((uint32_t)(multby))) 23 24 #define get_unaligned_be32(a) fdt32_to_cpu(*(uint32_t *)a) 25 #define put_unaligned_be32(a, b) (*(uint32_t *)(b) = cpu_to_fdt32(a)) 26 27 /* Default public exponent for backward compatibility */ 28 #define RSA_DEFAULT_PUBEXP 65537 29 30 /** 31 * subtract_modulus() - subtract modulus from the given value 32 * 33 * @key: Key containing modulus to subtract 34 * @num: Number to subtract modulus from, as little endian word array 35 */ 36 static void subtract_modulus(const struct rsa_public_key *key, uint32_t num[]) 37 { 38 int64_t acc = 0; 39 uint i; 40 41 for (i = 0; i < key->len; i++) { 42 acc += (uint64_t)num[i] - key->modulus[i]; 43 num[i] = (uint32_t)acc; 44 acc >>= 32; 45 } 46 } 47 48 /** 49 * greater_equal_modulus() - check if a value is >= modulus 50 * 51 * @key: Key containing modulus to check 52 * @num: Number to check against modulus, as little endian word array 53 * @return 0 if num < modulus, 1 if num >= modulus 54 */ 55 static int greater_equal_modulus(const struct rsa_public_key *key, 56 uint32_t num[]) 57 { 58 int i; 59 60 for (i = (int)key->len - 1; i >= 0; i--) { 61 if (num[i] < key->modulus[i]) 62 return 0; 63 if (num[i] > key->modulus[i]) 64 return 1; 65 } 66 67 return 1; /* equal */ 68 } 69 70 /** 71 * montgomery_mul_add_step() - Perform montgomery multiply-add step 72 * 73 * Operation: montgomery result[] += a * b[] / n0inv % modulus 74 * 75 * @key: RSA key 76 * @result: Place to put result, as little endian word array 77 * @a: Multiplier 78 * @b: Multiplicand, as little endian word array 79 */ 80 static void montgomery_mul_add_step(const struct rsa_public_key *key, 81 uint32_t result[], const uint32_t a, const uint32_t b[]) 82 { 83 uint64_t acc_a, acc_b; 84 uint32_t d0; 85 uint i; 86 87 acc_a = (uint64_t)a * b[0] + result[0]; 88 d0 = (uint32_t)acc_a * key->n0inv; 89 acc_b = (uint64_t)d0 * key->modulus[0] + (uint32_t)acc_a; 90 for (i = 1; i < key->len; i++) { 91 acc_a = (acc_a >> 32) + (uint64_t)a * b[i] + result[i]; 92 acc_b = (acc_b >> 32) + (uint64_t)d0 * key->modulus[i] + 93 (uint32_t)acc_a; 94 result[i - 1] = (uint32_t)acc_b; 95 } 96 97 acc_a = (acc_a >> 32) + (acc_b >> 32); 98 99 result[i - 1] = (uint32_t)acc_a; 100 101 if (acc_a >> 32) 102 subtract_modulus(key, result); 103 } 104 105 /** 106 * montgomery_mul() - Perform montgomery mutitply 107 * 108 * Operation: montgomery result[] = a[] * b[] / n0inv % modulus 109 * 110 * @key: RSA key 111 * @result: Place to put result, as little endian word array 112 * @a: Multiplier, as little endian word array 113 * @b: Multiplicand, as little endian word array 114 */ 115 static void montgomery_mul(const struct rsa_public_key *key, 116 uint32_t result[], uint32_t a[], const uint32_t b[]) 117 { 118 uint i; 119 120 for (i = 0; i < key->len; ++i) 121 result[i] = 0; 122 for (i = 0; i < key->len; ++i) 123 montgomery_mul_add_step(key, result, a[i], b); 124 } 125 126 /** 127 * num_pub_exponent_bits() - Number of bits in the public exponent 128 * 129 * @key: RSA key 130 * @num_bits: Storage for the number of public exponent bits 131 */ 132 static int num_public_exponent_bits(const struct rsa_public_key *key, 133 int *num_bits) 134 { 135 uint64_t exponent; 136 int exponent_bits; 137 const uint max_bits = (sizeof(exponent) * 8); 138 139 exponent = key->exponent; 140 exponent_bits = 0; 141 142 if (!exponent) { 143 *num_bits = exponent_bits; 144 return 0; 145 } 146 147 for (exponent_bits = 1; exponent_bits < max_bits + 1; ++exponent_bits) 148 if (!(exponent >>= 1)) { 149 *num_bits = exponent_bits; 150 return 0; 151 } 152 153 return -EINVAL; 154 } 155 156 /** 157 * is_public_exponent_bit_set() - Check if a bit in the public exponent is set 158 * 159 * @key: RSA key 160 * @pos: The bit position to check 161 */ 162 static int is_public_exponent_bit_set(const struct rsa_public_key *key, 163 int pos) 164 { 165 return key->exponent & (1ULL << pos); 166 } 167 168 /** 169 * pow_mod() - in-place public exponentiation 170 * 171 * @key: RSA key 172 * @inout: Big-endian word array containing value and result 173 */ 174 static int pow_mod(const struct rsa_public_key *key, uint32_t *inout) 175 { 176 uint32_t *result, *ptr; 177 uint i; 178 int j, k; 179 180 /* Sanity check for stack size - key->len is in 32-bit words */ 181 if (key->len > RSA_MAX_KEY_BITS / 32) { 182 debug("RSA key words %u exceeds maximum %d\n", key->len, 183 RSA_MAX_KEY_BITS / 32); 184 return -EINVAL; 185 } 186 187 uint32_t val[key->len], acc[key->len], tmp[key->len]; 188 uint32_t a_scaled[key->len]; 189 result = tmp; /* Re-use location. */ 190 191 /* Convert from big endian byte array to little endian word array. */ 192 for (i = 0, ptr = inout + key->len - 1; i < key->len; i++, ptr--) 193 val[i] = get_unaligned_be32(ptr); 194 195 if (0 != num_public_exponent_bits(key, &k)) 196 return -EINVAL; 197 198 if (k < 2) { 199 debug("Public exponent is too short (%d bits, minimum 2)\n", 200 k); 201 return -EINVAL; 202 } 203 204 if (!is_public_exponent_bit_set(key, 0)) { 205 debug("LSB of RSA public exponent must be set.\n"); 206 return -EINVAL; 207 } 208 209 /* the bit at e[k-1] is 1 by definition, so start with: C := M */ 210 montgomery_mul(key, acc, val, key->rr); /* acc = a * RR / R mod n */ 211 /* retain scaled version for intermediate use */ 212 memcpy(a_scaled, acc, key->len * sizeof(a_scaled[0])); 213 214 for (j = k - 2; j > 0; --j) { 215 montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */ 216 217 if (is_public_exponent_bit_set(key, j)) { 218 /* acc = tmp * val / R mod n */ 219 montgomery_mul(key, acc, tmp, a_scaled); 220 } else { 221 /* e[j] == 0, copy tmp back to acc for next operation */ 222 memcpy(acc, tmp, key->len * sizeof(acc[0])); 223 } 224 } 225 226 /* the bit at e[0] is always 1 */ 227 montgomery_mul(key, tmp, acc, acc); /* tmp = acc^2 / R mod n */ 228 montgomery_mul(key, acc, tmp, val); /* acc = tmp * a / R mod M */ 229 memcpy(result, acc, key->len * sizeof(result[0])); 230 231 /* Make sure result < mod; result is at most 1x mod too large. */ 232 if (greater_equal_modulus(key, result)) 233 subtract_modulus(key, result); 234 235 /* Convert to bigendian byte array */ 236 for (i = key->len - 1, ptr = inout; (int)i >= 0; i--, ptr++) 237 put_unaligned_be32(result[i], ptr); 238 return 0; 239 } 240 241 static void rsa_convert_big_endian(uint32_t *dst, const uint32_t *src, int len) 242 { 243 int i; 244 245 for (i = 0; i < len; i++) 246 dst[i] = fdt32_to_cpu(src[len - 1 - i]); 247 } 248 249 int rsa_mod_exp_sw(const uint8_t *sig, uint32_t sig_len, 250 struct key_prop *prop, uint8_t *out) 251 { 252 struct rsa_public_key key; 253 int ret; 254 255 if (!prop) { 256 debug("%s: Skipping invalid prop", __func__); 257 return -EBADF; 258 } 259 key.n0inv = prop->n0inv; 260 key.len = prop->num_bits; 261 262 if (!prop->public_exponent) 263 key.exponent = RSA_DEFAULT_PUBEXP; 264 else 265 key.exponent = 266 fdt64_to_cpu(*((uint64_t *)(prop->public_exponent))); 267 268 if (!key.len || !prop->modulus || !prop->rr) { 269 debug("%s: Missing RSA key info", __func__); 270 return -EFAULT; 271 } 272 273 /* Sanity check for stack size */ 274 if (key.len > RSA_MAX_KEY_BITS || key.len < RSA_MIN_KEY_BITS) { 275 debug("RSA key bits %u outside allowed range %d..%d\n", 276 key.len, RSA_MIN_KEY_BITS, RSA_MAX_KEY_BITS); 277 return -EFAULT; 278 } 279 key.len /= sizeof(uint32_t) * 8; 280 uint32_t key1[key.len], key2[key.len]; 281 282 key.modulus = key1; 283 key.rr = key2; 284 rsa_convert_big_endian(key.modulus, (uint32_t *)prop->modulus, key.len); 285 rsa_convert_big_endian(key.rr, (uint32_t *)prop->rr, key.len); 286 if (!key.modulus || !key.rr) { 287 debug("%s: Out of memory", __func__); 288 return -ENOMEM; 289 } 290 291 uint32_t buf[sig_len / sizeof(uint32_t)]; 292 293 memcpy(buf, sig, sig_len); 294 295 ret = pow_mod(&key, buf); 296 if (ret) 297 return ret; 298 299 memcpy(out, buf, sig_len); 300 301 return 0; 302 } 303