Irreducible Polynomials for XTS mode of operation

This is the very short cheat sheet list for common block sizes of XTS mode of operation.

XTS mode of operation requires you to use an appropriate irreducible polynomial within it's tweak multiplication operation.

The basic code you will use for XTS multiply is derived from LibTomCrypt, optimized for the word size you use with your cipher (i.e., NOT the machine word size):

#define CIPHER_UNIT_TYPE uint32_t
#define CIPHER_UNIT_BITS 32
#define CIPHER_NR_BLOCK_UNITS 4 /* 32 * 4 = 128 bit block size */

static inline void xts_mult_x(CIPHER_UNIT_TYPE *x)
{
    size_t i, t, tt;

    for (i = t = 0; i < CIPHER_NR_BLOCK_UNITS; i++) {
        tt = x[i] >> (CIPHER_UNIT_BITS-1);
        x[i] = ((x[i] << 1) | t) & ((CIPHER_UNIT_TYPE)~0);
        t = tt;
    }
    if (tt) x[0] ^= (1<<7 | 1<<2 | 1<<1 | 1);
}

Here, the last line in function defines this irreducible polynomial:

x^128 + x^7 + x^2 + x^1 + 1

It is often referred as a constant 0x87 or 135, since the

(1<<7 | 1<<2 | 1<<1 | 1)

part is same as XOR with 0x87 (try to print this with printf(%02x) or in gdb).

It is the only thing you need to change to match XTS mode to your cipher's block size.

Here is the list of polynomials to use with XTS (with shift notations and XOR constants):

32 bit

x^32 + x^7 + x^3 + x^2 + 1
x[0] ^= (1<<7 | 1<<3 | 1<<2 | 1);

, or

x[0] ^= 0x8d;

In case if you'll want to go with Speck32 ;-)

48 bit

x^48 + x^5 + x^3 + x^2 + 1
x[0] ^= (1<<5 | 1<<3 | 1<<2 | 1);

, or

x[0] ^= 0x2d;

56 bit

x^56 + x^7 + x^4 + x^2 + 1
x[0] ^= (1<<7 | 1<<4 | 1<<2 | 1);

, or

x[0] ^= 0x95;

Maybe useful only for DES and very short files or messages (see below why). And DES was brute forced already in 1998.

64 bit

x^64 + x^4 + x^3 + x + 1
x[0] ^= (1<<4 | 1<<3 | 1<<1 | 1);

, or

x[0] ^= 0x1b;

The 64 bit block size maybe already phased out soon due to it's short length thus weak resistance against birthday paradox attacks such as SWEET32. However, this maybe mitigated easily with key change after the byte counter hits the (about) 32GB ceiling. Still, it is undesirable today to encrypt the terabytes lengthy disks with XTS and 64 bit block cipher, both for performance and privacy concerns, so this one is only for your reference.

Maybe useful for 3DES too.

80 bit

x^80 + x^9 + x^4 + x^2 + 1
x[0] ^= (1<<9 | 1<<4 | 1<<2 | 1);

, or

x[0] ^= 0x215;

80 bit block/key size ciphers are said to be weak against governmental eavesdropping, and are no longer recommended for future deployment and use.

96 bit

x^96 + x^10 + x^9 + x^6 + 1
x[0] ^= (1<<10 | 1<<9 | 1<<6 | 1);

, or

x[0] ^= 0x641;

Don't know why you even will need this, but there is a Speck96 variant.

128 bit

x^128 + x^7 + x^2 + x + 1
x[0] ^= (1<<7 | 1<<2 | 1<<1 | 1);

, or

x[0] ^= 0x87;

AES and AES finalists do use this block size. Many lightweight block ciphers do too. It's very common today.

160 bit

x^160 + x^5 + x^3 + x^2 + 1
x[0] ^= (1<<5 | 1<<3 | 1<<2 | 1);

, or

x[0] ^= 0x2d;

