IA012:2011 1S:Lista II

De DCA-Wiki

IA012 A - Segurança em Comunicação de Dados

FEEC - UNICAMP

Lista de Exercícios 2 - Entregar no início da aula

  • Obs:
    • Os exercícios ímpares deverão ser entregues até a data constante do programa da disciplina (no início da aula).
    • Pelo menos um destes exercícios será sorteado e corrigido como questão complementar da Prova. Os demais não serão corrigidos para efeito de nota.
    • Aqueles que não entregarem os exercícios selecionados no prazo marcado terão nota zero na questão complementar da Prova.


(1) Considere os seguintes esquemas de distribuição de chaves:

Esquema I:

(1) A -> B: IDA, EKA(NA)

(2) B -> KDC: IDA, EKA(NA), IDB, EKB(NB)

(3) KDC -> B: EKB(KS, IDA, NB), EKA(KS, IDB, NA)

(4) B -> A: EKA(KS, IDB, NA)


Esquema II:

(1) A -> KDC: Pedido | | N1

(2) KDC -> A: EKA{KS | | Pedido| | N1 | | EKB(KS, IDA)}

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

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

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

Descreva a utilidade/necessidade de cada etapa destes esquemas e discuta uma vantagem/desvantagem do Esquema I do ponto de vista do KDC.


(2) Para saber se uma pessoa tem uma chave secreta K igual à sua, você escolhe uma seqüência aleatória de bits A e envia o XOR dela com sua chave. O destinatário recebe a seqüência, faz XOR com a chave secreta combinada e devolve o resultado. Se este for igual à seqüência aleatória original, então as chaves são iguais. Portanto o teste foi feito sem necessidade de se transmitir nenhuma chave. Mas, existe uma falha no mesmo. Explique qual é.


(3) No protocolo de transporte fictício XTP são usadas duas funções hash simples de 16 bits cada: uma que faz um XOR bit a bit nos dados de 16 bits e outra chamada RXOR que faz um deslocamento circular de um bit para a direita no resultado parcial da função antes de fazer um XOR com os 16 bits do próximo dado. Os dois resultados são concatenados resultando em um código detetor de erros de 32 bits. Pergunta-se o seguinte sobre este código resultante.

(a) Ele é capaz de detetar todos os erros que envolvam um número ímpar de bits? Por que?

(b) Ele é capaz de detetar todos os erros que envolvam um número par de bits? Por que?

(c) Ele é adequado para ser usado como código de autenticação de mensagens? Por que?


(4) Criptografia e funções hash podem ser usadas para controlar erros na transmissão de uma mensagem. Existe o tipo de controle interno (mensagem e código detetor de erro são concatenados e cifrados) e o externo (mensagem é cifrada antes do código detetor de erros ser calculado e concatenado a ela). Além dos códigos detetores de erros, existem ainda os códigos corretores de erro, os quais não só acusam a ocorrência de algum erro durante a transmissão como também permitem que tais erros sejam corrigidos sem necessidade de uma nova transmissão. Analise a viabilidade de se implantar códigos corretores de erro nos modos interno e externo como descrito acima.


(5) Supondo que senhas se limitam aos 95 caracteres ASCII imprimíveis e que todas as senhas tenham 10 caracteres, determine o tempo necessário para se fazer uma busca exaustiva usando um circuito capaz de cifrar e comparar 6,4 milhões de senhas (de 10 caracteres) por segundo.


(6) Há basicamente 3 formas de se usar nonces:

  • Forma 1:
    • (1) A -> B : Na
    • (2) B -> A : Ek(Na)
  • Forma 2:
    • (1) A -> B : Ek(Na)
    • (2) B -> A : Na
  • Forma 3:
    • (1) A -> B : Ek(Na)
    • (2) B -> A : Ek{f(Na)}

Compare e discuta as 3 formas do ponto de vista da eficácia do nonce em cumprir sua tarefa.


(7) No tópico relativo a assinaturas digitais intermediadas vimos que há duas maneiras de utilizar criptografia simétrica: uma na qual o intermediador pode ler a mensagem e outra na qual ele não pode ler. Mostre como estes 2 protocolos podem ser modificados para que o destinatário possa verificar a autenticidade da mensagem por si só, mas ainda havendo atuação do intermediador.


(8) Em assinaturas digitais intermediadas com criptografia assimétrica temos uma codificação tripla na primeira parte do protocolo. Como o mesmo pode ser modificado de modo a eliminar esta tripla codificação?


(9) Para minimizar os riscos envolvidos no sistema de senhas tradicional do Unix, recomenda-se a substituição do arquivo público de senhas por um arquivo público contendo as chaves pública (Kpu) e privada (Kpr) de cada usuário. A chave Kpr estaria cifrada por DES utilizando a senha (S) do usuário. Quando o mesmo fornecesse a senha, a chave Kpr seria decifrada e ficaria pronta para uso. Neste caso pergunta-se:

(a) Como o sistema verifica que a senha S está correta?

(b) Como um invasor, que só conhece o novo arquivo público de senhas, tentaria entrar no sistema? Descreva todos os passos que ele seguiria.


(10) Considere o seguinte esquema de assinatura digital intermediada baseada em chave pública.

  • Ana --> Autoridade: IDA || EKprA [ IDA || EKpuB { EKprA ( M ) } ]
  • Autoridade --> Beto: EKprAut [ IDA || EKpuB { EKprA ( M ) } ]

