Aula03 - Criptoanálise

Prévia do material em texto

ACH2076 – Segurança da Informação
Aula 03: Criptoanálise
Valdinei Freire
valdinei.freire@usp.br
http://www.each.usp.br/valdinei
Escola de Artes, Ciências e Humanidades - USP
2023
V. Freire (EACH-USP) ACH2076 2023 1 / 28
Livros Textos
1. William Stallings. Criptografia e Segurança de redes: prinćıpios e
práticas, 4ª edição. Caṕıtulo 2
2. Marcio Moretto Ribeiro. Segurança da Informação (apostila).
I Força Bruta
I Máxima Verossimilhança
I Criptoanálise
I Texto cifrado
I Pares texto cifrado / texto aberto
I Pares texto cifrado / texto aberto arbitrários
V. Freire (EACH-USP) ACH2076 2023 2 / 28
Criptoanálise
Estudo de métodos e prinćıpios de transformar mensagens ininteliǵıveis de
volta a mensagens inteliǵıveis, sem conhecimento da chave.
Origem
da chave
Enc - E Dec - D
K
c
Criptoanalista
S
m m
R
K̂
m̂
V. Freire (EACH-USP) ACH2076 2023 3 / 28
Criptoanálise vs Força Bruta
I Criptoanálise
I Contam com a natureza do algoritmo
I Caracteŕısticas gerais do texto claro
I Pares de (texto claro, texto cifrado)
I Força Bruta
I Conhece algoritmo de decriptografia
I Experimenta cada chave posśıvel
I Testa se é uma tradução inteliǵıvel
I Na média, metade de todas chaves precisam ser experimentadas
V. Freire (EACH-USP) ACH2076 2023 4 / 28
Criptoanálise
I Incondicionalmente seguro
I one-time pad (chave de uso único)
I Texto com n caracteres
I Vigènere e chave com n caracteres aleatórios
I Computacionalmente Seguro
I Custo para quebrar cifra superior ao valor da informação codificada
I Tempo exigido para quebrar a cifra superior ao tempo de vida útil da
informação
V. Freire (EACH-USP) ACH2076 2023 5 / 28
Força Bruta
Tamanho da cha-
ve
Quantidade de
Chaves
Tempo Necessário
(1 decrip/µs)
Tempo Necessário
(106 decrip/µs)
2 caracteres (Cifra
de César Afim)
312 156µs < 1µs
26 caracteres
(monoalfabética)
26!=4× 1026 6, 4× 1012 anos 6, 4× 106 anos
32 bits 232=4, 3× 109 35, 8 minutos 2, 15ms
56 bits (DES) 256=7, 2× 1016 1142 anos 10, 01 horas
128 bits (AES) 2128=3, 4× 1038 5, 4× 1024 anos 5, 4× 1018 anos
168 bits (3DES) 2168=3, 7× 1050 5, 9× 1036 anos 5, 9× 1030 anos
V. Freire (EACH-USP) ACH2076 2023 6 / 28
Força Bruta
I Teste de texto inteliǵıvel
I Texto em ĺıngua conhecida: português, inglês, etc.
I Exemplo:
I “Drosb mykmr, Wkckiycrs Wkxklo, cksn: Go my-ybnsxkdon bokvvi
govv kxn dro zvkiobc gybuon bokvvi govv dyqodrob. Lydr dokwc gobo
cy xobfyec sx dro psxkv cod, led Tkzkx rkn tecd k vsddvo lsd wybo.”
V. Freire (EACH-USP) ACH2076 2023 7 / 28
Força Bruta
I Cesar Afim (1,8): Vjgkt eqcej, Ocucaqujk Ocpcdg, uckf: Yg
eq-qtfkpcvgf tgcnna ygnn cpf vjg rncagtu yqtmgf tgcnna ygnn
vqigvjgt. Dqvj vgcou ygtg uq pgtxqwu kp vjg hkpcn ugv, dwv Lcrcp
jcf lwuv c nkvvng dkv oqtg.
I Cesar Afim (1,9): Uifjs dpbdi, Nbtbzptij Nbobcf, tbje: Xf
dp-psejobufe sfbmmz xfmm boe uif qmbzfst xpslfe sfbmmz xfmm
uphfuifs. Cpui ufbnt xfsf tp ofswpvt jo uif gjobm tfu, cvu Kbqbo ibe
kvtu b mjuumf cju npsf.
I Cesar Afim (1,10): Their coach, Masayoshi Manabe, said: We
co-ordinated really well and the players worked really well together.
Both teams were so nervous in the final set, but Japan had just a
little bit more.
V. Freire (EACH-USP) ACH2076 2023 8 / 28
Força Bruta
I Como testar automaticamente?
I Exemplo: Análise de Frequência
I Ĺıngua apenas com 3 śımbolos: a, b e c
I Considere textos com 100 caracteres
I Distribuições de probabilidades (monogramas, digramas, trigramas)
Pr(Na = α,Nb = β,Nc = θ)
Pr(Naa = α,Nab = β,Nac = θ,Nba = γ, . . .)
Pr(Naaa = α,Naab = β,Naac = θ,Naba = γ, . . .)
V. Freire (EACH-USP) ACH2076 2023 9 / 28
Força Bruta
I Como obter distribuições de probabilidades?
I Simplificação: assume independência
Pr(Na = α,Nb = β,Nc = θ) =
= Pr(Na = α|Nb = β,Nc = θ)× Pr(Nb = β|Nc = θ)× Pr(Nc = θ)
u Pr(Na = α)× Pr(Nb = β)× Pr(Nc = θ)
V. Freire (EACH-USP) ACH2076 2023 10 / 28
Força Bruta
Distribuição Binomial (Bernoulli)
I Distribuição de probabilidades discreta
I Número de sucessos em uma sequência de N tentativas
I p é chance de obter sucesso e mantém-se constante
Pr(Na = α) =
(
N
α
)
(pa)
α(1− pa)N−α(
N
α
)
=
N !
(N − α)!α!
V. Freire (EACH-USP) ACH2076 2023 11 / 28
Força Bruta
Máxima Verossimilhança (exemplo com monogramas)
I Dado um texto cifrado c, testa-se todas chaves K
I Para cada chave, conte as quantidades αKa , α
K
b , α
K
c , . . . , α
K
z para
cada letra no texto “aberto” m obtido ao aplicar a chave espećıfica
K no texto cifrado c.
I Maximize
Pr
(
texto em inglês |Na = αKa , Nb = αKb , Nc = αKc , . . . , Nz = αKz
)
∝
∝ Pr
(
Na = αKa , Nb = αKb , Nc = αKc , . . . , Nz = αKz
∣∣ texto em inglês
)
V. Freire (EACH-USP) ACH2076 2023 12 / 28
Força Bruta - Exemplo
I Considere um alfabeto com apenas 3 letras: a, b e c; e a distribuição
abaixo para textos com 10 caracteres
I Utilizando verossimilhança, encontre as chaves nos casos a seguir:
I c = “bbabcbbabb”; cifra monoalfabética
I c = “acaaaaaacc”; cifra de Hill (chave 2× 2 e não contém zeros)
I c = “bbbccbbbba”; cifra Afim
0 2 4 6 8 10
letra a
letra b
letra c
pr
ob
ab
ili
d
ad
e
quantidade de ocorrência
0.1
0.2
0.3
0.4
V. Freire (EACH-USP) ACH2076 2023 13 / 28
Criptoanálise vs Força Bruta
I Criptoanálise
I Contam com a natureza do algoritmo
I Caracteŕısticas gerais do texto claro
I Pares de (texto claro, texto cifrado)
I Força Bruta
I Conhece algoritmo de decriptografia
I Experimenta cada chave posśıvel
I Testa se é uma tradução inteliǵıvel
I Na média, metade de todas chaves precisam ser experimentadas
V. Freire (EACH-USP) ACH2076 2023 14 / 28
Criptoanálise: força do adversário
I Apenas Texto Cifrado: o adversário conhece um texto cifrado c
I Texto claro conhecido: o adversário conhece um texto claro m e o
texto cifrado correspondente c
I Texto claro escolhido: o adversário pode escolher um texto claro m e
obter o texto cifrado correspondente c
I Texto cifrado escolhido: o adversário pode escolher um texto cifrado c
e obter o texto claro correspondente m
V. Freire (EACH-USP) ACH2076 2023 15 / 28
Criptoanálise: Cifra de Hill e Afim
I Texto claro/cifrado escolhido:
I Qual texto escolher?
I Qual tamanho ḿınimo?
I Texto claro conhecido: esperar a condição acima acontecer.
I Apenas texto cifrado: dá pra fazer melhor que força bruta?
V. Freire (EACH-USP) ACH2076 2023 16 / 28
Criptoanálise: Cifra de Vigènere
I Texto claro/cifrado escolhido:
I Qual texto escolher?
I Qual tamanho ḿınimo?
I Texto claro conhecido: esperar a condição acima acontecer.
I Apenas texto cifrado: dá pra fazer melhor que força bruta?
V. Freire (EACH-USP) ACH2076 2023 17 / 28
Criptoanálise: Cifra Monoalfabética
I Texto claro/cifrado escolhido:
I Qual texto escolher?
I Qual tamanho ḿınimo?
I Texto claro conhecido: esperar a condição acima acontecer.
I Apenas texto cifrado: dá pra fazer melhor que força bruta?
V. Freire (EACH-USP) ACH2076 2023 18 / 28
Criptoanálise: Cifra Monoalfabética
Apenas Texto Cifrado: análise de frequência
I Solução Força Bruta
I Considero um critério para indicar o quanto um texto é “inglês”
I Testo todas as chaves posśıveis (26!)
I Verifico a chave que produziu maior aderência ao “inglês”
I Problema: custoso computacionalmente
V. Freire (EACH-USP) ACH2076 2023 19 / 28
Criptoanálise: Cifra Monoalfabética
Apenas Texto Cifrado: análise de frequência
I Solução Ingênua
I Solução Ingênua
I Considera ordem da frequência de ocorrência de letras E, T, A, O, I, N,
S, H, R, D, L, C, U, M, W, F, G, Y, P, B, V, K, J, X, Q e Z
I Realizo a contagem de ocorrência de letras no texto cifrado
I Atribuo conforme a ordem acima
I Problema: qualidade varia bastante com o tamanho do texto
V. Freire (EACH-USP) ACH2076 2023 20 / 28
Criptoanálise: Cifra Monoalfabética
Apenas Texto Cifrado: análise de frequência
I Solução “Greedy” (gulosa)
I Em cada iteração preencho uma letra ou um conjuntode letras na
chave-solução
I Considera um teste de aderência para cada letra
I Teste de aderência considera solução parcial
I Teste de aderência considera digrama, trigrama, etc.
V. Freire (EACH-USP) ACH2076 2023 21 / 28
Criptoanálise: Cifra Monoalfabética
Solução “Greedy” (gulosa)
I Solução Parcial ∆: chave para encriptar
a b c d e f g h i j k l m n o p q r s t u v w x y z
. . .. . .. . .. . .X. . .. . .K. . .L. . .. . .. . .. . .T . . .. . .F . . .. . .. . .G. . .. . .. . .. . .
I Notação
I conjunto P: conjunto de letras no texto aberto {a, b, . . . , y, z}
I conjunto C: conjunto de letras no texto cifrado {A,B, . . . , Y, Z}
I conjunto R ⊂ P: se θ ∈ R, então letra θ não foi atribúıda a uma letra
do texto cifrado
I conjunto T ⊂ C: se Θ ∈ T , então letra Θ ainda não foi atribúıda a
uma letra do texto aberto
I Solução Geral: repete enquanto |T | > 0
I Escolha uma permutação Φ com NC letras em T
I Para cada permutação φ de NC letras em R avalie sua aderência com
a permutação Φ
I Escolha a permutação φ∗ com melhor aderência
V. Freire (EACH-USP) ACH2076 2023 22 / 28
Criptoanálise: Teste de aderência
Considere as permutações φ e Φ, dada uma medida X do texto cifrado e
solução parcial ∆, deseja-se calcular a probabilidade:
Pr(φ = Φ|X ,∆) = Pr(φ1 = Φ1, φ2 = Φ2, . . . , φk = Φk|X ,∆)
Posso medir no texto cifrado:
I XΦi para 1 ≤ i ≤ NC : quantas vezes aparece a letra Φi
I XΦiΦj para 1 ≤ i, j ≤ NC : quantas vezes aparece o digrama ΦiΦj
I XΦi∆j para 1 ≤ i ≤ NC e 1 ≤ j ≤ |∆|: digramas Φi∆j com
elementos em Φ e ∆
I X∆jΦi para 1 ≤ i ≤ NC e 1 ≤ j ≤ |∆|: digramas ∆jΦi com
elementos em Φ e ∆
I XΦiΦjΦk
, XΦiΦjΦkΦl
, XΦiΦjΦkΦlΦm , etc.
V. Freire (EACH-USP) ACH2076 2023 23 / 28
Criptoanálise: Probabilidades
Como calcular (estimar) Pr(φ = Φ|X ,∆)?
Regra de Bayes:
Pr(φ = Φ|X ,∆) ∝ Pr(X|φ = Φ,∆)Pr(φ = Φ|∆)
Aproximação (exemplo apenas com digramas):
Pr(X|φ = Φ,∆) = Pr(XΦi ,XΦiΦj ,XΦi∆j , . . . |φ1 = Φ1, . . . , φk = Φk,∆)
≈
∏
Φi
Pr(XΦi |φi = Φi)
∏
Φi,Φj
Pr(XΦiΦj |φi = Φi, φj = Φj)∏
Φi,∆j
Pr(XΦi∆j |φi = Φi)
∏
Φi,∆j
Pr(X∆jΦi |φi = Φi)
Finalmente, as distribuições Pr(XΦi |φi = Φi) e
Pr(XΦiΦj |φi = Φi, φj = Φj) são aproximadas por distribuições binomiais.
V. Freire (EACH-USP) ACH2076 2023 24 / 28
Criptoanálise: Exemplo
Considere um alfabeto com apenas 5 letras (P = {a, b, c, d, e} e
C = {A,B,C,D,E}) e o texto cifrado:
ACDEADECADCEDACDEDACDEDCBABCDBBCDEADBECBACDEBAACDE
DEABBBADEADEDABDDAAABDEBDEABDEACDEACDEADACBDEBCADE
Ocorrem as seguintes medidas para cada letra: XA = 23, XB = 16,
XC = 15, XD = 27 e XE = 19
Ocorrem as seguintes medidas para cada digrama: XAA = 3, XAB = 5,
XAC = 8, XAD = 7, XAE = 0, XBA = 3, XBB = 3, etc.
Solução Inicial ∆ vazia
a b c d e
. . .. . .. . .. . .. . .
, R = P e T = C
V. Freire (EACH-USP) ACH2076 2023 25 / 28
Criptoanálise: Exemplo
I Escolha uma permutação Φ com 2 letras em T : Φ = AD
I Permutações em R: ab, ac, ad, ae, ba, bc, bd, be, ca, cb, . . .
I Para cada permutação φ calcule sua probabilidade (exemplo φ = ab)
Pr(XA = 23|a = A)Pr(XD = 27|b = D)Pr(XAA = 3|a = A)
Pr(XAD = 7|a = A, b = D)Pr(XDA = 5|a = A, b = D)Pr(XDD = 1|b = D)
I Escolha a permutação φ∗ com melhor aderência (suponha φ∗ = ce)
V. Freire (EACH-USP) ACH2076 2023 26 / 28
Criptoanálise: Exemplo
Passo 2 (NP = 2)
I ∆ =
a b c d e
. . .. . .A. . .D
, R = {a, b, d} e T = {B,C,E}
I Escolha uma permutação Φ com 2 letras em T : φ = BC
I Permutações em R: ab, ad, ba, bd, da, db
I Para cada permutação φ calculo a probabilidade (exemplo φ = ab)
Pr(XB = 16|a = B)Pr(XC = 15|b = C)Pr(XBB = 3|a = B)
Pr(XBC = 3|a = B, b = C)Pr(XCB = 2|a = B, b = C)Pr(XCC = 0|b = C)
Pr(XBA = 4|c = A, a = B)Pr(XAB = 4|c = A, a = B)
Pr(XBD = 5|e = D, a = B)Pr(XDB = 2|e = D, a = B)
Pr(XCA = 2|c = A, b = C)Pr(XAC = 8|c = A, b = C)
Pr(XCD = 9|e = D, b = C)Pr(XDC = 2|e = D, b = C)
I Escolha a permutação φ∗ com melhor aderência (suponha φ∗ = ad)
V. Freire (EACH-USP) ACH2076 2023 27 / 28
Criptoanálise: Melhorias
Problema: Se NC é muito grande existem muitas permutações
Solução: Considerar letras em R que atendem algum requisito
Exemplo: Pr(XA|a = A) > 0.1 maxθ∈R Pr(XA|θ = A)
Problema: Quais letras em ∆ preencher primeiro?
Solução: alfabética, aleatória, maior frequência, análise otimizada
V. Freire (EACH-USP) ACH2076 2023 28 / 28