Bulk encryption with Triple Blowfish

Question

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.

Answer 1

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$.