1
$\begingroup$

Recently, I read here on Crypto SE that $2^{60}$ doesn't provide enough resistance to current adversaries. Could someone please provide me with good references related to that threshold, or any updated versions of it, say, $2^{70}$ or $2^{80}$?

I made an effort to find the exact discussion, but, unfortunately, I was unable to locate it.

$\endgroup$
3
  • $\begingroup$ Does your browser save history for the last 6 months? Maybe try filter out all entries with "crypto.stackexchange.com" domain. $\endgroup$
    – DannyNiu
    Aug 15, 2023 at 2:16
  • 1
    $\begingroup$ This shows that by 1977, $2^{56}$ was already considered breakable if necessary. $\endgroup$
    – fgrieu
    Aug 15, 2023 at 6:29
  • 1
    $\begingroup$ SHAttered immediately comes to mind. There's also the Chosen-Prefix Collisions paper. Then Too Much Crypto mentions Bitcoin computations. $2^{80}$ is considered secure enough for committing security, which is based on collision resistance. $\endgroup$ Aug 16, 2023 at 19:54

4 Answers 4

4
$\begingroup$

We're generally aiming for a cryptographic strength of $2^{128}$ (i.e. close to $2^{128}$ operations are required to break a scheme). This is also called a cryptographic or security strength of 128 bits. An operation is anything that can be used to test a key value or possible break. Lower than that is possible for specific instances (real time cryptography) but 128 bits of security are generally considered safe.

For which key sizes or hash functions should be used to obtain this kind of security please have a look at https://keylength.com, e.g. going into the NIST recommendations. Beware though that this only shows secure key or output sizes. It is much more likely that protocol or implementation errors will result in security issues than a smaller key size.


Normally when we show these kind of values we only consider classical computers, possibly run in parallel of course. Against full fledged quantum computers we can have a similar security value, so $2^{128}$ operations running on a quantum computer. Beware though that this is probably a lot harder to do, which is why cryptographers may still consider AES-128 secure even though it may "only" require $2^{64}$ operations of a quantum computer to break it.

A full fledged quantum computer will however make many common asymmetric primitives such as RSA, (EC)DH and ECDSA insecure. You could take a look at Post Quantum Cryptography to choose a Quantum-Secure Cryptographic algorithm.


$2^{60}$ operations has never been considered secure against all adversaries. $2^{80}$ is about the strength of SHA-1 and 2-key (128 bit key of which 112 bits are used) triple DES. That has been seen as secure in a legacy sense for a while by NIST, but it isn't considered secure anymore. The very bare minimum that should be used is 112 bit strength which for instance is offered by three key triple DES and 2048 bit RSA or DSA, but 128 bit security should always be preferred.

The SHAttered attack that broke SHA-1 collision resistance took $\sim2^{63}$ operations. Single DES with 56 bits has been broken for considerably longer (and took only 16 times less effort than 60 bit security would require). 60 bits just doesn't do at all.

$\endgroup$
2
  • $\begingroup$ Here is a German government resource which is in line with your answer (included since it is--at least to me--less familiar than the NIST) but has quite a lot of discussion. bsi.bund.de/SharedDocs/Downloads/EN/BSI/Publications/… $\endgroup$
    – kodlu
    Jul 25, 2023 at 17:21
  • 2
    $\begingroup$ I'm more familiar to it due to previous work and I think that in general the BSI has high quality documents and tests. They maybe somewhat less accessible to the general public, but yes, definitely leading as a national institute within the EU. $\endgroup$
    – Maarten Bodewes
    Jul 25, 2023 at 17:24
3
$\begingroup$

On a practical note, a single consumer GPU (RTX4090) is capable of computing 164.1 GHashes/s of MD5. Note these are full MD5 computations, which of course are comprised of much more than a single operation. An hypothetical attack requiring $2^{60}$ MD5 computations would take approximately 81 days, that is, less than 3 months. On a single consumer-grade device.

As a proxy for the computational capabilities of a large government, consider the hash rate of the Bitcoin network. It hit a peak of 465 exahashes/s in July 2023. That's almost $2^{69}$ hashes/s.

$\endgroup$
1
  • 2
    $\begingroup$ What counts as a Bitcoin hash is two SHA-256, thus we have wasted over $2^{69}$ SHA-256/s on average in the first 7 months of 2023. $\endgroup$
    – fgrieu
    Aug 16, 2023 at 17:32
2
$\begingroup$

A multivariate-quadratic signature scheme (Rainbow) was broken last year in a way that got a lot of attention. This occurred in the paper "Breaking Rainbow takes a Weekend on a Laptop".

The estimated cost of this attack (namely the "simple attack", on the Second-Round security level 1 parameters) was $2^{61}$ operations. As advertised in the paper title, this is doable on commodity hardware ("a laptop") in a relatively short timeperiod (53 hours, or "a weekend"). So this is pretty direct evidence for why $2^{60}$ operations to break a scheme is too low --- someone can execute this attack in a short timeperiod with cheap machines.

$\endgroup$
-3
$\begingroup$

For AES-256, a 40-character password randomly selected from 94 keyboard characters delivers 40^94=8.416x10^78 possible combinations. Compare that to 2^256=1.158x10^77.

A variety of tests and measures determined that a specific CSPRNG delivers 98.896% randomness, resulting in an effective 8.823x10^78 unique combinations, 71.88 times more than 2^256.

Put simply, the generator fully fills AES-256's keyspace.

Using VeraCrypt with AES-256 and SHA-512/256 with a highly random, 40-character keyboard password fills the AES-256 keyspace and is both extremely fast and extremely secure.

$\endgroup$
1
  • 4
    $\begingroup$ This does not answer the question. $\endgroup$
    – DannyNiu
    Aug 15, 2023 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.