Many designer claimed that their cryptography scheme has 80-bit security. So how to calculate the time of attcking this 80-bit security cryptography scheme, such as 80-bit security RSA using a kind of CPU?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ 80-bit RSA is breakable in a blink, using e.g. GMP-ECM. For info on RSA factorization records, see this. For info on 80-bit security, see this. For choice of key size, see this. $\endgroup$– fgrieu ♦Apr 10, 2020 at 15:35
-
$\begingroup$ Thanks for your answer. Now I take 128-bit security as example. I want to ask that 128-bit security means 2^128 basic operation to attack this scheme. Is this true？ And does the basic operation means general multiplication or addition? And how to calculate the concrete time to attack this scheme? 2^128 multiplies time of doing general multiplication or addition? $\endgroup$– Alex IdealApr 12, 2020 at 13:47
-
2$\begingroup$ ah so your question is: what does $n$-bit security mean. I'm trying to find a Q/A about this. In a nutshell: it means $2^n$ steps are needed to break the system, where "step" is loosely defined. For symmetric crypto, it generally is "as much work as one encryption or hash". For theoretical work on asymmetric crypto, "step" tends to be "one group (or field) operation or one hash". For RSA, that could be 1 modular multiplication mod N (of the public key), or 1 hash. But in practice, $n$-bit security often is used for: as much (computer) work as breaking a symmetric cipher with $n$-bit security. $\endgroup$– fgrieu ♦Apr 12, 2020 at 18:29
-
1$\begingroup$ There was a question about 64-bit insecurity. Supercomputers like Summit can reach $2^{72}$ in a year. However, a dedicated group like Bitcoin miners can reach $2^{92}$ in a year so 80-bit is no more secure. If multi-target attack available even AES-128 is not secure to all targets see here and What is a multi-target attack? and here Has AES-128 been fully broken? $\endgroup$– kelalakaApr 12, 2020 at 18:58
-
$\begingroup$ @fgrieu Thanks for your answer. I also want to know that can 2^{128} be seen as clock cycles? As I see that running time can also be measured by clock cycles. $\endgroup$– Alex IdealApr 13, 2020 at 2:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The question largely boils down to:
What does $n$-bit security means in practice for a given value of $n$?
TL;DR: as secure as a good symmetric cipher with an $n$-bit key.
There's not a single more precise definition, even if we restrict to attackers using classical computers (rather than quantum computers), as this answer does.
One generally accepted meaning is that the number of "steps" to break the system is believed to be $2^n$; or more precisely that the probability to break the system with $s$ "steps" is not known to be more than $s\,2^{-n}$ by any method for any $s$. However "steps" and "break" are not precisely defined.
In theory of symmetric encryption,"step" is typically taken as one execution of the cipher with a new key. This way, an ideal cipher with a key of $n$ bits has $n$-bit security, under brute force key search. When we move to practice, attackers are not bound to brute force key search, and the definition of a "step" has to become a number of sub-steps comparable in number and computational cost to the sub-steps required for one execution of the cipher with a new key for a plaintext the size of the key. With this definition, a practical cipher with a key of $n$ bits has at most $n$-bit security, and aims at that ideal.
When we move to hashes, the definition of a step could become a number of sub-steps comparable in number and computational cost to the sub-steps required for hashing a new message the size of the hash output.
One of many problems with the above is that there is no agreement about if we should count or not the cost of memory and memory accesses in the computational cost. The safe thing from a user's perspective is not to count it, but that can be be of paramount importance for an attacker.
The definition of "steps" becomes even more murky when it comes to asymmetric cryptography like RSA. In theory, "steps" might be one computation in the algebraic structure used for the cryptosystem; like, for RSA, one evaluation of modular multiplication $(a,b)\mapsto a\,b\bmod N$ for arbitrary integer $a$ and $b$ in $[0,N)$, where $N$ is the public modulus. But there are problems moving this to practice, in particular for RSA: the best known attack is to factor the public modulus $N$ using the GNFS algorithm, which computational cost is dominated by operations having little similarity with modular multiplication, and of practical cost dominated by memory and accesses to memory. Which puts use back to the vague definition in the TL;DR.
how to calculate the time of attacking this 80-bit security cryptography scheme, such as 80-bit security RSA using a kind of CPU?
"80-bit security RSA" is not to be understood as RSA with a 80-bit public modulus $N$, which is terminally insecure. If we had the size of $N$, we could estimate the difficulty based on that and previous experience (see this and its links). But we do not, and there is no consensus on the size of $N$ for RSA with 80-bit security: 1024-bit is often cited, but depending on hypothesis, and who you ask, that's grossly too much or too little. Thus the best is to ignore that we are talking about RSA, and get back to: as much time as needed to break a good symmetric cipher with a 80-bit key.
Which brings us to: $$\text{Time}=\frac{2^n\times k\times p}{\text{Frequency}\times\text{Number-of-CPUs}}$$ where $n$ is the security level in bits, $k$ is an estimation of the number of CPU cycles to evaluate a good cipher using an ultra-optimized algorithm, and $p$ is the residual probability of success of an adversary. Depending on perspective we might take $k=1$ (which saves examining the particulars), $k=32$ (because that's still less than in the best attacks against good ciphers using a general-purpose computer), or much more. Depending on perspective, we can take $p=1$ (most prudent from a legitimate user's perspective), $p=1/2$ (yielding the expected time in the case of a block cipher), or a smaller $p$ if we want a security margin¹.
For example, with $n=80$, $k=1$, $p=1/1000\approx2^{-10}$, $\text{Frequency}=4\text{GHz}\approx2^{32}\text{s}^{-1}$, $\text{Number-of-CPUs}=1000\approx2^{10}$, we get $\text{Time}\approx2^{80-10-32-10}\text{s}=2^{28}\text{s}$, that is about 8 years. In other words, our 1000 CPUs have only a very small probability of success against 80-bit symmetric crypto, until they become technically obsolete.
On the other hand, 1000 CPUs is a tiny fraction of worldwide CPUs, and bitcoin mining conclusively shows that 80-bit crypto is no longer enough against adversaries with the capabilities to design ASICs, build them in massive quantities, and sustain the energy costs for their operation; see this.
¹ The $p$ term in the formula is the most prudent from a legitimate user's perspective, but it causes $\text{Time}$ to be underestimated in many attack scenario. For example, in collision search, the correct term would be more like $\sqrt p$.
