Source

`stdlib/tests/p256_test.cpp`

2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.

3// p256_test — NIST P-256 ECDSA correctness against the RFC 6979 Appendix A.2.5

4// test vector (P-256, SHA-256, message "sample"). Deterministic signing means

5// the (r, s) is fixed and checkable bit-for-bit; verification round-trips it.

7#include <array>

8#include <string>

10#include <gtest/gtest.h>

12#include "hashlib.hpp"

13#include "p256.hpp"

15namespace p256 = cheatah::p256;

17namespace {

19// hex (big-endian) -> raw bytes

20std::string unhex(const std::string& h) {

21 auto nib = [](char c) -> int {

22 if (c >= '0' && c <= '9') return c - '0';

23 if (c >= 'a' && c <= 'f') return c - 'a' + 10;

24 return c - 'A' + 10;

25 };

26 std::string out;

27 out.reserve(h.size() / 2);

28 for (std::size_t i = 0; i + 1 < h.size(); i += 2)

29 out.push_back(static_cast<char>((nib(h[i]) << 4) | nib(h[i + 1])));

30 return out;

31}

32std::string hex(const std::string& b) {

33 static const char* d = "0123456789abcdef";

34 std::string out;

35 for (unsigned char c : b) {

36 out.push_back(d[c >> 4]);

37 out.push_back(d[c & 15]);

38 }

39 return out;

40}

42// RFC 6979 A.2.5 — P-256, key + the "sample"/SHA-256 expected signature.

43const std::string kPriv = "C9AFA9D845BA75166B5C215767B1D6934E50C3DB36E89B127B8A622B120F6721";

44const std::string kUx = "60FED4BA255A9D31C961EB74C6356D68C049B8923B61FA6CE669622E60F29FB6";

45const std::string kUy = "7903FE1008B8BC99A41AE9E95628BC64F2F1B20C2D7E9F5177A3C294D4462299";

46const std::string kR = "EFD48B2AACB6A8FD1140DD9CD45E81D69D2C877B56AAF991C34D0EA84EAF3716";

47const std::string kS = "F7CB1C942D657C41D436C7A1B6E29F65F3E900DBB9AFF4064DC4AB2F843ACDA8";

49} // namespace

51TEST(CheatahP256, SignKnownVector) {

52 const std::string hash = cheatah::hashlib::sha256_digest("sample");

53 const std::string sig = p256::sign_raw(unhex(kPriv), hash);

54 ASSERT_EQ(sig.size(), 64u);

55 EXPECT_EQ(hex(sig.substr(0, 32)), "efd48b2aacb6a8fd1140dd9cd45e81d69d2c877b56aaf991c34d0ea84eaf3716");

56 EXPECT_EQ(hex(sig.substr(32, 32)), "f7cb1c942d657c41d436c7a1b6e29f65f3e900dbb9aff4064dc4ab2f843acda8");

57}

59TEST(CheatahP256, VerifyKnownVector) {

60 const std::string hash = cheatah::hashlib::sha256_digest("sample");

61 const std::string pub = unhex(kUx) + unhex(kUy);

62 const std::string sig = unhex(kR) + unhex(kS);

63 EXPECT_TRUE(p256::verify_raw(pub, hash, sig));

65 // A tampered signature must fail.

66 std::string bad = sig;

67 bad[63] ^= 0x01;

68 EXPECT_FALSE(p256::verify_raw(pub, hash, bad));

69 // A different message must fail.

70 EXPECT_FALSE(p256::verify_raw(pub, cheatah::hashlib::sha256_digest("test"), sig));

71}

73// SECURITY (invalid-curve point validation, SP 800-56A): a public key whose coordinates are in

74// range but does NOT satisfy y^2 = x^3 - 3x + b is rejected before it enters the group law.

75TEST(CheatahP256, RejectsOffCurvePublicKey) {

76 const std::string hash = cheatah::hashlib::sha256_digest("sample");

77 const std::string sig = unhex(kR) + unhex(kS);

78 const std::string good = unhex(kUx) + unhex(kUy);

79 ASSERT_TRUE(p256::verify_raw(good, hash, sig)); // the genuine (on-curve) key verifies

81 std::string off = good;

82 off[63] ^= 0x01; // flip the low bit of y: still < p, but no longer on the curve

83 EXPECT_FALSE(p256::verify_raw(off, hash, sig));

85 // A point with y = 0 (never on this curve) is also refused.

86 std::string y_zero = good;

87 for (int i = 32; i < 64; ++i) y_zero[i] = 0;

88 EXPECT_FALSE(p256::verify_raw(y_zero, hash, sig));

89}

