What makes a symmetric encryption algorithm cryptographically secure?

Question

I'm trying to learn a bit more about symmetric encryption and found out that basically every symmetric encryption and decryption is (somehow) in the end based on a simple XOR-Byte-Toggle with using a password and some data.

My Question now is, why do we need to make "secure" encryption and decryption algorithms?

I think of it like this:

When I get data, which I happen to know is AES (or with whatever algorithm) encrypted and I now want to read it. You need a password to decrypt it. The only way I see a "security" problem here is, that someone who receives that data besides you, needs the password to decrypt it (also knowing that the data is AES encrypted).

The way he now tries to decrypt the data is: Dictionary-Attacks,... (going all the way up to Bruteforce).

But a computer cannot really define the data to be correctly decrypted as long as the data has no standard header or something how you can identify the correct decryption of it (think of a simple Text-File for example). With all that in mind, I'm struggling to understand why we not only use a simple XOR-Encryption as it is simple, most likely the fastest way on en- and decrypting files and easy to implement in basically every programming language.

The more or less key-question here is, what exactly means that an en- and decryption-algorithm is cryptographically secure?

Answer 1

When you design an encryption algorithm, you generally want it to be secure in as many use cases as possible. This would allow you to reuse the same algorithm everywhere, saving a lot of resources and permitting things like hardware acceleration for the industry standard algorithms (like for AES).

When you want to design an algorithm for as many use cases as possible, you have to defend against a wide variety of attacks, many of which would never even cross the mind of a non-cryptographer. Take, for example, the known plaintext attack model. To a cryptography newbie, it sounds counter-intuitive to defend against a known plaintext model. If the adversary already knows the plaintext, what exactly is there left to protect?

Well, it turns out that in the real world, a lot of the encrypted stuff is actually just known plaintext. Consider what happens when you visit https://security.stackexchange.com. The server and your browser negotiate a symmetric key, and then the server uses that key to encrypt the html for the homepage and sends it to you. Except, the homepage is entirely known plaintext! Anybody can browse to the security.stackexchange.com and receive the plaintext for the homepage. If your algorithm is not known-plaintext attack resistant, an attacker could employ some form of cryptanalysis to derive the symmetric encryption key that the server and your browser negotiated. Now, when you proceed to log in to your account, the attacker can decrypt the credentials you use to sign in, because they already have the encryption key you are using to communicate with the server. Similarly, most file formats have some sort of header which can be easily guessed, and so are also susceptible to known plaintext attacks.

And cryptanalysis is not limited to known-plaintext attacks, you also have chosen plaintext attacks, chosen ciphertext attacks, padding oracle attacks, related key attacks, frequency analysis attacks and many many more. At this point, only a person who has devoted a significant amount of time to studying cryptography and cryptanalysis would be able to design an algorithm that can protect against all of these. Which is why security folks always repeat the mantra:

Do not roll your own

So to answer your key question:

An algorithm is considered cryptographically secure if it is resistant to all known attacks. As soon as someone figures out a new way to break the security of the encryption (i.e. allow decryption of some data encrypted by the algorithm that they should not have been able to decrypt), it will cease to be considered cryptographically secure. This effectively means the term cryptographically secure doesn't have a constant definition. What is considered cryptographically secure today, might not be secure twenty years later.

Answer 2

You are correct that most stream ciphers (and many block ciphers in stream modes) generate a keystream and then XOR the data with it. For security, there is usually some sort of message authentication code applied, either as part of an AEAD or externally. There are certainly many other approaches involved, but those are very common.

For most asymmetric algorithms, the typical thing that makes them secure is some sort of hard problem, typically one in NP. For example, RSA is based on the difficulty of factoring large integers, and Diffie-Hellman is based on the difficulty of computing discrete logarithms.

Sometimes these algorithms have a "trapdoor" of sorts, where a person who knows a secret (the person with the private key) can compute a value efficiently, but for everyone else the problem is computationally infeasible. Common examples of this approach include most knapsack problems.

In many cases, we cannot prove that the problem is actually hard, we just conjecture that it is. For example, the actual hard problem in Diffie-Hellman is one of the variants of what is called the Diffie-Hellman problem. We conjecture that there is no easier way to solve the Diffie-Hellman problem than to solve the Discrete Logarithm Problem, but nobody has proven this for certain. However, nobody has shown a counterexample, either, so we continue to use these algorithms and believe them to be secure.

Answer 3

I'm trying to learn a bit more about symmetric encryption and found out that basically every symmetric encryption and decryption is (somehow) in the end based on a simple XOR-Byte-Toggle with using a password and some data.

This is wrong. Let's begin some formal definitions;

A block cipher is a family of permutations where each key is expected to select a unique premutation from the family. And we want the block cipher to be Pseudo-Random permutation (PRP).

Block ciphers are primitives and need a proper mode of operation for the target system. We have tons of mode of operations for block ciphers on which CTR and OFB are common modes to turn any block cipher into a stream cipher. When we define the mode of operation we can talk about

• KPA: Known Plaintext Attack
• CPA: Chosen Plaintext Attack
• CCA: Chosen Ciphertext Attack and its variants as CCA1,CCA2,CCA3,
• and some other more...

