Mais ataques em cifras de bloco (16 min)

Há uma imensa literatura em atacar cifras de bloco.

Neste segmento, eu só quero dar-lhe um gosto para o que esses ataques parecem.

E eu espero que eu vou convencer você de que você nunca deve projetar sua própria cifra de bloco,

e ficar com as normas como Triple DES e AES.

O primeiro conjunto de ataques que eu quero falar sobre

são ataques contra a implementação da cifra do bloco.

Como exemplo, imagine que você tem um cartão inteligente que está implementando uma cifra de bloco.

Assim, o cartão inteligente, por exemplo, poderiam ser usados para pagamentos de cartão de crédito. Ela pode ter uma

chave secreta dentro dele para autenticar os seus pagamentos de cartão de crédito que você furar o

cartão em um terminal de pagamento, por exemplo. Então, agora, se um atacante obtém seu cartão inteligente,

o que ele poderia fazer é que ele poderia realmente ter o cartão inteligente a um laboratório, e depois executar o

cartão, e medida de tempo muito precisamente o quanto o cartão levou para fazer a criptografia e

descriptografia. Agora, se a quantidade de tempo que a aplicação levou a fazer

criptografia depende bits da chave secreta, em seguida, pela medição do tempo, o

atacante vai aprender alguma coisa sobre sua chave secreta e, de fato, ele pode ser capaz

para extrair completamente a sua chave secreta. E há muitos exemplos de implementações

que simplesmente através da medição do tempo muito precisamente para muitas operações de

algoritmos de criptografia, você pode extrair completamente a chave secreta. Outro exemplo é,

ao invés de apenas medir o tempo, você pode realmente medir o consumo de energia

do cartão como é operacional. Então, literalmente, você pode conectá-lo a um dispositivo

que irá medir a corrente que o cartão está chegando e, em seguida, o gráfico

correntes muito, com muita precisão. Agora, estes cartões não são muito rápidos, e como resultado,

você pode realmente medir a quantidade exata de energia consumida em cada ciclo de relógio como

o cartão estava sendo executado. Quando você faz isso, você realmente obter gráficos deste formulário.

Portanto, este é um exemplo de uma operação de cartão inteligente, enquanto ele está fazendo a

DES computação. Assim você pode ver muito claramente, aqui é quando ele estava fazendo

a permutação inicial. Aqui é quando ele está fazendo a permutação final. E, em seguida,

aqui, você pode contar. Na verdade, existem dezesseis colinas e vales

correspondente aos dezasseis rodadas. E, essencialmente, quando você aumentar o zoom em um gráfico

como este, basicamente você pode ler os bits de chave fora, um por um, só de olhar para

quanta energia o cartão consumido como ele estava fazendo as diferentes operações. Acontece

que, até mesmo cartões que tomem medidas para mascarar este tipo de informação, são ainda

vulnerável. Há um ataque chamado de análise de poder diferencial, onde

, basicamente, você medir a energia consumida pela placa sobre muitos, muitos, muitos, funciona de

algoritmo de criptografia. E enquanto não há qualquer dependência ainda pequeno entre

quantidade de consumo de corrente e os bits da chave secreta, que basicamente

dependência vai aparecer após a execução suficiente do algoritmo de criptografia. E como um

resultado que você vai ser capaz de extrair completamente a chave secreta. Ok, então estes

ataques foram realmente descobertos por Paul Kocher e seus colegas até a

Pesquisa Criptografia e há realmente uma indústria bastante grande dedicada a apenas

defesa contra esses ataques de energia. No que diz respeito ataques de tempo estão em causa,

quero mencionar que estes são reais. Eles não são apenas sobre os cartões inteligentes.

Por exemplo, você pode imaginar um processador multicore, onde o algoritmo de criptografia

está sendo executado em um núcleo eo código atacante passa a ser executado em outro

núcleo. Agora, esses núcleos realmente compartilhar o mesmo cache. E, como resultado, um invasor

pode realmente medir ou pode realmente olhar para o cache exata falta que o

algoritmo de criptografia incorridos. Acontece que, olhando para erros de cache, você

pode completamente descobrir a chave secreta usada pelos algoritmos. Assim, um núcleo pode

essencialmente extrair informações de outro núcleo, apenas olhando erros de cache.

Então implementar essas cifras de bloco é realmente muito sutil

porque você tem que se certificar de que os ataques de canal lateral não vazar

informações sobre a sua chave secreta. Outro tipo de ataque que tem sido discutido em

literatura é o que é chamado um ataque de culpa. Então, aqui, basicamente, se você for

atacar um cartão inteligente, você pode realmente fazer com que o cartão inteligente para mau funcionamento,

talvez por overclocking, talvez aquecendo-se. Essencialmente, você pode causar

