Blowfish

Na criptografia, Blowfish é uma cifra simétrica de blocos que pode ser usado em substituição ao DES, algoritmo que possuía em torno de 19 anos de uso,e era vulnerável a ataques por força bruta devido ao tamanho de sua chave (56 bits), ou em substituição ao IDEA. O Blowfish apresenta uma rede de Feistel de 16 iterações com tamanho de bloco de 64-bits, uma chave que pode variar entre 32 a 448-bits, e S-boxes altamente chaves-dependentes, tornando-o ideal para aplicações tanto domésticas, quanto comerciais. O Blowfish foi desenvolvido em 1993 por Bruce Schneier como uma alternativa grátis mais rápida para os algorítmos criptográficos existentes. Desde então ele vem sendo analisado de forma considerável e está conquistando a aceitação do mercado como um algoritmo forte. O Blowfish não é patenteado, tem sua licença grátis e está a disposição para todos.

O artigo original do Blowfish foi apresentado no "First Fast Software Encryption Workshop" ocorrido em Cambridge, NY, EUA. Os resultados do workshop foram publicados por Springer-Verlang, "Lecture Notes in Computer Science" #809, 1994). A edição de abril de 1994 de "Dr. Dobb's Journal" também tratou expôs a proposta de Bruce Schneier. "Blowfish -- One Year Later" foi publicada em Setembro de 1995 em outra edição de "Dr. J.R.' Bob' Dobb's Journal".

Muitos estudiosos em criptografia examinaram o Blowfish, entretanto, ainda são poucos os resultados publicados. Serge Vaudenay examinou chaves fracas no Blowfish: existe uma classe de chaves que podem ser detectadas - mas não "quebradas" - no Blowfish com variantes de 14 iterações ou menos.

Qualquer pessoa pode obter uma cópia do código-fonte do Blowfish a partir da Internet e fazer uso em suas aplicações. Não há regras de uso do código. Bruce Schneier pede, somente, que seja notificado de aplicações comerciais para que possam ser listadas em sua página na Internet.

Existem duas derivações do Blowfish:

1. Twofish: é uma cifra de blocos simétrica projetado e desenvolvido em 1998 por Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, e Niels Ferguson. O algoritmo foi um dos cinco finalistas no AES (Advanced Encryption Stantard contest), ele é composto por blocos de 128-bits de tamanho e chaves de tamanho até 256-bits, assim como seu predecessor, o Twofish possui S-boxes chaves dependentes, é composto por Redes de Feistel com uma função-F bijetora feita por quatro S-boxes de 8-bits, uma matrix de 4x4 de distância de separação máxima sobre GF(2$^{8}$) (MDS-matrix), uma pseudo-transformação de Hadamard (PHT), rotação bit a bit, e um organizador de chaves interno complexo.
2. Threefish: é também uma cifra de blocos simétrica projetado e desenvolvido em 2008 por Bruce Schneier, Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, e Jesse Walker. O algoritmo foi criado para fazer parte do "Skein Hash Function" um algoritmo competidor no "NIST hash function competition". Definido por blocos de tamanho 256, 512, e 1024-bits, com chave do tamanho do bloco, valor "tweak" de 128 bits para qualquer bloco, não possuindo nenhuma S-Box, e sim uma função simples não linear de mistura chamada MIX que opera em 2 palavras de 64-bits cada. A função MIX consiste em uma simples adição, uma rotação por uma constante, e um XOR. Threefish-256 e Threefish-512 consiste de 72 iterações, já o Threefish-1024 consiste de 80 iterações. O algoritmo consiste de apenas 3 operações em palavras de 64-bits: XOR, ADD e rotações de tamanho fixo.

Princípios do projeto

