Criptografia - Aula 4: Cifras simétricas a partir de … › ~rvr › resources › Criptografia › Aula4.pdfchave k e um criptograma c, devolve uma mensagem m 2f0;1g. A propriedade

CriptografiaAula 4: Cifras simetricas a partir de cifras por blocos

Manuel Barbosa(mbb at dcc.fc.up.pt)

2018/2019

Seguranca de uma cifra simetrica

Pseudo-aleatoriedade

Primeiras construcoes de cifras simetricasMensagens de comprimento fixoMensagens de comprimento variavel

Seguranca para multiplas mensagens

Seguranca contra adversarios activos

Funcoes Pseudo-Aleatorias

Sintaxe de uma cifra simetrica

Um esquema de cifra simetrica define tres algoritmos PPT:

Um algoritmo probabilıstico Gen de geracao de chaves, que recebe oparametro de seguranca 1n e gera uma chave k. Vamos assumir que|k| ≥ n. Geralmente Gen usa a distribuicao uniforme sobre {0, 1}n.

Um algoritmo de cifracao probabilıstico Enc que, dados uma chavek e uma mensagem m ∈ {0, 1}∗, devolve um criptograma c.Permitimos que Enc execute em tempo polinomial em |k|+ |m|.

Um algoritmo de decifracao determinıstico Dec que, dados umachave k e um criptograma c, devolve uma mensagem m ∈ {0, 1}∗.

A propriedade de correccao exige que, para todo o n, todas asmensagens m ∈ {0, 1}∗ e todas a chaves k geradas por Gen(1n):

Pr[ Deck(Enck(m)) = m ] = 1 .

Quando o espaco de mensages esta limitado a {0, 1}`(n), dizemosque se trata de uma cifra para mensagens de comprimento fixo.

Princıpio de Kerckhoff

Qualquer adversario de conheca Dec e k tem acesso a informacaocontida nos criptogramas.

E ma ideia basear a seguranca na ocultacao de Dec.

Os algoritmos tem estrutura e podem ser alvo de engenharia reversa.

O esforco implicado na substituicao de um algoritmo e muito maior.

Um algoritmo publico pode ser escrutinado (as falhas seraoprovavelmente divulgadas) e partilhado.

Uma chave de, e.g., 100 bits e muito mais facil de armazenar deforma segura.

A chave k devera ser o unico parametro a ser secreto.

Ainda hoje se ignora este princıpio, apesar da existencia dealgoritmos normalizados.

Modelos de ataque

A que tipos de ataque devera uma cifra resistir?

Criptograma conhecido O adversario observa um ou maiscriptogramas e tenta determinar os textos-limpos correspondentes.

Texto-limpo conhecida O adversario conhece um ou mais parestexto-limpo/criptograma cifrados com a mesma chave e tentadepois recuperar o texto-limpo de um outro criptograma.

Texto-limpo escolhido O adversario consegue obter criptogramaspara mensagens a sua escolha e tenta depois recuperar otexto-limpo de um outro criptograma.

Criptograma escolhido O adversario consegue obter o resultado dedecifrar criptogramas a sua escolha e tenta depois recuperar otexto-limpo de um outro criptograma.

Os dois primeiros sao ataques passivos. Os restantes sao activos.Serao cenarios realistas?

Seguranca computational de uma cifra

DefinicaoSeja o jogo Priveav

A,Π aquele definido em baixo e seja Π = (Gen,Enc,Dec)um esquema de cifra simetrico. Entao Π e (computacionalmente) segurona presenca de um adversario passivo se, para qualquer adversario PPTA = (A1,A2), existe uma funcao negligenciavel negl tal que:

Pr[ PriveavA,Π(1n)⇒ T ] ≤ 1

2+ negl(n) .

Game PriveavA,Π(1n):

(m0,m1, st)←$ A1(1n)k←$ Gen(1n)b ←$ {0, 1}c←$ Enck(mb)b′ ←$ A2(c, st)Return b = b′

O adversario e legitimo se |m0| = |m1|.

Seguranca computational de uma cifra

O espaco de probabilidades na experiencia e definido sobre asmoedas utilizadas por A e pelo jogo (na escolha do bit b epossivelmente na execucao do algoritmo Enc).

A definicao e equivalente a esta outra:

DefinicaoSeja o jogo Priveav

A,Π aquele definido em baixo e seja Π = (Gen,Enc,Dec)um esquema de cifra simetrico. Entao Π e (computacionalmente) segurona presenca de um adversario passivo se, para qualquer adversario PPTA = (A1,A2), existe uma funcao negligenciavel negl tal que:

| Pr[ b′ = 1 | b = 0 ]− Pr[ b′ = 1 | b = 1 ] | ≤ negl(n) .

Prova.








Um conceito fundamental em criptografia, e que vamos utilizar naconstrucao de diversos esquemas e o de strings de bits queparecem aleatorios.

Tal como a seguranca computacional e um relaxamento daseguranca perfeita, a pseudo-aleatoriedade e um relaxamento daimposicao de um distribuicao uniforme.

Importante: uma sequencia de bits concreta nao pode serdesignada de pseudo-aleatoria.

A pseudoaleatoriedade e uma propriedade atribuıvel a umalgoritmo de amostragem/ geracao dessas sequencias.

Os strings de bits pseudo-aleatorios sao gerados por distribuicoesque sao indistinguıveis da uniforme para qualquer algoritmo PPT.

Geradores pseudo-aleatorios

DefinicaoSeja `(·) um polinomio e seja G um algoritmo determinıstico polinomialque, para qualquer input s ∈ {0, 1}n, produz uma sequencia de bits decomprimento `(n).Dizemos que G e um gerador pseudo-aleatorio se:

1 (Expansao:) Para todo o n, temos `(n) > n.