para o processador, mau funcionamento e saída de dados errôneos. Acontece que, se,

durante a criptografia, existem erros na última rodada do processo de criptografia, os

textos cifrados resultantes que são produzidos são suficientes para realmente expor a chave secreta K.

Isso é completamente um resultado interessante que na verdade se você tiver algum erro, se você nunca

saída de um resultado errado, que realmente pode comprometer completamente a sua chave secreta.

Então, é claro, a defesa contra isso significa que antes de produzir o resultado de sua

algoritmo, você deve verificar para se certificar de que o resultado correto foi computado.

Agora é claro que é trivial, porque como você sabe que o erro não aconteceu

em seu algoritmo de verificação. Mas há formas conhecidas de contornar isso. Então, basicamente você

pode realmente calcular algo três ou quatro vezes, tomar a maioria sobre todos aqueles

resultados, e ter a certeza que a saída é realmente correto, desde que não muitas

faltas ocorreu dentro de seu cálculo. Estes são os ataques sobre a execução.

Espero que estes exemplos podemos assegurar que não só você deve não

inventar suas próprias cifras de bloco, você nunca deve ainda implementar essas crypto

primitivas de si mesmo. Como A, você tem que ter certeza que não há canal lateral

anexos em sua implementação e B, você tem que ter certeza que o

implementação é seguro contra ataques de falhas. Ok então, em vez disso você deve apenas

bibliotecas de uso padrão, como os disponíveis no OpenSSL e muitos outros

bibliotecas por aí. Portanto, não implementar essas primitivas a si mesmo, é só usar

bibliotecas existentes. Tudo bem, então agora eu quero voltar para o tipo de mais sofisticado

ataques cifras de bloco e eu vou particularmente falar sobre como aplicar esses ataques ao DES.

Ok então esses ataques foram descobertos por volta Biham e Shamir em 1989, e eu vou

particularmente descrever uma versão do ataque descoberto por Matsui em 1993.

Assim, o objetivo aqui é basicamente dado muitos, muitos pares de entrada-saída, podemos realmente

recuperar a chave melhor do que a busca exaustiva? Então, qualquer coisa que funcione melhor do que

busca exaustiva já conta como um ataque à cifra de bloco. Ok, então o

exemplo, eu quero dar a você é que é chamado criptoanálise linear. E aqui imaginá-lo

que acontece é que, você sabe, c é a criptografia de chave k estou usando, e

suponha que acontece que se eu olhar para chave aleatória e uma mensagem aleatória, de alguma forma

há uma dependência entre a mensagem, texto cifrado, e os bits de chave. Em

particular, se eu XOR um subconjunto de bits de mensagem, então este é apenas um

subconjunto dos bits da mensagem, se eu XOR que com um certo subconjunto do texto cifrado

bits. -Então, esses dois, o atacante vê. O atacante tem a mensagem eo

atacante tem o texto cifrado. E então você comparar isso a um XOR de um subconjunto de

os bits de chave. Agora, se os dois estavam completamente independente que é o que você

como, você definitivamente não quer que a sua mensagem e seu texto cifrado de alguma forma

prever seus bits de chave, se os dois são assim, totalmente independente, então este

igualdade realizará com probabilidade exatamente a metade. Mas suponho que isso

acontece que há um viés e esta probabilidade mantém com metade da probabilidade

epsilon mais por algum epsilon pequeno. Acontece que, de fato, para o DES, há

uma relação desse tipo. A relação é especificamente por causa de um bug no projeto

do quinto S-box. Acontece que o quinto S-box passa a ser muito próximo de uma linear

função. E que a função linear, basicamente, uma vez que se propaga através do

circuito DES inteiro, gera uma relação deste tipo. Você percebe, este é

, basicamente, uma relação linear que está sendo calculado aqui. Então, este pequeno minúsculo, minúsculo

linearidade no quinto S-box gera esta relação ao longo de todo o circuito,

onde o epsilon é pequena. Epsilon é uma mais de 2 ^ 21, e eu escrevi o que

que é. Assim, o viés é muito, muito, muito pequeno. Mas, no entanto, existe uma

preconceito com estes subconjuntos particulares de bits. Agora, eu não vou mostrar-lhe como

derivar esta relação, ou eu não vou mostrar para você mesmo o que é. Vou apenas dizer-lhe

como usar uma relação como essa uma vez que você encontrá-lo. Okay. Então aqui está a nossa relação

que temos. E a questão é como usá-lo. Assim, com um pouco de estatísticas

você pode realmente usar uma equação como essa para determinar alguns dos bits-chave. E

aqui está você fazê-lo. Suponha que você recebeu uma mensagem sobre epsilon quadrados texto cifrado pares.

e estes têm de ser mensagens independentemente aleatórios e os

