0
$\begingroup$

Blowfish has a large key setup penalty, except is fast once it gets rolling. I believe that before AES optimizations became commonplace, it was faster than AES after the initial key setup. It's top speed once it gets rolling is good for bulk encryption, except it has a 64 bit block size. Would the following address the block size limitation in terms of bulk encryption?

You encrypt the first 64 bit block with all three keys.

You then take the first key and grab the next block starting at bit 33 to 97. After that you encrypt blocks 98-162, 163-227, etc., progressing 64 bits at a time after the initial half-step.

You then transpose the bytes of the intermediate ciphertext 128 bits at a time across the entire hard drive, specifically mixing across the two 64-bit blocks. You could use a static byte level transposition, odd byes in one block and even bytes in the other. I'm looking into other ideas, such as a matrix, except for now I'm still at a static or possible key-based columnar transposition for now.

You then take the second key and grab the next block starting at bit 17 to 81. After that you encrypt blocks 82-146, 147-211, etc.

You then transpose the bytes of the intermediate ciphertext 128 bits at a time, specifically mixing across the 2 64-bit blocks.

You then take the third key and grab the next block starting at bit 9 to 73. After that you encrypt blocks 74-138, 139-203, etc., progress 64 bits at a time.

Does the key staggering complicate the MITM attack? I'm trying for triple 256 Blowfish with defense against the 64 bit block size and possibly even defense against the MITM attack.

$\endgroup$
3
  • $\begingroup$ It would be three separate keys with three separate IVs. The key setup penalty would have to be paid for each key on the first block. The initial 1024 bit permutation cost is trivial in the context of encrypting multiple terabytes of data. It is only being done because the first 16 bits are not subjected to key staggering. Only one bit of the first 16 bits are originally from that block. $\endgroup$ – GuyOnInternet Nov 26 '20 at 6:52
  • $\begingroup$ The bit numbers are slightly off, no matter if we start numbering at 0 or 1. For example there's an offset of 64 between [33 to 97) and [98-162), leaving bit 97 untouched. But at least I think I now get the general idea (except about how the end of the plaintext is handled). This seems to be an operating mode essentially performing 3 ECB passes with an offset of 32-bit, 16-bit and 8-bit compared to natural block alignment (with an irregularity in the first 64 bits, and an arbitrary public plaintext permutation before that). $\endgroup$ – fgrieu Nov 27 '20 at 7:32
  • $\begingroup$ " The first bit of each of the 16 64 bit-blocks is placed in the first 16 bits and replaced with bits from the first 16 bits" sorry, I cannot parse that sentence. This is why having a more formal description makes sense. $\endgroup$ – Maarten Bodewes Nov 27 '20 at 14:57
1
$\begingroup$

My understanding is that the cipher's encryption:

  1. Performs a fixed public reversible transformation of the first 128 bytes of plaintext.
  2. Enciphers the first 8 bytes $[B_0…B_7]$ with $K_1$, $K_2$, then $K_3$
  3. Enciphers bytes $[B_{4+8i}…B_{11+8i}]$ with $K_1$
  4. Enciphers bytes $[B_{2+8i}…B_{9+8i}]$ with $K_2$
  5. Enciphers bytes $[B_{1+8i}…B_{8+8i}]$ with $K_3$

The index $i\ge0$ grows as large as necessary to cover the whole plaintext (something untold takes care of the end).

Consider what happens when one enciphers the all-zero plaintext. Step 1 leaves that unchanged. Step 2 causes irregularities in the first 8 bytes. Step 3 extends that to the first 8+4=12 bytes. Step 4 extends that to the first 12+6=18 bytes. Step 4 extends that to the first 18+7=25 bytes. But starting from byte 25 in the output of step 5, there's a key-dependent pattern that repeats every 8 bytes.

More generally, for any repeating 8-byte pattern in plaintext, there's a matching 8-byte pattern in the ciphertext (after the first 128+4+6+7=145 bytes or so).

I conclude that the proposed construction does not fully "address the block size limitation in terms of bulk encryption". It does increase diffusion, thought.


I advocate against step 1. It does make the first byte of ciphertext dependent on more input bytes, but any fixed public reversible transformation of plaintext demonstrably has no cryptographic value under Chosen Plaintext Attack (as in the above), or under any Known Plaintext Attack working with random plaintext.

It's possible to make a 128-bit block cipher out of a 64-bit one. Assuming some safe operating mode like GCM, CTR, CBC, OFB, CFB on top of that, a simple such 128-bit block cipher construction that I would trust to have security up to $2^{48}$ bytes encrypted (rather than $2^{31}$ for Blowfish or $2^{64}$ for AES) uses 6 keys, assumed independent. In a Blowfish context, we could prefix a common key with 6 different 4-byte haphazard public constants. Starting from a 128-bit plaintext $[B_0…B_{15}]$:

  • encipher $[B_0…B_7]$ with $K_1$, $[B_8…B_{15}]$ with $K_2$.
  • encipher $[B_4…B_{11}]$ with $K_3$, $[B_{12}…B_{15}]\mathbin\|[B_0…B_3]$ with $K_4$.
  • encipher $[B_0…B_7]$ with $K_5$, $[B_8…B_{15}]$ with $K_6$.
$\endgroup$
2
  • $\begingroup$ After the first key encrypts the entire message, does taking 128 bit blocks of the intermediate ciphertext and shuffling them into two halves based on even-odd indexing (with even indexed bytes in one block and odd-indexed bytes in the other), and then doing the same thing after the second key is done encrypting help increase block size when used in conjunction with the key staggering? $\endgroup$ – GuyOnInternet Nov 28 '20 at 3:55
  • $\begingroup$ @GuyOnInternet: This new proposition removes the "for any repeating 8-byte pattern in plaintext, there's a matching 8-byte pattern in the ciphertext" property, increasing that to 16, even with two stages instead of three. However, for two stages (and I do not rule out this extends to three), there exists sizably many repeating 8-byte patterns in plaintext with a matching 8-byte pattern in the ciphertext. For two stages that happens for $2^{32}$ out of $2^{64}$ patterns. That can be avoided by additionally using more keys, alternating use of two keys at each stage. $\endgroup$ – fgrieu Nov 28 '20 at 6:55

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.