2
$\begingroup$

I recently posted a question about AES dual ciphers based on a certain understanding of them. Now I am not so sure if my understanding is correct. AES: a question about dual ciphers and security

Originally I thought $AES$ dual ciphers were essentially the same as the original, but with slight (but equally secure) changes that would produce distinct ciphertexts.

For example, if we encrypted $M$ with $AES$, using key $K$, we would get ciphertext $C$. But I thought if we encrypted the same $M$, using the same $K$, but using some dual cipher $AES*$ we would get $C*$ (i.e. a different ciphertext).

However, from this paper I read (in the Intro, par. 3): ... how to make dual ciphers which are equivalent to the original Rijndael in all aspects ... the idea is to make another ciphers which generate the same ciphertext as the original Rijndael for the given plaintext and key.

This makes it sound as though the same input $M$, in ANY dual cipher (or is it just some?), will produce exactly the same ciphertext regardless of the dual cipher being used.

Is this correct? Or is it just the case for some dual ciphers?

$\endgroup$
3
$\begingroup$

$\newcommand{\compose}{\mathbin{\circ}}\DeclareMathOperator{\AES}{AES}\DeclareMathOperator{\Round}{Round}\DeclareMathOperator{\Final}{Final}\DeclareMathOperator{\KeyExpansion}{KeyExpansion}\DeclareMathOperator{\SubBytes}{SubBytes}\DeclareMathOperator{\ShiftRows}{ShiftRows}\DeclareMathOperator{\MixColumns}{MixColumns}\DeclareMathOperator{\AddRoundKey}{AddRoundKey}$The AES function is mathematically a composition of other functions: \begin{align*} \AES_k(m) &= \Final_\kappa({\Round_\kappa}^r(m)) \quad \text{where} \quad \kappa = \KeyExpansion(k), \\ \Round_\kappa(m) &= \AddRoundKey_\kappa(\MixColumns(\ShiftRows(\SubBytes(m)))), \\ \Final_\kappa(m) &= \AddRoundKey_\kappa(\ShiftRows(\SubBytes(m))). \end{align*} This is a mathematical description. You can write the same mathematical description as a composition of functions: \begin{align*} \AES_k &= \Final_\kappa \compose {\Round_\kappa}^r \quad \text{where} \quad \kappa = \KeyExpansion(k), \\ \Round_\kappa &= \AddRoundKey_\kappa \compose \MixColumns \compose \ShiftRows \compose \SubBytes, \\ \Final_\kappa &= \AddRoundKey_\kappa \compose \ShiftRows \compose \SubBytes. \end{align*} (Here ${\Round_\kappa}^r$ means $\Round_\kappa$ iterated $r$ times, i.e. $\Round_\kappa \compose \cdots \compose \Round_\kappa$.)

To implement AES, you could write software instructions, or design a circuit, that follows exactly this structure, by making a $\SubBytes$ circuit, and wiring it to a $\ShiftRows$ circuit, etc. Not all AES implementations do this. For example, Paulo Barreto adapted the composition of column and row transpositions with a table lookup into just a composition of table lookups (mathematical description, example source code).

Any physical implementation of AES will have physical characteristics like timing and power usage. Different physical implementations might be different approaches to evaluate the same function. For example, here are two C implementations of the mathematically same table lookup:

uint8_t S[256];

uint8_t
fast_vartime_lookup(uint8_t b)
{
        return S[b];
}

uint8_t
slow_consttime_lookup(uint8_t b)
{
        uint8_t m, r = 0, i = 0;

        do {
                m = ((b ^ i) - 1) >> 8;
                r |= S[i] & m;
        } while (++i);

        return r;
}

These are two ways to implement the $\SubBytes$ round function, and they could be written mathematically by two different compositions of different mathematical functions, although they always give the same results for the same inputs.

An AES implementation using fast_vartime_lookup and an AES implementation using slow_consttime_lookup could be called implementations of two self-dual ciphers—recall the definition of dual ciphers $E$ and $E'$ as the existence of functions $f$, $g$, and $h$ such that for every key $K$ and plaintext $P$, $f(E_K(P)) = E'_{g(K)}(h(P))$; in this case of self-dual ciphers, $f$, $g$, and $h$ are all the identity function, so that $E_K(P) = E'_K(P)$.

The pragmatic differences of fast_vartime_lookup and slow_consttime_lookup are in the mean and variance of the time they take to execute. The mean time of fast_vartime_lookup is much shorter than the mean time of slow_consttime_lookup, to the point that if handed an AES implementation using slow_consttime_lookup you would probably throw it away in disgust. But the variance of slow_consttime_lookup is near zero, whereas the variance of fast_vartime_lookup is significant, and the time that it takes depends on the values of secrets and the state of the machine's CPU cache—this is what enables cache-timing attacks to recover secrets by timing AES computations. Newer cipher designs like Threefish avoid the temptation to use leaky operations like fast_vartime_lookup in the first place.

The paper you cited is about thwarting different classes of attacks, namely power analysis, by using a circuit implementing a different self-dual cipher (or, just a differently structured circuit implementing the same cipher—same idea) for each round, and randomly chosen for each round, so that the adversary not only has to guess the key and/or plaintext and any other variations in power usage of the device, but also the choice of circuit at any given time when sampling.

This is not the only technique for thwarting power analysis—there is a large public literature on the subject, and doubtless an even larger secret proprietary literature because it usually lies in the domain of hardware manufacturers who clutch at trade secrets like pearls even though most of it is probably rediscovered over and over and over again by different hardware vendors.

Another example countermeasure in hardware is to compute everything simultaneously with its complement; of course, this costs extra area. Another one—which also works in software—is some form of blinding, typically in asymmetric crypto like RSA which has additional structure that is invariant under the private key operation: $(r c)^d \equiv r^d c^d \pmod n$, so since $r^e r^d \equiv 1 \pmod n$, $c^d \equiv r^e r^d c^d \equiv r^e (r c)^d \pmod n$; thus you can pre-multiply by a random $r$ and post-multiply by $r^e$ so that the base of the modular exponentiation is uniform random and independent of the secret $c$. This doesn't work generically with AES because AES is designed to destroy all structure coming into it like a supervillain bent on bringing the apocalypse, but the randomization of circuits implementing the round function is a variation on the theme.

$\endgroup$

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.