1 // Copyright 2021 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 ///////////////////////////////////////////////////////////////////////////////
16 #include "tink/internal/rsa_util.h"
17
18 #include <stddef.h>
19 #include <stdint.h>
20
21 #include <algorithm>
22 #include <iterator>
23 #include <memory>
24 #include <string>
25 #include <utility>
26 #include <vector>
27
28 #include "gmock/gmock.h"
29 #include "gtest/gtest.h"
30 #include "absl/status/status.h"
31 #include "absl/strings/escaping.h"
32 #include "absl/strings/string_view.h"
33 #include "openssl/bn.h"
34 #include "openssl/rsa.h"
35 #include "tink/internal/bn_util.h"
36 #include "tink/internal/ssl_unique_ptr.h"
37 #include "tink/subtle/random.h"
38 #include "tink/util/secret_data.h"
39 #include "tink/util/status.h"
40 #include "tink/util/statusor.h"
41 #include "tink/util/test_matchers.h"
42
43 namespace crypto {
44 namespace tink {
45 namespace internal {
46 namespace {
47
48 using ::crypto::tink::test::IsOk;
49 using ::crypto::tink::test::StatusIs;
50 using ::testing::IsEmpty;
51 using ::testing::Not;
52
53 constexpr int kSslSuccess = 1;
54 // 2048 bits modulus.
55 constexpr absl::string_view k2048BitRsaModulus =
56 "b5a5651bc2e15ce31d789f0984053a2ea0cf8f964a78068c45acfdf078c57fd62d5a287c32"
57 "f3baa879f5dfea27d7a3077c9d3a2a728368c3d90164690c3d82f660ffebc7f13fed454eb5"
58 "103df943c10dc32ec60b0d9b6e307bfd7f9b943e0dc3901e42501765365f7286eff2f1f728"
59 "774aa6a371e108a3a7dd00d7bcd4c1a186c2865d4b370ea38cc89c0b23b318dbcafbd872b4"
60 "f9b833dfb2a4ca7fcc23298020044e8130bfe930adfb3e5cab8d324547adf4b2ce34d7cea4"
61 "298f0b613d85f2bf1df03da44aee0784a1a20a15ee0c38a0f8e84962f1f61b18bd43781c73"
62 "85f3c2b8e2aebd3c560b4faad208ad3938bad27ddda9ed9e933dba0880212dd9e28d";
63
64 // Utility function to create an RSA key pair.
GetKeyPair(size_t modulus_size_in_bits)65 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> GetKeyPair(
66 size_t modulus_size_in_bits) {
67 RsaPublicKey public_key;
68 RsaPrivateKey private_key;
69 internal::SslUniquePtr<BIGNUM> e(BN_new());
70 BN_set_word(e.get(), RSA_F4);
71 util::Status res =
72 NewRsaKeyPair(modulus_size_in_bits, e.get(), &private_key, &public_key);
73 if (!res.ok()) {
74 return res;
75 }
76 return {{public_key, private_key}};
77 }
78
TEST(RsaUtilTest,BasicSanityChecks)79 TEST(RsaUtilTest, BasicSanityChecks) {
80 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
81 GetKeyPair(/*modulus_size_in_bits=*/2048);
82 ASSERT_THAT(keys, IsOk());
83 const RsaPublicKey& public_key = keys->first;
84 const RsaPrivateKey& private_key = keys->second;
85
86 EXPECT_THAT(private_key.n, Not(IsEmpty()));
87 EXPECT_THAT(private_key.e, Not(IsEmpty()));
88 EXPECT_THAT(private_key.d, Not(IsEmpty()));
89
90 EXPECT_THAT(private_key.p, Not(IsEmpty()));
91 EXPECT_THAT(private_key.q, Not(IsEmpty()));
92 EXPECT_THAT(private_key.dp, Not(IsEmpty()));
93 EXPECT_THAT(private_key.dq, Not(IsEmpty()));
94 EXPECT_THAT(private_key.crt, Not(IsEmpty()));
95
96 EXPECT_THAT(public_key.n, Not(IsEmpty()));
97 EXPECT_THAT(public_key.e, Not(IsEmpty()));
98
99 EXPECT_EQ(public_key.n, private_key.n);
100 EXPECT_EQ(public_key.e, private_key.e);
101 }
102
TEST(RsaUtilTest,FailsOnLargeE)103 TEST(RsaUtilTest, FailsOnLargeE) {
104 // OpenSSL requires the "e" value to be at most 32 bits.
105 RsaPublicKey public_key;
106 RsaPrivateKey private_key;
107
108 internal::SslUniquePtr<BIGNUM> e(BN_new());
109 BN_set_word(e.get(), 1L << 33);
110 EXPECT_THAT(NewRsaKeyPair(/*modulus_size_in_bits=*/2048, e.get(),
111 &private_key, &public_key),
112 StatusIs(absl::StatusCode::kInvalidArgument));
113 }
114
TEST(RsaUtilTest,KeyIsWellFormed)115 TEST(RsaUtilTest, KeyIsWellFormed) {
116 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
117 GetKeyPair(/*modulus_size_in_bits=*/2048);
118 ASSERT_THAT(keys, IsOk());
119 const RsaPrivateKey& private_key = keys->second;
120
121 util::StatusOr<internal::SslUniquePtr<BIGNUM>> n =
122 internal::StringToBignum(private_key.n);
123 ASSERT_THAT(n, IsOk());
124 util::StatusOr<internal::SslUniquePtr<BIGNUM>> d =
125 internal::StringToBignum(util::SecretDataAsStringView(private_key.d));
126 ASSERT_THAT(d, IsOk());
127 util::StatusOr<internal::SslUniquePtr<BIGNUM>> p =
128 internal::StringToBignum(util::SecretDataAsStringView(private_key.p));
129 ASSERT_THAT(p, IsOk());
130 util::StatusOr<internal::SslUniquePtr<BIGNUM>> q =
131 internal::StringToBignum(util::SecretDataAsStringView(private_key.q));
132 ASSERT_THAT(q, IsOk());
133 util::StatusOr<internal::SslUniquePtr<BIGNUM>> dp =
134 internal::StringToBignum(util::SecretDataAsStringView(private_key.dp));
135 ASSERT_THAT(dp, IsOk());
136 util::StatusOr<internal::SslUniquePtr<BIGNUM>> dq =
137 internal::StringToBignum(util::SecretDataAsStringView(private_key.dq));
138 ASSERT_THAT(dq, IsOk());
139 internal::SslUniquePtr<BN_CTX> ctx(BN_CTX_new());
140
141 // Check n = p * q.
142 {
143 auto n_calc = internal::SslUniquePtr<BIGNUM>(BN_new());
144 ASSERT_EQ(BN_mul(n_calc.get(), p->get(), q->get(), ctx.get()), kSslSuccess);
145 EXPECT_EQ(BN_cmp(n_calc.get(), n->get()), 0);
146 }
147
148 // Check n size >= 2048 bit.
149 EXPECT_GE(BN_num_bits(n->get()), 2048);
150
151 // dp = d mod (p - 1)
152 {
153 auto pm1 = internal::SslUniquePtr<BIGNUM>(BN_dup(p->get()));
154 ASSERT_EQ(BN_sub_word(pm1.get(), /*w=*/1), kSslSuccess);
155 auto dp_calc = internal::SslUniquePtr<BIGNUM>(BN_new());
156 ASSERT_EQ(BN_mod(dp_calc.get(), d->get(), pm1.get(), ctx.get()),
157 kSslSuccess);
158 EXPECT_EQ(BN_cmp(dp_calc.get(), dp->get()), 0);
159 }
160
161 // dq = d mod (q - 1)
162 {
163 auto qm1 = internal::SslUniquePtr<BIGNUM>(BN_dup(q->get()));
164 ASSERT_EQ(BN_sub_word(qm1.get(), /*w=*/1), kSslSuccess);
165 auto dq_calc = internal::SslUniquePtr<BIGNUM>(BN_new());
166 ASSERT_EQ(BN_mod(dq_calc.get(), d->get(), qm1.get(), ctx.get()),
167 kSslSuccess);
168 EXPECT_EQ(BN_cmp(dq_calc.get(), dq->get()), 0);
169 }
170 }
171
TEST(RsaUtilTest,GeneratesDifferentPrivateKeys)172 TEST(RsaUtilTest, GeneratesDifferentPrivateKeys) {
173 RsaPublicKey public_key;
174 internal::SslUniquePtr<BIGNUM> e(BN_new());
175 BN_set_word(e.get(), RSA_F4);
176
177 std::vector<RsaPrivateKey> private_keys;
178 std::generate_n(std::back_inserter(private_keys), 4, [&]() {
179 RsaPrivateKey private_key;
180 EXPECT_THAT(NewRsaKeyPair(/*modulus_size_in_bits=*/2048, e.get(),
181 &private_key, &public_key),
182 IsOk());
183 return private_key;
184 });
185
186 for (int i = 0; i < private_keys.size() - 1; i++) {
187 for (int j = i + 1; j < private_keys.size(); j++) {
188 // The only field that should be equal.
189 EXPECT_EQ(private_keys[i].e, private_keys[j].e);
190 EXPECT_NE(private_keys[i].n, private_keys[j].n);
191 EXPECT_NE(private_keys[i].d, private_keys[j].d);
192 EXPECT_NE(private_keys[i].p, private_keys[j].p);
193 EXPECT_NE(private_keys[i].q, private_keys[j].q);
194 EXPECT_NE(private_keys[i].dp, private_keys[j].dp);
195 EXPECT_NE(private_keys[i].dq, private_keys[j].dq);
196 EXPECT_NE(private_keys[i].crt, private_keys[j].crt);
197 }
198 }
199 }
200
TEST(RsaUtilTest,ValidateRsaModulusSize)201 TEST(RsaUtilTest, ValidateRsaModulusSize) {
202 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
203 GetKeyPair(/*modulus_size_in_bits=*/2048);
204 ASSERT_THAT(keys, IsOk());
205 {
206 const RsaPrivateKey& private_key = keys->second;
207
208 util::StatusOr<internal::SslUniquePtr<BIGNUM>> n =
209 internal::StringToBignum(private_key.n);
210 EXPECT_THAT(ValidateRsaModulusSize(BN_num_bits(n->get())), IsOk());
211 }
212 keys = GetKeyPair(/*modulus_size_in_bits=*/1024);
213 ASSERT_THAT(keys, IsOk());
214 {
215 const RsaPrivateKey& private_key = keys->second;
216
217 util::StatusOr<internal::SslUniquePtr<BIGNUM>> n =
218 internal::StringToBignum(private_key.n);
219 EXPECT_THAT(ValidateRsaModulusSize(BN_num_bits(n->get())), Not(IsOk()));
220 }
221 }
222
TEST(RsaUtilTest,ValidateRsaPublicExponent)223 TEST(RsaUtilTest, ValidateRsaPublicExponent) {
224 internal::SslUniquePtr<BIGNUM> e_bn(BN_new());
225
226 // Failure scenario.
227 const std::vector<BN_ULONG> invalid_exponents = {2, 3, 4, 65536, 65538};
228 for (const BN_ULONG exponent : invalid_exponents) {
229 BN_set_word(e_bn.get(), exponent);
230 util::StatusOr<std::string> e_str =
231 internal::BignumToString(e_bn.get(), BN_num_bytes(e_bn.get()));
232 ASSERT_THAT(e_str, IsOk());
233 EXPECT_THAT(ValidateRsaPublicExponent(*e_str), Not(IsOk()));
234 }
235
236 // Successful case.
237 BN_set_word(e_bn.get(), RSA_F4);
238 util::StatusOr<std::string> e_str =
239 internal::BignumToString(e_bn.get(), BN_num_bytes(e_bn.get()));
240 ASSERT_THAT(e_str, IsOk());
241 EXPECT_THAT(ValidateRsaPublicExponent(*e_str), IsOk());
242 }
243
244 // Checks if a BIGNUM is equal to a string value.
ExpectBignumEquals(const BIGNUM * bn,absl::string_view data)245 void ExpectBignumEquals(const BIGNUM* bn, absl::string_view data) {
246 util::StatusOr<std::string> converted =
247 internal::BignumToString(bn, BN_num_bytes(bn));
248 ASSERT_THAT(converted, IsOk());
249 EXPECT_EQ(*converted, data);
250 }
251
252 // Checks if a BIGNUM is equal to a SecretData value.
ExpectBignumEquals(const BIGNUM * bn,const util::SecretData & data)253 void ExpectBignumEquals(const BIGNUM* bn, const util::SecretData& data) {
254 internal::ExpectBignumEquals(bn, util::SecretDataAsStringView(data));
255 }
256
TEST(RsaUtilTest,GetRsaModAndExponents)257 TEST(RsaUtilTest, GetRsaModAndExponents) {
258 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
259 GetKeyPair(/*modulus_size_in_bits=*/2048);
260 ASSERT_THAT(keys, IsOk());
261 const RsaPrivateKey& private_key = keys->second;
262 internal::SslUniquePtr<RSA> rsa(RSA_new());
263 util::Status result = GetRsaModAndExponents(private_key, rsa.get());
264 ASSERT_THAT(result, IsOk());
265 const BIGNUM* n = nullptr;
266 const BIGNUM* e = nullptr;
267 const BIGNUM* d = nullptr;
268 RSA_get0_key(rsa.get(), &n, &e, &d);
269 ExpectBignumEquals(n, private_key.n);
270 ExpectBignumEquals(e, private_key.e);
271 ExpectBignumEquals(d, private_key.d);
272 }
273
TEST(RsaUtilTest,GetRsaPrimeFactors)274 TEST(RsaUtilTest, GetRsaPrimeFactors) {
275 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
276 GetKeyPair(/*modulus_size_in_bits=*/2048);
277 ASSERT_THAT(keys, IsOk());
278 const RsaPrivateKey& private_key = keys->second;
279 internal::SslUniquePtr<RSA> rsa(RSA_new());
280 util::Status result = GetRsaPrimeFactors(private_key, rsa.get());
281 ASSERT_THAT(result, IsOk());
282 const BIGNUM* p = nullptr;
283 const BIGNUM* q = nullptr;
284 RSA_get0_factors(rsa.get(), &p, &q);
285 ExpectBignumEquals(p, private_key.p);
286 ExpectBignumEquals(q, private_key.q);
287 }
288
TEST(RsaUtilTest,GetRsaCrtParams)289 TEST(RsaUtilTest, GetRsaCrtParams) {
290 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
291 GetKeyPair(/*modulus_size_in_bits=*/2048);
292 ASSERT_THAT(keys, IsOk());
293 const RsaPrivateKey& private_key = keys->second;
294 internal::SslUniquePtr<RSA> rsa(RSA_new());
295 const BIGNUM* dp = nullptr;
296 const BIGNUM* dq = nullptr;
297 const BIGNUM* crt = nullptr;
298 util::Status result = GetRsaCrtParams(private_key, rsa.get());
299 ASSERT_THAT(result, IsOk());
300 RSA_get0_crt_params(rsa.get(), &dp, &dq, &crt);
301 ExpectBignumEquals(dp, private_key.dp);
302 ExpectBignumEquals(dq, private_key.dq);
303 ExpectBignumEquals(crt, private_key.crt);
304 }
305
TEST(RsaUtilTest,CopiesRsaPrivateKey)306 TEST(RsaUtilTest, CopiesRsaPrivateKey) {
307 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
308 GetKeyPair(/*modulus_size_in_bits=*/2048);
309 ASSERT_THAT(keys, IsOk());
310 const RsaPrivateKey& private_key = keys->second;
311
312 util::StatusOr<internal::SslUniquePtr<RSA>> rsa_result =
313 RsaPrivateKeyToRsa(private_key);
314 EXPECT_TRUE(rsa_result.ok());
315 internal::SslUniquePtr<RSA> rsa = std::move(rsa_result).value();
316 const BIGNUM* n = nullptr;
317 const BIGNUM* e = nullptr;
318 const BIGNUM* d = nullptr;
319 RSA_get0_key(rsa.get(), &n, &e, &d);
320 const BIGNUM* p = nullptr;
321 const BIGNUM* q = nullptr;
322 RSA_get0_factors(rsa.get(), &p, &q);
323 ExpectBignumEquals(n, private_key.n);
324 ExpectBignumEquals(e, private_key.e);
325 ExpectBignumEquals(d, private_key.d);
326 ExpectBignumEquals(p, private_key.p);
327 ExpectBignumEquals(q, private_key.q);
328 }
329
TEST(RsaUtilTest,CopiesRsaPublicKey)330 TEST(RsaUtilTest, CopiesRsaPublicKey) {
331 util::StatusOr<std::pair<RsaPublicKey, RsaPrivateKey>> keys =
332 GetKeyPair(/*modulus_size_in_bits=*/2048);
333 ASSERT_THAT(keys, IsOk());
334 const RsaPublicKey& public_key = keys->first;
335
336 util::StatusOr<internal::SslUniquePtr<RSA>> rsa_result =
337 RsaPublicKeyToRsa(public_key);
338 EXPECT_TRUE(rsa_result.ok());
339 internal::SslUniquePtr<RSA> rsa = std::move(rsa_result).value();
340
341 const BIGNUM* n = nullptr;
342 const BIGNUM* e = nullptr;
343 RSA_get0_key(rsa.get(), &n, &e, /*d=*/nullptr);
344 ExpectBignumEquals(n, public_key.n);
345 ExpectBignumEquals(e, public_key.e);
346 }
347
348 // Utility function that creates an RSA public key with the given modulus
349 // `n_hex` and exponent `exp`.
NewRsaPublicKey(absl::string_view n_hex,uint64_t exp)350 util::StatusOr<internal::SslUniquePtr<RSA>> NewRsaPublicKey(
351 absl::string_view n_hex, uint64_t exp) {
352 internal::SslUniquePtr<RSA> key(RSA_new());
353 util::StatusOr<internal::SslUniquePtr<BIGNUM>> n_bn =
354 internal::StringToBignum(absl::HexStringToBytes(n_hex));
355 if (!n_bn.ok()) {
356 return n_bn.status();
357 }
358 internal::SslUniquePtr<BIGNUM> n = *std::move(n_bn);
359 internal::SslUniquePtr<BIGNUM> e(BN_new());
360 BN_set_word(e.get(), exp);
361 if (RSA_set0_key(key.get(), n.get(), e.get(), /*d=*/nullptr) != 1) {
362 return util::Status(absl::StatusCode::kInternal, "RSA_set0_key failed");
363 }
364 // RSA_set0_key takes ownership of the arguments.
365 n.release();
366 e.release();
367 return std::move(key);
368 }
369
TEST(RsaUtilTest,RsaCheckPublicKeyNullKey)370 TEST(RsaUtilTest, RsaCheckPublicKeyNullKey) {
371 EXPECT_THAT(RsaCheckPublicKey(nullptr), Not(IsOk()));
372 }
373
TEST(RsaUtilTest,RsaCheckPublicKeyMissingExponentAndModule)374 TEST(RsaUtilTest, RsaCheckPublicKeyMissingExponentAndModule) {
375 internal::SslUniquePtr<RSA> key(RSA_new());
376 EXPECT_THAT(RsaCheckPublicKey(key.get()), Not(IsOk()));
377 }
378
TEST(RsaUtilTest,RsaCheckPublicKeyValid)379 TEST(RsaUtilTest, RsaCheckPublicKeyValid) {
380 util::StatusOr<internal::SslUniquePtr<RSA>> key =
381 NewRsaPublicKey(k2048BitRsaModulus, RSA_F4);
382 ASSERT_THAT(key, IsOk());
383 EXPECT_THAT(RsaCheckPublicKey(key->get()), IsOk());
384 }
385
TEST(RsaUtilTest,RsaCheckPublicKeyExponentTooLarge)386 TEST(RsaUtilTest, RsaCheckPublicKeyExponentTooLarge) {
387 // Invalid exponent of 34 bits.
388 constexpr uint64_t kExponentTooLarge = 0x200000000;
389 util::StatusOr<internal::SslUniquePtr<RSA>> key =
390 NewRsaPublicKey(k2048BitRsaModulus, kExponentTooLarge);
391 ASSERT_THAT(key, IsOk());
392 EXPECT_THAT(RsaCheckPublicKey(key->get()), Not(IsOk()));
393 }
394
TEST(RsaUtilTest,RsaCheckPublicKeyExponentTooSmall)395 TEST(RsaUtilTest, RsaCheckPublicKeyExponentTooSmall) {
396 constexpr uint64_t kExponentEqualsToOne = 0x1;
397 util::StatusOr<internal::SslUniquePtr<RSA>> key =
398 NewRsaPublicKey(k2048BitRsaModulus, kExponentEqualsToOne);
399 ASSERT_THAT(key, IsOk());
400 EXPECT_THAT(RsaCheckPublicKey(key->get()), Not(IsOk()));
401 }
402
TEST(RsaUtilTest,RsaCheckPublicKeyExponentNotOdd)403 TEST(RsaUtilTest, RsaCheckPublicKeyExponentNotOdd) {
404 constexpr uint64_t kExponentNotOdd = 0x20000000;
405 util::StatusOr<internal::SslUniquePtr<RSA>> key =
406 NewRsaPublicKey(k2048BitRsaModulus, kExponentNotOdd);
407 ASSERT_THAT(key, IsOk());
408 EXPECT_THAT(RsaCheckPublicKey(key->get()), Not(IsOk()));
409 }
410
TEST(RsaUtilTest,RsaCheckPublicKeyModulusTooLarge)411 TEST(RsaUtilTest, RsaCheckPublicKeyModulusTooLarge) {
412 // Get 1 byte more than 16384 bits (2048 bytes).
413 std::string too_large_modulus = subtle::Random::GetRandomBytes(2049);
414 if (too_large_modulus[0] == '\0') {
415 too_large_modulus[0] = 0x01;
416 }
417 util::StatusOr<internal::SslUniquePtr<RSA>> key =
418 NewRsaPublicKey(absl::BytesToHexString(too_large_modulus), RSA_F4);
419 ASSERT_THAT(key, IsOk());
420 EXPECT_THAT(RsaCheckPublicKey(key->get()), Not(IsOk()));
421 }
422
TEST(RsaUtilTest,RsaCheckPublicKeyModulusSmallerThanExp)423 TEST(RsaUtilTest, RsaCheckPublicKeyModulusSmallerThanExp) {
424 constexpr absl::string_view kModulusSmallerThanExp = "1001";
425 util::StatusOr<internal::SslUniquePtr<RSA>> key =
426 NewRsaPublicKey(kModulusSmallerThanExp, RSA_F4);
427 ASSERT_THAT(key, IsOk());
428 EXPECT_THAT(RsaCheckPublicKey(key->get()), Not(IsOk()));
429 }
430
431 } // namespace
432 } // namespace internal
433 } // namespace tink
434 } // namespace crypto
435