2 (Pseudo-aleatoriedade:) Para todo o adversario PPT D, existe umafuncao negligenciavel negl tal que:

| Pr[ D(r)⇒ T : r ←$ {0, 1}`(n) ] −

Pr[ D(G (s))⇒ T : s ←$ {0, 1}n ] | ≤ negl(n)

O polinomio `(·) chama-se factor de expansao.

Geradores pseudo-aleatorios

Observacoes:

O algoritmo G e determinıstico, logo o numero de outputspossıveis e 2n.

E sempre possıvel efectuar um ataque por forca bruta a umgerador deste tipo. Porque?

O numero de sementes possıveis tem de ser sempre suficientepara excluir este tipo de ataque.

Sera que estes geradores existem?

Resultados teoricos indicam que eles existem se existiremfuncoes one-way.







Mensagens de comprimento fixo

Uma utilizacao directa de um gerador pseudo-aleatorio permitecifrar mensagens de tamanho fixo `(n) (potencialmente muitomaior que n).

Algorithm Gen(1n)

k←$ {0, 1}nReturn k

Algorithm Enck(m)

c← G(k)⊕mReturn c

Algorithm Deck(c)

m← G(k)⊕ cReturn m

PRNGseedkey

textolimpo

textocifrado

Seguranca da construcao

TeoremaSe G e um gerador pseudo-aleatorio, entao a construcao anterior(computacionalmente) segura na presenca de um adversariopassivo.

Prova.

Daqui para a frente vamos referir-nos as propriedades de segurancade um esquema utilizando expressoes do tipo o esquema eIND-EAV-seguro:

IND refere a propriedade de ter criptogramas indistinguıveis.

EAV descreve os atacantes contra os quais a propriedade severifica. Neste caso os adversarios passivos.

Mensagens de comprimento variavel

Para estender o esquema anterior para mensagens de tamanhovariavel precisamos de um gerador pseudo-aleatorio de sequenciasde tamanho variavel.

DefinicaoSeja G um algoritmo determinıstico polinomial. Dizemos que G e umgerador pseudo-aleatorio de sequencias de tamanho variavel se:

1 Se s for uma sequencia de bits e ` > 0 for um inteiro, entaoG (s, 1`) produz uma sequencia de bits de tamanho `.

2 Para todo o s, `, `′, com ` < `′, temos que G (s, 1`) gera um prefixode G (s, 1`

′).

3 Defina-se G`(s) := G (s, 1`). Entao, para todo o polinomio `(·)temos que G`(s) e um gerador pseudo-aleatorio.

Porque a restricao no ponto 2?Vamos pedir um string muito longo, mas so usar um prefixo!

Cifras sequenciais na praticaA construcao anterior chama-se geralmente uma cifra sequencial.Por razoes de consistencia, nos vamos utilizar esta designacao parao componente de geracao de sequencias de tamanho variavel.

Uma cifra sequencial e assim uma ferramenta para construiresquemas de cifra.

Na pratica ha muitas cifras sequenciais:

O RC4 e um algoritmo popular para o qual se conhecem fraquezassignificativas (nao recomendado actualmente).

Os Linear Shift Feedback Registers (LSFRs) foram muito utilizadosno passado devido a sua eficiencia em HW. Hoje em dia saoconsiderados totalmente inseguros.

Para todas as aplicacoes (excepto em dispositivos ultra-limitados)recomendam-se solucoes baseadas em cifras por blocos.

Em particular, e possıvel construir facilmente uma cifra sequencial apartir de uma cifra por blocos.








DefinicaoSeja o jogo mPriveav

A,Π aquele definido em baixo e sejaΠ = (Gen,Enc,Dec) um esquema de cifra simetrico. Entao Π e(computacionalmente) seguro para multiplas mensagens na presenca deum adversario passivo se, para qualquer adversario PPT A = (A1,A2),existe uma funcao negligenciavel negl tal que:

Pr[ mPriveavA,Π(1n)⇒ T ] ≤ 1

2+ negl(n) .

Game mPriveavA,Π(1n):

(m10,m

11, . . . ,m

t0,m

t1, st)←$ A1(1n)

k←$ Gen(1n)b ←$ {0, 1}For i ∈ 1 . . . t

ci ←$ Enck(mib)

b′ ←$ A2(c1, . . . , ct , st)Return b = b′

O adversario e legitimo se |mi0| = |mi

1| para todo o i .

Dificuldades em satisfazer esta definicao

Ja vimos anteriormente que nem o One-Time-Pad e seguro no casode se utilizar duas vezes a mesma chave.

Isso aplica-se tambem a utilizacao trivial de uma cifra sequencial,mas o problema e mais profundo.

TeoremaSeja Π = (Gen,Enc,Dec) um esquema de cifra simetrico. Se Enc edeterminıstico, entao Π nao e seguro para multiplas mensagens.

Prova.

Concluımos entao que necessitamos de esquemas de cifra comalgoritmos de cifracao probabilısticos.

Solucao pratica #1: Sincronismo

Na pratica as cifras sequenciais sao utilizadas em dois modos quevisam contornar o problema anterior.

Se pudermos assumir que emissor e receptor vao estarsincronizados, entao podemos adoptar o seguinte procedimento:

A primeira mensagem e cifrada como anteriormente.

A segunda mensagem e cifrada com os bits seguintes geradospela cifra sequencias.

Assim sucessivamente, nunca se reutilizando os bits da chave.

Desta maneira, simula-se a cifracao de uma unica mensagemenorme.

A limitacao pratica de manutencao de estado e sincronismo entreduas cifracoes e significativa.

Solucao pratica #2: Vectores de inicializacaoUsa-se uma cifra sequencial que recebe tambem um vector deinicializacao e que satisfaz uma propriedade mais forte (!).

Informalmente, a propriedade diz que:

se IV for amostrado da distribuicao uniforme, entao G (k, IV) epseudo-aleatorio, mesmo que IV seja conhecido.

se IV1 e IV2 forem amostrados da distribuicao uniforme, entaoG (k, IV1) e G (k, IV2) sao pseudo-aleatorios mesmo que IV1 eIV2 sejam conhecidos.

O algoritmo de cifracao define-se agora como.

Algorithm Enck(m)

IV←$ {0, 1}nc← G (k, IV)⊕mReturn (IV, c)








Todas as definicoes que vimos ate agora consideram apenasadversarios passivos.

Sera que esse nıvel de seguranca e suficiente para as aplicacoes nomundo real?

Exemplos de ataques activos:

Nos meios militares e comum utilizar tecnicas decontra-informacao para provocar a cifracao de mensagensescolhidas.

Nos sistemas distribuıdos, os servicos cifram mensagensgeralmente em resposta a estımulos externos. E possıvelinfluenciar as mensagens que vao ser cifradas.

Estes ataques sao chamados texto limpo escolhido.E sera suficiente?

Chosen-plaintext attacks

DefinicaoSeja o jogo Privcpa

A,Π aquele definido em baixo e seja Π = (Gen,Enc,Dec)um esquema de cifra simetrico. Entao Π e IND-CPA-seguro se, paraqualquer adversario PPT A = (A1,A2), existe uma funcao negligenciavelnegl tal que:

Pr[ PrivcpaA,Π(1n)⇒ T ] ≤ 1

2+ negl(n) .

Game PrivcpaA,Π(1n):

k←$ Gen(1n)

(m0,m1, st)←$ AEncrypt1 (1n)

b ←$ {0, 1}c←$ Enck(mb)

b′ ←$ AEncrypt2 (c, st)

Return b = b′

Oracle Encrypt(m):

c←$ Enck(m)Return c

O adversario e legitimo se |m0| = |m1|.

Propriedades do modelo IND-CPA

Seguranca neste modelo implica seguranca contra adversariospassivos.

Nenhum esquema com cifracao determinıstica pode ser seguroneste modelo (mesmo para uma unica mensagem cifrada).Porque? Podera ser possıvel com estado.

O resultado seguinte e muito importante e implica, entre outrascoisa, que garante sempre seguranca para mensagens de tamanhovariavel. Como?

TeoremaQualquer esquema de cifra simetrico que e IND-CPA-seguro,oferece o mesmo nıvel de seguranca para multiplas mensagens.

Vamos provar um teorema semelhante, mais tarde, para cifras dechave publica.







Funcoes Aleatorias

Consideremos o conjunto F de todas as funcoes com domınio econtra-domınio {0, 1}n.

O que esperamos de uma funcao que e escolhida deste conjunto deacordo com a distribuicao uniforme?

A forma mais simples de responder a esta questao e:

Observar que a descricao de qualquer funcao f ∈ F pode ser vistacomo uma tabela com 2n posicoes.

A posicao i guardara f (i) ∈ {0, 1}n.

Escolher uma funcao e assim preencher esta tabela com valoresescolhidos de maneira totalmente uniforme. (Quantas funcoespossıveis?)

A incerteza relativamente a um valor f (x), quando f egerada desta forma, e todo o contradomınio de tamanho 2n.


Para construir esquemas IND-CPA vamos utilizar funcoes que saoindistinguıveis de funcoes aleatorias.

Consideremos uma funcao F : {0, 1}n × {0, 1}n → {0, 1}n, emque o primeiro argumento e uma chave k.Vamos tambem definir Fk(x) := F (k, x).

A intuicao e a seguinte:

se k for gerada de maneira uniforme, e

se k for mantida secreta; entao

Fk(x) comporta-se como uma funcao uniforme.

(Quantas funcoes possıveis?)

Vamos considerar apenas funcoes F que podem ser avaliadaseficientemente por um algoritmo PPT.


DefinicaoSejam os jogos PRF-RealA,F e PRF-RandomA aqueles definidos embaixo, e seja F : {0, 1}n × {0, 1}n → {0, 1}n uma funcao computavel porum algoritmo PPT. Entao F e uma funcao pseudo-aleatoria se, paraqualquer adversario PPT A, existe uma funcao negligenciavel negl talque:

Pr[ PRF-RealA,F (1n)⇒ 1 ]− Pr[ PRF-RandomA(1n)⇒ 1 ] ≤ negl(n) .

Game PRF-RealA,F (1n):

k←$ {0, 1}nb ←$ AFk(·)(1n)Return b

Game PRF-RandomA(1n):

f ←$ Fb ←$ Af (·)(1n)Return b

Note-se que o adversario pode fazer multiplas perguntas ao seuoraculo, de forma adaptativa.

Comentarios sobre funcoes pseudo-aleatorias

Nao faz qualquer sentido considerar uma nocao semelhante se oadversario conhecer a chave k. Porque?

Na pratica, as cifras por blocos sao consideradas instanciacoesrazoaveis de uma funcao pseudo-aleatoria.

A nıvel teorico, sabe-se que estas funcoes existem se e so seexistirem geradores pseudo-aleatorios!

Estas funcoes sao muito uteis do ponto de vista das provas deseguranca:

Primeiro provamos que o esquema e seguro se for instanciado comuma funcao aleatoria (argumento puramente probabilıstico).

Depois mostramos que qualquer ataque tem forcosamente queimplicar um ataque sobre a pseudo-aleatoriedade da instanciacao,e.g., da cifra por blocos.

Cifra IND-CPA-segura

Seja F uma funcao pseudo-aleatoria. A cifra simetrica naconstrucao seguinte permite cifrar mensagens de tamanho fixo n.

Algorithm Gen(1n)


Algorithm Enck(m)

r ←$ {0, 1}nc← 〈r ,Fk(r)⊕m〉Return c

Algorithm Deck(c)

〈r , s〉 ← cm← Fk(r)⊕ cReturn m

PRF

key textolimpo

textocifrado

r

Neste caso, mensagens de tamanho fixo nao sao uma limitacao. Noentanto, temos uma expansao de 2× no tamanho do criptograma.

Cifra IND-CPA-segura

TeoremaSe F e uma funcao pseudo-aleatoria, entao a construcao anterior eIND-CPA-segura.

Prova.

Intuicao: O pad parece totalmente aleatorio a um adversario quenao conheca k. Mas isso so e verdade se ele for utilizado apenasuma vez!

O facto de um novo r ser gerado de todas as vezes que se cifrauma mensagem m, faz com que a cifra nao seja determinıstica(tinhamos ja visto que isto era uma condicao necessaria).

Modos de funcionamento de cifras por blocos

As cifras simetricas utilizadas na pratica para mensagens detamanho variavel sao construıdas a partir de cifras por blocos.

Historicamente, a cada construcao da-se o nome de um modo defuncionamento.

A escolha de um modo de funcionamento foi, durante muitos anos,deixada ao criterio do utilizador, dependendo de criterios deeficiencia de diversas naturezas.

Gradualmente, a compreensao dos diferentes modos defuncionamento do ponto de vista teorico foi sendo consolidado.

Hoje em dia as escolhas, na maioria das aplicacoes centram-se emuma ou duas alternativas, que levam em consideracao as garantiasde seguranca provadas formalmente.

Electronic Code Book (ECB)

Cipher Block Chaining (CBC)

Output Feedback (OFB)

Modos de funcionamento de cifras por blocosOs modos de funcionamento de cifras por blocos sao maiseficientes para mensagens de tamanho longo. Porque?

Dos modos de funcionamento estudados (creditos a Wikipediapelas figuras seguintes):

Electronic Code Book (ECB)

Cipher Block Chaining (CBC)

Output Feedback (OFB)

Counter Mode (CTR)

O ECB nao oferece seguranca IND-CPA.

Tanto o OFB como o CTR sao IND-CPA assumindo apenas que acifra por blocos se comporta como uma funcao pseudo-aleatoria.

No entanto, para o CBC, e necessario um pressuposto diferente:que a cifra por blocos e indistinguıvel de uma permutacao aleatoria.

Permutacoes pseudo-aleatorias

Consideremos uma funcao F : {0, 1} × {0, 1}n → {0, 1}n, em queo primeiro argumento e uma chave k.Fixando k, exigimos tambem que F seja eficientementecomputavel e invertıvel: uma permutacao.

DefinicaoSejam os jogos PRP-RealA,F e PRP-RandomA aqueles definidos embaixo. Entao F e uma permutacao pseudo-aleatoria se, para qualqueradversario PPT A, existe uma funcao negligenciavel negl tal que:

Pr[ PRP-RealA,F (1n)⇒ 1 ]− Pr[ PRP-RandomA(1n)⇒ 1 ] ≤ negl(n) .

Game PRP-RealA,F (1n):

k←$ {0, 1}nb ←$ AFk(·)(1n)Return b

Game PRP-RandomA(1n):

π ←$ Πb ←$ Aπ(·)(1n)Return b

Comentarios sobre permutacoes pseudo-aleatorias

A definicao e quase identica a das funcoes pseudo-aleatorias.

De facto, qualquer permutacao pseudo-aleatoria e tambem umafuncao pseudo-aleatoria. Porque?

Para certos resultados, no entanto, e necessario assumir que ascifras por blocos satisfazem uma nocao denominada Strong PRP.

Neste caso, o adversario tem tambem acesso a um oraculo queinverte a permutacao. Nao precisar desta definicao.

Em geral podemos considerar funcoes e permutacoes aleatorias emque o tamanho do bloco e diferente do tamanho da chave (e.g.DES).

Counter mode

Seja F uma funcao pseudo-aleatoria. A cifra simetrica seguintepermite cifrar mensagens de tamanho arbitrario.

Algorithm Gen(1n)


Algorithm Enck(m1, . . . ,ml )

ctr←$ {0, 1}n; j ← ctrFor i = 1 to l

ci ← Fk(j)⊕mi

j ← j + 1c← 〈ctr, c1, . . . , cl 〉Return c

Algorithm Deck(c)

〈ctr, c1, . . . , cl 〉 ← c; j ← ctrFor i = 1 to l

mi ← Fk(j)⊕ cij ← j + 1

Return (m1, . . . ,ml )

PRFkeyctr c1

ctr

m1

PRFkeyctr+1 c2

m2

PRFkeyctr+2 c3

m3

...

Seguranca do counter mode

TeoremaSe F e uma funcao pseudo-aleatoria, entao a construcao anterior eIND-CPA-segura.

Prova.

Intuicao: O contador assegura que nao ha repeticoes do paddentro de uma dada cifracao. A amostragem do contador de formaaleatoria assegura que nao ha repeticoes entre cifracoes diferentes.

Note-se que a probabilidade de existir uma colisao no contadordepende do tamanho do bloco!

O modo CTR tem excelentes propriedades de eficiencia e temmelhores propriedades de seguranca que o modo CBC.

Documents

Criptografia - Aula 4: Cifras simétricas a partir de … › ~rvr › resources › Criptografia › Aula4.pdfchave k e um criptograma c, devolve uma mensagem m 2f0;1g. A propriedade