I'm going to use the Simon Cipher as an example, but I want to frame the question to be more general. Why would the same cipher structure have a different optimal attack for different bit widths? I would think that structure would be what dictates the attack and not the bit width. SIMON32/64 and SIMON128/256 are virtually identical, with the only differences being key/block widths and round count. An integral attack is better on SIMON32/64 and linear hull attack is better on SIMON128/256.

Why is on attack better than the other for the same structure of cipher?


1 Answer 1


There are couple of reasons.

First of all, the notion that the relative power of different attack methods against a cipher depends only on the logical structure and not on the block and key size (at least in cases where these are independent of the structure) is a rough heuristic only.

Indeed, imagine as a trivial counterexample a cipher where the key size is variable and the subkeys are generated from the master key by a pseudorandom function. For small enough key size, our cipher will easily become formally "secure" against all attacks (but totally insecure from a practical point of view), because the cost of brute force search literally drops exponentially with key size. If the cipher is well designed, then at a sufficient number of rounds, it will be secure against all the standard attacks for some range of key sizes. But if we increase the key size sufficiently, it again becomes formally vulnerable to meet-in-the-middle attack, because now brute force search is more expensive than the meet-in-the-middle attack (although of course one could just claim less security than the master key size in this case).

Secondly, it is difficult to determine what the best attack on a cipher actually is, and this difficulty tends to increase with the size of the cipher. Much of the literature on cryptographic attacks uses a simplistic cost model where access to memory is very cheap and independent of the amount of memory an attack needs. In addition, it is often not clear what the true cost of a brute force attack would be and the best attacks in the literature are usually considered to be the ones that break the largest number of rounds at an estimated cost just shy of what the author thinks the cost of brute force key search would be. All of these effects together probably lead to a nontrivial percentage of published attacks being actually more expensive than brute force key search, which means that there is some randomness in the determination of which attack is best. This is true for any block/key size, but probably more pronounced for the larger ones, because reviewers cannot ask that the attack be demonstrated practically in full.

Thirdly, some attacks are easier to explore for small block and key sizes than for large ones; this means that some attacks that are known to work for small variants of a block cipher may well have an equally effective counterpart for a larger version, but we have not found it yet.

The most important reason, though, is in my opinion the first one mentioned: the study of small versions of a cipher can give us some hints about good directions of attack against bigger versions, but this is only a useful heuristic, not a law of nature.


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.