1
$\begingroup$

I know this question might sound strange, but is it theoretically possible to create an unbreakable cipher if we don't consider bruteforce? Some of us believe that it is possible to create ciphers and hash algorithms that are unbreakable (like when people said that we'd never run into an MD5 collision in the lifetime of the universe), but get broken in a couple of decades time (MD5 collision can be created on a modern PC in minutes). Others (including me) think that it's impossible. I believe that it is near impossible to create an unbreakable cipher, but I don't quite understand why.

Sure, computing power increases, and transistors double in count every year, but is a cipher really just a bodyguard that has a limited lifespan and dies when computing power increases? With quantum computing (I'll refer to it as QC) rapidly growing, many algorithms such as RSA and AES are becoming vulnerable.

I know, AES256 is safe against QC for now, but in the long run, it'll only get weaker and weaker until it is broken. But why (don't consider bruteforce because hashes take care of that)?

The logic behind cryptography is math, and math is getting more complex (Calculus, modern math, etc). When DES was created, there was no Shor's algorithm or Grover's. As time went on, math advanced, as did technology, and thus Shor's and Grover's algorithms are created. These discoveries weaken ciphers like AES by not a lot, but when they pile up as time goes on, it greatly weakens them.

Is it just impossible to create a cryptographically secure cipher that is strongly rooted in math and designed so that no advance in QC/math will weaken it? If we gathered the world's best cryptographers, gave them telepath (just for example), and gave them 1 billion dollars to create a cipher, would it always be able to be cracked?

I read this SE question and quickly came to the conclusion that it's a scam and just for views, but I'm sure many people believe it. I would like to know if ciphers can be unbreakable and if they can't be unbreakable, why they can't.

$\endgroup$
6
  • $\begingroup$ What exactly do you mean by unbreakable? Do you mean that there is no algorithm that reduces the brute-forcing of the whole key space to the small set that is brute-forcible in the acceptable time? $\endgroup$ – mentallurg Jan 4 at 3:34
  • $\begingroup$ By unbreakable, I mean a cipher that can't be cryptanalyzed and can't be cracked itself. Example: Birthday attacks, oracle attacks, any attacks that weaken and eventually break a cipher, not considering bruteforce. $\endgroup$ – HACKERALERT Jan 4 at 3:35
  • $\begingroup$ You mean like, one-time pads? $\endgroup$ – forest Jan 4 at 3:40
  • $\begingroup$ Kind of. Like, is it theoretically possible to create an unbreakable AES? $\endgroup$ – HACKERALERT Jan 4 at 3:42
  • 2
    $\begingroup$ @HACKERALERT You might want to look into the ideal cipher model. Perhaps your question is whether or not it is possible to make an actual ideal cipher for which the best attack is brute force (i.e. no cryptanalytic shortcuts exist). The answer is that we simply don't know. $\endgroup$ – forest Jan 4 at 3:43
4
$\begingroup$

