1
$\begingroup$

Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?

Why aren't many popular algorithms like AES like this?

$\endgroup$
4
  • $\begingroup$ @kelalaka Sure, thanks. Although isn't CBC actually IND-CPA insecure (quick google search seems to confirm it) and many applications using it can actually tell you whether your key was wrong or not just by giving it the key, instead of just giving you a wrong answer? $\endgroup$
    – Hormoz
    Aug 16 '20 at 1:32
  • $\begingroup$ Yes, and I said CBC and CTR can achieve this. Are you talking about authentication? CBC doesn't provide authentication. One needs to use HMACA or similar keyed MACs or use AEAD in a combined mode. $\endgroup$
    – kelalaka
    Aug 16 '20 at 7:22
  • $\begingroup$ Kinda authentication, but not exactly authentication, just the fact that you can tell your key was wrong from the output of the algorithm (which also can act as a theoretical security flaw, because you can easily tell if the key used was wrong or not), but it seems you are talking about the same thing. $\endgroup$
    – Hormoz
    Aug 16 '20 at 16:20
  • $\begingroup$ That is integrity and MAC are used for these. AEAD can provide confidentiality, integrity, and authentication altogether. $\endgroup$
    – kelalaka
    Aug 16 '20 at 17:07
4
$\begingroup$

Why don't most encryption algorithms use perfect secrecy?

Perfect secrecy can only achievable if the $\text{key size} \geq \text{message size}$ and the key is never re-used.

It is not suitable for modern usage, where a lot of messages are sent/received and that is impractical since one has to send the key beforehand in a secure channel and this is not encryption. You must trust the carrier or you have to carry the keys yourself. Instead, we go the other way, use shorter keys with good analyzes algorithms. Exchange the key with DHKE protocol ( where mostly elliptic curve version is used), and use AES-GCM, AES-GCM-SIV, or ChaCha20-Poly1305.

Reuse of the key has catastrophic results that confidentiality is broken. What will you do when the keystream is depleted? Would you wait for the new key, or you would re-use some part of the keystream? Both have critical results. You will not communicate when needed or OTP will fail, see Crib-Dragging. Instead, one can use DHKE to create a new key, even for every encryption, and even can achieve forward secrecy.

Isn't it possible to make algorithms that are both computationally complex and have many possible answers if you try to crack them without knowing the password?

The encryption should be easily computed so that the legal party doesn't use so much power to encrypt. This doesn't mean that it is breakable since the adversary can compute with lots of resources. If the algorithm, block or stream cipher, use correctly given key then, then one can adjust the key size so that brute force out of reach of anybody, even for the quantum computers.

The encryption can be randomized and indeed in modern cryptography, we prefer this, forget the otherwise, it is insecure. See semantic security and indistinguishability. For example, we prefer at least Ind-CPA security. CBC and CTR mode can achieve this, however, ECB cannot. Actually we want more, the standard of IND-CCA2/NM-CCA2- ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack. The examples are AES-GCM, AES-CCM, and ChaCha20 which are an Authenticated Encryption with Associated Data (AEAD) and provides Confidentiality, Integrity and Authentication.

The decryption must be unique since there is no way for the receiver to determine the correct message among the possible answers.

The password is not the correct term. We use the encryption key or in a short key when it is clear in the context. The password is only applicable if the key is generated by using a Password Based Key Derivation Function like PBKDF2 or Argon2id.

Why aren't many popular algorithms like AES like this?

Mostly answered, AES is a fast and secure keyed permutation. Yes, for each key, AES chooses a permutation from all possible permutations. We expect that it chooses this in a way that its selection is indistinguishable.


There are also Q/A and answer here that talks about achieving perfect secrecy with AES with some very nice answers;

$\endgroup$
0

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.