0
$\begingroup$

For an ideal block cipher, what size key would be required when the cipher has a 32-bit block size?

$\endgroup$
  • 1
    $\begingroup$ Well, of course a 32-bit block size cipher... Or do you talk about the key? Ciphers with this small block size are only secure in a very limited way. If you don't keep this in mind, even the longest key would not help you. 128 bit should be enough for the key, but it's hard to give a firm answer without more informations. $\endgroup$ – Nova Apr 2 '15 at 19:05
  • $\begingroup$ @Nova I think the title was misleading, the question did indeed mention the key. asdfhjk, please re-read your question before posting. $\endgroup$ – Maarten - reinstate Monica Apr 2 '15 at 19:21
  • $\begingroup$ I suspect this is a homework question aimed at establishing why we can't construct an ideal cipher for even modest block sizes. asdfhjk: For a cipher to be ideal, you need one key for each possible permutation. So how many strings are in the set {0, 1}^32? How many permutations are there on a set of this size? $\endgroup$ – Seth Apr 3 '15 at 22:53
4
$\begingroup$

The size of the key depends on the security level you want, it is not possible to say "you need exactly $n$ key bits if you have a block size of $m$ bits".

Let's assume that for an ideal cipher, a block size of 32 bits means $2^{32}$ possible input values which can be permuted in $(2^{32})!$ ways. That means you would have at most $\log_2(2^{32}!)$ key bits, to avoid equivalent keys. This is a lot, and in practice only a (very!) tiny fraction of that amount of bits would be used. In fact, one could argue that this upper bound on the key size is so ridiculously large that it's almost meaningless.

For a lower bound (this is probably what you are interested in), you need to look at the required security level. For example, a 10 bit key is easily bruteforced, but a 256 bit key is secure against brute force attacks (assuming of course there are no other attacks on the cipher).

$\endgroup$
  • 2
    $\begingroup$ $\log_2(2^{32}!)\approx131,242,625,471$ bit. Storing that key for would require slightly less than 16GiB. It is quite easy to make a program implementing such a theoretically perfect 32-bit block cipher; the challenging thing is to make it bearably fast. $\endgroup$ – fgrieu Apr 3 '15 at 7:06
  • 1
    $\begingroup$ @fgrieu A 16 GiB lookup table could fit into RAM and should have acceptable performance. Efficient key expansion from a minimal-size key might be a bit trickier though. $\endgroup$ – CodesInChaos Apr 3 '15 at 8:14

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.