13
$\begingroup$

Consider a block cipher with a key of size 128 bits but a small block size, say 32 bits. Is this kind of block cipher secure?

I would like to know to what extent I can use a small block cipher, like a 32 bit block cipher. What are the constraints so that the use is acceptable in a real life application.

For instance, if we use a one-time key, that is, to encrypt only one message. Besides, the message could be small.

Suppose that when we want so send one file, we perform a key agreement so that we use the key for one message. This scenario is not efficient, but the CPA find-then-guess game is not adequate in this case.

Improve this question
$\endgroup$
1
  • $\begingroup$ Please define what you mean by "secure". It might be a secure pseudorandom permutation, even though it's not very useful in practice (e.g., not very useful in any standard mode of operation). Which are you asking about? I suggest you edit the question to be more specific. $\endgroup$
    – D.W.
    Jun 21, 2013 at 21:29

2 Answers 2

Reset to default
13
$\begingroup$

Such a block cipher would be completely unusable in any of the standard modes of operation, presuming you want at least IND-CPA security. Say, for instance, that you are using it in CTR mode. A chosen plain text adversary looking at a cipher text consisting of only two blocks (i.e. 2 times 32 bits), would have a non-negligible probability (higher than $2^{-32}$) of guessing if the cipher text is produced by your block cipher in CTR mode, or a random function.

This matters in so far that a block cipher in CTR mode is only secure up to the bound where the block cipher might still be modeled as a PRF, as defined in the security proof. If you are able to distinguish the block cipher from a PRF, CTR mode is no longer IND-CPA secure. This applies to all other standard modes as well.

If one of the CTR mode cipher texts is 16 GB, you will have revealed the entire code book, and the adversary will not need the key.

If you have a hard time seeing this, consider a 2-bit block cipher in CTR mode that has produced the ciphertext stream 3-1-0. If Eve has tricked us into encrypting 0 three times, then the next CTR value must be 2 with probability 100%. Real plaintexts are nearly that predictable, so exhaustion of the ciphertext space is a practical limit. 32 bits is just too tight.

Edit: Please also note that it would be a mistake to assume that failure to meet IND-CPA security, would only be relevant in scenarios where the exact CPA game can be played out. Suppose, for instance, that you encrypt only a single message (in CTR mode) with each key, and that this message is $l$ bits long. If $l \le 32$ you are safe, but if it is longer, you are not. Suppose $l=64$. In such case the plain text $m$ might be divided into two blocks $m=m_0|m_1$ and the cipher text $c$ into two blocks $c=c_0|c_1$. Now, the attacker might immediately deduce that $m_1\ne m_0\oplus c_0 \oplus c_1$ (because $m_i \oplus c_i = E_k(i)$ and $E_k(0) \ne E_k(1)$) and has learned $32/{2^{32}}=2^{-27}$ bits of information about $m$. The more that is known of patterns in $m$ and the greater the length $l$, the more information about $m$ might be deduced even in a cipher text only attack.

Improve this answer
$\endgroup$
14
  • $\begingroup$ For 32-bit block sizes I think a few hundred megabytes of output should be sufficient to distinguish between a CTR keystream and a random function, actually, assuming the plaintext has sufficient structure. $\endgroup$
    – Thomas
    Jun 19, 2013 at 23:35
  • 2
    $\begingroup$ @Thomas: That, of course, depends on the confidence coefficient, as well as what is known of the plain text. As I wrote in my answer, you really only need two known plain text blocks to be more likely right than wrong if you guess it is CTR cipher text if there is no repetition. $\endgroup$
    – Henrick Hellström
    Jun 20, 2013 at 0:00
  • $\begingroup$ Thank you for your answers. I don't understand how an adversary having only a ciphertext of two blocks (and the corresponding plaintext) can distinguish between the block cipher in CTR mode and a random function ? If we speak about the randomized CTR and that the adversary sees several pair (plaintext, ciphertext) I think that I can understand, but if the adversary has only one pair... ? $\endgroup$
    – Dingo13
    Jun 20, 2013 at 7:47
  • 1
    $\begingroup$ @user7060: If you got two CTR mode key stream blocks, you know that, since the counter never repeats, the second key stream block cannot be equal to the first. A random function might otoh repeat. The probability of such repetitions increase with the amount of known plain text you are analyzing, and it is non zero starting from the second block. Suppose the adversary submits a plain text to the challenger, which returns either random data or CTR mode cipher text. If there is a repetition, the adversary will know it is random data. $\endgroup$
    – Henrick Hellström
    Jun 20, 2013 at 8:01
  • $\begingroup$ In a CPA game the adversary will first submit a bounded number of encryption requests to the oracle, which in the case of a block cipher with a 32 bit block size will rule out large portions of the code book. This means that the adversary might choose the two challenge plain texts $m_0,m_1$ such that, regardless of which of the yet unknown cipher text blocks will be used in the key stream, the odds will be low that the adversary will be able to tell which of the two plain texts the adversary encrypted. $\endgroup$
    – Henrick Hellström
    Jun 20, 2013 at 8:08
