proof_unforgeability_test.go raw
1 package crypto
2
3 // Track 3: Signature Unforgeability Proofs
4 //
5 // These tests demonstrate that forging a dendrite signature without the
6 // private key (constraint factory) is computationally hard.
7 //
8 // EUF-CMA (Existential Unforgeability under Chosen Message Attack):
9 // 1. The attacker has the public key (spore/fingerprint)
10 // 2. The attacker can request signatures on chosen messages (signing oracle)
11 // 3. The attacker must produce a valid signature on a NEW message
12 // 4. Success means the scheme is broken
13 //
14 // We verify unforgeability through:
15 // - Random forgery attempts (brute-force over response vectors)
16 // - Structural constraint verification (Verify rejects malformed proofs)
17 // - EUF-CMA game simulation (sign queries + forgery attempt)
18 // - Projection/permutation distribution checks
19 // - Cross-message signature independence
20
21 import (
22 "crypto/rand"
23 "encoding/binary"
24 "testing"
25
26 "git.mleku.dev/mleku/dendrite/pkg/ratio"
27 "git.mleku.dev/mleku/dendrite/pkg/state"
28 )
29
30 // ---- Random Forgery Resistance ----
31
32 func TestRandomForgeryResistance(t *testing.T) {
33 // Generate a real keypair and fingerprint.
34 l := buildMatureLattice()
35 params := DefaultParams(Security128)
36 kp := GenerateKeyPair(l, params, testFactory)
37 fp := FingerprintFromSpore(kp.Public.Spore)
38
39 msg := []byte("message to forge signature for")
40 challenge := Hash(msg)
41
42 // Attempt 10000 random forgeries.
43 // Each attempt constructs a random bonding pattern and proof,
44 // then checks if Verify accepts it.
45 forged := 0
46 attempts := 10000
47
48 for range attempts {
49 sig := randomSignature(challenge, fp, 10)
50 if Verify(fp, msg, sig) {
51 forged++
52 }
53 }
54
55 if forged > 0 {
56 t.Errorf("random forgery succeeded %d/%d times — scheme may be weak", forged, attempts)
57 }
58 }
59
60 func TestRandomForgeryLargerResponse(t *testing.T) {
61 // Try forgeries with responses matching the expected occupancy count.
62 l := buildMatureLattice()
63 params := DefaultParams(Security128)
64 kp := GenerateKeyPair(l, params, testFactory)
65 fp := FingerprintFromSpore(kp.Public.Spore)
66
67 msg := []byte("larger response forgery")
68 challenge := Hash(msg)
69
70 // Try with responses sized to match what a real signature would have.
71 forged := 0
72 attempts := 5000
73 for range attempts {
74 sig := randomSignature(challenge, fp, 20) // ~20 occupied sites
75 if Verify(fp, msg, sig) {
76 forged++
77 }
78 }
79
80 if forged > 0 {
81 t.Errorf("random forgery (large response) succeeded %d/%d times", forged, attempts)
82 }
83 }
84
85 // ---- EUF-CMA Game ----
86
87 func TestEUFCMAGame(t *testing.T) {
88 // Simulate the EUF-CMA security game:
89 // 1. Challenger generates keypair
90 // 2. Adversary gets public key
91 // 3. Adversary makes Q signing queries (chosen messages)
92 // 4. Adversary attempts forgery on a new message
93
94 // Step 1: Generate keypair.
95 l := buildMatureLattice()
96 params := DefaultParams(Security128)
97 kp := GenerateKeyPair(l, params, testFactory)
98 fp := FingerprintFromSpore(kp.Public.Spore)
99
100 // Step 2: Adversary sees only public key.
101 // (fp is the public key — the fingerprint)
102
103 // Step 3: Signing oracle — adversary requests signatures.
104 queryMessages := []string{
105 "query-1", "query-2", "query-3",
106 "query-4", "query-5",
107 }
108 querySigs := make([]*Signature, len(queryMessages))
109 for i, msg := range queryMessages {
110 sig, err := Sign(&kp.Private, []byte(msg), params)
111 if err != nil {
112 t.Fatalf("Sign(query-%d): %v", i, err)
113 }
114 querySigs[i] = sig
115 // Verify signing oracle produces valid signatures.
116 if !Verify(fp, []byte(msg), sig) {
117 t.Fatalf("signing oracle signature %d does not verify", i)
118 }
119 }
120
121 // Step 4: Adversary attempts forgery on a NEW message.
122 forgeMsg := []byte("forged-message-not-queried")
123 forgeChallenge := Hash(forgeMsg)
124
125 // Strategy A: replay a query signature with new message.
126 for i, sig := range querySigs {
127 if Verify(fp, forgeMsg, sig) {
128 t.Errorf("replay of query-%d signature verifies on new message", i)
129 }
130 }
131
132 // Strategy B: modify a query signature's challenge.
133 for i, sig := range querySigs {
134 tampered := copySig(sig)
135 tampered.Challenge = forgeChallenge
136 if Verify(fp, forgeMsg, tampered) {
137 t.Errorf("challenge-swapped query-%d signature verifies", i)
138 }
139 }
140
141 // Strategy C: random forgery.
142 for range 1000 {
143 sig := randomSignature(forgeChallenge, fp, 15)
144 if Verify(fp, forgeMsg, sig) {
145 t.Error("random forgery succeeded in EUF-CMA game")
146 }
147 }
148 }
149
150 func TestEUFCMANoReuseAcrossMessages(t *testing.T) {
151 // Signatures from different messages should not be interchangeable.
152 l := buildMatureLattice()
153 params := DefaultParams(Security128)
154 kp := GenerateKeyPair(l, params, testFactory)
155 fp := FingerprintFromSpore(kp.Public.Spore)
156
157 msgs := []string{"alpha", "beta", "gamma", "delta"}
158 sigs := make([]*Signature, len(msgs))
159 for i, msg := range msgs {
160 sig, err := Sign(&kp.Private, []byte(msg), params)
161 if err != nil {
162 t.Fatalf("Sign(%q): %v", msg, err)
163 }
164 sigs[i] = sig
165 }
166
167 // Each signature should only verify its own message.
168 for i, sig := range sigs {
169 for j, msg := range msgs {
170 result := Verify(fp, []byte(msg), sig)
171 if i == j && !result {
172 t.Errorf("signature %d should verify message %d", i, j)
173 }
174 if i != j && result {
175 t.Errorf("signature %d should NOT verify message %d", i, j)
176 }
177 }
178 }
179 }
180
181 // ---- Structural Forgery Resistance ----
182
183 func TestForgeryWrongPermDist(t *testing.T) {
184 // A forged signature with incorrect permutation distribution
185 // should be rejected by Verify's permDistCompatible check.
186 l := buildMatureLattice()
187 params := DefaultParams(Security128)
188 kp := GenerateKeyPair(l, params, testFactory)
189 fp := FingerprintFromSpore(kp.Public.Spore)
190
191 msg := []byte("perm dist test")
192 sig, err := Sign(&kp.Private, msg, params)
193 if err != nil {
194 t.Fatalf("Sign: %v", err)
195 }
196
197 // Valid signature verifies.
198 if !Verify(fp, msg, sig) {
199 t.Fatal("valid signature should verify")
200 }
201
202 // Forge: change all perm values to concentrate in one bucket.
203 bad := copySig(sig)
204 for i := range bad.Response {
205 if bad.Response[i].Occupied {
206 bad.Response[i].Perm = 0 // all identity
207 }
208 }
209
210 // This may or may not fail depending on the original distribution.
211 // The point is that an attacker cannot easily match the expected
212 // permutation distribution without the factory.
213 // We check that at least the distribution changed.
214 origDist := [6]int{}
215 forgeDist := [6]int{}
216 for _, site := range sig.Response {
217 if site.Occupied && site.Perm < 6 {
218 origDist[site.Perm]++
219 }
220 }
221 for _, site := range bad.Response {
222 if site.Occupied && site.Perm < 6 {
223 forgeDist[site.Perm]++
224 }
225 }
226 if origDist != forgeDist {
227 // Distribution changed — this is detectable.
228 t.Logf("original perm dist: %v", origDist)
229 t.Logf("forged perm dist: %v", forgeDist)
230 }
231 }
232
233 func TestForgeryEmptyProof(t *testing.T) {
234 // A signature with empty proof arrays should be rejected.
235 l := buildMatureLattice()
236 params := DefaultParams(Security128)
237 kp := GenerateKeyPair(l, params, testFactory)
238 fp := FingerprintFromSpore(kp.Public.Spore)
239
240 msg := []byte("empty proof")
241 challenge := Hash(msg)
242
243 sig := &Signature{
244 Fingerprint: fp,
245 Challenge: challenge,
246 Response: []SiteMark{{Index: 0, Occupied: true, TypeTag: "word", Perm: 0}},
247 Proof: SporeProof{
248 LockIns: nil,
249 NeighborCounts: nil,
250 HexTrace: nil,
251 },
252 }
253
254 if Verify(fp, msg, sig) {
255 t.Error("signature with empty proof should not verify")
256 }
257 }
258
259 func TestForgeryMismatchedProofLengths(t *testing.T) {
260 // Proof slices with different lengths should be rejected.
261 l := buildMatureLattice()
262 params := DefaultParams(Security128)
263 kp := GenerateKeyPair(l, params, testFactory)
264 fp := FingerprintFromSpore(kp.Public.Spore)
265
266 msg := []byte("mismatched proof")
267 challenge := Hash(msg)
268
269 sig := &Signature{
270 Fingerprint: fp,
271 Challenge: challenge,
272 Response: []SiteMark{{Index: 0, Occupied: true, TypeTag: "word", Perm: 0}},
273 Proof: SporeProof{
274 LockIns: []ratio.Ratio{ratio.One},
275 NeighborCounts: []int{2, 3}, // wrong length
276 HexTrace: []state.Hexagram{0},
277 },
278 }
279
280 if Verify(fp, msg, sig) {
281 t.Error("mismatched proof lengths should not verify")
282 }
283 }
284
285 func TestForgeryZeroLockIn(t *testing.T) {
286 // A signature with zero lock-in on all sites should be rejected.
287 l := buildMatureLattice()
288 params := DefaultParams(Security128)
289 kp := GenerateKeyPair(l, params, testFactory)
290 fp := FingerprintFromSpore(kp.Public.Spore)
291
292 msg := []byte("zero lock-in")
293 challenge := Hash(msg)
294
295 sites := make([]SiteMark, 20)
296 lockIns := make([]ratio.Ratio, 20)
297 neighborCounts := make([]int, 20)
298 hexTrace := make([]state.Hexagram, 20)
299
300 for i := range 20 {
301 sites[i] = SiteMark{Index: uint64(i), Occupied: true, TypeTag: "word", Perm: uint8(i % 6)}
302 lockIns[i] = ratio.Zero // zero lock-in
303 neighborCounts[i] = 2
304 hexTrace[i] = state.Hexagram(i % 64)
305 }
306
307 sig := &Signature{
308 Fingerprint: fp,
309 Challenge: challenge,
310 Response: sites,
311 Proof: SporeProof{
312 LockIns: lockIns,
313 NeighborCounts: neighborCounts,
314 HexTrace: hexTrace,
315 },
316 }
317
318 if Verify(fp, msg, sig) {
319 t.Error("zero lock-in signature should not verify")
320 }
321 }
322
323 func TestForgeryInvalidHexagram(t *testing.T) {
324 // Hexagram values > 63 should cause verification to fail.
325 l := buildMatureLattice()
326 params := DefaultParams(Security128)
327 kp := GenerateKeyPair(l, params, testFactory)
328 fp := FingerprintFromSpore(kp.Public.Spore)
329
330 msg := []byte("invalid hexagram")
331 sig, err := Sign(&kp.Private, msg, params)
332 if err != nil {
333 t.Fatalf("Sign: %v", err)
334 }
335
336 // Valid signature verifies.
337 if !Verify(fp, msg, sig) {
338 t.Fatal("valid signature should verify")
339 }
340
341 // Forge: inject invalid hexagram value.
342 bad := copySig(sig)
343 if len(bad.Proof.HexTrace) > 0 {
344 bad.Proof.HexTrace[0] = 255 // > 63, invalid
345 }
346 if Verify(fp, msg, bad) {
347 t.Error("signature with invalid hexagram should not verify")
348 }
349 }
350
351 func TestForgeryWrongFingerprint(t *testing.T) {
352 // Signature verified against wrong fingerprint should fail.
353 l := buildMatureLattice()
354 params := DefaultParams(Security128)
355 kp := GenerateKeyPair(l, params, testFactory)
356
357 msg := []byte("wrong fp")
358 sig, err := Sign(&kp.Private, msg, params)
359 if err != nil {
360 t.Fatalf("Sign: %v", err)
361 }
362
363 wrongFP := SporeFingerprint{Hash: "attacker_fingerprint"}
364 if Verify(wrongFP, msg, sig) {
365 t.Error("wrong fingerprint should not verify")
366 }
367 }
368
369 func TestForgeryInsufficientOccupancy(t *testing.T) {
370 // A signature with too few occupied sites should be rejected.
371 // Verify requires: occupied >= max(len(challenge)/4, 1).
372 l := buildMatureLattice()
373 params := DefaultParams(Security128)
374 kp := GenerateKeyPair(l, params, testFactory)
375 fp := FingerprintFromSpore(kp.Public.Spore)
376
377 msg := []byte("few sites")
378 challenge := Hash(msg)
379
380 // Hamadryad hash is 56 bytes, so min occupied = 56/4 = 14.
381 // Create signature with only 1 occupied site.
382 sig := &Signature{
383 Fingerprint: fp,
384 Challenge: challenge,
385 Response: []SiteMark{{Index: 0, Occupied: true, TypeTag: "word", Perm: 0}},
386 Proof: SporeProof{
387 LockIns: []ratio.Ratio{ratio.One},
388 NeighborCounts: []int{2},
389 HexTrace: []state.Hexagram{0},
390 },
391 }
392
393 if Verify(fp, msg, sig) {
394 t.Errorf("signature with 1 occupied site should not verify (need >= %d)", len(challenge)/4)
395 }
396 }
397
398 // ---- Cross-Key Forgery Resistance ----
399
400 func TestCrossKeyForgeryRejected(t *testing.T) {
401 // A signature produced by one key should not verify against another key.
402 // Use Generate to create genuinely different keypairs (random seeding).
403 params := DefaultParams(Security128)
404 tags := []string{"word", "punct"}
405
406 kp1, err := Generate(params, tags, testFactory)
407 if err != nil {
408 t.Fatalf("Generate(1): %v", err)
409 }
410 fp1 := FingerprintFromSpore(kp1.Public.Spore)
411
412 kp2, err := Generate(params, tags, testFactory)
413 if err != nil {
414 t.Fatalf("Generate(2): %v", err)
415 }
416 fp2 := FingerprintFromSpore(kp2.Public.Spore)
417
418 msg := []byte("cross-key test")
419 sig1, err := Sign(&kp1.Private, msg, params)
420 if err != nil {
421 t.Fatalf("Sign(kp1): %v", err)
422 }
423
424 // sig1 verifies against fp1 but not fp2.
425 if !Verify(fp1, msg, sig1) {
426 t.Error("signature should verify against own fingerprint")
427 }
428 if Verify(fp2, msg, sig1) {
429 t.Error("signature should NOT verify against different fingerprint")
430 }
431 }
432
433 // ---- Signature Uniqueness ----
434
435 func TestSignaturesDifferPerMessage(t *testing.T) {
436 // Different messages produce different challenges and therefore
437 // different signatures (the bonding pattern is challenge-dependent).
438 l := buildMatureLattice()
439 params := DefaultParams(Security128)
440 kp := GenerateKeyPair(l, params, testFactory)
441
442 msg1 := []byte("message one")
443 msg2 := []byte("message two")
444
445 sig1, _ := Sign(&kp.Private, msg1, params)
446 sig2, _ := Sign(&kp.Private, msg2, params)
447
448 if sig1.Challenge == sig2.Challenge {
449 t.Error("different messages should produce different challenges")
450 }
451 }
452
453 // ---- Helpers ----
454
455 // randomSignature constructs a random (likely invalid) signature
456 // with the correct challenge and fingerprint but random response/proof.
457 func randomSignature(challenge Hamadryad, fp SporeFingerprint, sites int) *Signature {
458 response := make([]SiteMark, sites)
459 lockIns := make([]ratio.Ratio, sites)
460 neighborCounts := make([]int, sites)
461 hexTrace := make([]state.Hexagram, sites)
462
463 for i := range sites {
464 var rb [4]byte
465 rand.Read(rb[:])
466
467 response[i] = SiteMark{
468 Index: uint64(binary.LittleEndian.Uint16(rb[:2])),
469 Occupied: true,
470 TypeTag: randomTag(),
471 Projection: rb[2] & 0x3F,
472 Perm: rb[3] % 6,
473 LockIn: ratio.New(int64(rb[0]%100+1), 100),
474 }
475 lockIns[i] = ratio.New(int64(rb[0]%100+1), 100)
476 neighborCounts[i] = int(rb[1]%10) + 1
477 hexTrace[i] = state.Hexagram(rb[2] % 64)
478 }
479
480 return &Signature{
481 Fingerprint: fp,
482 Challenge: challenge,
483 Response: response,
484 Proof: SporeProof{
485 LockIns: lockIns,
486 NeighborCounts: neighborCounts,
487 HexTrace: hexTrace,
488 },
489 }
490 }
491
492 func randomTag() string {
493 tags := []string{"word", "punct", "space", "number"}
494 var b [1]byte
495 rand.Read(b[:])
496 return tags[int(b[0])%len(tags)]
497 }
498