2
$\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?

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

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
1
  • 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, 2017 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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