1
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.

2
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

3
00:00:08,469 --> 00:00:12,922
algoritmo que é dada uma mensagem e uma chave irá gerar uma etiqueta correspondente eo

4
00:00:12,922 --> 00:00:17,103
segundo é algoritmos de verificação é dada uma mensagem de chave e um tag enquanto

5
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

6
00:00:21,736 --> 00:00:26,313
um MAC é seguro se é existencialmente falsificáveis em um ataque de mensagem escolhida.

7
00:00:26,313 --> 00:00:30,890
Em outras palavras, os atacantes permitem montar um ataque mensagem escolhida onde ele pode

8
00:00:30,890 --> 00:00:35,298
enviar mensagens arbitrárias de sua escolha e obter as marcas correspondentes para

9
00:00:35,298 --> 00:00:39,520
essas mensagens, e depois, apesar da capacidade de gerar etiquetas arbitrárias A

10
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

11
00:00:43,616 --> 00:00:47,976
durante o ataque mensagem escolhida. Ok então já vimos esta definição, no

12
00:00:47,976 --> 00:00:52,179
último segmento e agora a questão é como vamos construir MACs seguras? Assim, o primeiro

13
00:00:52,179 --> 00:00:57,217
exemplo, eu quero te dar é, basicamente, mostrando que qualquer PRF seguro diretamente dá

14
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

15
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

16
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

17
00:01:12,173 --> 00:01:17,182
, basta avaliar a função de 'M' o ponto Assim, a tag para a mensagem M é

18
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

19
00:01:21,350 --> 00:01:26,006
mensagem para que o par é por recomputing o valor da função na mensagem M e

20
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

21
00:01:30,283 --> 00:01:34,681
rejeitar o contrário. Então aqui você tem basicamente em imagens que, quando Alice quer

22
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

23
00:01:39,023 --> 00:01:43,252
acrescenta esta tag com a mensagem, Bob recebe o par guia correspondente, ele

24
00:01:43,252 --> 00:01:47,820
recomputes o valor da função e testa se a etiqueta dada é realmente

25
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

26
00:01:52,730 --> 00:01:57,832
esta instrução. E assim supor que temos uma função pseudo-aleatório que acontece

27
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ó

28
00:02:02,873 --> 00:02:07,668
Acontece que para 'M' qualquer mensagem que ele só gera 10 valor bits. A minha pergunta

29
00:02:07,668 --> 00:02:12,463
para você é se usar 'F' esta função para construir um MAC, é que vai ser um

30
00:02:12,463 --> 00:02:17,184
MAC é seguro? Portanto, a resposta é não, este MAC é inseguro. Em particular, porque o

31
00:02:17,184 --> 00:02:21,471
tags são muito curta. Por isso, considero o adversário seguinte simples. O que o

32
00:02:21,471 --> 00:02:26,119
adversário vai fazer é simplesmente escolher uma mensagem arbitrária M e apenas acho que a

33
00:02:26,119 --> 00:02:30,768
valor do MAC para que a mensagem particular. Agora, porque a etiqueta só é 10

34
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

35
00:02:35,175 --> 00:02:40,004
corretamente. Em outras palavras, a vantagem de o adversário supondo, um distintamente

36
00:02:40,004 --> 00:02:44,351
palpites tag aleatória para uma determinada mensagem. Que o adversário vai ter um

37
00:02:44,351 --> 00:02:48,898
vantagem contra o mac que é basicamente um espaço de dois a dez, que é uma mais

38
00:02:48,898 --> 00:02:52,962
mil 24 e que é definitivamente não negligenciável. Assim, o adversário

39
00:02:52,962 --> 00:02:57,348
basicamente vai conseguir forjar o mac em uma determinada mensagem com probabilidade um

40
00:02:57,348 --> 00:03:01,841
em mil que é inseguro. No entanto, acontece que este é o único exemplo que

41
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

42
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

43
00:03:10,536 --> 00:03:14,344
função. E vamos indicar o teorema de segurança aqui. Assim, suponha que temos um

44
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

45
00:03:18,257 --> 00:03:22,588
que é derivado dessa PRF na verdade é um MAC segura. Em particular, se você olhar para

46
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

47
00:03:26,804 --> 00:03:31,179
desde a PRF é seguro sabemos que essa quantidade aqui é insignificante. E assim se

48
00:03:31,179 --> 00:03:35,395
quer esta quantidade para ser insignificante, é isso que queremos, queremos dizer que não

49
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

50
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

51
00:03:43,722 --> 00:03:48,096
exemplo, tomar um PRF que produz oitenta bits é perfeitamente bem. Que vai gerar

52
00:03:48,096 --> 00:03:52,102
um 80 bits MAC e, portanto, a vantagem de qualquer adversário será no máximo

53
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

54
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

55
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

56
00:04:05,446 --> 00:04:10,087
é apenas uma função aleatória de X para Y que é escolhido aleatoriamente do conjunto de

57
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

58
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

59
00:04:19,551 --> 00:04:24,157
tag que só acontece de ser a função avaliada no ponto M1. Observe que há

60
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

61
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

62
00:04:33,096 --> 00:04:37,264
M3, M4 até MQ e ele obtém todas as tags correspondentes. Agora seu objetivo é

63
00:04:37,264 --> 00:04:41,432
produzir um par de tags mensagem e dizemos que ele ganha, lembre-se que esta é uma