textos cifrados correspondentes. O que você faria se você usar a fórmula acima. Em

fato de você usar o lado esquerdo da fórmula acima para calcular essa relação

entre a mensagem eo texto cifrado para todos os pares que lhe foi dada. Agora, o que fazer

você sabe? Você sabe que para epsilon metade mais um desses valores, você sabe que

estas coisas será igual a um XOR dos bits de chave. Então, se você

ter maioria sobre todos os valores que você calculado, verifica-se que não é tão

difícil ver que na verdade você vai ter a correta previsão para o XOR do

bits de chave, com uma probabilidade de 97,7%. Em outras palavras, se esta relação acontece para

ser correto mais de metade do tempo, então a maioria vai estar certo. E porque

há um preconceito, há um viés epsilon, a probabilidade de que você estará correto

mais de metade do tempo é, de fato, 97,7%. Nesse caso, a maioria, em

fato, irá dar-lhe a correta XOR dos bits-chave. Ok? Portanto, este é kinda cool.

Dentro de um longo tempo epsilon quadrado, você pode descobrir um XOR de um monte de chave

bits. Então, agora, vamos aplicar isso a DES. Assim, por DES, temos epsilon, que é um

mais de 2 ^ 21. O que significa que se você me der 2 ^ 42 pares de entrada-saída, eu posso

descobrir um XOR dos bits-chave. E agora, ao que parece, eu não vou mostrar exatamente

como, grosso modo, usando esse método, você não é só pegar um pouco de chaves. Em

verdade, você tem dois bits de chave. Você pode usar esse tipo de relação. Um vai em um

frente e um está indo em uma direção para trás. Então, que lhe dá dois

XORs de bits da chave secreta. Ok, então é dois bits de informações sobre o

chave secreta. E então acontece que você pode obter mais doze bits, porque,

essencialmente, você pode descobrir o que as entradas são para o quinto S-box. Ok, então,

eu não vou mostrar-lhe exatamente como. Mas acontece que você pode obter doze mais bits,

que é um total de catorze bits de global. Então, agora, com este método, você tem

recuperado quatorze bits da chave secreta. E, claro, que você levou tempo de 2 ^ 42.

Ok, então, o que você faz? Bem, então o resto é fácil. Agora, o que

você vai fazer é você está indo para fazer a pesquisa exaustiva sobre os bits restantes.

Bem quantos bits restantes estão lá? Bem, existem 42 bits restantes, de modo

pesquisa exaustiva a levará tempo 2 ^ 42. Então, qual é o tempo de ataque total?

Bem, o primeiro passo do algoritmo para determinar os catorze bits de tomou 2 ^ 42 tempo,

e pesquisa de força bruta restante também teve 2 ^ 42 tempo.

De modo geral, o ataque teve dois para o tempo 43. Ok? Então, agora, isso é muito melhor

de busca exaustiva. Dentro de dois para o tempo de 43 anos, que quebrou o DES. Mas claro, isso

necessários dois para os 42 aleatórios de entrada-saída pares enquanto busca exaustiva só

necessários três pares. Ok, então este é um número bastante grande de input-output

pares que são necessários, mas dado um número tão grande, você pode realmente recuperar o

chave mais rápido do que a busca exaustiva. Ok, então qual é a lição de tudo isso?

A lição é, em primeiro lugar, qualquer pouquinho de linearidade, basicamente, neste no-

quinta S-caixa, que não foi concebido, bem como a outras caixas de S-, basicamente levou

a um ataque com o algoritmo. Okay. Uma batida pequena de linearidade já introduziu esta

ataque linear. E eu quero enfatizar novamente que este não é o tipo de coisa

você pensa quando você projetar uma cifra. E assim, novamente, a conclusão aqui é,

há ataques muito sutis sobre cifras de bloco, aquelas que você não será capaz de

encontrar-se. E assim se ater apenas às normas. Não nunca, nunca, nunca, nunca

projetar sua cifra de bloco. Ok, então isso é tudo que eu quero dizer sobre sofisticado

ataques. Agora vamos passar para o último tipo de ataque que eu quero mencionar, que

vou chamar ataques quânticos, que são de novo, estes são ataques genéricos sobre

todas as cifras de bloco. Então deixe-me explicar o que quero dizer com isto.

Então, primeiro de tudo, vamos olhar para um problema genérico, um problema de busca genérico. Suponha que eu tenho uma função

em alguns X domínio grande, que passa a ser duas saídas, seja zero ou um.

E acontece que essa função é mais zero. E há, como, talvez uma entrada

onde a função acontece para avaliar a um. E seu objetivo é, basicamente, você sabe,

me encontrar as entradas onde a função passa a ser um. Talvez haja apenas um

entrada tal. Mas seu objetivo é encontrá-lo. Bem, então em um computador clássico, o que pode

