criptografia - universidade de...
TRANSCRIPT
1
© André Zúquete Segurança Informática e nas Organizações 1
CriptografiaCriptografiaCriptografiaCriptografia
© André Zúquete Segurança Informática e nas Organizações 2
CriptografiaCriptografiaCriptografiaCriptografia: : : : terminologiaterminologiaterminologiaterminologia (1/2)(1/2)(1/2)(1/2)
� Criptografia� Arte ou ciência de escrever de forma escondida
� do Gr. kryptós, oculto + graph, r. de graphein, escrever� Serve para garantir a privacidade da informação� Esteganografia
� do Gr. steganós, oculto + graph, r. de graphein, escrever� Criptanálise
� Arte ou ciência de violar sistemas criptográficos ouinformação criptografada
� Criptologia� Criptografia + criptanálise
2
© André Zúquete Segurança Informática e nas Organizações 3
CriptografiaCriptografiaCriptografiaCriptografia: : : : terminologiaterminologiaterminologiaterminologia (2/2)(2/2)(2/2)(2/2)
� Cifra� Técnica concreta de criptografia
� Operação de uma cifraCifra: texto em claro � criptogramaDecifra: criptograma � texto em claro
Algoritmo: modo de transformação de dadosChave: parâmetro do algoritmo
cifra()
Criptogramatexto
decifra()
Chave(s)
© André Zúquete Segurança Informática e nas Organizações 4
CriptanCriptanCriptanCriptanáááálise: objectivoslise: objectivoslise: objectivoslise: objectivos
� Obtenção do texto original� Relativo a um criptograma
� Obtenção de uma chave de cifra� Ou de uma equivalente
� Obtenção do algoritmo de cifra� Ou de um equivalente� Normalmente os algoritmos não são secretos, mas há
excepções:� Lorenz, A5, RC4� A maioria dos algoritmos para DRM (Digital Rights
Management)� Engenharia reversa normalmente revela-os
3
© André Zúquete Segurança Informática e nas Organizações 5
AtaquesAtaquesAtaquesAtaques de criptande criptande criptande criptanáááálise:lise:lise:lise:AproximaAproximaAproximaAproximaççççõesõesõesões
cifra()
criptogramatexto
decifra()
chave(s)
Só com criptograma
Texto conhecido
Texto escolhido
© André Zúquete Segurança Informática e nas Organizações 6
Cifras: evoluCifras: evoluCifras: evoluCifras: evoluçççção da tecnologiaão da tecnologiaão da tecnologiaão da tecnologia
� Manuais� Algoritmos de substituição
ou transposição� Mecânicas
� A partir do Séc. XIX� Máquina Enigma� M-209 Converter
� Algoritmos de substituição ou transposição
� Informáticas� Surgem com o uso dos
computadores� Algoritmos de substituição
mais complexos� Algoritmos matemáticos
4
© André Zúquete Segurança Informática e nas Organizações 7
Cifras: tipos bCifras: tipos bCifras: tipos bCifras: tipos báááásicos (1/3)sicos (1/3)sicos (1/3)sicos (1/3)
� Transposição� O texto original é “baralhado”
ooibh tonaa erard xilao tgel
� Permutações intra-blocos� (13524) � pruem tceao snrit alcbo os
� (25413) � eumpr aeotc irtsn bcoal so
� Substituição� Cada símbolo original é substituído por outro símbolo
� Originalmente os símbolos era letras, algarismos e pontuação� Actualmente os símbolos são blocos de bits
� Tipos de substituição� Monoalfabética (um�um)� Polialfabética (vários um�um)� Homofónica (um�muitos)� Poligramática (conjuntos�conjuntos)
LEGT
OALIX
DRARE
AANOT
HBIOO
© André Zúquete Segurança Informática e nas Organizações 8
Cifras: tipos bCifras: tipos bCifras: tipos bCifras: tipos báááásicos (2/3):sicos (2/3):sicos (2/3):sicos (2/3):MonoalfabMonoalfabMonoalfabMonoalfabééééticasticasticasticas
� Usam apenas um alfabeto de substituição� Com um número de elementos #A
� Exemplos� Aditivas (ou de translação)
� cripto-letra = (letra + chave) mod #A� letra = (cripto-letra – chave) mod #A� Número de chaves efectivas = #A� Cifra de César (ROT-x)
� Com frase-chaveABCDEFGHIJKLMNOPQRSTUVWXYZ
QTUWXYZCOMFRASEHVBDGIJKLNP
� Número de chaves efectivas = #alfabeto ! � 26! ≈ 288
� Problemas� Reproduzem padrões do texto original
� Letras, digramas, trigramas, etc.� A análise estatística facilita a criptanálise
� “The Gold Bug”, Edgar Alan Poe
5
© André Zúquete Segurança Informática e nas Organizações 9
Cifras: tipos bCifras: tipos bCifras: tipos bCifras: tipos báááásicos (3/3):sicos (3/3):sicos (3/3):sicos (3/3):PolialfabPolialfabPolialfabPolialfabééééticasticasticasticas
� Usam N alfabetos de substituição� Têm período N
� Exemplo� Cifra de Vigenère
� Problemas� Conhecido o período, podem ser criptanalisadas tal como
as monoalfabéticas� O período pode ser descoberto usando estatística� Método de Kasiski
� Factorização de distâncias entre fracções de criptograma iguais
� Índice de coincidência� Factorização de factores de deslocamento que produzem mais
coincidências na sobreposição do criptograma
© André Zúquete Segurança Informática e nas Organizações 10
Cifra de VigenCifra de VigenCifra de VigenCifra de Vigenèèèère (ou quadrado de Vigenre (ou quadrado de Vigenre (ou quadrado de Vigenre (ou quadrado de Vigenèèèère)re)re)re)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
a 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
b 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 A
c C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
d D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
e E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
f F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
g G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
h H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
i I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
j J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
k K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
l L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
m M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
n N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
o O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
p P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
r R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
s S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
t T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
u U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
v V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
w W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
x X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
z Z 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
� Exemplo da cifra da letra M com a chave S, originando o criptograma E
6
© André Zúquete Segurança Informática e nas Organizações 11
CriptanCriptanCriptanCriptanáááálise de um criptograma Vigenlise de um criptograma Vigenlise de um criptograma Vigenlise de um criptograma Vigenèèèère:re:re:re:Exemplo (1/2)Exemplo (1/2)Exemplo (1/2)Exemplo (1/2)
� Texto:Eles não sabem que o sonho é uma constante da vidatão concreta e definida como outra coisa qualquer,como esta pedra cinzenta em que me sento e descanso,como este ribeiro manso, em serenos sobressaltoscomo estes pinheiros altos
� Cifra com o quadrado de Vigenère e chave “poema”texto elesnaosabemqueosonhoeumaconstantedavidataoconcretaedefinida
chave poemapoemapoemapoemapoemapoemapoemapoemapoemapoemapoemapoema
criptograma tzienpcwmbtaugedgszhdsyyarcretpbxqdpjmpaiosoocqvqtpshqfxbmpa
� Teste de Kasiski� Com o texto acima:
� Com o poema completo:
© André Zúquete Segurança Informática e nas Organizações 12
CriptanCriptanCriptanCriptanáááálise de um criptograma Vigenlise de um criptograma Vigenlise de um criptograma Vigenlise de um criptograma Vigenèèèère:re:re:re:Exemplo (2/2)Exemplo (2/2)Exemplo (2/2)Exemplo (2/2)
� Índice de coincidência (c/ poema completo)
C oi nc i de nc e inde x
0
5
10
15
20
25
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180
T r ansl at i on shi f t
7
© André Zúquete Segurança Informática e nas Organizações 13
MMMMááááquinas de rotores (1/2)quinas de rotores (1/2)quinas de rotores (1/2)quinas de rotores (1/2)
� As máquinas de rotores concretizam cifras polialfabéticas complexas� Cada rotor efectua uma permutação do alfabeto
� Que consiste num conjunto de substituições� A posição do rotor concretiza um alfabeto de substituição� A rotação de um rotor ao longo do tempo concretiza uma cifra
polialfabética� Acumulando vários rotores em sequência e rodando-os de forma
diferenciada consegue-se uma cifra polialfabética complexa� A chave de cifra é:
� O conjunto de rotores usado (conjunto de permutações)� A ordem relativa dos rotores (ordem das permutações)� A posição original dos rotores (alfabetos de substituição originais)
� Rotores simétricos (bidireccionais) permitem concretizar a decifras usando cifras duplas� Uso de um disco reflector (meio-rotor)� Cada símbolo nunca pode ser substituído por si mesmo
© André Zúquete Segurança Informática e nas Organizações 14
MMMMááááquinas de rotores (2/2)quinas de rotores (2/2)quinas de rotores (2/2)quinas de rotores (2/2)
� Operação recíproca com um reflector� O operador emissor carrega em “A” (o texto em claro) e
obtém “Z” como criptograma, o qual é transmitido� O operador receptor carrega em “Z” (o criptograma) e
obtém “A” como texto em claro� Uma letra nunca pode ser cifrada para si própria!
8
© André Zúquete Segurança Informática e nas Organizações 15
EnigmaEnigmaEnigmaEnigma
� Máquina de rotores usada pelosAlemães na 2ª GG
� Originalmente apresentada em 1919� Enigma I, com 3 rotores
� Foram usadas diversas variantes� Com diferentes números de rotores� Com cablagem para permutar alfabetos� Selecções de chaves distribuídas em livros de códigos
© André Zúquete Segurança Informática e nas Organizações 16
Criptografia: aproximaCriptografia: aproximaCriptografia: aproximaCriptografia: aproximaçççções teões teões teões teóóóóricasricasricasricas
� Espaço de texto� Número de combinações de texto diferentes (M)
� Espaço do criptograma� Número de combinações de criptograma diferentes (C)
� Espaço das chaves� Número de chaves diferentes para um algoritmo de cifra (K)
� Cifra perfeita� Dado cj ∈ C, p(mi, kj) = p(mi)� #K ≥ #M� One-time pad
XOR
Criptogramatexto
XOR
Chave aleatória
infinita
9
© André Zúquete Segurança Informática e nas Organizações 17
Criptografia: aproximaCriptografia: aproximaCriptografia: aproximaCriptografia: aproximaçççções prões prões prões prááááticas (1/4)ticas (1/4)ticas (1/4)ticas (1/4)
� Teoricamente seguras vs. seguras na prática� Uso teórico ≠ exploração prática� Uma cifra teoricamente segura pode ser usada de forma
insegura� Exemplo: distribuição de chaves com one-time-pads
� Cifras seguras na prática� É fácil garantir uma exploração mais isenta de
problemas� Têm uma segurança baseada em limites razoáveis:
� Custo de uma solução técnica de criptanálise� Infra-estrutura reservada para a criptanálise� Tempo útil de criptanálise
© André Zúquete Segurança Informática e nas Organizações 18
Criptografia: aproximaCriptografia: aproximaCriptografia: aproximaCriptografia: aproximaçççções prões prões prões prááááticas (2/4)ticas (2/4)ticas (2/4)ticas (2/4)
� 5 critérios de Shannon� A quantidade de secretismo oferecida� A complexidade na escolha das chaves� A simplicidade da realização� A propagação de erros� A dimensão do criptograma
10
© André Zúquete Segurança Informática e nas Organizações 19
Criptografia: aproximaCriptografia: aproximaCriptografia: aproximaCriptografia: aproximaçççções prões prões prões prááááticas (3/4)ticas (3/4)ticas (3/4)ticas (3/4)
� Confusão� Complexidade na relação entre o texto, a chave e o criptograma
� Dificuldade de deduzir partes da chave� Difusão
� Alteração de grandes porções do criptograma em função de uma pequena alteração do texto
© André Zúquete Segurança Informática e nas Organizações 20
Criptografia: aproximaCriptografia: aproximaCriptografia: aproximaCriptografia: aproximaçççções prões prões prões prááááticas (4/4)ticas (4/4)ticas (4/4)ticas (4/4)
� Assumir sempre o pior caso� O criptanalista conhece o algoritmo
� A segurança está na chave� O criptanalista possui grande número de criptogramas gerados com esse algoritmo� Os criptogramas não são secretos
� O criptanalista conhece parte do texto original que produziu esses criptogramas� É normal haver alguma noção do texto original� Ataques com texto conhecido
11
© André Zúquete Segurança Informática e nas Organizações 21
Cifras contCifras contCifras contCifras contíííínuas (nuas (nuas (nuas (streamstreamstreamstream) (1/3)) (1/3)) (1/3)) (1/3)
� Motivação� Ter cifras próximas de uma one-time-pad� Facilidade de realização com computadores
� Aproximação� Chave contínua (keystream) gerada de forma determinística� Aproximação da chave contínua a uma sequência verdadeiramente
aleatória� Aleatoriedade local da sequência pseudo-aleatória
� Mistura da chave contínua com o texto usando uma função facilmente invertível
mistura Criptogramatexto
keystream gerador chave
mistura-1
gerador
texto
© André Zúquete Segurança Informática e nas Organizações 22
Cifras contCifras contCifras contCifras contíííínuas (2/3)nuas (2/3)nuas (2/3)nuas (2/3)
� Geração e mistura da chave contínua� Gerador: máquina de estados� Algoritmo: diagrama de transições da máquina de estados� Chave: estado inicial da máquina de estados� Mistura: XOR bit a bit (C = T ⊕ K, T = C ⊕ K)
� Caracterização� São cifras polialfabéticas
� A chave contínua pode ser infinita mas o período é finito� O período é dado pelo ciclo executado pela máquina de estados
para uma dada chave� A sincronização é crítica
� Usa confusão� Mas não difusão� Não propaga erros
12
© André Zúquete Segurança Informática e nas Organizações 23
Cifras contCifras contCifras contCifras contíííínuas (3/3)nuas (3/3)nuas (3/3)nuas (3/3)
� Segurança prática� O texto a cifrar deverá ser inferior ao período da chave
contínua� A exposição da chave contínua é total caso se conheça o
texto� A repetição de ciclos facilita a criptanálise se se conhecer
o período e amostras do texto original� Aleatoriedade local
� Deverá ser impossível descobrir troços adjacentes de um troço da chave contínua inferior ao seu período
� O criptograma deverá aparentar ser aleatório� Tem que existir controlo de integridade
� É fácil alterar de forma deterministica o criptograma
© André Zúquete Segurança Informática e nas Organizações 24
Lorenz (Lorenz (Lorenz (Lorenz (TunnyTunnyTunnyTunny))))
� Máquina de cifra contínuacom 12 rotores� Usada pelo alto-comando Alemão durante a 2ª GG� Concretizava uma cifra contínua
� Cada símbolo de 5 bits era misturado com uma chave contínua de símbolos de 5 bits
� Operação� 5 rotores rodados regularmente (S)� 5 rotores rodados irregularmente (K)
� Segundo uma política “todos ou nenhuns”
� 2 rotores de controlo (M)� Para rodar os rotores K
� O número de posições em cada rotorera co-primo com os demais
13
© André Zúquete Segurança Informática e nas Organizações 25
CriptanCriptanCriptanCriptanáááálise de lise de lise de lise de TunnyTunnyTunnyTunny em em em em BletchleyBletchleyBletchleyBletchley ParkParkParkPark (1/3)(1/3)(1/3)(1/3)
� A estrutura da máquina Lorenz não era conhecida� Só no final da guerra a conseguiram observar� Sabiam que ela existia porque interceptavam
comunicações cifradas usando símbolos de 5 bits� Usando o código de 32 símbolos de Baudot em vez do
código Morse
© André Zúquete Segurança Informática e nas Organizações 26
CriptanCriptanCriptanCriptanáááálise de lise de lise de lise de TunnyTunnyTunnyTunny em em em em BletchleyBletchleyBletchleyBletchley ParkParkParkPark (2/3)(2/3)(2/3)(2/3)
� O erro (30 de Agosto de 1941)� Um operador alemão tinha uma grande mensagem para enviar (~4,000 caracteres)
� Configurou a sua Lorenz e enviou um indicador de 12 letras (posição inicial dos rotores) para o receptor
� Depois de ter escrito ~4,000 caracteres, manualmente, recebeu do receptor “envie outra vez”
� Ambos colocaram a Lorenz na mesma posição inicial� Completamente proibido!
� O emissor recomeçou o envio da mensagem, manualmente� Mas escreveu algo ligeiramente diferente!
� A descoberta� A mensagem começava com um texto bem conhecido: SPRUCHNUMMER — número de
mensagem� Na primeira vez o operador escreveu S P R U C H N U M M E R� Na segunda vez escreveu S P R U C H N R� Assim, imediatamente após o N os dois criptogramas eram diferentes!
� As mensagens foram completamente decifradas por John Tiltman, em Bletchley Park, usando combinações aditivas dos criptogramas (chamados Depths) � A segunda mensagem era cerca de 500 caracteres mais curta que a primeira
� Assim se conseguiu obter, pela 1ª vez, um exemplar longo de uma chave contínua Lorenz� Tiltman ainda não sabia como a Lorenz operava, apenas sabia que o que tinha era o
resultado da sua operação!
14
© André Zúquete Segurança Informática e nas Organizações 27
CriptanCriptanCriptanCriptanáááálise de lise de lise de lise de TunnyTunnyTunnyTunny em em em em BletchleyBletchleyBletchleyBletchley ParkParkParkPark (3/3):(3/3):(3/3):(3/3):ColossusColossusColossusColossus
� A estrutura da cifra foi deduzida apartir da chave contínua capturada� Mas a decifra dependia do
conhecimento da posição inicial dosrotores
� Os alemães começaram a usarnúmeros para definir o estado inicial dos rotores� Bill Tutte desenvolveu um método para o encontrar
� A máquina Colossus foi desenvolvida para aplicar esse método� A concepção começou em Março de 1943� O Colossus Mark 1 (1500 válvulas) estava operacional em
Janeiro de 1944� O Colossus reduziu o tempo de criptanálise de semanas para
horas
© André Zúquete Segurança Informática e nas Organizações 28
Cifras modernas: tiposCifras modernas: tiposCifras modernas: tiposCifras modernas: tipos
� Quanto à operação� Por blocos (mono-alfabéticas)� Contínuas (poli-alfabéticas)
� Quanto ao tipo de chave� Simétricas (chave secreta ou segredo partilhado)
� Potencialmente sujeitas a caução (escrowing)� Assimétricas (chave pública)
� Combinatória
Assimétricas
Simétricas
ContínuasPor blocos
15
© André Zúquete Segurança Informática e nas Organizações 29
Cifras simCifras simCifras simCifras siméééétricastricastricastricas
� Chave secreta� Partilhada por 2 ou mais interlocutores
� Permitem� Confidencialidade para todos os conhecedores da chave� Autenticação de mensagens (cifra por blocos)
� Vantagens� Desempenho (normalmente muito eficientes)
� Desvantagens� N interlocutores, 2 a 2 secretamente � N x (N-1)/2 chaves
� Problemas� Distribuição de chaves
© André Zúquete Segurança Informática e nas Organizações 30
Cifras simCifras simCifras simCifras siméééétricas por blocostricas por blocostricas por blocostricas por blocos
� Aproximações usadas� Blocos de grande dimensão
� 64, 128, 256, etc.� Difusão, confusão
� Permutação, substituição, expansão, compressão� Feistel Networks
� Li=Ri-1 Ri=Li-1⊕f(Ri-1,Ki)� Iterações
� Algoritmos mais usados� DES (Data Enc. Stand.), D=64; K=56� IDEA (Int. Data Enc. Alg.), D=64; K=128� AES (Adv. Enc. Stand., aka Rijndael), D, K=128,192,256� Outros (Blowfish, CAST, RC5, etc.)
Li Ri
Li-1 Ri-1
f(Ki)
16
© André Zúquete Segurança Informática e nas Organizações 31
DESDESDESDES ((((Data Data Data Data EncryptionEncryptionEncryptionEncryption StandardStandardStandardStandard) (1/4)) (1/4)) (1/4)) (1/4)
� 1970: necessidade de uma cifra padrão que para a sociedade civil
� 1972: NBS abre um concurso para uma nova cifra com os seguintes requisitos:� alto nível de segurança� completamente especificado, fácil de perceber� Algoritmo público
� secretismo dependente apenas das chaves� Multiusos� Economicamente realizável em dispositivos electrónicos � Eficiente� Susceptível de validação� Susceptível de exportação
© André Zúquete Segurança Informática e nas Organizações 32
DESDESDESDES (2/4)(2/4)(2/4)(2/4)
� 1974: novo concurso� Proposta baseada no Lucifer da IBM� Blocos de 64 bits� Chaves de 56 bits, sub-chaves de 48 bits� Difusão, confusão
� Permutação, substituição, expansão, compressão� 16 iterações
� Vários modos de funcionamento� ECB (Electronic Code Book), CBC (Cypher Block Chaining)� OFB (Output Feedback Mode), CFB (Cypher Feedback Mode)
� 1976: adoptado nos EU como padrão federal
17
© André Zúquete Segurança Informática e nas Organizações 33
DESDESDESDES (3/4)(3/4)(3/4)(3/4)
� Substituição, Permutação, Compressão e Expansão
Input (64)
P I
L0 R0
Li Ri
L1 R1
KS1
L16 R16
KS16
inverso PI
output (64)
Li-1 Ri-1
Ri
E + P
S-Box i
K (56)
[i] [i]
C + P
P-box
KSi
© André Zúquete Segurança Informática e nas Organizações 34
DESDESDESDES: seguran: seguran: seguran: segurançççça oferecidaa oferecidaa oferecidaa oferecida
� Escolha de chaves� Chaves fracas, semi-fracas e quasi-fracas� Fáceis de identificar
� Ataques conhecidos� Pesquisa exaustiva
� Dimensão das chaves� 56 bits são actualmente insuficientes
� A pesquisa exaustiva é tecnica e economicamente viável� Solução: cifra múltipla
� Cifra dupla não é completamente segura (teoricamente ...)� Cifra tripla: 3DES (Triple-DES)
� Com duas ou três chaves� Chaves equivalentes de 112 ou 168 bits
18
© André Zúquete Segurança Informática e nas Organizações 35
Cifras simCifras simCifras simCifras siméééétricas conttricas conttricas conttricas contíííínuasnuasnuasnuas
� Aproximações usadas� Desenho de geradores pseudo-aleatórios seguros
� Baseados em LFSRs� Baseados em cifras por blocos� Outras aproximações (famílias de funções, etc.)
� Normalmente sem sincronização� Normalmente sem possibilidade de acesso aleatório rápido
� Algoritmos mais usados� A5 (GSM)� RC4 (802.11 WEP, etc.)� SEAL (com acesso aleatório rápido)
© André Zúquete Segurança Informática e nas Organizações 36
Linear Feedback Linear Feedback Linear Feedback Linear Feedback ShiftShiftShiftShift RegisterRegisterRegisterRegister ((((LFSRLFSRLFSRLFSR))))
� 2n-1 sequências não nulas� Se uma delas tiver período 2n-1 então todas o têm
� Funções de realimentação primitivas� Todas as sequências não nulas têm comprimento 2n - 1
Sn-1 S1 S0
Cn-1 C2 C1 C0
Estado inicial (chave)Função de realimentação
Ck
19
© André Zúquete Segurança Informática e nas Organizações 37
ComposiComposiComposiComposiçççção de ão de ão de ão de LFSRLFSRLFSRLFSR::::A5A5A5A5 (GSM)(GSM)(GSM)(GSM)
LFSR1
LFSR2
LFSR3
19 bits
22 bits
23 bits
Σ Maioria
© André Zúquete Segurança Informática e nas Organizações 38
Cifras assimCifras assimCifras assimCifras assiméééétricastricastricastricas
� Par de chaves� Uma privada, pessoal e intransmissível� Um pública
� Permitem� Confidencialidade sem troca de segredos� Autenticação
� De conteúdos (integridade)� De autoria (assinaturas digitais)
� Desvantagens� Desempenho (normalmente pouco eficientes)
� Vantagens� N interlocutores, N pares de chaves
� Problemas� Distribuição de chaves públicas� Tempo de vida dos pares de chaves
20
© André Zúquete Segurança Informática e nas Organizações 39
ConfidencialidadeConfidencialidadeConfidencialidadeConfidencialidade
� Menos chaves� C = E(K, P) P = D(K-1, C)� Para comunicar confidencialmente com X basta conhecer KX
� Não há autenticação� X não sabe quem produziu o criptograma
KX (pública)
mensagem
KX-1 (privada)
criptograma mensagemcifra decifra
Mr. X
© André Zúquete Segurança Informática e nas Organizações 40
AutenticidadeAutenticidadeAutenticidadeAutenticidade
� O criptograma não pode ser alterado� C = E(K-1, P) P = D(K, C);� Só X conhece a chave KX
-1 com que foi gerado� Não há confidencialidade
� Quem conhecer KX decifra o criptograma� KX é pública
KX (pública)
mensagem
KX-1 (privada)
criptograma mensagemcifra decifra
21
© André Zúquete Segurança Informática e nas Organizações 41
Cifras assimCifras assimCifras assimCifras assiméééétricas (por blocos)tricas (por blocos)tricas (por blocos)tricas (por blocos)
� Aproximações usadas� Complexidade matemática
� Cálculo de logaritmos discretos� Factorização de grandes números� Problema da mochila (knapsack)
� Algoritmos mais usados� RSA� ElGamal
� Outras técnicas com chave pública� Diffie-Hellman
© André Zúquete Segurança Informática e nas Organizações 42
RSARSARSARSA (Rivest, (Rivest, (Rivest, (Rivest, ShamirShamirShamirShamir, , , , AdelmanAdelmanAdelmanAdelman))))
� Publicado em 1978� Complexidade matemática
� Dificuldade de factorização de grandes números� Dificuldade de cálculo de logaritmos discretos
� Operações e chaves� C = Pe mod n P = Cd mod n K = (e, n) K-1 = (d, n)� C = Pd mod n P = Ce mod n
� Escolha dos valores das chaves� n de grande dimensão (centenas ou milhares de bits)� n = p · q p e q primos� Escolher e coprimo de (p-1)(q-1)� Procurar um d tal que e · d ≡ 1 mod (p-1)(q-1)� Não se consegue deduzir d a partir de e e n
22
© André Zúquete Segurança Informática e nas Organizações 43
RSARSARSARSA: exemplo: exemplo: exemplo: exemplo
� p = 5 q = 11� n = p x q = 55� (p-1)(q-1) = 40
� e = 3� Coprimo de 40
� d = 27� e x d ≡ 1 mod 40
� P = 26� C = Pe mod n = 263 mod 55 = 31� P = Cd mod n = 3127 mod 55 = 26
© André Zúquete Segurança Informática e nas Organizações 44
ElGamalElGamalElGamalElGamal
� Publicado por El Gamal em 1984� Semelhante ao RSA
� Mas baseado apenas na dificuldade de cálculo de logaritmos discretos
� Uma variante é muito usada em assinaturas digitais� DSA (Digital Signature Algorithm)� US Digital Signature Standard (DSS)
� Operações e chaves (para assinaturas)� β = αa mod p K = (β, α, p) K-1 = (a, α, p)� k aleatório, k · k-1 ≡ 1 mod (p-1)� Assinatura de x: (γ,δ) γ = αk mod p δ = k-1 (x - aγ) mod (p-1)� Validação da assinatura de x: βγγδ ≡ αx (mod p)
� Problema� O valor de k precisa de ser secreto� O seu conhecimento revela a!
23
© André Zúquete Segurança Informática e nas Organizações 45
AplicaAplicaAplicaAplicaççççãoãoãoão das das das das cifrascifrascifrascifras::::ModosModosModosModos de de de de cifracifracifracifra
� Problema� Como adaptar uma cifra por blocos de dimensão fixa a
um texto de dimensão diferente� Maior ou menor que o bloco� Com um comprimento múltiplo ou não do comprimento
do bloco� Solução 1
� Fraccionar o texto em blocos de igual dimensão� Aplicar a cifra a cada um dos blocos� Aplicar um algoritmo diferente ao sub-bloco final
� Solução 2� Transformar a cifra por blocos numa cifra contínua� Gerar uma chave contínua e somá-la (mod 2) ao texto
© André Zúquete Segurança Informática e nas Organizações 46
ModosModosModosModos de de de de cifracifracifracifra
� Inicialmente apresentados para o DES� ECB (Electronic Code Book)� CBC (Cipher Block Chaining)� OFB (Output Feeback Mode)� CFB (Cipher Feedback Mode)
� Podem ser usados por outras cifras por blocos� Em princípio ...
� Outros entretanto propostos� CTR (Counter Mode)
� Tratamento do sub-bloco� Alinhamento com excipiente
� Aumenta o criptograma face ao texto original� Cifra contínua ou ciphertext stealing
� O criptograma e o texto original têm o mesmo comprimento
24
© André Zúquete Segurança Informática e nas Organizações 47
ModosModosModosModos de de de de cifracifracifracifra::::ECB e CBCECB e CBCECB e CBCECB e CBC
Electronic Code BookCi = EK(Ti)Ti = DK(Ci)
Cipher Block ChainingCi = EK(Ti ⊕ Ci-1)Ti = DK(Ci ) ⊕ Ci-1
T1 T2 Tn
C1 C2 Cn
EK EK EK EK
DK DK DK DK
T1 T2 Tn
T1 T2 Tn-1 Tn
C1 C2 Cn-1 Cn
EK EK EK EK EK
T1 T2 Tn-1 Tn
DK DK DK DK DK
IV
IV
© André Zúquete Segurança Informática e nas Organizações 48
ModosModosModosModos de de de de cifracifracifracifra::::nnnn----bit OFBbit OFBbit OFBbit OFB
Output Feedback (autokey)Ci = Ti ⊕ EK(Si)Ti = Ci ⊕ EK(Si)Si = f(Si-1, EK(Si-1))
T1
C1
EK EK EK
Tn
Cn
EK EK EK
T1 Tn
IV
IV
T C
EK
IV
Realimentação
25
© André Zúquete Segurança Informática e nas Organizações 49
ModosModosModosModos de de de de cifracifracifracifra::::nnnn----bit CFBbit CFBbit CFBbit CFB
Ciphertext FeedbackCi = Ti ⊕ EK(Si)Ti = Ci ⊕ EK(Si)Si = f(Si-1, Ci)
T1
C1
EK EK EK
Tn
Cn
T1 Tn
IV
EK EK EKIV
T C
EK
IV
Realimentação
© André Zúquete Segurança Informática e nas Organizações 50
ModosModosModosModos de de de de cifracifracifracifra::::nnnn----bit CTRbit CTRbit CTRbit CTR
CounterCi = Ti ⊕ EK(Si)Ti = Ci ⊕ EK(Si)Si = Si-1+1 S0 = IV
T1
C1
EK EK EK
Tn
Cn
EK EK EK
T1 Tn
IV
IV
T C
EK
IV
Realimentação
+1
26
© André Zúquete Segurança Informática e nas Organizações 51
ModosModosModosModos de de de de cifracifracifracifra::::TratamentoTratamentoTratamentoTratamento de subde subde subde sub----blocosblocosblocosblocos
� Cifra contínua � Ciphertext stealing
Cn-1
Tn
Cn
EK
Tn
EK
Cn-1
EK
DK
Tn-1
EK
DK
Tn-1
Cn
Tn
C’
C’
Tn C’
Tn-1
Cn-1
EK EK
Tn-1
DK DK
Cn
Tn
0
0
Tn C’
Cn-2
EK
© André Zúquete Segurança Informática e nas Organizações 52
ModosModosModosModos de de de de cifracifracifracifra::::ComparaComparaComparaComparaççççãoãoãoão
����
����
outro IV(contador)
contador secreto
����
CTR
alguns bits
seguintes
bloco seguintePropagação de erros
perda de múltiplos de n-bits
perda de blocos
perda de blocos
Capacidade de recuperar a sincronização
decifracom pré-processam.decifra����
Paralelização
Acesso aleatório rápido
����Pré-processamento
���� (...)����Dificuldade de alteração
outro IVoutro IV��������Mesma chave para mensagens diferentes
��������Confusão na entrada da cifra
������������Não exposição padrões
CFBOFBCBCECB
27
© André Zúquete Segurança Informática e nas Organizações 53
Modos de cifra:Modos de cifra:Modos de cifra:Modos de cifra:ReforReforReforReforçççço da segurano da segurano da segurano da seguranççççaaaa
� Cifra múltipla� Cifra dupla
� Violável por intromissão em 2n+1 tentativas� Com 2 ou mais blocos de texto conhecido� Usando 2n blocos de memória ...
� Não é (teoricamente) muito mais segura ...� Cifra tripla (EDE)
� Ci = EK1(DK2 (EK3 (Ti)))� Pi = DK3(EK2 (DK1 (Ci))� Normalmente usa-se K1=K3
� Se K1=K2=K3 transforma-se numa cifra simples� Branqueamento (whitening)
� Técnica simples e eficiente de introdução de confusão� Ci = EK(K1 ⊕⊕⊕⊕ Ti ) ⊕⊕⊕⊕ K2
� Ti = K1 ⊕⊕⊕⊕ DK(K2 ⊕⊕⊕⊕ Ci )
© André Zúquete Segurança Informática e nas Organizações 54
FunFunFunFunçççções de sões de sões de sões de sííííntese (ntese (ntese (ntese (digestdigestdigestdigest))))
� Produzem um valor de dimensão constante com base em textos de dimensão variável� Aplicação iterativa de uma função de compressão com dimensões
fixas� O texto é alinhado ao bloco de entrada
� Produzem valores muito diferentes para entradas semelhantes� São “não invertíveis”:
� Resistência à descoberta de um texto� Dada uma síntese, é difícil encontrar um texto que o produza
� Resistência à descoberta de um 2º texto� Dado um texto e a sua síntese, é difícil encontrar um segundo texto que a
produza� Resistência à colisão
� É díficil encontrar dois textos diferentes que produzam a mesma síntese� Paradoxo do aniversário
28
© André Zúquete Segurança Informática e nas Organizações 55
Função de
compressão
� Aproximações� Difusão & confusão em funções de compressão� Construção Merkle-Damgård
� Compressão iterativa� Padding com o comprimento
� Algoritmos mais comuns� MD5 (128 bits)
� Já não é seguro! É fácil descobrir colisões!� SHA-1 (Secure Hash Algorithm, 160 bits)
� Ainda não se conhecem colisões (por enquanto)� Não se conhece nenhuma forma de as gerar (por enquanto)
� Outros (SHA-2, aka SHA-256/SHA-512, etc.)
FunFunFunFunçççções de sões de sões de sões de sííííntesentesentesentese((((digestdigestdigestdigest))))
IV
T1
síntese
Tn
© André Zúquete Segurança Informática e nas Organizações 56
MessageMessageMessageMessage AuthenticationAuthenticationAuthenticationAuthentication CodeCodeCodeCode (MAC)(MAC)(MAC)(MAC)
� Síntese gerada com recurso a uma chave� Cifrando uma síntese normal
� Por exemplo, com uma cifra simétrica por blocos� Usando uma função chaveada
� ANSI X9.9 (ou DES-MAC) com DES CBC (64 bits)� Usando uma chave nos parâmetros da função
� Keyed-MD5 (128 bits)MD5(K, keyfill, texto, K, MD5fill)
� HMAC (dimensão da função de síntese usada)H(K, opad, H(K, ipad, texto)) ipad = 0x36 B vezesopad = 0x5C B vezes
29
© André Zúquete Segurança Informática e nas Organizações 57
Assinaturas digitaisAssinaturas digitaisAssinaturas digitaisAssinaturas digitais
� Objectivo� Autenticar o conteúdo de um documento
� Garantir a sua integridade� Autenticar o seu assinante
� Assegurar a identidade do criador/originador� Poder assegurar a autenticação perante terceiros
� Os autores genuínos não podem negar a autoria� Aproximações usadas
� Cifra de chave pública� Funções de síntese
� Apenas para aumentar o desempenho!� Algoritmos
Assinatura: Ax(doc) = info + E(Kx-1, digest(doc+info))
Verificação: info�KxD(Kx, Ax(doc)) ≡≡≡≡ digest(doc + info)
© André Zúquete Segurança Informática e nas Organizações 58
DiagramasDiagramasDiagramasDiagramas de de de de assinaturaassinaturaassinaturaassinatura e e e e validavalidavalidavalidaççççãoãoãoão((((dadadada wikipediawikipediawikipediawikipedia, http://, http://, http://, http://en.wikipedia.org/wiki/Digital_signatureen.wikipedia.org/wiki/Digital_signatureen.wikipedia.org/wiki/Digital_signatureen.wikipedia.org/wiki/Digital_signature))))
30
© André Zúquete Segurança Informática e nas Organizações 59
AssinaturaAssinaturaAssinaturaAssinatura digital num edigital num edigital num edigital num e----mail:mail:mail:mail:ConteConteConteConteúúúúdosdosdosdos multimultimultimulti----partidospartidospartidospartidos, , , , assinaturaassinaturaassinaturaassinatura c/ c/ c/ c/ certificadoscertificadoscertificadoscertificados
From - Fri Oct 02 15:37:14 2009
[…]
Date: Fri, 02 Oct 2009 15:35:55 +0100
From: =?ISO-8859-1?Q?Andr=E9_Z=FAquete?= <[email protected]>
Reply-To: [email protected]
Organization: IEETA / UA
MIME-Version: 1.0
To: =?ISO-8859-1?Q?Andr=E9_Z=FAquete?= <[email protected]>
Subject: Teste
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=sha1; boundary="------------ms050405070101010502050101"
This is a cryptographically signed message in MIME format.
--------------ms050405070101010502050101
Content-Type: multipart/mixed;
boundary="------------060802050708070409030504"
This is a multi-part message in MIME format.
--------------060802050708070409030504
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Corpo do mail
--------------060802050708070409030504—
--------------ms050405070101010502050101
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"
Content-Description: S/MIME Cryptographic Signature
MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIamTCC
BUkwggSyoAMCAQICBAcnIaEwDQYJKoZIhvcNAQEFBQAwdTELMAkGA1UEBhMCVVMxGDAWBgNV
[…]
KoZIhvcNAQEBBQAEgYCofks852BV77NVuww53vSxO1XtI2JhC1CDlu+tcTPoMD1wq5dc5v40
Tgsaw0N8dqgVLk8aC/CdGMbRBu+J1LKrcVZa+khnjjtB66HhDRLrjmEGDNttrEjbqvpd2QO2
vxB3iPTlU+vCGXo47e6GyRydqTpbq0r49Zqmx+IJ6Z7iigAAAAAAAA==
--------------ms050405070101010502050101--
© André Zúquete Segurança Informática e nas Organizações 60
Assinaturas cegasAssinaturas cegasAssinaturas cegasAssinaturas cegas
� Assinaturas digitais em que o assinante “não vê” o que assina� Semelhantes a uma assinatura sobre um envelope fechado com
um documento e papel químico dentro� Servem para garantir o anonimato e a não alteração da
informação assinada� O assinante X sabe quem lhe pede a assinatura (Y)� X assina T1, mas Y depois recupera a assinatura sobre T2
� T2 não é qualquer, está associado a T1
� O requerente pode apresentar T2 assinado por X� Mas não pode alterar T2
� X não consegue associar T2 ao T1 que viu
31
© André Zúquete Segurança Informática e nas Organizações 61
Chaum Chaum Chaum Chaum BlindBlindBlindBlind SignaturesSignaturesSignaturesSignatures
� Usa RSA� Cegamento
� Factor de cegamento K aleatório� k × k-1 ≡ 1 (mod N)� m’ = ke × m mod N
� Assinatura normal� Ax (m’) = (m’)d mod N
� Anulação do cegamento� Ax (m) = k-1 × Ax (m’) mod N