1
2 /*
3 * Copyright 2018 Google LLC
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 #include "fcp/secagg/shared/shamir_secret_sharing.h"
18
19 #include <cstdint>
20 #include <string>
21 #include <vector>
22
23 #include "gmock/gmock.h"
24 #include "gtest/gtest.h"
25 #include "fcp/secagg/shared/ecdh_keys.h"
26 #include "fcp/secagg/testing/ecdh_pregenerated_test_keys.h"
27 #include "fcp/secagg/testing/fake_prng.h"
28 namespace fcp {
29 namespace secagg {
30 namespace {
31 using ::testing::Eq;
TEST(ShamirSecretSharingTest,ShareReturnsTheAppropriateNumberOfShares)32 TEST(ShamirSecretSharingTest, ShareReturnsTheAppropriateNumberOfShares) {
33 ShamirSecretSharing shamir;
34 std::string secret = "abcdefghijklmnopqrstuvwxyz123456";
35 std::vector<ShamirShare> shares;
36 for (int num_shares = 2; num_shares < 5; ++num_shares) {
37 for (int threshold = 2; threshold <= num_shares; ++threshold) {
38 shares = shamir.Share(threshold, num_shares, secret);
39 EXPECT_THAT(shares.size(), Eq(num_shares));
40 }
41 }
42 }
TEST(ShamirSecretSharingTest,ShareFailsWhenTheSecretIsEmpty)43 TEST(ShamirSecretSharingTest, ShareFailsWhenTheSecretIsEmpty) {
44 ShamirSecretSharing shamir;
45 std::string secret = "";
46 EXPECT_DEATH(shamir.Share(2, 5, secret), "to_share must not be empty");
47 }
TEST(ShamirSecretSharingTest,ShareFailsWhenNumberOfSharesIsSmall)48 TEST(ShamirSecretSharingTest, ShareFailsWhenNumberOfSharesIsSmall) {
49 ShamirSecretSharing shamir;
50 std::string secret = "abcdefghijklmnopqrstuvwxyz123456";
51 EXPECT_DEATH(shamir.Share(1, 1, secret), "num_shares must be greater than 1");
52 }
TEST(ShamirSecretSharingTest,ShareFailsWhenTheThresholdIsOutOfBounds)53 TEST(ShamirSecretSharingTest, ShareFailsWhenTheThresholdIsOutOfBounds) {
54 ShamirSecretSharing shamir;
55 std::string secret = "abcdefghijklmnopqrstuvwxyz123456";
56 EXPECT_DEATH(shamir.Share(6, 5, secret),
57 "threshold must be at least 2 and at most num_shares");
58 EXPECT_DEATH(shamir.Share(1, 5, secret),
59 "threshold must be at least 2 and at most num_shares");
60 }
TEST(ShamirSecretSharingTest,ShareAndReconstructIntegrate)61 TEST(ShamirSecretSharingTest, ShareAndReconstructIntegrate) {
62 ShamirSecretSharing shamir;
63 std::string secret = "abcdefghijklmnopqrstuvwxyz123456";
64 std::vector<ShamirShare> shares;
65 int num_shares = 6;
66 int threshold = 4;
67 shares = shamir.Share(threshold, num_shares, secret);
68 auto reconstructed_or_error =
69 shamir.Reconstruct(threshold, shares, secret.size());
70 EXPECT_THAT(reconstructed_or_error.ok(), Eq(true));
71 EXPECT_THAT(reconstructed_or_error.value(), Eq(secret));
72 }
TEST(ShamirSecretSharingTest,ShareAndReconstructIntegrateWithMissingShares)73 TEST(ShamirSecretSharingTest, ShareAndReconstructIntegrateWithMissingShares) {
74 ShamirSecretSharing shamir;
75 std::string secret = "abcdefghijklmnopqrstuvwxyz123456";
76 std::vector<ShamirShare> shares;
77 int num_shares = 6;
78 int threshold = 4;
79 shares = shamir.Share(threshold, num_shares, secret);
80 shares[0].data = "";
81 shares[2].data = "";
82 auto reconstructed_or_error =
83 shamir.Reconstruct(threshold, shares, secret.size());
84 EXPECT_THAT(reconstructed_or_error.ok(), Eq(true));
85 EXPECT_THAT(reconstructed_or_error.value(), Eq(secret));
86 }
TEST(ShamirSecretSharingTest,ShareAndReconstructIntegrateWithZeroInSecret)87 TEST(ShamirSecretSharingTest, ShareAndReconstructIntegrateWithZeroInSecret) {
88 ShamirSecretSharing shamir;
89 std::string secret = "abcdefghijklmnopqrstuvwxyz123456";
90 secret[26] = '\0';
91 std::vector<ShamirShare> shares;
92 int num_shares = 6;
93 int threshold = 4;
94 shares = shamir.Share(threshold, num_shares, secret);
95 auto reconstructed_or_error =
96 shamir.Reconstruct(threshold, shares, secret.size());
97 EXPECT_THAT(reconstructed_or_error.ok(), Eq(true));
98 EXPECT_THAT(reconstructed_or_error.value(), Eq(secret));
99 }
TEST(ShamirSecretSharingTest,ShareAndReconstructIntegrateWithHighOrderCharactersInSecret)100 TEST(ShamirSecretSharingTest,
101 ShareAndReconstructIntegrateWithHighOrderCharactersInSecret) {
102 ShamirSecretSharing shamir;
103 std::string secret = "abcdefghijklmnopqrstuvwxyz123456";
104 secret[10] = static_cast<char>(128);
105 secret[20] = static_cast<char>(197);
106 secret[30] = static_cast<char>(255);
107 std::vector<ShamirShare> shares;
108 int num_shares = 6;
109 int threshold = 4;
110 shares = shamir.Share(threshold, num_shares, secret);
111 auto reconstructed_or_error =
112 shamir.Reconstruct(threshold, shares, secret.size());
113 EXPECT_THAT(reconstructed_or_error.ok(), Eq(true));
114 EXPECT_THAT(reconstructed_or_error.value(), Eq(secret));
115 }
TEST(ShamirSecretSharingTest,ShareAndReconstructIntegrateWithKeys)116 TEST(ShamirSecretSharingTest, ShareAndReconstructIntegrateWithKeys) {
117 ShamirSecretSharing shamir;
118 EcdhPregeneratedTestKeys keys;
119 std::vector<ShamirShare> shares;
120 int num_shares = 6;
121 int threshold = 4;
122 shares = shamir.Share(threshold, num_shares, keys.GetPrivateKeyString(3));
123 auto reconstructed_string_or_error =
124 shamir.Reconstruct(threshold, shares, EcdhPrivateKey::kSize);
125 EXPECT_THAT(reconstructed_string_or_error.ok(), Eq(true));
126 EcdhPrivateKey reconstructed(reinterpret_cast<const uint8_t*>(
127 reconstructed_string_or_error.value().c_str()));
128 EXPECT_THAT(reconstructed, Eq(keys.GetPrivateKey(3)));
129 EXPECT_THAT(reconstructed_string_or_error.value(),
130 Eq(keys.GetPrivateKeyString(3)));
131 }
TEST(ShamirSecretSharingTest,ReconstructFailsIfThresholdIsInvalid)132 TEST(ShamirSecretSharingTest, ReconstructFailsIfThresholdIsInvalid) {
133 ShamirSecretSharing shamir;
134 std::vector<ShamirShare> shares(5, {"fake"});
135 EXPECT_DEATH(auto secret_or_error = shamir.Reconstruct(1, shares, 16),
136 "threshold must be at least 2");
137 EXPECT_DEATH(
138 auto secret_or_error = shamir.Reconstruct(6, shares, 16),
139 "A vector of size 5 was provided, but threshold was specified as 6");
140 }
TEST(ShamirSecretSharingTest,ReconstructFailsIfSecretLengthSmall)141 TEST(ShamirSecretSharingTest, ReconstructFailsIfSecretLengthSmall) {
142 ShamirSecretSharing shamir;
143 std::vector<ShamirShare> shares(5, {"fake"});
144 EXPECT_DEATH(auto secret_or_error = shamir.Reconstruct(2, shares, 0),
145 "secret_length must be positive");
146 }
TEST(ShamirSecretSharingTest,ReconstructFailsIfSharesAreInvalid)147 TEST(ShamirSecretSharingTest, ReconstructFailsIfSharesAreInvalid) {
148 ShamirSecretSharing shamir;
149 std::vector<ShamirShare> shares(5, {"fakefakefakefakefake"});
150 shares[0].data = "bad";
151 EXPECT_DEATH(auto secret_or_error = shamir.Reconstruct(5, shares, 16),
152 "Share with index 0 is invalid: a share of size 3 was provided "
153 "but a multiple of 4 is expected");
154 shares[0].data = "baad";
155 EXPECT_DEATH(auto secret_or_error = shamir.Reconstruct(5, shares, 16),
156 "Share with index 1 is invalid: all shares must match sizes");
157 shares[0].data = "baadbaadbaadbaadbaadbaad";
158 EXPECT_DEATH(auto secret_or_error = shamir.Reconstruct(5, shares, 16),
159 "Share with index 0 is invalid: the number of subsecrets is 6 "
160 "but between 1 and 5 is expected");
161 shares[0].data = "";
162 auto secret_or_error = shamir.Reconstruct(5, shares, 16);
163 EXPECT_THAT(secret_or_error.ok(), Eq(false));
164 EXPECT_THAT(secret_or_error.status().message(),
165 testing::HasSubstr("Only 4 valid shares were provided, but "
166 "threshold was specified as 5"));
167 }
TEST(ShamirSecretSharingTest,ReconstructWorksWithPrecomputedShares)168 TEST(ShamirSecretSharingTest, ReconstructWorksWithPrecomputedShares) {
169 ShamirSecretSharing shamir;
170 std::vector<ShamirShare> shares(5);
171 int threshold = 3;
172 // These shares were generated by the legacy Java code.
173 uint8_t shares0[] = {112, 207, 118, 46, 110, 212, 170, 28};
174 shares[0].data = std::string(reinterpret_cast<char*>(shares0), 8);
175 uint8_t shares1[] = {48, 160, 197, 172, 38, 235, 145, 204};
176 shares[1].data = std::string(reinterpret_cast<char*>(shares1), 8);
177 uint8_t shares2[] = {63, 115, 238, 144, 40, 68, 183, 71};
178 shares[2].data = std::string(reinterpret_cast<char*>(shares2), 8);
179 uint8_t shares3[] = {29, 72, 240, 207, 114, 224, 26, 141};
180 shares[3].data = std::string(reinterpret_cast<char*>(shares3), 8);
181 uint8_t shares4[] = {74, 31, 204, 116, 6, 189, 187, 136};
182 shares[4].data = std::string(reinterpret_cast<char*>(shares4), 8);
183 ASSERT_THAT(shares[0].data.size(), Eq(8));
184 auto reconstructed_or_error = shamir.Reconstruct(threshold, shares, 4);
185 EXPECT_THAT(reconstructed_or_error.ok(), Eq(true));
186 EXPECT_THAT(reconstructed_or_error.value(), Eq(std::string({0, 0, 0, 33})));
187 }
188 } // namespace
189 } // namespace secagg
190 } // namespace fcp
191