Question for Cryptography experts

Here is the end user scenario:
You get a large chunk of data, and the corresponding encrypted data.

Does having both versions help you significantly in your ability to find the key?

Behind the scenes, the encryption method is BlowFish (strong encryption) and the key is 48 bits long. What I want to know, if a user got a sample of both the encrypted and decrypted data, would this pose a significant security risk in allowing a hacker to find the key used to encrypt/decrypt everything?

In this case yes, because a 48-bit key is easily within the realm of being brute-forced when they have the plaintext to verify success.

Not if the encryption is any good.

A good algorithm is one that, if the attacker had plaintext, cyphertext, and (in the case of public key cryptography) the public key, the attacker still wouldn’t wouldn’t have an affective means.

Wikipedia quote:

There is no effective cryptanalysis on the full-round version of Blowfish known publicly as of 2006, although the 64-bit block size is now considered too short, because encrypting more than 232 data blocks can begin to leak information about the plaintext in most modes of operation due to the birthday attack. Despite this, Blowfish seems thus far to be secure. While the short block size does not pose any serious concerns for routine consumer applications like e-mail, Blowfish may not be suitable in situations where large plaintexts must be encrypted, as in data archival.

In 1996, Serge Vaudenay found a known-plaintext attack requiring 28r + 1 known plaintexts to break, where r is the number of rounds. Moreover, he also found a class of weak keys that can be detected and broken by the same attack with only 24r + 1 known plaintexts. This attack cannot be used against the full 16-round Blowfish; Vaudenay used a reduced-round variant of Blowfish. Vincent Rijmen, in his Ph.D. thesis, introduced a second-order differential attack that can break four rounds and no more. There remains no known way to break the full 16 rounds, apart from a brute-force search. [1]

So, if you use the strong version, it should be safe from plaintext attacks.

Yup. 48 bits is weak.

Are you using the full 16-round Blowfish? There are publically-known weaknesses in any implementation of Blowfish that uses less than the full 16 rounds for the cipher.

Yup. 48 bits is weak.

Are you using the full 16-round Blowfish? There are publically-known weaknesses in any implementation of Blowfish that uses less than 8 rounds for the cipher.*

*Google: Serge Vaudenay blowfish

Any encryption method (including Blowfish, as Schneier himself would say) is useless if you have both the plaintext and ciphertext and you know it’s a 48-bit key.

At Schneier indicates that a Pentium 1 (that’s old school, kids!) encrypts one byte every 18 clock cycles using blowfish. On a P150, that’s just over 8 million encrypted bytes per second. If we pretend just for a goof that they use an 8-byte block size, that’s 1 million bruteforce attacks per second: taking the plain text, encrypting it with a key, and comparing it with the ciphertext.

A 48-bit keyspace is about 281.5 trillion possible keys. On average we will have to search half the keyspace to find the key, so about 150 trillion (rounded up because I’m lazy). This will take about 150 million seconds = 42000 hours (again, rounded up) on a single P150.

If we assume today’s high end AMD64 or P4 chip is, say, 100 times faster than the P150s (especially on math ops as used in crypto), this breaks a 48-bit key in three weeks on a single computer. Two dual proc computers? Five days.

edit: corrected speed estimates and calcs, in bold

I do not think a P4 chip is 1000 times, or even 100 times as fast as a P150. I could be wrong, but I would guess maybe 50 times as fast.

However, 1 day or 10 days, is far to little. I guess I am going to have to tell someone something they do not want to hear.

If, they did not know what they key size was, would that throw a monkey wrench into the works? Also, if I brought the key up to 128 bits, would that be nearly uncrackable?

Yes, I am using the 16 rounds for blowfish. I could bump that number up too and just pick some odd amount of rounds like 22 or so. Maybe a key of a weird length like 72 or 90 bits might be good too.

Is that table of numbers normally assoicated with blowfish ‘speical’ ? IE: If I used my own random numbers in thier place, would that be fine or are they significant in some way?

I’d agree 1000 times faster is way too large of an assumption in the speed difference area. Somewhere between 50-100 sounds better. And yeah, if he doesn’t know the keysize and he’s not a lucky guesser, he’d have to start with a 32 bit keysize and work his way up from there to 48. If he’s dedicated at all, you’re still looking at something that is pretty achievable, especially if he has a small network of computers to devote to it, but I’d have to have more context on the situation to have an opinion on whether it is something you should really be worried about. (eg: I use 64bit WAP on my wireless router. I know it isn’t very secure at all in theory, but I consider it secure enough for my meager security requirements of not wanting Joe Blow neighbor stealing my bandwidth).

