Subject: [Cfrg] Trouble reproducing mulX_POLYVAL() test vector from RFC 8452 Appendix A

From: Tony Arcieri <[email-masked]>
Date: Thu, 5 Sep 2019 13:04:46 -0700

I've been trying to implement mulX_POLYVAL() as described in RFC 8452
Appendix A:

https://tools.ietf.org/html/rfc8452#appendix-A

It says:

Given the 16-byte string 01000000000000000000000000000000, [...]

mulX_POLYVAL of that string is 02000000000000000000000000000000.

As a more general example, given 9c98c04df9387ded828175a92ba652d8, [...]
mulX_POLYVAL of it is 3931819bf271fada0503eb52574ca5f2.

However, I am getting 3931819bf271fada0503eb52574ca572 (highest bit unset).
I'm not sure if it's a problem with my code, or the test vector.

Here is the code. If I remove the "... ^ (hbhi << 63) ^ ..." from the last
line of "mulx", it matches, but that seems like it wouldn't match POLYVAL's
polynomial? Or is there something else I'm missing?

#include <stdio.h>
#include <stdint.h>

static void
mulx(uint64_t *lo, uint64_t *hi)
{
        uint64_t hblo, hbhi;

        hblo = *lo >> 63;
        hbhi = *hi >> 63;
        *lo <<= 1;
        *hi <<= 1;
        *lo ^= hbhi;
        *hi ^= hblo ^ (hbhi << 63) ^ (hbhi << 62) ^ (hbhi << 57);
}

static uint64_t
dec64le(const void *src)
{
        const uint8_t *buf;
        int i;
        uint64_t x;

        buf = src;
        x = 0;
        for (i = 0; i < 8; i ++) {
                x |= (uint64_t)buf[i] << (8 * i);
        }
        return x;
}

static void
enc64le(void *dst, uint64_t x)
{
        uint8_t *buf;
        int i;

        buf = dst;
        for (i = 0; i < 8; i ++) {
                buf[i] = (uint8_t)(x >> (8 * i));
        }
}

static void
print128(const char *name, const void *src)
{
        const uint8_t *buf;
        int i;

        printf("%s = ", name);
        buf = src;
        for (i = 0; i < 16; i ++) {
                printf("%02x", buf[i]);
        }
        printf("\n");
}

int
main(void)
{
        /*
         * From RFC 8452:
         *
         * given 9c98c04df9387ded828175a92ba652d8, mulX_GHASH
         * of that string is 4e4c6026fc9c3ef6c140bad495d3296c and mulX_POLYVAL
         * of it is 3931819bf271fada0503eb52574ca5f2.
         */
        static const uint8_t kat_in[] = {
                0x9c, 0x98, 0xc0, 0x4d, 0xf9, 0x38, 0x7d, 0xed,
                0x82, 0x81, 0x75, 0xa9, 0x2b, 0xa6, 0x52, 0xd8
        };

        uint64_t lo, hi;
        uint8_t tmp[16];

        print128("in ", kat_in);
        lo = dec64le(kat_in);
        hi = dec64le(kat_in + 8);
        mulx(&lo, &hi);
        enc64le(tmp, lo);
        enc64le(tmp + 8, hi);
        print128("out", tmp);
        return 0;
}

-- 
Tony Arcieri

---

From: Adam Langley <[email-masked]>
Date: Thu, 5 Sep 2019 14:07:44 -0700

On Thu, Sep 5, 2019 at 1:05 PM Tony Arcieri <[email-masked]> wrote:

> However, I am getting 3931819bf271fada0503eb52574ca572 (highest bit
> unset). I'm not sure if it's a problem with my code, or the test vector.
>

Ah fuck, so do I. Indeed, even if I revert my test code back to the point
in time when I wrote that, I still get the same answer. I fear that it's a
transliteration error: I may have been editing the XML on a different
machine than the one that I had the code on and the '7' looked like an 'f'.

The IETF doesn't fix RFCs, but could you report an errata on it and then I
think I can mark it verified.

Cheers

AGL

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 5 Sep 2019 14:21:51 -0700

Thanks for confirming. I filed an errata report.

-- 
Tony Arcieri

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 6 Sep 2019 06:19:03 +0000

>think I can mark it verified.

Naah, leave it for awhile and see how many implementations get validated
against the incorrect vectors :-).  That's always been fun with some of the
NIST test vectors that have errors, implementations still get validated even
when the values are incorrect.

Peter.

​