I'm trying to understand what characteristics or properties make the result of a function a block cipher. I understand that for a function to be a block cipher it has to be invertible and can't be a one-way function.

What I don't get is how to compute a cipher. So for example, I have the following cipher: $F_k^r(m) := r(k,m)$. Now $r$ is defined as a random compression function such that $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$. The length of $k$ and the number of bits for the message $m$ are both $n$, i.e. arbitrary.

What I don't know is how to compute the cipher and why it may potentially not be a block cipher? I think it isn't a block cipher because you are starting with $3n$ and then getting an output $n$ in the random compression function. But I think I am going wrong something.

I know I am getting close in better understanding it, I just kindly need someone to clarify the cipher and why it may not be a block cipher

  • $\begingroup$ Why is the above cipher not a block cipher though? That's what I'm failing to understand. Also how do I compute the cipher, given a random compression function as mentioned above? Please any help, much appreciated. I'm self teaching myself $\endgroup$ Nov 28 '18 at 21:24
  • $\begingroup$ @kelalaka so in this case, why is my example not a block cipher? More importantly, how do I even compute a cipher :S. Sorry sir, I'm really dumb and stupid at things like this. $\endgroup$ Nov 28 '18 at 21:29
  • $\begingroup$ @kelalaka thats why I think it isn't a block cipher, but i don't know how to even compute a cipher $\endgroup$ Nov 28 '18 at 21:34
  • $\begingroup$ I just made it up myself. I'm trying to better understand how to design ciphers and figure out what makes or doesn't make a block cipher $\endgroup$ Nov 28 '18 at 21:36
  • $\begingroup$ i just came up with this one and showed it to a friend who vaguely told me that it wasn't a block cipher. I just wanna know why it isn't that is all $\endgroup$ Nov 28 '18 at 21:38

The Wikipedia definition states;

In cryptography, a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called a block, with an unvarying transformation that is specified by a symmetric key

A block cipher consists of two paired algorithms, one for encryption, E, and the other for decryption, D. Both algorithms accept two inputs: an input block of size n bits and a key of size k bits; and both yield an n-bit output block. The decryption algorithm D is defined to be the inverse function of encryption.

Your $F_k^r(m) := r(k,m)$ with $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$ is not a block cipher since:

  • The input block size and the output block size are not same as in the Wikipedia definition. Therefore you cannot define the inverse (decryption). With the key concerned, the input space must be $2^{2n}$, not $2^{3n}$ and output space must be $2^{n}$.
  • $\begingroup$ Thanks for your answer. The question is why would it be a block cipher if it was 2^n???? Apparently it has to be a n input to n output, i.e. n -> n no? $\endgroup$ Nov 28 '18 at 23:28
  • $\begingroup$ @JezDon-Tresgrafteron in the the question r is defined from $\{0,1\}^{3n}$. It is your definition. could you clear the above comments under the question? $\endgroup$
    – kelalaka
    Nov 28 '18 at 23:37
  • $\begingroup$ @JezDon-Tresgrafteron It can be a block cipher if the input space is $2^{2n}$, but not necessarily. Does the inverse exist? $\endgroup$
    – kelalaka
    Nov 28 '18 at 23:39
  • $\begingroup$ No the question says its a mapping from 3^n to n. My question is why can't it be a block cipher if the random compression function is 2^n to n? Like does it have to be n to n?? $\endgroup$ Nov 28 '18 at 23:42
  • 2
    $\begingroup$ You made an interesting point about "The input block size and the output block size are not same" and so you can't define decryption. So you mean that 2n -> n means that it can't be decrypted? Input has to be same as output right?? $\endgroup$ Nov 29 '18 at 0:05

So for example, I have the following cipher: $F_k^r(m) := r(k,m)$. Now $r$ is defined as a random compression function such that $r: \{0,1\}^{3n} \rightarrow \{0,1\}^n$. The length of $k$ and the number of bits for the message $m$ are both $n$, i.e. arbitrary.

This doesn't quite make sense, there is certainly a mix of mistakes and missing context:

  • It can't be the case that both $k$ and $m$ are of length $n$, and that $r$'s domain is strings of size $3n$. (I think it's likely that what was meant is that $m$ is of length $n$ but $k$ of length $2n$.)
  • Saying that the length $n$ is arbitrary is imprecise at best; it makes it sound like we're talking about variable length messages. Likely what was meant is that $n$ can be any size chosen at the time the definition is instantiated (not at the time the function is used).
  • I don't see that it's strictly wrong, but it's odd to talk about a block cipher with block size $n$ and key size $2n$ as taking a single input of size $3n$.
  • The fact that the formulation here mentions compressions functions suggests that we're in a hash function scenario, but the question doesn't mention that anywhere.

The last point I think is a critical clue of what's going on here. The problem is that the term "block cipher" is used with slightly different senses in more than one context:

So it turns out that what's precisely meant by "block cipher" actually depends on context, but the stable property is that it's a keyed family of permutations (i.e., a collection of permutations where each permutation is identified by a key), such that to a computationally-limited adversary it "looks random." The bit in scare quotes then needs to be clarified by a contextually appropriate model, e.g., PRP for encryption vs. ideal cipher for hashing.


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.