Introdução a criptografia

Uma introdução informal sobre esta área tão complexa e misteriosa.

O assunto é meio delicado, pois sempre haverá maneiras diferentes, profundas e “mais corretas” de se explicar a mesma coisa. Esta série de artigos é um compilado de anotações resultado de várias leituras e respostas a indagações deste que vos escreve. Não sou autoridade no assunto, portanto, estou sujeito a erros.

A criptografia surgiu séculos atrás, e tinha como único objetivo proteger o conteúdo de mensagens trocadas. Hoje, a criptografia moderna vai mais além, e tem como premissa não apenas a garantia da confidencialidade dos dados, mas também garantir a integridade e a autenticidade dos mesmos, que, por sinal, são considerados um dos pilares da Segurança da Informação (além destes pilares, temos a disponibilidade, que não pode ser garantida pela criptografia).

Figura 1: Pilares da segurança da informação. Fonte: debsolutionsti.com

Basicamente, um sistema para ser considerado seguro precisa satisfazer estes pilares. E para garantir a confidencialidade e a integridade, é bem provável que a criptografia será utilizada.

Uma curiosidade: no mundo da TA (Tecnologia da Automação) a disponibilidade tem maior prioridade que na TI.

A criptografia é implementada por meio dos chamados “algoritmos criptográficos”. Estes algoritmos definem quais serão os procedimentos para se manipular os bits do dado original.

Para criptografar um dado, além de ser necessário o uso de um determinado algoritmo de criptografia (existem vários), é necessário utilizar a chamada “chave criptográfica”. Em criptografia, uma chave é uma sequência de bits de quantidade fixa utilizada para “alimentar” o algoritmo de criptografia, com o objetivo de orientá-lo em seu processo de encriptação/decriptação. Sem a chave não é possível descriptografar ou criptografar o dado.

O termo “chave” é uma referência ao conceito de chave do mundo real, onde teoricamente a chave seria um instrumento único capaz de trancar ou destrancar uma fechadura.

Figura 2: Encaixe da chave correta em uma fechadura.

Perceba que a chave preenche precisamente as lacunas de dentro de uma fechadura, permitindo que seja girado o cilindro para o bloqueio ou desbloqueio da fechadura. Caso seja inserido uma chave incorreta, as lacunas do cilindro da fechadura não serão corretamente preenchidas e, portanto, não será possível torcer a chave. A mesma ideia se aplica a criptografia.

Exemplo didático de uso de chave criptográfica

A lógica de boole é formada pelos conetivos AND, OR, XOR e NOT. O XOR é uma versão diferente do OR em um sentido: 1 ⊕ 1 = 0.

OBS: o símbolo ⊕ é a representação do XOR.

Existe uma propriedade interessante do XOR que nos permite ver na prática os princípios da criptografia moderna: a capacidade de reverter uma sequência de bits a seu estado original antes de sofrer um xor.

Vamos a um exemplo:

O caractere “K” em binário corresponde a sequência 01001011.

Vamos criptografar este caractere utilizando xor com a chave 10101010:

Figura 3: Operação XOR entre byte original e chave.

Com isto, o caractere K se transforma em uma sequência de bits sem representação gráfica (11100001).

Para reverter a sequência 11100001 para seu estado original, basta aplicar um xor com a chave 10101010:

Figura 4: Fazendo o procedimento reverso com o byte criptografado.

Se quiséssemos criptografar uma string seguindo esta lógica, basta repetir a chave várias vezes acompanhando a quantidade de caracteres da string.

Fazendo este processo com os bits dos caracteres da string “King”, utilizando a chave 00001111, teremos: Dfah.

Se um atacante interceptar a mensagem “Dfah” será muito difícil (mas não impossível) de reverter a string criptografada para seu estado original. Pois ele terá que descobrir a chave 00001111 antes.

Os algoritmos criptográficos podem ser classificados de diversas formas (cifras de bloco, de fluxo, de substituição, de permutação, e etc). No geral, podemos classificá-los em dois tipos:

  • Algoritmos de criptografia de chave simétrica;
  • Algoritmos de criptografia de chave assimétrica;

Modelo simétrico

