symm/poly1305.c: Implement Bernstein's Monte-Carlo test.

I did run the full test once, but it took almost an hour.

diff --git a/symm/poly1305.c b/symm/poly1305.c
index 55fe37118d740de0f77ecaad7f829423061963c9..278895744b981c65c9708eac177804a52410ac31 100644 (file)
--- a/symm/poly1305.c
+++ b/symm/poly1305.c
@@ -852,6 +852,8 @@ void poly1305_done(poly1305_ctx *ctx, void *h)
 
 #include <mLib/testrig.h>
 
 
 #include <mLib/testrig.h>
 

+#include "rijndael-ecb.h"
+

 static int vrf_hash(dstr v[])
 {
   poly1305_key k;
 static int vrf_hash(dstr v[])
 {
   poly1305_key k;


@@ -934,11 +936,76 @@ static int vrf_cat(dstr v[])
   return (ok);
 }
 
   return (ok);
 }
 

+#define MSZMAX 1000
+
+static int vrf_mct(dstr v[])
+{
+  unsigned j, msz;
+  unsigned long i, niter;
+  rijndael_ecbctx rij;
+  poly1305_key key;
+  poly1305_ctx mac;
+  dstr d = DSTR_INIT;
+  octet k[16], r[16], n[16], s[16], *t, m[MSZMAX] = { 0 };
+  int ok = 1;
+
+  if (v[0].len != sizeof(k)) { fprintf(stderr, "AES key len\n"); exit(2); }
+  if (v[1].len != sizeof(r)) { fprintf(stderr, "poly key len\n"); exit(2); }
+  if (v[2].len != sizeof(n)) { fprintf(stderr, "nonce len\n"); exit(2); }
+  if (v[4].len != sizeof(n)) { fprintf(stderr, "result len\n"); exit(2); }
+  memcpy(k, v[0].buf, sizeof(k));
+  memcpy(r, v[1].buf, sizeof(k));
+  memcpy(n, v[2].buf, sizeof(k));
+  niter = *(unsigned long *)v[3].buf;
+  dstr_ensure(&d, 16); d.len = 16; t = (octet *)d.buf;
+
+  rijndael_ecbinit(&rij, k, sizeof(k), 0);
+  poly1305_keyinit(&key, r, sizeof(r));
+  for (i = 0; i < niter; i++) {
+    msz = 0;
+    for (;;) {
+      rijndael_ecbencrypt(&rij, n, s, 16);
+      poly1305_macinit(&mac, &key, s);
+      poly1305_hash(&mac, m, msz);
+      poly1305_done(&mac, t);
+      if (msz >= MSZMAX) break;
+      n[0] ^= i&0xff;
+      for (j = 0; j < 16; j++) n[j] ^= t[j];
+      if (msz%2) {
+       for (j = 0; j < 16; j++) k[j] ^= t[j];
+       rijndael_ecbinit(&rij, k, sizeof(k), 0);
+      }
+      if (msz%3) {
+       for (j = 0; j < 16; j++) r[j] ^= t[j];
+       poly1305_keyinit(&key, r, sizeof(r));
+      }
+      m[msz++] ^= t[0];
+    }
+  }
+
+  if (memcmp(t, v[4].buf, 16) != 0) {
+    ok = 0;
+    fprintf(stderr, "failed...");
+    fprintf(stderr, "\n\tinitial k = "); type_hex.dump(&v[0], stderr);
+    fprintf(stderr, "\n\tinitial r = "); type_hex.dump(&v[1], stderr);
+    fprintf(stderr, "\n\tinitial n = "); type_hex.dump(&v[2], stderr);
+    fprintf(stderr, "\n\titerations = %lu", niter);
+    fprintf(stderr, "\n\texpected = "); type_hex.dump(&v[4], stderr);
+    fprintf(stderr, "\n\tcalculated = "); type_hex.dump(&d, stderr);
+    fputc('\n', stderr);
+  }
+
+  dstr_destroy(&d);
+  return (ok);
+}
+

 static const struct test_chunk tests[] = {
   { "poly1305-hash", vrf_hash,
     { &type_hex, &type_hex, &type_hex, &type_hex } },
   { "poly1305-cat", vrf_cat,
     { &type_hex, &type_hex, &type_hex, &type_hex, &type_hex, &type_hex } },
 static const struct test_chunk tests[] = {
   { "poly1305-hash", vrf_hash,
     { &type_hex, &type_hex, &type_hex, &type_hex } },
   { "poly1305-cat", vrf_cat,
     { &type_hex, &type_hex, &type_hex, &type_hex, &type_hex, &type_hex } },

+  { "poly1305-mct", vrf_mct,
+    { &type_hex, &type_hex, &type_hex, &type_ulong, &type_hex } },

   { 0, 0, { 0 } }
 };
 
   { 0, 0, { 0 } }
 };
 

