6
$\begingroup$

I've recently heard the claim that wide block ciphers avoid birthday bound problems. Trying to figure out what exactly "wide block encryption" is, a quick search turned up this paper which is trying to do the following:

The focus of this paper is how to use a standard block cipher as a component to build a ”wide” block cipher, or, in other words, to build a secure PRP from another PRP operating on a smaller domain.

Also stating that

The size of the wide block cipher is l=n∗m bits.

It specifically mentions IEEE P1619-2 (Wikipedia). But that standard seems to be paywalled. From the description on Wikipedia it sounds like it is related to disk encryption but that is not a real definition. It might just be a block cipher with a bigger block size but that seems pretty vague.

Could somebody please tell me what a wide block cipher is and why it avoids the birthday bound?

$\endgroup$
  • $\begingroup$ From the document "This standard improves on IEEE Std 1619-2007 by defining wide-block encryption algorithms. This means that they act on the whole logical block at once, and each bit on the input plaintext influences every bit of the output ciphertext (and vice versa for decryption). In particular, this standard specifies the EME2-AES and the XCB-AES wide-block encryption algorithms." $\endgroup$ – b degnan Jun 13 '17 at 10:57
7
$\begingroup$

I don't think the term "wide block cipher" has a hard definition beyond

has a larger block size than the current standard algorithm(s)

which right now in most cases would equal to

has a block size larger than 128 bit

because AES is our current reference standard.


Now the thing with block ciphers is that they are are pseudo-random permutations and as such you can distinguish them from pseudo-random functions because you will see a collision with the latter at the birthday where you won't find that with PRPs. This can be important in scenarios where you need to generate a lot of random numbers mostly and even then I don't think the different characteristic would be exploitable in most cases.

To see how PRPs can be distinguished, assume as an example that you run CTR-mode with a PRF and a PRP, both with $n$-bit output length. You will now find that a collision in the CTR keystream occurs with the PRF at about $2^{n/2}$ invocations whereas this won't happen until after you wrap-around with the PRP.

Another application of wide block ciphers is in full-disk encryption where you can encrypt larger blocks implying that single bit-flips will destroy larger regions of plaintext thus being (hopefully) more notice-able.

The last somewhat popular application of wide block ciphers is as part of hashing functions. Imagine your average block cipher $E:\{0,1\}^k\times \{0,1\}^n\to\{0,1\}^n$, note that you can put more into the function than you take out of it. Now you expect collisions after $2^{n/2}$ invokations, ie you have $n/2$-bit collision resistance which makes non-wide block ciphers (such as AES) unsuitable for usage as a core compression function in hash functions (because $2^{64}$ operations is feasible and a similar amount of work was done for the SHA-1 collision).

$\endgroup$

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.