When a block cipher key length is greater than the block length, is it the case that for some keys $k_0, k_1$ (with $k_0 \not= k_1$) and plaintext message $m$ that $E_{k_0}(m) = E_{k_1}(m)$?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ This will likely be the case for some messages (even if the key is a shorter than the block size), but not for all of them. For a good block cipher for any key-pair $k_0 \neq k_1$ almost all messages will encrypt differently. $\endgroup$– CodesInChaosCommented Jun 30, 2013 at 11:18
-
1$\begingroup$ Related questions AES Key Length vs Block Length and AES key/ciphertext space sizes $\endgroup$– CodesInChaosCommented Jun 30, 2013 at 11:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
A block cipher processes a single block of input and produces a single block of output, where the input and output blocks are the same size. By the pigeonhole principle, if the key size is larger than the block size then there must be some keys that will encrypt the same input block to the same output block.
More formally, a block cipher is defined as the family of encryption functions $E: K \times X \to X$ (and their inverse decryption functions), where:
- $K$ is the set of possible keys with cardinality $|K|$.
- $X$ is the set of possible block values with cardinality $|X|$.
The cardinality (number of elements) of these sets is $2^b$ where $b$ is the length of an element in bits. For example for a 256 bit key, $|K|$ is $2^{256}$ and for a 128 bit block, $|X|$ is $2^{128}$.
If you think of setting the key for the block cipher as fixing the value $k \in K$ to produce a function $e(X) \to X = E(k,X)$, then it's obvious that there are $|K|$ such functions.
It's then easy to see that if $|K| > |X|$, there are more possible encryption functions than there are possible output values, and so for any $x \in X$ there must exist (at least) two keys $k_0 \in K$ and $k_1 \in K$ where $E(k_0,x) = E(k_1,x)$. For a good block cipher, the number of such keys will be very low.
-
1$\begingroup$ Would it not be possible to generate a set of permutations where no element in any permutation has the same place twice? This would avoid the "collisions" at the cost of having fewer keys. $\endgroup$– user7139Commented Jul 1, 2013 at 6:05
-
1$\begingroup$ Every block cipher has to be a bijective mapping over the input/output space $X$ - i.e. every input maps to and from one output using the encryption/decryption functions (this is entirely natural when you think about what a block cipher needs to do: encrypt every possible input value and decrypt that output value back to the input value. When $|K| > |X|$ you still have the same bijective mapping, but the selection of which mapping is used (and the mechanics of how it is effected) is based on the key supplied. $\endgroup$– archieCommented Jul 1, 2013 at 20:24
-
1$\begingroup$ Yes, I see what you mean. Looking at my comment question now it looks as though I had $E(k_0,x)=x$ in mind, which should be avoidable in theory. $\endgroup$– user7139Commented Jul 2, 2013 at 10:27
-
1$\begingroup$ @sashank Apart from using "size" instead of "cardinality" this answer looks correct to me. It only argues that there are multiple keys which encrypt one particular $x$ to the same value. It doesn't argue that there are equivalent keys, which encrypt all $x$ to the same value. This fits the question, which is about that particular property, not about equivalent keys, like the question you linked. $\endgroup$ Commented Jan 30, 2014 at 10:26
-
1$\begingroup$ but the relation is not established correctly. the factor does not depend on cardinality of block size but cardinality on the set of permutations possible which is the crucial part to be specific $\endgroup$– sashankCommented Jan 30, 2014 at 15:38