0
$\begingroup$

Given an encryption scheme that takes as input a key $k$ and converts it to an encryption operation $E$ via the function $M(k) = E$, is it possible that more than one $k$ can give the same $E$?

For example, let $k$ and $k'$ be two distinct keys. Is it possible that $M(k) = M(k') = E$. In this sense, the mapping from the 'key space' to the 'encryption operation space' is surjective.

It doesn't seem like it would be a vulnerability or flaw me given the number of different possible encryption operators given by the scheme is large enough, and that each distinct encryption operator is mapped onto by roughly the same number of keys. For instance, let's say the key space for a given key of length $n$ is $2^n$, but the corresponding encryption operation space is of size $2^{\frac{n}{2}}$. For large values of $n$, although a given key would have many 'collisions' (other keys that give the same encryption operator), the protocol could still be secure.

$\endgroup$
3
  • $\begingroup$ I remember that we have a dupe for this. Block ciphers are a family of permutations and each permutation is represented with a key. If we model the selection of permutation uniform random then some keys will represent the same permutation. Well, hard to see one in real life and nearly impossible to find one AES... $\endgroup$
    – kelalaka
    Jun 17 at 18:50
  • $\begingroup$ Just consider that AES has $2^{128}$ permutations from $(2^{128})!$ permutations. If there is a uniform selection, what is the probability of the collision? $\endgroup$
    – kelalaka
    Jun 17 at 18:58
  • $\begingroup$ Here one of the dupes; Do key collisions for symmetric ciphers exist? Are there key collisions in AES-192, AES-256? $\endgroup$
    – kelalaka
    Jun 17 at 18:59

1 Answer 1

2
$\begingroup$

Are there any encryption schemes where more than one key give the same encryption and decryption operations?

Technically, DES does (as does any system built on DES, such as 3DES).

DES takes 64 bit keys [1]; of those key bytes, the lsbit of each byte is ignored. That is, $DES_k$ and $DES_{k'}$ are the same operation if $k$ and $k'$ differ only in the lsbits.

Now, DES isn't considered secure, but not because of that reason; rather it's because the key space is far too small, and the block size is too small.


[1]: You will often read that DES takes 56 bit keys, but that's not how DES is defined. It can be defined more pedantically as taking a 64 bit key, of which 56 bits are used.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.