2 – Criptografia Flashcards
O que é a criptanálise?
Arte ou ciência de violar informação criptografada ou sistemas criptográficos
Quais são os objetivos da criptanálise?
Obter texto original
Obter chave de cifra
Obter algoritmo de cifra
Indica 5 técnicas/ataques de criptanálise.
– Ataques usando apenas o criptograma (ciphertext-only attacks)
– Ataques com conhecimento de parte do texto original (known-plaintext attacks) + criptograma
– Ataques com texto original escolhido (chosen-plaintext attacks)
– Ataques com criptogramas escolhidos (chosen-ciphertext attacks)
– Ataques de aniversário (birthday attacks)
Quais são os dois tipos de cifra?
Cifras de transposição e de substituição
Em que consistem as cifras de transposição?
Baralham os caracteres do texto original.
Ex: – Permutações fixas em blocos com um número constante de caracteres • Permutação 45231 • Criptograma: raifc • Texto original ?
– Blocos verticais de dimensão fixa • Blocos verticais de 5 caracteres: eaeo... loms esqo saun nbeh
Em que consistem as cifras de substituição?
Substituem os caracteres do alfabeto usado no texto original por caracteres de um alfabeto de substituição
Quais são os dois tipo de cifras de substituição?
Monoalfabéticas e Polialfabéticas
Em que consistem as cifras de substituição monoalfabéticas?
– Usam apenas um alfabeto de substituição
– Um carácter do alfabeto original é substituído sempre pelo mesmo carácter
– Criptanálise
• Força bruta
• Ataques com texto original escolhido
• Padrões estatísticos dos caracteres usados no texto original
Em que consistem as cifras de substituição polialfabéticas?
- Aplicação sucessiva e cíclica de várias cifras monoalfabéticas
- Cifra de Vigenère
Em que consiste a cifra Vigenére?
– Chave: conjunto de caracteres
– Mecanismo:
· Repete-se a chave em sequência até que a chave seja do tamanho do texto a ser cifrado
· Para cada letra, é feita uma substituição:
• B+C =D (A=0,B=1,C=2,….)
· Se a chave tem uma letra apenas, temos uma cifra monoalfabética
– Exemplo:
Chave poemapoemapoe
Texto em claro elesnaosabemq
Texto cifrado tzienpcwmbtau
– Criptanálise
· Determinar a dimensão da chave -> criptanálise de N cifras
monoalfabéticas
· Técnicas estatísticas para determinar N: teste de Kasiski e índice de coincidência
O que é uma cifra perfeita?
Uma cifra diz-se perfeita quando, dado um criptograma c, a probabilidade de ele corresponder a um dado texto original m e de ter sido gerado com uma dada chave k é igual à probabilidade de ocorrência do texto m.
Quais são as dificuldades associadas às cifras perfeitas?
- Para cada texto tem de ser usada uma chave diferente
- O comprimento das chaves tem de ser igual ou superior ao dos textos
- As chaves não são memorizáveis
- Pré-distribuição de chaves de grande dimensão
- Não faz sentido usar para cifrar dados armazenados
O que é na prática uma cifra segura?
Uma cifra diz-se segura se cumprir o objectivo para que é usada
- As vulnerabilidades da cifra, mesmo quando usada de forma correcta, não permitem a sua criptanálise em tempo útil e admitindo um investimento tendo em conta a relação custo-benefício
- A cifra é usada de forma correcta, sem aumentar as suas vulnerabilidades intrínsecas
Quais são os 5 critérios para avaliar a qualidade das cifras?
- Quantidade de secretismo oferecida
– Tempo mínimo de segurança do criptograma
– Confusão e difusão - Dimensão das chaves
– Cifra de Vernam – gestão de chaves :( - Simplicidade de realização e uso
- Propagação de erros
- Dimensão do criptograma
– O tamanho do texto cifrado não deve ser maior que o do texto em claro – custo de armazenamento ou transmissão
Quais são os dois conceitos associados a cifras com boas quantidades de secretismo?
Confusão e Difusão
Em que consiste a confusão associada ao secretismo de cifras?
• Relação entre texto em claro, chave e criptograma deve ser o mais complexa possível
• É difícil descobrir parte do texto em claro mesmo conhecendo outras
• É difícil descobrir parte ou toda a chave usada para produzir um
criptograma
Em que consiste a difusão associada ao secretismo de cifras?
- Cada bit de informação do texto original deve influenciar vários bits do criptograma
- Pequena alteração no texto original implica grandes alterações no criptograma
Indica três boas práticas associadas à criptografia.
– Criptanalista conhece o algoritmo de cifra e as suas fragilidades
• Segurança baseia-se no desconhecimento da chave
• Tem de ser baseado em matemática sólida
• Tem de ter sido analisado por vários especialistas
• Tem de ter passado no teste do tempo
– Criptanalista pode capturar todos os criptogramas
– Criptanalista conhece partes do texto original
Existem 3 tipos de cifras atualmente. Quais são?
Simétricas, assimétricas e hibridas.
Quais são os dois modos de operação nas cifras modernas?
A cifra por blocos e a cifra continua
Qual é o tipo de cifra mais rápido? Simétrica ou assimétrica?
Simétrica
As cifras simétricas são por blocos ou continuas?
Por blocos
Quais são os 4 tipos de cifras simétricas que abordámos?
Data Encryption Standard (DES)
Triple-DES
International Data Encryption Algorithm (IDEA)
Advanced Encryption Standard (AES)
Quais são os dois tipos de ataques a cifras simétricas e em que consistem?
– Criptanálise
· Algoritmo
• Deduzir texto em claro específico
• Deduzir a chave
· Conhecimento de características do texto em claro
· Exemplos de pares texto em claro/criptograma
· Se a chave for comprometida
• Compromete mensagens passadas e futuras cifradas com a chave
– Ataques de força bruta
· Tenta todas as chaves
· Em média, tem de tentar metade das chaves
Quais são os problemas do DES?
Chaves pequenas (56 bits)
Alguns passos do algoritmo não se sabe o porquê de existirem
Muitos algoritmos para “quebrá-lo” já foram desenvolvidos
Em 1998 foi apresentado um sistema que quebrava o DES em quatro dias
Ficou claro que ele já não era uma solução de segurança viável
O que é o Triple DES?
Usa DES 3 vezes com 2 ou 3 chaves
Requer O(2^2n) cifras e O(2^n) de memória com chaves de 56 bits Ataque muito difícil
Qual dos algoritmos é mais robusto? DES ou IDEA?
IDEA
O IDEA usa chaves de que tamanho?
Utiliza chaves de 128 bits, o que significa que:
ataque força bruta requer 10^38 cifrações
com chip de 10^9 cifr/seg, requer 10^13 anos
Qual é o problema do IDEA?
Nunca foi normalizado
Como funciona o AES?
Recebe como entrada blocos de 128 bits de texto em claro
As chaves podem ter 128, 192, 256 bits (quanto maior, mais seguro)
Produz blocos de 128 bits de texto cifrado
Funciona iterativamente
• Cada bloco é dividido em 4 grupos de 4 bytes
• Um bloco inteiro é modificado em cada iteração (no DES é só metade)
Rápida e eficiente em CPUs pequenos e grandes
Em que consiste a cifra por blocos?
Processa o texto em claro por blocos, um bloco em cada iteração
Produz um bloco por cada bloco de entrada
Pode reusar chaves
Em que consiste a cifra continua?
Processa o texto em claro de forma contínua Normalmente mais rápidas
Quais são os dois modos de cifra por blocos?
ECB - Electronic CodeBook
CBC - Cypher Block Chaining
Em que consiste o ECB?
Cifra por blocos independentes
Fraquezas
• Reprodução de padrões de texto original – dois blocos iguais produzem o mesmo criptograma
• Vulnerável a ataques de reordenação ou replay
Em que consiste o CBC?
O texto em claro é “XOR” com o texto cifrado do bloco anterior antes de ser cifrado
Reduz risco de replicação de padrões
Initialization Vector (IV): usado no 1o bloco (necessário para decifrar -> ver API
do Java)
Padding: bits para compor blocos inteiros do tamanho requerido pelo algoritmo
O que significa XOR?
Exclusive OR
Como se processa a operação das cifras continuas?
Geração de chaves em tempo real por uma black box
Chaves usadas apenas uma vez
Distribuição?
• A chave contínua é gerada em simultâneo em ambos os pontos – sincronização
• Black boxes são parametrizadas por uma master key
Cifra/decifra
• Processa um bit/byte de cada vez, continuamente
5 aspectos das cifras continuas.
Usam chaves contínuas
Usam princípio da confusão (não da difusão)
As chaves não devem ser reusadas
O período de uma chave contínua deve ser o mais longa possível
A sequência de bits de uma chave contínua deve aparentar ser aleatória
Quais são os 3 tipos de cifras continuas?
CFB - Cypher Feedback
OFB – Output Feedback
CTR (counter)
Descreve o CFB
Transforma cifra por blocos em cifra contínua
Vantagens sobre o CBC:
• a cifra de bloco só é utilizada na direcção de cifrar (independentemente de a operação ser cifrar ou decifrar) o que simplifica a sua implementação, e
• a mensagem não necessita de ser “padded” para um múltiplo do tamanho do bloco porque o algoritmo trabalha com qualquer quantidade de bytes
Descreve o OFB
Mantém as vantagens do CFB e ainda acrescenta outra
• a mensagem não é utilizada para iniciar o bloco seguinte, o que implica que as operações de cifra de bloco podem ser feitas antecipadamente permitindo que o último passo seja realizado em paralelo assim que o texto (mensagem ou mensagem cifrada) estiver disponível
Descreve o CTR
Apresentado por Diffie e Hellman em 1979
Modo de cifra padrão para o AES
Nonce+contador devem ser diferentes em cada operação de cifra
• Caso seja usada a mesma chave e o mesmo nonce+contador para cifrar dois conteúdos diferentes, eles serão cifrados com duas chaves contínuas iguais :(
Quais são os requisitos de robustez das cifras simétricas continuas?
Secretismo, aleatoriedade e uso único da chave de fluxo
A chave de fluxo precisa ser distribuída nas duas pontas do canal
Quais são as 4 vantagens e desvantagens da criptografia simétrica?
Chave secreta
– se perdida ou revelada em qualquer ponta, o canal é comprometido
Distribuição de chaves
– O problema do ovo e da galinha: “como distribuir a chave para ter canais seguros sem ter canais seguros?”
– E se as chaves precisarem de ser mudadas frequentemente
Gestão de chaves
– Grande escala
– (n(n-1)/2) chaves são requeridas para n participantes
Eficientes
Que criptografia é mais lenta, simétrica ou assimétrica?
Assimétrica
Como funciona a cifra assimétrica?
Cifra com a chave pública de forma a poder decifrar com a chave privada
O algoritmo Diffie-Hellman lançou as bases para que tipo de criptografia?
Assimétrica
Qual é o objectivo do Diffie-Hellman?
Obter um número secreto K, partilhado entre A e B, sem o comunicar em claro
Como se realiza a operação do Diffie-Hellman?
escolher dois números primos m e n públicos (n grande)
A gera um número aleatório xa
A calcula ya = m^xa MOD n
B gera um número aleatório xb
B calcula yb =m^xb MOD n
ya e yb são tornados públicos
Cada um calcula K localmente utilizando ya e yb
A segurança do Diffie-Hellman está baseada em que problema?
Dado um elemento m e os valores m^x e m^y, qual o valor de m^xy?
O RSA pode ser usado para que duas funções?
Cifrar e assinar
Como se procede à criptanálise do RSA?
- Procura de chaves “à bruta”
• Inexequível se usarmos chaves grandes (≥ 1024 bits) - Ataques matemáticos
• d é fácil de calcular a partir de e se forem conhecidos p e q -> factorização de nos grandes
• Determinar m a partir de c, e e n -> Função inversa da exponenciação modular: logaritmo modular
• ainda seguro com chaves ≥ 1024 bits - Ataques temporais (timing attacks) na execução da operação de decifração
• Consegue estimar d pelo tempo que demora uma decifração
Quais são os outros dois algoritmos de criptografia assimétrica?
El Gamal e Elliptic Curve Cryptography
Quais são as vantagens e desvantagens da criptografia assimétrica?
Eficiência :(
Escala :)
Distribuição da chaves públicas – cuidado !
– autenticidade das chave públicas
O que tornou necessária a cifra híbrida?
As cifras simétricas serem eficientes mas não escaláveis
As cifras assimétricas não serem eficientes mas escaláveis
O melhor de dois mundos
Em que consiste o envelope digital da cifra hibrida?
O envelope digital consiste na mensagem encriptada com a chave simétrica aleatória e a chave simétrica aleatória encriptada com a chave pública do utilizador.
O que são funções de síntese?
Produzem valores de dimensão constante a partir de entradas (mensagens, ficheiros, …) de dimensão variável
– A função de compressão é aplicada de forma iterativa
• 2 argumentos de entrada da função de compressão: síntese prévia, bloco a processar
– Não servem para cifrar/decifrar
Quais são as 3 propriedades das funções de síntese?
Resistência à descoberta do texto original
• Dada a síntese H, é muito difícil descobrir um texto M, tal que H = h(M)
Resistência à descoberta de um segundo texto original
• Dado um Texto M, é muito difícil descobrir M’(M’≠M) tal que h(M)=H(M’)
Resistência à colisão
• É difícil descobrir dois textos quaisquer, M e M’, M’≠M, tais que h(M) = h(M’)
Quais são as dimensões de uma síntese?
> = 128 bits
O que é um ataque de aniversário?
Baseia-se no “paradoxo do aniversário” e é usado para encontrar um par de mensagens com a mesma síntese (colisão)
Para sínteses de n bits, o atacante deve tentar aproximadamente 2^(n/2) mensagens
Como é que o SHA aumenta a sua segurança?
Aumentando o tamanho da sintese