From: Mark Wooding Date: Thu, 26 May 2016 08:26:09 +0000 (+0100) Subject: symm/poly1305.c: Implement Bernstein's Monte-Carlo test. X-Git-Tag: 2.4.0~59 X-Git-Url: https://git.distorted.org.uk/~mdw/catacomb/commitdiff_plain/47af781c8f727c45d0f74584f5f67521a4cbdfcb 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 55fe3711..27889574 100644 --- a/symm/poly1305.c +++ b/symm/poly1305.c @@ -852,6 +852,8 @@ void poly1305_done(poly1305_ctx *ctx, void *h) #include +#include "rijndael-ecb.h" + static int vrf_hash(dstr v[]) { poly1305_key k; @@ -934,11 +936,76 @@ static int vrf_cat(dstr v[]) 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 } }, + { "poly1305-mct", vrf_mct, + { &type_hex, &type_hex, &type_hex, &type_ulong, &type_hex } }, { 0, 0, { 0 } } }; diff --git a/symm/t/poly1305 b/symm/t/poly1305 index 7ec03805..b03a0a83 100644 --- a/symm/t/poly1305 +++ b/symm/t/poly1305 @@ -75,3 +75,38 @@ poly1305-cat { 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 index 00000000..ea0bc4c1 --- /dev/null +++ b/utils/poly1305-mct.c @@ -0,0 +1,77 @@ +#include +#include + +#include + +#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); +}