A “simetria” aplicada ao uso da chave neste tipo de algoritmo, significa que a chave utilizada para criptografar um dado é a mesma utilizada para descriptografá-lo. Em um primeiro momento isto pode parecer ser óbvio, ainda mais fazendo a analogia com uma fechadura, mas veremos que é justamente neste quesito que os algoritmos de chave assimétrica se diferenciam.

Existem vários tipos de algoritmos criptográficos de chave simétrica. Segue uma lista citando alguns:

  • AES (aes128, aes192, aes256)
  • BLOWFISH
  • CAMELLIA
  • DES
  • 3DES
  • IDEA
  • MARS
  • RC4
  • RC6
  • SEED
  • SERPENT
  • TWOFISH

Cada um possui suas vantagens e desvantagens que podem ser definidas de acordo com características como: tamanho de chave suportado, tempo de encriptação/decriptação (complexidade algorítmica), memória utilizada, possibilidade de implementação tanto em hardware quanto em software, copyright, confiança nos mecanismos internos do algoritmo (garantia de que não há trapdoors), e outros.

Como dito anteriormente, uma chave é dada na forma de uma sequência de bits de quantidade fixa. A quantidade de bits que compõe uma chave é pré-determinada pelo algoritmo. Um determinado algoritmo de criptografia não trabalhará com tamanhos arbitrários de chave, por exemplo: o DES não trabalhará com chaves ora de 40 bits, ora 37 bits. Por padrão ele trabalha somente com chaves compostas por sequências de 56 bits.

Uma cifra pode ser constituída por vários “sub-algoritmos”. Como exemplo, o Data Encryption Standard, DES, dentre outros componentes, é constituído pelo encadeamento de vários algoritmos de substituição (chamados de S-BOX) e de permutação (chamados de P-BOX):

Figura 5: descrição parcial dos componentes do DES. As caixinhas amarelinhas “S1”, “S2", “Sn” …“S8", representam os algoritmos de Substituição de bits. O retângulo verde, P, representa um algoritmo de Permutação, ou seja, o algoritmo que irá bagunçar a posição dos bits. Fonte: wikipedia.org

Engana-se quem acredita que estes mecanismos internos dos principais algoritmos de criptografia devam ser secretos, alimentando a ideia da chamada “segurança por obscuridade”. Pelo contrário, de acordo o princípio do criptógrafo Auguste Kerckhoff, é dito que:

Todos os algoritmos devem ser públicos; apenas as chaves são secretas.

Um dos critérios para a garantia da segurança de um algoritmo criptográfico, além da segurança em saber que se trata de um algoritmo público, testado e auditado por vários especialistas, está no tamanho da chave que ele suporta.

Segurança da chave

Como a chave é dada em bits, em um primeiro momento, toda a segurança estará relacionada com o tamanho dela, dada pela quantidade máxima de bits.

Vamos supor, que tenhamos um algoritmo hipotético que trabalhe com chaves de 8 bits. Agora, imagine que um arquivo criptografado por este algoritmo foi interceptado por um atacante.

Uma das possibilidades para adquirir a chave, pode ser utilizando a técnica de força bruta. A força bruta é uma técnica antiga utilizada na computação por algoritmos que desejam chegar a um objetivo por tentativa e erro. Adaptando esta técnica para a nossa situação, o atacante poderia ir gerando todas as possibilidades de chaves e testar uma a uma, por tentativa e erro, até gerar a chave correta que consiga descriptografar o arquivo.

De acordo com a análise combinatória, se temos 8 casas de algarismos que variam somente duas vezes (0 ou 1), podemos representar o número máximo de possibilidades de chaves com 8 bits da seguinte forma:

2x2x2x2x2x2x2x2 = 2⁸ = 256 posibilidades diferentes de chaves.

Isto daria uma faixa de 00000000, 00000001, 00000010, 00000011, … até 11111111.

Só para termos uma ideia do quão rápido os processadores atuais podem calcular 256 valores diferentes, vejamos este teste:

$ time seq 0 255 > /dev/null
real 0m0.002s
user 0m0.000s
sys 0m0.000s

