7
$\begingroup$

I hope this doesn't look like a silly question. In an age where our current cryptography is often impossible to crack when properly implemented and used, would we be able to decipher anything, for example if WWIII were to break out ? Similarly to how the Germans added some rotors to Enigma, what could be done against 500-rounds AES if classic AES were to be broken ? Iirc, quantum computers can trivially break RSA, but I don't know about AES. Also, while talking about quantum things, I think I heard about a paper related to the teleportation of some bits between 2 processors. This would mean that in the future, even intercepting the messages would be impossible.

In ~1900, the physicists thought that, minus one small problem, they were almost done with describing physics. Is it possible than in the future, cryptanalysis would also reach a state of near-completion ?

$\endgroup$
3

3 Answers 3

7
$\begingroup$

Will cryptanalysis always stay a relevant topic?

In the modern cryptologic sense cryptanalysis is the science of breaking concrete constructions. This will stay relevant for as long as we rely on constructions which only satisfy security notions heuristically. We can't come up with a general construction that is a Pseudo-Random Permutation for all input lengths, because that would imply $P\neq NP$. Therefore we need heuristic constructions like AES. Additionally this field will stay relevant for as long as we try to come up with new schemes that are ever faster and smaller for some definitions of fast and small.

Furthermore one could argue that side-channel analysis belongs to the general group of cryptanalysis as well and that will remain relavant for as long as we compute cryptographic algorithms on non-ideal hardware.

One may also argue that all these attacks one hears about against TLS, WPA, or SSH also fall under "cryptanalysis". In a sense I agree: While quite a few of them are implementation errors there are also some that aren't. In fact usually these days these protocols have security proofs in a particular communication and adversary model. The point of the attacks is then to find scenarios that aren't covered by the adversary's possibilities in said model, then find an attack that breaks an intuitive security property and argue why this break is (more or less) relevant. Though it is to be expected that this line of research will eventually exhaust all possible oversights in any given class of models. Of course some people also use protocols without proofs and those will always be the target of cryptanalysts (or proof-focused people) for as long as people do this - which may also yield successful attacks despite unbroken building blocks.

I hope this doesn't look like a silly question. In an age where our current cryptography is often impossible to crack when properly implemented and used, would we be able to decipher anything, for example if WWIII were to break out ?

It is currently believed that things like AES are actually secure. However, many governments have their own encryption algorithms, e.g. for highly-classified data. Most of these algorithm descriptions are classified, so only some of that country's researchers can analyse it and so some weaknesses could have been missed. This is of course less of a problem for countries like the USA but more of a problem for smaller countries with less access to enough people who are really good at this sort of cryptanalysis. A similar argument applies to the mechanisms used to transport / negotiate the keys for these algorithms, though probably less strongly. Because of this, it is not impossible for "hostile" encryption schemes to be broken once a description has been acquired - though it is unlikely as the really hard part about this kind of cryptography is getting it fast and secure as opposed to "merely" secure.

Iirc, quantum computers can trivially break RSA, but I don't know about AES.

Quantum computers can break most currently deployed asymmetric cryptography given a sufficient size. They can also give a substantial speed-up (in theory at least) for breaking symmetric schemes, but it is generally believed that this is "fixed" by doubling the key size from 128 to 256 bit (as quantum algorithms half the bitlength of the search space).

This point actually allows us to come back to the first question: It is currently an active effort to come up with as efficient asymmetric cryptographic algorithms as possible that resist quantum computers. As we don't have unconditionally provable secure constructions against quantum computers, we resort to heuristic methods again, which require analysis to see whether they actually stand up against quantum computers.

Also, while talking about quantum things, I think I heard about a paper related to the teleportation of some bits between 2 processors.

This is more of a question for Quantum Computing SE or Physics SE. If you're still looking for an answer on this site, I'll refer you to poncho's answer.

$\endgroup$
10
  • 3
    $\begingroup$ Actually, whether AES is a "Pseudorandom Permutation" is irrelevant to $P = NP$; AES is a fixed sized function, while the concepts of $P$ and $NP$ deal with functions with arbitrarily large inputs. $\endgroup$
    – poncho
    Commented Oct 5, 2020 at 17:24
  • $\begingroup$ @poncho you're right of course, I fixed that (reversing the logic to "we can't give a general construction therefore we need a heuristic one for which we need cryptanalysis"). $\endgroup$
    – SEJPM
    Commented Oct 5, 2020 at 17:48
  • $\begingroup$ teleportation of quantum states does not exceed lightspeed. $\endgroup$ Commented Oct 6, 2020 at 0:52
  • $\begingroup$ Besides cryptographic primitives, researchers also analyze protocols like SSL/TLS to find weaknesses. Just because a cipher has no practical attacks doesn't mean it is used safely and properly in the real world. $\endgroup$
    – Nayuki
    Commented Oct 6, 2020 at 4:24
  • 3
    $\begingroup$ @Tomeamis It is generally believed that coming up with a resolution to P vs NP is really difficult (though not theoretically impossible). As this has been such a "hard" problem, it means that anything that resolves it apparently is also hard (or otherwise that something would have already resolved it) and therefore it seems that proving such a thing that resolves P vs NP is inherently very difficult. $\endgroup$
    – SEJPM
    Commented Oct 6, 2020 at 9:11
5
$\begingroup$

To talk about an issue you raised that SEJPM didn't cover:

Also, while talking about quantum things, I think I heard about a paper related to the teleportation of some bits between 2 processors. This would mean that in the future, even intercepting the messages would be impossible.

Quantum Teleportation is a real thing; it requires that the two sides share an entangled qubit (which can be arranged before hand), and the sender send two classical bits to the receiver (these classical bits prevent us from using it to send messages FTL). As for security, that's one possible way to perform Quantum Key Distribution, another real thing. However, most current QKD systems sold today do not exchange entangled qubits (and hence can't be used for Quantum Teleportation), instead, they rely on Heisenberg's principle for security; this may change in the future.

$\endgroup$
1
2
$\begingroup$

A point that you don't mention is that extensive cryptanalysis of a problem can allow you to more aggressively tune parameters. A recent paper by Aumasson entitled "Too Much Crypto" argues for reducing the rounds in certain symmetric primitives for various reasons.

One can only do this if cryptanalysis is a relevant topic (the cryptanalysis Aumasson refers to is breaking reduced round variants of ciphers, if I remember correctly). Without extensive study of the limits of reduced-round attacks, one risks reducing the number of rounds "too far".

One runs into a similar situation when setting parameters, even for public-key schemes. LWE-based encryption is in the process of standardizing parameter choices, and these decisions require being able to look at a wide body of cryptanalytic work to be able to properly estimate the bit security of certain parameter choices.

Even partial attacks are still partial attacks, and if you reward partial attacks over some period of time (so people are still motivated to cryptanalyze things), and look back and only see partial attacks, it isn't a "failure" of cryptanalysis. It is still contributing to the mutual understanding of the practical security of constructions.

$\endgroup$

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.