0:00:00.000,0:00:04.052
Agora que sabemos o que MACs são, vamos em frente e construir nossos primeiros MACs seguras.

0:00:04.052,0:00:08.469
Primeiro quero lembrá-lo que um MAC é um par de algoritmos. A primeira é uma sessão de autógrafos

0:00:08.469,0:00:12.922
algoritmo que é dada uma mensagem e uma chave irá gerar uma etiqueta correspondente eo

0:00:12.922,0:00:17.103
segundo é algoritmos de verificação é dada uma mensagem de chave e um tag enquanto

0:00:17.103,0:00:21.736
saídas zero ou um, dependendo se a etiqueta é válido ou não. E nós dissemos que

0:00:21.736,0:00:26.313
um MAC é seguro se é existencialmente falsificáveis em um ataque de mensagem escolhida.

0:00:26.313,0:00:30.890
Em outras palavras, os atacantes permitem montar um ataque mensagem escolhida onde ele pode

0:00:30.890,0:00:35.298
enviar mensagens arbitrárias de sua escolha e obter as marcas correspondentes para

0:00:35.298,0:00:39.520
essas mensagens, e depois, apesar da capacidade de gerar etiquetas arbitrárias A

0:00:39.520,0:00:43.616
atacante não pode criar um par de mensagem de marca-novo que não foi dado a ele

0:00:43.616,0:00:47.976
durante o ataque mensagem escolhida. Ok então já vimos esta definição, no

0:00:47.976,0:00:52.179
último segmento e agora a questão é como vamos construir MACs seguras? Assim, o primeiro

0:00:52.179,0:00:57.217
exemplo, eu quero te dar é, basicamente, mostrando que qualquer PRF seguro diretamente dá

0:00:57.217,0:01:01.952
-nos um MAC seguro também. Então vamos ver como fazemos. Assim, suponha que temos um pseudo

0:01:01.952,0:01:06.808
função aleatória para a função pseudo-aleatório e tem entradas e saídas em X

0:01:06.808,0:01:12.173
Y. E vamos definir o MAC seguinte. Então, a nossa forma de assinar 'M' é basicamente uma mensagem

0:01:12.173,0:01:17.182
, basta avaliar a função de 'M' o ponto Assim, a tag para a mensagem M é

0:01:17.182,0:01:21.350
simplesmente o valor da função no ponto M e em seguida, a maneira como verificar uma

0:01:21.350,0:01:26.006
mensagem para que o par é por recomputing o valor da função na mensagem M e

0:01:26.006,0:01:30.283
verificação se que é igual à tag que nos foi dado. Nós dizemos que sim, se assim e nós

0:01:30.283,0:01:34.681
rejeitar o contrário. Então aqui você tem basicamente em imagens que, quando Alice quer

0:01:34.681,0:01:39.023
para enviar uma mensagem para Bob, ela calcula uma tag pelo valor da PRF e então ela

0:01:39.023,0:01:43.252
acrescenta esta tag com a mensagem, Bob recebe o par guia correspondente, ele

0:01:43.252,0:01:47.820
recomputes o valor da função e testa se a etiqueta dada é realmente

0:01:47.820,0:01:52.730
igual ao valor da função no ponto M. Então, vamos olhar para um mau exemplo de

0:01:52.730,0:01:57.832
esta instrução. E assim supor que temos uma função pseudo-aleatório que acontece

0:01:57.832,0: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ó

0:02:02.873,0:02:07.668
Acontece que para 'M' qualquer mensagem que ele só gera 10 valor bits. A minha pergunta

0:02:07.668,0:02:12.463
para você é se usar 'F' esta função para construir um MAC, é que vai ser um

0:02:12.463,0:02:17.184
MAC é seguro? Portanto, a resposta é não, este MAC é inseguro. Em particular, porque o

0:02:17.184,0:02:21.471
tags são muito curta. Por isso, considero o adversário seguinte simples. O que o

0:02:21.471,0:02:26.119
adversário vai fazer é simplesmente escolher uma mensagem arbitrária M e apenas acho que a

0:02:26.119,0:02:30.768
valor do MAC para que a mensagem particular. Agora, porque a etiqueta só é 10

