UNISINOS
Teoria da Informação
Ataque KGC Malicioso na
Criptografia Sem Certificado
José Rodrigo Molina Moraes
Sidarta Omar Semprebon da Silva
São Leopoldo, 08 de junho de 2007.
Sistemas de Autenticação

Entre 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 (IDPKC)) são freqüentemente adotadas.
Característica PKI
Num 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-PKC

De 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 (IDPKC) por Shamir em 1984.
Característica ID-PKC

O 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).
KGC
KGC , 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 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 Chaves

A 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 Chaves

Para 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, CLPKC.) ou, simplesmente, criptografia sem
certificado. É um modelo onde não há a
necessidade
de
certificados
para
relacionar chaves públicas com suas
entidades.
Problemas Constatados
PKI - 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-PKC

Em 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.
Ataques
Há 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.

Ataques

Tipo 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 passivo-mas-malicioso
O 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 paper

Propõ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 Paterson

Esquemas 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-ZhangDeng

Essa 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 paper


Mostramos 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

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

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
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 Assinatura
Sem Certificado (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/ assinatura s/
certificado (CL-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/ criptografia s/
certificado (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 passivo-mas-malicioso:
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 assinatura sem
certificado de Hu-Wong-Zhang-Deng:
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 criptografia sem
certificado de 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 (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 (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.