91TEST(CheatahP256, PublicFromPrivate) {

92 const std::string pub = p256::public_from_private(unhex(kPriv));

93 ASSERT_EQ(pub.size(), 64u);

94 EXPECT_EQ(hex(pub.substr(0, 32)), "60fed4ba255a9d31c961eb74c6356d68c049b8923b61fa6ce669622e60f29fb6");

95 EXPECT_EQ(hex(pub.substr(32, 32)), "7903fe1008b8bc99a41ae9e95628bc64f2f1b20c2d7e9f5177a3c294d4462299");

96}

98TEST(CheatahP256, SignVerifyRoundTrip) {

99 const std::string hash = cheatah::hashlib::sha256_digest("the quick brown fox");

100 const std::string sig = p256::sign_raw(unhex(kPriv), hash);

101 ASSERT_EQ(sig.size(), 64u);

102 const std::string pub = unhex(kUx) + unhex(kUy);

103 EXPECT_TRUE(p256::verify_raw(pub, hash, sig));

104}

105

106// The P-256 group order n (big-endian). A "hash" whose leftmost 256 bits are >= n

107// exercises the FIPS 186-4 reduction in hash_to_scalar (e -= n once). Using exactly

108// n also drives geq's all-limbs-equal return path.

109const std::string kN = "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551";

110

111TEST(CheatahP256, HashToScalarReducesWhenGreaterThanOrder) {

112 const std::string pub = unhex(kUx) + unhex(kUy);

113 const std::string sig = unhex(kR) + unhex(kS);

114 // A 32-byte "hash" equal to n reduces to 0 (geq true via full equality); a hash

115 // of all-0xFF (> n) reduces by one n. Neither matches the real message, so verify

116 // returns false — we only need the reduction lines to execute.

117 EXPECT_FALSE(p256::verify_raw(pub, unhex(kN), sig));

118 EXPECT_FALSE(p256::verify_raw(pub, std::string(32, '\xff'), sig));

119 // Signing with such a digest must still produce a well-formed 64-byte signature

120 // that verifies against the derived key (round-trips through the reduced scalar).

121 const std::string msg_hash = std::string(32, '\xff');

122 const std::string s2 = p256::sign_raw(unhex(kPriv), msg_hash);

123 ASSERT_EQ(s2.size(), 64u);

124 EXPECT_TRUE(p256::verify_raw(pub, msg_hash, s2));

125}

126

127TEST(CheatahP256, VerifyDerWithLeadingZeroIntegers) {

128 // DER-encode the RFC 6979 (r, s): both start with a high bit set (0xEF / 0xF7),

129 // so DER requires a 0x00 sign byte — exercising der_to_rs's leading-zero strip.

130 const std::string r = unhex(kR), s = unhex(kS);

131 std::string der;

132 der.push_back(0x30);

133 der.push_back(0x46); // SEQUENCE, length 70

134 der.push_back(0x02);

135 der.push_back(0x21); // INTEGER, length 33 (32 + sign byte)

136 der.push_back(0x00);

137 der += r;

138 der.push_back(0x02);

139 der.push_back(0x21);

140 der.push_back(0x00);

141 der += s;

142 const std::string pub = unhex(kUx) + unhex(kUy);

143 const std::string hash = cheatah::hashlib::sha256_digest("sample");

144 EXPECT_TRUE(p256::verify_der(pub, hash, der));

145

146 // Malformed DER (wrong sequence length) must be rejected.

147 std::string bad = der;

148 bad[1] = 0x40;

149 EXPECT_FALSE(p256::verify_der(pub, hash, bad));

150}

151

152TEST(CheatahP256, RsToDerRoundTripsAndRejects) {

153 // The RFC 6979 (r, s) both have the top bit set, so the encoder must emit 0x00 sign bytes —

154 // and the result must byte-match the hand-built DER the verify test above accepts, then

155 // round-trip through verify_der against the real public key.

156 const std::string raw = unhex(kR) + unhex(kS);

157 const std::string der = p256::rs_to_der(raw);

158 ASSERT_FALSE(der.empty());

159 EXPECT_EQ(static_cast<unsigned char>(der[0]), 0x30u);

160 EXPECT_EQ(static_cast<unsigned char>(der[1]), 0x46u); // 70 bytes: two 33-byte INTEGERs

161 const std::string pub = unhex(kUx) + unhex(kUy);

162 const std::string hash = cheatah::hashlib::sha256_digest("sample");

163 EXPECT_TRUE(p256::verify_der(pub, hash, der));

164

165 // A small r (leading zeros, top bit clear) must MINIMALLY encode — strip zeros, no sign byte.

166 const std::string small = std::string(31, '\0') + "\x7f" + unhex(kS);

167 const std::string small_der = p256::rs_to_der(small);

168 ASSERT_FALSE(small_der.empty());

169 EXPECT_EQ(static_cast<unsigned char>(small_der[2]), 0x02u);

170 EXPECT_EQ(static_cast<unsigned char>(small_der[3]), 0x01u); // r shrank to one byte

171 EXPECT_EQ(static_cast<unsigned char>(small_der[4]), 0x7fu);

172

173 // Wrong length and zero integers are not signatures.

174 EXPECT_EQ(p256::rs_to_der(raw.substr(1)), "");

175 EXPECT_EQ(p256::rs_to_der(std::string(32, '\0') + unhex(kS)), "");

176 EXPECT_EQ(p256::rs_to_der(unhex(kR) + std::string(32, '\0')), "");

177

178 // Full circle: a fresh sign_raw -> rs_to_der -> verify_der chain on a random-ish key.

179 const std::string priv = unhex(kPriv);

180 const std::string sig_raw = p256::sign_raw(priv, hash);

181 ASSERT_EQ(sig_raw.size(), std::size_t{64});

182 EXPECT_TRUE(p256::verify_der(p256::public_from_private(priv), hash, p256::rs_to_der(sig_raw)));

183}

