test/differential/ed25519-vs-libsodium.c

1/*

2 * Differential test: sigil-crypto's Ed25519 verify against libsodium's

3 * crypto_sign_verify_detached, the verifier the minisign tool uses.

4 *

5 * Input (stdin): one case per line, "<label> <pk-hex> <sig-hex> <msg-hex>"

6 * (msg-hex may be "-" for the empty message). For each case both verifiers

7 * run and the verdicts are printed. Then a mutation phase signs random

8 * messages with libsodium and flips single bits in the key, the signature

9 * and the message, comparing verdicts on every mutant.

10 *

11 * Output ends with a summary line

12 * SUMMARY cases=N agree=A expected-divergence=E disagree=D mutants=M ...

13 * and the exit status is 0 only when N > 0, D = 0, E = 3 (speccheck 4 and

14 * 5 and crafted-mixed-order-r, see below), no mutant is accepted or

15 * disagrees, all 200 unmutated

16 * signatures verify, and all 20 units (7 encoding boundaries, 10 small-order

17 * encodings, 3 large-order controls) pass.

18 *

19 * Build and run: test/differential/run.sh

20 */

22#include <stdio.h>

23#include <stdlib.h>

24#include <string.h>

26#include <sodium.h>

28#include "ed25519-verify.h"

30static int hexval(int c)

31{

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

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

34 if (c >= 'A' && c <= 'F') return c - 'A' + 10;

35 return -1;

36}

38/* Decode hex into out (capacity cap). Returns length, or -1. */

39static long unhex(const char *hex, unsigned char *out, size_t cap)

40{

41 if (strcmp(hex, "-") == 0) return 0;

42 size_t n = strlen(hex);

43 if (n % 2 != 0 || n / 2 > cap) return -1;

44 for (size_t i = 0; i < n / 2; i++) {

45 int hi = hexval(hex[2 * i]), lo = hexval(hex[2 * i + 1]);

46 if (hi < 0 || lo < 0) return -1;

47 out[i] = (unsigned char)(hi * 16 + lo);

48 }

49 return (long)(n / 2);

50}

52static int sodium_verdict(const unsigned char *pk, const unsigned char *sig,

53 const unsigned char *msg, size_t len)

54{

55 return crypto_sign_verify_detached(sig, msg, len, pk) == 0;

56}

58int main(void)

