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 23 #include <openssl/bn.h> 24 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 } 170