Slides do curso de Segurança e Privacidade de Dados - UNICAMPmarco/cursos/ia012_14_1/slides/slides_ia... · IA012 (DCA-FEEC-UNICAMP) ver: 20140312 1 IA 012 Segurança em Comunicação

1IA012 (DCA-FEEC-UNICAMP) ver: 20140312

IA 012

Segurança em Comunicação de Dados

Prof. Marco A. A. Henriques

Faculdade de Engenharia Elétrica

e de Computação

Universidade Estadual de Campinas


Visão Geral

• Segurança de dados (SD)– No passado:

• meios físicos: arquivos e salas trancadas

• meios administrativos: seleção rigorosa de pessoal

– Atualmente:• necessidade de proteger dados em computadores

• interligação de computadores por redes tornou dados mais vulneráveis


Pontos Relevantes emSegurança de Dados

• Mecanismos de Segurança

• Serviços de Segurança

• Ataques (fraudes)


Mecanismos de Segurança

• Não há um mecanismo único que provê todos os serviços de segurança necessários.

• Maioria dos mecanismos têm um ponto em comum: CRIPTOGRAFIA.

• Quase todas as pesquisas em SD são voltadas às técnicas de criptografia.


Serviços de Segurança

• Documentos (dados) em forma eletrônica necessitam dos mesmos serviços (funções) associados aos seus pares em papel.– datas e assinaturas

– proteção contra destruição, modificação ou divulgação

– autenticação e registro

– gravação e licenciamento


Dificuldades comDocumentos Eletrônicos

• Peculiaridades dos documentos em forma eletrônica dificultam a implementação de serviços de segurança.

Função Documentos (dados) em papel eletrônicos

Distinção entre originais e cópias fácil (tipo de difícil (apenas

papel, cor) seq. de bits)

Comprovação de alteração (rasura) fácil (textura, difícil (rastrear

cor, etc.) troca de bits)

Autenticação (assinatura) fácil (formato difícil (baseada

de assinaturas e no conteúdo do

carimbos) documento)


Serviços de Segurança Comuns• Segredo

– conteúdo ou existência da informação só será conhecido por pessoas autorizadas.

• Autenticação– garante a identidade da

origem do documento.

• Integridade– informação só pode ser

alterada por pessoas autorizadas.

• Controle de acesso– seleção entre partes

autorizadas e não autorizadas.

• Disponibilidade– dados disponíveis sempre que

necessário.

• Não-rejeição– remetente e destinatário não

podem negar que uma mensagem foi transmitida em um certo instante.


Ataques (Fraudes)

• Segurança pode ser vista como prevenção e detecção de fraudes.

• Muitas formas distintas mas que se enquadram em 4 tipos genéricos:– Interrupção

– Interceptação

– Modificação

– Fabricação

• Podem ser também Passivos ou Ativos.


Modelo de Acesso Normal

• Sistema de informações (computador, rede):– provedor de informações no qual há um fluxo de

dados de uma origem (arquivo, região de memória, rede) para um destino (outro arquivo, monitor, memória).

Origemdos

dados

Destinodos

dados


Interrupção

• Bloqueia fluxo normal dos dados.

• Ataque à disponibilidade da informação.

• Exemplos:– destruição de partes do hardware (discos, links)– remoção de registros ou de arquivos

– tornar arquivo inacessível, mas sem apagá-lo

Origemdos

dados

Destinodos

dados


Interceptação• Acesso não autorizado aos dados.

• Ataque ao segredo da informação.

• Exemplos:– “grampos” em linhas telefônicas ou redes

– cópia não autorizada de arquivos

Origemdos

dados

Destinodos

dados

Destinonão

autorizado


Modificação• Alteração não autorizada dos dados.

• Ataque à integridade da informação.

• Exemplos:– mudança de valores em arquivos.

– transformação de programas em outros.

– alteração do conteúdo de mensagens.

Origemdos

dados

Destinodos

dados

Modificaçãonão

autorizada


Fabricação• Criação não autorizada de dados (falsificação).

• Ataque à autenticidade da informação.

• Exemplos:– inserção de mensagens falsas na rede.

– inserção de registros falsos em arquivos.

Origemdos

dados

Destinodos

dados

Criaçãode dados

falsos


Ataques Passivos• Limitam-se em obter informações sem

alterá-las.

• Interceptação é ataque passivo.

• Formas:– divulgação de conteúdo

– análise de tráfego: mesmo com o conteúdo codificado, ainda é possível obter informações como: identidade e localização das partes, horário e volume das transmissões, etc.

• Detecção difícil: melhor prevenir.


Ataques Ativos

• Há algum tipo de intervenção no sistema de informação.

• São ataques ativos:– Interrupção

– Modificação

– Fabricação

• Difíceis de prevenir– normalmente o objetivo é detectá-los.


Categorias de Ataques Ativos• Mascaramento:

– uma parte tenta se fazer passar por outra.

• Retransmissão: – captura passiva de dados seguida de retransmissões em

outros instantes sem modificações.

• Modificação de mensagens:– alteração de parte do conteúdo,

– imposição de atrasos na entrega,

– reordenamento.

• Rejeição:– uso ou administração do sistema é impedido pela

interrupção ou sobrecarga dos canais de comunicação.


Modelo de Segurança em Sistemas de Transmissão de Informação

Dados Dados

Codifi-cação

Decodi-ficação

Canal detransmissão

Intermediadorde transações

Espião


Técnicas de Segurança em Transmissão• Baseiam-se em dois componentes:

– Codificação da informação:• torna dados ilegíveis para terceiros,

• acrescenta código aos dados originais, autenticando o remetente.

– Compartilhamento de informação secreta pelo remetente e destinatário:

• define tipo de código usado.

• Intermediador de transações pode ser necessário– para distribuir a informação secreta para as partes,– para resolver problemas de autenticação das partes.


Projetos de Serviços de Segurança em Transmissão

• Projeto do algoritmo de codificação

• Geração da informação secreta

• Elaboração de métodos de distribuição e compartilhamento da informação secreta

• Especificação das regras de conversação entre as partes que faça uso do algoritmo de codificação


Segurança no Acesso à Informação

• Proteção dos dados e demais recursos mantidos em sistemas de informação.

• Invasor pode ser um programa (talvez embutido em programas legítimos) – vírus, worms, etc.

• Mecanismos de segurança no acesso– Função de controle de acesso (gatekeeper)

– Função de monitoramento e análise de atividades• detecção de condutas não usuais => invasores.


Função de Controle de Acesso

Invasor(indivíduo,programa)

Canal de acesso

• Recursos computacionais• Dados• Processos• Programas

Controle internode segurança

Controle

acesso

de

• Procedimentos de login baseados em senhas.

• Testes contra vírus e ataques similares.


Criptografia• Principal ferramenta em segurança.

• Duas variações principais

– Criptografia de Chave Única:• Também conhecida como Criptografia

Convencional ou Simétrica.

• Usa a mesma chave para cifrar e decifrar dado.

• Muito antiga e a mais usada.

– Criptografia de Chave Pública• Chaves distintas para cifrar e decifrar dados.

• Desenvolvimento recente (1976).


Sistemas de Criptografia• Classificação mais geral em três dimensões:

Númerode chaves

Tipo de operação nos dados

Substituição

Transposição

Chaves pública e privada

Chave única

Tipo de processamentonos dadosPor blocos

Por símbolos


Criptografia de Chave Única• Processo de Codificação consiste de:

– algoritmo de criptografia– chave

• independente dos dados,

• comum à codificação e decodificação.

Codificação Decodificação

Dadosinteligíveis

Dadosinteligíveis

Dadoscifrados

ChaveCompartilhada


Segurança da Criptografia Simétrica

• Depende do segredo da chave e não do segredo do algoritmo de criptografia.– Algoritmo não deve permitir a descoberta dos

dados baseada somente nos dados cifrados.

– Algoritmos não secretos possibilitam o aparecimento de circuitos de baixo custo.

• Problemas de segurança estão relacionados à – geração, – troca e – manutenção do segredo de chaves.


Modelo de Criptografia Simétrica

Geraçãode chave

CanalSeguro

Origemdos dados

Destinodos dados

Codificação Decodificação

Espião

YX X

X

K

ˆ

ˆ

K K


Notação• Dados originais: X = [X1, X2, X3, ..., XM]

• Chave única: K = [K1, K2, K3, ..., KJ ]

• Dados cifrados: Y = [Y1,Y2 ,Y3 , ..., YN]

– Xi , Yi e Ki são letras de um alfabeto (binário, por exemplo).

• Algoritmo de codificação: E

Y = EK(X)

• Algoritmo de decodificação: D

X = DK(Y)


Criptoanálise

• Tentativa de se descobrir X e/ou K.

• Técnica usada depende do que é conhecido.– Normalmente o algoritmo é conhecido.

– Força bruta: teste de todas as chaves possíveis.– Análise estatística: tipo do dado precisa ser

conhecido (Texto em inglês? Programa em C?).

– Análise de pares (Xi, Yi) conhecidos.• Obtidos casualmente ou intencionalmente.

– Adivinhação de palavras prováveis no texto.


Segurança dos Métodos de Criptografia

• Métodos Incondicionalmente Seguros– Dados cifrados não contêm informação suficiente

para se quebrar o código, independentemente do volume de dados disponível.

– Difíceis de obter.• Só há um exemplo: One-Time Pad.

• Demais métodos buscam satisfazer um dos critérios:– custo de quebrar o código excede o valor da informação.

– tempo requerido para quebrar o código excede o tempo de vida útil da informação.


Segurança dos Métodos de Criptografia• Métodos Computacionalmente Seguros

– Eficiência baseada no custo de quebrar o código.

– Problema: • difícil estimar tempo para analisar o código com sucesso.

• primeira estimativa: tempo para análise por força bruta.Tamanho da chave

Número de chaves

Tempo (1 código/µs)

Tempo (106 códigos/µs)

32 bits 232=4,3x109 231µs =35,8 min

2,15 ms

56 bits 256=7,2x1016 255µs =1142 anos

10,01 h

128 bits 2128=3,4x1038 2127µs =5,4x1024 anos

5,4x1018 anos

26 símbolos 26!=4,03x1026 2x1026µs =6,4x1012 anos

6,4x106 anos


Técnicas Básicas de Criptografia

• Esteganografia– Oculta a existência de uma mensagem.

• Substituição– Substitui um grupo de símbolos por outro.

• Transposição– Troca as posições dos símbolos.


Técnicas de Esteganografia• Verdadeira informação é oculta no meio de outras

sem valor (sobrecarga é alta).

• Ex: informação obtida a partir de– últimas palavras de cada linha de um texto;

– primeira letra de cada palavra;

– letras impressas sobrescritas com lápis;• visíveis quando há um reflexo adequado de luz;

– letras escritas com tinta invisível;• tornam-se visíveis ao receberem certa substância;

– letras marcadas com minúsculos furos no papel;– letras escritas com fita de correção nas entrelinhas.


Esteganografia em Computação

• É comum se encontrar mensagens, fotos, etc. escondidos em programas de computador (“Ovos de Páscoa”).

• Bit menos significativo de pixels de fotos ou amostras de som pode ser alterado sem mudar significativamente o conteúdo original.– Ex: uma foto de alta resolução, 2048 X 3072

pixels, cada pixel formado de 3 grupos de 8 bits (RGB), permite ocultar 2,25 MBytes.


Técnicas de Substituição• Código de Cesar

– Troca símbolo por outro k posições à frente no alfabeto.

– Ex: texto original: criptography texto cifrado: FULSWRJUDSKB (k=3)

• Forma geral:C = E(p) = (p+k) mod 26 (p/ cifrar)p = D(C) = (C-k) mod 26 (p/ decifrar)