0:02:30.768,0:02:35.175
bits de comprimento, o adversário tem a chance de um em cada dois a 10 em adivinhar o MAC

0:02:35.175,0:02:40.004
corretamente. Em outras palavras, a vantagem de o adversário supondo, um distintamente

0:02:40.004,0:02:44.351
palpites tag aleatória para uma determinada mensagem. Que o adversário vai ter um

0:02:44.351,0:02:48.898
vantagem contra o mac que é basicamente um espaço de dois a dez, que é uma mais

0:02:48.898,0:02:52.962
mil 24 e que é definitivamente não negligenciável. Assim, o adversário

0:02:52.962,0:02:57.348
basicamente vai conseguir forjar o mac em uma determinada mensagem com probabilidade um

0:02:57.348,0:03:01.841
em mil que é inseguro. No entanto, acontece que este é o único exemplo que

0:03:01.841,0:03:06.280
onde as coisas podem dar errado, só quando a saída da função é pequena lata coisas

0:03:06.280,0:03:10.536
dar errado. Se a saída do PRF é grande, então obtemos um MAC seguro para fora deste

0:03:10.536,0:03:14.344
função. E vamos indicar o teorema de segurança aqui. Assim, suponha que temos um

0:03:14.344,0:03:18.257
'F' função que recebe as mensagens em 'X' e produz etiquetas em 'Y', então o MAC

0:03:18.257,0:03:22.588
que é derivado dessa PRF na verdade é um MAC segura. Em particular, se você olhar para

0:03:22.588,0:03:26.804
teorema de segurança aqui, você vai ver muito claramente os limites da época, em outras palavras

0:03:26.804,0:03:31.179
desde a PRF é seguro sabemos que essa quantidade aqui é insignificante. E assim se

0:03:31.179,0:03:35.395
quer esta quantidade para ser insignificante, é isso que queremos, queremos dizer que não

0:03:35.395,0:03:39.664
adversário pode derrotar o MAC 'Eu sub F', que implica que queremos que esta quantidade de

0:03:39.664,0:03:43.722
ser insignificante, em outras palavras, queremos que o espaço de saída a ser grandes. E assim por

0:03:43.722,0:03:48.096
exemplo, tomar um PRF que produz oitenta bits é perfeitamente bem. Que vai gerar

0:03:48.096,0:03:52.102
um 80 bits MAC e, portanto, a vantagem de qualquer adversário será no máximo

0:03:52.102,0:03:56.521
um sobre dois para o 80. Então, agora a prova deste teorema é muito simples, então vamos

0:03:56.521,0:04:00.906
apenas ir em frente e fazê-lo. Então, na verdade vamos começar dizendo que supor em vez de um

0:04:00.906,0: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

0:04:05.446,0:04:10.087
é apenas uma função aleatória de X para Y que é escolhido aleatoriamente do conjunto de

0:04:10.087,0:04:14.966
todas essas funções. Agora vamos ver se essa função pode nos dar um mac seguro. Então, o que

0:04:14.966,0:04:19.551
o adversário diz é: 'Eu quero um tag no M1 mensagem ". O que ele recebe de volta é o

0:04:19.551,0:04:24.157
tag que só acontece de ser a função avaliada no ponto M1. Observe que há

0:04:24.157,0:04:28.489
chave nenhuma aqui porque F é apenas uma função verdadeiramente aleatório de X a Y. E então o

0:04:28.489,0:04:33.096
adversário começa a escolher uma mensagem de M2 e ele obtém a marca de M2, que ele escolher

0:04:33.096,0:04:37.264
M3, M4 até MQ e ele obtém todas as tags correspondentes. Agora seu objetivo é

0:04:37.264,0:04:41.432
produzir um par de tags mensagem e dizemos que ele ganha, lembre-se que esta é uma

0:04:41.432,0:04:45.891
falsificação existencial, por outras palavras, antes de tudo T tem de ser igual a F de M Esta

0:04:45.891,0:04:49.968
significa que 'T' é uma tag válida para 'M' da mensagem. E em segundo lugar, o

0:04:49.968,0: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.

0:04:54.685,0:04:58.879
Mas vamos pensar sobre isso por um minuto, o que significa isso? Assim, o

0:04:58.879,0:05:03.830
adversário tem que ver o valor de uma função verdadeiramente aleatório nos pontos M-um para MQ

