3
$\begingroup$

Many of the cryptographic primitives currently in use have a number of their rounds already broken. Generally and with no particular primitive in mind, what is the scale of the effort to break one more round? Is is anything like $O(n)$, or more like $O(n^{something})$ where $n$ is the number of rounds for any individual primitive? In short, is breaking each additional round as easy or harder than the previous one? Or are there impediments other than simple computational time & effort?

So for example, assume an iterated primitive of $n$ rounds in total, where each round is $r_i$. I'm asking is it as easy to break $r_{i+1}$ as it was to break $r_{i}$? It seems to me that this relationship should be independent of $n$ itself within the particular primitive. I'm not comparing between primitives.

This question is loosely based on the numbers of broken rounds identified in Origin of values for "security margin"?.

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ The answer depends entirely on what primitive you're talking about. $\endgroup$
    – Squeamish Ossifrage
    Apr 12, 2019 at 1:37
  • $\begingroup$ @SqueamishOssifrage I've probably phased this question terribly, but I'm trying to think of the rounds only relative to each other within any single primitive, not between different primitives. So I'd 'a thought that this would be independent of the total number. Is it a linear effort or not kinda thing? $\endgroup$
    – Paul Uszak
    Apr 12, 2019 at 10:17
  • 2
    $\begingroup$ I see some downvotes and close votes for this question. Please note that this is not an answer; some leniency is allowed when the preconceptions of a question are off - in your opinion. $\endgroup$
    – Maarten Bodewes ♦
    Apr 12, 2019 at 15:27

1 Answer 1

Reset to default
6
$\begingroup$

Think of breaking through rounds as doing ballistics tests to see how deep a projectile can get into a defensive barrier. Breaking through the first layer or two is easy, but each subsequent layer becomes increasingly harder to penetrate. It would be impossible to ask exactly how difficult it is without knowing both the projectile and the defensive material. All you can say is that each layer makes it less and less likely that anything will get through. Breaking an iterated cipher is exactly like that, but with more math.

Generally and with no particular primitive in mind, what is the scale of the effort to break one more round?

There is no way to answer this without knowing the particular primitive you are talking about. In some cases, for a cipher with a small number of very complex rounds, extending an attack to another round may be a truly monumental effort and the discovery may be significant. For a cipher with a huge number of simple rounds, breaking one more may be just a matter of revisiting the original attack. In general, it's easier to extend an attack one more round for ciphers with a large number of simple rounds than with a few complex ones. This is why people tend to refer to broken rounds only in the context of the number of total rounds. Finding an attack that breaks 9 rounds is a big deal for a cipher with 10 rounds, but is not a big deal at all for a cipher with 72 rounds. That's why security margin is given as a percent.

In short, is breaking each additional round as easy or harder than the previous one?

Each round introduces more confusion and diffusion. With the exception of a few rare types of attacks which do not depend on the number of rounds (like slide attacks), following e.g. a differential trail or linear hull through more rounds may not be possible without using completely new techniques in the attack. In general, each additional round is significantly harder to break than the last.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. So you see it as an $O(n^{something})$ effort? $\endgroup$
    – Paul Uszak
    Apr 12, 2019 at 12:51
  • 2
    $\begingroup$ If you truly need to alter the attack to accommodate for the extra round then $n$ nor $something$ would be well defined. As they would not be the same as for the original attack, the big-O notation would not make all that much sense (I guess). $\endgroup$
    – Maarten Bodewes ♦
    Apr 12, 2019 at 14:15
  • $\begingroup$ @PaulUszak No, big-O notation can't be used for modeling the difficulty of discovering new attacks. $\endgroup$
    – forest ♦
    May 3, 2019 at 1:05
  • $\begingroup$ @forest I absolutely don't mean new attacks. I mean using the same attack ie. in a 5 round attack, was round 5 harder than round 4? That seems to follow O notation, or is there some other determinant? Or are such attacks not mounted incrementally like this? I'll have to edit to try and make it clearer. Sorry. $\endgroup$
    – Paul Uszak
    May 3, 2019 at 1:21
  • 1
    $\begingroup$ @PaulUszak Most cryptographic attacks against block ciphers involve trying to "track" a certain characteristic (often triggered by a chosen input or set of inputs) through rounds. As it passes through more rounds, this characteristic has an increasingly lower probability of surviving and becomes increasingly "weak". At the point when it can no longer pass through, that specific attack is finished and a new attack must be found to allow it to penetrate further. See theamazingking.com/crypto-linear.php and theamazingking.com/crypto-diff.php for some useful information. $\endgroup$
    – forest ♦
    May 3, 2019 at 1:28

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.