A Crise das Funções de Hash

Transcrição

A Crise das Funções de Hash
Paulo S. L. M. Barreto
Copyright © 2005 Paulo Barreto
LARC/PCS/EPUSP
1
Sumário
• Famílias tradicionais de resumos criptográficos (funções de hash).
• Histórico de problemas e a crise recente.
• Perspectivas de correção e dificuldades de
substituição.
LARC/PCS/EPUSP
2
Resumos criptográficos
• Um resumo criptográfico (ou função de hash) é
uma função H: {0, 1}* → {0, 1}n satisfazendo as
seguintes propriedades:
– [Resistência a primeira inversão:] Dado um resumo R,
é inviável encontrar uma mensagem M tal que R =
H(M) ⇒ esforço 2n.
– [Resistência a segunda inversão:] Dado um resumo R e
uma mensagem M1 tal que R = H(M1), é inviável
encontrar uma mensagem M2 ≠ M1 tal que R = H(M2)
⇒ esforço 2n.
– [Resistência a colisões:] É inviável encontrar duas
mensagens distintas M1 e M2 tais que H(M1) = H(M2)
⇒ esforço 2n/2.
LARC/PCS/EPUSP
3
Importância
• Assinaturas digitais em documentos
eletrônicos
(“mensagens”)
não
são
realizadas diretamente sobre o conteúdo dos
documentos, mas sobre seus resumos
criptográficos.
LARC/PCS/EPUSP
4
Importância
• Motivo: algoritmos de assinatura são muito
mais lentos que funções de hash.
• Aplicá-los sobre cadeias < 100B é razoável,
mas sobre dados de e.g. 600MB está fora de
cogitação.
LARC/PCS/EPUSP
5
Importância
• As três propriedades essenciais de resumos
criptográficos significam a inviabilidade de
fraudes.
• Exemplo (resistência a segunda inversão): dado
um documento eletrônico M1 cuja assinatura
digital foi aplicada ao resumo R = H(M1), se fosse
viável calcular outro documento M2 ≠ M1 com o
mesmo resumo, H(M2) = R, a mesma assinatura
legitimamente gerada para M1 seria ilegitimamente
válida para M2.
LARC/PCS/EPUSP
6
Funções “Fortes”?
• “Nobody knows how to design a strong
hash function from scratch” (Rijmen &
Barreto 2005).
• Certas construções tradicionais de funções
de hash garantem algumas propriedades de
segurança.
• Infelizmente, muitas instâncias dessas
construções possuem problemas fatais por
abuso das premissas de segurança.
LARC/PCS/EPUSP
7
Construção Merkle-Damgård
• Particionamento da mensagem em blocos de
tamanho fixo e acúmulo iterativo dos blocos sobre
um estado de n bits (função de compressão f ).
• “If there exists a computationally collision-free
function f from k bits to n bits where k > n, then
there exists a computationally collision-free
function H mapping messages of arbitrary
polynomial lengths to n-bit strings.” (Damgård
1989).
LARC/PCS/EPUSP
8
• Complementação e particionamento em t
blocos de b bits: m’ ≡ m1 || ... || mt–1 || mt’,
onde |mi| = |mt’| = b, mt’ ≡ mt || 1 || 0* || |m|.
mensagem original: |m| bits
m1
m2
...
mt–1
b bits
mt
1 0 ... 0 |m|
padding
LARC/PCS/EPUSP
9
• Função de compressão
f: {0, 1}k → {0, 1}n
com k = n + b.
IV
m1
f
H1
m2
f
...
Ht–1
...
...
mt
f
• Define-se H(m) ≡ Ht.
LARC/PCS/EPUSP
Ht
≡ H(m)
10
Funções de Compressão
• Tradicionalmente, modos de operações para
cifras de bloco dedicadas.
• Construção mais comum: Davies-Meyer.
mi
Hi–1
Hi ≡ f(Hi–1 || mi)
E
LARC/PCS/EPUSP
11
Cifra Dedicada
ESHA–1
(1 passo de 80)
Source: Rijmen 2005
LARC/PCS/EPUSP
12
Famílias de Funções de Hash
• Família MD:
– Desenvolvida por Ronald Rivest.
– Operações simples sobre words de 32 bits: ¢, ¿, À,
ª, ©, ⊕, ∧, ∨, ¬.
– MD2, MD4 e MD5.
– Completamente quebrada.
• Família SHA:
– Desenvolvida pela NSA.
– SHA-0, SHA-1: projeto inspirado em MD4.
– SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512).
LARC/PCS/EPUSP
13
Família MD
• Vulnerabilidades na função de compressão
de MD4 encontradas em pouco tempo.
–
–
–
–
den Boer & Bosselaers (1993)
Merkle
Vaudenay
Dobbertin (1995)
• A análise de Dobbertin leva a um algoritmo
eficiente para produzir colisões de MD4.
• Colisões realísticas são possíveis!
LARC/PCS/EPUSP
14
Família MD
********************
********************
CONTRACT
CONTRACT
At the price of $176,495 Alf Blowfish
At the price of $276,495 Alf Blowfish
sells his house to Ann Bonidea…
sells his house to Ann Bonidea…
fMD4(IV ||
"*********************_C
ONTRACT__At_the_price_of_
$176,495_Alf_Blow") = h
fMD4(IV ||
"*********************_C
ONTRACT__At_the_price_of_
$276,495_Alf_Blow") = h
ÂÂ
LARC/PCS/EPUSP
Â
Â
ÂÂ
15
Família MD
• Dobbertin descreve uma extensão parcial do
ataque ao MD5 (1996), mas SHA-0/SHA-1
estão fora de alcance.
• Wang et al. (1998): algoritmo eficiente para
encontrar colisões de MD4 e MD5!
• Problema: escrito em
.
• Colisões de MD4 podem ser calculadas com
papel e lápis. MD5 sucumbe a um laptop.
LARC/PCS/EPUSP
16
Família MD
• Ataques ao MD5 são práticos: como demonstração
de princípio, certificados digitais de mercado já
foram forjados (Lenstra & Wang 2005) com
código disponível na Internet!
• Contudo, continua não só em uso efetivo, mas
reconhecido em várias normas!
MD5 =
!
LARC/PCS/EPUSP
17
Família SHA
• SHA-0/SHA-1: n = 160 ⇒ esforço esperado
para obter colisões ≈ 280.
• Critérios de projeto não divulgados além da
inspiração no MD4.
• Vulnerabilidade anunciada pelo NIST/NSA
mas não revelada (1993).
• Chabaud & Joux (1998): criptoanálise
diferencial de SHA-0 (ataque acadêmico).
LARC/PCS/EPUSP
18
Família SHA
• SHA-0
– Biham & Chen (2004)
– Joux et al. (2004) ⇒ 250
– Wang et al. (2004) ⇒ 240
• SHA-1
– Biham and Chen (2004)
– Rijmen and Oswald (2004)
– Wang et al. (2005) ⇒ 263
LARC/PCS/EPUSP
19
Análise
• As cifras de bloco subjacentes às funções de hash
da família MD e SHA-0/SHA-1 são notoriamente
fracas:
– difusão lenta.
– baixa não-linearidade.
– escalonamento (alimentação) de mensagem simples
demais (NESSIE 2003).
• Ineficiências decorrentes: grande número de
passos (até 80).
• SHA-1 será aposentado pelo NIST até 2010.
LARC/PCS/EPUSP
20
Família SHA-2
• Essencialmente duas funções distintas
(SHA-256 e SHA-512), com parâmetros
alternativos para tamanhos de hash
adicionais (SHA-224 e SHA-384; talvez
SHA-160).
• Estrutura geral similar às funções SHA-0/
SHA-1. Diferenças em detalhes parecem ter
impacto relevante na segurança (e.g. difusão
mais rápida), mas ainda sub-avaliado.
LARC/PCS/EPUSP
21
Outras Funções de Hash
• Família RIPEMD:
– RIPEMD, RIPEMD-128, RIPEMD-160.
– Projeto europeu (RIPE).
– RIPEMD original quebrada (Dobbertin; Wang
et al.), atualizações OK(?).
• HAVAL:
– Comprimento variável (128, 160, 192, 224,
256), número de estágios variável (3–5).
– Quase todas as combinações quebradas.
LARC/PCS/EPUSP
22
• SMASH:
– Estrutura radicalmente nova.
– Proposta no FSE’2005, quebrada em menos de
1 mês.
• DHA-256:
– Remendo sugerido para a estrutura SHA.
– Proposta no NIST HFW’2005, quebrada na
mesma semana.
LARC/PCS/EPUSP
23
• WHIRLPOOL:
– Hash de 512 bits.
– Não utiliza a função de compressão Davies-Meyer, mas
Miyaguchi-Preneel.
– Não utiliza uma cifra interna do tipo SHA, mas uma
cifra da família do AES.
– Escalonamento de mensagens não-linear.
– Adotada no portfolio NESSIE.
– Acolhida na norma ISO/IEC 10118-3.
– Disponível prontamente no kernel do Linux.
LARC/PCS/EPUSP
24
Dificuldades de Atualização
• Que critérios serão usados para selecionar
funções de hash alternativas?
– Remendar as falhas
identificadas?
– Adotar uma estrutura
completamente diferente?
LARC/PCS/EPUSP
25
Dificuldades de Migração
• Havendo consenso em algum substituto
para as funções quebradas, como atualizar a
enorme base legada?
– Certificados digitais podem ser revogado$ e
reemitido$.
– Hardware criptográfico é mai$$$ problemático.
– Interoperabilidade de layouts (160 bits?).
• Contudo, o risco de fraude é elevado
(considerar e.g. movimento diário do SPB).
LARC/PCS/EPUSP
26
Perspectivas
• NIST provavelmente manterá o SHA-256
(ou uma função derivada, SHA-160) como
substituto recomendado do SHA-1.
• Eventualmente alguma função de outra
família poderá ser adotada como reserva.
• Migração lenta e penosa, mas necessária
(principalmente do MD5!): risco envolvido
afeta toda a infra-estrutura de certificação
digital em existência.
LARC/PCS/EPUSP
27
Perguntas?
LARC/PCS/EPUSP
28

A Crise das Funções de Hash

Transcrição

Documentos relacionados

Filtro 2" Super c/ Malha

- EDP Gás Serviço Universal

Kalahari

mandando bem – caldeirão do huck

Veja aqui

Veja abaixo a relação dos beneficiários aptos ao Programa Minha

esta apresentação em pdf

valentine`s day

GRÁTIS: Apostila de apoio e exercícios

B( ) Profª.: Rosane L

TV a Cabo - Laboratório de Comunicações e Sinais