Ataque KGC Malicioso na Ataque KGC Malicioso na Criptografia Sem Criptografia Sem CertificadoCertificado

José Rodrigo Molina MoraesSidarta Omar Semprebon da Silva

São Leopoldo, 08 de junho de 2007.

UNISINOS Teoria da Informação

Sistemas de AutenticaçãoSistemas de AutenticaçãoEntre os sistemas de autenticação

existentes, tecnologias assimétricas, como a infra-estrutura de chaves públicas (PKI – Public Key Infrastructure) e a criptografia de chave pública baseada em identidades (Identity-Based Public Key Cryptography (ID-PKC)) são freqüentemente adotadas.

Característica PKICaracterística PKINum típico sistema PKI, há a

necessidade de certificado para garantir ao usuário sobre o relacionamento entre a chave pública e a identidade de quem possui a chave privada correspondente;

Com o PKI, a utilização de certificados digitais torna-se complexa, pois é preciso gerenciar revogação, armazenamento, distribuição, etc.

ID-PKCID-PKCDe forma a dispensar a

necessidade de uma infra-estrutura de chaves públicas (PKI), pela complexidade do gerenciamento dos certificados digitais, foi proposto o modelo de criptografia de chave pública baseada em identidades (ID-PKC) por Shamir em 1984.

Característica ID-PKCCaracterística ID-PKCO esquema tem a propriedade

única de que a chave pública do usuário pode ser facilmente calculada da sua identidade (por exemplo, seu endereço de e-mail, nome ou CPF), enquanto que a chave privada pode ser calculada para ele por uma autoridade confiável chamada de Key Generator Center (KGC).

KGCKGCKGC , ou Centro de Geração de

Chaves, é uma TTP (Trusted Third Party).

É uma entidade confiável. É responsável por emitir parcialmente as chaves secretas associadas aos destinatários de mensagens criptografadas.

Característica KGCCaracterística KGC A dependência sobre um KGC

que usa uma chave mestre para todo sistema para gerar chaves privadas inevitavelmente introduz a custódia de chaves1 para sistemas ID-PKC.

1. Do inglês, key escrow.

Problema da Custódia de Problema da Custódia de ChavesChavesA custódia de chaves é uma

propriedade indesejável em muitas aplicações, pois a autoridade que gerencia o sistema tem o conhecimento de todas as chaves secretas associadas a cada identidade.

Problema da Custódia de Problema da Custódia de ChavesChavesPara evitar a inerência à custódia

de chaves, Al-Riyami e Paterson, em 2003, propuseram o conceito de criptografia de chave pública sem certificado (Certificateless Public Key Cryptography, CL-PKC.) ou, simplesmente, criptografia sem certificado. É um modelo onde não há a necessidade de certificados para relacionar chaves públicas com suas entidades.

Problemas ConstatadosProblemas ConstatadosPKI - gerenciamento de certificados;ID-PKC – custódia de chaves, pois o

KGC sempre conhece a chave secreta do usuário;

CL-PKC – ainda se mantém problemas advindos da custódia de chaves.

Exploramos adiante o problema do ataque KGC malicioso, referente a CL-PKC.

Característica CL-PKCCaracterística CL-PKCEm um sistema CL-PKC, um KGC

está envolvido em emitir uma chave parcial do usuário cuja identidade presume-se que seja única no sistema. O usuário também gera independentemente um par de chave pública/secreta do usuário.

AtaquesAtaquesHá dois tipos de ataques a serem

considerados para criptografia sem certificado:

Tipo I - Ataque de Substituição da Chave: Um terceiro tenta personificar o usuário depois de comprometer sua chave secreta e/ou substituir sua chave pública com algum valor escolhido pelo terceiro. Mas ele não conhece a chave parcial do usuário.

AtaquesAtaquesTipo II - Ataque KGC

Malicioso: O KGC conhece a chave parcial do usuário e tenta personificar o usuário. Mas o KGC não conhece a chave secreta do usuário ou como substituir a chave pública do usuário.

KGC KGC passivo-mas-passivo-mas-maliciosomaliciosoO KGC malicioso pode bisbilhotar

passivamente os textos cifrados enviados ao usuário e tentar decifrá-los usando seus conhecimento da chave parcial do usuário.

Nos referimos a esse KGC como KGC passivo-mas-malicioso.

Proposta do Proposta do paperpaperPropõe-se capturar os ataques KGC

passivos-mas-maliciosos especificando novos modelos adversários do Tipo II para esquemas de criptografia e assinatura sem certificado, removendo a hipótese que o KGC deva ser benigno durante o passo de geração da chave e ao executar a geração da chave parcial do usuário. Foi adotada a definição Hu-Wong-Zhang-Deng.

Al-Riyami e PatersonAl-Riyami e PatersonEsquemas de criptografia sem

certificado e assinatura sem certificado foram propostos por Al-Riyami e Paterson em 2003. Cada uma das definições consiste de sete algoritmos. As definições foram adotadas até que uma definição simplificada para esquemas de assinatura sem certificado foi proposta por Hu, Wong, Zhang e Deng em 2006.

