cl_kas_mandt - IME-USP
Transcrição
cl_kas_mandt - IME-USP
Correção de Deficiências no Acordo de Chaves de Mandt Vilc Queupe Rufino Instituto de Matemática e Estatı́stica - Universidade de São Paulo 23 de Junho de 2009 Sumário Sumário 1 Introdução Objetivo Metodologia Motivação 2 Conceitos Básicos Notações Emparelhamento Bilinear Problemas de Interesse Nı́veis de Confiança 3 Acordo de Chaves Acordos de Chaves sem Certificados Adversários Atributo de Segurança Acordo de Chaves de Mandt Vulnerabilidade de Swanson Modelo para mais de um KGC Deficiência para KGCs diferentes 4 Correção Correção da Deficiência para KGCs diferentes 5 Conclusão 6 Referências Introdução Objetivo Objetivo A respeito do protocolo de acordo de chaves proposto por [Mandt and Tan, 2006], será apresentado: A vulnerabilidade descrita em [Swanson, 2008]; Uma proposta para correção da vulnerabilidade de Swanson; Uma nova deficiência na versão para múltiplos KGCs; Uma proposta para correção da deficiência em múltiplos KGCs; Utilização do modelo corrigido para uso hierárquico; Introdução Metodologia Metodologia Verificar os conceitos básicos aplicados no protocolo de Mandt; Apresentar o protocolo de Mandt em sua forma original; Apresentar a vulnerabilidade de Swanson e sua correção proposta; Verificar as modificações para a versão com múltiplos KGCs; Discutir possı́veis deficiências e correção proposta; Verificar uso futuro do protocolo corrigido; Em todas as correções verificar a manutenção da integridade. Introdução Motivação Motivação Necessidade de um protocolo hierárquico para acordo de chaves com certificação implı́cita; O uso de dois KGCs descrito em Mandt foi fundamental pra estabelecer relações entre entidades de ramos hierárquicos diferentes; Há bons estudos sobre protocolos sem certificados; Há um ótimo trabalho feito pela Denise em [Goya, 2006]. Deficiências não identificadas podem ser mais nocivas que às conhecidas Conceitos Básicos Notações Notações utilizadas nesta apresentaçã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 é um valor gerador do grupo G conjunto dos números inteiros mod q; valores inteiros mod q; pontos da curva elı́ptica em G1 ; usuários do sistema criptográfico (entidades); Identificação da entidade A; um valor natural; Função hash que retorna um valor de n bits; Conceitos Básicos Emparelhamento Bilinear Emparelhamento Bilinear Admissı́vel Por [Boneh and Franklin, 2001]: A um algoritmo eficiente 1 . Definição e : G1 × G1 → G2 é 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) Não degenerativo: ∀hQ, Ri, e(Q, R) 6= identidade G2 ; Eficiente: ∀hQ, Ri, ∃A → A ≡ e(Q, R). Conceitos Básicos Problemas de Interesse Problemas de Interesse Definiçã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 Básicos Problemas de Interesse Problemas de Interesse Definiçã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 é o conjunto finito de pontos sobre uma curva elı́ptica, a operação ‘◦’ é a soma de dois pontos. Então: Encontrar um valor a, tal que Q = aR. Conceitos Básicos Problemas de Interesse Problemas de Interesse Definiçã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 Básicos Problemas de Interesse Problemas de Interesse Definição “Problema de Decisã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 Básicos Nı́veis de Confiança Nı́veis de Confiança Nı́veis de confiança, de [Girault, 1991]: Nı́vel 1. autoridade conhece (ou calcula facilmente) chaves secretas dos usuários; pode personificar qualquer entidade sem ser detectada; Nı́vel 2. autoridade desconhece (ou dificilmente calcula) chaves secretas dos usuários; pode personificar qualquer entidade, gerando falsas chaves públicas, sem ser detectada; Nı́vel 3. autoridade desconhece (ou dificilmente calcula) chaves secretas dos usuários; pode personificar qualquer entidade, porém é detectada; Conceitos Básicos Nı́veis de Confiança Nı́veis de Confiança Modelo convencional com PKI geralmente é nı́vel 3; Sistemas IBS em geral são nı́vel 1; O modelo descrito por [Gennaro et al., 2008] é nı́vel 1; Sistemas CLS em geral são nı́vel 2; O Sistema Hierárquico baseado em [Mandt and Tan, 2006] é nı́vel 2. Acordo de Chaves Esquema de Acordo de Chaves É um protocolo que permite duas ou mais entidades obter acesso a um segredo compartilhado; Podem ser divididos em “interativos” e “não interativos”; A chave definida em protocolos interativos é chamada “chave de sessão”; A interação ocorre durante o tempo de sessão; A entrega de segredos por uma autoridade de confiança via canal seguro antes do compartilhamento de chaves é chamado de “Pré-Distribuição de Chaves” [Stinson, 2006] pág. 393. Acordo de Chaves Acordo de Chaves Acordo de Chaves Acordo de Chaves Acordo de Chaves Acordos de Chaves sem Certificados Acordos de Chaves sem Certificados Dispensa a necessidade da infra-estrutura de chaves públicas; A chave privada possui duas partes, uma gerada pela Autoridade de Confiança (KGC) e outra pelo próprio usuário; Não há custódia de chaves; A chave pública é gerada pelo usuário, a partir de parâmetros públicos; A identidade faz parte da chave pública e também é usada para garantir a autenticidade. Acordo de Chaves Adversários Adversários para Acordos de Chaves Externos Não possuem acesso a chave mestra, porém é capaz de substituir as chaves públicas; Internos Possuem acesso a chave mestra, mas não são capazes de substituir as chaves públicas; KGC mal intencionado KGC que não estabelece honestamente os parâmetros do sistema, e neste caso estaremos assumindo que seja um adversário interno, e não possa substituir as chaves públicas. Acordo de Chaves Atributo de Segurança Atributo de Segurança Segurança contra personificação quanto ao comprometimento da chave: Se a chave da entidade A foi comprometida, um atacante C não pode se passar por um outro usuário B; Ressalta-se que todos os sistemas não interativos estão sujeito a este ataque, pois o atacante tem o mesmo poder que A para calcular a chave compartilhada. Acordo de Chaves Atributo de Segurança Atributo de Segurança Este trabalho mostra como um adversário externo é capaz de personificar o usuário B perante o usuário A, utilizando-se de valores públicos e eventualmente substituindo chaves públicas. Acordo de Chaves Acordo de Chaves de Mandt Modelo Mandt Definiçã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 é um valor secreto escolhido pelo KGC, n ∈ N. Acordo de Chaves Acordo de Chaves de Mandt Modelo Mandt Definição A entidade A: QA = H(IDA ) Recebe DA =sQA =sH(IDA ), chave secreta parcial (dir); Escolhe um aleatório xA ∈ Z∗q , chave secreta parcial (esq); Chave privada SA = hxA ,DA i = hxA ,sQA i; Chave Pública PA = XA =xA Q. Para o acordo de chaves interativo: Escolhe um aleatório a ∈ Z∗q e Envia TA =aQ Acordo de Chaves Acordo de Chaves de Mandt Modelo Mandt Definição A calcula a chave de sessã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 Acordo de Chaves de Mandt Modelo Mandt Definição Consistê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 Acordo de Chaves de Mandt Modelo Mandt Acordo de Chaves Vulnerabilidade de Swanson Vulnerabilidade de Swanson Em [Swanson, 2008] é mostrado como um adversário externo E pode assumir a identidade de um usuário legı́timo B perante o usuário A, conhecendo-se apenas o valor secreto xA : E substitui a chave pública de B e envia para A a chave pública PB∗ = −Qo + βQ e o valor TB = bQ; No protocolo original a chave pública é somente PB , e portanto A somente verificará se PB∗ ∈ G1 ; 0 : A calculará normalmente sua chave comum KAB Acordo de Chaves Vulnerabilidade de Swanson Vulnerabilidade de Swanson 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 Vulnerabilidade de Swanson Vulnerabilidade de Swanson O valor de xA é necessário na função hash H 0 , pois o adversário precisa do valor xA XB =xA xB Q. Em [Al-Riyami and Paterson, 2003] a chave pública é dada por: Acordo de Chaves Vulnerabilidade de Swanson Vulnerabilidade de Swanson hXA , YA i = h xA Q,xA Qo i Então cada usuá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 Vulnerabilidade de Swanson Vulnerabilidade de Swanson Neste caso, para que o adversário tenha êxito, ele deve calcular o valor: YB∗ = xB∗ sQ = (β − s)sQ Para este cálculo o adversário precisa do valor s, contudo este valor está protegido pelo PLD-CE. Acordo de Chaves Modelo para mais de um KGC Modelo de Mandt para mais de um KGC Definiçã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 é 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 Modelo para mais de um KGC Modelo de Mandt para mais de um KGC Definição A entidade A do KGCi : QA = H(IDA ) Recebe DA =si QA =si H(IDA ), chave secreta parcial (dir); Escolhe um aleatório xA ∈ Z∗q , chave secreta parcial (esq); Chave privada SA = hxA ,DA i = hxA ,si QA i; Chave Pública PA = hXA , YA i = h xA Q, xA Qi. Para o acordo de chaves interativo: Escolhe um aleatório a ∈ Z∗q e Envia TA =aQ Acordo de Chaves Modelo para mais de um KGC Modelo de Mandt para mais de um KGC Definição Cálculo da chave A do KGC1 e B do KGC2 A confere a chave pú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 pú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 A calcula a chave de sessão com B: 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 Modelo para mais de um KGC Modelo de Mandt para mais de um KGC Definição Consistê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 para mais de um KGC Modelo Mandt para 2 ou mais KGCs Acordo de Chaves Deficiência para KGCs diferentes Você consegue enxergar a deficiência??? Acordo de Chaves Deficiência para KGCs diferentes Deficiência para KGCs diferentes Apresentamos como um adversário externo E pode assumir a identidade de um usuário legı́timo B de perante o usuário A: E escolhe aleatoriamente sE ∈ Z∗q ; Constrói um falso KGCE e lhe atribui o valor de QE = sE Q e QoE = sE Qo , substitui a chave pública do verdadeiro KGCi da entidade B; Calcula a chave pública PB∗ = hXB∗ , YB∗ i = hxB∗ Q, xB∗ QoE i Envia para a entidade A a chave pública PB∗ e o valor TB∗ = bQ A verifica e(Q, YB∗ ) = e(QoE , XB∗ ) e e(Q, QoE ) = e(Qo , QE ), os quais são válidos; A calcula a chave com a entidade E , sem perceber que o KGCE é falso: Acordo de Chaves Deficiência para KGCs diferentes Deficiência para KGCs diferentes 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 Deficiência para KGCs diferentes Deficiência para KGCs diferentes Esta deficiência ocorre porque não existem relações privadas entre as chaves secretas dos KGCs, isto permite que qualquer participante do sistema gere seu próprio KGC; A solução trivial para evitar esta deficiência é entregar para todas as entidades as chaves públicas de todos os KGC; Contudo esta solução não é plenamente aceitável. Correção Correção da Deficiência para KGCs diferentes Modelo Mandt Correção Correção da Deficiência para KGCs diferentes Correção da Deficiência para KGCs diferentes Apresentamos como um adversário externo E pode assumir a identidade de um usuário legı́timo B de perante o usuá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 é 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 pública PKGCi = hXKGCi , YKGCi i = hsi Q, si Qo i = hsi Q, si so Qi; Correção Correção da Deficiência para KGCs diferentes Correção da Deficiência para KGCs diferentes 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 pública PA = hXA , YA i = hxA Q, xA Qo i = hxA Q, xA si Qi Durante a fase de sessão, a entidade A: escolhe aleatoriamente um valor a ∈ Z∗q , calcula e envia TA = aQ para a outra entidade. Correção Correção da Deficiência para KGCs diferentes Correção da Deficiência para KGCs diferentes Cálculo da chave A do KGC1 e B do KGC2 A confere a chave pú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 pú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 A calcula a chave de sessão com B: 0 = e(Q , X + X a a KAB B B KGC2 ) · e(Q2 , Qo ) · e(xA QA + DA , TB ) Correção Correção da Deficiência para KGCs diferentes Correção da Deficiência para KGCs diferentes A nova proposta continua sendo consistente; Para criar um KGC∗ falso é necessário obter informaçã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 informações a respeito do emparelhamento é o mesmo que resolver o BDH, ou descobrir o PLD-CE. Q2 = γQ; O segundo caso é o mesmo que resolver todo o protocolo de Mandt; Correção Correção da Deficiência para KGCs diferentes Correção da Deficiência para KGCs diferentes A nova proposta continua sendo consistente; Para criar um KGC∗ falso é necessário obter informaçã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 informações a respeito do emparelhamento é o mesmo que resolver o BDH, ou descobrir o PLD-CE. Q2 = γQ; O segundo caso é o mesmo que resolver todo o protocolo de Mandt; O KGCo pode obter o valor deste emparelhamento, podendo realizar este ataque. Esta solução atinge somente o nı́vel 2 da escala de Girault.. Correção Correção da Deficiência para KGCs diferentes Correção da Deficiência para KGCs diferentes A relação criada entre os KGCo e os KGCi s pode ser estendida para nı́veis hierárquicos, onde o KGCo define os parâ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 será j KGC i i i calculada usando-se um novo emparelhamento para cada nı́vel, a demonstração é deixada como exercı́cio para o leitor. Conclusão Conclusão Apresentamos uma deficiência nova no protocolo de [Mandt and Tan, 2006] para uso com mais de 1 KGCs; Apresentamos possı́veis soluções para a vulnerabilidade de [Swanson, 2008] conhecida e a nova deficiência; Nossa solução usa mais 4 emparelhamentos, prejudicando a eficiência; Contudo a complexidade do algorı́tmo não foi alterada, ainda é possı́vel calcular os emparelhamentos em paralelo, tornando-o mais eficientes em sistemas multiprocessados; Referê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. Referê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 pública sem certificado. Master’s thesis, IME - Universidade de Sã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). Referê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 - Canadá. http://hdl.handle.net/10012/4156.