WEBVTT 00:00:00.000 --> 00:00:04.052 Agora que sabemos o que MACs são, vamos em frente e construir nossos primeiros MACs seguras. 00:00:04.052 --> 00:00:08.469 Primeiro quero lembrá-lo que um MAC é um par de algoritmos. A primeira é uma sessão de autógrafos 00:00:08.469 --> 00:00:12.922 algoritmo que é dada uma mensagem e uma chave irá gerar uma etiqueta correspondente eo 00:00:12.922 --> 00:00:17.103 segundo é algoritmos de verificação é dada uma mensagem de chave e um tag enquanto 00:00:17.103 --> 00:00:21.736 saídas zero ou um, dependendo se a etiqueta é válido ou não. E nós dissemos que 00:00:21.736 --> 00:00:26.313 um MAC é seguro se é existencialmente falsificáveis em um ataque de mensagem escolhida. 00:00:26.313 --> 00:00:30.890 Em outras palavras, os atacantes permitem montar um ataque mensagem escolhida onde ele pode 00:00:30.890 --> 00:00:35.298 enviar mensagens arbitrárias de sua escolha e obter as marcas correspondentes para 00:00:35.298 --> 00:00:39.520 essas mensagens, e depois, apesar da capacidade de gerar etiquetas arbitrárias A 00:00:39.520 --> 00:00:43.616 atacante não pode criar um par de mensagem de marca-novo que não foi dado a ele 00:00:43.616 --> 00:00:47.976 durante o ataque mensagem escolhida. Ok então já vimos esta definição, no 00:00:47.976 --> 00:00:52.179 último segmento e agora a questão é como vamos construir MACs seguras? Assim, o primeiro 00:00:52.179 --> 00:00:57.217 exemplo, eu quero te dar é, basicamente, mostrando que qualquer PRF seguro diretamente dá 00:00:57.217 --> 00:01:01.952 -nos um MAC seguro também. Então vamos ver como fazemos. Assim, suponha que temos um pseudo 00:01:01.952 --> 00:01:06.808 função aleatória para a função pseudo-aleatório e tem entradas e saídas em X 00:01:06.808 --> 00:01:12.173 Y. E vamos definir o MAC seguinte. Então, a nossa forma de assinar 'M' é basicamente uma mensagem 00:01:12.173 --> 00:01:17.182 , basta avaliar a função de 'M' o ponto Assim, a tag para a mensagem M é 00:01:17.182 --> 00:01:21.350 simplesmente o valor da função no ponto M e em seguida, a maneira como verificar uma 00:01:21.350 --> 00:01:26.006 mensagem para que o par é por recomputing o valor da função na mensagem M e 00:01:26.006 --> 00:01:30.283 verificação se que é igual à tag que nos foi dado. Nós dizemos que sim, se assim e nós 00:01:30.283 --> 00:01:34.681 rejeitar o contrário. Então aqui você tem basicamente em imagens que, quando Alice quer 00:01:34.681 --> 00:01:39.023 para enviar uma mensagem para Bob, ela calcula uma tag pelo valor da PRF e então ela 00:01:39.023 --> 00:01:43.252 acrescenta esta tag com a mensagem, Bob recebe o par guia correspondente, ele 00:01:43.252 --> 00:01:47.820 recomputes o valor da função e testa se a etiqueta dada é realmente 00:01:47.820 --> 00:01:52.730 igual ao valor da função no ponto M. Então, vamos olhar para um mau exemplo de 00:01:52.730 --> 00:01:57.832 esta instrução. E assim supor que temos uma função pseudo-aleatório que acontece 00:01:57.832 --> 00:02:02.873 para a saída de apenas 10 bits. Ok, então esta é uma função pseudo-aleatória bem e isso só 00:02:02.873 --> 00:02:07.668 Acontece que para 'M' qualquer mensagem que ele só gera 10 valor bits. A minha pergunta 00:02:07.668 --> 00:02:12.463 para você é se usar 'F' esta função para construir um MAC, é que vai ser um 00:02:12.463 --> 00:02:17.184 MAC é seguro? Portanto, a resposta é não, este MAC é inseguro. Em particular, porque o 00:02:17.184 --> 00:02:21.471 tags são muito curta. Por isso, considero o adversário seguinte simples. O que o 00:02:21.471 --> 00:02:26.119 adversário vai fazer é simplesmente escolher uma mensagem arbitrária M e apenas acho que a 00:02:26.119 --> 00:02:30.768 valor do MAC para que a mensagem particular. Agora, porque a etiqueta só é 10 00:02:30.768 --> 00:02:35.175 bits de comprimento, o adversário tem a chance de um em cada dois a 10 em adivinhar o MAC 00:02:35.175 --> 00:02:40.004 corretamente. Em outras palavras, a vantagem de o adversário supondo, um distintamente 00:02:40.004 --> 00:02:44.351 palpites tag aleatória para uma determinada mensagem. Que o adversário vai ter um 00:02:44.351 --> 00:02:48.898 vantagem contra o mac que é basicamente um espaço de dois a dez, que é uma mais 00:02:48.898 --> 00:02:52.962 mil 24 e que é definitivamente não negligenciável. Assim, o adversário 00:02:52.962 --> 00:02:57.348 basicamente vai conseguir forjar o mac em uma determinada mensagem com probabilidade um 00:02:57.348 --> 00:03:01.841 em mil que é inseguro. No entanto, acontece que este é o único exemplo que 00:03:01.841 --> 00:03:06.280 onde as coisas podem dar errado, só quando a saída da função é pequena lata coisas 00:03:06.280 --> 00:03:10.536 dar errado. Se a saída do PRF é grande, então obtemos um MAC seguro para fora deste 00:03:10.536 --> 00:03:14.344 função. E vamos indicar o teorema de segurança aqui. Assim, suponha que temos um 00:03:14.344 --> 00:03:18.257 'F' função que recebe as mensagens em 'X' e produz etiquetas em 'Y', então o MAC 00:03:18.257 --> 00:03:22.588 que é derivado dessa PRF na verdade é um MAC segura. Em particular, se você olhar para 00:03:22.588 --> 00:03:26.804 teorema de segurança aqui, você vai ver muito claramente os limites da época, em outras palavras 00:03:26.804 --> 00:03:31.179 desde a PRF é seguro sabemos que essa quantidade aqui é insignificante. E assim se 00:03:31.179 --> 00:03:35.395 quer esta quantidade para ser insignificante, é isso que queremos, queremos dizer que não 00:03:35.395 --> 00:03:39.664 adversário pode derrotar o MAC 'Eu sub F', que implica que queremos que esta quantidade de 00:03:39.664 --> 00:03:43.722 ser insignificante, em outras palavras, queremos que o espaço de saída a ser grandes. E assim por 00:03:43.722 --> 00:03:48.096 exemplo, tomar um PRF que produz oitenta bits é perfeitamente bem. Que vai gerar 00:03:48.096 --> 00:03:52.102 um 80 bits MAC e, portanto, a vantagem de qualquer adversário será no máximo 00:03:52.102 --> 00:03:56.521 um sobre dois para o 80. Então, agora a prova deste teorema é muito simples, então vamos 00:03:56.521 --> 00:04:00.906 apenas ir em frente e fazê-lo. Então, na verdade vamos começar dizendo que supor em vez de um 00:04:00.906 --> 00:04:05.446 PRF temos uma função verdadeiramente aleatório partir do espaço mensagem para o espaço tag de modo que este 00:04:05.446 --> 00:04:10.087 é apenas uma função aleatória de X para Y que é escolhido aleatoriamente do conjunto de 00:04:10.087 --> 00:04:14.966 todas essas funções. Agora vamos ver se essa função pode nos dar um mac seguro. Então, o que 00:04:14.966 --> 00:04:19.551 o adversário diz é: 'Eu quero um tag no M1 mensagem ". O que ele recebe de volta é o 00:04:19.551 --> 00:04:24.157 tag que só acontece de ser a função avaliada no ponto M1. Observe que há 00:04:24.157 --> 00:04:28.489 chave nenhuma aqui porque F é apenas uma função verdadeiramente aleatório de X a Y. E então o 00:04:28.489 --> 00:04:33.096 adversário começa a escolher uma mensagem de M2 e ele obtém a marca de M2, que ele escolher 00:04:33.096 --> 00:04:37.264 M3, M4 até MQ e ele obtém todas as tags correspondentes. Agora seu objetivo é 00:04:37.264 --> 00:04:41.432 produzir um par de tags mensagem e dizemos que ele ganha, lembre-se que esta é uma 00:04:41.432 --> 00:04:45.891 falsificação existencial, por outras palavras, antes de tudo T tem de ser igual a F de M Esta 00:04:45.891 --> 00:04:49.968 significa que 'T' é uma tag válida para 'M' da mensagem. E em segundo lugar, o 00:04:49.968 --> 00:04:54.685 mensagem 'M' tem que ser novo. Então, 'M' a mensagem de que é melhor não ser um dos M-um a MQ. 00:04:54.685 --> 00:04:58.879 Mas vamos pensar sobre isso por um minuto, o que significa isso? Assim, o 00:04:58.879 --> 00:05:03.830 adversário tem que ver o valor de uma função verdadeiramente aleatório nos pontos M-um para MQ 00:05:03.830 --> 00:05:08.800 e agora ele? s supor para prever o valor desta função como algum ponto novo, M 00:05:08.800 --> 00:05:13.411 No entanto, para uma função verdadeiramente aleatório, o valor da função no ponto M é 00:05:13.411 --> 00:05:18.195 independente de seu valor no M-1 aponta para MQ. Então o melhor que o adversário pode fazer 00:05:18.195 --> 00:05:22.749 em prever o valor da função no ponto M é apenas adivinhar o valor, 00:05:22.749 --> 00:05:27.302 porque ele não tem informações sobre o F de M. E como resultado a sua vantagem se ele 00:05:27.302 --> 00:05:31.625 adivinha o valor da função no ponto M, ele vai adivinhar direito com 00:05:31.625 --> 00:05:36.294 probabilidade exatamente um sobre o Y. E, então, a marca que ele produziu será correta 00:05:36.294 --> 00:05:40.582 com probabilidade exatamente um sobre o Y. Ok, mais uma vez que não tinha informações sobre o 00:05:40.582 --> 00:05:44.801 valor da função de M e por isso o melhor que ele poderia fazer é adivinhar. E se adivinha, 00:05:44.801 --> 00:05:49.347 ele vai acertar com probabilidade um sobre Y. E agora, claro, porque o 00:05:49.347 --> 00:05:54.420 F de capital é uma função pseudo-aleatório O adversário vai se comportar o 00:05:54.420 --> 00:05:58.565 mesmo se lhe dermos a função verdadeiramente aleatório ou a função pseudo-aleatório. 00:05:58.565 --> 00:06:02.659 O adversário não pode dizer a diferença e, como resultado mesmo se usarmos um pseudo 00:06:02.659 --> 00:06:06.600 função aleatória, o adversário vai ter vantagens em mais um sobre Y em 00:06:06.600 --> 00:06:10.774 ganhar o jogo. Ok, então você pode ver exatamente o teorema de segurança, vamos 00:06:10.774 --> 00:06:15.561 lá por apenas um segundo. Essencialmente, este é basicamente por isso que nós temos um termo de erro 00:06:15.561 --> 00:06:20.005 de um sobre Y por causa do ataque de adivinhação e essa é a única maneira que o 00:06:20.005 --> 00:06:24.734 atacante pode ganhar o jogo. Portanto, agora que sabemos que qualquer PRF seguro é também um seguro 00:06:24.734 --> 00:06:29.122 MAC, já sabemos que temos o nosso primeiro exemplo MAC. Em particular, nós conhecemos 00:06:29.122 --> 00:06:33.680 que AES, ou, pelo menos, acreditamos que AES é uma PRF segura, por conseguinte, uma vez que AES 00:06:33.680 --> 00:06:38.011 tem dezesseis entradas de bytes, o direito do espaço mensagem para AES é 128 bits, o que 00:06:38.011 --> 00:06:43.212 é de dezesseis bytes. Portanto, a cifra AES essencialmente nos dá um MAC que pode corresponder 00:06:43.212 --> 00:06:48.140 mensagens que são exatamente dezesseis bytes. Ok, então esse é o nosso primeiro exemplo de uma 00:06:48.140 --> 00:06:53.257 MAC. Mas agora a questão é se temos uma PRF para entradas pequenas como AES que só 00:06:53.257 --> 00:06:58.564 atua em dezesseis bytes, podemos construir um MAC para mensagens grandes, que podem atuar em gigabytes 00:06:58.564 --> 00:07:02.066 de dados? Às vezes eu chamo este problema, o McDonalds. Basicamente dada uma 00:07:02.066 --> 00:07:05.871 MAC pequeno e vamos construir um Big Mac de fora. Em outras palavras, dado um MAC para pequena 00:07:05.871 --> 00:07:10.234 mensagens e que construímos um MAC para mensagens grandes. Então, vamos olhar para dois 00:07:10.234 --> 00:07:14.835 construções para o fazer. O primeiro exemplo é chamado um MAC CBC que novamente 00:07:14.835 --> 00:07:19.315 leva PRF para pequenas mensagens como entrada e produz uma PRF para muito grande 00:07:19.315 --> 00:07:23.686 mensagens. Como saídas. O segundo, vamos ver é HMAC que faz a mesma coisa 00:07:23.686 --> 00:07:28.278 novamente leva um PRF para entradas pequenas e gera uma PRF para entradas muito grandes. Agora 00:07:28.278 --> 00:07:32.050 os dois são utilizados em contextos muito diferentes. CBC-MAC é realmente muito 00:07:32.050 --> 00:07:36.315 comumente usada no setor bancário. Por exemplo, há um sistema chamado 00:07:36.315 --> 00:07:40.797 Automatic Clearing House, ACH, que os bancos usam para limpar cheques um com o outro e 00:07:40.797 --> 00:07:44.788 sistema que, CBC-MAC, é utilizado para garantir a integridade dos controlos, tal como eles são 00:07:44.788 --> 00:07:49.107 transferido de banco para banco. Na Internet, protocolos como SSL e IPsec e 00:07:49.107 --> 00:07:53.173 SSH, aqueles HMAC todos os usos de integridade. Dois MACs diferentes e ia discuti-los 00:07:53.173 --> 00:07:57.086 no próximo par de segmentos. E como eu disse também vai começar a partir de uma PRF para 00:07:57.086 --> 00:08:01.274 pequenas mensagens e produzem PRF para mensagens que são gigabytes de comprimento e em 00:08:01.274 --> 00:08:06.043 particular, eles podem tanto ser fundamentada com a AES como a cifra subjacente. Assim, o 00:08:06.043 --> 00:08:10.597 último comentário eu quero fazer sobre estes baseado PRF MACs é que de fato o seu 00:08:10.597 --> 00:08:15.269 saída pode ser truncado. Assim, suponha que temos um PRF que as saídas de N saídas bit. Assim 00:08:15.269 --> 00:08:19.941 novamente para AES este seria um PRF que gera 128 bits como saídas. Sua fácil 00:08:19.941 --> 00:08:24.909 lema para mostrar que de fato se você tiver um pouco PRF N se truncado, em outras palavras 00:08:24.909 --> 00:08:31.062 , se você só saída primeiros bits de chave O resultado é também um seguro PRF e do 00:08:31.062 --> 00:08:36.529 intuição aqui é se as grandes saídas PRF N bits de aleatoriedade para todas as entradas que você 00:08:36.529 --> 00:08:42.059 dar à PRF então certamente cortar-lo e truncando-lo em pedaços T ainda é 00:08:42.059 --> 00:08:46.572 vai parecer aleatória. O atacante agora recebe menos informações para seu trabalho de 00:08:46.572 --> 00:08:51.657 distinguir as saídas de aleatório só se tornou mais difícil. Em outras palavras, se o 00:08:51.657 --> 00:08:56.742 bit N PRF é seguro, então o bit menos de T N PRF, a PRF truncado, também 00:08:56.742 --> 00:09:01.177 ser seguro. Portanto, este é um lema fácil e seguro já que qualquer PRF também nos dá uma 00:09:01.177 --> 00:09:05.993 seguro MAC, o que isto significa é que se você me der um MAC que é baseado em uma PRF eo que eu 00:09:05.993 --> 00:09:10.686 pode fazer é I pode truncar-lo em pedaços W, no entanto, por causa do termo de erro na 00:09:10.864 --> 00:09:15.379 MAC teorema PRF baseado sabemos que truncando em pedaços W só será seguro 00:09:15.379 --> 00:09:19.954 enquanto uma sobre dois para a W é negligenciável. Então, se você truncar a PRF para 00:09:19.954 --> 00:09:24.410 apenas três bits, o MAC resultante não vai ser seguro. No entanto, se você 00:09:24.410 --> 00:09:29.222 truncar dizer 80 bits ou talvez mesmo 64 bits, então o MAC resultante é ainda 00:09:29.222 --> 00:09:33.974 vai ser um MAC segura. Ok, então a coisa a lembrar aqui é que, embora 00:09:33.974 --> 00:09:39.235 usar AES para construir PRF maiores ea saída destes PRF vai ser de 128 bits, 00:09:39.235 --> 00:09:44.115 isso não significa que o MAC se tem para produzir 128 etiquetas bits podemos sempre 00:09:44.115 --> 00:09:48.550 truncar as saídas para 90 bits ou 80 bits, e como resultado, gostaríamos de obter ainda 00:09:48.550 --> 00:09:53.097 MACs seguros, mas agora a marca de saída vai ser o tamanho mais razoável e não 00:09:53.097 --> 00:09:57.702 têm que ser os completa de 128 bits. Ok, então no próximo segmento nós vamos olhar como 00:09:57.702 --> 00:09:58.726 o CBC-MAC funciona.