Núcleo de Computação Eletrônica
Universidade Federal do Rio de Janeiro
Segurança em Redes
Aula 4
Luiz Fernando Rust
INMETRO
Tel. (021) 2679-9072
e-mail:
[email protected]
[email protected]
11
Criptografia Convencional
• CriptoAnálise
–
–
–
–
–
Linear
Diferencial
Timming Analysis
Power Analysis
Differential Fault analysis
• IDEA
• AES
2
Criptoanálise Linear
•
•
•
Ataque de texto-limpo conhecido
H. Heys, A tutorial on Linear and Differential Cryptamalysis
Idéia básica
– Aproxima S-boxes por funções lineares (ou afins)
– Exclusive-or “soma” de bits de entrada u e bits de saída 
– Para u e  aleatórios
• probabilidade da expressão ser satisfeita é ½
– Dado uma Probabilidade Linear pL (expressão linear ser satisfeita),
define-se desvio (bias) como
• pL - 1/2
– Quanto maior o desvio ( І pL - ½ І ), melhor a aplicabilidade da
criptoanálise linear com menos textos conhecidos
– Achar expressões que tenham alta ou baixa probabilidade de serem
satisfeitas (alto desvio)
3
Codificador
• S- Boxes
4
Mapeando um S-box
• Exemplo:
– X2 X3 y1 y3 y4 = 0 ou X2 X3 =y1 y3 y4
– Aplicando os 16 possíveis valores de X e examinando os
valores de Y, verifica-se sucesso em 12 dos16 casos
• o desvio de probabilidade é 12/16 –1/2
5
Generalizando mapeamento no S-box
• Entrada (horizontal)
• Saída (vertical)
• Valor representa o desvio (número de acertos – 8) * 16
6
Aproximação linear para o codificador inteiro
• Apenas para os 3 primeiros rounds
7
Piling-UP
•
Desvio
8
Extração dos bits da chave
• Aplicando Piling-UP
– Com probabilidade 15/32 e desvio = 1/32
• Processo envolve decodificação parcial do último round
• Testar todos os valores de subchaves possíveis
• Exemplo
–
–
–
–
–
–
10000 amostras (texto claro/texto cifrado)
Fazer ou-exclusivo do texto cifrado com a subchave em teste
Resultado é aplicado na função reversa do S-box
Valor é comparado com a função linear aplicada no texto claro
Se igual incrementa o contador da subchave
Valor correto da chave é aquele que tiver maior desvio
• Desvio = І contador – 5000 І / 10000
9
Chave do exemplo anterior
10
Criptoanálise Diferencial
• Desenvolvida em 1990 por Eli Biham e Adi Shamir
• Ataque de texto limpo escolhido
• Compara o comportamento do texto cifrado para blocos
com diferenças pré-determinadas
• Analisa as diferenças no processamento das Sboxes do
último round de forma a determinar a chave utilizada nesse
round
• Os bits restantes da chave (8) podem ser obtidos por força
bruta
11
Round no DES (função F)
• Propriedades importantes
12
Princípios
•
No projeto das S-boxes existiu a preocupação de garantir que é
produzida uma saída aleatória face a uma entrada aleatória
•
Porém, a diferença dos resultados de uma S-box para pares de
entradas com uma diferença determinada não é mais aleatória
•
Exemplo para S-1
– Frequência da diferença dos resultados nos pares de entrada com
diferença 01 (64 possíveis pares)
– comportamento está longe de ser aleatório
– muitas das possibilidades de resultado estão excluidas (0,1,2,4,8)
– maior probabilidade de ocorrer certos resultados
13
Tabela de distribuição de S1 - Probabilidade de saída
14
Exemplo
• Pode-se determinar também as entradas e as saídas
– Exemplo: Diferença de entrada = 34
15
Como achar K?
•
•
•
Dado S1E = 1 e S1E* = 35
Pela tabela verificamos que existem 8 formas de mapear 34 com D
Pela construção da tabela determinamos que K X tem de ser
– 06, 10, 16, 1C, 22, 24, 28, 32.
16
Como achar K?
•
•
•
Repetindo o mesmo raciocínio para S1E = 21 e S1E* = 15
Pela tabela verificamos que existem 6 formas de mapear 34 com 3
Pela construção da tabela determinamos que K X tem de ser
– 01, 02, 15, 21, 35, 36
•
Chave (K)
– Determinada pela intersecção dos conjuntos de possibilidades
– 17 ou 23
17
Ataque n-rounds
•
A cripto-análise diferencial baseia-se no conhecimento das
diferenças na entrada/saída das S-boxes...
•
As diferenças nas entradas da S-box do último round são
diretamente calculadas dos criptogramas disponíveis
•
Já as diferenças na saída terão de ser calculadas com base em
estimativas
•
Motivo pelo qual a viabilidade da criptoanálise diferencial é
fortemente influenciada pelo número de rounds
•
...para 3 rounds é possível conduzir uma análise determinística
•
Para mais do que isso é necessário uma abordagem probabilística
que aumenta muito o número de pares texto limpo/criptograma a
analisar e complica substancialmente o ataque
18
Ataque n-rounds
• Gerar características diferenciais até o penúltimo round
• Fazer decodificação parcial do último round
– Testar todos os valores de subchaves possíveis
• Exemplo
– Tabela de distribuição do codificador do tutorial de H. Heys, (A tutorial
on Linear and Differential Cryptamalysis(
19
Características Diferenciais
• Usando
20
Extração dos bits da chave
•
Conactenando S-boxes
– Com probabilidade
•
•
•
Processo envolve decodificação parcial do último round
Testar todos os valores de subchaves possíveis
Exemplo
–
–
–
–
5000 amostras (texto claro/texto cifrado)
Fazer ou-exclusivo do par de textos cifrados com a subchave em teste
Resultado é aplicado na função reversa do S-box
Valor é comparado com as diferenças obtidas para cada par de textos
claros correspondente
– Se igual incrementa o contador da subchave
– Valor correto da chave é aquele que tiver maior valor no contador
• prob = contador / 5000
21
Chave do exemplo anterior
22
Resumo de resultados da Criptoanálise diferencial
23
Outras Técnicas de Criptoanálise
• Muitas técnicas de cripto-análise não atacam diretamente o
algoritmo criptográfico mas procuram retirar informação do
“ambiente” onde este é executado
– Power analysis
– Timming analysis
– Differential fault analysis
• Estas técnicas não são, de forma alguma, específicas do
DES
• Algumas são até particularmente adequadas para atacar
cifras assimétricas
24
Timming Analysis
• Analisa tempos de execução das operações criptográficas
de forma a retirar informação sobre os parâmetros do
algoritmo
– Particularmente efetiva para algoritmos assimétricos, onde as
operações são fortemente dependentes dos dados (e.g.
Exponenciação modular)
– Cuidados especiais nas implementações dificultam ataques
(e.g. dummy code; randomized delays; etc.)
25
Power Analysis
• Retira informação dos
parâmetros dos
algoritmos por análise
do consumo de
energia
– Execuções
condicionais
– Escalonamento das
chaves
– Permutações
Divergência do relógio no ciclo 6
indica execução condicional...
26
Differential Fault analysis
• Comparam a execução do algoritmo com uma onde são
induzidos erros na sua execução
–
–
–
–
Induz-se um erro num dos bits do último round
Por analise diferencial, determina-se chave do round
Restantes bits por força bruta...
Vocacionada para atacar dispositivos “tamper proof” (e.g.
Smartcards)
27
International Data Encryption Algorithm (IDEA)
•
Criado em 1991 por James Massey e Xuejia Lai
•
Possui patente da suíça ASCOM Systec
•
Estruturado seguindo as mesmas linhas gerais do DES
– também é um cifrador de bloco iterativo, com um bloco de
tamanho igual a 64 bits e um tamanho de chave de 128 bits
– Possui apenas 8 iterações (DES possui 16)
– Cada iteração IDEA funciona como se fosse uma dupla
iteração DES
•
Na maioria dos microprocessadores, uma implementação por
software do IDEA é mais rápida do que uma implementação por
software do DES
•
•
Considerado um dos mais seguros codificadores atuais
Usado no PGP
28
IDEA
• Texto pleno organizado em blocos de 64 bits
• Confusão e difusão são gerados por grupos algébricos
– XOR
– Adição mod (216)
– Multiplicação mod (216 + 1) – também visto com S-boxes
• Todas as operações incidem em blocos de 16 bits
• Blocos de dados são divididos em 4 blocos de 16 bits
• Utiliza 8 rodadas e cada rodada tem 14 passos
29
IDEA - Rodadas
Exceto para a última rodada,
swap Y2 e Y3
Depois da última
rodada (oitava):
30
IDEA: Interações
X1
Z1
X2
X3
Z2
Z3
X4
Z4
Z5
uma
iteração
Z6
mais 7
iterações
Z1
Z2
Y1
Saída Final
Z3
Y2
Z4
Y3
Y4
XOR bit a bit dos sub-blocos de 16 bits.
Adição módulo 216 de inteiros de 16 bits.
Multiplicação módulo 216+1 de inteiros de 16 bits
com o sub-bloco zero correspondendo a 216.
31
IDEA – Geração de chaves
• Usa um total de 52 subchaves
• 6 em cada uma das 8 rodadas e 4 na operação de saída
• Chave original K é dividida em 8 subchaves de 16 bits
– 6 primeiras são usadas no primeiro round
– As duas restantes ficam para o segundo round
– Desloca chave 25 bits para esquerda e divide novamente em 8
subchaves
– Usa as quatro primeiras para completar as chaves do
segundo round
– As quatro restantes ficam para o terceiro round
– Desloca chave 25 bits para esquerda e divide novamente em 8
subchaves
– Assim sucessivamente....
32
IDEA considerações
• Velocidade
– Implementações atuais rodam duas vezes mais rápidas que o
DES
• Criptoanálise
– Ataque de força bruta necessita 2128
– Parece ser imune a ataques diferenciais (pouco estudo ainda)
– Algumas classe de chaves podem facilitar ataques do tipo
texto pleno escolhido, mas nunca serão usadas
33
Advanced Encryption Standard
•
•
Programa iniciado em 1997 pelo NIST para substituir o DES
AES: novo padrão durante os próximos 30 anos (e vida útil de
outros 50 ou 60 anos)
– Obs: AES deverá proteger informações até o século XXII!
•
Requisitos do sucessor do DES
–
–
–
–
–
•
•
ter chaves de 128, 192 e 256 bits
operar com blocos de 128 bits
ser “eficiente”
ser “flexível”
estar livre de royalties
Quinze candidatos foram selecionados em jun/98
Cinco candidatos em 1999: Serpent, Mars, RC6, Twofish e Rijndael
34
Advanced Encryption Standard
•
AES foi adotado o pelo National Institute of Standards and
Technology (NIST) como US FIPS PUB 197 em Novembro de 2001
depois de um processo de padronização de 5 anos
•
Concorrentes
– Rijndael (86 votos) - anunciado vencedor em Outubro de 2000
•
–
Rijndael can be pronounced "Rhine dahl", a long “i" and a silent “e“
• Desenvolvido por Joan Daemen e Vincent Rijmen (Rijmen-Daemen - Bélgica)
Serpent (59 votos)
– Mars (13 votos)
– RC6 (23 votos)
– Twofish (31votos)
•
Pela primeira vez um codificador público é usado plo NSA para
informação Top Secret
–
"The design and strength of all key lengths of the AES algorithm (i.e., 128, 192 and 256) are
sufficient to protect classified information up to the SECRET level. TOP SECRET information
will require use of either the 192 or 256 key lengths. The implementation of AES in products
intended to protect national security systems and/or information must be reviewed and
certified by NSA prior to their acquisition and use."
35
Rijndael
• Características
–
–
–
–
–
operações realizadas no nível de byte
tamanhos de chaves: 128, 192, 256 bits
tamanhos de blocos: 128, 192, 256 bits
número de rodadas: 9, 11, 13 (além de uma rodada
extra no final)
• Opera em arrays de 4×4 de bytes –
– Denominado estado
– Versões com blocos maiores operam com colunas adicionais
• Cada rodada composta de quatro passos
–
–
–
–
substituição de bytes
deslocamento de linhas
mistura de colunas,
soma da subchave de rodada
36
Substituição de bytes
0
0
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
0
63
7c
77
7b
f2
6b
6f
c5
30
01
67
2b
fe
d7
ab
76
1
ca
82
c9
7d
fa
59
47
f0
ad
d4
a2
af
9c
a4
72
c0
2
b7
fd
93
26
36
3f
f7
cc
34
a5
e5
f1
71
d8
31
15
3
04
c7
23
c3
18
96
05
9a
07
12
80
e2
eb
27
b2
75
4
09
83
2c
1a
1b
6e
5a
a0
52
3b
d6
b3
29
e3
2f
84
5
53
d1
00
ed
20
fc
b1
5b
6a
cb
be
39
4a
4c
58
cf
6
d0
ef
aa
fb
43
4d
33
85
45
f9
02
7f
50
3c
9f
a8
7
51
a3
40
8f
92
9d
38
f5
bc
b6
da
21
10
ff
f3
d2
8
cd
0c
13
ec
5f
97
44
17
c4
a7
7e
3d
64
5d
19
73
9
60
81
4f
dc
22
2a
90
88
46
ee
b8
14
de
5e
0b
db
a
e0
32
3a
0a
49
06
24
5c
c2
d3
ac
62
91
95
e4
79
b
e7
c8
37
6d
8d
d5
4e
a9
6c
56
f4
ea
65
7a
ae
08
c
ba
78
25
2e
1c
a6
b4
c6
e8
dd
74
1f
4b
bd
8b
8a
d
70
3e
b5
66
48
03
f6
0e
61
35
57
b9
86
c1
1d
9e
e
e1
f8
98
11
69
d9
8e
94
9b
1e
87
e9
ce
55
28
df
f
8c
a1
89
0d
bf
e6
42
68
41
99
2d
0f
b0
54
bb
16
37
Deslocamento de linhas
38
Mistura de colunas
39
Soma da subchave de rodada
40
AES completo
41
CriptoAnálise do AES
•
Pela primeira vez a Matemática envolvida é completamente aberta
•
Ataques conhecidos
– Quebras com codificadores que implementam um menor número de
rodadas
• 7/10 - 128, 8/12 – 192, 9/14 – 256
– Preocupações com a margem pequena entre o número de rodadas
passíveis de quebra e o padronizado
– Quebra criptográfica é qualquer coisa melhor que uma busca exaustiva
– Como uma busca exaustiva envolve pelo menos 2128...
•
Ataque téorico proposto em 2002 – XSL attack
– Erros nas estimativas
•
Cache timing attack
– Ataque não contra o AES mas contra implementações mal-feitas do AES
– Servidor usando OpenSSL sem restrição de tempo
– Recomendação do autor -> não usar S-box
42
Outros Algoritmos Simétricos
•
Blowfish (32-448 bits)
–
–
–
–
–
•
Não patenteado
Fácil implementar
Alta velocidade de execução
Roda em emenos de 5K de memória
S-boxes dependem dos dados
Skipjack (80 bits)
– Utilizado no Clipper e Fortezza
– Desenvolvido pela NSA
– Em domínio público desde jun/98
•
CAST-128 e CAST-256
– 128 e 256 bits, patenteado pela Nortel (não há royalties)
– As funções variam de rodada para rodada
43
Outros Algoritmos Simétricos
•
RC5 e RC28
– Projetados por Ron Rivest (o R da empresa RSA Data Security Inc.)
– Também é o autor do RC4 e RC6, este último foi concorrente ao AES
– RC5
•
•
•
•
•
•
•
Rápido, Simples
Adaptável para processadores com diferentes tamanhos de palavra
Número variável de rodadas
Chave de tamanho variável
Baixa necessidade de memória
Alta segurança
Rotações dependentes dos dados
– RC28
• Utilizado no protocolo S/MIME
• Voltado para criptografia de e-mail corporativo
• Também possui chave de tamanho variável
44