Duro de quebrar
Paulo Barreto, criptógrafo da empresa brasileira Scopus, ganhou destaque recentemente por ter assessorado a equipe belga que desenvolveu o algoritmo Rijndael, aprovado pelo governo americano como o novo Padrão Avançado de Criptografia (AES). Agora, três novos algoritmos desenvolvidos por Paulo e por um dos pesquisadores belgas estão sendo avaliados na Europa, e têm grandes chances de se tornarem padrões do outro lado do Atlântico também. Leon Achjian Jr. é gerente da área de Segurança Lógica da Scopus. Eles conversaram com a RdL e contaram alguns detalhes da bateria mundial de ataques para tentar quebrar o algoritmo.

RdL - Como foi que vocês se envolveram no projeto?

Leon Achjian Jr. - Há vários anos, nós desenvolvemos uma série de projetos para clientes que necessitavam de sistemas de criptografia forte, numa época em que os Estados Unidos impunham restrições para a exportação desse tipo de produto. Também não nos bastaria usar produtos fechados de terceiros, pois não poderíamos usá-los com confiabilidade absoluta.

Paulo Barreto - Alguns anos atrás, enquanto procurava algoritmos criptográficos eficientes na literatura científica pertinente, encontrei os trabalhos desenvolvidos por dois engenheiros belgas, Joan Daemen e Vincent Rijmen1, e imediatamente entrei em contato com eles. Devido às dificuldades em programação e otimização de código que eles estavam enfrentando, ofereci nossa estrutura para tocar o projeto adiante e constituímos informalmente um time. Na época, meus conhecimentos de criptografia eram bastante limitados, mas pude contar com todo o apoio (e a paciência) dos nossos amigos belgas para ganhar intimidade com o assunto. Era natural que eu me tornasse voluntário para auxiliá-los em 1997 quando o governo americano publicou uma solicitação, dirigida a todos os criptógrafos do mundo, para que apresentassem propostas de um novo algoritmo criptográfico a ser utilizado como padrão nos EUA durante o século XXI, em substituição ao hoje obsoleto DES (Data Encryption Standard). Quinze algoritmos foram apresentados em 1998 e reduzidos a cinco finalistas em 1999; finalmente, em 2 de outubro de 2000, o algoritmo Rijndael foi escolhido para ser o AES (Advanced Encryption Standard). É interessante notar que esses algoritmos foram submetidos ao crivo de todos os especialistas em criptoanálise do planeta; a escolha do Rijndael reflete um dos métodos criptográficos mais seguros e eficientes que já foram desenvolvidos.

RdL - Mas o algoritmo já estava pronto? Vocês entraram apenas com os bits?

PB - O algoritmo Rijndael é o sucessor de outro algoritmo criptográfico chamado Square, cujo desenvolvimento também acompanhamos desde o início. O Square era um modelo eficiente, mas que não havia sido testado e nem aperfeiçoado; durante as fases preliminares de elaboração, descobrimos nele uma pequena vulnerabilidade estrutural, devidamente corrigida antes de ser atingida a forma final. O Rijndael aprimora esse modelo, tornando-o mais flexível. Continuamos a sintonia fina na implementação do algoritmo mesmo depois que ele foi oficialmente apresentado como candidato ao AES, e sempre descobríamos algo para aumentar sua eficiência. Os parâmetros solicitados pelo governo americano (cifração em blocos de dados de 128 bits com chaves de 128, 192 ou 256 bits) impossibilitam qua quer tentativa de ataque por força bruta, e nossos estudos preliminares já indicavam uma resistência fora do comum do Rijndael a métodos mais requintados de ataque, denominados criptoanálise diferencial e linear. A avaliação do algoritmo por outros pesquisadores - até mesmo por autores de algoritmos rivais, isto é, de outros candidatos ao AES, e portanto fundamentalmente interessados em quebrá-lo - só fizeram aumentar a confiança no Rijndael, pois estão muito longe de representar uma ameaça à sua integridade lógica2. E é claro, toda a experiência adquirida nesse processo serviu de base para nossa participação atual no projeto Nessie, o equivalente europeu do processo do AES, porém mais abrang nte.

RdL - A área de segurança, comumente associada às empresas tradicionais, como a Brinks e a Thomas de La Rue, com seus carros blindados, homens fardados, matrizes sofisticadíssimas, parecem hoje fotos desbotadas de um passado muito distante diante da novidade da Internet e do comércio eletrônico. Como vocês vêem essa mudança?

LA - A Internet e o comércio eletrônico criaram uma nova cultura de segurança como a preocupação com confidencialidade, integridade, não repúdio e autenticidade das informações trocadas. Essas preocupações geraram demanda por novas ferramentas tais como criptografia, certificação e assinaturas digitais e VPNs, que se tornaram discussões obrigatórias e entraram na ordem do dia. Devemos observar que a segurança física continua tendo seu lugar, estando presente e complementando as políticas de segurança da informação de empresas e corporações.

PB - Gostaria de lembrar os recentes ataques DDOS (Distributed Denial Of Service), em que sites com uma política de segurança eficiente não tinham como deter a sobredemanda de pedidos de conexão, e que, embora fossem ataques baseados em força bruta, não podiam ser bloqueados por firewalls ou equipamentos de detecção de intrusão, pois eram baseados em padrões normais de acessos.