Característica Hu-Wong-Característica Hu-Wong-Zhang-DengZhang-DengEssa definição consiste de 5

algoritmos. Visa ser mais versátil e mantém a característica da criptografia sem certificado: o par de chave pública/secreta do usuário pode ser gerado independentemente pelo usuário mesmo antes de obter a chave parcial de usuário do KGC.

Proposta do Proposta do paperpaperMostramos que os esquemas propostos

por Al-Riyami e Paterson são vulneráveis a ataques KGC passivos-mas-maliciosos (ataque Tipo II) em nossos novos modelos adversários.

Damos novas provas para o esquema de assinatura sem certificado proposto por Hu, Wong, Zhang e Deng e o esquema de criptografia proposto por Libert e Quisquater de que são seguros sob nossos novos modelos adversários.

Adversário – Conceito Adversário – Conceito Um adversário é um algoritmo

probabilístico, construído por um criptoanalista, com o intuito de extrair alguma informação útil para os seus propósitos. Informalmente, dizemos que um ataque a um criptossistema é uma ofensiva aplicada por um adversário.

Jogo – Conceito Jogo – Conceito Para se chegar à definição do que

vem a ser um esquema seguro, especifica-se primeiramente uma forma de interação entre o adversário e o criptossistema. Isso se dá estabelecendo-se um jogo, com regras bem definidas, em que nenhuma das partes (nem o adversário, nem seu desafiante) de antemão pode saber se vai ganhar ou não.

Oráculo – Conceito Oráculo – Conceito Há ataques que permitem que o

criptoanalista tenha acesso aos algoritmos de criptografia e/ou decriptografia, dependendo do caso.

Costuma-se chamar o acesso ao algoritmo de decriptografia por consulta ao oráculo de decriptografia.

Modelo Adversário para Modelo Adversário para Assinatura Sem Certificado Assinatura Sem Certificado (CL-SIG)(CL-SIG)

Há 2 tipos de adversários: AI e AII.Há 5 oráculos que podem ser

acessados pelos adversários de acordo com especificações do jogo.

Definimos 2 jogos para os adversários: Game Sign-I e Game Sign-II.

Modelo adversário p/ Modelo adversário p/ assinatura s/ certificado (CL-assinatura s/ certificado (CL-SIG): constatação.SIG): constatação.No Game Sign-I, AI pode obter a

chave secreta do usuário e substituir a chave pública do usuário antes de gerar uma falsificação.

No Game Sign-II, AII pode não somente gerar o par de chave mestre maliciosamente, como gerar a chave parcial do usuário maliciosamente.

Modelo adversário p/ Modelo adversário p/ criptografia s/ certificado criptografia s/ certificado (CL-ENC): constatação.(CL-ENC): constatação.Há 2 tipos de adversários: BI e BII.Há 5 oráculos que podem ser

acessados.Há 2 jogos para os adversários: Game

Enc-I e Game Enc-II.O adversário BI simula um terceiro

lançando um ataque de substituição da chave e BII modela ataques lançados pelo KGC passivo-mas-malicioso.

Ataque KGC Ataque KGC passivo-mas-passivo-mas-malicioso: malicioso: como atacar.como atacar.A chave pública do usuário é

publicada. A partir da chave pública, o KGC pode computar a chave secreta do usuário. Desde que a chave parcial do usuário é gerada pelo KGC, após obter a chave secreta de usuário da vítima, o KGC pode, então, decriptografar todos os textos cifrados ou gerar qualquer assinatura em nome da vítima.

Esquema genérico de Esquema genérico de assinatura sem certificado de assinatura sem certificado de Hu-Wong-Zhang-Deng: Hu-Wong-Zhang-Deng: constatação.constatação.

Se substituirmos o oráculo de assinatura com o oráculo de assinatura proposto no esquema Hu-Wong-Zhang-Deng, vemos que o esquema é seguro no Game Sign-I. Também é seguro com o Game Sign-II, apenas adicionamos o ingrediente do ataque KGC passivo-mas-malicioso.

Esquema genérico de Esquema genérico de criptografia sem certificado de criptografia sem certificado de Libert-Quisquater: constatação.Libert-Quisquater: constatação.Libert e Quisquater propuseram uma

construção genérica CL-ENC que realiza segurança contra ataques por texto cifrado escolhido (CCA).

O esquema é seguro no Game Enc-I e Game Enc-II, pois o oráculo de decriptografia não pode ser acessado. Também é seguro contra CPA.

CCA – Conceito CCA – Conceito CCA (chosen ciphertext attack) –

modelo de ataque por texto ilegível1 escolhido: o adversário possui uma chave pública e consulta o oráculo de decriptografia, porém somente antes de receber um desafio de texto cifrado.

1. Do inglês, ciphertext.

CPA – Conceito CPA – Conceito CPA (chosen plaintext attack) –

modelo de ataque por texto legível1 escolhido: o adversário tem uma chave pública e pode fazer criptografias de mensagens à sua escolha.

1. Do inglês, plaintext.