1. Manipular dados em largos blocos preferencialmente de tamanho 32 bits.
2. Possuir tanto blocos de tamanho 64 bits ou 128 bits.
3. Possuir chave escalável de 32 bits até pelo menos 256 bits.
4. Usar operações simples que são eficientes em microprocessadores: XOR, ADD, table lookup, e multiplicação modular.
5. Ser implementável em um processador 8-bit com um mínimo de 24 kilobytes de memória RAM e 1Kb de ROM.
6. Não possuir estruturas lineares que reduza a complexidade de uma busca por força bruta.
7. Bloco de tamanho 64 bits produz uma palavra de tamanho 32 bits, e mantém compatibilidade do tamanho do bloco com outros algoritmos. Além disso, Blowfish é fácil de ser escalado tanto para blocos de tamanho 128 bits ou para blocos menores.
8. Se possível, não possuir chaves fracas. Caso não seja possível, a proporção de chaves fracas deve ser suficientemente pequena evitando que alguma destas chaves seja escolhida randomicamente. Qualquer uma dessas chaves fracas devem ser conhecidas para que sejam eliminadas durante o processo de geração de chaves.
9. Fazer uso de subchaves previamente computadas. Não pré-computar chaves resultará em operações mais lentas, porém ainda será possível fazer processo de encriptação dos dados.
10. A rede de Feistel que compõem o Blowfish foi projetada para ser a mais simples possível, enquanto mantém as propriedades criptográficas desejadas para a estrutura.
11. Processo de geração de subchaves é projetado para preservar totalmente a entropia da chave e distribuir esta entropia uniformemente entre as subchaves geradas. Durante o processo, as subchaves são ligeiramente alteradas a cada novo par de subchave gerado, protegendo contra qualquer ataque contra este processo que explore subchaves fixas e conhecidas. Os dígitos de Pi foram escolhidos como tabela inicial de subchaves por dois motivos: é uma sequencia randômica de números não relacionadas com o algoritmo, e pode tanto ser guardado como parte do algoritmo ou derivado quando necessário. Os dígitos da chave são repetidamente XORados com os dígitos de Pi no array P inicial, para evitar o seguinte ataque: suponha que os bits da chave não são repetidos, porém completados com zeros para que tenham o tamanho do array P. Um atacante pode encontrar duas chaves que diferem apenas nos 64bits XORados com P1 e P2, que usando chaves iniciais conhecidas, produzem o mesmo valor encriptado, portanto, o atacante pode encontrar duas chaves que produzem as mesmas subchaves.
12. O algoritmo de geração de subchaves não assume que os bits da chave são random.
13. Função-F não depende da iteração.
14. Cada bit do dado x da "metade esquerda" (xL) é usado apenas como entrada única para uma S-Box.

Estrutura de Funcionamento

Funcionamento de uma rede de Feistel

Blowfish é uma cifra de blocos simétrica que encripta dados em blocos de tamanho 8 bytes e possui uma chave de tamanho variável entre 32 a 448 bits, com subchaves previamente computadas, cada subchave é uma hash simples da chave, não possui estruturas lineares, possui uma implementação de simples entendimento. O algoritmo faz uso da rede de Feistel de 16 iterações onde cada iteração consiste em uma permutação da chave-dependente, e uma substituição da chave-dado dependente. A rede de Feistel é uma estrutura simétrica usada na construção de cifras de blocos responsável por transformar qualquer função (normalmente denominada de função-F) em uma permutação, mapeando uma string de entrada para uma string de saída.

Antes de demonstrar o funcionamento de uma rede de Feistel, deve-se mostrar duas fortes definições:

1. Definição 1: função-F de uma rede de Feistel
   1. F: $\{0,1\}^{n/2}\times \{0,1\}^{k}\rightarrow \{0,1\}^{n/2}$, onde n é o tamanho do bloco e k a quantidade de bits da chave.
2. Definição 2: N iterações de uma rede de Feistel
   1. $X_{i+1}=(F_{ki}(msb_{n/2}(X_{i}))\oplus lsb_{n/2}(X_{i}))\;\|\;msb_{n/2}(X_{i})$ , onde $X_{i+1}$ é o output da iteração, $k_{i}$ é a chave de cada iteração, $n$ é o tamanho do bloco, $lsb_{u}(x)$ e $msb_{u}(x)$ seleciona a parte mais significativa $(msb)$ e a menos significativa $(lsb)$ de tamanho $u$ bits de $x$, $\;\|\;$ indica concatenação. Em cada iteração, $msb_{n/2}(X_{i})$ opera, via uma função-F não linear chave-dependente, sobre $lsb_{n/2}(X_{i})$.

Uma rede de Feistel funciona da seguinte maneira:

