Cryptography is an indispensable tool for protecting information in computer systems. In this course you will learn the inner workings of cryptographic systems and how to correctly use them in real-world applications. The course begins with a detailed discussion of how two parties who have a shared secret key can communicate securely when a powerful adversary eavesdrops and tampers with traffic. We will examine many deployed protocols and analyze mistakes in existing systems. The second half of the course discusses public-key techniques that let two parties generate a shared secret key. Throughout the course participants will be exposed to many exciting open problems in the field and work on fun (optional) programming projects. In a second course (Crypto II) we will cover more advanced cryptographic tasks such as zero-knowledge, privacy mechanisms, and other forms of encryption.
Timing attacks on MAC verification
Loading...
Do curso por Stanford University
Cryptography I
2502 classificações
Na lição
Message Integrity
Week 3. This week's topic is data integrity. We will discuss a number of classic constructions for MAC systems that are used to ensure data integrity. For now we only discuss how to prevent modification of non-secret data. Next week we will come back to encryption and show how to provide both confidentiality and integrity. This week's programming project shows how to authenticate large video files. Even if you don't do the project, please read the project description --- it teaches an important concept called a hash chain.
Conheça os instrutores
Dan BonehProfessor
Computer Science
No último segmento, neste módulo, eu quero te mostrar um ataque geral que
afeta muitas implementações de algoritmos Mac. E há uma lição legal
ser aprendido a partir de um ataque como este. Então, vamos olhar para uma implementação específica
de verificação HMAC. Isto acontece por ser uma implementação da biblioteca Keyczar,
que passa a ser escrito em Python. Então aqui está o código que é usado para verificar uma
tag gerada pelo HMAC. Este código é realmente simplificada. Eu só queria
meio que simplificá-la tanto quanto eu puder para obter o ponto de vista. Então, basicamente, o que o
entradas são, a chave, a mensagem, e os bytes de tag. A forma como verificar se ele é, nós
re-calcular o HMAC da mensagem e então comparar dizem que a 16, resultando
bytes. Para as picadas de assinatura reais dadas. Então, isso parece perfeitamente bem.
De fato, qualquer um pode implementá-lo assim. E, de fato, muitas pessoas têm implementado
-lo assim. O problema é que, se você olhar como a comparação é feita, o
comparação, como se poderia esperar, é feita byte a byte. Há um laço dentro do
interpretador Python que faz um loop sobre todos os dezesseis bytes. E acontece que o
primeira vez que encontra uma desigualdade, o ciclo termina e diz que as cordas são
não igual. Eo facto de que as saídas do comparador quando a primeira desigualdade
é encontrado introduz um ataque de temporização significativo sobre esta biblioteca. Então deixe-me mostrar-lhe
como se poderia atacá-lo. Então, imagine que você é o invasor, e você tem a mensagem m,
para os quais você deseja obter uma marca válida. Agora, seu objetivo é atacar um servidor que
tem uma chave HMAC segredo armazenado nele. E o servidor expõe uma interface que
basicamente leva pares de mensagem MAC. Verifica se o MAC é válido, se o MAC é válido
ele faz algo com a mensagem. E se o MAC não é válido, diz rejeitar.
Ok, então ele está de volta ao remetente ou a mensagem rejeita. Então, agora este atacante
tem a oportunidade de apresentar, basicamente, muita mensagem que aparece e ver se ele
pode deduzir as tags da mensagem específica para a qual uma vez atacada. Aqui está
como podemos usar a implementação quebrado a partir do slide anterior para fazer exatamente isso.
Então, o que o atacante vai fazer é enviar consultas tag muitas mensagens, onde o
mensagem é sempre a mesma. Mas com uma tag, ele vai experimentar com lotes e
lotes e lotes de marcas diferentes. Assim, na primeira consulta, o que ele vai fazer é apenas
apresentar uma tag aleatório juntamente com a mensagem alvo. E ele vai medir o tempo
servidor o levou a responder. A próxima consulta que ele vai apresentar, é que ele vai tentar
todos os bytes possíveis primeiros para as marcas. Deixe-me explicar o que quero dizer com isso. Assim, o
bytes restantes das tags que ele coloca são apenas arbitrárias, realmente não
importa o que eles são. Mas para a primeira mordida, o que ele vai fazer é que ele vai apresentar uma tag
de partida com um zero bytes. E então ele vai ver se o servidor teve um pouco
pouco mais para verificar a marca do que antes. Se o servidor levou exactamente a mesma quantidade
de tempo para verificar a tag como no passo um, então ele vai tentar de novo, desta vez com
bytes em um. Se ainda o servidor respondeu muito rapidamente, ele vai tentar
com conjuntos de bytes de dois. Se o servidor respondeu rapidamente, em seguida, ele vai tentar
com conjuntos de bytes de três, e assim por diante até, finalmente, vamos dizer, quando o byte conjuntos de
três servidores do exame um pouco mais para responder. O que isto significa é realmente
quando se fez a comparação entre o MAC correto eo MAC apresentado pelo
atacante. Os dois combinados sobre este byte, ea rejeição aconteceu na segunda
bytes. Aha. Então, agora o atacante sabe que a primeira mordida da tag é definido como três
e agora ele pode montar exatamente o mesmo ataque na segunda mordida. Então aqui. É
vai apresentar o tag. E o segundo, volta aqui. Aqui Isto deve ir aqui. Assim
que vai apresentar uma tag quando o segundo byte é definido para zero. E vai
medida se este teve um pouco mais do que na etapa dois. Se não, ele é
vai mudar isso para ser definido como um, e ele vai medida se o servidor
tempo de resposta é um pouco mais do que antes. Eventualmente, vamos dizer, quando ele define
isso, eu não sei. Quando o byte é definido para, a 53, digamos, de repente, o
servidor demora um pouco mais para responder. O que significa que agora, o
comparador acompanhado nos dois primeiros bytes. E agora o atacante soube que o
dois primeiros bytes do Mac são três e 53. E agora ele pode seguir em frente e fazer o
mesma coisa no terceiro byte e, em seguida, o byte de quarto e assim por diante e assim
por diante. Até que, finalmente, o servidor diz que, sim, eu aceito. Você realmente me deu o
Mac direito. E então vamos em frente e agir sobre esta mensagem falsa. Isso, atacar o nosso
abastecimento. Então este é um belo exemplo de como um ataque de temporização pode revelar o valor
de um MAC, o valor correto do MAC. Tipo de byte por byte, até que finalmente,
atacante obtém todos os bytes corretos da marca, e então ele é capaz de enganar o
servidor em aceitar este par tag mensagem. A razão de eu gostar deste exemplo é
esta é uma maneira perfeitamente razoável de implementação de uma rotina de verificação MAC.
E ainda, se você direita-lo desta maneira, ele será completamente quebrado. Então o que fazemos? Assim
deixe-me mostrar-lhe duas defesas, a primeira defesa, vou escrevê-lo novamente em python
é, é como se segue. Na verdade, a biblioteca Keyczar exatamente implementada essa defesa.
Este código é realmente retirado da versão atualizada da biblioteca. O primeiro
coisa que fazemos é testar se os bytes de assinatura apresentadas pelo atacante são da
comprimento correto, dizem, por HMAC isso seria dizer, você sabe 96 bits ou 128 bits, e
se não rejeitamos que, como um MAC inválido. Mas agora, se os bytes de assinatura realmente
ter o comprimento correto, o que fazemos é implementar nosso comparador própria. E
sempre leva a mesma quantidade de tempo para comparar as duas strings. Assim, em particular,
este usa a função zip em Python, que, essencialmente, se você está dando
lo duas dezesseis cadeias de bytes. Ele vai criar dezesseis pares. De bytes. Por isso, vou
apenas criar um, uma lista de dezasseis elementos, onde cada elemento é um par de bytes. Um
tomadas a partir da esquerda e uma tomada a partir da direita. E então você volta, você sabe, você
percorrer esta lista de pares. Está calcular o XOR do primeiro par, ea
ou para o resultado. Em seguida, é calcular o XOR do segundo par, e
você ou que para o resultado. E você nota que, se em algum momento neste
loop, dois bytes que ser não igual, então o XOR irá avaliar a algo
que é diferente de zero. E, portanto, quando se or'ed-lo para o resultado. O resultado
também será contagem em zero, e, em seguida, vamos retornar falso, no final do
comparação. Assim, o ponto aqui é que agora o comparador sempre leva o mesmo
quantidade de tempo. Mesmo se encontra diferença no número de byte três, será
continuar executando as cordas ambos até o fim. E só então se
retornar os resultados. Portanto, agora o ataque de temporização supostamente é impossível. No entanto,
isso pode ser bastante problemático, porque compiladores tentou ser muito útil aqui. Assim
compilador otimizado um pode olhar para este código e dizer: ei, espere um minuto. Eu posso
realmente melhorar esse código, tornando o final do circuito fechado quatro. Logo que uma incompatível
conjunto de bytes é descoberto. E assim, um compilador otimizado pode ser o seu tipo,
de, calcanhar de Aquiles quando se trata de tornar os programas de sempre ter a mesma quantidade de
tempo. E assim uma defesa diferente, que não é tão amplamente implementado, é tentar
esconder do adversário, o que as cordas são realmente estão sendo comparados. Então deixe-me mostrar
você que eu quero dizer com isso. Então, novamente, aqui temos o nosso algoritmo de verificação. Por isso
toma como entradas, uma chave, uma mensagem, e MAC de um candidato do adversário. E
, em seguida, a forma como fazemos a comparação é que em primeiro lugar, calcular o MAC correto em
a mensagem. Mas, então, em vez de comparar diretamente o MAC ea assinatura
adversário bytes, o que vamos fazer é nós vamos uma vez mais de hash. Então, nós
computar um hash aqui do MAC. Nós computar um hash dos bytes de assinatura. Claro que,
se estes dois acontecer a ser a mesma, em seguida, os HMACs resultantes será também o
mesmo, assim que a comparação será bem sucedida. Mas a questão é agora, se sig
bytes acontecer a MAC igual no primeiro byte, mas não sobre os bytes remanescentes.
Então, quando fazemos essa camada adicional de hash, é provável que os dois resultando
valores são completamente diferentes. E, como resultado, o byte pelo comparador byte vai
saída apenas na primeira iteração. O ponto aqui é que o adversário não
realmente sabe quais seqüências estão sendo comparados. E, como resultado, ele não pode
montar um ataque de temporização que discutimos anteriormente. Ok, então isso é
defesa outro. Pelo menos agora, você não está à mercê de um compilador de otimização.
lição O principal de tudo isso é que você percebe que as pessoas que ainda são
especialistas em cryptolibraries de execução, obter esse material errado. E o código de direito
que as palavras perfeitamente bem e ainda é completamente vulnerável a um ataque de temporização
que completamente desfazer toda a segurança do sistema. Então a lição aqui é, naturalmente,
você não deve inventar o seu próprio crypto mas você não deve mesmo ser
implementar sua própria criptografia, porque muito provavelmente ele estará vulnerável para o lado
ataques de canal. Basta usar uma biblioteca padrão como OpenSSL. Keyczar é na verdade um
boa biblioteca de usar que reduziria as chances de que você está vulnerável a estes
tipos de ataques.
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2019 Coursera Inc. Todos os direitos reservados.