• Ataque por força bruta:– alfabeto inglês: 25 chaves– alfabeto chinês: mais de 10.000 chaves


Códigos Monoalfabéticos• Chaves do código de Cesar são aumentadas

permutando-se a tabela de codificação:26! = 4,03 x 1026 possibilidades.

– Ex: original: a b c d ... x y zcifrado: o j p t ... m a f

• Frequência dos símbolos facilita a criptoanálise.– Na língua inglesa: Letra Frequência Relativa

e 12,75 %

t 9,25 %

r 8,50 %

. . . . . .


Comparação de Freqüências Relativas de Letras

Freqüênciarelativaà letra E

Texto em inglês

Código Playfair

Código Vigenère

Código Polialfabético Randômico

E T R N I O A S D L H C F U M P Y G W V B K X Q J Z

100%

0%


Códigos de Múltiplos Símbolos• Objetivo: ocultar a freqüência dos padrões com múltiplos símbolos.

• Código mais conhecido: Playfair– Substitui dígrafos no texto original por outros dígrafos.– Baseia-se em matriz 5x5 iniciada por senha.– Análise fácil: muito da estrutura original do texto é mantida.

M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z

Método de codificação:

• Letras repetidas recebem outra no meio.

• Letras na mesma linha: trocadas pelas à direita.

• Letras na mesma coluna: trocadas pelas inferiores.

• Outros casos: letra trocada por outra na mesma linha, mas na coluna de seu par no dígrafo.


Códigos Polialfabéticos

• Utilizam diferentes códigos monoalfabéticos.

• Chave determina qual código usar a cada instante.

• Cada símbolo tem codificação diferente, dependendo da chave.– Informação sobre freqüência de símbolos é

obscurecida (mas não totalmente).

• Ex: código de Vigenère e suas variantes.


Código Polialfabético de Vigenère

• Códigos monoalfabéticos: código de Cesar com chaves k = 0,1,2,...,25 (ou k = a,b,c,...,z): chave \texto --> a b c d . . . x y za A B C D . . . X Y Zb B C D E . . . Y Z Ac C D E F . . . Z A B... . . . . . . . . . .z Z A B C . . . W X Y

• Texto cifrado: – intersecção da coluna texto com linha chave:

– Ex: chave: codigoscodigoscodigostexto: salvesequempuderagoracódigo: UOOVKGWSIHUVIVGFDOUFS


Variações do Código de Vigenère• Auto-chave: próprio texto usado como parte da chave para

eliminar repetições na mesma.– Vulnerável: mesma distribuição de probabilidade para letras do

texto e da chave facilita análise.

• Chave longa e sem relação com o texto.– Método de Vernam: ou-exclusivo de bits

• Ci = pi ⊕ ki (xi é o i-ésimo bit do símbolo x)

• Chave longa, mas repetitiva (fita perfurada).

– Método One-Time Pad: usa chave randômica do mesmo tamanho que o texto.

• Código e texto sem relação estatística: análise dificultada.

• Remetente e destinatário: possuir e proteger a longa chave.


Técnicas de Transposição

• Baseiam-se na permutação de símbolos.

• Método mais comum: transposição por matriz– texto reescrito em colunas com profundidade k1.

– Ex: texto: cuide bem da senha chave: k1 = 3 matriz: cdean uemsh ibdea código: CDEANUEMSHIBDEA

– Extremamente vulnerável à criptoanálise.


Transposição de Colunas da Matriz

• Escrita do texto linha por linha e

• transposição de colunas segundo chave k2.

– Ex: texto: cuide bem da senha chave:k1 = 3 (quase sempre conhecida)

matriz: c u i d e b e m d a s e n h a chave: k2 = 5 1 3 2 4

código: UEEDDHIMNEAACBS

• Também vulnerável à criptoanálise.


Transposição Múltipla de Colunas

• Aplicação da mesma transposição mais de uma vez.

• Código torna-se bem mais seguro:– permutação inversa difícil (maior embaralhamento).

• Ex: texto: UEEDDHIMNEAACBS chave: k1 = 3 (conhecida) matriz: u e e d d h I m n e a a c b s chave: k2 = 5 1 3 2 4 código: EIADNBEMCDESUHA


Máquinas de Rotores• Facilitam criptografia em múltiplos estágios.

• Cada rotor:– tem 26 entradas conectadas a 26 saídas;

• cada pino de entrada se conecta a um único pino de saída

– define um código monoalfabético de substituição;

– gira com velocidade diferente dos outros;

• primeiro rotor: 1 passo a cada entrada feita

• segundo rotor: 1 passo a cada volta completa do primeiro

• terceiro rotor : 1 passo a cada volta completa do segundo

• n-ésimo rotor: 1 passo a cada volta completa do (n-1)-ésimo

• Número de rotores: 3 4 5Número de alfabetos: 17.576 456.976 11.881.376


Máquina de 3 Rotores121314151617181920212223242526 1 2 3 4 5 6 7 8 91011

15 426101618211314 8 619 2 711201222 2317 3 9 124 25 5

5 6 7 8 91011121314151617181920212223242526 1 2 3 4

181224 25 5211314 8 61915 4261022 2317 3 9 116 2 71120

212223242526 1 2 3 4 5 6 7 8 91011121314151617181920

211315 8 619 2 7 42610161814 522 2317 3112012 125 9 24

ABCDEFGHIJKLMNOPQRSTUVWXYZ

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Direçãode giro

RápidoMédioLento

Entra O

Entra R

Sai M

Sai Z


Data Encryption Standard (DES)• Codifica 64 bits em 64 bits com chave de 56 bits em

várias etapas (codificação múltipla).– Mesmas etapas e chave usadas para decodificação.

• Versão simplificada do algoritmo LUCIFER da IBM– LUCIFER: chave de 128 bits

– DES: chave reduzida p/ viabilizar implementação em chips

• Adotado pelo NIST (1977) como padrão americano.– Muito criticado por manter princípios do projeto em sigilo

(porta dos fundos?) e por reduzir o tamanho da chave.

– Trabalhos recentes em criptoanálise indicam estrutura interna forte no DES, mas há vulnerabilidades a explorar.


Cri

ptog

rafi

a co

m D

ES

Perm

utaç

ão I

nici

al

Iter

ação

1

Tro

ca L

x R

Per

mut

ação

In

icia

l Inv

ersa

Iter

ação

2

Iter

ação

16

Perm

utaç

ão 2

Perm

utaç

ão 2

Perm

utaç

ão 2

Des

loca

men

to

Des

loca

men

to

Des

loca

men

to

Per

mut

ação

1

Cha

ve56

bits

Tex

to64

bits

Cód

igo

64 b

its

k 1

k 16k 2


Características de DES

• Decodificação– Mesmo algoritmo aplicado no código, mas com

chaves ki em ordem inversa.

• Efeito Avalanche– Muitos bits deveriam mudar com a alteração de

1 bit do texto ou da chave.– Ex: troca de 1 bit em: texto chave

mudança no código: 34 bits 35 bits


Segurança de DES• Há 2 preocupações básicas:

– Tamanho da chave: 56 bits (7,2 x 1016 chaves)• Em 1993: projeto de chip que busca 50 x 106 chaves/seg.

Tempo de busca Custo35 horas US$ 100.000

3,5 horas US$1.000.00021 min. US$10.000.000

• Técnica da “Loteria Chinesa”: teoricamente chave seria descoberta em segundos.

– Critérios do projeto de DES são mantidos em segredo.• Existiria maneira “direta” de analisar o código?

• Alguns comportamentos estranhos foram descobertos.


Modos de Operação de DES

• Há quatro modos básicos.– ECB: Electronic Codebook– CBC: Cipher Block Chaining

– CFB: Cipher Feedback

– OFB: Output Feedback

• Seleção depende da aplicação.


Modo Electronic Codebook (ECB)• Cada bloco de 64 bits cifrado com a mesma chave.

– Uma combinação de bits de entrada sempre produz uma mesma combinação de bits na saída.

– Grande tabela de 264 símbolos.

• Não adequado para transmissão de grandes volumes de dados com estrutura regular.

• Se há campos nos dados repetindo-se a distâncias múltiplas de 64 bits, dados dos campos podem ser trocados no código de saída.


Algoritmo Electronic Codebook

CifrarK

P1

C1

DecifrarK

P1

C1

Tempo: 1 2 N

CifrarK

P2

C2

DecifrarK

P2

C2

CifrarK

PN

CN

DecifrarK

PN

CN

Codificação

Decodificação


Modo Cipher Block Chaining (CBC)

• Evita que texto repetido gere mesmo código.– Código já produzido é usado na geração de novo

código.

Cn = Ek ( Cn-1 ⊕ Pn )

– Vetor de Inicialização (IV) é usado no primeiro estágio.

• C0 = IV

• Conhecimento de IV pode facilitar criptoanálise.

• Mais robusto que ECB para textos maiores que 64 bits.


Algoritmo Cipher Block Chaining

Tempo: 1 2 N

Codificação

Decodificação

P1

CifrarK

C1

IV

P2

CifrarK

C2

PN

CifrarK

CN

CN-1

P1

DecifrarK

IV

P2

K

PN

K

CN-1

Decifrar Decifrar


Modo Cipher Feedback (CFB)

• Não necessita de número inteiro de blocos de 64 bits: codificação de cadeias de dados.

• Dados cifrados e enviados em tempo real em blocos adequados ao meio.– Codifica e envia blocos de j bits, onde j é o

tamanho em bits da unidade de transmissão.

• Código atual depende dos códigos passados.


Algoritmo Cipher Feedback (Codificação)

Reg. deslocamento64 - b bits b bits

Usa Descartab bits 64 - b bits

Cifrar

64

64

b

K



Cifrar

64

64

b

K



Cifrar

64

64

b

K

P1 P2 PNC1

b b b

C2

bb b

CN

CN-1


Algoritmo Cipher Feedback (Decodificação)



Cifrar

64

64

b

K



Cifrar

64

64

b

K



Cifrar

64

64

b

K

P1 P2 PNC1

b b b

C2

bb b

CN

CN-1

Decodificação


Modo Output Feedback (OFB)• Similar ao CFB.

– Os j bits usados para compor próximo código são obtidos da saída do DES e não do resultado da codificação passada.

• Mais robusto a erros de transmissão.– Erros no código Ci só afetarão o texto Pi.

– Adequado para transmissão de cadeias de dados em canais ruidosos.

• Mais vulnerável que CFB a ataques de modificação na mensagem.– Alteração de 1 bit do código altera só 1 bit no texto.


Algoritmo Output Feedback (Codificação)



Cifrar

64

64

K



Cifrar

64

64

K



Cifrar

64

64

b

K

P1 P2 PNC1

b b b

C2

bbb

CN

ON-1

b b


Algoritmo Output Feedback (Decodificação)



Cifrar

64

64

K



Cifrar

64

64

K



Cifrar

64

64

b

K

P1 P2 PNC1

b b b

C2

bbb

CN

ON-1

b b


DES Múltiplo

• Problema:– Vulnerabilidade do DES simples a ataques por

força bruta.

• Soluções:– Pesquisar e propor um algoritmo completamente

novo.• Novos investimentos são necessários.

– Usar DES múltiplas vezes com diferentes chaves.• Aproveita os investimentos feitos até agora.


Modelo de DES Duplo

CifrarPT

C

K1 K2

Cifrar

T

K2 K1

DecifrarDecifrarC P

Codificação

Decodificação


Características de DES Duplo• Dois estágios com duas chaves distintas

– Codificação: C = Ek2 [ Ek1 ( P ) ]

– Decodificação: P = Dk1 [ Dk2 ( C ) ]

– Equivale a aumentar chave de 56 para 112 bits?

• Problema:– Será que Ek2 [ Ek1 ( P ) ] = Ek3 ( P ) ?

