Mattias Nissler | b62146d | 2016-03-31 16:31:42 +0200 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2016 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #include <crypto_utils/android_pubkey.h> |
| 18 | |
| 19 | #include <assert.h> |
| 20 | #include <stdlib.h> |
| 21 | #include <string.h> |
| 22 | |
David Benjamin | 2257f6b | 2016-04-15 17:44:05 -0400 | [diff] [blame] | 23 | #include <openssl/bn.h> |
| 24 | |
Mattias Nissler | b62146d | 2016-03-31 16:31:42 +0200 | [diff] [blame] | 25 | // Better safe than sorry. |
| 26 | #if (ANDROID_PUBKEY_MODULUS_SIZE % 4) != 0 |
| 27 | #error RSA modulus size must be multiple of the word size! |
| 28 | #endif |
| 29 | |
| 30 | // Size of the RSA modulus in words. |
| 31 | #define ANDROID_PUBKEY_MODULUS_SIZE_WORDS (ANDROID_PUBKEY_MODULUS_SIZE / 4) |
| 32 | |
| 33 | // This file implements encoding and decoding logic for Android's custom RSA |
| 34 | // public key binary format. Public keys are stored as a sequence of |
| 35 | // little-endian 32 bit words. Note that Android only supports little-endian |
| 36 | // processors, so we don't do any byte order conversions when parsing the binary |
| 37 | // struct. |
| 38 | typedef struct RSAPublicKey { |
| 39 | // Modulus length. This must be ANDROID_PUBKEY_MODULUS_SIZE. |
| 40 | uint32_t modulus_size_words; |
| 41 | |
| 42 | // Precomputed montgomery parameter: -1 / n[0] mod 2^32 |
| 43 | uint32_t n0inv; |
| 44 | |
| 45 | // RSA modulus as a little-endian array. |
| 46 | uint8_t modulus[ANDROID_PUBKEY_MODULUS_SIZE]; |
| 47 | |
| 48 | // Montgomery parameter R^2 as a little-endian array of little-endian words. |
| 49 | uint8_t rr[ANDROID_PUBKEY_MODULUS_SIZE]; |
| 50 | |
| 51 | // RSA modulus: 3 or 65537 |
| 52 | uint32_t exponent; |
| 53 | } RSAPublicKey; |
| 54 | |
| 55 | // Reverses byte order in |buffer|. |
| 56 | static void reverse_bytes(uint8_t* buffer, size_t size) { |
| 57 | for (size_t i = 0; i < (size + 1) / 2; ++i) { |
| 58 | uint8_t tmp = buffer[i]; |
| 59 | buffer[i] = buffer[size - i - 1]; |
| 60 | buffer[size - i - 1] = tmp; |
| 61 | } |
| 62 | } |
| 63 | |
| 64 | bool android_pubkey_decode(const uint8_t* key_buffer, size_t size, RSA** key) { |
| 65 | const RSAPublicKey* key_struct = (RSAPublicKey*)key_buffer; |
| 66 | bool ret = false; |
| 67 | uint8_t modulus_buffer[ANDROID_PUBKEY_MODULUS_SIZE]; |
| 68 | RSA* new_key = RSA_new(); |
| 69 | if (!new_key) { |
| 70 | goto cleanup; |
| 71 | } |
| 72 | |
| 73 | // Check |size| is large enough and the modulus size is correct. |
| 74 | if (size < sizeof(RSAPublicKey)) { |
| 75 | goto cleanup; |
| 76 | } |
| 77 | if (key_struct->modulus_size_words != ANDROID_PUBKEY_MODULUS_SIZE_WORDS) { |
| 78 | goto cleanup; |
| 79 | } |
| 80 | |
| 81 | // Convert the modulus to big-endian byte order as expected by BN_bin2bn. |
| 82 | memcpy(modulus_buffer, key_struct->modulus, sizeof(modulus_buffer)); |
| 83 | reverse_bytes(modulus_buffer, sizeof(modulus_buffer)); |
| 84 | new_key->n = BN_bin2bn(modulus_buffer, sizeof(modulus_buffer), NULL); |
| 85 | if (!new_key->n) { |
| 86 | goto cleanup; |
| 87 | } |
| 88 | |
| 89 | // Read the exponent. |
| 90 | new_key->e = BN_new(); |
| 91 | if (!new_key->e || !BN_set_word(new_key->e, key_struct->exponent)) { |
| 92 | goto cleanup; |
| 93 | } |
| 94 | |
| 95 | // Note that we don't extract the montgomery parameters n0inv and rr from |
| 96 | // the RSAPublicKey structure. They assume a word size of 32 bits, but |
| 97 | // BoringSSL may use a word size of 64 bits internally, so we're lacking the |
| 98 | // top 32 bits of n0inv in general. For now, we just ignore the parameters |
| 99 | // and have BoringSSL recompute them internally. More sophisticated logic can |
| 100 | // be added here if/when we want the additional speedup from using the |
| 101 | // pre-computed montgomery parameters. |
| 102 | |
| 103 | *key = new_key; |
| 104 | ret = true; |
| 105 | |
| 106 | cleanup: |
| 107 | if (!ret && new_key) { |
| 108 | RSA_free(new_key); |
| 109 | } |
| 110 | return ret; |
| 111 | } |
| 112 | |
| 113 | static bool android_pubkey_encode_bignum(const BIGNUM* num, uint8_t* buffer) { |
| 114 | if (!BN_bn2bin_padded(buffer, ANDROID_PUBKEY_MODULUS_SIZE, num)) { |
| 115 | return false; |
| 116 | } |
| 117 | |
| 118 | reverse_bytes(buffer, ANDROID_PUBKEY_MODULUS_SIZE); |
| 119 | return true; |
| 120 | } |
| 121 | |
| 122 | bool android_pubkey_encode(const RSA* key, uint8_t* key_buffer, size_t size) { |
| 123 | RSAPublicKey* key_struct = (RSAPublicKey*)key_buffer; |
| 124 | bool ret = false; |
| 125 | BN_CTX* ctx = BN_CTX_new(); |
| 126 | BIGNUM* r32 = BN_new(); |
| 127 | BIGNUM* n0inv = BN_new(); |
| 128 | BIGNUM* rr = BN_new(); |
| 129 | |
| 130 | if (sizeof(RSAPublicKey) > size || |
| 131 | RSA_size(key) != ANDROID_PUBKEY_MODULUS_SIZE) { |
| 132 | goto cleanup; |
| 133 | } |
| 134 | |
| 135 | // Store the modulus size. |
| 136 | key_struct->modulus_size_words = ANDROID_PUBKEY_MODULUS_SIZE_WORDS; |
| 137 | |
| 138 | // Compute and store n0inv = -1 / N[0] mod 2^32. |
| 139 | if (!ctx || !r32 || !n0inv || !BN_set_bit(r32, 32) || |
| 140 | !BN_mod(n0inv, key->n, r32, ctx) || |
| 141 | !BN_mod_inverse(n0inv, n0inv, r32, ctx) || !BN_sub(n0inv, r32, n0inv)) { |
| 142 | goto cleanup; |
| 143 | } |
| 144 | key_struct->n0inv = (uint32_t)BN_get_word(n0inv); |
| 145 | |
| 146 | // Store the modulus. |
| 147 | if (!android_pubkey_encode_bignum(key->n, key_struct->modulus)) { |
| 148 | goto cleanup; |
| 149 | } |
| 150 | |
| 151 | // Compute and store rr = (2^(rsa_size)) ^ 2 mod N. |
| 152 | if (!ctx || !rr || !BN_set_bit(rr, ANDROID_PUBKEY_MODULUS_SIZE * 8) || |
| 153 | !BN_mod_sqr(rr, rr, key->n, ctx) || |
| 154 | !android_pubkey_encode_bignum(rr, key_struct->rr)) { |
| 155 | goto cleanup; |
| 156 | } |
| 157 | |
| 158 | // Store the exponent. |
| 159 | key_struct->exponent = (uint32_t)BN_get_word(key->e); |
| 160 | |
| 161 | ret = true; |
| 162 | |
| 163 | cleanup: |
| 164 | BN_free(rr); |
| 165 | BN_free(n0inv); |
| 166 | BN_free(r32); |
| 167 | BN_CTX_free(ctx); |
| 168 | return ret; |
| 169 | } |