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.