OK I was off. It looks like about 75x faster in raw math.

I suspect that a brute-force attack program compiled to take advantage of 64bit CPUs, SSE instructions, etc. on a modern CPU would increase that though. Dedicated hardware like a clever pixel shader on a top notch video card perhaps even more. Blowfish basically only uses XOR and modulo addition so it wouldn’t be hard. 100x faster on this specific problem probably isn’t too much of an over-estimate.

Stick with 16 rounds. I personally am against changing round counts (up or down) because non-defaults are usually cryptanalyzed far less and may show a severe weakness. But you may want to use a larger block size than 64 bits/8 bytes. Wiki claims a plaintext leak has been shown with 8 byte block size after encrypting 2^32 blocks (or about 32Gb worth of data). If you’re one of those hard core paranoia guys or you have large amounts of data like archives, movies, etc. use 16 rounds on 16 byte blocks with a 256 bit key and you’ll be fine for a long time.

Brute forcing a 128-bit would currently take a long time… like end of the universe long.

For stuff you want to keep secure for the next 20 to 30 years, experts recommend a 256-bit key. You’ll need something like a 196 character English passphrase to generate a secure 256-bit key, though. For a 128-bit key, a passphrase “only” 98 English characters long is sufficient. :-)

And if you’re looking for a good English passphrase, just try an excerpt from a Koontz post. That should be totally unbreakable…

Naw, the key I am using is binary, aka it has bytes of any types, from things like 0x05 to 0xca . Ill just expand the key size then to 96 bits. Ill leave the SBoxes alone though if it really can cause a much longer encrypt/decrypt time since that is a big concern on the server-side.

You better leave the S-Boxes alone. The strength in an algorithm is 90% tied to those. Remember the conspiracy theorists who thought that the NSA had weakened DES when they asked IBM to change the S-Boxes way back in the day before IBM published the actual standard? 20 years of cryptanalysis by the public found out they actually strengthened it.

One strategy some people use to mitigate the length of keys is similar to yours. They will have something shorter, like say a 15-20 letter password, which encrypts the “real” key which is a random string 128 or 256 or longer. Then the real key is used for the data decryption. Why? Because attacking your 20 letter password doesn’t give them any info about the real key. It was a random bitstring to begin with, so it won’t look like plaintext when decrypted. It is just as feasible to brute force the data itself.

edit: clarify

The short answer is definitely yes. A lot of attacks on encryption relies on guessing some of the plaintext. If you have an actual sample of the plain text, figuring things out goes from being near-impossible to being doable.

Me: Blowfish? What the fuck?


Me: ohhhh

I am torn between “the government is focusing so much energy on quantum computing because ‘quantum computing’ sounds cool” and “they know something we don’t.”

Well, look how cool looking Hollywood are making these things:

That does look cool.

The nitty gritty is that quantum computing, when/if we manage to make it work, will render most existing cryptography obsolete. That includes TLS used to encrypt every website starting with “https://” and for the junkies, toddler twiddlers, and political dissidents, TOR too. And VPNs.

On a side note, we know from Snowden’s revelations that the UK did a “full take”, meaning they permanently recorded and retained all data going over their internet links. This was in 2013, 9 years ago. Today of course everybody does it.

This means the government will be able to view everything you did online for the past 10 years, if not more. And by “you”, I mean “YOU”. Everybody. Here in the US, they aren’t allowed to look at US citizen data without a court order but a) the TLAs only pay lip service to that, we know this from other Snowden revelations and b) The US is in league with the “14 eyes”, 13 other countries that agree to share SIGINT.

It basically breaks all forms of encryption other than those specifically designed to be resistant to quantum attacks. These algorithms do exist, and work fine, they just aren’t in wide use yet. The link @woolen_horde posted is about switching to those new algorithms. We need to do that before quantum computing even approaches the mainstream or basically all commerce (both offline and offline) and privacy will be destroyed in the blink of an eye.

@stusser, I’m madly searching for the “like” button and failing to find it, so have this thumbs-up reply instead.

Come back here in 11 months! Tell Siri to remind you.

Or tie a string around your finger so, you know, future quantum computers can’t decode your comms with Siri.