– Número de permutações possíveis: 264! > 1010 20

– Número de chaves: 256 < 1017

– É pouco provável que duas das 256 chaves sejam equivalentes a outra também dentro das 256.


Permutações

P C C C C C C . . . C k0=0 k1=1 k2=2 k3=3 ? ? . . . ? 0 5 4 3 7 6 2 . . . 1 1 3 1 7 2 4 6 . . . 0 2 1 5 1 6 3 2 . . . 4 3 2 7 5 0 1 4 . . . 6 4 0 2 4 5 6 3 . . . 7 5 7 3 6 1 7 5 . . . 2

C = Ek1 [ Ek0 ( P ) ] = Ek2 ( P )

Exemplo para P com 3 bits e k com 2 bits.


Ataque tipo Meet-in-the-Middle

• Ataca qualquer código baseado em blocos.

• Dados um bloco P e seu código C de 64 bits– cifra-se P com as 256 chaves k1 --> T = Ek1(P) ;

– ordena-se todos os códigos T;

– decifra-se C com as 256 chaves k2 --> T = Dk2(C) ;

– a cada novo T obtido verifica-se se já ocorreu antes;– se ocorreu, testa-se outro par (P,C) para confirmar se

chaves (k1,k2) são as corretas.

– o esforço será de 2 x 256 e não 2112 .


Modelo de DES Triplo

CifrarPT1 T2

K1 K2

Decifrar

Codificação

Decodificação

C

K1

Cifrar

DecifrarCT2 T1

K1 K2

Cifrar P

K1

Decifrar


Características de DES Triplo• Combate o ataque Meet-in-the-middle

– inclusão de um estágio extra: esforço de análise aumentado para 256 + 2112 ;

• há métodos de análise menos custosos, mas exigem 256 pares (P,C) ou estão próximos aos 2112 ;

– combina operações de cifrar e decifrar: compatibilidade com DES simplesC = Ek1 { Dk1[ Ek1 ( P ) ] } = Ek1 ( P ) ;

• Alternativa popular para o DES simples bastante utilizada na prática.– normas ANS X9.17 e ISO 8732


AES: Advanced Encryption Standard

• Novo algoritmo de criptografia simétrica padronizado pelo governo americano.

• Motivações:– DES vulnerável a ataques por força bruta (chave de apenas 56

bits):• NIST determinou em 1999 que DES Triplo (3DES) fosse adotado em

novas implementações;

– DES e 3DES não são eficientes se implementados em software:• projeto original voltado para hardware;

– DES e 3DES usam blocos de dados de apenas 64 bits:• blocos maiores são desejáveis por questões de segurança e eficiência.


AES: histórico• NIST lançou pedido de propostas em 1997 para um AES:

– tão ou mais seguro que 3DES;

– mais eficiente que 3DES;

– com bloco de dados de pelo menos 128 bits;

– com chave de 128, 192 e 256 bits.

• Primeira avaliação do NIST selecionou 15 dentre 21 propostas iniciais (1998).

• Segunda avaliação selecionou 5 finalistas (1999): MARS, TWOFISH, RC6, RIJNDAEL e SERPENT.

• Terceira e última avaliação definiu RIJNDAEL como o novo padrão AES (2000).– Norma FIPS PUB 197 publicada em 11/2001.

– Substituição de 3DES será gradual.


AES: avaliação de RIJNDAEL (I)• Não há ataques conhecidos.

• Implementação em software :– eficiente para CPUs de 8 a 64 bits;

– ocupa pouco espaço, principalmente se for dedicada só a cifragem ou decifragem.

• Implementação em hardware:– modos com realimentação: o mais rápido dentre os finalistas;

– modos sem realimentação: segundo mais rápido.

• Robusto contra ataques de temporização e de alimentação.

• Cifragem e decifragem diferem pouco em tempo, mas requerem 60% mais espaço em hardware que implementação só da cifragem.


AES: avaliação de RIJNDAEL (II)• Preparação de subchaves pode ser feita durante a

cifragem.– Antes da decifragem todas as subchaves já devem estar

prontas.

• Suporta todas as combinações entre os seguintes tamanhos de bloco e de chave: 128, 192 e 256 bits.– Permite trabalhar com outros tamanhos múltiplos de 32

bits (AES adotou bloco de dados fixo de 128 bits).

• Na cifragem de um bloco é possível explorar paralelismo de instruções.


AES: estrutura interna• Bloco de dados e chave: organizados em matriz de 4 x 4 bytes.

– Matriz da chave é expandida em 44, 52 ou 60 vetores de 4 x 1 bytes (subchaves).

• Iterações sobre dados: 10, 12 ou 14, dependendo do tamanho da chave.

• Cada iteração (exceto última) tem 4 etapas:– substituição de bytes

– deslocamentos na linha

– combinação de colunas

– soma de subchave

• Antes da 1a. iteração: soma de subchave.

• Última iteração: não tem combinação de colunas.


AES: etapas da cifragem e decifragem


AES: matriz de estados


AES: chave expandida


AES: detalhamento de uma iteração


AES: etapa de substituição de bytes


AES: etapa de deslocamentos na linha


AES: etapa de combinação de colunas


AES: etapa de soma de subchave


AES: expansão da chave


AES: características relevantes• Só a etapa de soma de subchave faz uso da chave.

– Por isso é usada no início e no fim, pois as outras etapas são reversíveis sem o conhecimento da chave.

• Algoritmo pode ser visto como uma seqüência de cifragem XOR (soma de subchave) acompanhada de uma mistura dos bytes (para prover confusão, difusão e não-linearidade).

• Cada etapa é reversível para permitir a decifragem.

• Etapas inversas são agrupadas de forma distinta na decifragem.


Sigilo com Criptografia Convencional

• Localização da lógica de criptografia

• Uso de criptografia contra ataques por análise de tráfego

• Distribuição de chaves

• Geração de números aleatórios


Localizações Vulneráveis• Hardware da rede: cabos, roteadores, chaves

– Pacotes com endereços de origem e destino são propagados por grande parte da LAN.

– Fibra ótica menos vulnerável a ataques.

• Portas de acesso discado em estações– Invasores podem ganhar acesso à rede.

• Armários de cabeamento– Pequenos transmissores podem ser colocados

em cabos selecionados.

• Estações: memória, periféricos, etc.


Codificação de Enlace

• Cada enlace de comunicação tem equipamento de codificação/decodificação em cada extremo.

• Custos elevados.

• Pacote deve ser decodificado para ser roteado:– roteadores são pontos vulneráveis.

• Uma chave para cada enlace: – muitas chaves;– autenticação do transmissor fica dificultada.

• Cada chave distribuída somente para 2 nós.


Codificação Ponto-a-Ponto• Codificação só ocorre nos nós extremos da

transmissão:– chave única;– autenticação do transmissor fica facilitada.

• Vulnerabilidades na rede não são importantes.

• Parte com endereço do destinatário no pacote não é codificada:– análise de tráfego torna-se possível;

• Maior segurança obtida usando-se ambas as codificações: análise de tráfego dificultada.


Localização da Codificação Ponto-a-Ponto

• Em software ou hardware na camada de rede da pilha de protocolo– número de entidades usando criptografia = número

de pontos da rede.– há situações práticas que inviabilizam esta opção:

conexões entre redes.

• Em software na camada de aplicação– evita problemas de conexão entre redes

– muitas entidades envolvidas (processos e usuários)• geração e distribuição de chaves é dificultada.


Comparação de Localizações

Enlace-H IP-H TCP-H Enlace-TDados





(A) Codificação no nível da aplicação (dados se mantêm codificados)

(B.1) Codificação no nível de transporte: pacote nos enlaces e roteadores.

(B.2) Codificação no nível de transporte: pacote nos gateways.

(C.1) Codificação no nível de rede: pacote nos enlaces.

(C.2) Codificação no nível de rede: pacote nos roteadores e gateways.


Sigilo de Tráfego

• Informações disponíveis no tráfego:– identidade das partes;

– o quão frequente são as comunicações;

– padrão, comprimento e quantidade de mensagens que sugiram a importância da mesma;

– possível correlação entre eventos e transmissão de mensagens entre duas partes determinadas.


Transmissões Camufladas• Comprimento, freqüência ou padrão das

mensagens pode servir para camuflar outros dados sendo transmitidos.

• Ex: – alguém pode passar informações para um espião

externo através de mensagens cujo comprimento pode indicar os bits 0 e 1.

– o tempo de demora para se obter o prompt “login:” de uma estação pode servir para se passar bits 0 e 1 a um estranho (a estação seria sobrecarregada intencionalmente pelo parceiro interno).


Sigilo de Tráfego com Codificação de Enlace

• Codificação de enlace não inibe análise de quantidade de tráfego.

• Contra-medida:– inserir dados aleatórios quando não existem

dados reais para serem enviados.

– fluxo de dados é mantido constante no enlace.


Sigilo de Tráfego com Codificação Ponto-a-Ponto

• Codificação ponto-a-ponto não inibe análise de detalhes do tráfego.

• Contra-medidas:– inserção de mensagens aleatórias;

– formatação das mensagens em um tamanho único;


Distribuição de Chaves

• Troca de chaves entre A e B:– A escolhe chave e entrega fisicamente a B;– um terceiro (C) escolhe e entrega fisicamente a

chave para A e B;– se A e B já compartilham uma chave secreta,

esta pode ser usada para envio de nova chave;

– se A e B possuem uma conexão segura com C, este pode entregar a chave aos dois através de canais codificados.


Número de Chaves

• Codificação de Enlace– número de chaves = número de enlaces– distribuição ocorre entre nós vizinhos

• Codificação Ponto-a-Ponto– número de chaves = número de pares = N(N-1)/2– codificação na camada de rede ou transporte:

• N = número de computadores

– codificação na camada de aplicação:• N = número de processos ( ~ número de usuários)


Diversificação de Chaves• Chave mestra:

– compartilhada entre cada usuário ou processo e um centro de distribuição de chaves (KDC);

– usada para codificar e distribuir chaves de sessão.

• Chave de sessão:– usada em cada nova conexão (sessão) entre 2 partes;

– definida e distribuída pelo KDC;

– validade limitada a uma sessão lógica (descartável).

• Número de chaves armazenadas:– reduzido de N(N-1)/2 para N.


Exemplo de Distribuição

Ana

Beto

KDC

(1) Pedido, NA

EkA{kS, Pedido, NA, EkB(kS, IDA)}

(3) EkB ( kS, IDA )

(4) EkS ( kS, NB )

(5) EkS { f(NB )}

Distribuição

Distribuição

Distribuição

Autenticação

Autenticação

Autenticação

(2)


Passos da Distribuição (I)

(1) Pedido de chave de sessão de Ana a KDC contendo– identificador único de sessão (nonce NA): número aleatório,

horário, contagem etc.,

– identidades das partes: Ana (IDA) e Beto (IDB).

(2) Resposta cifrada com kA para Ana contendo

– chave de sessão descartável kS ,

– pedido original: para saber se mensagem foi alterada,

– chave kS e identificador IDA cifrados com chave de Beto

kB: para serem enviados a Beto como credenciais de Ana.


Passos da Distribuição (II)(3) Repasse de Ana a Beto dos dados cifrados com kB

recebidos do KDC.– Só Beto pode decifrar os dados e ficar sabendo com quem

se comunicar e que chave de sessão kS usar.

(4) Envio de Beto a Ana de nonce NB cifrado com kS.

– Pedido de confirmação de Ana.

(5) Resposta de Ana com f(NB) cifrada com kS.

– f(NB) pode ser qualquer função previamente combinada.Ex: f(NB) = NB +1.

– f(NB) previne que um intruso se passe por Ana.


Distribuição Descentralizada

Ana Beto

(1) Pedido, IDA ,NA

