Are convergently-encrypted ciphertexts safe from collision attacks?

Question

Convergent encryption uses a message digest of the plaintext as the key to encrypt the plaintext to produce the ciphertext.

This is useful for automatic content sharing because it produces a deterministic ciphertext between unrelated parties who encrypt it without revealing contents to parties who never encrypted it. Weaknesses exist, but it can be a useful thing for automatic content sharing in storage systems.

e.g.

compute SHA256 of plaintext -> KEY1

Use KEY1 to encrypt plaintext using AES256 with CBC -> ciphertext

compute SHA256 of cyphertext -> ID1

When sharing, it would be nice to avoid malicious collisions (e.g. widely distributing the funny graphic in email, identified by ID1, and converting it to something obscene in automatically-shared storage that also happens to have ID1).

The straightforward way is to make sure the hash algorithm is secure. SHA256 is reasonably secure even against collision attacks, which is a greater vulnerability than the preimage attacks.

But let's say you want to store your blocks in a medium that identifies objects by a weaker hash, such as MD5, which is vulnerable to collision attacks. In the above example, this means that ID1 is computed or verified using MD5 instead of SHA256, because it is done by the system when storing the ciphertext. Specifically AWS S3 supports MD5 on objects, specifically not intended for security but it is there. KEY1 is still computed using SHA256 since that is not part of the object identification/verification process.

The question is, does the process of convergent encryption protect adequately against collision attacks to make them infeasible like preimage attacks of MD5?

It seems like on the one hand, producing a plaintext that after encryption with a known key collides might not be difficult because you can decrypt anything with a symmetric key.

But convergent encryption means that as you mutate your cyphertext looking for a collision changing the plaintext, the key changes as well. Colliding cyphertexts can be produced, but finding cyphertexts that can be mapped back to a plaintext whose MD used as a key produces the cyphertext during encryption seems difficult.

Is it likely that there is a practical way to compute collisions, or did the convergent encryption preprocessing make the weaker MD5 of the storage medium no longer vulnerable to collisions of content that originated as plaintext?

All I have to go on is that it boggles my mind how this collision could be computed, but this sort of instinct can be wrong, so I was wondering whether anyone else had thoughts on whether it might be achieved.

Answer 1

The answer should be "No. A convergently-encrypted ciphertext is not safe from collision attacks."

Just because it is encrypted convergently does not mean it is not subject to collision attacks. MD5 has 128 bits, therefore, I could expect to have to generate at worst around 2^64 attempts to crack it.

Each collision attempt is more complex to generate because of the need to generate a new key via SHA256, reencrypt, and recompute MD5. There is no need to re-SHA256 the entire plaintext each time for the key, and it is also not obvious whether or not there might be a way to exploit known weaknesses of the MD5 hash to crack it in less than 2^64 attempts, but the question as stated was whether it was safe from a collision attack, and the simple answer has to be "No".

The 2^64 worst case seems to be similar to that of the Google SHAttered SHA1 collision demonstration even if generating each attempt requires more computation for convergent encryption. "Safe" might be a relative term that I did not define. I will try to be more concise in the future. But using MD5 to guarantee non-colliding convergently-encrypted content should not pass a security review. This would be why in the SHA2 specification there is no hash with less than 224 bits, which is 96 rounds greater than MD5, a factor of 2^48 difference for collision attacks.