Agora que sabemos o que MACs são, vamos em frente e construir nossos primeiros MACs seguras.
Primeiro quero lembrá-lo que um MAC é um par de algoritmos. A primeira é uma sessão de autógrafos
algoritmo que é dada uma mensagem e uma chave irá gerar uma etiqueta correspondente eo
segundo é algoritmos de verificação é dada uma mensagem de chave e um tag enquanto
saídas zero ou um, dependendo se a etiqueta é válido ou não. E nós dissemos que
um MAC é seguro se é existencialmente falsificáveis em um ataque de mensagem escolhida.
Em outras palavras, os atacantes permitem montar um ataque mensagem escolhida onde ele pode
enviar mensagens arbitrárias de sua escolha e obter as marcas correspondentes para
essas mensagens, e depois, apesar da capacidade de gerar etiquetas arbitrárias A
atacante não pode criar um par de mensagem de marca-novo que não foi dado a ele
durante o ataque mensagem escolhida. Ok então já vimos esta definição, no
último segmento e agora a questão é como vamos construir MACs seguras? Assim, o primeiro
exemplo, eu quero te dar é, basicamente, mostrando que qualquer PRF seguro diretamente dá
-nos um MAC seguro também. Então vamos ver como fazemos. Assim, suponha que temos um pseudo
função aleatória para a função pseudo-aleatório e tem entradas e saídas em X
Y. E vamos definir o MAC seguinte. Então, a nossa forma de assinar 'M' é basicamente uma mensagem
, basta avaliar a função de 'M' o ponto Assim, a tag para a mensagem M é
simplesmente o valor da função no ponto M e em seguida, a maneira como verificar uma
mensagem para que o par é por recomputing o valor da função na mensagem M e
verificação se que é igual à tag que nos foi dado. Nós dizemos que sim, se assim e nós
rejeitar o contrário. Então aqui você tem basicamente em imagens que, quando Alice quer
para enviar uma mensagem para Bob, ela calcula uma tag pelo valor da PRF e então ela
acrescenta esta tag com a mensagem, Bob recebe o par guia correspondente, ele
recomputes o valor da função e testa se a etiqueta dada é realmente
igual ao valor da função no ponto M. Então, vamos olhar para um mau exemplo de
esta instrução. E assim supor que temos uma função pseudo-aleatório que acontece
para a saída de apenas 10 bits. Ok, então esta é uma função pseudo-aleatória bem e isso só
Acontece que para 'M' qualquer mensagem que ele só gera 10 valor bits. A minha pergunta
para você é se usar 'F' esta função para construir um MAC, é que vai ser um
MAC é seguro? Portanto, a resposta é não, este MAC é inseguro. Em particular, porque o
tags são muito curta. Por isso, considero o adversário seguinte simples. O que o
adversário vai fazer é simplesmente escolher uma mensagem arbitrária M e apenas acho que a
valor do MAC para que a mensagem particular. Agora, porque a etiqueta só é 10
bits de comprimento, o adversário tem a chance de um em cada dois a 10 em adivinhar o MAC
corretamente. Em outras palavras, a vantagem de o adversário supondo, um distintamente
palpites tag aleatória para uma determinada mensagem. Que o adversário vai ter um
vantagem contra o mac que é basicamente um espaço de dois a dez, que é uma mais
mil 24 e que é definitivamente não negligenciável. Assim, o adversário
basicamente vai conseguir forjar o mac em uma determinada mensagem com probabilidade um
em mil que é inseguro. No entanto, acontece que este é o único exemplo que
onde as coisas podem dar errado, só quando a saída da função é pequena lata coisas
dar errado. Se a saída do PRF é grande, então obtemos um MAC seguro para fora deste
função. E vamos indicar o teorema de segurança aqui. Assim, suponha que temos um
'F' função que recebe as mensagens em 'X' e produz etiquetas em 'Y', então o MAC
que é derivado dessa PRF na verdade é um MAC segura. Em particular, se você olhar para
teorema de segurança aqui, você vai ver muito claramente os limites da época, em outras palavras
desde a PRF é seguro sabemos que essa quantidade aqui é insignificante. E assim se
quer esta quantidade para ser insignificante, é isso que queremos, queremos dizer que não
adversário pode derrotar o MAC 'Eu sub F', que implica que queremos que esta quantidade de
ser insignificante, em outras palavras, queremos que o espaço de saída a ser grandes. E assim por
exemplo, tomar um PRF que produz oitenta bits é perfeitamente bem. Que vai gerar
um 80 bits MAC e, portanto, a vantagem de qualquer adversário será no máximo
um sobre dois para o 80. Então, agora a prova deste teorema é muito simples, então vamos
apenas ir em frente e fazê-lo. Então, na verdade vamos começar dizendo que supor em vez de um
PRF temos uma função verdadeiramente aleatório partir do espaço mensagem para o espaço tag de modo que este
é apenas uma função aleatória de X para Y que é escolhido aleatoriamente do conjunto de
todas essas funções. Agora vamos ver se essa função pode nos dar um mac seguro. Então, o que
o adversário diz é: 'Eu quero um tag no M1 mensagem ". O que ele recebe de volta é o
tag que só acontece de ser a função avaliada no ponto M1. Observe que há
chave nenhuma aqui porque F é apenas uma função verdadeiramente aleatório de X a Y. E então o
adversário começa a escolher uma mensagem de M2 e ele obtém a marca de M2, que ele escolher
M3, M4 até MQ e ele obtém todas as tags correspondentes. Agora seu objetivo é
produzir um par de tags mensagem e dizemos que ele ganha, lembre-se que esta é uma
falsificação existencial, por outras palavras, antes de tudo T tem de ser igual a F de M Esta
significa que 'T' é uma tag válida para 'M' da mensagem. E em segundo lugar, o
mensagem 'M' tem que ser novo. Então, 'M' a mensagem de que é melhor não ser um dos M-um a MQ.
Mas vamos pensar sobre isso por um minuto, o que significa isso? Assim, o
adversário tem que ver o valor de uma função verdadeiramente aleatório nos pontos M-um para MQ
e agora ele? s supor para prever o valor desta função como algum ponto novo, M
No entanto, para uma função verdadeiramente aleatório, o valor da função no ponto M é
independente de seu valor no M-1 aponta para MQ. Então o melhor que o adversário pode fazer
em prever o valor da função no ponto M é apenas adivinhar o valor,
porque ele não tem informações sobre o F de M. E como resultado a sua vantagem se ele
adivinha o valor da função no ponto M, ele vai adivinhar direito com
probabilidade exatamente um sobre o Y. E, então, a marca que ele produziu será correta
com probabilidade exatamente um sobre o Y. Ok, mais uma vez que não tinha informações sobre o
valor da função de M e por isso o melhor que ele poderia fazer é adivinhar. E se adivinha,
ele vai acertar com probabilidade um sobre Y. E agora, claro, porque o
F de capital é uma função pseudo-aleatório O adversário vai se comportar o
mesmo se lhe dermos a função verdadeiramente aleatório ou a função pseudo-aleatório.
O adversário não pode dizer a diferença e, como resultado mesmo se usarmos um pseudo
função aleatória, o adversário vai ter vantagens em mais um sobre Y em
ganhar o jogo. Ok, então você pode ver exatamente o teorema de segurança, vamos
lá por apenas um segundo. Essencialmente, este é basicamente por isso que nós temos um termo de erro
de um sobre Y por causa do ataque de adivinhação e essa é a única maneira que o
atacante pode ganhar o jogo. Portanto, agora que sabemos que qualquer PRF seguro é também um seguro
MAC, já sabemos que temos o nosso primeiro exemplo MAC. Em particular, nós conhecemos
que AES, ou, pelo menos, acreditamos que AES é uma PRF segura, por conseguinte, uma vez que AES
tem dezesseis entradas de bytes, o direito do espaço mensagem para AES é 128 bits, o que
é de dezesseis bytes. Portanto, a cifra AES essencialmente nos dá um MAC que pode corresponder
mensagens que são exatamente dezesseis bytes. Ok, então esse é o nosso primeiro exemplo de uma
MAC. Mas agora a questão é se temos uma PRF para entradas pequenas como AES que só
atua em dezesseis bytes, podemos construir um MAC para mensagens grandes, que podem atuar em gigabytes
de dados? Às vezes eu chamo este problema, o McDonalds. Basicamente dada uma
MAC pequeno e vamos construir um Big Mac de fora. Em outras palavras, dado um MAC para pequena
mensagens e que construímos um MAC para mensagens grandes. Então, vamos olhar para dois
construções para o fazer. O primeiro exemplo é chamado um MAC CBC que novamente
leva PRF para pequenas mensagens como entrada e produz uma PRF para muito grande
mensagens. Como saídas. O segundo, vamos ver é HMAC que faz a mesma coisa
novamente leva um PRF para entradas pequenas e gera uma PRF para entradas muito grandes. Agora
os dois são utilizados em contextos muito diferentes. CBC-MAC é realmente muito
comumente usada no setor bancário. Por exemplo, há um sistema chamado
Automatic Clearing House, ACH, que os bancos usam para limpar cheques um com o outro e
sistema que, CBC-MAC, é utilizado para garantir a integridade dos controlos, tal como eles são
transferido de banco para banco. Na Internet, protocolos como SSL e IPsec e
SSH, aqueles HMAC todos os usos de integridade. Dois MACs diferentes e ia discuti-los
no próximo par de segmentos. E como eu disse também vai começar a partir de uma PRF para
pequenas mensagens e produzem PRF para mensagens que são gigabytes de comprimento e em
particular, eles podem tanto ser fundamentada com a AES como a cifra subjacente. Assim, o
último comentário eu quero fazer sobre estes baseado PRF MACs é que de fato o seu
saída pode ser truncado. Assim, suponha que temos um PRF que as saídas de N saídas bit. Assim
novamente para AES este seria um PRF que gera 128 bits como saídas. Sua fácil
lema para mostrar que de fato se você tiver um pouco PRF N se truncado, em outras palavras
, se você só saída primeiros bits de chave O resultado é também um seguro PRF e do
intuição aqui é se as grandes saídas PRF N bits de aleatoriedade para todas as entradas que você
dar à PRF então certamente cortar-lo e truncando-lo em pedaços T ainda é
vai parecer aleatória. O atacante agora recebe menos informações para seu trabalho de
distinguir as saídas de aleatório só se tornou mais difícil. Em outras palavras, se o
bit N PRF é seguro, então o bit menos de T N PRF, a PRF truncado, também
ser seguro. Portanto, este é um lema fácil e seguro já que qualquer PRF também nos dá uma
seguro MAC, o que isto significa é que se você me der um MAC que é baseado em uma PRF eo que eu
pode fazer é I pode truncar-lo em pedaços W, no entanto, por causa do termo de erro na
MAC teorema PRF baseado sabemos que truncando em pedaços W só será seguro
enquanto uma sobre dois para a W é negligenciável. Então, se você truncar a PRF para
apenas três bits, o MAC resultante não vai ser seguro. No entanto, se você
truncar dizer 80 bits ou talvez mesmo 64 bits, então o MAC resultante é ainda
vai ser um MAC segura. Ok, então a coisa a lembrar aqui é que, embora
usar AES para construir PRF maiores ea saída destes PRF vai ser de 128 bits,
isso não significa que o MAC se tem para produzir 128 etiquetas bits podemos sempre
truncar as saídas para 90 bits ou 80 bits, e como resultado, gostaríamos de obter ainda
MACs seguros, mas agora a marca de saída vai ser o tamanho mais razoável e não
têm que ser os completa de 128 bits. Ok, então no próximo segmento nós vamos olhar como
o CBC-MAC funciona.