Score:2

Is there collision in encryption like in hash functions?

cz flag

In hash functions, $h(m) = h(m_1)$ is called collision and is very undesired that they are feasible to find as it undermines hash security. However, is there essentially analogous concern in encryption like block ciphers (AES-256) or RSA? If there is plaintext key pair $m,k$ that yields some ciphertext, and there exists another key, message pair $m_1, k_1$ that also yields the same ciphertext, is this essentially a similar issue as a hash collision? That is given two pairs you could then make 'cryptanalysis' and breakthrough cipher, 'learning' how two ended as the same ciphertext.

Another thing is whether this can raise issues like the inability to decrypt just as the irreversibility of hash functions as 'there's no way to choose from possible original inputs' (like also in one-time pads).

corsiKa avatar
us flag
I would like to say, good for having the gut feeling that just because something applies to hashing that it applies to encryption and vice versa. Yes they're both complex, and they often use the same or similar algorithms, but they're two different tools for two different problems, and making assumptions about one based on the other is unwise - actually, when security is the concern, you should *always* question your assumptions!
nimrodel avatar
cz flag
i didn't assume that collisions happen in encryption solely or even partially cause it happens in hashing. rather i brought hash just as example 'like in hash'. i was interested whether m1xk1 encrypts to m2xk2 in the first place and whether there's concern about to which to decrypt when there can be several options (just like in hash). so it's u assuming that i assumed.
Score:4
et flag

Collisions happen in Hashing because of the Pigeonhole Principle. In Hashing, the input is bigger in size than the output. Hence collisions will happen, you cannot prevent it.

This is not the case with encryption. The output of Encryption is always atleast same as the size of the input - so the Pigeonhole Principle doesn't apply.

Also, Encryption has to be an invertible function unlike Hashing which is a one way function. So any standard Encryption algorithm cannot have collisions, since it would make reversing the process (i.e. decryption) impossible. So no collisions in Encryption as long you are using the same encryption key.

Enc(Plaintext1, key1) never equal to Enc(Plaintext2, key1)

ilkkachu avatar
ws flag
true, though note that they had the two distinct keys $k$ and $k_1$ there. The question isn't $E(m_1, k) = E(m_2, k)$ but $E(m_1, k_1) = E(m_2, k_2)$
kelalaka avatar
in flag
This read incorrectly as I did before. The OP asking for collisions with different keys. proving existence is easy, finding with specific text is hard. Check the first part of my answer.
Score:3
in flag

Block Ciphers collision with different keys

If there is plaintext key pair $m,k$ that yields some ciphertext, and there exists another key, message pair $m_1,k_1$ that also yields the same ciphertext, is this essentially a similar issue as a hash collision?

Yes, it is similar to hash collision, there is an attack case if the same key is used, see the bonus section. For different keys it doesn't reveal anything.

If you are using CTR ( any streaming mode ) then if you have a ciphertext collision this will not reveal the messages since

$$m_1 \oplus o_1 = c_1 = c_2 = m_2 \oplus o_2$$ because

$$m_1 m_2 \oplus = o_1 \oplus o_2$$ and this will not reveal the messages even you guess one.

And similarly, CBC mode will be resist the collisions under different keys.

Ciphertext collision possibility

suppose we AES-encrypt 'moon' with key 'morehotquestions' getting 'fjydhpdag'. and we encrypt 'sun' with key 'hotnetworkquestions' getting also 'fjydhpdag'. is this even possible?

If we consider that AES is a PRP, then we have the exactly same condition as the birthday attack. The probability of two single blocks will have the same ciphertext is $1/2^{128}$ for the ECB block.

Finding one us much easier since AES is invertible. Consider ECB for easy case. Since AES is invertible, take a ciphertext and decrypt it with two different keys. Then you will get two different messages. Of course, they are not necessarily meaningful, this is easy way to find/show this.

Signature systems like RSA-Sign

Signature systems use a hash of the message to sign. One of the ways to forge the attacker needs a second pre-image attack on the hash function. What if we have a malicious signer or malicious secretary of the signer? Assume that they use MD5 for which collision is imminent ( don't use MD5 and SHA-1 for signature) then they can find two messages with the same hash values. $h(m_1) = h(m_2)$ with $m_1 \neq m_2$ then the two values $$\operatorname{RSA-Sign}(h(m_1)) = \operatorname{RSA-Sign}(h(m_2))$$ are the same.

Always use collision-resistant cryptographic hash functions like SHA-256, SHA-512, SHA-3, BLAKE2, etc. to mitigate this attack.


Bonus part: Block Ciphers collision with the same key

Yes, there are attacks and concerns about this; like Sweet32;

  • Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN

    In short, for a block cipher of size $b$, if you are encrypting $2^b$ blocks under the same key one can get a collision on the ciphertext of the CBC mode that it $c_i = c_j$ with $i \neq j$. That is;

    $$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$

    Then using CBC's properties we can get

    $$m_i \oplus m_j = c_{1-1} \oplus c_{j-1}.$$

    As we can see this is just the x-or of the plaintext blocks that a passive attacker can exploit.

I've talked only CBC mode, however, the page mentions more and left to investigate similar to CBC;

This is particularly important when using common modes of operation: we require block ciphers to be secure with up to $2^n$ queries, but most modes of operation (e.g. CBC, CTR, GCM, OCB, etc.) are unsafe with more than $2^{n/2}$ blocks of message (the birthday bound).

Of course, we are almost no longer using 64-bit block-sized ciphers. However, this attack is even possible if you are encrypting too much data using the same key. One might say encrypting a $2^{64}$ data is too much, we will not encrypt such size. Then we have a deeper argument, 50% of the birthday attack is too much for the advantage of an attacker, it is far from negligible. They can look even for lower probabilities to reveal some block of the messages. You should limit to $2^{32}$-block to reduce the advantage of the attacker.

nimrodel avatar
cz flag
suppose we AES-encrypt 'moon' with key 'morehotquestions' getting 'fjydhpdag'. and we encrypt 'sun' with key 'hotnetworkquestions' getting also 'fjydhpdag'. is this even possible? i am asking about two completely different keys and messages. can then, if they can indeed encrypt to same 'fjydhpdag', AES decryption system get confused, that is it does decrypt to both plaintexts with different keys?
kelalaka avatar
in flag
Different keys select different permutations and this, in general, prevents may attack. The Sweet32 attack requires the same key you don't. You should define your mode of operation to talk about more on this since devil is in the details ( please do not modify the question since it got some answers)
kelalaka avatar
in flag
I wrote a section for your specific question that I missed and anwer to you comment, also.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.