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
ExtendedEuclid(uint64 a,uint64 b,uint64 * x,uint64 * y,uint64 * 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
ModInverse(uint64 a,uint64 m)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
BnNew()69 uint32* BnNew() {
70 uint32* result = new uint32[kBigIntSize];
71 memset(result, 0, kBigIntSize * sizeof(uint32));
72 return result;
73 }
74
BnFree(uint32 * a)75 void BnFree(uint32* a) {
76 delete[] a;
77 }
78
BnCopy(uint32 * a)79 uint32* BnCopy(uint32* a) {
80 uint32* result = new uint32[kBigIntSize];
81 memcpy(result, a, kBigIntSize * sizeof(uint32));
82 return result;
83 }
84
BnMul(uint32 * a,uint32 b)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
BnSub(uint32 * a,uint32 * b)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
BnLeftShift(uint32 * a,int offset)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
BnCompare(uint32 * a,uint32 * b)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
BnGuess(uint32 * a,uint32 * b,uint64 from,uint64 to)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
BnDiv(uint32 * a,uint32 * b,uint32 ** pq,uint32 ** pr)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
AndroidRSAPrivateKey(Profile * profile)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
AndroidRSAPublicKey(crypto::RSAPrivateKey * key)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
AndroidRSASign(crypto::RSAPrivateKey * key,const std::string & body)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 }
272