(2) EkM{kS, Pedido, IDA , NA, IDB , f(NA), NB}

(3) EkS {f(NB)}

Distribuição

Autenticação

Distribuição

Autenticação


Passos na Distribuição Descentralizada(1) Pedido de Ana a Beto de chave de sessão kS com

– identidade de Ana IDA,

– número aleatório (nonce) NA (desafio)

(2) Resposta de Beto cifrada com chave mestra com– chave de sessão descartável kS criada por Beto,

– pedido original: para confirmação e averiguação,

– identidade de Beto IDB ,

– resposta ao desafio f(NA) : para garantir que é Beto,

– novo desafio nonce NB : para verificar se é Ana.

(3) Confirmação de Ana cifrada com chave kS contendo

– resposta ao desafio f(NB) : para garantir que é Ana.


Controle do Uso de Chaves• Chaves de sessão devem ser diferenciadas

segundo seu uso.– Chave para codificação de arquivos– Chave para codificação de PINs– Chave para codificação de mensagens

• Distinção limita os modos de uso das chaves.

• Modos de controle– Rótulo associado à chave

– Vetor de controle da chave


Controle por Rótulo Associado

• Chaves em DES: 64 bits - 8 bits ignorados = 56 bits úteis

• Rótulo usa os 8 bits ignorados.– Um bit indica se chave é mestra ou de sessão.

– Um bit indica se chave pode cifrar.

– Um bit indica se chave pode decifrar.

– Demais bits reservados para uso futuro.

• Prós (+) e contras (-):– Rótulo faz parte da chave e é protegido. (+)

– Rótulo é limitado a 8 bits. (-)

– Rótulo também é cifrado e só é visível no destino. (-)


Controle por Vetor de Controle• Vetor de Controle (CV)

– Vários campos descrevendo usos e restrições.– Tamanho pode variar.

– Combinado com chave de sessão quando ela é gerada.• HCV = h(CV) : vetor CV mapeado em outro (HVC) de mesmo

tamanho que chave gerada usando função hash h.

• k’M = kM ⊕ HCV : ou-exclusivo de chave mestra com HCV .

• Cks = Ek’M (kS) : chave de sessão é cifrada com nova chave mestra k’M contendo informação sobre CV.

– Usado na recuperação da chave de sessão.• kS = Dk’M (Cks) : chave k’M precisa ser preparada no destino

como foi na origem.


Combinação do Vetor de Controle com Chave de Sessão

kS kSCks

kM

CV

kM

CV

k’M k’M

Cifrar Decifrar

FunçãoHash

FunçãoHash

envio de CV


Comparação do Vetor de Controle com Rótulos

• Duas vantagens– Não há restrições de tamanho: controles

sofisticados podem ser adotados.

– Vetor não é codificado: em qualquer etapa do processo o controle do uso da chave pode ser exercido.


Criptografia Assimétricaou de Chave Pública

• Revolução na criptografia.– Diffie e Hellman (1976)

• Baseada em funções matemáticas.– Métodos anteriores só usavam permutações e

substituições.

• Chaves diferentes para cifrar e decifrar.– Impacto positivo no sigilo, distribuição de

chaves e autenticação.


Criptografia Simétrica X Assimétrica• Assimétrica não é mais resistente à criptoanálise.

– Resistência depende do tamanho da chave e algoritmo de codificação.

• Simétrica não se tornou obsoleta e inútil.– Grande esforço computacional para codificar

assimetricamente.

• Distribuição de chaves na assimétrica não é trivial.– Requer agente central para chaves públicas.

– Protocolos não são mais simples nem eficientes que os da criptografia simétrica.


Motivações para Criptografia Assimétrica

• Dificuldades e distribuir chaves secretas.– Distribuição é o ponto fraco em criptografia

simétrica.

• Necessidade de autenticar documentos digitalmente.– Como garantir que uma mensagem foi enviada

por alguém em particular?


Características de Criptografia Assimétrica (CA)

• Necessárias– Uso de chaves distintas para cifrar e decifrar.

– Inviabilidade de se obter chave privada, mesmo conhecendo-se:

• algoritmo de codificação,

• chave pública,

• amostras de texto cifrado.

• Opcional– Uso de qualquer das duas chaves para cifrar e a

outra para decifrar.


Usos de Criptografia Assimétrica

• Codificação & Decodificação– Prover sigilo para mensagens.

• Autenticação– Garantir identidade do transmissor.

• Troca de chaves de sessão– Prover segurança na obtenção de novas chaves.


Notação em CA

• Chave Secreta ou de Sessão: KS

– usada na criptografia simétrica

• Chave Pública: Kpu

• Chave Privada: Kpr

• Mensagem decodificada:

P = {P1, P2, ... , PM}

• Mensagem codificada:

C = {C1, C2, ... , CN}


Usos de CA: Sigilo• Qualquer um pode cifrar e enviar a Beto.

• Somente Beto poderá ler texto P.

C = EKpuB(P)

P = DKprB(C)

Cifrar DecifrarPC

P

Chave Públicade Beto (KpuB)

Chave Privadade Beto (KprB)


Usos de CA: Autenticação• Qualquer um pode decifrar.

• Somente Ana poderia ter enviado texto P.

C = EKprA(P)

P = DKpuA(C)

Cifrar DecifrarPC

P

Chave Privadade Ana (KprA)

Chave Públicade Ana (KpuA)


Usos de CA: Sigilo & Autenticação• Duas características são garantidas.

• Somente Beto poderá ler e conferir autenticidade do texto P.

Z = EKpuB{EKprA(P)}

P = DKpuA{DKprB(Z)}

Cifrar DecifrarC Z C

Chave Públicade Beto (KpuB)

Chave Privadade Beto (KprB)

CifrarP

DecifrarP

Chave Privadade Ana (KprA)

Chave Públicade Ana (KpuA)


Condições para CA• Necessárias:

– Geração de par de chaves: viável.

– Codificação com chave pública: viável.

– Decodificação com chave privada: viável.

– Determinação de chave privada a partir de chave pública: inviável.

– Determinação de chave privada a partir de chave pública e texto cifrado: inviável.

• Desejável:– Inversão de papéis das chaves pública e privada: viável.

• Obs:– Viável: solúvel em tempo polinomial.

– Inviável: solúvel em tempo exponencial.


Criptoanálise em CA• Ataque por força bruta:

– Prevenção com uso de chaves grandes• também dificultam o uso normal dos algoritmos.

– Compromisso entre tamanhos de chaves é necessário.

• Conclusão:– CA restrito a:

• distribuição de chaves e

• autenticação.


Criptoanálise em CA

• Ataque por cálculo de chave privada a partir da pública.– Ainda não foi provado que tal ataque é inviável.

– Um método pode ser descoberto a qualquer momento.

• Novas abordagens nunca antes pensadas podem levar a resultados surpreendentes.


Criptoanálise em CA

• Ataque tipo mensagem provável.– Dado: mensagem consiste de chave de sessão KS de

n bits: C = EKpu (KS) .

– Criptoanalista gera e cifra, com chave pública, 2n chaves KSi : Ci = EKpu (KSi), i = 0,1,2, ...,2n - 1.

– Criptoanalista busca Ci = C .

– Esforço limitado a 2n buscas e independente de Kpu e Kpr.

– Ataque pode ser prevenido inserindo-se bits aleatórios extras na chave de sessão KS .


Algoritmo RSA

• Desenvolvido em 1977 por Rivest, Shamir e Adleman no MIT (publicado em 1978).

• Resposta ao desafio lançado por Diffie e Hellman em 1976.

• O mais popular dos algoritmos de CA.

• Codificador por blocos:– texto cifrado ou não é formado por n inteiros de

0 a n-1.

• Baseado em funções exponenciais.


Uso de RSA

• Codificação

C = P e mod n

• Decodificação

P = C d mod n = (P e ) d mod n = P e d mod n

• Obs:– chave pública: Kpu = (e,n)– chave privada: Kpr = (d, n)


Questões em RSA

• Existem valores que satisfaçam

P = P e d mod n ?

• É viável calcular P e e C d para todo P < n?

• É viável calcular d a partir de e, n e pares (P,C)?


Fundamentos de RSA (I)

• Se P < n , então P = P mod n .

• Se P mod n = P e d mod n , então

P e d ≡ P mod n

(P e d e P são congruentes módulo n)

• Se mdc(a,b) = 1 , então a e b são relativamente primos (RP, primos entre si).


Fundamentos de RSA (II)• Função Totient de Euler: φ (n)

– φ (n) retorna o número de inteiros menores que n e RP em relação a n.

• Se n é primo, então φ (n) = n - 1 .

– Se p e q são números primos e n=pq, então φ (n) = φ (pq) = (p-1)(q-1)

• Se p e q são primos e k um inteiro, então m kφ (n)+1 = m k(p-1)(q-1)+1 ≡ m mod n

(Teorema de Euler)


Fundamentos de RSA (III)

• Se P e d ≡ P mod n, então

e d = k φ (n) + 1 ou

e d ≡ 1 mod φ (n) ou

e d ≡ 1 mod {(p-1)(q-1)} ou

e ≡ d -1 mod {(p-1)(q-1)}


Geração de Chaves em RSA

• Selecionar dois números primos p e q .

• Calcular n = pq e φ (n) = (p-1)(q-1) .

• Escolher inteiro d tal que: – mdc(φ (n) , d ) = 1 e 1 < d < φ (n) .

• Calcular e tal que e d ≡ 1 mod φ (n) .

• Chave pública: Kpu = ( e , n )

• Chave privada: Kpr = ( d , n )


Exemplo de Uso de RSA

• Seleção de dois primos: p = 3 e q = 11 .

• Cálculo de n e φ (n) : n = pq = 33 ; φ (n) = (p - 1)(q - 1) = 20 .

• Escolha da chave para decifrar d : d = 7, já que mdc(20,7) = 1, e 1 < 7 < 20 .

• Cálculo de e : 7e ≡ 1 mod 20; logo e = 3 .

• Codificação de P = 19 : C = P e mod n = 193 mod 33 = 28.

• Decodificação: P = C d mod n = 287 mod 33 = 19.


Criptoanálise em RSA (I)

• Ataque– Fatorar n em seus 2 fatores primos p e q:

permite obter φ (n) e calcular d .

• Contra-ataque: usar p e q grandes.– Melhor algoritmo de fatoração leva tempo

proporcional a e sqrt { ln n x ln ( ln n ) }

Tamanho de n Tempo (1012 códigos/seg)

100 dígitos 3 horas150 dígitos 4 meses

200 dígitos 3170 anos


Criptoanálise em RSA (II)

• Ataques– Determinar φ (n) ou d diretamente, sem saber p ou q .

• Tarefa tão difícil quanto fatorar n .

– Tentar todas as possíveis chaves privadas (força bruta).• Contra-ataque: usar chaves grandes.

• Desvantagem: algoritmo lento.


Distribuição de Chaves de Sessão usando Algoritmos de Chave Pública

• Algoritmos de chave pública são lentos– melhor utilizá-los para distribuir chaves secretas de

sessão de algoritmos mais rápidos.

• Distribuição Simples– Ana gera par (KpuA, KprA) e envia a Beto (KpuA, IDA).

– Beto gera KS e envia a Ana codificado com KpuA.

– Ana recupera KS usando KprA e estabelece com Beto um canal secreto, usando um algoritmo mais rápido com KS.


Falha na Distribuição Simples• Mecanismo anterior é vulnerável a ataque ativo.

– Ana gera par (KpuA, KprA) e envia a Beto o par (KpuA, IDA).

– Caio intercepta mensagem e troca KpuA por KpuC .

– Beto gera KS e envia a Ana codificado com KpuC .

– Caio intercepta mensagem, decifra KS e envia EKpuA(KS) a Ana.