1. Seja F uma função, K as subchaves das n iterações. A encriptação será da seguinte maneira:
   1. Divida o bloco da mensagem em duas metades iguais, criando uma “metade esquerda” e uma “metade direita”. $(L_{0},R_{0})$
   2. Para cada iteração $i=0,1,2,..,n:$
      1. “metade direita” se torna nova “metade esquerda” da iteração $i+1\rightarrow L_{i+1}=R_{i}$
      2. Nova “metade direita” é calculada: $R_{i+1}=L_{i}\oplus F(R_{i},K_{i})$
2. Resultado final será: $(R_{i+1},L_{i+1})$

A desencriptação é feita:

1. Para cada iteração i=n,n-1,n-2,...,0:
   1. $R_{i}=L_{i+1}$
   2. $L_{i}=R_{i+1}\oplus F(L_{i+1},K_{i})$
2. Resultado final será: $(L_{0},R_{0})$

Funcionamento do Algoritmo

O algoritmo consiste de duas partes: expansão de chaves e encriptação dos dados. Expansão de chaves converte uma chave de até 448 bits em vários arrays de subchaves totalizando 4168 bytes. Encriptação ocorre via 16 iterações da rede de Feistel, cada iteração consiste de uma permutação da chave dependente, e uma substituição de chave-dado dependente. Todas as opraçoes são XORs e ADD em palavras de 32 bits. Cada S-box aceita um input de 8-bits e o funcionamento das quatro resulta em um output de 32-bits.

Apesar do complexo algoritmo de inicialização, o Blowfish tem grande eficiência com os microprocessadores atuais. A fim de aumentar sua eficiência, foi escolhido usar na confecção deste algoritmo funções simples para os microprocessadores, tais como XOR, adição e multiplicação modular.

Sub-chaves

Blowfish faz uso de um grande número de subchaves. Estas subchaves devem ser pre-computadorizadas antes de qualquer encriptação ou desencriptação.

1. O P-array consiste de 18 subchaves de 32 bits: P1,P2,...,P18;
2. Existem quatro S-box de 32 bits com 256 entradas cada:
   1. $S_{1}:$ 0,1,2,...,255;
   2. $S_{2}:$ 0,1,2,...,255;
   3. $S_{3}:$ 0,1,2,...,255;
   4. $S_{4}:$ 0,1,2,...,255;

Criação das sub-chaves

1. Inicialize primeiro o P-array e as quatro S-boxes, em ordem, com uma string fixa, que consiste nos dígitos de Pi em hexadecimal, com exceção do inicial 3.
   1. P1 = 0x243f6a88; P2 = 0x85a308d3; P3 = 0x13198a2e; P4 = 0x03707344, etc;
2. P1 XOR primeiros 32 bits da chave, P2 XOR próximos 32 bits da chave, e assim por diante, até o término dos bits da chave. Percorra repetidamente os bits da chave até que todos os P-array tenham sido XORados com os bits da chave.
3. Encripte todas as strings totalmente zeradas com o algoritmo do Blowfish, using as subchaves descritas nos passos (1) e (2).
4. Substitua P1 e P2 da saída do passo (3).
5. Encripte a saída do passo (3) usando o algoritmo do Blowfish com as subchaves modificadas.
6. Substitua P3 e P4 da saída do passo (5)
7. Continue o processo, substituindo todas as entradas do P-array, até que todas as S-boxes estejam totalmente preenchidas, de acordo com as saídas das mudanças do próprio algoritmo Blowfish.

No total, serão feitas 521 iterações apenas para gerar as sub-chaves. A fim de tornar a utilização do algoritmo mais simples, é sugerido que os aplicativos guardem essas sub-chaves geradas, ao invés de fazer esse complexo processo múltiplas vezes.

Cifragem

"Algoritmo para encriptação, input x = (plaintext de 64-bits):

1. Divida x em duas metades de 32-bits cada: $xL,xR;$
2. Para $i=1$ até $16:$
   1. $xL=xL\oplus P_{i};$
   2. $xR=F(xL)\oplus xR;$
   3. Swap $xL$ com $xR;$
3. Swap $xL$ com $xR$ (desfazendo a última troca);
4. $xR=xR\oplus P17;$
5. $xL=xL\oplus P18;$
6. Recombine $xL$ com $xR$;

O texto cifrado será a união desses dois grupos (xL xR).

Para encriptação/desencriptação, a função F divide o input de 32-bits em 4 pedaços de 8-bits que serão usados como entrada nas S-boxes:

1. Divida xL em quatro pedaços de 8-bits cada: a, b, c, d;
2. $F(xL)=((S_{1}[a]+S_{2}[b]{\pmod {2^{32}}})\oplus S_{3}[c])+S_{4}[d]{\pmod {2^{32}}}$

O processo de obtenção do texto original a partir do cifrado é feito da mesma forma, porém utilizando a matriz P em ordem inversa."

Exemplo de uso

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.util.Arrays;
import javax.crypto.Cipher;
import javax.crypto.CipherOutputStream;
import javax.crypto.KeyGenerator;
import javax.crypto.SecretKey;
import javax.crypto.spec.SecretKeySpec;

public final class BlowfishTester {

    public static void main(String[] args) throws Exception {


        String text = "Testando o algoritmo blowfish";

        KeyGenerator KG = KeyGenerator.getInstance("Blowfish");
        KG.init(128);
        SecretKey SK = KG.generateKey();

        SecretKeySpec key = new SecretKeySpec(SK.getEncoded(), "Blowfish");
        Cipher cipher = Cipher.getInstance("Blowfish");

        cipher.init(Cipher.ENCRYPT_MODE, key);

        byte[] encrypted = cipher.doFinal(text.getBytes());
        String encryptedString = bytesToHex(encrypted);
        System.out.println("Encryptado -> Hexadecimal: " + encryptedString);
        System.out.print("Resultado da encriptaçao: ");
        System.out.println(new String(encrypted, "UTF8"));

        cipher.init(Cipher.DECRYPT_MODE, key);
        byte[] decrypted = cipher.doFinal(encrypted);
        System.out.println("Texto decifrado: " + new String(decrypted, "UTF8"));

        cipher.init(Cipher.ENCRYPT_MODE, key);
        //Cifrando uma imagem qualquer.
        FileInputStream fin = new FileInputStream("Blowfish/BlowFish_Algorithm.png");
        FileOutputStream fout = new FileOutputStream("Blowfish/imagemCriptografada.png");
        CipherOutputStream cout = new CipherOutputStream(fout, cipher);

        int input = 0;
        while ((input = fin.read()) != -1) {
            cout.write(input);
        }

        //Decifrando a imagem
        cipher.init(Cipher.DECRYPT_MODE, key);

        fin = new FileInputStream("Blowfish/imagemCriptografada.png");
        fout = new FileOutputStream("Blowfish/imagemDecrip.png");
        cout = new CipherOutputStream(fout, cipher);

        while ((input = fin.read()) != -1) {
            cout.write(input);
        }
        fin.close();
        cout.close();
    }

    public static String bytesToHex(byte[] data) {
        if (data == null) {
            return null;
        } else {
            int len = data.length;
            String str = "";
            for (int i = 0; i < len; i++) {
                if ((data[i] & 0xFF) < 16) {
                    str = str + "0" + java.lang.Integer.toHexString(data[i] & 0xFF);
                } else {
                    str = str + java.lang.Integer.toHexString(data[i] & 0xFF);
                }
            }
            return str.toUpperCase();
        }
    }
}

Conclusão

Blowfish é uma das cifras mais rápidas em uso, exceto ao mudar chaves. Cada chave nova requer o pre-processamento equivalente a encriptação de aproximadamente 4 kilobytes do texto, o que é muito lento se comparado a outras cifras. Isto impede seu uso em determinadas aplicações, mas não é um problema em outras. Em algumas aplicações é realmente um benefício: o método da troca de senha usado em OpenBSD usa um algoritmo derivado de Blowfish que emprega a programação de chave lenta; a ideia é que o esforço computacional extra requerido dá a proteção de encontro aos ataques de dicionário. Em algumas execuções, Blowfish tem uma exigência relativamente grande da memória (acima de 4 kilobytes). Este não é um problema mesmo para computadores menores e mais velhos ou laptops, mas impede o uso em sistemas menores tais como smartcards. Alguns exemplos que fazem uso do Blowfish:

Gerenciamento de senhas:

1. Password Wallet

Segurança de banco de dados:

1. SQL Server 2000 Encryption

Serviços de e-commerce:

1. Avactis Shopping Cart

Bibliotecas que implementam o algoritmo:

1. Crypto++
2. Java Cryptography Architecture
3. Pccipher

Sistemas Operacionais:

1. Linux
2. OpenBSD

Ligações externas

• Official Blowfish website (em inglês)