você faz? A função é dado a você. É dado a você como uma caixa preta. Assim, o melhor

você pode fazer é apenas tentar todas as entradas possíveis. Então, isso vai levar algum tempo que

em linear no tamanho do domínio. Agora, ao que parece há uma mágica absolutamente

resultado que diz que se você construir um computador que se baseia na física quântica

em oposição à física clássica, você pode resolver esse problema rapidamente. Então deixe-me

explicar o que quero dizer com isto. Então, em primeiro lugar nos anos 70 e 80, observou-se, eu

acho que foi realmente Richard Feynman observou que este, inicialmente, que disse

que acaba por ser muito difícil para simular experimentos quânticos em um

computador clássico. Então Feynman disse, se esse for o caso, talvez estes quantum

experimentos está computando as coisas que um computador clássico não pode computar.

Então, eles estão de alguma forma capaz de calcular rapidamente as coisas que são muito difíceis de

fazer classicamente. E isso acabou por ser correto. E, de fato, o exemplo que eu quero

para mostrar a você é uma dessas coisas incríveis que, de fato, se você pudesse construir um

computador quântico, que está usando a física quântica, então ele é, na verdade, você pode resolver

este problema de pesquisa não em X tempo, mas na raiz quadrada do tempo X. Então, de alguma forma, mesmo

que o computador não sabe nada sobre a função F, é tratá-la como

uma caixa preta, no entanto, é capaz de encontrar um ponto onde a função é uma só, em

raiz quadrada do tempo de X. Eu não vou explicar isso aqui, mas, no final do

classe, nós vamos ter uma palestra tópicos avançados. E se você gostaria de me explicar

como esse algoritmo funciona, posso explicá-lo em palestra que tópicos avançados.

É realmente muito interessante, e, de fato, os computadores quânticos têm um grande impacto sobre

crypto. E, novamente, como eu disse, eu posso explicar isso na palestra último.

Certo. Então, o que isso tem a ver com quebrar cifras de bloco? Até agora é apenas uma

problema de pesquisa genérica. Bem, oh, na verdade eu devo dizer antes de eu lhe mostrar o

aplicação, devo mencionar que, bem, você pode estar pensando, bem, pode ser alguém

construir um computador quântico. E isso ainda é completamente desconhecido. Neste ponto,

ninguém sabe ao certo se podemos construir grandes o suficiente para realmente computadores quânticos

tirar vantagem deste algoritmo bonita devido a Grover. Tudo bem, então o que isso

tem a ver com cifras de bloco? Bem, então suponho que eu dar-lhe uma mensagem par-texto cifrado.

Apenas um ou apenas alguns. Podemos definir uma função como se segue. É uma

função em K, é uma função, a tecla de espaço. Ea função basicamente

uma saída, se acontece que a criptografia de m com mapas k para c, e

saída será zero caso contrário. Agora nós argumentamos que, basicamente, este é exatamente o tipo de

função que é uma em um ponto no espaço de chave e é isso. Então, por Grover

algoritmo, podemos realmente encontrar a chave secreta na raiz quadrada do tempo K.

E o que isso significa? Para DES, isso destruir totalmente DES. Assim diria

que com o tempo 2 ^ 28, você poderia encontrar uma chave. 2 ^ 28 é de cerca de 200 milhões.

Assim, 200 milhões passos que é, você sabe, só tem um milésimo de segundo em um computador moderno.

Isto destruir totalmente DES. Mas mesmo AES com chaves de 128 bits,

você seria capaz de encontrar a chave secreta no tempo, cerca de 2 ^ 64.

E 2 ^ 64 é nos dias de hoje, considerado inseguro. Isso é dentro do reino da

busca exaustiva. E então, basicamente, se alguém foi capaz de construir um quantum

computador, então diria que a AES-128 não é mais seguro. Em vez disso, se alguém,

você sabe, se amanhã, você abre o jornal e ler um artigo que

diz, você sabe, assim e assim construiu um computador quântico, a conclusão, o

conseqüência de tudo o que é que você deve mover imediatamente para bloquear cifras que usam

256 bits, porque então o tempo de execução do algoritmo de Grover é 2 ^ 128,

que é mais tempo do que consideramos viável, e os, basicamente, há

cifras exemplo com 256 bits, por exemplo, AES-256. Este é um dos

razões pelas quais foi projetado com AES 256 bits em mente. Mas para ser honesto, esta é

não a única razão. Há outras razões pelas quais você quer que ele tem tamanhos maiores de chave.

Ok, então esta é, como eu disse, apenas um gosto dos ataques diferentes em cifras de bloco,

e eu vou deixar por isso mesmo. Se decidirmos em quantum para a última

tema do curso, então vamos recuperar essa na palestra último.