– Como Caio conhece KS , poderá decifrar todas as comunicações futuras entre Ana e Beto.


Distribuição de Chave de Sessão com Sigilo e Autenticação

• Assumindo que Ana e Beto já trocaram suas chaves públicas de um modo seguro:

Ana Beto

(1) EKpuB(N1, IDA)

(2) EKpuA(N1, N2)

(3) EKpuB{N2 , EKprA(KS)}


Método Híbrido• Uso de chaves públicas para distribuir chaves de

sessão pode ser lento em ambientes que necessitam distribuir muitas chaves.

• Solução:– Centro de distribuição de chaves (KDC) compartilha

uma chave mestra com cada usuário.

– Chave mestra usada para distribuir chaves de sessão.– Chaves públicas usadas apenas para distribuir e

atualizar esporadicamente chaves mestra.


Distribuição de Chaves Públicas

• Quatro categorias principais– Anúncio público

– Diretório público

– Autoridade administradora de chaves

– Certificados


Distribuição por Anúncio Público

• Cada parte envia a outras sua chave pública.– Popularidade do software PGP (Pretty Good

Privacy) estimulou a prática de anexar chave pública em cada mensagem enviada.

• Problemas: – Distribuição não controlada de chaves.– Usuário A pode se fazer passar por B, criando e

distribuindo uma chave como se fosse A.


Distribuição por Anúncio Público

Ana Beto

KpuA

KpuA

KpuA

KpuA

KpuB

KpuB

KpuB

KpuB


Distribuição por Diretório Público

• Um diretório público contendo chaves públicas é mantido por alguma entidade de confiança.

• Características– Para cada parte há um par (nome, chave).

– Partes têm que registrar suas chaves usando algum mecanismo confiável de autenticação.

– Partes podem substituir suas chaves se necessário.

– Chaves são acessadas através de uma publicação (lista) impressa pela entidade mantenedora ou eletronicamente (canal autenticado é fundamental).


Distribuição por Diretório Público

DiretórioPúblico de

Chaves

Ana Beto

KpuA KpuB


Autoridade Administradora de Chaves

• Características – Implementa controle mais estrito sobre

distribuição de chaves de diretório público.

– Autoridade possui suas próprias chaves pública e privada para garantir distribuição.

– Demais partes devem conhecer com segurança a chave pública da autoridade.

– Distribuição usa protocolo com 7 mensagens.• 4 delas são necessárias poucas vezes.


Protocolo de Distribuição de Chaves(1) Ana envia à autoridade pedido datado

solicitando chave pública de Beto.

(2) Autoridade responde com mensagem codificada por KprAut contendo:

– KpuB : chave pública de Beto

– Pedido original: garantia de integridade.

(3) Ana envia a Beto mensagem codificada por KpuB contendo:

– Identificador de Ana: IDA

– Número aleatório (nonce) N1: identifica transação.


Protocolo de Distribuição de Chaves

(4), (5) Beto obtém da autoridade a chave pública de Ana, como nos passos (1) e (2).

(6) Beto envia a Ana mensagem codificada por KpuA contendo nonce N1 e um novo nonce N2.

– Garantia da identidade de Beto é reforçada por N1 .

(7) Ana devolve a Beto o nonce N2 .

– Garantia da identidade de Ana é reforçada por N2 .


Protocolo de Distribuição de Chaves

DiretórioPúblico

Autoridade

Ana Beto

(1) Pedido de KpuB

(2) EKprAut(KpuB , Pedido)

(3) EKpuB(IDA, N1)

(4) Pedido de KpuA

(5) EKprAut(KpuA , Pedido)

(6) EKpuA (N1, N2)

(7) EKpuB (N2)


Certificados Públicos

• Diretórios públicos são pontos de gargalo e sujeitos a ataques.

• Certificados: – permitem troca confiável de chaves entre partes sem

contato com a autoridade;– são criados por autoridade certificadora;– partes podem verificar autenticidade dos certificados.


Características de Certificados

• Qualquer parte pode ler um certificado para obter nome e chave pública do dono do mesmo.

• Qualquer parte pode verificar se o certificado– é de origem autêntica, – está íntegro,

– ainda está válido.

• Somente a autoridade certificadora pode criar e atualizar certificados.


Uso de Certificados• Partes interessadas solicitam certificados à

autoridade, fornecendo suas chaves públicas.– Pedido deve ser feito pessoalmente ou usando um

canal de comunicação confiável.

• Autoridade fornece certificado para A na formaCA = EKprAut (T, IDA, KpuA)

• Parte B recebe certificado e o verifica:(T, IDA, KpuA) = DKpuAut {EKprAut (T, IDA, KpuA)}

T : indica prazo de validade do certificado

IDA : fornece identidade do portador do certificado


Protocolo de Troca de Certificados

AutoridadeCertificadora

Ana Beto

(1) KpuA

(2) CA=EKprAut(T1, IDA,KpuA)

(5) CA

(3) KpuB

(4) CB= EKprAut(T2, IDB,KpuB)

(6) CB


Esquema de troca de chaves de Diffie-Hellman

• Primeiro algoritmo de chave pública que foi publicado (1976).– Williamson (CESG-Inglaterra) diz ter inventado o

mesmo algoritmo alguns meses antes.

• Limitado somente a troca segura de chaves secretas (chaves de sessão).

• Baseia-se na dificuldade de se calcular logaritmos discretos.


Logaritmo Discreto• Definido sobre a aritmética modular.

• Raiz primitiva de um número primo p: é um valor cujas potências usando mod p podem gerar todos os inteiros de 1 a p - 1.– Se r é uma raiz primitiva de p, então r mod p, r2 mod p, r3

mod p, . . . , r p-1mod p é uma seqüência dos inteiros de 1 a p - 1 em alguma ordem.

• Logaritmo Discreto: valor l (0≤ l < p) que satisfaz X ≡ r l mod p. É denotado por ind r, p (X).

• Cálculo de expoente mod p é simples, mas cálculo de logaritmo discreto é inviável para primos grandes.


O esquema Diffie-Hellman• Valores públicos: primo p e sua raiz primitiva r.

• Ana (e Beto) escolhe chave privada KprA (e KprB) < p

• Ana (e Beto) calcula chave pública KpuA = r KprA mod p (e KpuB = r KprB mod p)

• Ana calcula chave secreta KA = (KpuB) KprA mod p

• Beto calcula chave secreta KB = (KpuA) KprB mod p

= (r KprA mod p ) KprB mod p = r KprA KprB mod p= r Kpr

B Kpr

A mod p = (r KprB mod p ) Kpr

A mod p = (KpuB ) Kpr

A mod p = KA = K

• Chave secreta K foi compartilhada sem ser transmitida.Troca segura de chave secreta.


Criptografia com Curvas Elípticas• Mercado de criptografia de chave pública é dominado pelo

algoritmo RSA.• Aumento do poder computacional tem exigido aumentos no

tamanho das chaves.– Sobrecarga em servidores de comércio eletrônico: necessidade de

muitas transações seguras.– Sobrecarga em equipamentos com poucos recursos de velocidade

e de memória: celulares, cartões inteligentes, computadores de mão, etc.

• Algoritmo de chave pública mais leve se torna cada vez mais necessário.– Criptografia com Curvas Elípticas (ECC) oferece segurança no

nível de RSA mas com chaves bem menores.


Características de ECC

• Teoria já é antiga, mas aplicações começam a surgir só agora.– Nível de confiança ainda é menor que em RSA.– Complexidade matemática superior à de RSA:

muitos parâmetros e muitas formas distintas de implementação.

– Mais comumente usada na criptografia de chaves de sessão que na do conteúdo das msgs.

• Presente em vários padrões: IEEE P1363, Wireless Access Protocol (WAP), etc.


Curvas Elípticas

• Apesar das equações serem similares, curvas elípticas não são elipses.

• Forma geral: equação cúbicay2 + axy + by = x3 + cx2 + dx + e

onde a, b, c, d e e são números reais.

• Além dos pontos (x,y) de uma curva, define-se também o Ponto no Infinito ou Ponto Nulo“O”.

• Aritmética sobre pontos da curva obedece regras especiais.


Exemplos de Curvas Elípticas


Adição em Curvas Elípticas• Ponto O é o elemento identidade da adição. Logo,

P + O = P , P - O = P e P - P = O.– A soma de um ponto com seu valor negativo resulta no Ponto

no Infinito O.

• Intersecções de retas com CE podem ser usadas para se obter a soma de pontos de uma CE. – Toda reta não vertical intercepta uma CE em 3 pontos normais

P, Q e R e no ponto O.P + Q + R = O —> P + Q = - R

– Uma reta vertical corta uma CE em dois pontos normais (P1(x,y) e P2(x,-y) ) e no ponto O.

– Se P1(x,y) + P2(x,-y) = O, então P2(x,-y) = - P1(x,y)• O valor negativo de um ponto é o reflexo do ponto no eixo x.


Exemplos de Adição em CEs


Multiplicação de pontos por escalar

• Multiplicação de P por escalar k —> kP :– k = 1 —> 1P = P – k = 2 —> 2P = P + P

– k = 3 —> 3P = P + P + P

– k = n —> nP = P + P + . . . + P (n vezes)

• Método geométrico para k=2:– Traça-se a tangente ao ponto P desejado;

– o ponto onde a tangente interceptar a CE é o reflexo do resultado em relação ao eixo x.


Exemplo de duplicação de um Ponto P


Curvas Elípticas sobre corpos finitos

• Em ECC não se usam CEs definidas sobre os reais, mas conjuntos variantes delas chamados Grupos Elípticos mod p , onde p é um número primo.

• Um Grupo Elíptico Ep(a,b) é definido como y2 mod p = x3 + ax + b mod p ,

onde a, b e p são inteiros que satisfazem 4a3 + 27b2 mod p ≠ 0 (a, b < p) .

• Os elementos (pontos) de Ep(a,b) são inteiros positivos menores que p .


Exemplo de Grupo Elíptico Ep(a,b)• Seja o Grupo Elíptico E23(1,12):

y2 mod 23 = x3 + x + 12 mod 23 (14 soluções)

1

3

5

7

9

11

13

15

17

19

21

0 2 4 6 8 10 12 14 16 18 20 22

P Q

R

1

3

5

7

9

11

13

15

17

19

21

0 2 4 6 8 10 12 14 16 18 20 22

P

R

Q

R = P + Q


Método analítico para soma de pontos

• É difícil usar métodos gráficos para somar em grupos elípticos: usar métodos analíticos.

• Se P=(xP , yP ) , Q=(xQ , yQ ) e P ≠ -Q, então R = (xR , yR ) = P + Q pode ser obtido por:

xR = L2 - xP - xQ mod p

yR = L (xP – xR ) - yP mod p

onde L = (yQ - yP ) / (xQ - xP ) , se P ≠ Q

ou L = (3 xP2 + a) / (2 yP ) , se P = Q


Curvas elípticas como função de mão-única

• A adição em ECC corresponde à multiplicação modular em RSA.

• Adições múltiplas em ECC correspondem à exponenciação em RSA.

• Para ser útil em criptografia, CEs devem oferecer característica de função de mão-única.– Esta função existe nos grupos elípticos, pois

apesar de ser simples calcular R = kP, é computacionalmente inviável calcular k a partir de R e P, para corpos grandes ( p elevado).


Troca de chaves usando CEs

• Análogo à troca de chaves de Diffie-Hellman.• Passos:

– selecione um número primo p da ordem de 2180;– selecione parâmetros a e b de Ep(a,b);– selecione um ponto P(xP ,yP) de Ep(a,b);

– parâmetros públicos: P(xP ,yP) e Ep(a,b);

– Ana escolhe inteiro KprA = nA (chave privada de Ana);– Ana calcula chave pública KpuA = nA x P(xP ,yP);