64
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

65
00:04:45,891 --> 00:04:49,968
significa que 'T' é uma tag válida para 'M' da mensagem. E em segundo lugar, o

66
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.

67
00:04:54,685 --> 00:04:58,879
Mas vamos pensar sobre isso por um minuto, o que significa isso? Assim, o

68
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

69
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

70
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 é

71
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

72
00:05:18,195 --> 00:05:22,749
em prever o valor da função no ponto M é apenas adivinhar o valor,

73
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

74
00:05:27,302 --> 00:05:31,625
adivinha o valor da função no ponto M, ele vai adivinhar direito com

75
00:05:31,625 --> 00:05:36,294
probabilidade exatamente um sobre o Y. E, então, a marca que ele produziu será correta

76
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

77
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,

78
00:05:44,801 --> 00:05:49,347
ele vai acertar com probabilidade um sobre Y. E agora, claro, porque o

79
00:05:49,347 --> 00:05:54,420
F de capital é uma função pseudo-aleatório O adversário vai se comportar o

80
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.

81
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

82
00:06:02,659 --> 00:06:06,600
função aleatória, o adversário vai ter vantagens em mais um sobre Y em

83
00:06:06,600 --> 00:06:10,774
ganhar o jogo. Ok, então você pode ver exatamente o teorema de segurança, vamos

84
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

85
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

86
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

87
00:06:24,734 --> 00:06:29,122
MAC, já sabemos que temos o nosso primeiro exemplo MAC. Em particular, nós conhecemos

88
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

89
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

90
00:06:38,011 --> 00:06:43,212
é de dezesseis bytes. Portanto, a cifra AES essencialmente nos dá um MAC que pode corresponder

91
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

92
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ó

93
00:06:53,257 --> 00:06:58,564
atua em dezesseis bytes, podemos construir um MAC para mensagens grandes, que podem atuar em gigabytes

94
00:06:58,564 --> 00:07:02,066
de dados? Às vezes eu chamo este problema, o McDonalds. Basicamente dada uma

95
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

96
00:07:05,871 --> 00:07:10,234
mensagens e que construímos um MAC para mensagens grandes. Então, vamos olhar para dois

97
00:07:10,234 --> 00:07:14,835
construções para o fazer. O primeiro exemplo é chamado um MAC CBC que novamente

98
00:07:14,835 --> 00:07:19,315
leva PRF para pequenas mensagens como entrada e produz uma PRF para muito grande

99
00:07:19,315 --> 00:07:23,686
mensagens. Como saídas. O segundo, vamos ver é HMAC que faz a mesma coisa

100
00:07:23,686 --> 00:07:28,278
novamente leva um PRF para entradas pequenas e gera uma PRF para entradas muito grandes. Agora

101
00:07:28,278 --> 00:07:32,050
os dois são utilizados em contextos muito diferentes. CBC-MAC é realmente muito

102
00:07:32,050 --> 00:07:36,315
comumente usada no setor bancário. Por exemplo, há um sistema chamado

103
00:07:36,315 --> 00:07:40,797
Automatic Clearing House, ACH, que os bancos usam para limpar cheques um com o outro e

104
00:07:40,797 --> 00:07:44,788
sistema que, CBC-MAC, é utilizado para garantir a integridade dos controlos, tal como eles são

105
00:07:44,788 --> 00:07:49,107
transferido de banco para banco. Na Internet, protocolos como SSL e IPsec e

106
00:07:49,107 --> 00:07:53,173
SSH, aqueles HMAC todos os usos de integridade. Dois MACs diferentes e ia discuti-los

107
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

108
00:07:57,086 --> 00:08:01,274
pequenas mensagens e produzem PRF para mensagens que são gigabytes de comprimento e em

109
00:08:01,274 --> 00:08:06,043
particular, eles podem tanto ser fundamentada com a AES como a cifra subjacente. Assim, o

110
00:08:06,043 --> 00:08:10,597
último comentário eu quero fazer sobre estes baseado PRF MACs é que de fato o seu

111
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

112
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

113
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

114
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

115
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ê

116
00:08:36,529 --> 00:08:42,059
dar à PRF então certamente cortar-lo e truncando-lo em pedaços T ainda é

117
00:08:42,059 --> 00:08:46,572
vai parecer aleatória. O atacante agora recebe menos informações para seu trabalho de

118
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

119
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

120
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

121
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

122
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

123
00:09:10,864 --> 00:09:15,379
MAC teorema PRF baseado sabemos que truncando em pedaços W só será seguro

124
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

125
00:09:19,954 --> 00:09:24,410
apenas três bits, o MAC resultante não vai ser seguro. No entanto, se você

126
00:09:24,410 --> 00:09:29,222
truncar dizer 80 bits ou talvez mesmo 64 bits, então o MAC resultante é ainda

127
00:09:29,222 --> 00:09:33,974
vai ser um MAC segura. Ok, então a coisa a lembrar aqui é que, embora

128
00:09:33,974 --> 00:09:39,235
usar AES para construir PRF maiores ea saída destes PRF vai ser de 128 bits,

129
00:09:39,235 --> 00:09:44,115
isso não significa que o MAC se tem para produzir 128 etiquetas bits podemos sempre

130
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

131
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

132
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

133
00:09:57,702 --> 00:09:58,726
o CBC-MAC funciona.