184

185TEST(CheatahP256, VerifyRejectsOutOfRangeAndInfinity) {

186 const std::string pub = unhex(kUx) + unhex(kUy);

187 const std::string hash = cheatah::hashlib::sha256_digest("sample");

188 // r or s == 0 -> reject.

189 EXPECT_FALSE(p256::verify_raw(pub, hash, std::string(32, '\0') + unhex(kS)));

190 EXPECT_FALSE(p256::verify_raw(pub, hash, unhex(kR) + std::string(32, '\0')));

191 // r or s >= n -> reject (use n and n+ff... both out of range).

192 EXPECT_FALSE(p256::verify_raw(pub, hash, unhex(kN) + unhex(kS)));

193 EXPECT_FALSE(p256::verify_raw(pub, hash, unhex(kR) + std::string(32, '\xff')));

194 // Public coordinate >= field prime p (all-0xFF x) -> reject.

195 EXPECT_FALSE(p256::verify_raw(std::string(32, '\xff') + unhex(kUy), hash, unhex(kR) + unhex(kS)));

196 // Wrong-size inputs -> reject.

197 EXPECT_FALSE(p256::verify_raw("short", hash, unhex(kR) + unhex(kS)));

198 EXPECT_FALSE(p256::verify_raw(pub, hash, "short"));

199 // sign_raw rejects a bad private key.

200 EXPECT_TRUE(p256::sign_raw("short", hash).empty());

201 EXPECT_TRUE(p256::sign_raw(std::string(32, '\0'), hash).empty());

202 EXPECT_TRUE(p256::sign_raw(unhex(kN), hash).empty()); // d == n, out of range

203 EXPECT_TRUE(p256::public_from_private("short").empty());

204 EXPECT_TRUE(p256::public_from_private(std::string(32, '\0')).empty());

205}

206

207// Subtract two 32-byte big-endian values (a - b), assuming a >= b.

208std::string be_sub(const std::string& a, const std::string& b) {

209 std::string r(32, '\0');

210 int borrow = 0;

211 for (int i = 31; i >= 0; --i) {

212 int av = static_cast<unsigned char>(a[i]);

213 int bv = static_cast<unsigned char>(b[i]) + borrow;

214 int d = av - bv;

215 if (d < 0) {

216 d += 256;

217 borrow = 1;

218 } else {

219 borrow = 0;

220 }

221 r[i] = static_cast<char>(d);

222 }

223 return r;

224}

225

226// Verifying against a pubkey equal to G, and to -G, forces the Strauss-Shamir

227// precompute table to add a point to ITSELF (G+G -> H==0, Rr==0, doubling branch)

228// and to its NEGATION (G+(-G) -> H==0, Rr!=0, point-at-infinity branch). These are

229// the two jac_add group-law special cases; the signatures need only be range-valid.

230TEST(CheatahP256, VerifyHitsGroupLawSpecialCases) {

231 const std::string p = unhex("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF");

232 // G = 1*G, derived from the implementation itself (avoids hand-transcribed hex).

233 const std::string G = p256::public_from_private(unhex(std::string(63, '0') + "1"));

234 ASSERT_EQ(G.size(), 64u);

235 const std::string gx = G.substr(0, 32), gy = G.substr(32, 32);

236 const std::string sig = unhex(kR) + unhex(kS);

237 const std::string hash = cheatah::hashlib::sha256_digest("sample");

238

239 // pubkey == G : tbl[1][1] = G + G (doubling special case)

240 (void)p256::verify_raw(G, hash, sig); // result irrelevant; the table path runs

241

242 // pubkey == -G = (Gx, p - Gy) : tbl[1][1] = G + (-G) (infinity special case)

243 const std::string pubNegG = gx + be_sub(p, gy);

244 (void)p256::verify_raw(pubNegG, hash, sig);

245}