– Beto escolhe chave KprB = nB e calcula KpuB = nB x P(xP ,yP);

– Ana calcula chave de sessão Ks = KprA x KpuB = nA x nB x P ;

– Beto calcula mesma chave de sessão Ks = KprB x KpuA = nB x nA x P;

• Chave de sessão não precisa ser transmitida pela rede.


Segurança de ECC• Segurança das chaves depende de quão difícil é obter k, dados

P e kP, que é conhecido como problema do logarítmo de curva elíptica.

• Melhor método para obter k: Pollard-Rho• Mesmo utilizando o método de Pollard-Rho, é muito mais

custoso calcular k que fatorar um inteiro da mesma ordem de grandeza que k usando General Number Sieve.

• Logo, ECC oferece maior segurança que RSA para um mesmo tamanho de chave ou oferece mesmo nível de segurança de RSA, mesmo usando chaves bem menores.

• ECC é vantajosa para uso em equipamentos portáteis e/ou com poucos recursos computacionais (memória e velocidade).


Segurança de ECC X RSA

Esforço para quebra (MIPS-anos) Tamanho da chave Algoritmo

3 x 104 512 General Number Sieve


4 x 1010 150 Pollard-Rho (ECC)








Autenticação

• Autenticação de mensagens é necessária para tratar os seguintes casos:– Mascaramento: envio ou confirmação de

mensagens por impostor.

– Modificação de conteúdo.

– Modificação de seqüência: inclui eliminação, inserção ou reordenação de mensagens.

– Modificação de tempo: • inserção de atrasos na entrega

• repetição de mensagens


Assinaturas Digitais

• Necessárias para evitar repudiação.– Destino não poderá negar o recebimento.– Origem não poderá negar o envio.

• Podem inibir também os ataques cobertos pela autenticação.

• Conclusão:– Assinatura Digital é um meio de autenticação

que pode também contra-atacar a repudiação por parte da origem ou do destino.


Funções de Autenticação• Mecanismos de autenticação têm 2 níveis:

– Nível Superior • protocolo de autenticação que usa o nível inferior para

confirmar a autenticidade da mensagem.

– Nível Inferior• alguma função que produza um autenticador (valor

usado para autenticar uma mensagem).

• funções se dividem em 3 classes:- Codificação de Mensagens- Message Authentication Code (MAC)- Funções Hash


Autenticação por Codificação de Mensagens

• Codificação de toda a mensagem é usada como forma de autenticar a origem.

• Problema: – Não é útil quando mensagem pode ser uma

combinação qualquer de bits: arquivos binários.

– Alguma estrutura fácil de identificar é necessária dentro da mensagem.

• Estrutura deve ser anexada à mensagem antes da codificação: controle interno de erro.

• Ex: - FCS (Frame Check Sequence): espécie de checksum. -Cabeçalhos de pilhas de protocolo.


Message Authentication Code• MAC: também conhecido como checksum

criptográfico.

• Mensagem é cifrada com uma chave secreta K:– código é anexado à mensagem original e enviado;

– destinatário pode verificar autenticidade, calculando o código novamente (com sua cópia de K) e comparando com o código recebido.

• MAC não provê sigilo.– Se necessário, outra codificação (com outra chave)

pode ser feita para garantir o sigilo da mensagem.


Razões para Uso de MAC ao invés de Codificação de Mensagem

• Mensagens de difusão (vários destinatários): – todos recebem e lêem a mensagem em claro;

– só um possui a chave secreta e se encarrega de autenticar a mensagem e alertar os demais.

• Destinatário muito carregado:– não obrigatoriedade de decifrar tudo é vantajosa.

• Autenticação de programas:– programas não precisam ser decifrados todas as

vezes que forem executados.


Razões para Uso de MAC ao invés de Codificação de Mensagem

• Algumas aplicações não requerem sigilo, mas somente autenticidade.– Ex: Simple Network Management Protocol

• Separação de funções de autenticação e de sigilo provê maior flexibilidade.– Funções podem ser implementadas em camadas distintas da

pilha de protocolo.

• Garantia da integridade da mensagem vai além do momento da decodificação.– Mensagem protegida contra modificações no sistema do

destinatário, mesmo após recebimento.


Características de MAC

• Codificação: C = MAC K (M)

– M : mensagem de tamanho variável (S)– K : chave secreta conhecida por remetente e

destinatário (k bits: 2k chaves)

– C : autenticador de tamanho fixo• n bits: 2n autenticadores

• Normalmente: S >> n

• Obter chave K é tão difícil quanto (ou mais difícil que) obter chaves em algoritmos de criptografia simétricos ou assimétricos.


Ataques a MAC• Seja M = X1 || X2 || X3 || ... || Xm a

mensagem composta de blocos de 64 bits Xi.

• Seja f(M) = X1 ⊕ X2 ⊕ X3 ⊕ ... ⊕ Xm

• Seja MAC K (M) = EK {f(M)} (DES-ECB)

• Intruso pode falsificar M, trocando X1 por Z1, X2 por Z2, ..., Xm-1 por Zm-1 e Xm por Zm = Z1 ⊕ Z2 ⊕ Z3 ⊕ ... ⊕ Zm-1 ⊕ f(M)

• Troca gera mensagem que passa no teste de autenticidade.


Requisitos para MAC• Deve ser inviável computacionalmente construir

uma mensagem M0 tal que MACK(M0) = MACK(M1) .

• MACK(M) deve ser uniformemente distribuída:

– Prob. {MACK(M0) = MACK(M1)} = 2-n

onde n é o número de bits no MAC.

• MAC não deve ser mais sensível a certas mudanças em M que a outras.– Prob. {MACK(M) = MACK [ f(M) ] } = 2-n para

qualquer função f(M).


MAC baseado em DES-CBC• Data Authentication Algorithm

– Um dos MAC’s mais usados.

– Aparentemente atende os requisitos anteriores.– Normalizado como FIPS PUB 113 e ANSI X9.17.

– DES no modo CBC é usado com IV = 0.

– Mensagem original: grupos de 64 bits Xi

C1 = EK (X1) , C2 = EK (X2 ⊕ C1)

C3 = EK (X3 ⊕ C2) , . . . , CN = EK (XN ⊕ CN-1)

• Autenticador: Data Authentication Code (DAC)– Código CN é usado total ou parcialmente como DAC.


Funções Hash

• Funções similares a MAC para produzir autenticador.

• Recebem mensagem de tamanho variável M e retornam um código hash H(M).

• Mudança em 1 bit de M altera código H(M).

• Pode ser usado de várias formas, combinado ou não com criptografia.


Função Hash: Uso I

• A envia a B: EK{M || H(M)}

– Provê sigilo e autenticação.

| |

HM

E

K

D

K

M

H(M)

H

Compara

EK{M || H(M)}

M

H(M)


Função Hash: Uso II

• A envia a B: M || EK{H(M)}

– Provê autenticação.

| |

HM

E

K

D

K

H

Compara

M || EK{H(M)}

M

H(M)


Função Hash: Uso III

• A envia a B: M || EKprA{H(M)}– Provê autenticação e assinatura digital.

| |

HM

E

KprA

D

H

Compara

M || EKprA{H(M)}

M

H(M)

KpuA


Função Hash: Uso IV

• A envia a B: EK { M || EKprA [ H(M) ] }

– Provê autenticação, sigilo e assinatura digital.

| |

HM

E

KprA

D

H

Compara

EK { M || EKprA [ H(M) ] }

M

H(M)

KpuA

E

K

D

K


Função Hash: Uso V

• A envia a B: M || H(M || K) – Provê autenticação com baixo custo.

| |

HM

H

Compara

M || H(M || K)

M

H(M || K)

| |

K

| |

K


Função Hash: Uso VI

• A envia a B: EKs{M || H(M || K)}

– Provê autenticação e sigilo.

| |

HM

H

Compara

EKs{M || H(M || K)}

M

H(M || K)

| |

K

| |

K

D

Ks

E

Ks


Comparando Modos de Uso• Modos de Uso II e III

– Criptografia só é usada em código hash.– Menor carga computacional.

• Modo V– Um dos mais atraentes: não requer criptografia.

• Software de criptografia é lento.

• Custo de hardware de criptografia não é desprezível.

• Hardware de criptografia é otimizado para grandes volumes de dados.

• Algoritmos de criptografia têm restrições de exportação ou de patente.


Requisitos para Função Hash H(M)• Implementação

– Ser aplicável a qualquer volume de dados.

– Produzir um código de tamanho fixo.

– Ser fácil de calcular e implementar em hardware e software.

• Função de mão-única– Ser computacionalmente inviável obter M dado H(M).

• Contra falsificação– Ser computacionalmente inviável obter M’ a partir de M tal que

H(M’) = H(M).

• Contra ataque-aniversário.– Ser computacionalmente inviável obter qualquer par

(M1, M2) tal que H(M1) = H(M2).


Exemplos de Função Hash• Função Hash de n bits

– usa dados de entrada em blocos de n bits.

• Função OU-Exclusivo comumente usada.

• Ex.: Função de Hash Simples

C i = bi1 ⊕ bi2 ⊕ bi3 ⊕ . . . ⊕ bim

onde: C i : i-ésimo bit do código hashm : número de blocos de n bitsbik : i-ésimo bit do k-ésimo bloco


Representação da Função de Hash Simples

Entrada bit 1 bit 2 . . . bit n Bloco 1 b11 b21 . . . bn1 Bloco 2 b12 b22 . . . bn2

. . . . . . . . . . . . . . . Bloco m b1m b2m . . . bnm

Código Hash C1 C2 . . . Cn • Probabilidade de erro/alteração resultar no mesmo

código hash: 2-n

• Regularidade nos dados pode aumentar esta probabilidade.

• Ex: função de 128 bits em texto ASCII: 2-128 --> 2-112


Função de Hash Simples com Deslocamento Circular

• Atenua problemas devidos regularidades nos blocos de entrada.– Torna processo mais aleatório.

• Consiste de 2 passos:– Deslocar de forma circular o código corrente um

bit à esquerda (ou direita).

– Calcular o ou-exclusivo entre o novo código e o próximo bloco de entrada.


Vulnerabilidades de Funções de Hash Simples

• É fácil criar outra mensagem com o mesmo código hash.– Usos II e III: texto claro com código cifrado

Mensagem original pode ser alterada e ainda produzir um mesmo código: basta acrescentar no final da alterada uma seqüência que force a produção do código desejado.

– Uso I: cifrar texto concatenado ao código• Padrão proposto pelo National Bureau of Standards

mostrou-se frágil, mesmo usando DES-CBC.


Ataque-Aniversário: Motivação

• Qual é o menor grupo de pessoas tal que a probabilidade de pelo menos 2 delas terem a mesma data de aniversário (dia e mês) seja maior ou igual a 0,5?– Resp: grupo com 23 pessoas.

• Caso geral: uma função com n=2m possíveis saídas precisa ser usada só k=2m/2 vezes para ter uma probabilidade de 0,5 de gerar 2 saídas iguais.


Ataque-Aniversário: Aplicação• Situação:

– Ana quer colocar assinatura de Beto em texto falso.

– Ana prepara 2m/2 variações de um texto legítimo L, todas com mesmo significado, 2m/2 variações do texto falso F, e aplica a função hash a todas elas.

• Há uma probabilidade de 0,5 de Ana encontrar um par (L0,F0) que produza o mesmo código hash (se não encontrar, novas variações podem ser geradas).

– Ana entrega a Beto L0 para ele ler e assinar, mas envia F0 com a assinatura obtida.

• Esforço requerido: ordem de 2m/2.


Protocolos de Autenticação

• Mecanismos de autenticação têm 2 níveis:– Nível Inferior

