Macs baseados em PRF (10 min)

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.