246

247// The mod-n conditional subtraction only fires for x-coordinates in [n, p) — a

248// ~2^-128 event on real curve points, so it is driven directly through the test seam

249// on the SAME reduce_mod_n the sign/verify paths call.

250TEST(CheatahP256, ReduceModNBoundary) {

251 const std::string P = "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF";

252 // value == n -> reduces to 0.

253 EXPECT_EQ(hex(p256::testonly::reduce_mod_n_be(unhex(kN))), std::string(64, '0'));

254 // value == p-1 (in [n, p)) -> reduces by exactly n: (p-1) - n.

255 const std::string pm1 = be_sub(unhex(P), unhex(std::string(63, '0') + "1"));

256 const std::string reduced = p256::testonly::reduce_mod_n_be(pm1);

257 EXPECT_EQ(reduced, be_sub(pm1, unhex(kN)));

258 // value < n -> unchanged.

259 const std::string small = unhex(std::string(63, '0') + "7");

260 EXPECT_EQ(p256::testonly::reduce_mod_n_be(small), small);

261}

262

263// The signing/keygen scalar multiply is constant-time (no secret-dependent branch or table index).

264// Its branch-free point ops must agree with the branchy reference ops on EVERY case — including

265// a==b, a==-b and infinity operands that real nonces almost never produce — or a subtle CT bug

266// would silently corrupt signatures. The seam drives all of those directly.

267TEST(CheatahP256, ConstantTimePointOpsMatchReference) {

268 EXPECT_TRUE(p256::testonly::ct_point_selfcheck());

269}

270

271// The RFC 6979 retry loop and its "no candidate" exhaustion return are effectively

272// unreachable with real inputs (each rejection is a ~2^-128 event). The seam forces

273// rejections so the retry tail runs on the real signing code.

274TEST(CheatahP256, SignRetryLoop) {

275 const std::string hash = cheatah::hashlib::sha256_digest("sample");

276 const std::string pub = unhex(kUx) + unhex(kUy);

277 // Forcing one rejection still yields a valid (different) signature via the next

278 // candidate — exercising the retry tail while proving the loop stays correct.

279 const std::string sig = p256::testonly::sign_raw_skip(unhex(kPriv), hash, 1);

280 ASSERT_EQ(sig.size(), 64u);

281 EXPECT_TRUE(p256::verify_raw(pub, hash, sig));

282 // Forcing more rejections than the attempt cap exhausts the loop -> "".

283 EXPECT_TRUE(p256::testonly::sign_raw_skip(unhex(kPriv), hash, 100).empty());

284 // force_retries == 0 matches the public sign_raw exactly.

285 EXPECT_EQ(p256::testonly::sign_raw_skip(unhex(kPriv), hash, 0),

286 p256::sign_raw(unhex(kPriv), hash));

287}

288

289TEST(CheatahP256, SpkiExtractsPoint) {

290 // A SubjectPublicKeyInfo carrying the RFC 6979 public point: id-ecPublicKey +

291 // prime256v1, then BIT STRING 00 04 X Y.

292 const std::string point = std::string("\x04", 1) + unhex(kUx) + unhex(kUy); // 65 bytes

293 // Minimal SPKI: SEQUENCE { SEQUENCE { OID ecPublicKey, OID prime256v1 }, BIT STRING }

294 std::string spki;

295 // Algorithm OIDs (id-ecPublicKey 1.2.840.10045.2.1 and prime256v1 1.2.840.10045.3.1.7)

296 const std::string alg = unhex("301306072A8648CE3D020106082A8648CE3D030107");

297 std::string bitstr;

298 bitstr.push_back(0x03);

299 bitstr.push_back(0x42); // 66 bytes: 00 unused + 65-byte point

300 bitstr.push_back(0x00);

301 bitstr += point;

302 std::string inner = alg + bitstr;

303 spki.push_back(0x30);

304 spki.push_back(static_cast<char>(inner.size()));

305 spki += inner;

306 const std::string got = p256::spki_ec_point(spki);

307 ASSERT_EQ(got.size(), 64u);

308 EXPECT_EQ(got, unhex(kUx) + unhex(kUy));

309

310 // A DER with no uncompressed EC point returns "".

311 EXPECT_TRUE(p256::spki_ec_point(std::string("\x30\x03\x02\x01\x00", 5)).empty());

312 // A BIT STRING whose length byte is not 66 (compressed-point sized) is skipped.

313 std::string wronglen = std::string("\x03\x21\x00\x04", 4) + std::string(64, '\0');

314 EXPECT_TRUE(p256::spki_ec_point(wronglen).empty());

315}