src/chrome/browser/devtools/adb/android_rsa.cc

   1 // Copyright (c) 2013 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/adb/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 void BnPrint(const std::string& title, uint32_t* a) {
  80     int i = kBigIntSize - 1;
  81     fprintf(stderr, "%s: ", title.c_str());
  82     while (!a[i]) --i;
  83     for (; i >= 0; --i)
  84         fprintf(stderr, "%08x", a[i]);
  85     fprintf(stderr, "\n");
  86 }
  87
  88 uint32* BnCopy(uint32* a) {
  89   uint32* result = new uint32[kBigIntSize];
  90   memcpy(result, a, kBigIntSize * sizeof(uint32));
  91   return result;
  92 }
  93
  94 void BnAdd(uint32* a, uint32* b) {
  95   uint64 carry_over = 0;
  96   for (size_t i = 0; i < kBigIntSize; ++i) {
  97     carry_over += static_cast<uint64>(a[i]) + b[i];
  98     a[i] = carry_over & kuint32max;
  99     carry_over >>= 32;
 100   }
 101 }
 102
 103 uint32* BnMul(uint32* a, uint32 b) {
 104   uint32* result = BnNew();
 105   uint64 carry_over = 0;
 106   for (size_t i = 0; i < kBigIntSize; ++i) {
 107     carry_over += static_cast<uint64>(a[i]) * b;
 108     result[i] = carry_over & kuint32max;
 109     carry_over >>= 32;
 110   }
 111   return result;
 112 }
 113
 114 void BnSub(uint32* a, uint32* b) {
 115   int carry_over = 0;
 116   for (size_t i = 0; i < kBigIntSize; ++i) {
 117     int64 sub = static_cast<int64>(a[i]) - b[i] - carry_over;
 118     carry_over = 0;
 119     if (sub < 0) {
 120       carry_over = 1;
 121       sub += GG_LONGLONG(0x100000000);
 122     }
 123     a[i] = static_cast<uint32>(sub);
 124   }
 125 }
 126
 127 void BnLeftShift(uint32* a, int offset) {
 128   for (int i = kBigIntSize - offset - 1; i >= 0; --i)
 129     a[i + offset] = a[i];
 130   for (int i = 0; i < offset; ++i)
 131     a[i] = 0;
 132 }
 133
 134 int BnCompare(uint32* a, uint32* b) {
 135   for (int i = kBigIntSize - 1; i >= 0; --i) {
 136     if (a[i] > b[i])
 137       return 1;
 138     if (a[i] < b[i])
 139       return -1;
 140   }
 141   return 0;
 142 }
 143
 144 uint64 BnGuess(uint32* a, uint32* b, uint64 from, uint64 to) {
 145   if (from + 1 >= to)
 146     return from;
 147
 148   uint64 guess = (from + to) / 2;
 149   uint32* t = BnMul(b, static_cast<uint32>(guess));
 150   int result = BnCompare(a, t);
 151   BnFree(t);
 152   if (result > 0)
 153     return BnGuess(a, b, guess, to);
 154   if (result < 0)
 155     return BnGuess(a, b, from, guess);
 156   return guess;
 157 }
 158
 159 void BnDiv(uint32* a, uint32* b, uint32** pq, uint32** pr) {
 160   if (BnCompare(a, b) < 0) {
 161     if (pq)
 162       *pq = BnNew();
 163     if (pr)
 164       *pr = BnCopy(a);
 165     return;
 166   }
 167
 168   int oa = kBigIntSize - 1;
 169   int ob = kBigIntSize - 1;
 170   for (; oa > 0 && !a[oa]; --oa) {}
 171   for (; ob > 0 && !b[ob]; --ob) {}
 172   uint32* q = BnNew();
 173   uint32* ca = BnCopy(a);
 174
 175   int digit = a[oa] < b[ob] ? oa - ob - 1 : oa - ob;
 176
 177   for (; digit >= 0; --digit) {
 178     uint32* shifted_b = BnCopy(b);
 179     BnLeftShift(shifted_b, digit);
 180     uint32 value = static_cast<uint32>(
 181         BnGuess(ca, shifted_b, 0, static_cast<uint64>(kuint32max) + 1));
 182     q[digit] = value;
 183     uint32* t = BnMul(shifted_b, value);
 184     BnSub(ca, t);
 185     BnFree(t);
 186     BnFree(shifted_b);
 187   }
 188
 189   if (pq)
 190     *pq = q;
 191   else
 192     BnFree(q);
 193   if (pr)
 194     *pr = ca;
 195   else
 196     BnFree(ca);
 197 }
 198
 199 }  // namespace
 200
 201 crypto::RSAPrivateKey* AndroidRSAPrivateKey(Profile* profile) {
 202   std::string encoded_key =
 203       profile->GetPrefs()->GetString(prefs::kDevToolsAdbKey);
 204   std::string decoded_key;
 205   scoped_ptr<crypto::RSAPrivateKey> key;
 206   if (!encoded_key.empty() && base::Base64Decode(encoded_key, &decoded_key)) {
 207     std::vector<uint8> key_info(decoded_key.begin(), decoded_key.end());
 208     key.reset(crypto::RSAPrivateKey::CreateFromPrivateKeyInfo(key_info));
 209   }
 210   if (!key) {
 211     key.reset(crypto::RSAPrivateKey::Create(2048));
 212     std::vector<uint8> key_info;
 213     if (!key || !key->ExportPrivateKey(&key_info))
 214       return NULL;
 215
 216     std::string key_string(key_info.begin(), key_info.end());
 217     if (base::Base64Encode(key_string, &encoded_key)) {
 218       profile->GetPrefs()->SetString(prefs::kDevToolsAdbKey,
 219                                      encoded_key);
 220     }
 221   }
 222   return key.release();
 223 }
 224
 225 std::string AndroidRSAPublicKey(crypto::RSAPrivateKey* key) {
 226   std::vector<uint8> public_key;
 227   if (!key)
 228     return kDummyRSAPublicKey;
 229
 230   key->ExportPublicKey(&public_key);
 231   std::string asn1(public_key.begin(), public_key.end());
 232
 233   base::StringPiece pk;
 234   if (!net::asn1::ExtractSubjectPublicKeyFromSPKI(asn1, &pk))
 235     return kDummyRSAPublicKey;
 236
 237   // Skip 10 byte asn1 prefix to the modulus.
 238   std::vector<uint8> pk_data(pk.data() + 10, pk.data() + pk.length());
 239   uint32* n = BnNew();
 240   for (size_t i = 0; i < kRSANumWords; ++i) {
 241     uint32 t = pk_data[4 * i];
 242     t = t << 8;
 243     t += pk_data[4 * i + 1];
 244     t = t << 8;
 245     t += pk_data[4 * i + 2];
 246     t = t << 8;
 247     t += pk_data[4 * i + 3];
 248     n[kRSANumWords - i - 1] = t;
 249   }
 250   uint64 n0 = n[0];
 251
 252   RSAPublicKey pkey;
 253   pkey.len = kRSANumWords;
 254   pkey.exponent = 65537; // Fixed public exponent
 255   pkey.n0inv = 0 - ModInverse(n0, GG_LONGLONG(0x100000000));
 256   if (pkey.n0inv == 0)
 257     return kDummyRSAPublicKey;
 258
 259   uint32* r = BnNew();
 260   r[kRSANumWords * 2] = 1;
 261
 262   uint32* rr;
 263   BnDiv(r, n, NULL, &rr);
 264
 265   for (size_t i = 0; i < kRSANumWords; ++i) {
 266     pkey.n[i] = n[i];
 267     pkey.rr[i] = rr[i];
 268   }
 269
 270   BnFree(n);
 271   BnFree(r);
 272   BnFree(rr);
 273
 274   std::string output;
 275   std::string input(reinterpret_cast<char*>(&pkey), sizeof(pkey));
 276   base::Base64Encode(input, &output);
 277   return output;
 278 }
 279
 280 std::string AndroidRSASign(crypto::RSAPrivateKey* key,
 281                            const std::string& body) {
 282   std::vector<uint8> digest(body.begin(), body.end());
 283   std::vector<uint8> result;
 284   if (!crypto::SignatureCreator::Sign(key, vector_as_array(&digest),
 285                                       digest.size(), &result)) {
 286     return std::string();
 287   }
 288   return std::string(result.begin(), result.end());
 289 }