192 bit

x^192 + x^7 + x^2 + x^1 + 1
x[0] ^= (1<<7 | 1<<2 | 1<<1 | 1);

, or

x[0] ^= 0x87;

Same as 128 bit.

224 bit

x^224 + x^9 + x^8 + x^3 + 1
x[0] ^= (1<<9 | 1<<8 | 1<<3 | 1);

, or

x[0] ^= 0x309;

256 bit

x^256 + x^10 + x^5 + x^2 + 1
x[0] ^= (1<<10 | 1<<5 | 1<<2 | 1);

, or

x[0] ^= 0x425;

Future ciphers and Threefish256 do use this block size. As computers will evolve, this block size will be more and more common, hence you'll need this version.

320 bit

x^320 + x^4 + x^3 + x + 1
x[0] ^= (1<<4 | 1<<3 | 1<<1 | 1);

, or

x[0] ^= 0x1b;

Same as 64 bit above.

384 bit

x^384 + x^12 + x^3 + x^2 + 1
x[0] ^= (1<<12 | 1<<3 | 1<<2 | 1);

, or

x[0] ^= 0x100d;

448 bit

x^448 + x^11 + x^6 + x^4 + 1
x[0] ^= (1<<11 | 1<<6 | 1<<4 | 1);

, or

x[0] ^= 0x851;

512 bit

x^512 + x^8 + x^5 + x^2 + 1
x[0] ^= (1<<8 | 1<<5 | 1<<2 | 1);

, or

x[0] ^= 0x125;

Future ciphers and Threefish512 do use this block size. CIA grade security.

640 bit

x^640 + x^14 + x^3 + x^2 + 1
x[0] ^= (1<<14 | 1<<3 | 1<<2 | 1);

, or

x[0] ^= 0x400d;

768 bit

x^768 + x^19 + x^17 + x^4 + 1
x[0] ^= (1<<19 | 1<<17 | 1<<4 | 1);

, or

x[0] ^= 0xa0011;

Maybe you'll go combine Threefish512 + Threefish256 into single block, then XTS it? Who knows...

896 bit

x^896 + x^7 + x^5 + x^3 + 1
x[0] ^= (1<<7 | 1<<5 | 1<<3 | 1);

, or

x[0] ^= 0xa9;

1024 bit

x^1024 + x^19 + x^6 + x + 1
x[0] ^= (1<<19 | 1<<6 | 1<<1 | 1);

, or

x[0] ^= 0x80043;

Future ciphers and Threefish1024 do use this block size. CIA+ grade security. 128 byte block size. Oh my...

1280 bit

x^1280 + x^12 + x^7 + x^5 + 1
x[0] ^= (1<<12 | 1<<7 | 1<<5 | 1);

, or

x[0] ^= 0x10a1;

Maybe you'll go combine Threefish1024 + Threefish256 into single block, then XTS it? Who knows...

1536 bit

x^1536 + x^21 + x^6 + x^2 + 1
x[0] ^= (1<<21 | 1<<6 | 1<<2 | 1);

, or

x[0] ^= 0x200045;

Maybe you'll go combine Threefish1024 + Threefish512 into single block, then XTS it? Who knows...

2048 bit

x^2048 + x^19 + x^14 + x^13 + 1
x[0] ^= (1<<19 | 1<<14 | 1<<13 | 1);

, or

x[0] ^= 0x86001;

Maybe you'll go combine Threefish1024 + Threefish1024 into single block, then XTS it? Who knows...

4096 bit

x^4096 + x^27 + x^15 + x + 1
x[0] ^= (1<<27 | 1<<15 | 1<<1 | 1);

, or

x[0] ^= 0x8008003;

FDE encryption covering whole 512 byte sector. No ciphers are known to handle such size as of 2018. As AF4096 is gaining the market, 512 byte sector is soon to be phased out anyway...


This list was brought to you by Andrey Rys, Nov2018.