# Is the 64-bit blocksize a fatal issue when encrypting TBs of data with Blowfish CBC?

Crashplan uses 448-bit Blowfish to encrypt the data you send them. The mode used is CBC, keys are multiple use, and IVs are generated with SecureRandom from JCE. Keys are not derived from the password, but are generated randomly. MACs used are MD5 or SHA1.

The more I do research on Blowfish the more it sounds like the 64-bit block size is totally insufficient for the size of the volumes they will be backing up.

I've read that especially in certain modes (like CTR) it is totally insufficient for large streams of data, and can be distinguished from random data after only gigabytes? However, other stuff I've read seems to indicate this isn't an issue if properly implemented.

Would such an attack not apply to Crashplan's implementation?

With this sort of implementation does the 64-bit block size become an issue other than simply being distinguishable from random data after 'x' GB, or would there be greater issues if one were to encrypt say 10TB of data, such as plaintext leaks?

Keep in mind I'm using Crashplan's third option where I generated my own key which is supposedly never sent to Crashplan's servers and the client encrypts all data before sending to their servers. So I don't think transport is an issue? Correct me if I'm wrong.

Another question deals with the Blowfish weak key reflection attack, and is this something I should be worried about? Is there a relatively easy way to check if I'm using a weak key? Or does this just not apply to my situation?

I can make Crashplan backup to a folder on my PC and it seems to encrypt files the same way it would before sending to Crashplan's cloud. I could try to analyze data encrypted with my key if I actually knew what I was doing, but I don't. So, My final question is how would I begin to start analyzing this data if I wanted to try to crack my own stuff or find weaknesses in their implementation? What tools should I use? I'm interested in crypto and would like to learn more.

[This is a follow-up to a question I asked on Stack Overflow.]

-
I think I may have found the answer to my main question here: crypto.stackexchange.com/a/1106/7298. And basically I'm gathering this means that when encrypting TBs of data there is a very high chance of some plaintext leaks, but only 8 bytes here and there? So it probably wouldn't actually matter. Another thing is... since Crashplan uses data de-duplication, would this mean that this actually might not be an issue whatsoever as it won't be encrypting the same data twice ever? –  user7298 Jun 20 '13 at 4:23
Also, according to wikipedia: "Blowfish. Blowfish's weak keys produce bad S-boxes, since Blowfish's S-boxes are key-dependent. There is a chosen plaintext attack against a reduced-round variant of Blowfish that is made easier by the use of weak keys. This is not a concern for full 16-round Blowfish." So, I think that answers my question regarding the reflection attack? Please someone correct me if I'm wrong. –  user7298 Jun 20 '13 at 4:50

I didn't find anything about the exact way Crashplan encrypts files, only that it uses Blowfish in CBC mode. The block size of Blowfish is 64 bit, so there are $2^{64}$ different input blocks and the same number of output blocks. All in all $147573953$ terabytes of different output data. The problem with this is the birthday attack. Summarized it says that the problems with too much encrypted data (for CBC mode) start at ca. $\sqrt{2^{n}} = 2^{\frac{n}{2}}$ (n denotes the block size in bit). For Blowfish we get approximate 34 gigabyte. You'r mentioned "TBs of data" are much more than this. The accepted answer from "poncho" to the question "Importance of block size in CBC mode" shows why it is no good idea to encrypt much more than the mentioned limit with a single key. It would be a good idea to change the algorithm to a higher block size variant or change the key after ca. 34 gigabyte or even less.

To analyse the ciphertext of Crashplan you have to know how the program saves the encrypted data. Try to convert the saved file into the original output blocks of Blowfish and then look for equal blocks. As soon as you find two equal blocks you can use the attack in the answer of poncho mentioned earlier. If you know the plaintext block of one of the block (due to some patterns or something else) you can calculate the value of the other block.

How bad is this attack? Well, the attacker has to have good luck with finding equal blocks. The bigger the ciphertext, the higher the probability for equal blocks. After that the attacker has to know some patterns of the plaintext. Many identical or just similar files (like many pictures saved in PNG format) can help the attacker to exploit patterns. And that's only for the hardest attack someone could use, a Ciphertext-only attack (the enemy only knows the ciphertext, but nothing concrete about the plaintext). If the attacker has the ability to save his or her own files in your backup (like a employee maybe could do it) there's no way to prevent him or her from getting special patterns into your plaintext.

There's no publicly known way to break Blowfish. Even if your key is a weak key (or will be hashed into a weak key) it won't harm the encryption in any known way. The mentioned attacks only work for a reduced-round Blowfish.

-

You are correct in that after the birthday bound you will leak some plaintext in random 8-byte blocks. Nova's answer has the specifics and links to useful sources.

To give you a rough idea of the risk, you can look at what percentage of the data could leak. 10 TB is about $2^{40}$ blocks. The expected number of collisions is $2^k (1-(1-2^{-n})^{2^k-1})$, which is about $2^{k^2-n}$ when $2^k \ll 2^n$.

With $2^{40}$ that adds up to about $2^{16}$ collisions, or half a megabyte of data. About one part in twenty million ($2^{-24}$), considering the share of all the encrypted data. Every time you double the data, you quadruple the data leaked and double the share of it.

This approximation only works while you are relatively far from $2^{64}$ blocks, but should be reasonably accurate until you start talking about exabytes of data.

-