Can we quantify strength of encryption scheme ?

Was wondering if we have any (or can we come up with) "units" for strength of encryption like in Physics. Most of our comparative analysis of encryption schemes are based on number of S boxes or number of rounds or proofs in a particular model or some times even performance of algorithms.

Is it possible at all for quantifying the security of encryption schemes objectively ? irrespective of the scheme's internal workings ? Say AES provides "X" units of Strength (under a particular attack, say IND-CCA2) Similar to how we quantify in Physics for temperature, pressure, weights etc.

I would imagine such metric should consider the encryption algorithm as black box

• Of course if you consider only that there is a primitive then the effective key size = the cryptographic strength (possibly bounded by the block size for the security of the plaintext), but I'm not sure if that's a very useful notion; strength is not a mathematical property in that sense. – Maarten Bodewes Dec 30 '14 at 16:47
• For symmetric algorithms that are secure by virtue of many skilled cryptographers attempting to break it I like to think in terms of kiloSchneiers. where a Schneier is the equivalent of one hour of concentrated study of the algorithm by a cryptographer of Bruce Schneier's caliber. And the creator of the algorithm's hours only count a tenth as much as those of third parties. – John Meacham Jan 1 '15 at 3:05
• @JohnMeacham that would be too subjective, who qualifies to be schneier ? how would you experimentally verify such units ? – sashank Jan 2 '15 at 4:42

Usually cryptographic strength is given as the effective strength in bits of a security primitive. This is related to the amount of tries necessary to break a primitive. So for AES-128 the effective strength is about 126 bits. The number of bits is of course directly related to the number of tries required to perform an attack. This is often given as a power of two as well (e.g. $2^{126}$ for above). This of course directly relates to the number of bits. The time it costs for a single try of course depends on the runtime and is usually not considered significant.

For attacks it is often necessary as well to keep some kind of state. In that case the memory requirements are described as well. Often the memory requirements are particular to a specific primitive (e.g. the amount of encrypted blocks to store in memory), but usually those are easily converted to bits or bytes.

If the strength is related to an algorithm then of course the order $\mathcal{O}$ is most often used. If an attack has a specific order $\mathcal{O}$ then filling in the parameters of the function should return an approximation of the amount of tries.

Background

Cryptographic strength can be tricky to calculate and is highly dependent on the known attacks. It very much depends on the use of the primitive within a protocol or setting if attacks are applicable at all. Because of this the cryptographic strength shown is just the cryptographic strength of the primitive within its mathematical context. So that would be 128 bit effective for AES-128 and SHA-256 (because of the birthday paradox).

Even then it may be hard to clearly identify cryptographic strength. For instance for DH there is no clearly defined key size. Both the size of the modulus as well as the size of the subgroup should be taken into account. Key size and cryptographic strength do not have to be directly related (and key size may not be that well defined in the first place).

To get a clear idea about cryptographic strength there are organizations such as NIST and ECRYPT (II) take a look at keylength.com and the documents linked from that site.

• OK, that's it for layman's terms (I hope) I'll leave it to the more mathematically inclined to write a more formal answer :) – Maarten Bodewes Dec 30 '14 at 16:04
• Depends on threat model, the effective strength for AES-128 of 126 bits is only true if an attacker can supply 2^88 data. Which isn't feasible, and in any case, you should rekey before 2^64 encryptions, which is when 128-bit block ciphers start to deteriorate in security. – user3201068 Dec 31 '14 at 21:54
• @user3201068 Yeah, that's the problem with defining a single "strength" value parameter to what is essentially a complex set of problems. Anyway, what's more likely, a requiring a huge amount of memory or 4 times infinity tries... Both are completely off the charts anyway. Won't change the answer, the memory requirement was already in but if you have a good & easy to understand wording for it, go right ahead. – Maarten Bodewes Jan 1 '15 at 17:38