Some of us believe that it is possible to create ciphers and hash algorithms that are unbreakable (like when people said that we'd never run into an MD5 collision in the lifetime of the universe), but get broken in a couple of decades time (MD5 collision can be created on a modern PC in minutes).

MD5 or any other hash function is not proven to be secure. MD5 has already 128-bit output that has 64-bit collision security bound that was low even 2000s. As "Attacks always get better; they never get worse" and we expect new attacks as time goes. Despite this, consider AES-128 still secure after 20 years. The only practical attack is the multi-target attacks that are applicable to all block-cipher. The easy mitigate is to use 256-bit key that is already the golden industry standard.

Sure, computing power increases and transistors double in count every year, but is a cipher really just a bodyguard that has a limited lifespan and dies when computing power increases? With quantum computing (I'll refer to it as QC) rapidly growing, many algorithms such as RSA and AES are becoming vulnerable.

Classical computer power is limited, there is no way for classical computers to break 256-bit block cipher just by brute-force. Even for AES-128, the collective powers of Bitcoin miners need around $2^{34}$ years to brute force 128-bit AES. As said before for 128-bit the multi-target attack is the real attack and not for 256-bit.

Shor's algorithm can break the RSA and some ECC. There is a secure ECC system like the Isogeny to be considered secure against QC.

I know, AES256 is safe against QC for now, but in the long run, it'll only get weaker and weaker until it is broken. But why (don't consider bruteforce because hashes take care of that)?

In the case of Block ciphers, the Grover can provide at most quadratic speed up and this is proven to be the lower bound. Therefore 256-bit block cipher is safe against Grover's algorithm.

Unless there is a new breakthrough result in QC, we can create a cipher safe against them. See NIST competition on post-quantum cryptography and target security level, or see the Ella Rose's answer on QC

The logic behind cryptography is math, and math is getting more complex (Calculus, modern math, etc). When DES was created, there was no Shor's algorithm or Grover's. As time went on, math advanced, as did technology, and thus Shor's and Grover's algorithms are created. These discoveries weaken ciphers like AES by not a lot, but when they pile up as time goes on, it greatly weakens them.

Is it just impossible to create a cryptographically secure cipher that is strongly rooted in math and designed so that no advance in QC/math will weaken it? If we gathered the world's best cryptographers, gave them telepath (just for example), and gave them 1 billion dollars to create a cipher, would it always be able to be cracked?

It is well-known that the One-Time Pad has information-theoretic security so that no one can break the cipher as long as it used correctly. The key needs to be generated uniformly randomly, the key size must be at least the message size, and the key never to be used again. Then you have the

  • key distribution problem that you need to solve if you want to communicate. That is a huge problem in the modern world.
  • key storage problem if you need to encrypt your files. It is the chicken-egg problem.

Therefore, the cryptographers for a long time concluded that instead of the informationally secure cipher, we should use a computationally secure cipher that is achievable with shorter keys. The cryptography is mature enough that we can calculate the security of a system in the foreseeable future. See keylength.com for such predictions.

On the plus side, we can use a key more than once with the help of nonce/IVs.

In today's Cryptography, the usual problem is not the cipher but the human factor;

Others (including me) think that it's impossible. I believe that it is near impossible to create an unbreakable cipher, but I don't quite understand why.

Unbreakable == no limit on the attacker's power then you turn back to Information Theoretically secure cipher as OTP and you will be fine!

Take AES, except for the side-channel attacks, it is secure. It is considered as PRP but no one has shown that is the case or not.

We consider the security against the attack model. If you say you have the unbreakable cipher then I can say my attack model is xkcd-538

enter image description here

Or should we say once you connect your PC to the internet is it no longer secure?

A nice read of Mitnick's book The Art of Deception: Controlling the Human Element of Security

I read this SE question and quickly came to the conclusion that it's a scam and just for views, but I'm sure many people believe it. I would like to know if ciphers can be unbreakable and if they can't be unbreakable, why they can't.

Prof. Lindell is already debunked that there. If people want to believe then we cannot do anything at all for them.

Sure, there will attack the ciphers that are faster than the brute-force and we act according to it. AES-256 has attacks faster than 256-bit key search, however, these attacks are not practical.

We cannot prove that a cipher is unbreakable since we don't know all possible attacks. The Ideal-Cipher-Model is theoretic and one can create hash algorithms from an ideal-Cipher to be known secure but when instantiated they can be broken.

Theoretically, we can build an ideal cipher; for example, consider a 128-bit key and 128 bits block size. For each key, there are $2^n!$ possible permutation to select randomly and we need to select $2^{128}$ among them uniform randomly. We can represent each permutation with a table of $2^{128}$ rows and each row contains 128-bits of information. Therefore we need to store $2^{272}$ bits and if we generate each bit with random then this is not practical to generate and store. In the realization, this is neither practical in space, and there is the difficulty of secrecy and uniformity of the physical randomness. In contrast, modern cryptography easier to understand which helps to easy to analyze and control the security.

In short; we act on what we understand and analyze and control our assets according to the foreseeable future, not something that we cannot easily understand and analyze.

$\endgroup$
1
  • $\begingroup$ Very detailed and useful answer. You've helped me look from different perspectives and now I understand. $\endgroup$ – HACKERALERT Jan 4 at 14:16
1
$\begingroup$

Back to 1949, Claude Shannon in Communication Theory of Secrecy Systems proved that perfect security (cipher that is perfectly secure and unbreakable) can be obtained only in information-theoretic model with the One Time Pad and only when the amount/size of your key is longer or equal to the amount/size of your plaintext, so impractical, and so welcome to complexity-based cryptography!

In complexity-based cryptography, unlike information-theoretic cryptography, you can't design a cipher that is completely immune to the exhaustive key search and brute-force attacks. but you can make it hard and practically impossible for the attacker to break your cipher. This is what a practical cipher like AES does.

As @forest mentioned: there is an ideal model. Ideal block cipher model is a heuristic way for modeling block ciphers and a good model for designing hash functions, that similar to the OTP isn't practical.

$\endgroup$
1
  • $\begingroup$ Are OTPs just Vigenere ciphers using PRNG's as keys? Since PRNG's are used, OTPs are therefore not vulnerable to frequency analysis? $\endgroup$ – HACKERALERT Jan 4 at 14:21
1
$\begingroup$

Yes, you mean encryption methods with perfect secrecy

Perfect Secrecy (or information-theoretic security) means that the ciphertext conveys no information about the content of the plaintext. In effect, this means that, no matter how many ciphertexts you have, it does not convey anything about what the plaintext and key were. It can be proved that any such scheme must use at least as much key material as there is plaintext to encrypt. In terms of probabilities, it means that the probability distribution of the possible plaintexts is independent of the ciphertext.

And one of the famous encryption methods with perfect secrecy and can be performed with normal computers is One time pad.

One time pad creates a random key same length as the plaintext message and XOR these two together.

$\endgroup$
1
$\begingroup$

We do not know if there are one way functions. This is related to the P=?NP question you may have heard of. If P=NP we can not have cryptography as we know it as if you can decode something with a key in Polynomial time you will also be able you to decode it without the key in polynomial time provided you can verify correct results. It is also possible that P does not equal NP but still one way functions don't exist. These are open questions.

We still have perfect security as in a one time pad where, no amount of computing resources will break the cipher because the information simply isn't there.

If we move away from cryptography and towards physics we theoretically can have true random numbers generated and shared with quantum key exchange this would be unbreakable with any computing power.

$\endgroup$
0
$\begingroup$

Proving that a secure cipher can exist is an open problem (aside from one-time pads, mentioned in other answers, which are not very practical). But it isn't reasonable to predict that what happened to MD5 and DES will happen to AES.

MD5 was expected to have a limited lifespan. It's been known from the beginning that collisions could be found with roughly 264 hash evaluations, and it's always been widely believed that computers would eventually get fast enough to do that. There are attacks known now that are faster than brute force, but even brute force is feasible on current hardware.

DES was outright designed to have a limited lifespan. After more than 40 years, the only significant known weaknesses of DES are the ones that were designed into it: the block size and the key size. It hasn't been broken, in the sense of a serious unknown weakness being found. It just reached its point of planned obsolescence.

AES was not designed to have a limited lifespan. AES-128 may be vulnerable to quantum computers in the distant future (as was known when it was standardized), but it's entirely plausible that AES-256 will be secure forever.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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