What is 'security margin'?

Question

I have been academic papers about Rijndael, Serpent, and Twofish, and there is this term that is vague to me. I cannot find a tangible definition in google. Can someone briefly define, describe, and/or give examples about security margin and where it is used.

Answer 1

In this context 'security margin' is a measure for how much better we need to get at analyzing a cipher to break it. Such advances in cryptoanalysis require new ideas of how one might attack a cipher. Thus estimating how strong a cipher is, is hard.

Ultimately we can only tell something is broken, after we've broken it.

We typically look at a few properties to estimate the security margin:

• How much effort was put into analyzing this cipher?

  AES has seen a lot, finalists in a popular competition (Serpent etc.) have seen quite a bit, but less than AES, and some random guy's cipher has probably seen almost no effort at all.

• How well do we understand it?

  We have a decent understanding of certain block-cipher constructions with a clear iterated round structure. But we might not understand some new innovative cipher very well.

  For example NIST eliminated some candidates in the SHA-3 competition because their design was unusual and not understood very well.

• How many rounds are broken so far?

  For example a cipher where we've broken 2.5 out of 10 rounds is probably stronger than a cipher where 60 out of 80 rounds are broken if we understand both of them equally well.

  Ciphers with a clear round structure are often preferred. Typically breaking more rounds becomes a lot harder, and it provides at least some way to quantify how much progress was made in breaking the cipher.

  Lack of clear round structure makes sudden breaks more likely.

So if we put a lot of effort into analyzing some cipher, think we understand it well, and still only broke a few rounds, then we believe the security margin is large.

Resistance to brute-force can be easily quantified, estimating resistance to cryptoanalysis is full of guesswork and pretty subjective. So it's not surprising that you only find pretty vague statements.