1 // Copyright 2014 The Chromium 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 #include "chrome/browser/devtools/device/usb/android_rsa.h" 6 7 #include "base/base64.h" 8 #include "base/memory/scoped_ptr.h" 9 #include "chrome/browser/prefs/pref_service_syncable.h" 10 #include "chrome/browser/profiles/profile.h" 11 #include "chrome/common/pref_names.h" 12 #include "crypto/rsa_private_key.h" 13 #include "crypto/signature_creator.h" 14 #include "net/cert/asn1_util.h" 15 16 namespace { 17 18 const size_t kRSANumWords = 64; 19 const size_t kBigIntSize = 1024; 20 21 static const char kDummyRSAPublicKey[] = 22 "MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEA6OSJ64q+ZLg7VV2ojEPh5TRbYjwbT" 23 "TifSPeFIV45CHnbTWYiiIn41wrozpYizNsMWZUBjdah1N78WVhbyDrnr0bDgFp+gXjfVppa3I" 24 "gjiohEcemK3omXi3GDMK8ERhriLUKfQS842SXtQ8I+KoZtpCkGM//0h7+P+Rhm0WwdipIRMhR" 25 "8haNAeyDiiCvqJcvevv2T52vqKtS3aWz+GjaTJJLVWydEpz9WdvWeLfFVhe2ZnqwwZNa30Qoj" 26 "fsnvjaMwK2MU7uYfRBPuvLyK5QESWBpArNDd6ULl8Y+NU6kwNOVDc87OASCVEM1gw2IMi2mo2" 27 "WO5ywp0UWRiGZCkK+wOFQIDAQAB"; 28 29 typedef struct RSAPublicKey { 30 int len; // Length of n[] in number of uint32 31 uint32 n0inv; // -1 / n[0] mod 2^32 32 uint32 n[kRSANumWords]; // modulus as little endian array 33 uint32 rr[kRSANumWords]; // R^2 as little endian array 34 int exponent; // 3 or 65537 35 } RSAPublicKey; 36 37 // http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm 38 // a * x + b * y = gcd(a, b) = d 39 void ExtendedEuclid(uint64 a, uint64 b, uint64 *x, uint64 *y, uint64 *d) { 40 uint64 x1 = 0, x2 = 1, y1 = 1, y2 = 0; 41 42 while (b > 0) { 43 uint64 q = a / b; 44 uint64 r = a % b; 45 *x = x2 - q * x1; 46 *y = y2 - q * y1; 47 a = b; 48 b = r; 49 x2 = x1; 50 x1 = *x; 51 y2 = y1; 52 y1 = *y; 53 } 54 55 *d = a; 56 *x = x2; 57 *y = y2; 58 } 59 60 uint32 ModInverse(uint64 a, uint64 m) 61 { 62 uint64 d, x, y; 63 ExtendedEuclid(a, m, &x, &y, &d); 64 if (d == 1) 65 return static_cast<uint32>(x); 66 return 0; 67 } 68 69 uint32* BnNew() { 70 uint32* result = new uint32[kBigIntSize]; 71 memset(result, 0, kBigIntSize * sizeof(uint32)); 72 return result; 73 } 74 75 void BnFree(uint32* a) { 76 delete[] a; 77 } 78 79 uint32* BnCopy(uint32* a) { 80 uint32* result = new uint32[kBigIntSize]; 81 memcpy(result, a, kBigIntSize * sizeof(uint32)); 82 return result; 83 } 84 85 uint32* BnMul(uint32* a, uint32 b) { 86 uint32* result = BnNew(); 87 uint64 carry_over = 0; 88 for (size_t i = 0; i < kBigIntSize; ++i) { 89 carry_over += static_cast<uint64>(a[i]) * b; 90 result[i] = carry_over & kuint32max; 91 carry_over >>= 32; 92 } 93 return result; 94 } 95 96 void BnSub(uint32* a, uint32* b) { 97 int carry_over = 0; 98 for (size_t i = 0; i < kBigIntSize; ++i) { 99 int64 sub = static_cast<int64>(a[i]) - b[i] - carry_over; 100 carry_over = 0; 101 if (sub < 0) { 102 carry_over = 1; 103 sub += 0x100000000LL; 104 } 105 a[i] = static_cast<uint32>(sub); 106 } 107 } 108 109 void BnLeftShift(uint32* a, int offset) { 110 for (int i = kBigIntSize - offset - 1; i >= 0; --i) 111 a[i + offset] = a[i]; 112 for (int i = 0; i < offset; ++i) 113 a[i] = 0; 114 } 115 116 int BnCompare(uint32* a, uint32* b) { 117 for (int i = kBigIntSize - 1; i >= 0; --i) { 118 if (a[i] > b[i]) 119 return 1; 120 if (a[i] < b[i]) 121 return -1; 122 } 123 return 0; 124 } 125 126 uint64 BnGuess(uint32* a, uint32* b, uint64 from, uint64 to) { 127 if (from + 1 >= to) 128 return from; 129 130 uint64 guess = (from + to) / 2; 131 uint32* t = BnMul(b, static_cast<uint32>(guess)); 132 int result = BnCompare(a, t); 133 BnFree(t); 134 if (result > 0) 135 return BnGuess(a, b, guess, to); 136 if (result < 0) 137 return BnGuess(a, b, from, guess); 138 return guess; 139 } 140 141 void BnDiv(uint32* a, uint32* b, uint32** pq, uint32** pr) { 142 if (BnCompare(a, b) < 0) { 143 if (pq) 144 *pq = BnNew(); 145 if (pr) 146 *pr = BnCopy(a); 147 return; 148 } 149 150 int oa = kBigIntSize - 1; 151 int ob = kBigIntSize - 1; 152 for (; oa > 0 && !a[oa]; --oa) {} 153 for (; ob > 0 && !b[ob]; --ob) {} 154 uint32* q = BnNew(); 155 uint32* ca = BnCopy(a); 156 157 int digit = a[oa] < b[ob] ? oa - ob - 1 : oa - ob; 158 159 for (; digit >= 0; --digit) { 160 uint32* shifted_b = BnCopy(b); 161 BnLeftShift(shifted_b, digit); 162 uint32 value = static_cast<uint32>( 163 BnGuess(ca, shifted_b, 0, static_cast<uint64>(kuint32max) + 1)); 164 q[digit] = value; 165 uint32* t = BnMul(shifted_b, value); 166 BnSub(ca, t); 167 BnFree(t); 168 BnFree(shifted_b); 169 } 170 171 if (pq) 172 *pq = q; 173 else 174 BnFree(q); 175 if (pr) 176 *pr = ca; 177 else 178 BnFree(ca); 179 } 180 181 } // namespace 182 183 crypto::RSAPrivateKey* AndroidRSAPrivateKey(Profile* profile) { 184 std::string encoded_key = 185 profile->GetPrefs()->GetString(prefs::kDevToolsAdbKey); 186 std::string decoded_key; 187 scoped_ptr<crypto::RSAPrivateKey> key; 188 if (!encoded_key.empty() && base::Base64Decode(encoded_key, &decoded_key)) { 189 std::vector<uint8> key_info(decoded_key.begin(), decoded_key.end()); 190 key.reset(crypto::RSAPrivateKey::CreateFromPrivateKeyInfo(key_info)); 191 } 192 if (!key) { 193 key.reset(crypto::RSAPrivateKey::Create(2048)); 194 std::vector<uint8> key_info; 195 if (!key || !key->ExportPrivateKey(&key_info)) 196 return NULL; 197 198 std::string key_string(key_info.begin(), key_info.end()); 199 base::Base64Encode(key_string, &encoded_key); 200 profile->GetPrefs()->SetString(prefs::kDevToolsAdbKey, 201 encoded_key); 202 } 203 return key.release(); 204 } 205 206 std::string AndroidRSAPublicKey(crypto::RSAPrivateKey* key) { 207 std::vector<uint8> public_key; 208 if (!key) 209 return kDummyRSAPublicKey; 210 211 key->ExportPublicKey(&public_key); 212 std::string asn1(public_key.begin(), public_key.end()); 213 214 base::StringPiece pk; 215 if (!net::asn1::ExtractSubjectPublicKeyFromSPKI(asn1, &pk)) 216 return kDummyRSAPublicKey; 217 218 // Skip 10 byte asn1 prefix to the modulus. 219 std::vector<uint8> pk_data(pk.data() + 10, pk.data() + pk.length()); 220 uint32* n = BnNew(); 221 for (size_t i = 0; i < kRSANumWords; ++i) { 222 uint32 t = pk_data[4 * i]; 223 t = t << 8; 224 t += pk_data[4 * i + 1]; 225 t = t << 8; 226 t += pk_data[4 * i + 2]; 227 t = t << 8; 228 t += pk_data[4 * i + 3]; 229 n[kRSANumWords - i - 1] = t; 230 } 231 uint64 n0 = n[0]; 232 233 RSAPublicKey pkey; 234 pkey.len = kRSANumWords; 235 pkey.exponent = 65537; // Fixed public exponent 236 pkey.n0inv = 0 - ModInverse(n0, 0x100000000LL); 237 if (pkey.n0inv == 0) 238 return kDummyRSAPublicKey; 239 240 uint32* r = BnNew(); 241 r[kRSANumWords * 2] = 1; 242 243 uint32* rr; 244 BnDiv(r, n, NULL, &rr); 245 246 for (size_t i = 0; i < kRSANumWords; ++i) { 247 pkey.n[i] = n[i]; 248 pkey.rr[i] = rr[i]; 249 } 250 251 BnFree(n); 252 BnFree(r); 253 BnFree(rr); 254 255 std::string output; 256 std::string input(reinterpret_cast<char*>(&pkey), sizeof(pkey)); 257 base::Base64Encode(input, &output); 258 return output; 259 } 260 261 std::string AndroidRSASign(crypto::RSAPrivateKey* key, 262 const std::string& body) { 263 std::vector<uint8> digest(body.begin(), body.end()); 264 std::vector<uint8> result; 265 if (!crypto::SignatureCreator::Sign(key, vector_as_array(&digest), 266 digest.size(), &result)) { 267 return std::string(); 268 } 269 return std::string(result.begin(), result.end()); 270 } 271
