Polynomials for CMAC and GCM mode

[noloader]

We recently added variable block sizes and ciphers that incorporate them. Refer to the bug reports below. The larger block sizes require different polynomials. This ticket will track the related work.

We already accomplished the work for the polynomials for CMAC, but it should be documented. GCM mode is still outstanding.

According to Table of Low-Weight Binary Irreducible Polynomials, here are the 256, 512 and 1024-bit polynomials:

• x^256 + x^10 + x^5 + x + 1
• x^512 + x^8 + x^5 + x^2 + 1
• x^1024 + x^19 + x^6 + x + 1

Also see OMAC/CMAC constant for different block sizes on Crypto Stack Exchange.

---

Related bug reports:

• Add support for variable block sizes, GH #408
• Add Kalyna block cipher, GH #411
• Add Threefish block cipher, GH #422

[noloader]

The library already had the 256-bit CMAC polynomial. The 512 and 1024-bit CMAC polynomials were handled at:

• Commit 7697857481f5 (512-bit)
• Commit bc2678478ce9 (1024-bit)

[kerukuro]

Table of Low-Weight Binary Irreducible Polynomial (http://www.hpl.hp.com/techreports/98/HPL-98-135.pdf) lists 256,10,5,2 for 256-bit polynomial, which means x^256 + x^10 + x^5 + x^2 + 1.
Note that it ends with "x^2 + 1", not with "x + 1".
The same polynomial is listed in other sources, eg the book referenced in https://crypto.stackexchange.com/questions/35490/xts-and-256-bit-data-blocks
Which means the constant should be 0x425 (for ...x^2+1), not 0x423 (which is the constant for ...x+1)

See also this thread: http://sci.crypt.narkive.com/3lS5EbY4/omac-cmac-constants-for-different-block-sizes
-> 0x423 (x^256 + x^10 + x^5 + x + 1) is not irreducible.

[noloader]

Thanks @kerukuro.

Crud, it looks like a typo on out part. I think we need this change:

$ git diff cmac.cpp
diff --git a/cmac.cpp b/cmac.cpp
index 1b56662..ed56b10 100644
--- a/cmac.cpp
+++ b/cmac.cpp
@@ -32,9 +32,9 @@ static void MulU(byte *k, unsigned int length)
                        break;
                case 32:
                        // https://crypto.stackexchange.com/q/9815/10496
-                       // Polynomial x^256 + x^10 + x^5 + x + 1
+                       // Polynomial x^256 + x^10 + x^5 + x^2 + 1^M
                        k[30] ^= 4;
-                       k[31] ^= 0x23;
+                       k[31] ^= 0x25;^M
                        break;
                case 64:
                        // https://crypto.stackexchange.com/q/9815/10496

I was suspect of that for a long time. I think I convinced myself it was correct when it was wrong. My apologies for that.

Before I check it in, can you confirm it?

[kerukuro]

This looks like the correct fix. Thanks.

(FWIW I've also found an online gp calculator where one can test if a polynomial is irreducible using commands from the sci.crypt thread)

[noloader]

@kerukuro,

Thanks. Committed at fca8adc54976.

[noloader]

Thanks to @kerukuro we got the polynomials straitened out. Closing this ticket.