We expect a mode that has at least Ind-CPA secure ( Ind -> Indistinguishable) where ECB fails and CTR and CBC can have Ind-CPA security.

• The CTR mode actually doesn't need the inverse permutation (i.e. the decryption of the block cipher) so we can use any Pseudo-Random Function (PRF) as a wide range set of functions with better security margins. The CTR mode was originally designed for PRFs.

• The CBC mode was very common, see pre TLS 1.3. CBC mode had the padding oracle attacks that are finally removed from TLS 1.3.

• Authenticated mode of operation: In TLS 1.3 we have only authenticated modes AES-GCM, AES-CCM, and ChaCha20-Poly1305 where each of them internally uses CTR mode (ChaCha is built-in CTR mode ) and they have also authentication with the GCM and Poly1305. There is no padding in CTR mode to be attacked.

My Question now is, why do we need to make "secure" encryption and decryption algorithms?

Of course, we need. We want to secure our information. For example; If if you insist on using DES with a single key there can be entities that can break your encryption in a day!. The current secure key size is at least 112 according to NIST.

Use AES with a 256-bit key to be secure against even the possible Cryptographic Quantum Computers (QCQ). You can also use ChaCha20 with a 256-bit key ( or better use XChaCha20 with 192-bit random nonces to mitigate a possible (IV,key) pair reuse problem ).

When I get data, which I happen to know is AES (or with whatever algorithm) encrypted and I now want to read it. You need a password to decrypt it. The only way I see a "security" problem here is, that someone who receives that data besides you, needs the password to decrypt it (also knowing that the data is AES encrypted).

The way he now tries to decrypt the data is: Dictionary-Attacks,... (going all the way up to Bruteforce).

Yes, since AES is secure against key searches ( even AES-128 has), the plausible attack is your password. If you use a bad password then the attacker brute-for them starting from the known over 613M pawned passwords. They may try to rainbow tables, too, for all possible combinations like 8 characters.

To mitigate password search attacks you need

• to use a good password with a good strength like generated from dice-wire, minimum 128-bit strength is recommended.
• to use a good Password-Based Key Derivation Function like the latest contest winner Argon2. With the correct parameters, you can reduce the attacker's capabilities. A high number of iterations, memory-hardness, and increased threads are the key to achieving this what Argon2 provides all. Massive GPU, ASIC, and CPU attacks are reduced.

But a computer cannot really define the data to be correctly decrypted as long as the data has no standard header or something how you can identify the correct decryption of it (think of a simple Text-File for example).

This really depends on the encryption scheme that is used. For example

• CBC mode has PKCS#7 padding that can be tested during the brute-force as the DES challenger did.

• In GCM and ChaCha the authentication tag can be tested to be correct or not.

  Note that there are deep details in each like the probability of the padding to be a false-positive and similarly for the GCM and ChaCha. This is not considered here.

If the file is a text file then one can look for the possible strings, too. The more close to natural language the higher candidate to be the true key. All of this can be automated.

With all that in mind, I'm struggling to understand why we not only use a simple XOR-Encryption as it is simple, most likely the fastest way on en- and decrypting files and easy to implement in basically every programming language.

It seems that you are talking about One Time Pad (OTP) encryption. The simple reason is this; to be unconditionally secure ( or call it perfect secrecy or information-theoretically secure) the key size must be equal to the message size. We know this since 1949 by Claude Shannon. This is impractical for today's most systems.

Today we relaxed this condition to be computationally secure against polynomially bounded adversaries. We construct a block cipher or stream cipher that resists known attacks. Then with a stream cipher, we can directly encrypt the messages with x-or. For block ciphers, we need a mode of operation and as mentioned above we select a proper mode of operation for our needs. Different application has different risks and needs a different mode of operations like today we use XTS/XTX mode of operations for disk encryptions instead of CTR mode that was used before and had some attack points.

OTP seems to be easy to implement, however, the key generation and distribution was the common problem. Remember the reuse can cause a crib-Draggin attack and this happened in history,

The more or less key-question here is, what exactly means that an en- and decryption-algorithm is cryptographically secure?

What makes a symmetric encryption algorithm cryptographically secure?

The simple answer is years of research and cryptanalysis during the design.

• Block ciphers need

  • good diffusion and confusion properties

  • Resistance to all known attacks like

    • differential attack and it's variants;
      • truncated differential attack
      • partial differential attack
      • boomerang attack
      • impossible differential cryptanalysis
    • Linear attacks.
    • Integral cryptanalysis
    • Slide attacks,
    • Algebraic attacks, XL, XLS.

  • needs to be indistinguishable from a random permutation.

  • enough round with a good round function.

    as a necessary condition.

  A good block cipher like AES has resisted attacks for more than 20 years. Even a QCQ is built we expect that AES-256 will be secure in the near future and in the industry is called the golden standard. Use AES-256 instead of AES-128 and you will get at most %40 performance penalty.

• Stream ciphers

  • requires a large period
  • No related key attack
  • and Pseudo-Random Sequence are necessary conditions.

And remember

There is an old saying inside the US National Security Agency (NSA): Attacks always get better; they never get worse.**

Therefore prepare for all possible attack scenarios even failure of the RSA/ECC to CQC and use post-quantum public-key cryptosystem