Coverage Report

Created: 2020-06-30 13:58

/src/botan/src/fuzzer/ecc_helper.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
* (C) 2015,2016 Jack Lloyd
3
*
4
* Botan is released under the Simplified BSD License (see license.txt)
5
*/
6
7
#ifndef ECC_HELPERS_H_
8
#define ECC_HELPERS_H_
9
10
#include "fuzzers.h"
11
#include <botan/ec_group.h>
12
#include <botan/reducer.h>
13
#include <botan/numthry.h>
14
15
namespace {
16
17
inline std::ostream& operator<<(std::ostream& o, const Botan::PointGFp& point)
18
0
   {
19
0
   o << point.get_affine_x() << "," << point.get_affine_y();
20
0
   return o;
21
0
   }
Unexecuted instantiation: ecc_p384.cpp:(anonymous namespace)::operator<<(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, Botan::PointGFp const&)
Unexecuted instantiation: ecc_bp256.cpp:(anonymous namespace)::operator<<(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, Botan::PointGFp const&)
Unexecuted instantiation: ecc_p256.cpp:(anonymous namespace)::operator<<(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, Botan::PointGFp const&)
Unexecuted instantiation: ecc_p521.cpp:(anonymous namespace)::operator<<(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, Botan::PointGFp const&)
22
23
Botan::BigInt decompress_point(bool yMod2,
24
                               const Botan::BigInt& x,
25
                               const Botan::BigInt& curve_p,
26
                               const Botan::BigInt& curve_a,
27
                               const Botan::BigInt& curve_b)
28
3.13k
   {
29
3.13k
   Botan::BigInt xpow3 = x * x * x;
30
3.13k
31
3.13k
   Botan::BigInt g = curve_a * x;
32
3.13k
   g += xpow3;
33
3.13k
   g += curve_b;
34
3.13k
   g = g % curve_p;
35
3.13k
36
3.13k
   Botan::BigInt z = ressol(g, curve_p);
37
3.13k
38
3.13k
   if(z < 0)
39
1.39k
      throw Botan::Exception("Could not perform square root");
40
1.74k
41
1.74k
   if(z.get_bit(0) != yMod2)
42
951
      z = curve_p - z;
43
1.74k
44
1.74k
   return z;
45
1.74k
   }
ecc_p384.cpp:(anonymous namespace)::decompress_point(bool, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&)
Line
Count
Source
28
784
   {
29
784
   Botan::BigInt xpow3 = x * x * x;
30
784
31
784
   Botan::BigInt g = curve_a * x;
32
784
   g += xpow3;
33
784
   g += curve_b;
34
784
   g = g % curve_p;
35
784
36
784
   Botan::BigInt z = ressol(g, curve_p);
37
784
38
784
   if(z < 0)
39
312
      throw Botan::Exception("Could not perform square root");
40
472
41
472
   if(z.get_bit(0) != yMod2)
42
164
      z = curve_p - z;
43
472
44
472
   return z;
45
472
   }
ecc_bp256.cpp:(anonymous namespace)::decompress_point(bool, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&)
Line
Count
Source
28
762
   {
29
762
   Botan::BigInt xpow3 = x * x * x;
30
762
31
762
   Botan::BigInt g = curve_a * x;
32
762
   g += xpow3;
33
762
   g += curve_b;
34
762
   g = g % curve_p;
35
762
36
762
   Botan::BigInt z = ressol(g, curve_p);
37
762
38
762
   if(z < 0)
39
428
      throw Botan::Exception("Could not perform square root");
40
334
41
334
   if(z.get_bit(0) != yMod2)
42
159
      z = curve_p - z;
43
334
44
334
   return z;
45
334
   }
ecc_p256.cpp:(anonymous namespace)::decompress_point(bool, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&)
Line
Count
Source
28
765
   {
29
765
   Botan::BigInt xpow3 = x * x * x;
30
765
31
765
   Botan::BigInt g = curve_a * x;
32
765
   g += xpow3;
33
765
   g += curve_b;
34
765
   g = g % curve_p;
35
765
36
765
   Botan::BigInt z = ressol(g, curve_p);
37
765
38
765
   if(z < 0)
39
328
      throw Botan::Exception("Could not perform square root");
40
437
41
437
   if(z.get_bit(0) != yMod2)
42
298
      z = curve_p - z;
43
437
44
437
   return z;
45
437
   }
ecc_p521.cpp:(anonymous namespace)::decompress_point(bool, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&)
Line
Count
Source
28
824
   {
29
824
   Botan::BigInt xpow3 = x * x * x;
30
824
31
824
   Botan::BigInt g = curve_a * x;
32
824
   g += xpow3;
33
824
   g += curve_b;
34
824
   g = g % curve_p;
35
824
36
824
   Botan::BigInt z = ressol(g, curve_p);
37
824
38
824
   if(z < 0)
39
324
      throw Botan::Exception("Could not perform square root");
40
500
41
500
   if(z.get_bit(0) != yMod2)
42
330
      z = curve_p - z;
43
500
44
500
   return z;
45
500
   }
46
47
void check_ecc_math(const Botan::EC_Group& group,
48
                    const uint8_t in[], size_t len)
49
3.13k
   {
50
3.13k
   // These depend only on the group, which is also static
51
3.13k
   static const Botan::PointGFp base_point = group.get_base_point();
52
3.13k
53
3.13k
   // This is shared across runs to reduce overhead
54
3.13k
   static std::vector<Botan::BigInt> ws(Botan::PointGFp::WORKSPACE_SIZE);
55
3.13k
56
3.13k
   const size_t hlen = len / 2;
57
3.13k
   const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
58
3.13k
   const Botan::BigInt b = Botan::BigInt::decode(in + hlen, len - hlen);
59
3.13k
   const Botan::BigInt c = a + b;
60
3.13k
61
3.13k
   const Botan::PointGFp P1 = base_point * a;
62
3.13k
   const Botan::PointGFp Q1 = base_point * b;
63
3.13k
   const Botan::PointGFp R1 = base_point * c;
64
3.13k
65
3.13k
   const Botan::PointGFp S1 = P1 + Q1;
66
3.13k
   const Botan::PointGFp T1 = Q1 + P1;
67
3.13k
68
3.13k
   FUZZER_ASSERT_EQUAL(S1, R1);
69
3.13k
   FUZZER_ASSERT_EQUAL(T1, R1);
70
3.13k
71
3.13k
   const Botan::PointGFp P2 = group.blinded_base_point_multiply(a, fuzzer_rng(), ws);
72
3.13k
   const Botan::PointGFp Q2 = group.blinded_base_point_multiply(b, fuzzer_rng(), ws);
73
3.13k
   const Botan::PointGFp R2 = group.blinded_base_point_multiply(c, fuzzer_rng(), ws);
74
3.13k
   const Botan::PointGFp S2 = P2 + Q2;
75
3.13k
   const Botan::PointGFp T2 = Q2 + P2;
76
3.13k
77
3.13k
   FUZZER_ASSERT_EQUAL(S2, R2);
78
3.13k
   FUZZER_ASSERT_EQUAL(T2, R2);
79
3.13k
80
3.13k
   const Botan::PointGFp P3 = group.blinded_var_point_multiply(base_point, a, fuzzer_rng(), ws);
81
3.13k
   const Botan::PointGFp Q3 = group.blinded_var_point_multiply(base_point, b, fuzzer_rng(), ws);
82
3.13k
   const Botan::PointGFp R3 = group.blinded_var_point_multiply(base_point, c, fuzzer_rng(), ws);
83
3.13k
   const Botan::PointGFp S3 = P3 + Q3;
84
3.13k
   const Botan::PointGFp T3 = Q3 + P3;
85
3.13k
86
3.13k
   FUZZER_ASSERT_EQUAL(S3, R3);
87
3.13k
   FUZZER_ASSERT_EQUAL(T3, R3);
88
3.13k
89
3.13k
   FUZZER_ASSERT_EQUAL(S1, S2);
90
3.13k
   FUZZER_ASSERT_EQUAL(S1, S3);
91
3.13k
92
3.13k
   try
93
3.13k
      {
94
3.13k
      const auto yp = decompress_point(true, a, group.get_p(), group.get_a(), group.get_b());
95
3.13k
      const auto pt_p = group.blinded_var_point_multiply(group.point(a, yp), b, fuzzer_rng(), ws);
96
3.13k
97
3.13k
      const auto yn = -yp;
98
3.13k
      const auto pt_n = group.blinded_var_point_multiply(group.point(a, yn), b, fuzzer_rng(), ws);
99
3.13k
100
3.13k
      FUZZER_ASSERT_EQUAL(pt_p, -pt_n);
101
3.13k
      }
102
3.13k
   catch(...) {}
103
3.13k
   }
ecc_p384.cpp:(anonymous namespace)::check_ecc_math(Botan::EC_Group const&, unsigned char const*, unsigned long)
Line
Count
Source
49
784
   {
50
784
   // These depend only on the group, which is also static
51
784
   static const Botan::PointGFp base_point = group.get_base_point();
52
784
53
784
   // This is shared across runs to reduce overhead
54
784
   static std::vector<Botan::BigInt> ws(Botan::PointGFp::WORKSPACE_SIZE);
55
784
56
784
   const size_t hlen = len / 2;
57
784
   const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
58
784
   const Botan::BigInt b = Botan::BigInt::decode(in + hlen, len - hlen);
59
784
   const Botan::BigInt c = a + b;
60
784
61
784
   const Botan::PointGFp P1 = base_point * a;
62
784
   const Botan::PointGFp Q1 = base_point * b;
63
784
   const Botan::PointGFp R1 = base_point * c;
64
784
65
784
   const Botan::PointGFp S1 = P1 + Q1;
66
784
   const Botan::PointGFp T1 = Q1 + P1;
67
784
68
784
   FUZZER_ASSERT_EQUAL(S1, R1);
69
784
   FUZZER_ASSERT_EQUAL(T1, R1);
70
784
71
784
   const Botan::PointGFp P2 = group.blinded_base_point_multiply(a, fuzzer_rng(), ws);
72
784
   const Botan::PointGFp Q2 = group.blinded_base_point_multiply(b, fuzzer_rng(), ws);
73
784
   const Botan::PointGFp R2 = group.blinded_base_point_multiply(c, fuzzer_rng(), ws);
74
784
   const Botan::PointGFp S2 = P2 + Q2;
75
784
   const Botan::PointGFp T2 = Q2 + P2;
76
784
77
784
   FUZZER_ASSERT_EQUAL(S2, R2);
78
784
   FUZZER_ASSERT_EQUAL(T2, R2);
79
784
80
784
   const Botan::PointGFp P3 = group.blinded_var_point_multiply(base_point, a, fuzzer_rng(), ws);
81
784
   const Botan::PointGFp Q3 = group.blinded_var_point_multiply(base_point, b, fuzzer_rng(), ws);
82
784
   const Botan::PointGFp R3 = group.blinded_var_point_multiply(base_point, c, fuzzer_rng(), ws);
83
784
   const Botan::PointGFp S3 = P3 + Q3;
84
784
   const Botan::PointGFp T3 = Q3 + P3;
85
784
86
784
   FUZZER_ASSERT_EQUAL(S3, R3);
87
784
   FUZZER_ASSERT_EQUAL(T3, R3);
88
784
89
784
   FUZZER_ASSERT_EQUAL(S1, S2);
90
784
   FUZZER_ASSERT_EQUAL(S1, S3);
91
784
92
784
   try
93
784
      {
94
784
      const auto yp = decompress_point(true, a, group.get_p(), group.get_a(), group.get_b());
95
784
      const auto pt_p = group.blinded_var_point_multiply(group.point(a, yp), b, fuzzer_rng(), ws);
96
784
97
784
      const auto yn = -yp;
98
784
      const auto pt_n = group.blinded_var_point_multiply(group.point(a, yn), b, fuzzer_rng(), ws);
99
784
100
784
      FUZZER_ASSERT_EQUAL(pt_p, -pt_n);
101
784
      }
102
784
   catch(...) {}
103
784
   }
ecc_bp256.cpp:(anonymous namespace)::check_ecc_math(Botan::EC_Group const&, unsigned char const*, unsigned long)
Line
Count
Source
49
762
   {
50
762
   // These depend only on the group, which is also static
51
762
   static const Botan::PointGFp base_point = group.get_base_point();
52
762
53
762
   // This is shared across runs to reduce overhead
54
762
   static std::vector<Botan::BigInt> ws(Botan::PointGFp::WORKSPACE_SIZE);
55
762
56
762
   const size_t hlen = len / 2;
57
762
   const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
58
762
   const Botan::BigInt b = Botan::BigInt::decode(in + hlen, len - hlen);
59
762
   const Botan::BigInt c = a + b;
60
762
61
762
   const Botan::PointGFp P1 = base_point * a;
62
762
   const Botan::PointGFp Q1 = base_point * b;
63
762
   const Botan::PointGFp R1 = base_point * c;
64
762
65
762
   const Botan::PointGFp S1 = P1 + Q1;
66
762
   const Botan::PointGFp T1 = Q1 + P1;
67
762
68
762
   FUZZER_ASSERT_EQUAL(S1, R1);
69
762
   FUZZER_ASSERT_EQUAL(T1, R1);
70
762
71
762
   const Botan::PointGFp P2 = group.blinded_base_point_multiply(a, fuzzer_rng(), ws);
72
762
   const Botan::PointGFp Q2 = group.blinded_base_point_multiply(b, fuzzer_rng(), ws);
73
762
   const Botan::PointGFp R2 = group.blinded_base_point_multiply(c, fuzzer_rng(), ws);
74
762
   const Botan::PointGFp S2 = P2 + Q2;
75
762
   const Botan::PointGFp T2 = Q2 + P2;
76
762
77
762
   FUZZER_ASSERT_EQUAL(S2, R2);
78
762
   FUZZER_ASSERT_EQUAL(T2, R2);
79
762
80
762
   const Botan::PointGFp P3 = group.blinded_var_point_multiply(base_point, a, fuzzer_rng(), ws);
81
762
   const Botan::PointGFp Q3 = group.blinded_var_point_multiply(base_point, b, fuzzer_rng(), ws);
82
762
   const Botan::PointGFp R3 = group.blinded_var_point_multiply(base_point, c, fuzzer_rng(), ws);
83
762
   const Botan::PointGFp S3 = P3 + Q3;
84
762
   const Botan::PointGFp T3 = Q3 + P3;
85
762
86
762
   FUZZER_ASSERT_EQUAL(S3, R3);
87
762
   FUZZER_ASSERT_EQUAL(T3, R3);
88
762
89
762
   FUZZER_ASSERT_EQUAL(S1, S2);
90
762
   FUZZER_ASSERT_EQUAL(S1, S3);
91
762
92
762
   try
93
762
      {
94
762
      const auto yp = decompress_point(true, a, group.get_p(), group.get_a(), group.get_b());
95
762
      const auto pt_p = group.blinded_var_point_multiply(group.point(a, yp), b, fuzzer_rng(), ws);
96
762
97
762
      const auto yn = -yp;
98
762
      const auto pt_n = group.blinded_var_point_multiply(group.point(a, yn), b, fuzzer_rng(), ws);
99
762
100
762
      FUZZER_ASSERT_EQUAL(pt_p, -pt_n);
101
762
      }
102
762
   catch(...) {}
103
762
   }
ecc_p256.cpp:(anonymous namespace)::check_ecc_math(Botan::EC_Group const&, unsigned char const*, unsigned long)
Line
Count
Source
49
765
   {
50
765
   // These depend only on the group, which is also static
51
765
   static const Botan::PointGFp base_point = group.get_base_point();
52
765
53
765
   // This is shared across runs to reduce overhead
54
765
   static std::vector<Botan::BigInt> ws(Botan::PointGFp::WORKSPACE_SIZE);
55
765
56
765
   const size_t hlen = len / 2;
57
765
   const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
58
765
   const Botan::BigInt b = Botan::BigInt::decode(in + hlen, len - hlen);
59
765
   const Botan::BigInt c = a + b;
60
765
61
765
   const Botan::PointGFp P1 = base_point * a;
62
765
   const Botan::PointGFp Q1 = base_point * b;
63
765
   const Botan::PointGFp R1 = base_point * c;
64
765
65
765
   const Botan::PointGFp S1 = P1 + Q1;
66
765
   const Botan::PointGFp T1 = Q1 + P1;
67
765
68
765
   FUZZER_ASSERT_EQUAL(S1, R1);
69
765
   FUZZER_ASSERT_EQUAL(T1, R1);
70
765
71
765
   const Botan::PointGFp P2 = group.blinded_base_point_multiply(a, fuzzer_rng(), ws);
72
765
   const Botan::PointGFp Q2 = group.blinded_base_point_multiply(b, fuzzer_rng(), ws);
73
765
   const Botan::PointGFp R2 = group.blinded_base_point_multiply(c, fuzzer_rng(), ws);
74
765
   const Botan::PointGFp S2 = P2 + Q2;
75
765
   const Botan::PointGFp T2 = Q2 + P2;
76
765
77
765
   FUZZER_ASSERT_EQUAL(S2, R2);
78
765
   FUZZER_ASSERT_EQUAL(T2, R2);
79
765
80
765
   const Botan::PointGFp P3 = group.blinded_var_point_multiply(base_point, a, fuzzer_rng(), ws);
81
765
   const Botan::PointGFp Q3 = group.blinded_var_point_multiply(base_point, b, fuzzer_rng(), ws);
82
765
   const Botan::PointGFp R3 = group.blinded_var_point_multiply(base_point, c, fuzzer_rng(), ws);
83
765
   const Botan::PointGFp S3 = P3 + Q3;
84
765
   const Botan::PointGFp T3 = Q3 + P3;
85
765
86
765
   FUZZER_ASSERT_EQUAL(S3, R3);
87
765
   FUZZER_ASSERT_EQUAL(T3, R3);
88
765
89
765
   FUZZER_ASSERT_EQUAL(S1, S2);
90
765
   FUZZER_ASSERT_EQUAL(S1, S3);
91
765
92
765
   try
93
765
      {
94
765
      const auto yp = decompress_point(true, a, group.get_p(), group.get_a(), group.get_b());
95
765
      const auto pt_p = group.blinded_var_point_multiply(group.point(a, yp), b, fuzzer_rng(), ws);
96
765
97
765
      const auto yn = -yp;
98
765
      const auto pt_n = group.blinded_var_point_multiply(group.point(a, yn), b, fuzzer_rng(), ws);
99
765
100
765
      FUZZER_ASSERT_EQUAL(pt_p, -pt_n);
101
765
      }
102
765
   catch(...) {}
103
765
   }
ecc_p521.cpp:(anonymous namespace)::check_ecc_math(Botan::EC_Group const&, unsigned char const*, unsigned long)
Line
Count
Source
49
824
   {
50
824
   // These depend only on the group, which is also static
51
824
   static const Botan::PointGFp base_point = group.get_base_point();
52
824
53
824
   // This is shared across runs to reduce overhead
54
824
   static std::vector<Botan::BigInt> ws(Botan::PointGFp::WORKSPACE_SIZE);
55
824
56
824
   const size_t hlen = len / 2;
57
824
   const Botan::BigInt a = Botan::BigInt::decode(in, hlen);
58
824
   const Botan::BigInt b = Botan::BigInt::decode(in + hlen, len - hlen);
59
824
   const Botan::BigInt c = a + b;
60
824
61
824
   const Botan::PointGFp P1 = base_point * a;
62
824
   const Botan::PointGFp Q1 = base_point * b;
63
824
   const Botan::PointGFp R1 = base_point * c;
64
824
65
824
   const Botan::PointGFp S1 = P1 + Q1;
66
824
   const Botan::PointGFp T1 = Q1 + P1;
67
824
68
824
   FUZZER_ASSERT_EQUAL(S1, R1);
69
824
   FUZZER_ASSERT_EQUAL(T1, R1);
70
824
71
824
   const Botan::PointGFp P2 = group.blinded_base_point_multiply(a, fuzzer_rng(), ws);
72
824
   const Botan::PointGFp Q2 = group.blinded_base_point_multiply(b, fuzzer_rng(), ws);
73
824
   const Botan::PointGFp R2 = group.blinded_base_point_multiply(c, fuzzer_rng(), ws);
74
824
   const Botan::PointGFp S2 = P2 + Q2;
75
824
   const Botan::PointGFp T2 = Q2 + P2;
76
824
77
824
   FUZZER_ASSERT_EQUAL(S2, R2);
78
824
   FUZZER_ASSERT_EQUAL(T2, R2);
79
824
80
824
   const Botan::PointGFp P3 = group.blinded_var_point_multiply(base_point, a, fuzzer_rng(), ws);
81
824
   const Botan::PointGFp Q3 = group.blinded_var_point_multiply(base_point, b, fuzzer_rng(), ws);
82
824
   const Botan::PointGFp R3 = group.blinded_var_point_multiply(base_point, c, fuzzer_rng(), ws);
83
824
   const Botan::PointGFp S3 = P3 + Q3;
84
824
   const Botan::PointGFp T3 = Q3 + P3;
85
824
86
824
   FUZZER_ASSERT_EQUAL(S3, R3);
87
824
   FUZZER_ASSERT_EQUAL(T3, R3);
88
824
89
824
   FUZZER_ASSERT_EQUAL(S1, S2);
90
824
   FUZZER_ASSERT_EQUAL(S1, S3);
91
824
92
824
   try
93
824
      {
94
824
      const auto yp = decompress_point(true, a, group.get_p(), group.get_a(), group.get_b());
95
824
      const auto pt_p = group.blinded_var_point_multiply(group.point(a, yp), b, fuzzer_rng(), ws);
96
824
97
824
      const auto yn = -yp;
98
824
      const auto pt_n = group.blinded_var_point_multiply(group.point(a, yn), b, fuzzer_rng(), ws);
99
824
100
824
      FUZZER_ASSERT_EQUAL(pt_p, -pt_n);
101
824
      }
102
824
   catch(...) {}
103
824
   }
104
105
}
106
107
#endif