1 O Vincent, assim como o Paulo, é um linuxer contumaz.
2 Para se ter uma idéia, o melhor ataque conhecido só funciona contra uma versão simplificada do Rijndael (algo como parar o processo de cifração no meio do caminho), e mesmo assim exige que o adversário do sistema convença o dono da chave a criptografar 99,8% de todas as mensagens possíveis, além de acarretar um esforço de computação adicional quase tão grande quanto testar exaustivamente todas as chaves. Em resumo, é um ataque de interesse acadêmico, e na prática só reforça a solidez estrutural do Rijndael.

Para saber mais

Scopus Tecnologia S.A. - www.scopus.com.br
Site oficial do governo americano dedicado ao AES - www.nist.gov/aes
Página do Rijndael - www.esat.kuleuven.ac.be/~rijmen/rijndael
Site oficial do projeto Nessie, da União Européia - www.cryptonessie.org
Informações adicionais sobre o AES - www.cryptix.org/news/02102000.html

-----Source file: rijndaelref.c-----

/***************************************************************************
    module:     rijndaelref.c   (v. 1.0)
    author:     Paulo S. L. M. Barreto <pbarreto@iname.com>
    comments:   set tabstop=4 to correctly visualize the indentation.
 ***************************************************************************/

/***************************************************************************
*    This program is free software; you can redistribute it and/or modify  *
*    it under the terms of the GNU General Public License as published by  *
*    the Free Software Foundation; either version 2 of the License, or     *
*    at your option) any later version.                                   *
***************************************************************************/

#include <stdio.h>

typedef unsigned char   byte;
typedef unsigned int    uint;

#define MAXKB (256/8) /* maximum key size in bytes */
#define MAXNR (MAXKB/4 + 6) /* maximum # rounds */
#define MAXKS (4*(MAXNR + 1)) /* maximum # words needed by the key schedule
*/

static const byte Sbox[256] = {
 99, 124, 119, 123, 242, 107, 111, 197,  48,   1, 103,  43, 254, 215, 171, 118,
202, 130, 201, 125, 250,  89,  71, 240, 173, 212, 162, 175, 156, 164, 114, 192,
183, 253, 147,  38,  54,  63, 247, 204,  52, 165, 229, 241, 113, 216,  49,  21,
  4, 199,  35, 195,  24, 150,   5, 154,   7,  18, 128, 226, 235,  39, 178, 117,
  9, 131,  44,  26,  27, 110,  90, 160,  82,  59, 214, 179,  41, 227,  47, 132,
 83, 209,   0, 237,  32, 252, 177,  91, 106, 203, 190,  57,  74,  76,  88, 207,
208, 239, 170, 251,  67,  77,  51, 133,  69, 249,   2, 127,  80,  60, 159, 168,
 81, 163,  64, 143, 146, 157,  56, 245, 188, 182, 218,  33,  16, 255, 243, 210,
205,  12,  19, 236,  95, 151,  68,  23, 196, 167, 126,  61, 100,  93,  25, 115,
 96, 129,  79, 220,  34,  42, 144, 136,  70, 238, 184,  20, 222,  94,  11, 219,
224,  50,  58,  10,  73,   6,  36,  92, 194, 211, 172,  98, 145, 149, 228, 121,
231, 200,  55, 109, 141, 213,  78, 169, 108,  86, 244, 234, 101, 122, 174,   8,
186, 120,  37,  46,  28, 166, 180, 198, 232, 221, 116,  31,  75, 189, 139, 138,
112,  62, 181, 102,  72,   3, 246,  14,  97,  53,  87, 185, 134, 193,  29, 158,
225, 248, 152,  17, 105, 217, 142, 148, 155,  30, 135, 233, 206,  85,  40, 223,
140, 161, 137,  13, 191, 230,  66, 104,  65, 153,  45,  15, 176,  84, 187,  22,
};

static const byte Ibox[256] = {
 82,   9, 106, 213,  48,  54, 165,  56, 191,  64, 163, 158, 129, 243, 215, 251,
124, 227,  57, 130, 155,  47, 255, 135,  52, 142,  67,  68, 196, 222, 233, 203,
 84, 123, 148,  50, 166, 194,  35,  61, 238,  76, 149,  11,  66, 250, 195,  78,
  8,  46, 161, 102,  40, 217,  36, 178, 118,  91, 162,  73, 109, 139, 209,  37,
114, 248, 246, 100, 134, 104, 152,  22, 212, 164,  92, 204,  93, 101, 182, 146,
108, 112,  72,  80, 253, 237, 185, 218,  94,  21,  70,  87, 167, 141, 157, 132,
144, 216, 171,   0, 140, 188, 211,  10, 247, 228,  88,   5, 184, 179,  69,   6,
208,  44,  30, 143, 202,  63,  15,   2, 193, 175, 189,   3,   1,  19, 138, 107,
 58, 145,  17,  65,  79, 103, 220, 234, 151, 242, 207, 206, 240, 180, 230, 115,
150, 172, 116,  34, 231, 173,  53, 133, 226, 249,  55, 232,  28, 117, 223, 110,
 71, 241,  26, 113,  29,  41, 197, 137, 111, 183,  98,  14, 170,  24, 190,  27,
252,  86,  62,  75, 198, 210, 121,  32, 154, 219, 192, 254, 120, 205,  90, 244,
 31, 221, 168,  51, 136,   7, 199,  49, 177,  18,  16,  89,  39, 128, 236,  95,
 96,  81, 127, 169,  25, 181,  74,  13,  45, 229, 122, 159, 147, 201, 156, 239,
160, 224,  59,  77, 174,  42, 245, 176, 200, 235, 187,  60, 131,  83, 153,  97,
 23,  43,   4, 126, 186, 119, 214,  38, 225, 105,  20,  99,  85,  33,  12, 125,
};