5
$\begingroup$

I think we are all aware of the CAESAR-competition. Now the aim of this competition is to select a (portfolio of) winner(s) which provide authenticated encryption.
I'll now assume that the results produced by this competition are very good, meaning the cryptanalysis of the next 50+ (!) years won't yield any significant attacks (speed-up no more than $2^{80}$ compared to brute-force). Further it may be assumed that the scheme has 512-bit keys, to reach 256-bit security against quantum-computers.

So far for the assumptions, now to the background:
I recentely read this text by B. Schneier, where it was stated that the laws of thermodynamics disallow a counter to count to more than $2^{200}$, even in an ideal setting (3.2K, dyson sphere, kT for bit-flip,...). So I asked myself the following question as 512-bit seem to fully suffice forever (if we don't harvest the whole universe's energy...)

Now my question:
Besides performance and flexibility, will there ever be the need for 1024-bit symmetric encryption?

Improve this question
$\endgroup$
8
  • $\begingroup$ What do you mean with "besides performance and flexibility"? Do mean that a symmetric cipher with a 1024 bit symmetric key would be flexible and fast? Because it definitely wouldn't. If you agree with that then you may have to rewrite the last sentence. $\endgroup$
    – Maarten Bodewes ♦
    Jul 7, 2015 at 18:38
  • $\begingroup$ @MaartenBodewes, Threefish-1024 isn't all that slow and with more modern processors, we'll probably get 1024-bit AVX instructions (like we'll getting AVX-512 soon^(tm) ) which may bring significant speed advantages over "older 512-bit ciphers". Concerning flexibility: It may be that a potential sucessor features "new useful features" like enhanced intermediate tagging or similar stuff that nobody thought of yet. $\endgroup$
    – SEJPM
    Jul 7, 2015 at 18:42
  • $\begingroup$ Threefish was slow when I implemented it, but it wasn't called "Skein from spec" for nothing, and Java is relatively slow compared to AVX / native implementations of course :) But you make interesting points and it is now clear that you did mean what was written down. Thanks for the clarification. $\endgroup$
    – Maarten Bodewes ♦
    Jul 7, 2015 at 18:53
  • $\begingroup$ Is there something to this that isn't covered here: crypto.stackexchange.com/a/1148/13625 $\endgroup$
    – otus
    Jul 7, 2015 at 18:58
  • $\begingroup$ @MaartenBodewes ... if we want to allow abusage of the said scheme for hashing, we'd need 1024 bits for 256-bit collision resistance against quantum-computers, meaning the question isn't clear enough wether such applications should be taken into account... But in the way it's currently formulated we'll indeed need 1024-bit ciphers (for Skein-like hashes). But I guess at leat we won't need 2048-bit symmetric crypto... $\endgroup$
    – SEJPM
    Jul 7, 2015 at 19:24

1 Answer 1

Reset to default
8
$\begingroup$

In order to answer this question, we need to understand the basis behind all of modern cryptography, which is computational hardness. Today, we believe that we know how to construct block ciphers that are secure, except for brute force search (or almost that secure). However, we don't really know this. We also think that factoring is hard, and so on. All of these are just assumptions since we don't know how to prove significant algorithmic lower bounds for problems like this. In particular, we don't even know how to prove that $P \neq NP$, and if $P=NP$ then no block cipher will be secure. Note, by the way, that even if $P\neq NP$, this doesn't suffice for crypto (we need one-way functions, which as an assumption is equivalent to pseudorandom functions/permutations).

Coming back to your question: assume that in 100 years it has been proven that $P\neq NP$ and even that one-way functions exist. However, assume also that all problems in $NP$ can be solved in time $2^{\sqrt n}$ where $n$ is the input length. (Note that it is strongly conjectured that $NP$-hard problems cannot be solved in sub-exponential time, but this is also an assumption.) In this case, if we want security against machines running in time $2^{128}$ then we will need keys of size 16384. Another more likely possibility (but who knows) is that all $NP$ is solvable in time $2^{n/10}$. This would require keys of size $1280$.

Is this a likely event? Do I believe that this is the case? No, I don't! But, if you are asking: will such key lengths ever be needed? Well, no one really knows and the future will tell.

Currently we set key lengths by what we know. RSA needs 2048 bit keys due to the best factoring algorithms, and likewise discrete log and DDH over $\mathbb{Z}_p^*$; ECC needs 256-bit keys since the best algorithms known take time that is a square-root of the group size; symmetric keys need to be 128 bits since the best known attacks are brute force (and when better attacks are known then we phase out the algorithm).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ For such run-times to happen we'd have to develop new techniques of computing beyond quantum computing (at max $\mathcal O(\sqrt{n})$) and classical computing (at max $\mathcal O(n})$). Of course such developements aren't impossible but very unlikely... $\endgroup$
    – SEJPM
    Jul 8, 2015 at 21:06
  • 1
    $\begingroup$ Indeed, I don't believe that any of the above will happen and fully agree with you. However, my point was that the question of if "we'll ever need larger key sizes" is something that depends on open questions that we are currently far from being able to answer. $\endgroup$
    – Yehuda Lindell
    Jul 8, 2015 at 21:08

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.