diff --git a/symm/t/poly1305 b/symm/t/poly1305
index 7ec03805309fc0a5d0475a83329f384ed00b0132..b03a0a83763998403f31207244c7bd9b85d99c68 100644 (file)
--- a/symm/t/poly1305
+++ b/symm/t/poly1305
@@ -75,3 +75,38 @@ poly1305-cat {
     7973f622a43d14a6599b1f654cb45a74e355a5
     f3ffc7703f9400e52a7dfb4b3d3305d9;
 }
     7973f622a43d14a6599b1f654cb45a74e355a5
     f3ffc7703f9400e52a7dfb4b3d3305d9;
 }

+
+poly1305-mct {
+  ## Monte-Carlo test from https://cr.yp.to/mac/test.html.
+  ## Rather than check MD5 hashes of transcripts, I check the final tag
+  ## value.  These were calculated from transcripts of a scratch
+  ## implementation (utils/poly1305-mct.c) which I checked against the
+  ## reference hashes.
+  ##
+  ## [universe /tmp/mdw]{ ./poly1305-mct | tee >(md5sum >&3) | tail -n1; } 3>&1
+  ## 3ceb64843c00984c5c2b7897f499141b  -
+  ## df62013a9d388ea6e82cb7295fa706ec
+
+  00000000000000000000000000000000
+    00000000000000000000000000000000
+    00000000000000000000000000000000
+    1 596382b2c34704b87e291250fcb927fd;
+  00000000000000000000000000000000
+    00000000000000000000000000000000
+    00000000000000000000000000000000
+    10 7f1d971da577bdd6fb24437aaac845f5;
+  00000000000000000000000000000000
+    00000000000000000000000000000000
+    00000000000000000000000000000000
+    100 e1cb88ba2c498ade2091ab06cefa24fd;
+  00000000000000000000000000000000
+    00000000000000000000000000000000
+    00000000000000000000000000000000
+    1000 f7064b7217e8a6b74b381c58175d9ff2;
+
+  ## The full test.  This takes aaaaages.
+  ##00000000000000000000000000000000
+  ##  00000000000000000000000000000000
+  ##  00000000000000000000000000000000
+  ##  1000000 df62013a9d388ea6e82cb7295fa706ec;
+}

diff --git a/utils/poly1305-mct.c b/utils/poly1305-mct.c
new file mode 100644 (file)
index 0000000..ea0bc4c
--- /dev/null
+++ b/utils/poly1305-mct.c
@@ -0,0 +1,77 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <mLib/bits.h>
+
+#include "ct.h"
+#include "rijndael-ecb.h"
+#include "poly1305.h"
+
+#define MSZMAX 1000
+#define NITER 1000000
+
+int main(void)
+{
+  unsigned i, msz, ii;
+  rijndael_ecbctx rij;
+  poly1305_key key;
+  poly1305_ctx mac;
+  octet
+    r[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
+    n[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
+    k[16] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
+    s[16], t[16],
+    m[MSZMAX] = { 0 };
+#ifdef notdef
+  octet t0[16], t1[16];
+#endif
+
+  rijndael_ecbinit(&rij, k, sizeof(k), 0);
+  poly1305_keyinit(&key, r, sizeof(r));
+  for (ii = 0; ii < NITER; ii++) {
+    msz = 0;
+    for (;;) {
+      rijndael_ecbencrypt(&rij, n, s, 16);
+
+      poly1305_macinit(&mac, &key, s);
+      poly1305_hash(&mac, m, msz);
+      poly1305_done(&mac, t);
+      for (i = 0; i < sizeof(t); i++) printf("%02x", t[i]);
+      putchar('\n');
+
+#ifdef notdef
+      poly1305_macinit(&mac, &key, s);
+      poly1305_hash(&mac, m, msz);
+      poly1305_done(&mac, t0);
+      if (!ct_memeq(t, t0, sizeof(t))) {
+       fprintf(stderr, "verify failed\n");
+       exit(112);
+      }
+
+      t0[rand()%16] += 1 + rand()%255;
+      poly1305_macinit(&mac, &key, s);
+      poly1305_hash(&mac, m, msz);
+      poly1305_done(&mac, t1);
+      if (ct_memeq(t0, t1, sizeof(t))) {
+       fprintf(stderr, "verify accepted wrong tag\n");
+       exit(112);
+      }
+#endif
+
+      if (msz >= MSZMAX) break;
+      n[0] ^= ii;
+      for (i = 0; i < 16; i++) n[i] ^= t[i];
+      if (msz%2) {
+       for (i = 0; i < 16; i++) k[i] ^= t[i];
+       rijndael_ecbinit(&rij, k, sizeof(k), 0);
+      }
+      if (msz%3) {
+       for (i = 0; i < 16; i++) r[i] ^= t[i];
+       poly1305_keyinit(&key, r, sizeof(r));
+      }
+      m[msz++] ^= t[0];
+    }
+  }
+
+  return (0);
+}