Introduction to the

Blowfish is a symmetric key block encryption algorithm invented by Bruce Schneier in 1993. Similar to DES and AES, Blowfish is a block encryption algorithm. Blowfish is used to replace DES.

AES, by contrast, is a symmetric cryptographic algorithm with high cryptographic strength, but it pays a licensing fee to NIST for commercial use.

Blowfish,

Blowfish, like DES, uses a Feistel password for block encryption. Blowfish’s block size is 64bits and the variable key length can range from 32bits to 448bits.

Blowfish requires 16 rounds of feistel encryption. Let’s first get a rough feel of the encryption process of blowfish algorithm from the following figure:

The general process is to divide P(original data) into left and right parts, perform xOR operation with the left part and Kr first, call F function with the obtained result, and finally perform xOR operation with the output result of F function and the right part.

Replace the left and right parts of the position, continue to carry out such operations, a total of 16 rounds to get the final encryption results.

You can see that the two most important variables in the whole encryption process are the Kr and F functions.

And we’ll talk about that in more detail.

Key array and S-box

Key array

As we can see from the graph, Kr ranges from K1 to K18. There is an array of 18 keys. Each key is 32 bits long.

Let’s look at how the key array is generated.

First we initialize the key array with a random number. How do you generate a sufficiently random 32 digit number?

A common approach is to take the fractional part of the constant π and convert it to 16 net values, as shown below:

K₁ = 0x76a301d3

K₂ = 0xbc452aef

.

K₁₈ = 0xd7acc4a5

Remember the length of blowfish’s variable key? From 32bits to 448bits, that is, from 1 to 14 32-bit digits. Let’s call it Pi, so there are 14 mutable keys from P1 to P14.

Next we need to operate with K and P to generate the final K-array.

We use K1 and P1 for xOR, K2 and P2 for xor, all the way to K14 and P14.

Since P has only 14 values and K has 18 values, then we need to repeat the values of P, namely K15 xOR with P1, K16 xOR with P2, all the way to K18 and P4.

Take the xor value as the value of the new K-array.

Now we have a new K array.

Notice that this k-array is not the final array, so let’s see.

S-box

Before we generate the final P array, we’ll introduce a concept called s-box.

In cryptography, s-box stands for Diction -box, which is a substitution box that replaces inputs with different outputs.

The S-box takes n bits of input and converts it to m bits of output.

Here n and m can be different.

Let’s look at an example of s-box in DES:

The s-box above converts the 6-bits input to the 4-bits output.

An S-box can be fixed or dynamic. For example, s-boxes are static in DES and dynamically generated in Blowfish and Twofish.

The F function in Blowfish uses four S-boxes. The input of the F function is 32bits, which is first divided into four 8bits.

The s-box is used to convert 8bits to 32bits.

Let’s take a closer look at the workflow of F function:

The values generated by the S-box are added and xor is performed. You end up with the final 32bits.

An s-box can also be initialized with the fractional part of the constant π, just like a k-array.

Generates the final K-array

In the previous two sections, we generated the initialized k-array and s-box.

Blowfish thinks that’s not safe enough, not random enough.

We still need to do something to generate the final K-array.

First we take a 64bits all zeros, then the K-array and s-box, apply blowfish algorithm, generate a 64bits.

Divide the 64bits into two parts, the new K1 and K2.

This 64bits is then taken as input and blowfish is called again as the new K3 and K4.

And so on, eventually generating all the elements in the K-array.

The array of four S-boxes is also generated according to the above process. So you get the final S-box.

blowfish

With the final K-array and s-box, we can actually encrypt the files we want to encrypt.

Use a pseudocode to represent the entire process:

uint32_t P[18];
uint32_t S[4] [256];

uint32_t f (uint32_t x) {
   uint32_t h = S[0][x >> 24] + S[1][x >> 16 & 0xff];
   return ( h ^ S[2][x >> 8 & 0xff] ) + S[3][x & 0xff];
}

void encrypt (uint32_t & L, uint32_t & R) {
   for (int i=0 ; i<16 ; i += 2) {
      L ^= P[i];
      R ^= f(L);
      R ^= P[i+1];
      L ^= f(R);
   }
   L ^= P[16];
   R ^= P[17];
   swap (L, R);
}

void decrypt (uint32_t & L, uint32_t & R) {
   for (int i=16 ; i > 0 ; i -= 2) {
      L ^= P[i+1];
      R ^= f(L);
      R ^= P[i];
      L ^= f(R);
   }
   L ^= P[1];
   R ^= P[0];
   swap (L, R);
}

  // ...
  // initializing the P-array and S-boxes with values derived from pi; omitted in the example
  // ...
{
   for (int i=0 ; i<18 ; ++i)
      P[i] ^= key[i % keylen];
   uint32_t L = 0, R = 0;
   for (int i=0 ; i<18 ; i+=2) {
      encrypt (L, R);
      P[i] = L; P[i+1] = R;
   }
   for (int i=0 ; i<4 ; ++i)
      for (int j=0 ; j<256; j+=2) {
         encrypt (L, R);
         S[i][j] = L; S[i][j+1] = R; }}Copy the code

The application of the blowfish

As you can see from the above flow, Blowfish takes some time to generate the final K-array and S-box, but once it is generated, or if the key remains unchanged, Blowfish is still a fast grouping encryption method.

Each new key requires about 4 KB of text preprocessing, which can be slow compared to other block cipher algorithms.

Is there any advantage to being so slow?

Of course, because for a normal application, you don’t change keys very often. So preprocessing is only generated once. It’s going to be really quick when you use it later.

For a malicious attacker, each time a new key is tried, lengthy preprocessing is required, so it is not cost-effective for an attacker to break blowfish. So Blowfish is protected against dictionary attacks.

Because Blowfish has no patent restrictions, it is free for anyone to use. This benefit has contributed to its popularity in cryptographic software.

Such as blowfish’s bcrypt algorithm, which we’ll cover in a later article.

The disadvantage of blowfish

Blowfish’s use of a 64-bit block size (compared to AES’s 128-bit block size) makes it vulnerable to birthday attacks, especially in an environment like HTTPS. In 2016, the SWEET32 attack demonstrated how a birthday attack can be used to perform plain text recovery (that is, decrypt ciphertext) on 64-bit block-size passwords.

Because blowfish’s blocks are only 64bits, which is relatively small, the GnuPG project recommends not using blowfish to encrypt files larger than 4 GB.

In addition, Blowfish is vulnerable to known plaintext attacks with reflexive weak keys if it does only one round of encryption. But our implementation uses 16-round encryption, so it’s not vulnerable to this kind of attack. But Blowfish inventor Bruce Schneier still recommends migrating to Blowfish’s successor, Twofish.

This article has been included in www.flydean.com/blowfish/

The most popular interpretation, the most profound dry goods, the most concise tutorial, many tips you didn’t know waiting for you to discover!

Welcome to pay attention to my public number: “procedures those things”, understand technology, more understand you!