1 /* Copyright (c) 2017, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 #include <openssl/bn.h>
16 #include <openssl/bytestring.h>
17 #include <openssl/mem.h>
18
19 #define CHECK(expr) \
20 do { \
21 if (!(expr)) { \
22 printf("%s failed\n", #expr); \
23 abort(); \
24 } \
25 } while (false)
26
27 // Basic implementation of mod_exp using square and multiple method.
mod_exp(BIGNUM * r,const BIGNUM * a,const BIGNUM * p,const BIGNUM * m,BN_CTX * ctx)28 int mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m,
29 BN_CTX *ctx) {
30 if (BN_is_one(m)) {
31 BN_zero(r);
32 return 1;
33 }
34
35 bssl::UniquePtr<BIGNUM> exp(BN_dup(p));
36 bssl::UniquePtr<BIGNUM> base(BN_new());
37 if (!exp || !base) {
38 return 0;
39 }
40 if (!BN_one(r) || !BN_nnmod(base.get(), a, m, ctx)) {
41 return 0;
42 }
43
44 while (!BN_is_zero(exp.get())) {
45 if (BN_is_odd(exp.get())) {
46 if (!BN_mul(r, r, base.get(), ctx) || !BN_nnmod(r, r, m, ctx)) {
47 return 0;
48 }
49 }
50 if (!BN_rshift1(exp.get(), exp.get()) ||
51 !BN_mul(base.get(), base.get(), base.get(), ctx) ||
52 !BN_nnmod(base.get(), base.get(), m, ctx)) {
53 return 0;
54 }
55 }
56
57 return 1;
58 }
59
LLVMFuzzerTestOneInput(const uint8_t * buf,size_t len)60 extern "C" int LLVMFuzzerTestOneInput(const uint8_t *buf, size_t len) {
61 CBS cbs, child0, child1, child2;
62 uint8_t sign;
63 CBS_init(&cbs, buf, len);
64 if (!CBS_get_u16_length_prefixed(&cbs, &child0) ||
65 !CBS_get_u8(&child0, &sign) ||
66 CBS_len(&child0) == 0 ||
67 !CBS_get_u16_length_prefixed(&cbs, &child1) ||
68 CBS_len(&child1) == 0 ||
69 !CBS_get_u16_length_prefixed(&cbs, &child2) ||
70 CBS_len(&child2) == 0) {
71 return 0;
72 }
73
74 // Don't fuzz inputs larger than 512 bytes (4096 bits). This isn't ideal, but
75 // the naive |mod_exp| above is somewhat slow, so this otherwise causes the
76 // fuzzers to spend a lot of time exploring timeouts.
77 if (CBS_len(&child0) > 512 ||
78 CBS_len(&child1) > 512 ||
79 CBS_len(&child2) > 512) {
80 return 0;
81 }
82
83 bssl::UniquePtr<BIGNUM> base(
84 BN_bin2bn(CBS_data(&child0), CBS_len(&child0), nullptr));
85 BN_set_negative(base.get(), sign % 2);
86 bssl::UniquePtr<BIGNUM> power(
87 BN_bin2bn(CBS_data(&child1), CBS_len(&child1), nullptr));
88 bssl::UniquePtr<BIGNUM> modulus(
89 BN_bin2bn(CBS_data(&child2), CBS_len(&child2), nullptr));
90
91 if (BN_is_zero(modulus.get())) {
92 return 0;
93 }
94
95 bssl::UniquePtr<BN_CTX> ctx(BN_CTX_new());
96 bssl::UniquePtr<BIGNUM> result(BN_new());
97 bssl::UniquePtr<BIGNUM> expected(BN_new());
98 CHECK(ctx);
99 CHECK(result);
100 CHECK(expected);
101
102 CHECK(mod_exp(expected.get(), base.get(), power.get(), modulus.get(),
103 ctx.get()));
104 CHECK(BN_mod_exp(result.get(), base.get(), power.get(), modulus.get(),
105 ctx.get()));
106 CHECK(BN_cmp(result.get(), expected.get()) == 0);
107
108 if (BN_is_odd(modulus.get())) {
109 bssl::UniquePtr<BN_MONT_CTX> mont(
110 BN_MONT_CTX_new_for_modulus(modulus.get(), ctx.get()));
111 CHECK(mont);
112 // |BN_mod_exp_mont| and |BN_mod_exp_mont_consttime| require reduced inputs.
113 CHECK(BN_nnmod(base.get(), base.get(), modulus.get(), ctx.get()));
114 CHECK(BN_mod_exp_mont(result.get(), base.get(), power.get(), modulus.get(),
115 ctx.get(), mont.get()));
116 CHECK(BN_cmp(result.get(), expected.get()) == 0);
117 CHECK(BN_mod_exp_mont_consttime(result.get(), base.get(), power.get(),
118 modulus.get(), ctx.get(), mont.get()));
119 CHECK(BN_cmp(result.get(), expected.get()) == 0);
120 }
121
122 uint8_t *data = (uint8_t *)OPENSSL_malloc(BN_num_bytes(result.get()));
123 BN_bn2bin(result.get(), data);
124 OPENSSL_free(data);
125
126 return 0;
127 }
128