cl_kas_mandt - IME-USP

Transcrição

Correção de Deficiências no Acordo de Chaves de
Mandt
Vilc Queupe Rufino
Instituto de Matemática e Estatı́stica - Universidade de São Paulo
23 de Junho de 2009
Sumário
Sumário
1
Introdução
Objetivo
Metodologia
Motivação
2
Conceitos Básicos
Notações
Emparelhamento Bilinear
Problemas de Interesse
Nı́veis de Confiança
3
Acordo de Chaves
Acordos de Chaves sem Certificados
Adversários
Atributo de Segurança
Acordo de Chaves de Mandt
Vulnerabilidade de Swanson
Modelo para mais de um KGC
Deficiência para KGCs diferentes
4
Correção
Correção da Deficiência para KGCs diferentes
5
Conclusão
6
Referências
Introdução
Objetivo
Objetivo
A respeito do protocolo de acordo de chaves proposto por [Mandt
and Tan, 2006], será apresentado:
A vulnerabilidade descrita em [Swanson, 2008];
Uma proposta para correção da vulnerabilidade de Swanson;
Uma nova deficiência na versão para múltiplos KGCs;
Uma proposta para correção da deficiência em múltiplos
KGCs;
Utilização do modelo corrigido para uso hierárquico;
Introdução
Metodologia
Metodologia
Verificar os conceitos básicos aplicados no protocolo de
Mandt;
Apresentar o protocolo de Mandt em sua forma original;
Apresentar a vulnerabilidade de Swanson e sua correção
proposta;
Verificar as modificações para a versão com múltiplos KGCs;
Discutir possı́veis deficiências e correção proposta;
Verificar uso futuro do protocolo corrigido;
Em todas as correções verificar a manutenção da integridade.
Introdução
Motivação
Motivação
Necessidade de um protocolo hierárquico para acordo de
chaves com certificação implı́cita;
O uso de dois KGCs descrito em Mandt foi fundamental pra
estabelecer relações entre entidades de ramos hierárquicos
diferentes;
Há bons estudos sobre protocolos sem certificados;
Há um ótimo trabalho feito pela Denise em [Goya, 2006].
Deficiências não identificadas podem ser mais nocivas que às
conhecidas
Conceitos Básicos
Notações
Notações utilizadas nesta apresentação
q
G1
G2
G = hg i
Zq
a, b, c, x, y
Q, R ∈ G1
A, B
IDA
n∈N
H(·) → {0, 1}n
um valor primo grande;
grupo aditivo cı́clico de ordem prima q;
grupo multiplicativo cı́clico de ordem prima q;
g é um valor gerador do grupo G
conjunto dos números inteiros mod q;
valores inteiros mod q;
pontos da curva elı́ptica em G1 ;
usuários do sistema criptográfico (entidades);
Identificação da entidade A;
um valor natural;
Função hash que retorna um valor de n bits;
Conceitos Básicos
Emparelhamento Bilinear
Emparelhamento Bilinear Admissı́vel
Por [Boneh and Franklin, 2001]:
A um algoritmo eficiente 1 .
Definição
e : G1 × G1 → G2 é um “Emparelhamento Bilinear Admissı́vel”:
Bilinear:
Para qualquer P, Q, R ∈ G1 , temos:
e(P + Q, R) = e(P, R) · e(Q, R) e
e(P, Q + R) = e(P, Q) · e(P, R).
caso particular a, b ∈ Zq :
e(aQ, bQ) = e(Q, Q)ab
= e(abQ, Q) = e(Q, abQ)
Não degenerativo: ∀hQ, Ri, e(Q, R) 6= identidade G2 ;
Eficiente:
∀hQ, Ri, ∃A → A ≡ e(Q, R).
Conceitos Básicos
Definição
“Problema do Logaritmo Discreto” (DLP):
Dado b ∈ G e g um gerador de G
Encontrar um valor a ∈ Zq ,
tal que b = g a .
Conceitos Básicos
Definição
“Problema do Logaritmo Discreto sobre Curvas Elı́pticas”
(DLP-EC):
Caso especial do DLP:
Seja J ⊆ G
Dado Q ∈ G e R ∈ J;
Encontrar um valor a,
tal que 1 ≤ a ≤ |J| − 1 e Q a = R,
Q ◦ Q ◦ ...Q
{z
}
onde Q a = | a vezes
Se G é o conjunto finito de pontos sobre uma curva elı́ptica,
a operação ‘◦’ é a soma de dois pontos. Então:
Encontrar um valor a,
tal que Q = aR.
Conceitos Básicos
Definição
“Problema de Diffie-Hellman Bilinear” (BDH):
Dados Q, aQ, bQ, cQ ∈ G1 ,
onde a, b, c ∈ Z∗q e Q um gerador do grupo G1 :
encontrar o valor e(Q, Q)abc ∈ G2 .
Conceitos Básicos
Definição
“Problema de Decisão de Diffie-Hellman Bilinear” (DBDH):
Dados Q, aQ, bQ, cQ ∈ G1 e z ∈ G2 ,
onde a, b, c ∈ Z∗q e Q um gerador do grupo G1 :
decidir se z = e(Q, Q)abc .
Conceitos Básicos
Nı́veis de confiança, de [Girault, 1991]:
Nı́vel 1. autoridade conhece (ou calcula facilmente)
chaves secretas dos usuários; pode personificar
qualquer entidade sem ser detectada;
Nı́vel 2. autoridade desconhece (ou dificilmente calcula)
qualquer entidade, gerando falsas chaves
públicas, sem ser detectada;
Nı́vel 3. autoridade desconhece (ou dificilmente calcula)
qualquer entidade, porém é detectada;
Conceitos Básicos
Modelo convencional com PKI geralmente é nı́vel 3;
Sistemas IBS em geral são nı́vel 1;
O modelo descrito por [Gennaro et al., 2008] é nı́vel 1;
Sistemas CLS em geral são nı́vel 2;
O Sistema Hierárquico baseado em [Mandt and Tan, 2006] é
nı́vel 2.
Acordo de Chaves
Esquema de Acordo de Chaves
É um protocolo que permite duas ou mais entidades obter
acesso a um segredo compartilhado;
Podem ser divididos em “interativos” e “não interativos”;
A chave definida em protocolos interativos é chamada “chave
de sessão”;
A interação ocorre durante o tempo de sessão;
A entrega de segredos por uma autoridade de confiança via
canal seguro antes do compartilhamento de chaves é chamado
de “Pré-Distribuição de Chaves” [Stinson, 2006] pág. 393.
Acordo de Chaves
Acordo de Chaves
Acordo de Chaves
Acordo de Chaves
Acordo de Chaves
Dispensa a necessidade da infra-estrutura de chaves públicas;
A chave privada possui duas partes, uma gerada pela
Autoridade de Confiança (KGC) e outra pelo próprio usuário;
Não há custódia de chaves;
A chave pública é gerada pelo usuário, a partir de parâmetros
públicos;
A identidade faz parte da chave pública e também é usada
para garantir a autenticidade.
Acordo de Chaves
Adversários
Adversários para Acordos de Chaves
Externos
Não possuem acesso a chave mestra, porém é capaz
de substituir as chaves públicas;
Internos
Possuem acesso a chave mestra, mas não são
capazes de substituir as chaves públicas;
KGC mal intencionado
KGC que não estabelece honestamente os parâmetros
do sistema, e neste caso estaremos assumindo que
seja um adversário interno, e não possa substituir as
chaves públicas.
Acordo de Chaves
Segurança contra personificação quanto ao comprometimento da
chave:
Se a chave da entidade A foi comprometida, um atacante C
não pode se passar por um outro usuário B;
Ressalta-se que todos os sistemas não interativos estão sujeito
a este ataque, pois o atacante tem o mesmo poder que A para
calcular a chave compartilhada.
Acordo de Chaves
Este trabalho mostra como um adversário externo é capaz de
personificar o usuário B perante o usuário A, utilizando-se de
valores públicos e eventualmente substituindo chaves públicas.
Acordo de Chaves
Modelo Mandt
Definição
A Autoridade do Sistema KGC define:
G1 , G2 , e : G1 × G1 → G2 , Q ∈ G1 , Qo =sQ,
H : {0, 1}∗ → G1 , H 0 : (G2 , G1 , G1 ) → {0, 1}n
onde s é um valor secreto escolhido pelo KGC, n ∈ N.
Acordo de Chaves
Modelo Mandt
Definição
A entidade A:
QA = H(IDA )
Recebe DA =sQA =sH(IDA ), chave secreta parcial (dir);
Escolhe um aleatório xA ∈ Z∗q , chave secreta parcial (esq);
Chave privada SA = hxA ,DA i = hxA ,sQA i;
Chave Pública PA = XA =xA Q.
Para o acordo de chaves interativo:
Escolhe um aleatório a ∈ Z∗q e
Envia TA =aQ
Acordo de Chaves
Modelo Mandt
Definição
A calcula a chave de sessão com B:
KA0 = e(QB , XB + Qo )a ·e(xA QA +DA , TB )
KAB = H 0 (KA0 ,aTB ,xA XB ) = H 0 (KA0 ,abQ,xA xB Q)
Acordo de Chaves
Modelo Mandt
Definição
Consistência de KA0 :
KA0 =e(QB , XB + Qo )a
·e(xA QA +DA , TB )
=e(H(IDB ),xB Q+sQ)a
·e(xA H(IDA )+sH(IDA ),bQ)
=e(H(IDB ), (xB + s)Q)a
·e((xA + s)H(IDA ),bQ)
=e(H(IDB ), Q)a(xB +s)
·e(H(IDA ), Q)b(xA +s)
=e((xB + s)H(IDB ),aQ)
·e(H(IDA ), (xA + s)Q)b
=e(xB H(IDB )+sH(IDB ),aQ)·e(H(IDA ),xA Q+sQ)b
0
KB =e(xB QB +DB , TA )
·e(QA , XA + Qo )b
Acordo de Chaves
Modelo Mandt
Acordo de Chaves
Em [Swanson, 2008] é mostrado como um adversário externo E
pode assumir a identidade de um usuário legı́timo B perante o
usuário A, conhecendo-se apenas o valor secreto xA :
E substitui a chave pública de B e envia para A a chave
pública PB∗ = −Qo + βQ e o valor TB = bQ;
No protocolo original a chave pública é somente PB , e
portanto A somente verificará se PB∗ ∈ G1 ;
0 :
A calculará normalmente sua chave comum KAB
Acordo de Chaves
0 =e(Q , X + Q )a
KAB
·e(xA QA + DA , TB )
o
B
B
=e(H(IDB ), −Qo + βQ + Qo )a ·e(xA H(IDA ) + sH(IDA ), bQ)
=e(H(IDB ), βQ)a
·e((xA + s)H(IDA ), bQ)
=e(H(IDB ), Q)aβ
·e(H(IDA ), Q)b(xA +s)
=e(βH(IDB ), aQ)
·e(H(IDA ), (xA + s)Q)b
=e(βH(IDB ), aQ)
·e(H(IDA ), xA Q + sQ)b
0∗
KBA =e(βQB , TA )
·e(QA , XA + Qo )b
Acordo de Chaves
O valor de xA é necessário na função hash H 0 , pois o
adversário precisa do valor xA XB =xA xB Q.
Em [Al-Riyami and Paterson, 2003] a chave pública é dada
por:
Acordo de Chaves
hXA , YA i = h xA Q,xA Qo i
Então cada usuário deve conferir o emparelhamento:
e(Q, YA ) = e(Qo , XA )
e(Q,xA sQ) = e(sQ,xA Q) = e(Q, Q)xA s
Acordo de Chaves
Neste caso, para que o adversário tenha êxito, ele deve calcular o
valor:
YB∗ = xB∗ sQ = (β − s)sQ
Para este cálculo o adversário precisa do valor s, contudo este
valor está protegido pelo PLD-CE.
Acordo de Chaves
Modelo de Mandt para mais de um KGC
Definição
A Autoridade do Sistema define:
G1 , G2 , e : G1 × G1 → G2 , Q ∈ G1 , Qo =sQ,
H : {0, 1}∗ → G1 , H 0 : (G2 , G1 , G1 ) → {0, 1}n
onde s é um valor secreto escolhido pelo KGC, n ∈ N.
Cada KGCi define:
Escolhe si ∈ Z∗q
Qi =si Q;
Supomos ainda que calcula Qoi =si Qo .
Acordo de Chaves
Definição
A entidade A do KGCi :
QA = H(IDA )
Recebe DA =si QA =si H(IDA ), chave secreta parcial (dir);
Escolhe um aleatório xA ∈ Z∗q , chave secreta parcial (esq);
Chave privada SA = hxA ,DA i = hxA ,si QA i;
Chave Pública PA = hXA , YA i = h xA Q, xA Qi.
Para o acordo de chaves interativo:
Escolhe um aleatório a ∈ Z∗q e
Envia TA =aQ
Acordo de Chaves
Definição
Cálculo da chave A do KGC1 e B do KGC2
A confere a chave pública de B:
e(XB , Qo ) = e(YB , Q)
e(xB Q,sQ)=e(xB sQ, Q)
e(Q, Q)xB s = e(Q, Q)xB s
A confere a chave pública do KGC2 :
e(Q2 , Qo ) = e(Qo2 , Q)
e(s2 Q,sQ)=e(s2 sQ, Q)
e(Q, Q)s2 s = e(Q, Q)s2 s
KA0 = e(QB , XB + Q2 )a ·e(xA QA +DA , TB )
KAB = H 0 (KA0 ,aTB ,xA XB ) = H 0 (KA0 ,abQ,xA xB Q)
Acordo de Chaves
Definição
Consistência de KA0 :
KA0 =e(QB , XB + Q2 )a
·e(xA QA +DA , TB )
=e(H(IDB ),xB Q+s2 Q)a
·e(xA H(IDA )+s1 H(IDA ),bQ)
=e(H(IDB ), (xB + s2 )Q)a
·e((xA + s1 )H(IDA ),bQ)
=e(H(IDB ), Q)a(xB +s2 )
·e(H(IDA ), Q)b(xA +s1 )
=e((xB + s2 )H(IDB ),aQ)
·e(H(IDA ), (xA + s1 )Q)b
=e(xB H(IDB )+s2 H(IDB ),aQ)·e(H(IDA ),xA Q+s1 Q)b
0
KB =e(xB QB +DB , TA )
·e(QA , XA + Q1 )b
Acordo de Chaves
Modelo Mandt para 2 ou mais KGCs
Acordo de Chaves
Você consegue enxergar a deficiência???
Acordo de Chaves
Apresentamos como um adversário externo E pode assumir a
identidade de um usuário legı́timo B de perante o usuário A:
E escolhe aleatoriamente sE ∈ Z∗q ;
Constrói um falso KGCE e lhe atribui o valor de QE = sE Q e
QoE = sE Qo , substitui a chave pública do verdadeiro KGCi da
entidade B;
Calcula a chave pública PB∗ = hXB∗ , YB∗ i = hxB∗ Q, xB∗ QoE i
Envia para a entidade A a chave pública PB∗ e o valor
TB∗ = bQ
A verifica e(Q, YB∗ ) = e(QoE , XB∗ ) e e(Q, QoE ) = e(Qo , QE ),
os quais são válidos;
A calcula a chave com a entidade E , sem perceber que o
KGCE é falso:
Acordo de Chaves
0 =e(H(ID ), X ∗ + Q )a
KAB
·e(xA H(IDA1 ) + DA , TB∗ )
B
E
B
∗
a
=e(H(IDB ), xB Q + sE Q)
·e(xA H(IDA ) + s1 H(IDA ), bQ)
∗
a
=e(H(IDB ), (xB + sE )Q)
·e((xA + s1 )H(IDA ), bQ)
∗
=e(H(IDB ), Q)a(xB +sE )
·e(H(IDA ), Q)b(xA +s1 )
·e(H(IDA ), (xA + s1 )Q)b
=e((xB∗ + sE )H(IDB ), aQ)
∗
=e(xB H(IDB ) + sE H(IDB ), aQ)·e(H(IDA ), xA Q + s1 Q)b
0 =e(x ∗ H(ID ) + s H(ID ), T )·e(H(ID ), X + Q )b
KBA
1
B
E
B
A
A
A
B
Acordo de Chaves
Esta deficiência ocorre porque não existem relações privadas
entre as chaves secretas dos KGCs, isto permite que qualquer
participante do sistema gere seu próprio KGC;
A solução trivial para evitar esta deficiência é entregar para
todas as entidades as chaves públicas de todos os KGC;
Contudo esta solução não é plenamente aceitável.
Correção
Modelo Mandt
Correção
Apresentamos como um adversário externo E pode assumir a
identidade de um usuário legı́timo B de perante o usuário A:
A Autoridade do Sistema (KGCo ) define:
G1 , G2 , e : G1 × G1 → G2 , Q ∈ G1 , Qo =so Q,
H : {0, 1}∗ → G1 , H 0 : (G2 , G1 , G1 ) → {0, 1}n
onde so é um valor secreto escolhido pelo KGCo , n ∈ N.
Cada KGCi define:
Qi = H(IDKGCi )
Recebe do KGCo DKGCi = so Qi = so H(IDKGCi ), sua chave
parcial secreta (dir);
Escolhe si ∈ Z∗q , sua chave parcial secreta (esq);
Chave secreta SKGCi = hxKGCi , DKGCi i = hxA , so Qi i;
Chave pública
PKGCi = hXKGCi , YKGCi i = hsi Q, si Qo i = hsi Q, si so Qi;
Correção
Entidade A do KGCi bdefine:
QA = H(IDA ) Recebe
DA = si QA + DKGCi = si H(IDA ) + so H(IDKGCi ), sua chave
parcial secreta (dir)
Escolhe xA ∈ Z∗q , sua chave parcial secreta (esq);
Chave secreta SA = hxA , DA i = hxA , si H(IDA ) + so H(IDKGCi )i
Chave pública PA = hXA , YA i = hxA Q, xA Qo i = hxA Q, xA si Qi
Durante a fase de sessão, a entidade A: escolhe
aleatoriamente um valor a ∈ Z∗q , calcula e envia TA = aQ
para a outra entidade.
Correção
Cálculo da chave A do KGC1 e B do KGC2
A confere a chave pública de B:
e(XB , Qo ) = e(YB , Q)
e(xB Q,sQ) = e(xB sQ, Q)
e(Q, Q)xB so =e(Q, Q)xB so
A confere a chave pública do KGC2 :
e(XKGC2 , Qo )=e(YKGC2 , Q)
e(s2 Q,so Q) =e(s2 so Q, Q)
e(Q, Q)s2 so = e(Q, Q)s2 so
0 = e(Q , X + X
a
a
KAB
B
B
KGC2 ) · e(Q2 , Qo ) · e(xA QA + DA , TB )
Correção
A nova proposta continua sendo consistente;
Para criar um KGC∗ falso é necessário obter informação do
emparelhamento:
e(Q2 , Qo )a ou e(xA QA + DA , TB )
No primeiro caso:
e(H(KGC2 ), so Q)a = e(H(KGC2 ), so aQ) = e(Q2 , so TA ),
descobrir informações a respeito do emparelhamento é o
mesmo que resolver o BDH, ou descobrir o PLD-CE.
Q2 = γQ;
O segundo caso é o mesmo que resolver todo o protocolo de
Mandt;
Correção
A nova proposta continua sendo consistente;
Para criar um KGC∗ falso é necessário obter informação do
emparelhamento:
e(Q2 , Qo )a ou e(xA QA + DA , TB )
No primeiro caso:
e(H(KGC2 ), so Q)a = e(H(KGC2 ), so aQ) = e(Q2 , so TA ),
descobrir informações a respeito do emparelhamento é o
mesmo que resolver o BDH, ou descobrir o PLD-CE.
Q2 = γQ;
O segundo caso é o mesmo que resolver todo o protocolo de
Mandt;
O KGCo pode obter o valor deste emparelhamento, podendo
realizar este ataque. Esta solução atinge somente o nı́vel 2 da
escala de Girault..
Correção
A relação criada entre os KGCo e os KGCi s pode ser estendida
para nı́veis hierárquicos, onde o KGCo define os parâmetros do
(l)
(l+1)
sistema, e cada KGCi no nı́vel l passa para o KGCj
no nı́vel
l + 1 uma chave parcial secreta
DKGC (l+1) = s (l) H(IDKGC l+1 ) + DKGC l . A chave comum será
j
KGC
i
i
i
calculada usando-se um novo emparelhamento para cada nı́vel, a
demonstração é deixada como exercı́cio para o leitor.
Conclusão
Conclusão
Apresentamos uma deficiência nova no protocolo de [Mandt
and Tan, 2006] para uso com mais de 1 KGCs;
Apresentamos possı́veis soluções para a vulnerabilidade
de [Swanson, 2008] conhecida e a nova deficiência;
Nossa solução usa mais 4 emparelhamentos, prejudicando a
eficiência;
Contudo a complexidade do algorı́tmo não foi alterada, ainda
é possı́vel calcular os emparelhamentos em paralelo,
tornando-o mais eficientes em sistemas multiprocessados;
Referências
Al-Riyami, S. S. and Paterson, K. G. (2003).
Certificateless public key cryptography.
In LNCS - Asiacrypt’03, pages 452–473, Taipei, Taiwan.
Springer-Verlag.
Boneh, D. and Franklin, M. K. (2001).
Identity-based encryption from the weil pairing.
In LNCS - Cripto’01, pages 213–229, Santa Barbara,
California, USA. Springer-Verlag.
v.2139.
Gennaro, R., Halevi, S., Krawczyk, H., Rabin, T., Reidt, S.,
and Wolthusen, S. D. (2008).
Strongly-resilient and non-interactive hierarchical
key-agreement in manets.
In LNCS - Esorics’08, volume 5283, pages 47–55.
Springer-Berlin.
v.5283.
Referências
Girault, M. (1991).
Self-certified public keys.
In LNCS - EuroCrypt’91, pages 490–497. Springer Berlin.
v.547.
Goya, D. H. (2006).
Proposta de esquemas de criptografia e de assinatura sob
modelo de criptografia de chave pública sem certificado.
Master’s thesis, IME - Universidade de São Paulo.
http://www.ime.usp.br/~dhgoya/dis_denise.pdf.
Mandt, T. K. and Tan, C. H. (2006).
Certificateless Authenticated Two-Party Key Agreement
Protocols.
In 11th Asian Computing Science Conference’06, pages 37–44.
Springer Berlin.
v.4435.
Stinson, D. R. (2006).
Referências
Cryptography Theory and Pratice.
Chapman & Hall/CRC, Waterloo.
Swanson, C. M. (2008).
Security in key agreement: Two-party certificateless schemes.
Master’s thesis, University of Waterloo - Canadá.
http://hdl.handle.net/10012/4156.

cl_kas_mandt - IME-USP

Transcrição

Documentos relacionados

jogo chave umbrako bola fervi jogo chave umbrako bola hr

ATA Nº25

Um Passo por um Sorriso - Escola Superior de Enfermagem Dr

pela voz dos avós - Galicia Encantada

“como chegar”, pergunte ao nosso recepcionista.

Satsang do Coletivo do Um

TeSP de Mecânica Automóvel

NOTIFICAÇÃO DE ENTREGA DE IMÓVEL.indd

Sistema anti-furto Chaves

The KeyWatcher - Grasp Sistemas e Comércio