Score:7

Notion of elementary operation when complexities in the form of $2^{128}$

cn flag

In lots of cryptoanalytic papers I read, attack complexities are stated in the form of a constant. For example, this related key attack on of AES states:

[...] For AES-256 we show the first key recovery attack that works for all the keys and has $2^{99.5}$ time and data complexity

I have seen this notation of $2^{n}$ time in other papers too. However, it is unclear to me to which elementary operation is taken as a baseline for a "time" measurement? The underlying model is certainly not a turing-machine, so what is? For other algorithms, the big-O notation usually hides the constant factors, making the exact elementary operation an unimportant detail. But the cryptographic papers state the complexities exact, which is suprising to me.

kelalaka avatar
in flag
$2^n$ for the brute-force timing for $n$-bit AES like $2^{128}$. Big-O notation is not correct since $n$ is constant here!.
kelalaka avatar
in flag
[What is the time and space complexity of the AES S-boxes?](https://crypto.stackexchange.com/q/98477/18298)
Score:10
ng flag

For other algorithms, the big-O notation usually hides the constant factors, making the exact elementary operation an unimportant detail. But the cryptographic papers state the complexities exact, which is surprising to me.

You're right to be surprised --- in general, writing "exact complexities" is hopeless due to what is known as the linear speedup theorem --- we can only pin down computational complexties up to an arbitrary multiplicative factor. This is because we can always increase the size of the underlying alphabet by some constant factor to allow us to compute a larger number of operations per unit time step. This (sort of) has a practical component --- you can increase the size of an instruction set architecture to do more computations per clock cycle (at the cost of chips using more silicon).

So what cost metric do people use? It really depends on the application. For example, a well-known attack on AES is the Biclique Attack, which recovers the AES key in complexity $2^{126.1}$. Of course, authors do not tend to claim arbitrary numbers as their results --- how do they compute this?

The full complexity of the independent biclique approach is evaluated as follows: $$C_{full} = 2^{n−2d}[C_{biclique} + C_{precomp} + C_{recomp} + C_{falsepos}],$$ where

  • $C_{precomp}$ is the complexity of the precomputation in Step 3. It is equivalent to less than $2^d$ runs of the subcipher $g$.
  • $C_{recomp}$ is the complexity of the recomputation of the internal variable $v$ $2^{2d}$ times. It strongly depends on the diffusion properties of the cipher. For AES this value varies from $2^{2d−1.5}$ to $2^{2d−4}$. The biclique construction is quite cheap in this paradigm. The method in Section 3.1 enables construction of a biclique in only $2^{d+1}$ calls of subcipher $f$. Therefore, usually the full key recovery complexity will be dominated by $2^{n−2d}C_{recomp}$. However, it is dependent on the width of the matching variable and biclique dimension $d$ too. We give more details for the case of AES in further sections. The memory complexity of the key recovery is upper-bounded by storing $2^d$ full computations of the cipher.

For AES in particular, they then say

Altogether, we need an equivalent of $3.4375$ SubBytes operations (i.e., 55 S-boxes), 2.3125 MixColumns operations, and a negligible amount of XORs in the key schedule. The number of SubBytes computations clearly is a larger summand. S-boxes are also the major contributor to the practical complexity of AES both in hardware and software. Therefore, if we aim for a single number that refers to the complexity, it makes sense to count the number of SubBytes operations that we need and compare it to that in the full cipher. The latter number is $10 + 2.5 = 12.5$ as we have to take the key schedule nonlinearity into account. As a result, $C_{recomp}$ is equivalent to $2^{16}\times 3.4375/12.5 = 2^{14.14}$ runs of the full AES-128. The values $C_{biclique}$ and $C_{precomp}$ together do not exceed $2^8$ calls of the full AES-128. The full computational complexity amounts to about $2^{112} (2^7 + 2^7 + 2^{14.14} + 2^8) = 2^{126.18}$.

This is to say that the "primitive operation" of the biclique attack is the number of SubBytes calls, where one normalizes things such that the brute force attack would take $2^{128}$ complexities.

There are of course other notions of complexity. For example

  • I've heard of an "Area x Time" metric, measuring the complexity of an attack in terms of the time it takes a certain size circuit to complete it (but cannot find references now),

  • similarly, it is common for attacks to measure both some notion of computational complexity along with some notion of memory/sample complexity,

  • in lattice-based cryptography, a certain metric known as the "Core SVP count" is fairly popular in analysis.

In general though, as it is not at all obvious what $2^{128}$ primitive operations means (for example), it is up to authors to define these terms, so they generally do.

kelalaka avatar
in flag
+1 for the bringing linear speedup theorem to the table. The authors theoretically calculated this against brute-force implementation requirements and removed some simple operations. The memory access and data storage, the other details make this far worse than brute-force. The process x time calculation is on the table since the Time-memory trade of Hellman.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.