Hardware Criptográfico, uma solução nacional
Condensado do texto apresentado no XXII Congresso Brasileiro de Informática,
promovido pela SUCESU no ano de 1989.
O texto original recebeu Mensão Honrosa no IV Prêmio Nacional de Informática,
promovido pela SEI, Modata e Fundação Roberto Marinho
e pode ser encontrado nos anais do Congresso.
Sinopse Os Autores
Início do Texto Testes de Validação
Bibliografia deste Artigo Bibliografia sobre TN
Home Page do Amílcar
Salve esta página para poder lê-la off-line
Propõem-se uma solução para a proteção de sistemas computacionais através de criptografia via hardware, totalmente desenvolvido no Brasil, denominado Chave KD*.
Comenta-se o método de projeto e apresenta-se os seus teste de validação realizados de maneira a permitir sua comparação ao sistema padrão americano DES.
* - atualmente a Chave KD incorpora o Sistema KD
de segurança de dados em micro-computadores,
produzido pela empresa TD Tecnologia Digital.
[Volta ao Índice deste Artigo]
Amílcar Brunazo Filho - ( Enviar mensagem )
Engenheiro Mecânico pela Escola Politécnica da USP em 1975. Na época de apresentação do trabalho era pesquisador do Laboratorio de Sub-sistemas Integraveis da EPUSP. Atualmente é diretor da TD Tecnologia Digital, empresa especializada em segurança de dados em micro-computadores.
Daniel Kao Sun Ting - ( Enviar mensagem )
Engenheiro Mecânico pela Escola Politécnica da USP em 1973 e PHD em Engenharia Nuclear pela University of California at Berkeley em 1981. É professor no CNEN-IPEN.
O vertiginoso desenvolvimento da informática nos últimos 30 anos foi incompleto: a vulnerabilidade dos computadores, dos dados e dos programas neles contidos, ao acesso, uso e cópia não autorizados, é indubitavelmente o elo fraco no uso irrestrito da informática.
Investe-se maciçamente em desenvolvimento de computadores mais rápidos e eficientes, e em softwares mais poderosos, entretanto pouco é feito na proteção contra acesso não autorizado. Dos 70 bilhões de dolares gastos em sistemas computacionais nos EUA em 1988 ( época do texto original ), apenas 500 milhões foram dispendidos associados com a proteção de sistemas.
Mesmo instituições militares e diplomáticas carecem de métodos adequados para proteção de seus sistemas computacionais e de comunicações. Todos os meios baseados no bloqueio, tanto físico quanto lógico, do acesso ao sistema do "criminoso digital" mostram-se ineficientes.
Criptografia via hardware
Acreditamos que a solução definitiva deverá se basear na criptografia das informações/dados/programas do sistema. Transfere-se desta forma a proteção do sistema global para a proteção do sistema criptográfico. A pergunta portanto é: "Qual o sistema criptográfico mais seguro?".
O algoritmo criptográfico em sí
Forma física do algoritmo ( software ou hardware )
Não é intensão deste trabalho discorrer sobre técnicas criptográficas, as quais podem ser encontradas por ex. em [1, 2, 3]. Hoje em dia os algoritmos mais consagrados são do DES e o RSA.
Quanto a implementeção física, define-se por criptografia via hardware aquela em que o algoritmo criptográfico é processado por um ou alguns circuitos integrados (CIs) dedicados ou especialmente programados. As principais vantagens da criptografia via hardware são a velocidade e irreprodutibilidade.
A solução nacional
A necessidade de se procurar uma solução 100% brasileira para o problema da criptografia vem do simples fato de que não se pode delegar a outras nações o projeto de equipamentos destinados à nossa segurança sem corrermos o risco de vermos nosso segredo desvendado justamente pelo país fornecedor, que é o mais provável conhecedor das fraquezas do sistema e um virtual "oponente". Os CI hoje existentes do DES e do RSA tem sua exportação totalmente controlada pelo governo americano.
O projeto e fabricação de um chip nacional seria desejável, porém esbarra num problema, no momento, intransponível, pois nenhuma empresa brasileira produtora de CIs possui domínio completo de todas as fases de produção e algumas destas fases são feitas no exterior.
A solução por nós proposta sugere a utilização de CIs das diversas famílias genericamente denominadas por PLD ( Programable Logical Devices ), que podem ser programados para executarem as funções criptográficas por nós escolhidas. Estes CIs não tem sua produção controlada e o fabricante não sabe de que forma eles serão programados.
O problema que devemos, agora, resolver é como programar um circuito lógico booleano (PLD) para que execute funções matemáticas criptográficas. Neste século XX os matemáticos conseguiram formalizar a matemática a partir da Algebra Booleana [4, 5], mostrando teoricamente, que é possivel obter expressões booleanas de problemas matemáticos, como uma função criptográfica. Tivemos, então, que procurar caminhos que a partir de funções criptográficas (bijetoras) nos levassem à sua expressão booleana, afim de permitir o projeto de circuitos lógicos.
Na solução que obtivemos utilizou-se de uma abordagem aritmética não convencional que foi construida e ampliada a partir dos conceitos de Funções Pseudo-Booleanas [6] e Transformada Numérica [7]. Chegamos a um método de programação de PLD, sem similar estrangeiro conhecido, com capacidade criptográfica original. Este método permite criar um número ilimitado de algoritmos criptográficos com variáveis graus de segurança.
A abordagem aritmética que utilizamos revelou-se bastante prática, pois tornou desnecessário passagens algébricas intermediárias complexas, chegando-se diretamente a uma expressão final. Os hardwares criptográficos construidos desta forma possuem boas características com relação a velocidade e complexidade tendo, entretanto, como maior limitação o tamanho dos PLDs existentes. Por ex., não é possível programar um PLD para executar o DES, apenas porque seria necessário um chip com 64 "inputs" e 56 realimentações, e o maior comercializado hoje possui 32 inputs e 32 realimentações.
Análise estatística de validação
Baseado nesta nossa metodologia, citada acima, foram construidos protótipos que obedeceram as seguintes condições:
Hardware criptográfico acoplável a computadores tipo IBM PC de 8 bits
CIs programáveis (PLD) e programador existente no mercado brasileiro
Criptografia polialfabética e polimorfa
Velocidade compatível com transmissão "on-line"
Portabilidade e irreprodutibilidade
Escolhida a PLD adequada construiu-se uma interface para conecção à CPU e programaram-se 6 CIs diferentes. Numa primeira estimativa determinou-se a existência de 10 milhões possíveis algorítmos diferentes, para apenas um tipo de PLD escolhida. Estes PLDs programados, com seus encapsulamentos protetores serão doravante chamados de Chaves KD, e possuem as seguintes características físicas:
Dimensões: 40 x 35 x 16 mm
Velocidade de ciframento: 120.000 bauds
Velocidade de deciframento: 60.000 bauds
A velocidade é limitada pelo próprio computador usado pois a Chave KD é capaz de criptografar um byte em menos de 50 ns.
A validação de um algoritmo criptográfico pode ser feita através de métodos analíticos ou estatísticos. Neste trabalho foram feitos quatro tipos de testes estatísticos para a validação da Chave KD e, afim de permitir futuras comparações dos resultados com o sistema DES, utilizou-se como texto de entrada para criptografia mensagens sempre compostas de 64 bits. Criou-se duas mensagens padrões que foram utilizadas em todos os testes como textos originais a serem criptografados.
00111100 01001011 01011010 01101001 01111000 10000111 10010110 10100101
Para simplificar o texto a seguir designaremos a Mensagem Original por "M" e o Código Criptografado por uma Chave KD por "C".
Teste de Polialfabetismo e de Polimorfia
(para uma mesma chave e mensagem)
O teste consiste em criptografar nas 256 formas possíveis (polialfabetismo) uma mesma mensagem com uma dada chave e comparar, em cada criptografia, quantos bits em C são diferentes de M. Na tabela abaixo está apresentada a média porcentual do número de bits diferentes entre M e as 256 formas diferentes de C, para cada Chave.
Nº médio de bits diferentes entre M e C
(256 formas)
Mens. A
Mens. B
0 50,00 10,85 50,00 2,21
1 50,00 12,52 50,00 4,95
2 50,00 6,26 50,00 5,86
3 50,00 6,26 50,00 6,64
4 50,00 10,85 50,00 4,95
5 50,00 10.85 50,00 5,86
Média geral = 50,00% - Média dos desvio-padrão = 7,34%
Os resultados mostram que, em média, 50 % dos bits de M são alterados ao se efetuar uma criptografia com uma Chave KD. Este é o resultado ideal, isto é, a probabilidade de um bit de C ser 0 ou 1 é igual a um sorteio ao acaso sem vícios, o que não permite obter nenhuma informação sobre a mensagem original (M) a partir da analise do código criptografado (C).
O resultado deste teste, na realidade, não pode ser comparado àqueles do DES, que é um sistema monoalfabético (uma mesma chave e uma mesma mensagem produz sempre o mesmo código criptografado), ao contrário da Chave KD que é polialfabética (uma mesma chave e uma mesma mensagem produz até 256 códigos criptografados diferentes).
Teste de troca de um bit na mensagem
(para uma mesma chave)
Este teste consiste em, para uma mesma chave, se alterar um único bit em M, obtendo M', e comparar C e C' (o código criptografado de M'), verificando-se quantos bits se alteraram. Como M possui 64 bits é possivel se fazer 64 trocas para uma dada mensagem e chave. Apresentamos abaixo o resultado médio porcentual obtido para cada chave e mensagem.
Nº médio de bits diferentes entre C e C'
(64 alterações)
0 49,32 10,83 48,44 12,93
1 52,44 14,02 52,73 16,78
2 50,98 13,07 52,10 14,41
3 50,44 13,32 51,27 10,10
4 46,68 13,72 48,39 14,45
5 49,73 13,45 50,29 12,20
Média geral = 50,15% - Média dos desvio-padrão = 13,27%
Verifica-se que trocando um bit em M alteram-se aproximadamente, em média, 50% dos bits de C.
Este resultado mostra a resistência da criptografia com uma Chave KD a um tipo de ataque muito forte chamado por "Criptoanálise de texto conhecido", pois mostra que não é possivel descobrir uma relação entre um certo bit da mensagem original (M) e os bits do código criptografado (C).
Teste de troca de chaves
(para uma mesma mensagem)
Este teste consiste em criptografar uma mesma mensagem M com chaves diferentes e comparar os diversos códigos criptografados C entre si, determinando-se o número de bits diferentes para cada par (15 pares). A tabela abaixo apresenta a média porcentual de diferenças para cada mensagem.
Média de bits diferentes entre pares de Cs
(6 chaves, 15 pares)
média das diferenças 48,33 51,88
média dos desvios-padrão 4,32 5,42
Os três testes apresentados acima comprovam a segurança da Chave KD contra a criptoanálise estatística, isto e', aquela que e' feita pelo estudo da variação do Código Cifrado com a variação dos parâmetros envolvidos (chave, mensagem e algorítmo).
Estes testes foram conduzidos segundo um formato que permitem sua comparação com os resultados do sistema DES.
[1] - Diffie, W.
"The First Ten Years of Public-Key Cryptography", Proceedings of de IEEE, vol. 76, nº 5, pg. 560-577, Maio de 1988.