Explique que problema pode ocorrer caso o remetente tenha mais de um par de chaves e um dos pares tenha sido comprometido.


(11) O sistema de senhas tradicional do Unix faz uso de 12 bits extras (conhecidos como sal).

  • Explique como o sal é gerado e usado.
  • Explique qual é a sua vantagem.
  • Dobrar o triplicar o número de bits do sal usado no esquema de senhas do Unix não aumenta significativamente a dificuldade de invasores em quebrar senhas (considerando que o invasor possui o arquivo de senhas). Por quê?
  • Explique os efeitos de se aumentar o número de bits do sal em um sistema com poucos usuários.
  • Explique os efeitos de se aumentar o número de bits do sal em um sistema com muitos usuários.


(12) Considere o seguinte esquema de assinatura digital intermediada baseada em chave pública.

  • Ana --> Autoridade: IDA || EKprA [ IDA || EKpuB { EKprA ( M ) } ]
  • Autoridade --> Beto: EKprAut [ IDA || EKpuB { EKprA ( M ) } ]

Descreva qual é o tipo de aliança (acordo) entre os envolvidos que poderia surgir a fim de fraudar o sistema. Dica: a fraude se basearia em uma situação tão pouco provável que dificilmente tal aliança teria sucesso.


(13) Explique o que são certificados, para que servem e mostre como eles são usados.


(14) Assinatura Digital Intermediada: explique o que é, por que é necessária e dê um exemplo de utilização, mostrando as informações que são trocadas entre as partes.


(15) O Filtro de Bloom é considerado um método eficiente para verificação prévia de senhas ruins. Explique como é o seu funcionamento e quais as vantagens que o mesmo oferece em relação a outras abordagens com o mesmo objetivo.


(16) Existem várias maneiras de se usar funções de hash para autenticar mensagens. Normalmente estas autenticações envolvem o uso de criptografia, seja da mensagem toda ou somente do código hash. Entretanto, o uso de criptografia não é essencial. Mostre como uma função de hash pode ser usada para autenticar e conferir a autenticidade de uma mensagem M sem recorrer aos recursos da criptografia. Considere a função hash como uma caixa preta cujo conteúdo (implementação) é desconhecido.


(17) Os algoritmos de chave assimétrica são úteis na codificação e distribuição de chaves de sessão descartáveis que serão usadas em algoritmos simétricos mais rápidos. Nessa distribuição deve-se ter o cuidado de evitar que repetições de mensagens interceptadas no passado possam ser usadas por invasores para se fazer passar por um usuário legítimo. Uma maneira de se contornar este problema é associar carimbos de tempo à chave de sessão sendo distribuída. Mas esta solução exige que os relógios dos vários sistemas envolvidos estejam sincronizados, o que é uma exigência difícil de ser cumprida sempre. O protocolo abaixo mostra como se pode usar números aleatórios (nonces) para distribuir chaves de sessão de forma confiável e sem recorrer a relógios. Mostre como este protocolo pode ser reduzido de 7 para 5 passos, sem perder suas características e objetivos.

Versão original

  • A --> KDC : IDA || IDB
  • KDC --> A : EKprKDC{IDB || KpuB}
  • A --> B : EKpuB{NA || IDA}
  • B --> KDC : IDA || IDB || EKpuKDC{NA}
  • KDC --> B : EKprKDC{IDA || KpuA} || EKpuB{EKprKDC(NA || IDA || IDB ||KS)}
  • B --> A : EKpuA{NB||EKprKDC(NA || IDA || IDB ||KS

Versão reduzida

  • A --> B :
  • B --> KDC :
  • KDC --> B :
  • B --> A :
  • A --> B : EKs{NB} <-- dica


(18) O que são chave-mestra e chave de sessão? Quais são as vantagens em utilizá-las?


(19) Woo e Lam propuseram um protocolo de chave pública para distribuição de chaves de sessão baseado em nonces e que não requer sincronização entre relógios. Logo em seguida, os próprios autores publicaram uma atualização do protocolo a qual incluia o identificador de A (IDA) nos passos 5 e 6. Esta alteração no protocolo visou protegê-lo contra algum ataque? Qual? Por quê?


(20) Explique detalhadamente como funciona o esquema de troca de chaves proposto por Diffie e Helmann em 1976.


(21) (a) Mostre que no filtro de Bloom a probabilidade de bits zero na tabela hash é dado por z = (1 - k/N)D, onde k é o número de funções hash, N é o número de bits na tabela hash e D é o número de palavras no dicionário de senhas ruins.

(b) Mostre que a probabilidade de se ter alarmes falsos neste filtro (indicação de que uma senha está no dicionário quando na verdade não está) é dada por (1 - z)k.

(c) Mostre que a expressão do item (b) pode ser aproximada por (1 - e -kD/N)k.


(22) Sabe-se que é possível criar métodos de criptografia baseados na família de funções matemáticas conhecida como Curvas Elípticas (CE). Mostre os procedimentos para cifrar e decifrar por este algoritmo supondo que fossem usados os pontos da curva y2 = x3 + x + 1 mod 23 (curva sobre corpo finito primo). Desenvolva um exemplo, mostrando a cifragem e a decifragem da dezena final de seu RA. (Dica: use o algoritmo proposto por Menezes-Vanstone que admite que a mensagem M seja um ponto não pertencente à curva, isto é, ela pode ser formada por um par arbitrário de inteiros.)

Ferramentas pessoais