1
$\begingroup$

The first part of the classical description of XEX is

$X = E_{k}(I) \otimes \alpha^j$

What I see a lot in sample code on the Internet is that you start with $T_ = E_{k}(I)$ and use that for the first block of the message. You then take $T$ and left shift it one bit. If the carry from that operation is a 1, then you XOR in 0x87 on the bottom byte. That becomes the pre- and post-crypto XOR material for the next block and so on.

This operation is exactly the same as the $K1$ and $K2$ derivation operations in CMAC. That's either an interesting coincidence or... well, I don't know.

Is that functionally correct?

$\endgroup$
  • $\begingroup$ Where did you get your profile picture? :-) Just curious $\endgroup$ – pushpen.paul Dec 27 '18 at 7:25
  • $\begingroup$ I’m a long-time FreeBSD user and stole the logo. $\endgroup$ – nsayer Dec 27 '18 at 15:24
2
$\begingroup$

You then take $T$ and left shift it one bit. If the carry from that operation is a 1, then you XOR in 0x87 on the bottom byte. That becomes the pre- and post-crypto XOR material for the next block and so on.

What's going on here is a finite field multiplication in the field $GF(2^{128})$, modulo the irreducible polynomial $x^{128} + x^7 + x^2 + x + 1$; if you look closely at the exponents of last four terms of that polynomial, they correspond to the positions of the one bits in 0b10000111 = 0x87. This shift-and-conditional-XOR trick is a cheap way of "doubling" a binary string in $GF(2^{128})$, i.e., multiplying it by the polynomial $x$, whose binary representation is the numeral for two. So sometimes you see the exact same thing notated as $2^n \cdot E_k(0)$, where the dot denotes multiplication in whichever finite field has been fixed for that context.

$\endgroup$
  • 1
    $\begingroup$ Also, it might be worth noting that the polynomial $x^{128}+x^7+x^2+x+1$ is the minimal binary irreducible polynomial of order 128 (in the sense of having the smallest number of terms, and the lexicographically smallest list of exponents among all irreducible polynomials with that many terms). Thus, it's not really a coincidence that, out of the huge number of possible polynomials, both schemes just happened to choose that particular one. $\endgroup$ – Ilmari Karonen May 8 '17 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.