chrome/browser/devtools/device/usb/android_rsa.cc

   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, crypto::SignatureCreator::SHA1,
 266                                       vector_as_array(&digest), digest.size(),
 267                                       &result)) {
 268     return std::string();
 269   }
 270   return std::string(result.begin(), result.end());
 271 }