0:05:03.830,0:05:08.800
e agora ele? s supor para prever o valor desta função como algum ponto novo, M

0:05:08.800,0:05:13.411
No entanto, para uma função verdadeiramente aleatório, o valor da função no ponto M é

0:05:13.411,0:05:18.195
independente de seu valor no M-1 aponta para MQ. Então o melhor que o adversário pode fazer

0:05:18.195,0:05:22.749
em prever o valor da função no ponto M é apenas adivinhar o valor,

0:05:22.749,0:05:27.302
porque ele não tem informações sobre o F de M. E como resultado a sua vantagem se ele

0:05:27.302,0:05:31.625
adivinha o valor da função no ponto M, ele vai adivinhar direito com

0:05:31.625,0:05:36.294
probabilidade exatamente um sobre o Y. E, então, a marca que ele produziu será correta

0:05:36.294,0:05:40.582
com probabilidade exatamente um sobre o Y. Ok, mais uma vez que não tinha informações sobre o

0:05:40.582,0:05:44.801
valor da função de M e por isso o melhor que ele poderia fazer é adivinhar. E se adivinha,

0:05:44.801,0:05:49.347
ele vai acertar com probabilidade um sobre Y. E agora, claro, porque o

0:05:49.347,0:05:54.420
F de capital é uma função pseudo-aleatório O adversário vai se comportar o

0:05:54.420,0:05:58.565
mesmo se lhe dermos a função verdadeiramente aleatório ou a função pseudo-aleatório.

0:05:58.565,0:06:02.659
O adversário não pode dizer a diferença e, como resultado mesmo se usarmos um pseudo

0:06:02.659,0:06:06.600
função aleatória, o adversário vai ter vantagens em mais um sobre Y em

0:06:06.600,0:06:10.774
ganhar o jogo. Ok, então você pode ver exatamente o teorema de segurança, vamos

0:06:10.774,0:06:15.561
lá por apenas um segundo. Essencialmente, este é basicamente por isso que nós temos um termo de erro

0:06:15.561,0:06:20.005
de um sobre Y por causa do ataque de adivinhação e essa é a única maneira que o

0:06:20.005,0:06:24.734
atacante pode ganhar o jogo. Portanto, agora que sabemos que qualquer PRF seguro é também um seguro

0:06:24.734,0:06:29.122
MAC, já sabemos que temos o nosso primeiro exemplo MAC. Em particular, nós conhecemos

0:06:29.122,0:06:33.680
que AES, ou, pelo menos, acreditamos que AES é uma PRF segura, por conseguinte, uma vez que AES

0:06:33.680,0:06:38.011
tem dezesseis entradas de bytes, o direito do espaço mensagem para AES é 128 bits, o que

0:06:38.011,0:06:43.212
é de dezesseis bytes. Portanto, a cifra AES essencialmente nos dá um MAC que pode corresponder

0:06:43.212,0:06:48.140
mensagens que são exatamente dezesseis bytes. Ok, então esse é o nosso primeiro exemplo de uma

0:06:48.140,0:06:53.257
MAC. Mas agora a questão é se temos uma PRF para entradas pequenas como AES que só

0:06:53.257,0:06:58.564
atua em dezesseis bytes, podemos construir um MAC para mensagens grandes, que podem atuar em gigabytes

0:06:58.564,0:07:02.066
de dados? Às vezes eu chamo este problema, o McDonalds. Basicamente dada uma

0:07:02.066,0:07:05.871
MAC pequeno e vamos construir um Big Mac de fora. Em outras palavras, dado um MAC para pequena

0:07:05.871,0:07:10.234
mensagens e que construímos um MAC para mensagens grandes. Então, vamos olhar para dois

0:07:10.234,0:07:14.835
construções para o fazer. O primeiro exemplo é chamado um MAC CBC que novamente

0:07:14.835,0:07:19.315
leva PRF para pequenas mensagens como entrada e produz uma PRF para muito grande

0:07:19.315,0:07:23.686
mensagens. Como saídas. O segundo, vamos ver é HMAC que faz a mesma coisa

0:07:23.686,0:07:28.278
novamente leva um PRF para entradas pequenas e gera uma PRF para entradas muito grandes. Agora