59{

60 if (sodium_init() < 0) {

61 fprintf(stderr, "SETUP-FAILED: sodium_init\n");

62 return 2;

63 }

64 printf("libsodium %s\n", sodium_version_string());

66 static char line[1 << 20];

67 static unsigned char msg[1 << 19];

68 long cases = 0, agree = 0, disagree = 0, expected_diverged = 0;

70 while (fgets(line, sizeof line, stdin)) {

71 char label[256], pkh[256], sigh[512];

72 static char msgh[1 << 20];

73 if (line[0] == '#' || line[0] == '\n') continue;

74 if (sscanf(line, "%255s %255s %511s %1048575s",

75 label, pkh, sigh, msgh) != 4) {

76 fprintf(stderr, "SETUP-FAILED: bad input line: %s", line);

77 return 2;

78 }

79 unsigned char pk[32], sig[64];

80 long mlen;

81 if (unhex(pkh, pk, 32) != 32 || unhex(sigh, sig, 64) != 64 ||

82 (mlen = unhex(msgh, msg, sizeof msg)) < 0) {

83 /* Wrong-length keys or signatures are rejected by both APIs'

84 * callers before verification; skip them visibly. */

85 printf("SKIP %s (not 32-byte key / 64-byte signature)\n", label);

86 continue;

87 }

88 int ours = sigil_crypto_ed25519_verify(pk, msg, (size_t)mlen, sig);

89 int theirs = sodium_verdict(pk, sig, msg, (size_t)mlen);

90 cases++;

91 /* The documented divergence, cofactored (ours) against cofactorless

92 * (libsodium): speccheck cases 4 and 5 need a public key with a

93 * small-order component; crafted-mixed-order-r is an honest key with

94 * R = rB + T8. Only the key holder can produce either. They must

95 * diverge in exactly this direction (ours accepts, libsodium

96 * rejects); anything else is a finding. */

97 int expected_divergence = strcmp(label, "speccheck-4") == 0 ||

98 strcmp(label, "speccheck-5") == 0 ||

99 strcmp(label, "crafted-mixed-order-r") == 0;

100 const char *tag;

101 if (expected_divergence) {

102 if (ours == 1 && theirs == 0) {

103 expected_diverged++;

104 tag = "EXPECTED-DIVERGENCE";

105 } else {

106 disagree++;

107 tag = "DIVERGENCE-CHANGED";

108 }

109 } else if (ours == theirs) {

110 agree++;

111 tag = "AGREE";

112 } else {

113 disagree++;

114 tag = "DISAGREE";

115 }

116 printf("%s %s ours=%d libsodium=%d\n", tag, label, ours, theirs);

117 }

118

119 /* Mutation phase: valid signatures from libsodium, one bit flipped. */

120 long mutants = 0, mutant_disagree = 0, valid_ok = 0;

121 for (int round = 0; round < 200; round++) {

122 unsigned char pk[32], sk[64], sig[64], m[97];

123 size_t mlen = (size_t)(round % (int)sizeof m);

124 crypto_sign_keypair(pk, sk);

125 randombytes_buf(m, sizeof m);

126 crypto_sign_detached(sig, NULL, m, mlen, sk);

127 if (sigil_crypto_ed25519_verify(pk, m, mlen, sig) &&

128 sodium_verdict(pk, sig, m, mlen)) {

129 valid_ok++;

130 } else {

131 printf("DISAGREE unmutated round=%d\n", round);

132 mutant_disagree++;

133 }

134 for (int bit = 0; bit < 8; bit++) {

135 unsigned char p2[32], s2[64], m2[97];

136 memcpy(p2, pk, 32); memcpy(s2, sig, 64); memcpy(m2, m, sizeof m);

137 int which = (round + bit) % 3;

138 if (which == 0) {

139 p2[randombytes_uniform(32)] ^= (unsigned char)(1u << bit);

140 } else if (which == 1) {

141 s2[randombytes_uniform(64)] ^= (unsigned char)(1u << bit);

142 } else if (mlen > 0) {

143 m2[randombytes_uniform((uint32_t)mlen)] ^= (unsigned char)(1u << bit);

144 } else {

145 s2[0] ^= 1;

146 }

147 int ours = sigil_crypto_ed25519_verify(p2, m2, mlen, s2);

148 int theirs = sodium_verdict(p2, s2, m2, mlen);

149 mutants++;

150 if (ours != theirs || ours) {

151 /* Any accepted mutant is a finding, agreeing or not. */

152 printf("MUTANT-%s round=%d bit=%d which=%d ours=%d libsodium=%d\n",

153 ours == theirs ? "ACCEPTED" : "DISAGREE",

154 round, bit, which, ours, theirs);

155 mutant_disagree++;

156 }

157 }

158 }

159

160 /* Unit phase: the y < p encoding check at its boundaries. No signature

161 * can reach this check alone (a y >= p encoding of a large-order point

162 * has no known discrete log to sign with, and the small-order ones are

163 * also caught by the small-order check), so it is tested directly. */

164 struct { const char *label; int want; unsigned char last; unsigned char first; int mid_ff; } bounds[] = {

165 /* little-endian: first byte, 30 middle bytes, last byte */

166 { "y=p-1 (ec ff..ff 7f)", 1, 0x7f, 0xec, 1 },

167 { "y=p (ed ff..ff 7f)", 0, 0x7f, 0xed, 1 },

168 { "y=p+18 (ff ff..ff 7f)", 0, 0x7f, 0xff, 1 },

169 { "y=p, sign bit (ed ff..ff ff)", 0, 0xff, 0xed, 1 },

170 { "y=p-1, sign bit (ec ff..ff ff)",1, 0xff, 0xec, 1 },

171 { "y=0 (00..00)", 1, 0x00, 0x00, 0 },

172 { "y=2^254 (00..00 40)", 1, 0x40, 0x00, 0 },

173 };

174 long unit = 0, unit_bad = 0;

175 for (size_t i = 0; i < sizeof bounds / sizeof bounds[0]; i++) {

176 unsigned char p[32];

177 memset(p, bounds[i].mid_ff ? 0xff : 0x00, 32);

178 p[0] = bounds[i].first;

179 p[31] = bounds[i].last;

180 int got = sigil_crypto_ed25519_point_is_canonical(p);

181 unit++;

182 if (got != bounds[i].want) unit_bad++;

183 printf("%s canonical(%s) = %d, want %d\n",

184 got == bounds[i].want ? "UNIT-OK" : "UNIT-BAD",

185 bounds[i].label, got, bounds[i].want);

186 }

187

188 /* Unit phase: the small-order test against the 8-torsion subgroup,

189 * derived independently (Python, RFC 8032 section 6 arithmetic: [L]P

190 * for random points P until 8 distinct points appear). Also the two

191 * non-canonical encodings of torsion points (y = p, y = p + 1) and

192 * large-order controls that must NOT be flagged. */

193 static const char *const torsion[] = {

194 "0000000000000000000000000000000000000000000000000000000000000000", /* 4 */

195 "0000000000000000000000000000000000000000000000000000000000000080", /* 4 */

196 "0100000000000000000000000000000000000000000000000000000000000000", /* 1 */

197 "26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05", /* 8 */

198 "26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85", /* 8 */

199 "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a", /* 8 */

200 "c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa", /* 8 */

201 "ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f", /* 2 */

202 "edffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f", /* y=p (0) */

203 "eeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f", /* y=p+1 (1) */

204 };

205 static const char *const large_order[] = {

206 "d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a", /* RFC 8032 T1 */

207 "3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c", /* RFC 8032 T2 */

208 "5866666666666666666666666666666666666666666666666666666666666666", /* base point */

209 };

210 for (size_t i = 0; i < sizeof torsion / sizeof torsion[0]; i++) {

211 unsigned char p[32];

212 unhex(torsion[i], p, 32);

213 int got = sigil_crypto_ed25519_has_small_order(p);

214 unit++;

215 if (got != 1) unit_bad++;

216 printf("%s small-order(%s) = %d, want 1\n",

217 got == 1 ? "UNIT-OK" : "UNIT-BAD", torsion[i], got);

218 }

219 for (size_t i = 0; i < sizeof large_order / sizeof large_order[0]; i++) {

220 unsigned char p[32];

221 unhex(large_order[i], p, 32);

222 int got = sigil_crypto_ed25519_has_small_order(p);

223 unit++;

224 if (got != 0) unit_bad++;

225 printf("%s small-order(%s) = %d, want 0\n",

226 got == 0 ? "UNIT-OK" : "UNIT-BAD", large_order[i], got);

227 }

228

229 printf("SUMMARY cases=%ld agree=%ld expected-divergence=%ld disagree=%ld mutants=%ld "

230 "mutant-disagree=%ld valid-ok=%ld unit=%ld unit-bad=%ld\n",

231 cases, agree, expected_diverged, disagree, mutants, mutant_disagree, valid_ok,

232 unit, unit_bad);

233 return (cases > 0 && disagree == 0 && expected_diverged == 3 &&

234 mutant_disagree == 0 &&

235 valid_ok == 200 && unit == 20 && unit_bad == 0) ? 0 : 1;

236}