• alguma função que produza um autenticador (valor usado para autenticar uma mensagem).

• funções se dividem em 3 classes:- Codificação de Mensagens- Message Authentication Code (MAC)- Funções Hash

– Nível Superior • protocolo de autenticação que usa o nível inferior

para confirmar a autenticidade da mensagem.


Protocolo de Autenticação Mútua• É uma troca de chaves autenticadas.

• Dois pontos fundamentais:– sigilo: informações devem ser trocadas de forma

cifrada.– instante de envio: repetição de mensagens válidas

pode causar danos.• Duas formas de evitar repetições

- Carimbos de tempo– Problema: dificuldade em sincronizar vários relógios

- Desafios (nonces)– Problema: handshaking antes da transmissão não é adequado para

aplicações tipo connectionless.


Autenticação Mútua por Criptografia Simétrica

• Troca de chaves de sessão entre Ana e Beto com auxílio de uma autoridade X.

• Protocolo de Needham/Schroeder(1) A -> X: IDA || IDB || N1

(2) X -> A: EKA{KS || IDB || N1 || EKB(KS || IDA)}

(3) A -> B: EKB(KS || IDA)

(4) B -> A: EKS {N2}

(5) A -> B: EKS {f(N2)}

• Se uma chave KS antiga for descoberta por Caio, ele se passa por Ana repetindo msg. no passo (3).



• Protocolo de Denning: resolve problema de Needham/Schroeder inserindo carimbo de tempo T.(1) A -> X: IDA || IDB

(2) X -> A: EKA{KS || T || IDB || EKB(KS || IDA || T )}

(3) A -> B: EKB(KS || IDA || T )

(4) B -> A: EKS {N1}

(5) A -> B: EKS {f(N1)}

– Validade da mensagem é verificada por A e B com

| Clock - T | < ∆t1 + ∆t2

∆t1: diferença esperada entre relógios

∆t2: atraso esperado na rede



• Protocolo de Neuman: não requer relógios sincronizados, mas resolve protocolo de Needham / Schroeder.(1) A -> B: IDA || NA

(2) B -> X: IDB || NB || EKB (IDA || NA || TB )

(3) X -> A: EKA (IDB || NA || TB || KS ) || EKB (IDA || TB || KS ) || NB

(4) A -> B: EKB (IDA || TB || KS ) || EKS ( NB )

- TB : prazo de validade da chave (só verificado em B)

- Mesma chave de sessão pode ser reusada dentro de sua validade:

(1) A -> B: EKB (IDA || TB || KS ) || NA’

(2) B -> A: NB’ || EKS ( NA’) (B aceitou validade TB )

(3) A -> B: EKS ( NB’)


Autenticação Mútua porCriptografia Assimétrica

• Assumir que cada parte já possui a chave pública da outra parte não é prático.

• Protocolo de Denning(1) A -> X: IDA || IDB

(2) X -> A: EKprX{IDA || KpuA|| T} || EKprX{IDB || KpuB|| T}

(3) A -> B: EKprX{IDA || KpuA|| T} || EKprX{IDB || KpuB|| T}

|| EKpuB{EKprA(KS || T)}

– Autoridade X distribui certificados de chaves públicas.

– Protocolo compacto, mas requer relógios sincronizados.



• Protocolo de Woo/Lam– Usa nonces e não requer sincronização.

(1) A -> X: IDA || IDB

(2) X -> A: EKprX{IDB || KpuB}

(3) A -> B: EKpuB{NA || IDA}

(4) B -> X: IDA || IDB || EKpuX {NA}

(5) X -> B: EKprX{IDA || KpuA} || EKpuB{EKprX (NA || IDB || KS )}

(6) B -> A: EKpuA{EKprX (NA || IDB || KS ) || NB }

(7) A -> B: EKS {NB}



• Protocolo de Woo/Lam modificado– Adiciona identificador IDA nos passos (5) e (6).

• Modificação liga mais fortemente chave KS ao par (A, B).

(1) A -> X: IDA || IDB

(2) X -> A: EKprX{IDB || KpuB}

(3) A -> B: EKpuB{NA || IDA}

(4) B -> X: IDA || IDB || EKpuX {NA}

(5) X -> B: EKprX{IDA || KpuA} || EKpuB{EKprX (NA || IDA || IDB || KS)}

(6) B -> A: EKpuA{EKprX (NA || IDA || IDB || KS ) || NB }

(7) A -> B: EKS {NB}


Assinatura Digital• Autenticação de mensagens

– protege contra falsificações de terceiros;– não protege uma parte contra falsificações da outra.

• Requisitos– Deve ser uma seqüência de bits dependente do texto.– Deve usar informação exclusiva do remetente.

– Deve ser fácil de produzir.

– Deve ser fácil de reconhecer e verificar.

– Deve ser difícil de falsificar• criando assinatura falsa para texto existente ou

• criando texto falso para assinatura existente.


Assinatura Digital Direta• Só envolve remetente e destinatário.

• Pode ser aplicada ao texto inteiro ou à saída de uma função hash do texto.

• Ponto fraco: chave privada do remetente.– Remetente pode negar o envio da mensagem

alegando que sua chave foi roubada ou perdida.

– Solução: adotar carimbo de tempo na assinatura e verificar em uma autoridade central avisos sobre chaves comprometidas.

• Problema: chave roubada pode assinar mensagem usando carimbo de tempo mais antigo que o real.


Assinatura Digital Intermediada• Há uma autoridade intermediária X na qual as partes

A e B confiam.

• Técnicas baseadas em criptografia simétrica:Assinatura só é conferida por X, no envio e em disputas.

– Autoridade lê mensagem.

(1) A -> X: M || EKAX {IDA || H(M)}

(2) X -> B: EKXB [ T || IDA || M || EKAX{IDA || H(M)}]

– Autoridade não lê mensagem.(1) A -> X: IDA || EKAB[M] || EKAX{IDA || H(EKAB[M])}

(2) X -> B: EKXB[T || IDA || EKAB[M] || EKAX{IDA || H(EKAB[M])}]


Assinatura Digital Intermediada• Técnicas baseadas em criptografia assimétrica:

– Técnicas anteriores podem falhar se a autoridade resolve favorecer a uma das partes.

– Autoridade deve verificar validade da chave pública de A antes de enviar mensagem a B.

– Autoridade não lê mensagem.

(1) A -> X: IDA || EKprA {IDA || EKpuB [EKprA(M)]}

(2) X -> B: EKprX { T || IDA || EKpuB [EKprA(M)]}


Invasões• Tentativas de acesso ilegal a informações por

usuários ou programas.– Usuários:

• login de usuário não registrado

• obtenção ou abuso de privilégios por usuário registrado

– Programas:• Virus

• Worm

• Cavalo de Tróia

• Feitas pela rede, terminais locais ou via disquetes.


Tipos de Invasões• Benignas

– Objetivam apenas explorar as redes e sistemas de computação para ver o que há neles.

• Sérias– Objetivam ler e/ou modificar dados confidenciais ou

interromper funcionamento dos sistemas.

• Não há como distinguir as duas invasões.– Invasão benigna também reduz desempenho dos

sistemas e perturba usuários convencionais.– Invasão benigna pode ser tornar séria mais tarde.

– Conclusão: os dois tipos devem ser evitados.


Causas do Crescimento de Invasões Sérias

• Globalização:– Espionagem industrial cada vez mais presente.

• Mudança do modelo centralizado para o modelo distribuído– De mainframes a cliente-servidor: uso de redes.

– Popularização do Unix: segurança frágil.

• Rápida aprendizagem dos invasores– Invasores trocam informações muito mais frequente,

rápido e eficientemente que administradores de sistemas.


Invasores• Externos

– Mascarado: usuário externo (não registrado) que ganha acesso a uma conta legítima.

– Clandestino: usuário que obtém controle da parte de supervisão do sistema e inibe o rastreamento e registro de suas ações.

• Internos– Malfeitor: usuário interno (registrado) que tenta

ter acesso a dados sem autorização ou que faz mal uso de seus privilégios no sistema.

– Clandestino: como descrito acima.


Arquivo de Senhas• Obtenção de acesso ou aumento privilégios exige

conhecimento de alguma informação protegida: – SENHA

• Tabela usuário X senha armazenada em forma de arquivo protegido.

• Tipos de proteção para arquivo de senhas:– Codificação de mão-única

• Arquivo é armazenado cifrado e senha do usuário é comparada ao mesmo depois de ser cifrada.

– Controle de acesso• Acesso restrito a poucos usuários (administradores).


Obtenção de Senhas por Adivinhação• Técnicas mais comuns

– Uso de senhas de default embutidas nos sistemas e não atualizadas pelos administradores.

– Uso de todas as combinações de 1 a 3 caracteres ou de todas as combinações de placas de carro da cidade.

– Uso das palavras do dicionário do sistema ou em um dicionário de senhas prováveis.

– Uso de senhas derivadas de informações pessoais de usuário: sobrenomes, nomes de esposa e filhos, livros, hobby, número de telefone, RG, CIC, etc.

• Não são viáveis se feitas manualmente ou de forma detectável.– Cópia do arquivo de senhas é necessária para testes.


Obtenção de Senhas sem Adivinhação

• Cavalo de Tróia:– programa com dupla finalidade faz com que usuário

forneça senha e/ou outras informações.

• “Grampo” na linha entre terminal remoto e host.

• Invasor se faz passar por usuário legítimo e pede ao administrador o envio de nova senha.

• Invasor procura senhas em anotações do usuário.

• Invasor observa usuário teclando senha.


Prevenindo Invasões de Carater Não Técnico

• Difíceis de tratar: pessoas não sabem guardar segredos.• Métodos incluem:

– educação e conscientização dos usuários sobre o perigo potencial de ataques não técnicos: vulnerabilidades de aplicações como e-mail e fax devem ser ressaltadas;

– verificação periódica e consistente do sistema;

– assinatura de termos de compromisso pelos usuários a fim de torná-los cientes de suas responsabilidades e obrigações;

– adoção de diferentes categorias de usuários, de acordo com graus de privilégios e responsabilidade.


Proteção de Senhas em Unix• Senhas são armazenadas cifradas

• Arquivo contém ainda:– identificador do usuário (ID): texto claro– sal: número aleatório de 12 bits baseado no

relógio do sistema; também não é cifrado.

• Senha cifrada por DES modificado– Entrada inicial: bloco de 64 zeros

– Chave: senha em texto claro (56 bits)– Sal: modifica tabela E (expansão) em DES– Saída é levada à entrada novamente (25 vezes)


Autenticação de Senhas em Unix• ID fornecido é usado para obter sal e senha

cifrada de arquivo.

• Senha fornecida é cifrada usando o sal obtido e comparada com senha do arquivo.

ID sal senha cifrada

crypt(3)ID do usuário

senha em claro

comparasal

senha cifrada(11 caracteres)

Arquivo de senhas

12 bits

56bits


Razões para Uso de Sal em Senhas

• Diferencia senhas duplicadas no arquivo.– Mesmo que 2 usuários escolham mesma senha,

elas aparecerão diferentes devido à hora.

• Aumenta artificialmente o tamanho da senha sem exigir mais caracteres do usuário.– Espaço de busca aumentado em 4096 vezes para

usuários externo.

• Previne o uso de mecanismos de quebra rápidos baseados em hardware DES padrão.– Tabela E de DES é alterada pelo sal.


Vulnerabilidade de Senhas• Ataque por força bruta não é viável.

– Adivinhação pode dar melhor resultado.

• Senhas são normalmente mal escolhidas.– Estudo em Purdue University mostrou que 3%

das senhas tinham até 3 caracteres.

– Estudo em 13.797 contas Unix conseguiu descobrir 25% das senhas. Tipos mais comuns:•nome do usuário ou seu ID