0:07:28.278,0:07:32.050
os dois são utilizados em contextos muito diferentes. CBC-MAC é realmente muito

0:07:32.050,0:07:36.315
comumente usada no setor bancário. Por exemplo, há um sistema chamado

0:07:36.315,0:07:40.797
Automatic Clearing House, ACH, que os bancos usam para limpar cheques um com o outro e

0:07:40.797,0:07:44.788
sistema que, CBC-MAC, é utilizado para garantir a integridade dos controlos, tal como eles são

0:07:44.788,0:07:49.107
transferido de banco para banco. Na Internet, protocolos como SSL e IPsec e

0:07:49.107,0:07:53.173
SSH, aqueles HMAC todos os usos de integridade. Dois MACs diferentes e ia discuti-los

0:07:53.173,0:07:57.086
no próximo par de segmentos. E como eu disse também vai começar a partir de uma PRF para

0:07:57.086,0:08:01.274
pequenas mensagens e produzem PRF para mensagens que são gigabytes de comprimento e em

0:08:01.274,0:08:06.043
particular, eles podem tanto ser fundamentada com a AES como a cifra subjacente. Assim, o

0:08:06.043,0:08:10.597
último comentário eu quero fazer sobre estes baseado PRF MACs é que de fato o seu

0:08:10.597,0:08:15.269
saída pode ser truncado. Assim, suponha que temos um PRF que as saídas de N saídas bit. Assim

0:08:15.269,0:08:19.941
novamente para AES este seria um PRF que gera 128 bits como saídas. Sua fácil

0:08:19.941,0:08:24.909
lema para mostrar que de fato se você tiver um pouco PRF N se truncado, em outras palavras

0:08:24.909,0:08:31.062
, se você só saída primeiros bits de chave O resultado é também um seguro PRF e do

0:08:31.062,0:08:36.529
intuição aqui é se as grandes saídas PRF N bits de aleatoriedade para todas as entradas que você

0:08:36.529,0:08:42.059
dar à PRF então certamente cortar-lo e truncando-lo em pedaços T ainda é

0:08:42.059,0:08:46.572
vai parecer aleatória. O atacante agora recebe menos informações para seu trabalho de

0:08:46.572,0:08:51.657
distinguir as saídas de aleatório só se tornou mais difícil. Em outras palavras, se o

0:08:51.657,0:08:56.742
bit N PRF é seguro, então o bit menos de T N PRF, a PRF truncado, também

0:08:56.742,0:09:01.177
ser seguro. Portanto, este é um lema fácil e seguro já que qualquer PRF também nos dá uma

0:09:01.177,0:09:05.993
seguro MAC, o que isto significa é que se você me der um MAC que é baseado em uma PRF eo que eu

0:09:05.993,0:09:10.686
pode fazer é I pode truncar-lo em pedaços W, no entanto, por causa do termo de erro na

0:09:10.864,0:09:15.379
MAC teorema PRF baseado sabemos que truncando em pedaços W só será seguro

0:09:15.379,0:09:19.954
enquanto uma sobre dois para a W é negligenciável. Então, se você truncar a PRF para

0:09:19.954,0:09:24.410
apenas três bits, o MAC resultante não vai ser seguro. No entanto, se você

0:09:24.410,0:09:29.222
truncar dizer 80 bits ou talvez mesmo 64 bits, então o MAC resultante é ainda

0:09:29.222,0:09:33.974
vai ser um MAC segura. Ok, então a coisa a lembrar aqui é que, embora

0:09:33.974,0:09:39.235
usar AES para construir PRF maiores ea saída destes PRF vai ser de 128 bits,

0:09:39.235,0:09:44.115
isso não significa que o MAC se tem para produzir 128 etiquetas bits podemos sempre

0:09:44.115,0:09:48.550
truncar as saídas para 90 bits ou 80 bits, e como resultado, gostaríamos de obter ainda

0:09:48.550,0:09:53.097
MACs seguros, mas agora a marca de saída vai ser o tamanho mais razoável e não

0:09:53.097,0:09:57.702
têm que ser os completa de 128 bits. Ok, então no próximo segmento nós vamos olhar como

0:09:57.702,0:09:58.726
o CBC-MAC funciona.