3
$\begingroup$

As pointed in this other answer, a 32-bit block cipher with 128-bit key can be practically unsafe when used with the standard operating modes. However, it is still fine in some other uses.

For example, we can derive a wide shared secret from the initial 128-bit $K$, say as the concatenation of $E_K(3\cdot i)\oplus E_K(3\cdot i+1)\oplus E_K(3\cdot i+2)$ for $i$ in range $[0\dots(2^{32}-4)/3]$, which is may be [update: I wildly conjecture, without proof or even strong argument, and thus imprudently; see hand-waving attempts of coming with justification in my comments] computationally indistinguishable from a random sequence of $(2^{37}-32)/3$ bits (I use three terms because with just one, all the blocks are different. And with two, the all-zero block can not occur). We can then use the above random sequence in a stream cipher.

Improve this answer
$\endgroup$
5
  • $\begingroup$ iacr.org/archive/eurocrypt2000/1807/18070476-new.pdf $\endgroup$
    – Henrick Hellström
    Jun 22, 2013 at 19:26
  • 2
    $\begingroup$ Intuitively, this makes sense, but do you know of a better security proof, than the one in the link in the comment above? How do you prove that the construct does better than preserve security of the underlying block encryptor? $\endgroup$
    – Henrick Hellström
    Jun 23, 2013 at 7:11
  • $\begingroup$ @Henrick Hellström: I have no proof of my assertion (any attack that I can think of is beyond unworkable, but that should not convince anyone, including me). The construct pass an entropic acid test: defining an arbitrary 32-bit permutation requires $\log_2(2^{32}!)$ bits, we disclose $(2^{37}-32)/3$ bits, about $2.86$ times less. I did not feel confident enough to propose $E_K(2⋅i)⊕\operatorname{RORL}(E_K(2⋅i+1),1)$ for $i$ in range $[0…2^{31}−2]$, although I have no working attack either. The reference that you quote XORs distinct random permutations, thus its proof does not apply to mine. $\endgroup$
    – fgrieu ♦
    Jun 23, 2013 at 11:20
  • 1
    $\begingroup$ It might be a mere curiosity, but I did a full computation of all permutations with a 3 bit and 4 bit block size, and for such small block sizes the output sequence was far from uniformly distributed. Isn't it generally dangerous to just assume it would be indistinguishable from uniform for block sizes that are so small that the permutation is in principle searchable? $\endgroup$
    – Henrick Hellström
    Jun 23, 2013 at 17:06
  • $\begingroup$ @Henrick Hellström: Starting with $8$ bits, the $2^{128}$ keyspace allows only for a tiny subsample of the possible output sequences (there are $2^{680}$ for 8 bits, $2^{45812984480}$ for 32 bits); therefore, any consideration on a small bias in the output sequences is moot (further, I expect that this bias you observed quickly evens out). What would matter very much would be that some of the output sequences can not be reached for any input permutation. $\endgroup$
    – fgrieu ♦
    Jun 24, 2013 at 5:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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