•sobrenomes

•frases conhecidas

•nomes comuns

•nomes de lugares

•termos esportivos

•filmes e atores/atrizes

•personalidades, etc.


Controle de Acesso ao Arquivo de Senhas

• Versões mais recentes do Unix restringem ao super-usuário (root) o acesso ao arquivo de senhas.– Invasor não pode ler o arquivo sem antes obter

privilégios de super-usuário.

• Confiança neste controle não deve ser total.– Acidente de proteção pode deixar arquivo exposto.

– Usuários podem ter senhas idênticas em máquinas com critérios de proteção distintos: senha pode ser quebrada em máquina menos protegida.


Técnicas de Escolha de Senhas

• Educação do usuário– Há várias sugestões para escolha de senhas:

• iniciais de palavras em poemas ou músicas;

• combinação de palavras que fazem sentido p/ usuário

• regras de transformação de palavras

– Difícil convencer e ensinar usuários a usar senhas robustas.


Técnicas de Escolha de Senhas

• Senhas geradas pelo sistema– São aleatórias e difíceis de memorizar

• se usuário necessita escrever a senha, então ela não é uma boa escolha.

– Norma FIPS PUB 181 propõe programa em C para gerar senhas aleatórias, mas pronunciáveis.


Verificação de Senhas

• Verificação Posterior: – sistema usa periodicamente programa de quebra

de senhas;

– as contas que têm senhas descobertas são travadas;

– desempenho do sistema é comprometido, caso a verificação seja bem feita.

• Verificação Prévia:– teste de qualidade da senha é feito no momento

da escolha desta pelo usuário, educando-o.


Técnicas para Verificação Prévia• Uso de regras estritas

– Ex: - senhas têm que ter no mínimo n caracteres ou - senhas têm que ter no mínimo m símbolos não alfabéticos

– Desvantagem: indica que senhas não devem ser tentadas pelos invasores.

• Uso de dicionário de senhas ruins– Desvantagens:

• ocupa muito espaço

• procura demanda muito tempo


Técnicas para Verificação Prévia• Uso de Modelos de Markov

– Modelo consiste na quádrupla M = [m, A, T, r] onde• m : número de estados no modelo

• A : espaço de estados

• T : matriz de probabilidades de transição

• r : ordem do modelo

– Ex:

a b

c

0,5

0,2

1 0,40,5 0

M=[m, A, T, r] = [3,{a,b,c}, T, 1]

T = { 0.0 , 0.5 , 0.5 ,

0.2 , 0.4 , 0.4 ,

1.0 , 0.0 , 0.0 }

Seqüência provável: abbcacaba

Seqüência improvável: aacccbaaa

0

0

0,4


Técnicas para Verificação Prévia

• Características do Modelo de Markov– Ordem r representa número de estados

anteriores dos quais estado atual depende.

– Matriz T é criada a partir de dicionário de senhas ruins.

– Modelo M é usado em lugar de dicionário para verificar se senha é ou não adequada.

• Teste estatístico

• Bons resultados com modelo de ordem r = 2


Técnicas para Verificação Prévia• Filtro de Bloom

– Filtro de ordem r formado de r funções hash H1(x), H2(x), . . . , Hr(x).

– Cada função mapeia senha em um valor entre 0 e N-1.– Uso do filtro:

• Seqüência de N bits 0 é criada (tabela ou vetor hash).

• Cada senha x, do dicionário de senhas ruins, passa pelas r funções hash, e o bit correspondente à saída de cada função é setado no vetor hash.

• Quando uma nova senha é sugerida pelo usuário, as r funções são calculadas. Se todas as saídas já estiverem setados no vetor hash, a senha é rejeitada.


Técnicas para Verificação Prévia• Características do Filtro de Bloom

– Rejeita todas as senhas do dicionário de senhas ruins.– Rejeita também algumas senhas novas válidas (alarme

falso)Palarme falso ≈ (1 – e- r D / N )r = (1 – e- r / R )r

– P : probabilidade de haver alarme falso

– D: número de senhas do dicionário– N: número de bits da seqüência– R = N/D : razão entre tamanho da seqüência de bits e

número de senhas do dicionário.


Técnicas para Verificação PréviaProbabilidade do Filtro deBloom Gerar Alarme Falso

0.0001

0.001

0.01

0.1

1

0 2 4 6 8 10 12 14 16 18

Razão R

Prob

abili

dade

POrdem 2Ordem 4Ordem 8Ordem 16


Técnicas para Verificação Prévia

• Exemplo de uso do filtro de Bloom– Dados

• Dicionário de senhas ruins: 106 palavras (8 • 106 Bytes)

• Número de funções hash: 8

• Probabilidade de alarme falso: menor que 1%

– Pelo gráfico (ou fórmula) obtemos R = 10.

– Vetor hash = R x 106= 107 bits = 1,25 • 106 Bytes

– Taxa de compressão: 8 / 1,25 = 6,4 vezes– Conclusão: teste de senha envolve apenas o cálculo de

8 funções hash e independe do tamanho do dicionário.


Administração de Senhas• Norma FIPS PUB 112

– Recomendações gerais sobre administração de senhas para baixa, média e alta proteção.

Fator Baixa Prot. Média Prot. Alta Prot.

Símbolos dígitos letras e dígitos 95 ASCII

Comprimento 4 a 6 4 a 8 6 a 8

Validade 1 ano 6 meses 1 mês

Fonte usuário sistema gera sistema gera

(usuário escolhe)

Gravação texto claro cifrada cifrada

Autenticação cada sessão cada 10 min. cada 5 min.


Deteção de Invasões

• Mesmo o mais seguro sistema pode falhar e ser invadido.

• Deteção de invasões: segunda linha de defesa.

• Motivações:– Quanto antes a invasão for detetada, menor os danos

causados.

– Sistema de deteção de invasões eficiente inibe e previne novas invasões.

– Dados coletados durante deteção podem ajudar a tornar o sistema mais seguro.


Comportamento Suspeito• Deteção de invasão se baseia no comportamento

distinto entre invasor e usuário legítimo.

Probabilidade

Parâmetro deComportamentoComportamento

médio de usuárioComportamentomédio de invasor

Sobreposição deComportamentos

Padrão de Comportamentode Usuário Legítimo

Padrão de Compor-tamento de Invasor


Abordagens para Deteção de Invasões• Deteção Estatística

– Dados sobre comportamento de usuário legítimo são coletados durante certo tempo.

– Testes estatísticos são aplicados para determinar se comportamento atual é ou não de um invasor.

• Deteção Baseada em Regras– Definição de regras que podem ser usadas para

decidir se um comportamento é ou não legítimo.

• Combinação dos dois tipos deve ser usada contra mascarados e malfeitores.


Parâmetros para Deteção Estatística• Contador: inteiro que só pode ser incrementado até ser

zerado pelo administrador.– Ex: logins/hora, senhas falhas/minuto, etc.

• Medidor: inteiro a ser incrementado ou decrementado.– Ex: número de conexões atuais de uma aplicação, número de

mensagens para um processo, etc.

• Cronômetro: mede intervalos entre operações.– Ex: intervalo entre logins sucessivos em uma mesma conta.

• Utilização de recursos em certo período de tempo.– Ex: tempo de execução de programa, número de páginas

impressas, etc.


Auditoria• Programas: nativos do SO ou específicos

• Registros de Auditoria: facilitam deteção de invasões– Sujeito: iniciador da ação (usuário ou processo)

– Ação: operação efetuada pelo sujeito (login, read, ...)

– Objeto: receptor das ações: (arquivos, terminais, impressoras,...)

– Condição de exceção: mostra exceção causada pela operação

– Uso de recursos: quantidade de recursos usados (linhas impressas, tempo de CPU, ...)

– Carimbo de tempo: identifica momento da ação

Sujeito Ação ObjetoCondição de

ExceçãoUso de

RecursosCarimbode Tempo


Exemplo de Registro de Auditoria

• Linha de comando executada por Ana:copy xfile /usr/bin/xfile

• Registros:

Ana executar /usr/bin/copy 0 CPU=005 980820210439

Ana ler /home/ana/xfile 0 bytes = 75 980820210440

Ana executar /usr/bin/copy escrita nãoautorizada CPU=005 980820210445


Deteção Distribuída de Invasões• Necessidade de proteger computadores

conectados por rede: deteção coordenada

• Ex. de Sistema de Deteção Distribuída de Invasões da Universidade da Califórnia (Davis)– Módulo Agente de Host: processo de auditoria no

sistema monitorado que coleta dados e envia ao Gerenciador Central.

– Módulo Agente Monitor de Rede: processo de auditoria na rede.

– Módulo Gerenciador Central: recebe relatórios de auditoria e os correlaciona para detetar invasões.


Fluxo de Informações em Deteção Distribuída

Dados deAuditoria

GeraisFiltro

AtividadesSuspeitas

Lógica Regras

Agente Alertas

Perguntas/Respostas

GerenciadorCentral

Dados deAuditoria deSegurança


Vulnerabilidades de Sistema

• Programas maliciosos– Necessitam de programa hospedeiro

• Atalhos (Trapdoors)

• Bombas-relógio

• Cavalos de Troia

• Virus

– Independentes• Bacterias

• Vermes


Atalhos (Trapdoors)• Ponto de entrada secreto no programa

– Implementado pelo desenvolvedor para facilitar depuração do programa: permite acesso rápido e simplificado ao programa, sem passar por rotinas convencionais de segurança.

• É código que reconhece alguma seqüência especial de entrada, ou que é disparado quando executado por certo usuário.

• Medidas de segurança devem visar o estágio de desenvolvimento e distribuição do software.


Bombas-Relógio• Código embutido em programa legítimo que é

acionado quando certas condições são satisfeitas:– presença ou ausência de certos arquivos– data e/ou hora específicas

– uso do programa por usuário específico

– tempo de atividade/inatividade do sistema/usuário

• Pode interromper o funcionamento normal do programa, do sistema ou causar algum dano (alteração, eliminação de arquivos, etc.).


Cavalo de Troia• Programa útil (ou aparentemente útil) contendo

código oculto que executa alguma ação indesejada:– usando ID de usuário legítimo, programa muda

privilégios de acesso de um certo arquivo para que outros possam ter acesso ao mesmo;

– fazendo-se passar por editor, jogo, etc., programa pode apagar arquivos e/ou enviar informações pela rede.

• Difícil de detetar e prevenir se implementado por compilador– leitura do código fonte não revela o Cavalo de Troia.


Vírus

• Programa que pode se inserir no código de (infectar) outros programas.

• Ao encontrar programas executáveis ainda não infectados faz cópia de si próprio no início dos mesmos.

• Normalmente tem objetivos de destruir dados ou perturbar o funcionamento do computador.

• Pode passar despercebido por longo tempo.


Bactéria

• Tipo de programa cujo objetivo é somente duplicar-se.– Na memória: gera e executa cópia idêntica.– Em disco: duplica arquivo contendo seu código.

• Reprodução é exponencial.– Em pouco tempo toda a CPU e/ou disco estão

tomados pelo programa da bactéria, interrompendo o funcionamento normal do sistema.


Vermes• Programas com capacidade de usar redes para

penetrar em outros sistemas e se propagar.

• Quando dentro de um sistema, vermes podem se comportar como vírus, bactérias, Cavalos de Tróia ou causar algum dano por si mesmos.

• São mais complexos e mais difíceis de produzir: requerem grupo de computadores com mesmo tipo de falhas de segurança e conhecimentos suficientes para explorar tais falhas.

Documents

Slides do curso de Segurança e Privacidade de Dados - UNICAMPmarco/cursos/ia012_14_1/slides/slides_ia... · IA012 (DCA-FEEC-UNICAMP) ver: 20140312 1 IA 012 Segurança em Comunicação