Self-organised Group Key
Management for Ad Hoc
Networks
Adriano Simões 53813
Tiago Almeida 53867
Problema
■
Desenvolver um protocolo para estabelecer uma
chave de sessão comum a um conjunto de nós.
Motivação
■
Cenários de Guerra
■
Catástrofes
■
Emergências
■
Monitorização Ambiental
■
Entretenimento (Rede Segura de Portáteis/PDA's)
Requisitos
■
Não existe qualquer tipo de acordo à priori (infraestrutura, chaves partilhadas, routing, “terceiras
entidades confiáveis”)
■
Chave tem de ser gerada por todos.
■
Rede tem de permitir que nós se juntem ou a
abandonem facilmente.
■
TEM DE SER SEGURO! 
(Confidencial)
Ideia do protocolo
■
Alguns nós da rede são definidos como “grupo
iniciador” (Initiator Group = IG)
■
IG combina entre si (de forma segura) uma chave
de sessão a usar.
■
Chave de sessão é propagada ao resto da rede
(de forma segura).
■
Todo o tráfego “útil” é cifrado com chave de
sessão (qualquer algoritmo)
Restrições
■
Os nós que iniciam a rede (IG) têm de conseguir
comunicar uns com os outros directamente.
■
Cada nó tem uma maneira única de ser
identificado. (ex: SIM card)
Ideia “refinada” do protocolo
■
IG acorda um conjunto P de chaves e particiona-o
em K subconjuntos.

{1,2,3,4,5,6}  { {1,2} , {3,4} , {5,6} }
■
Cada nó escolhe aleat. Uma chave de cada
subconjunto. (cada um fica com K chaves).
■
Nós tentam “adivinhar” as chaves que os vizinhos
escolheram aleat.
■
Quando cada nó souber as chaves do vizinho,
geram todos uma chave de sessão.
Notação
■
Existe um conjunto P de chaves igual para todos
os nós e público.
■
Conjunto P tem tamanho N.
■
O conjunto P irá ser partido em k blocos de m
elementos (N=mk).
■
L é o número mínimo de chaves partilhadas entre
cada par de nós para que se considere que eles
têm uma ligação segura.
Protocolo
■
Consiste em 3 fases:



Setup Inicial.
Descoberta de chaves partilhadas.
Estabelecer chave de sessão e propagá-la a toda a
rede.
Protocolo
■
Consiste em 3 fases:



Setup Inicial.
Descoberta de chaves partilhadas.
Estabelecer chave de sessão e propagá-la a toda a
rede.
Setup Inicial
■
Definir o conjunto P (tamanho N e elementos).
■
Definir k (número de subconjuntos).
■
Partir P em k subconjuntos chamados blocos.
■
Definir L.
■
(Isto pode ser hardcoded ou negociado
dinamicamente)
■
Cada nó escolhe 1 chave de cada bloco
aleatoriamente.
Protocolo
■
Consiste em 3 fases:



Setup Inicial.
Descoberta de chaves partilhadas.
Estabelecer chave de sessão e propagá-la a toda a
rede.
■
■
Cifras Homomórficas
Cifras Homomórficas:


E(A) & E(B) = E(A&B) , & é uma operação qualquer.
K*E(A) = E(K*A)
Descoberta de chaves partilhadas 1/6
■
Na fase de Setup cada nó escolheu k chaves do
conjunto P.
■
A tem de conseguir perceber as chaves de B e de
C que são iguais às suas. Como?
Descoberta de chaves partilhadas 2/6
■
A constrói um polinómio FA(x)=(x-KA1)*…*(x-KAk)

(fácil ver que FA(KA1) = 0)
■
Aplica a distributiva e obtém os coeficientes do
polinómio.
(Exemplo para B)
■
Cifra os coeficientes com algoritmo de cifra
homomórfico e envia a B.
■
B recebe o polinómio, calcula:

Zi = EKA(rFA(KBi)) onde r é um número aleatório e envia
para A.
Descoberta de chaves partilhadas 3/6
■A decifra obtendo rFA(KBi).
■Se este valor for 0 então a chave é igual tanto em
A como em B.
Descoberta de chaves partilhadas 4/6
■
“Demonstração”






■
B tem o seguinte: EKA(c1), … , EKA(ck+1)
EKA(c1)*xk + … + EKA(ck+1)* x0
EKA(c1)*B1k + … + EKA(ck+1)* B10
EKA(c1 * B1k) + …. + EKA(ck+1 *B10)
EKA(c1 * B1k + ... + ck+1 *B10)
EKA(FA(KB1))
=
=
=
=
Porquê o r ?



Atacante sabe que o B respondeu com algo estilo:
EKA(c1)*Xk + … + EKA(ck+1)* X0
E também sabe EKA(ck) , portanto seria só resolver a
equação em ordem a X para obter os Bi
Descoberta de chaves partilhadas 5/6
■
Este processo é repetido para todas as chaves de
cada nó, para todos os nós.
■
Finalmente, cada nó fica com uma matriz que diz
para cada nó as chaves que são comuns.
■
Matriz tem q-1 linhas por k colunas, onde q é o
número de nós no IG.
Descoberta de chaves partilhadas 6/6
■
O IG considera-se bem formado se existirem L
chaves partilhadas entre cada par de nós do IG.
■
Se não existirem, os nós não concordantes voltam
a repetir o processo para tentar acertar em chaves
comuns.
Protocolo
■
Consiste em 3 fases:



Setup Inicial.
Descoberta de chaves partilhadas.
Estabelecer chave de sessão e “propagá-la” a toda a
rede.
Estabeler chave de sessão
■
Cada nó i (pertencente a IG) gera um aleatório Si
■
Cada nó i calcula o XOR de todas as L chaves
partilhadas KIG = K1IG xor…xor KLIG
■
Cada nó i cifra Si com KIG e envia para todos os
vizinhos (pertencentes a IG).
■
Cada nó decifra com KIG e calcula a chave de
sessão Ks = S1 xor … xor Sr
■
Finalmente (Chave partilhada entre o IG)!
Propagar chave de sessão
■
Cada nó do IG manda a chave de sessão para os
vizinhos (só para os que tem ligação segura, ou
seja, L chaves partilhadas).
Ideia:
O novo Nó junta-se a partir de um Nó já pertencente à rede.
➔ A Chave de Sessão tem que ser mudada para que o novo
nó não veja comunicação passada (Segurança Futura
Perfeita).
➔
Propagar chave de sessão 2
■
Cada nó na fronteira repete a fase 2 com os
vizinhos fora do IG.
■
Gera-se uma nova chave de sessão aplicando
função não invertível à chave de sessão actual.
(seg. futura perfeita)
■
Nós da rede passam a usar a nova chave.
■
Nova chave enviada para o novo membro usando
as L chaves comuns como cifra.
Seguro?
■
Soa bem, mas será realmente seguro?!
■
Situação1: Atacante consegue apanhar o tráfego
entre todos os nós.
Seguro?
■
Mensagens trocadas na fase 2 são cifradas com
cifra homomórfica segura.
■
Desde que o algoritmo de cifra seja seguro,
atacante não tem qualquer informação das L
chaves partilhadas.
Chave de sessão também vai cifrada com
algoritmo seguro.
■
■
■
■
N=mk chaves possíveis.
Ele sabe valor de L (público) mas não sabe de
que bloco é que cada chave veio.
Vai ter de testar (kCL)mL conjuntos de chaves.
Seguro?
■
■
Parâmetros bem definidos:
1264 chaves, partidas em blocos de 4  316
blocos. 20 chaves partilhadas por todos.
■
m=4 , L=20 , k=316
■ (316C20)420
Seguro!
■
■
Parâmetros bem definidos:
1264 chaves, partidas em blocos de 4  316
blocos. 20 chaves partilhadas por todos.
■
m=4 , L=20 , k=316
■ (316C20)420 ~=
2150
Seguro!
■
Situação 2: Atacante apoderou-se de um dos nós.

■
■
Assumindo que os vizinhos conseguem detectar essa
situação…
B envia para rede a dizer “D é espião!”
Todas as chaves comuns entre B e D estão
comprometidas!
Seguro!
■
D é eliminado da lista de nós autorizados da rede.
■
Se a intersecção entre chaves comuns BD com
chaves BA e BC for “pequena” segurança da rede
continua intacta.
■
B volta a juntar-se à rede. 
Mais detalhes
■
Protocolo é independente do algoritmo de Cifra
E(.) desde que seja homomórfico na soma.
■
Paper usa algoritmo de cifra algo complexo para
ser usado, proposto por Chan.

■
A. C.-F. Chan and E. S. R. Sr. Distributed symmetric key management for
mobile ad hoc networks. In Infocom 2004, 2004.
Consideramos não ser importante devido à
independência do protocolo.
Eficiência e mobilidade
• Protocolo é muito pesado.
– K+1 coefs  k+1 cifras + k decifras.
– Cada nó faz o mesmo. N nós  n(k^2 + 2k +1) trocas de informação na
rede e cálculos.
– Nj - nós a juntar, p – custo (de)cifra homomórfica , a – custo de soma em
dados cifrados homomórficamente.
Memória
K valores
Tempo processamento
N((2k+1)p + ak2)
Custo junção
Nj((2k+1)p + ak2)
Mais detalhes
■
Custo amortizado. Cada nó só precisa de 1
ligação segura com 1 vizinho para pertencer à
rede.
■
Um nó ao mover-se pode ganhar novos vizinhos e
negociar chaves com eles aumentando a
fiabilidade da rede.
Como definir bem os parâmetros?
■
Parâmetros mal definidos podem tornar a
probabilidade de formação de IG muito baixa ou
tornar o sistema fraco.
■
Bons valores tornam o sistema fortíssimo e com
boa probabilidade de formação de IG (>=0.5).
■
Fácil ver que:



Quanto maior L maior a segurança e menor a probabilidade de
formação de IG.
Quanto mais nós no IG maior a força da chave de sessão mas menor
a probabilide de formação de IG.
Quanto menor k (e menor m para N fixo N=mk) menor a
probabilidade de formação de IG mas maior a segurança.
Trabalhos relacionados
■
Artigo refere dois outros trabalhos parecidos:


Chan
Eschenauer and Gligor
■
O primeiro tem baixa probabilidade de formação
de IG (muito baixa).
■
Segundo requer terceira entidade confiável.
■
Algoritmo de cifra usado é o do Chan.
Dúvidas / sugestões?