Como vimos, em apenas 0.002 segundos um loop do comando “seq” gerou valores de 0 á 255. Isto quer dizer que em menos de 1 segundo o hacker conseguiria “quebrar” a segurança do arquivo criptografado.

Agora, imagine que nosso algoritmo trabalhe com chaves de 32 bits. Chaves de 32 bits nos permitem trabalhar com 4.294.967.296 chaves diferentes, pois 2³² é igual a este valor.

Realizando novamente o teste, onde criaremos um loop de 0 á 4.294.967.295, teremos:

$ time seq 0 4294967295 > /dev/null
real 2m1.473s
user 1m58.840s
sys 0m2.476s

Foram gastos pouco mais de 2 minutos para a execução do loop completo. Durante este tempo, o processo do comando ‘seq’ ocupou muito tempo de CPU:

Figura 5: Processo do comando seq no topo dos processos que mais utilizaram a CPU no momento do print.

Logo, a conclusão que podemos chegar, é que o tamanho da chave é crucial na inviabilização do processo de quebra por força bruta. Onde quanto maior for a chave, maior as possibilidades de chaves a serem testadas, e maior será o custo computacional para o processo de quebra.

Dos algoritmos de chave simétrica citados na lista anterior, o que utiliza a menor chave é o DES, com chaves de 56 bits. O número de possibilidades de chaves distintas são tão grandes nos algoritmos atuais que devem ser representados por notação científica, no caso, 56 bits nos proporciona 2⁵⁶ = 7.2057594 x 10¹⁶ chaves diferentes (ou 72.057.594.037.927.936 possibilidades).

Em uma tentativa de reproduzir o teste com o comando seq:

$ time seq 0 72057594037927935 > /dev/null
^C
real 78m12.455s
user 74m5.152s
sys 3m42.194s

... desisti 1 hora e 18 minutos depois.

OBS: o DES é reconhecido como um algoritmo inseguro! Usei-o como exemplo apenas por razões didáticas.

“Senhas frase” como chaves

Muitas implementações de algoritmos de chave simétrica representam as chaves por meio de caracteres alpha-numéricos presentes na grande maioria das tabelas de codificação de caracteres (como ASCII e UTF-8).

Isto permite uma maior comodidade para o usuário. Com isto, o usuário poderá memorizar uma chave criptográfica. Por exemplo: o DES trabalha com chaves de 56 bits, isto permitirá criar passphrases de 7 caracteres. Desta forma, uma aplicação poderá aceitar a string “S4turn0” como chave.

Quando você adiciona uma senha na comprensão de arquivos com zip, a senha é utilizada como chave para a encriptação dos arquivos. Em redes Wifi com autenticação PSK, a senha utilizada na associação/autenticação em access points é utilizada também como parte da chave usada para encriptar/decriptar os pacotes transmitidos e recebidos.

Para termos uma ideia da quantidade de senhas diferentes que podem ser utilizadas como chaves para o DES, tendo como premissa a utilização de algum dos 95 caracteres “renderizáveis” da tabela ASCII somada ao limite de 7 caracteres como tamanho máximo de senha (pois 56 / 8 é igual a 7), podemos calcular algo como:

95x95x95x95x95x95x95 = 95⁷ = 6.983373x10¹³ (ou 69.833.729.609.375) posibilidades diferentes de chaves.

Mesmo sendo um subconjunto menor, ainda sim é muita coisa!

Por ter quantidade finita de possibilidades de senhas, teoricamente, qualquer algoritmo é passível de “quebra” por força bruta. O problema é justamente no tempo decorrido para que essa quebra possa ser efetivada, em razão da limitação dos processadores atuais.

Poderíamos sugerir que, para aumentar a segurança dos nossos algoritmos só precisamos trabalhar com chaves maiores, como por exemplo, chaves de 16.384 bits (chutei esse valor). A princípio seria uma boa ideia, mas isto impactaria muito na performance (não podemos esquecer que a criptografia tem que ser acessível a todos os equipamentos, isto inclui dispositivos embarcados e mobile) e também de nada adiantaria trabalhar com chaves maiores se elas forem facilmente quebráveis por serem de baixa entropia.

[Artigo em edição. Em breve parte 1 completa]

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.