-
Universidade de BrasliaInstituto de Cincias Exatas
Departamento de Cincia da Computao
Um problema de escala na distribuio de chavespblicas e seu
impacto na ICP Brasil
Ivan Menezes Sena
Monograa apresentada como requisito parcial
para concluso do Bacharelado em Cincia da Computao
Orientador
Prof. Dr. Pedro A. D. Rezende
Braslia
2017
-
Universidade de Braslia UnB
Instituto de Cincias Exatas
Departamento de Cincia da Computao
Bacharelado em Cincia da Computao
Coordenador: Prof. Dr. Rodrigo Bonifcio de Almeida
Banca examinadora composta por:
Prof. Dr. Pedro A. D. Rezende (Orientador) CIC/UnB
Prof. Dr. Jan Mendonca Correa CIC/UnB
Prof. Dr. Edison Ishikawa CIC/UnB
CIP Catalogao Internacional na Publicao
Sena, Ivan Menezes.
Um problema de escala na distribuio de chaves pblicas e seu
impacto
na ICP Brasil / Ivan Menezes Sena. Braslia : UnB, 2017.
219 p. : il. ; 29,5 cm.
Monograa (Graduao) Universidade de Braslia, Braslia, 2017.
1. Criptograa assimtrica, 2. algoritmo RSA, 3. chave
privada,
4. chave pblica, 5. primos grandes, 6. ICP-Brasil, 7. MP
2200-2,
8. entropia, 9. gerao de primos aleatrios, 10. ITI, 11. teste
de
Lenstra, 12. biblioteca GMP, 13. fastGCD
CDU 004
Endereo: Universidade de Braslia
Campus Universitrio Darcy Ribeiro Asa Norte
CEP 70910-900
BrasliaDF Brasil
-
Universidade de BrasliaInstituto de Cincias Exatas
Departamento de Cincia da Computao
Um problema de escala na distribuio de chavespblicas e seu
impacto na ICP Brasil
Ivan Menezes Sena
Monograa apresentada como requisito parcial
para concluso do Bacharelado em Cincia da Computao
Prof. Dr. Pedro A. D. Rezende (Orientador)
CIC/UnB
Prof. Dr. Jan Mendonca Correa Prof. Dr. Edison Ishikawa
CIC/UnB CIC/UnB
Prof. Dr. Rodrigo Bonifcio de Almeida
Coordenador do Bacharelado em Cincia da Computao
Braslia, 29 de novembro de 2017
-
Dedicatria
Dedico esta conquista aos meus amados pais Frederico Arajo Sena
e Maria de
Ftima Menezes Sena, minha estimada irm Pmela Menezes Sena
Ferreira e meus
dois queridos sobrinhos Eduardo Sena L. Ferreira e Maria Vitria
Sena Ferreira.
i
-
Agradecimentos
Universidade de Braslia, por me proporcionar a oportunidade de
estudar e apren-
der com mestres, doutores e graduados das mais diversas reas das
cincias. Sou grato
cada membro do corpo docente, direo e a administrao dessa
instituio de
ensino.
professora Germana Menezes da Nobrega, por todo auxlio e esforo
empregados
no meu regresso para a Universidade de Braslia.
Ao professor Pedro Antnio Dourado de Rezende, alm de toda
pacincia e apoio
durante a produo deste trabalho, suas aulas em Segurana de Dados
me permitiram
encontrar o meu lugar na Cincia da Computao.
Ao meu psiclogo, Thiago Cardoso Costa, por me auxiliar durante o
meu perodo
afastado da universidade e por me proporcionar as ferramentas
didticas necessrias
para o meu sucesso acadmico e prossional.
Ao meu colega Gabriel Gomes Gaspar por toda ajuda prestada
durante as etapas
iniciais deste trabalho.
Aos meus amigos Lucas Alem Martins e Fernanda Moraes, pela viso
e reviso
jurdica que serviram de apoio ao desenvolvimento deste
trabalho.
minha me Maria de Ftima Menezes Sena e minha irm Pmela Menezes
Sena
Ferreira, por todo auxlio e tempo empreendidos na reviso
ortogrca deste trabalho.
minha famlia, por sempre me apoiar e sempre estar presente.
Aos meus amigos de infncia, por nunca me deixaram duvidar das
minhas capaci-
dades.
Aos meus companheiros de farda, os Tubares do Cerrado, por me
motivarem a ser
melhor todos os dias.
ii
-
Resumo
O presente Trabalho de Graduao aborda um problema que surge na
relao entre
a funo semiolgica de irrefutabilidade de assinaturas digitais, e
o desequilbrio de
riscos e responsabilidades legais imposto a signatrios pelo
regime da ICP-BR. Anali-
samos a relao lgica entre as premissas de inviolabilidade dessas
assinaturas, e um
nvel adequado de entropia no processo de gerao de nmeros primos
que compem
chaves criptogrcas, sob condies de uso em larga escala do
algoritmo RSA. Mos-
tramos a implementao de um algoritmo estado-da-arte que
relativiza tais premissas,
pelo mtodo indireto que permite derivar uma chave privada RSA a
partir da chave
pblica correspondente, mediante fatorao do mdulo desse par de
chaves via clcu-
los amostrais de MDCs. Revelamos os resultados da execuo desse
algoritmo em um
ambiente preparado para realizar teste de robustez em
importantes acervos de chaves
pblicas, com vistas ao acervo das chaves certicadas no regime da
ICP-BR. Desenvol-
vemos e apresentamos uma aplicao para teste de robustez de
chaves pblicas RSA
individuais, voltada para o usurio comum. Expomos todas as
tentativas frustradas
de contactar ou engajar o ITI (Instituto Nacional de Tecnologia
da Informao) e,
luz do recente caso paralelo na Estnia em que 750 mil certicados
digitais foram
revogados devido deteco de correspondente vulnerabilidade ,
tambm motivos que
supomos plausveis para o desinteresse das autoridades
responsveis pela ICP-BR na
cooperao originalmente proposta para este Trabalho.
Palavras-chave: Criptograa assimtrica, algoritmo RSA, chave
privada, chave p-
blica, primos grandes, ICP-Brasil, MP 2200-2, entropia, gerao de
primos aleatrios,
ITI, teste de Lenstra, biblioteca GMP, fastGCD
iii
-
Abstract
The present work examines a problem that arises from the
relationship between the
semiological irrefutability function of digital signatures and
unbalances among risks and
responsibilities imposed upon signatories under Brazil's ocial
PKI regime (ICP-BR).
We analyze the logical relation between digital signature's
premises for inviolability
and an adequate level of entropy for the process of generating
pseudorandom prime
integers to compose cryptographic keys, under conditions of
widespread use of the
RSA algorithm. We show an implementation of a state-of-the-art
algorithm which
relativizes these premises, through the indirect method that
allows for the derivation
of a RSA private key from the corresponding public key, upon
factoring of the key
pair's module through the sampling calculations of GCDs. We
reveal the results from
executing said algorithm on a setup prepared for testing
robustness of important public
key collections, aiming for the collection of RSA public keys
certied under the ICP-
BR regime. We expose all frustrated attempts to engage the
National Institute of
Information Technology (ITI) and, given the recent parallel case
in Estonia where
750 thousand digital certicates were revoked due to detection of
the corresponding
vulnerability , also the motives we deem plausible for the
unconcern and aloofness of
ICP-BR authorities regarding the cooperation originally proposed
for this work.
Keywords: Asymmetric cryptography, RSA algorithm, private key,
public Key, big
prime numbers, ICP-Brasil, MP 2200-2, entropy, generic prime
number generation,
ITI, Lenstra test, GMP library, fastGCD
iv
-
Sumrio
1 Introduo 1
1.1 Apresentao de termos e conceitos . . . . . . . . . . . . . .
. . . . . . 1
1.2 A equivalncia entre fsico e virtual . . . . . . . . . . . .
. . . . . . . . 5
1.3 O problema jurdico da funo semiolgica . . . . . . . . . . .
. . . . . 6
1.4 O teste de Lenstra . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 7
1.5 A possibilidade realista de violao da primeira premissa de
conana . 10
1.6 Motivao e caminho percorrido . . . . . . . . . . . . . . . .
. . . . . . 11
2 Raiz do Problema 13
2.1 Identicando a raiz do problema . . . . . . . . . . . . . . .
. . . . . . . 13
2.1.1 O RSA (isoladamente) robusto? . . . . . . . . . . . . . .
. . . 14
2.1.2 Intervalos entre nmeros primos . . . . . . . . . . . . . .
. . . . 15
2.1.3 A raz da vulnerabilidade . . . . . . . . . . . . . . . . .
. . . . . 17
3 Um problema ou vrios? 19
3.1 Anlise dos possveis problemas . . . . . . . . . . . . . . .
. . . . . . . 19
3.2 Anlise do perl dos primos em mdulos fatorados . . . . . . .
. . . . . 21
3.2.1 Gerao de primos na biblioteca OpenSSL . . . . . . . . . .
. . 22
3.2.2 Gerao de primos no necessariamente seguros na
biblioteca
OpenSSL . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 22
3.3 Onde e quando o OpenSSL utiliza geradores pseudorandmicos
com
baixa entropia? . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 25
v
-
4 Geradores Pseudorandomicos no Kernel LINUX 27
4.1 Propriedades de um gerador pseudorandmico seguro . . . . . .
. . . 28
4.1.1 Estrutura dos PRNGs random e urandom no Linux . . . . . .
. 28
4.1.2 Outputs dos repositrios . . . . . . . . . . . . . . . . .
. . . . . 29
4.1.3 Adio ao contador de entropia . . . . . . . . . . . . . . .
. . . 30
4.1.4 Atualizao dos repositrios . . . . . . . . . . . . . . . .
. . . . 31
4.1.5 Extrao de Bits aleatrios dos repositrios secundrio e
urandom 31
4.2 Fragilidades no LRNG . . . . . . . . . . . . . . . . . . . .
. . . . . . . 33
4.2.1 Ataque de criptoanlise na propriedade 1. no LRNG . . . . .
. 33
4.2.2 Ataque na gerao de Entropia do reservatrio primrio . . . .
. 34
4.3 Consideraes Finais . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 34
5 Entendendo o algoritmo implementado por Halderman 36
5.1 Introduo . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 36
5.1.1 rvore de Multiplicao . . . . . . . . . . . . . . . . . . .
. . . 39
5.1.2 rvore de Restos . . . . . . . . . . . . . . . . . . . . .
. . . . . 40
5.1.3 Mximo Divisor Comum . . . . . . . . . . . . . . . . . . .
. . . 41
6 Metodologia 42
6.1 O setup para o FastGCD . . . . . . . . . . . . . . . . . . .
. . . . . . . 43
6.1.1 Biblioteca GMP . . . . . . . . . . . . . . . . . . . . . .
. . . . . 44
6.1.2 Base de mdulos RSA . . . . . . . . . . . . . . . . . . . .
. . . 45
6.2 Resultados do fastGCD . . . . . . . . . . . . . . . . . . .
. . . . . . . . 46
6.2.1 Coleta de mdulos no repositrio da EFF . . . . . . . . . .
. . . 46
6.2.2 Colises, tempos de execuo e erros . . . . . . . . . . . .
. . . 47
6.3 A motivao para a ferramenta Chave Fraca GUI . . . . . . . .
. . . . 48
6.4 Manual Chave Fraca GUI . . . . . . . . . . . . . . . . . . .
. . . . . . 48
7 ICP-Brasil 54
vi
-
7.1 Alguns termos Jurdicos . . . . . . . . . . . . . . . . . . .
. . . . . . . 55
7.1.1 nus da Prova . . . . . . . . . . . . . . . . . . . . . . .
. . . . 55
7.1.2 Medida Provisria . . . . . . . . . . . . . . . . . . . . .
. . . . 55
7.1.3 Autarquia . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 55
7.1.4 F Pblica . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 56
7.1.5 Prova Diablica . . . . . . . . . . . . . . . . . . . . . .
. . . . . 56
7.2 Sobre a MP 2200 . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 56
7.3 Desequilbrio de riscos e responsabilidades . . . . . . . . .
. . . . . . . 58
7.3.1 Certicados de uso geral . . . . . . . . . . . . . . . . .
. . . . . 58
7.3.2 Risco vinculado a chave de uso geral . . . . . . . . . . .
. . . . 59
7.4 Inverso do nus da prova . . . . . . . . . . . . . . . . . .
. . . . . . . 61
7.4.1 A iniciativa privada e o seu interesse na ICP-Brasil . . .
. . . . 62
7.4.2 O problema da inverso do nus da prova . . . . . . . . . .
. . 63
8 Consideraes Finais 65
8.1 O caso da Estnia . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 67
8.2 Concluso . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 68
Referncias 72
A Algoritmo responsvel pelo teste de robustez 76
B Algoritmo responsvel pelo calculo da Chave Privada 80
C Algoritmo responsvel por encriptar uma mensagem 82
D Ofcio encaminhado para o ITI 84
E E-mail enviado ao Doutor Ricardo Custdio no dia 05 de Julho
88
F Despacho encaminhado para assessoria da GRT 90
vii
-
G A reunio que nunca aconteceu 92
H Regulamentao da Criptograa de Curvas Elpticas Brainpool
para
gerao de Chaves Assimtricas no mbito da ICP-BRASIL 96
viii
-
Lista de Figuras
4.1 esquema PRNG [26] . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 29
4.2 Extrao de bits aleatrios da funo TGFSR [26] . . . . . . . .
. . . . 32
5.1 rvore de multiplicao [34] dos mdulos para fatorao . . . . .
. . . 40
5.2 rvore de restos [34] dos mdulos utilizada para encontrar a
existncia
de um divisor comum a dois mdulos distintos . . . . . . . . . .
. . . 40
6.1 Teste de coliso entre Chave Pblica e coleo de mdulos RSA
em
hexadecimal . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 50
6.2 Resultado do teste de coliso entre Chave Pblica e coleo de
mdulos
RSA em hexadecimal . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 50
6.3 Calculo do expoente da Chave Privada . . . . . . . . . . . .
. . . . . . 51
6.4 Prova dos nove. . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 52
ix
-
Captulo 1
Introduo
Em segurana nas comunicaes, possvel observar que a busca por
mtodos para
se estabelecer transmisses consideradas seguras entre dois
agentes um problema
circular, do tipo metaforicamente conhecido em linguagem popular
como de ovo-e-
galinha. Tal metfora, assim empregada para ilustrar esta busca,
se refere ao uso da
criptograa para proteger sigilo ou integridade de mensagens ou
documentos durante
transmisses digitais (seja atravs do tempo, ou do espao). Pois
tal uso requer trans-
misso j protegida (no mnimo, com integridade) da chave
criptogrca que antes
encripta ou que depois autentica tais mensagens ou documentos.
Este trabalho tema-
tiza um problema relacionado gerncia de chaves criptogrcas, que
expe nuanas
dessa metfora. Mais precisamente, um problema que surge com o
uso disseminado
de protocolos projetados para viabilizar a distribuio e gesto de
chaves pblicas em
larga escala, operando sob o escopo de uma constelao de regras
de natureza jurdica.
1.1 Apresentao de termos e conceitos
Antes de prosseguir com a introduo ao tema, necessrio uma breve
apresentao
de determinados termos, aos quais atribuiremos sentido tcnico
especco, adequado
correta interpretao do contedo deste trabalho. O primeiro termo
que utilizaremos
com uma acepo tcnica especca, de extrema relevncia para nossa
abordagem,
conana. Conana deve ser aqui entendida como aquilo que essencial
para um
canal de comunicao e que no pode ser transferido da fonte para o
destino atravs
deste canal1. Aquilo que essencial para que a informao
supostamente transmitida
faa sentido, ou seja, produza algum signicado coerente com a
situao cognitiva do
1
-
receptor da transmisso.
O segundo termo que usaremos com acepo especca premissas de
conana [5].
Premissas de conana so as condies ou requisitos para operao
adequada dos me-
canismos escolhidos para a proteo desejada. Exemplos incluem
condies e requisitos
relacionados implementao, instalao e operao de determinado
algoritmo crip-
togrco, de senha ou de chaves, garantia de origem de material
criptogrco, canal
utilizvel para transmisses de inicializao destes, etc. Com tais
denies, podemos
abordar com mais clareza os processos de distribuio e gesto de
chaves criptogrcas,
com foco em chaves pblicas.
O terceiro termo a denir, assinatura digital. Assinatura digital
um esquema
criptogrco criado para tornar possvel a validao de origem e de
integridade de
mensagens e documentos em meio digital, de forma objetiva [2];
Ou seja, de forma
que possa ser tecnicamente sustentada, no domnio jurdico, como
oponvel a terceiros.
Em essncia, a assinatura digital busca prover as mesmas funes
semiolgicas2 que a
assinatura de punho desempenha como meio de prova. A saber:
inforjabilidade, invio-
labilidade, irrecuperabilidade e irrefutabilidade3. A
inforjabilidade remete conana
do vericador na identicao de autoria, ou seja, na identicao
correta do autor da
assinatura. A conana do vericador na integridade do contedo
expresso no docu-
mento, vinculado manifestao da vontade do signatrio se for o
caso, corresponde
inviolabilidade. A irrecuperabilidade a convico de ambos,
vericador e signatrio,
de que a assinatura lavrada sobre um documento no pode ser
reutilizada em outro
documento, sem permitir deteco da manobra. Por m, a
irrefutabilidade, conceito
tcnico que, no domnio do Direito, ganha o nome de
irretratabilidade: refere-se con-
ana do vericador na inviabilidade tcnica de negao da autoria da
assinatura pelo
1 Conana no pode ser forada (Gerk). Assim, quando um agente
sente-se obrigado a agir como
se conasse noutro, tal situao indica potencial conito de
interesses, modelvel pelas distintas
percepes da extenso da conana que ambos presumem do contexto,
isto , pelas diferenas
entre a conana que um agente presume ser demandada de si pelo
outro, e a oferecida de si
para o outro, relativamente ao assunto em tela e em expectativa
a esse agir (ou ao no-agir).
A denio de Conana aqui adotada foi originalmente proposta por
Edward Gerk no artigo
Toward Real-World models of Trust, disponvel em
http://mcwg.org/mcg-mirror/trustdef.htm
2
-
signatrio4.
A eccia do esquema de assinatura digital decorre, e portanto
depende, de trs
premissas de conana:
1. Somente o titular de um par de chaves criptogrcas assimtricas
pblica e
privada deve controlar o uso de sua chave privada.
2. A titularidade de uma chave pblica, usada para vericar
assinaturas digitais do
titular, ou para cifrar transmisses sigilosas destinadas a este,
deve ser conavel-
mente conhecida pelo vericador ou remetente.
3. O titular manifesta, ou pode manifestar, sua vontade no
contedo de documentos
assinados com sua chave privada.
A terceira premissa requer no s que a interpretao dos formatos
digitais de docu-
mentos assinados seja invariante entre as interfaces
computacionais utilizadas na lavra
da assinatura e na vericao da mesma, mas tambm que os
respectivos ambientes
computacionais estejam sadios, isto , livres de contaminao por
programas maliciosos
capazes de violar a caracterstica wysiwyg5dessas interfaces,
durante tais operaes.
J a segunda premissa conana na titularidade de uma chave pblica
tem sua
demanda atendida, quando esta precisa superar problemas de
escala, por protocolos de
certicao digital, onde as premissas de sigilo e de integridade
(de chaves privadas e
de chaves pblicas, respectivamente) so transformadas em
autenticao recursiva com
2 Na teoria linguistica cognitiva, conforme desenvolvida por
Ronald Langacker por exemplo, a lin-
guagem desempenha uma funo semiolgica, que permite conceituaes a
serem simbolizadas
por ilocues e gestos, associada a uma funo interativa, que
envolve comunicao, manipu-
lao, expressividade e comunho social ([29], pg 14). No caso
especco aqui citado, estamos
nos referindo conceituao de prova de autoria e/ou de manifestao
de vontade, conforme a
acepo doutrinria no Direito, expressa em documento eletronico
que interage com atores atra-
vs de passos expressos por ilocues e gestos de um esquema de
autenticao criptogrca
(assinatura digital como procedimento), onde a autoria e/ou a
manifestao da vontade de um
signatrio simbolizada por componente descrito como autenticador
criptogrco (assinatura
digital como objeto).
3 Aos nveis qualitativos considerados equiparveis ou superiores
aos do mtodo da assinatura de
punho como meio de prova de autoria, ou de eccia probante para
manifestao da vontade, na
jurisprudncia do direito processual.
4 Essa traduo da quarta funo semiolgica (irrefutabilidade ->
irretratabilidade), entre os
domnios tcnico e jurdico, tenta evitar ambiguidade com outro
conceito jurdico, o qual antes
negaria ao acusado o direito de sequer postular sua negao de
autoria.
3
-
validao objetiva (da origem e integridade) de documentos que
titulam e transportam
chaves pblicas, conhecidos como certicados digitais, os quais
podem assim formar
encadeamentos conhecidos pelo ambguo nome de cadeias de
conana6.
Um protocolo de certicao para certicados digitais de chave
pblica regido por
relaes envolvendo entidade certicadora, titulares de pares de
chaves assimtricas,
documentos eletrnicos contendo dados obrigatrios, e usurios
desses documentos. A
integridade e a titularidade de uma chave pblica atestada, em
documento eletrnico
de formato especco conhecido abreviadamente por certicado
digital, mediante va-
lidao completa de uma cadeia de conana (ver nota6) nele
terminada. Para isso,
essencial que o formato desses documentos represente duas
relaes: a primeira, entre
a chave pblica nele contida, e a titularidade do par formado por
esta chave pblica e
sua correspondente chave privada (no contida no certicado), via
identicao deste
titular; e a segunda, entre uma identicao da entidade
certicadora, e uma assina-
tura digital desta no certicado, que nele representa o ato de
sua emisso. Assim, tais
certicados servem no s para identicar o titular de um par de
chaves cuja chave
pblica nele transportada, mas tambm como meio para distribuio
desta chave
pblica.
Mediante a validao completa de uma correspondente cadeia, os
usurios desses
certicados podem ento inferir que a respectiva chave privada
controlada pelo titular
identicado no certicado. Controle este que se presume exclusivo
caso a primeira
premissa de conana esteja valendo para esse titular e chave
privada, mas premissa
esta que nenhum certicado com tal estrutura ter como atestar
(como na metfora
aludida inicialmente).
Dos dados contidos em tais certicados, so portanto obrigatrios
os seguintes:
chave pblica, identicao do titular desta chave, identicao da
entidade que emitiu
5 Acrnimo de what you see is what you get, referente ao
pressuposto de que o que est sendo
processado (a nvel binrio) corresponde elmente ao que est sendo
mostrado na interface de
usurio (na tela ou impressora).
6 Ambguo no sentido em que a conana inspirada por tais cadeias,
a saber, conana na titulari-
dade e integridade das chaves contidas nos certicados
encadeados, decorre no apenas como o
nome pode dar a entender do mero encadeamento, isto , da chave
pblica em cada certicado
na cadeia ser aquela que serve para validar a assinatura no
certicado seguinte (e portanto, para
validar a titularidade da chave transportada neste). Ela tambm
decorre, e portanto depende
tambm, da validao de todas essas assinaturas e, crucialmente,
das trs premissas de conana
estarem valendo para a chave pblica no certicado que inicia tal
cadeia, conhecido por isso como
certicado-raiz.
4
-
o certicado, e assinatura digital desta no certicado. E dentre
os dados teis, porm
no obrigatrios em formatos-padro como o X.509 [19], podemos
citar os que informam
sobre o uso que o titular pretende para este seu par de chaves
(no subcampo userNotice
do campo policyQualifyer da extenso certicatePolicies), sobre
possvel revogao
antecipada do certicado (na extenso CRLDistributtionPoints),
dentre outros.
1.2 A equivalncia entre fsico e virtual
No Brasil, com a assinatura (de punho) da Medida Provisria 2200
pelo Presidente
da Repblica em junho de 2001, eventualmente reeditada em verso
atualmente vigente
a MP 2200-2 , foi instituda a Infraestrutura de Chaves Pblicas
Brasileira (ICP-
BR), regime normativo tcnico-jurdico ao qual se refere o
primeiro pargrafo desta
Introduo. Dentre seus dispositivos vigentes, o regime da ICP-BR
estabelece que
as cadeias de conana sob seu escopo jurdico devem seguir o padro
X.509 com
hierarquia nica, no sentido de que qualquer certicado
autoreferenciado7 que seja
raiz ltima (ver nota6) para tais cadeias, deva ter como titular
uma nica entidade,
nomeada Autoridade Certicadora Raiz da ICP-BR [22]. Conforme o
mesmo regime,
tal entidade primria operada pelo Instituto Nacional de
Tecnologia da Informao
(ITI), que tambm responsvel pelo credenciamento e
descredenciamento das demais
certicadoras participantes (cujos certicados podem compor
cadeias na ICP-BR), pela
superviso das operaes destas, e pela auditoria de processos
pertinentes.
Tendo j explicado como uma cadeia de certicados operada no
processo de vali-
dao destes6, resta explicar como formada no processo de emisso.
A Certicadora
Raiz, que tambm chamada primria, responsvel pela emisso dos
certicados
das entidades certicadoras cujos certicados ocupam posio
imediatamente inferior
nessas cadeias de conana, e assim por diante. As certicadoras no
primrias, tam-
bm chamadas intermedirias, tm a responsabilidade de emitir,
distribuir, renovar,
revogar e gerenciar certicados digitais de certicadoras em posio
abaixo da sua, ou
de clientes nais. Cabe observar que o padro X.509 estabelece uma
espcie de reserva
de mercado para certicao, no sentido em que os certicados de
clientes nais devem
car, nas aplicaes aderentes ao padro, desabilitados a vericar
assinaturas em outros
certicados X.509 (habilitados, portanto, a vericar assinaturas
apenas em documen-
tos que no sejam certicados X.509), e os de certicadoras no
primrias, passveis
7 Frequentemente chamados de autoassinados, termo ainda mais
perigosamente ambguo por dar
a entender que so capazes de atestar sua prpria integridade.
5
-
de limites para a posio que possam ocupar em cadeias de conana
(atravs da
extenso CerticateBasicConstraints)
Ainda, para cuidar da coleta e validao de dados de entrada para
certicados
de clientes nais, dados que iro identicar tais clientes como
titulares das respecti-
vas chaves, ou coletar dados para pedidos de revogao antecipada
de certicados j
emitidos e ainda vlidos, e validao de tais pedidos quanto a
legitimidade, o regime
normativo da ICP-BR estabelece tambm as chamadas autoridades de
registro, que
interfaceiam com as certicadoras intermedirias para tal
nalidade. As autoridades
de registro devem, ou deveriam, tambm operar sob credenciamento
e superviso da
entidade primria da ICP-BR, ou seja, da Certicadora Raiz operada
pelo ITI em sua
capacidade scalizatria.
1.3 O problema jurdico da funo semiolgica
Aps essa breve introduo aos protocolos de certicao como
instrumentos de
suporte distribuio e gesto de chaves pblicas, estamos aptos a
descrever o pro-
blema que ser abordado neste trabalho. Tal problema surge na
relao entre a funo
semiolgica de irrefutabilidade (no domnio jurdico,
irretratabilidade) de assinaturas
digitais, e o seu fundamento terico, que inviabilidade tcnica de
se obter, com custo
cabvel, a chave privada a partir da correspondente chave pblica.
No domnio tcnico,
essa inviabilidade que podemos chamar de premissa de assimetria
a caracterstica
que classica o correspondente algoritmo criptogrco como
assimtrico, caso ela seja
infervel para qualquer par de chaves til ao algoritmo.
Para oferecer garantias dessa inviabilidade, ou seja, garantias
de que qualquer chave
pblica certicada possui tal caracterstica (de assimetria),
garantias estas que o escopo
jurdico da ICP-BR decreta sucientes, para o Direito Civil, pelo
disposto no 2o do art.
10o da MP 2200-2, o regime da ICPBR estabelece normas
adicionais, de cunho tcnico
correspondente, com diversas especicaes e parmetros para
algoritmos, como por
exemplo o RSA (que se tornou padro de fato), softwares e
hardwares homologveis,
tanto para gerao como para uso de pares de chaves sob tal
regime.
O problema peculiar ICP-BR, quando comparada a outras
iniciativas do gnero8
, surge da citada presuno de sucincia jurdica, insculpida no 2o,
Art. 10o da MP
2200-2[17]. Se um agente oportunista puder gerar, com custo
cabvel, a chave privada
correspondente a uma chave pblica a partir desta, o titular
deste par de chaves estar
6
-
exposto a srios riscos e problemas de carter jurdico, de difcil
soluo no mbito da
ICP-BR. Ento, para que a implcita hiptese de eccia dessas regras
e padres tenha
real valor, necessrio que se analise:
num primeiro crivo, os mtodos conhecidos para se obter chaves
privadas a partirda correspondente chave pblica;
num segundo crivo, em mais detalhes, aqueles cuja viabilidade
tcnica possa sermensurada por meios empricos, com distintas
distribuies de probabilidade;
E num terceiro crivo, avaliar se dentre estes existe algum mtodo
cuja viabilidade,mensurada em algum sentido prtico e sob condies
realistas, ponha em cheque
a base terica para tal presuno de sucincia jurdica, sob algum
princpio juris
doutrinrio.
A hiptese de existncia de um tal mtodo, e se ele poderia ser
usado para robustecer
ao invs de vulnerar o arcabouo tcnico-jurdico da ICP-BR, aqui
tematizada
como problema a ser abordado nesse trabalho.
1.4 O teste de Lenstra
No caso do algoritmo-padro RSA [3], podemos reduzir a vericao
dessa hiptese,
aqui tematizada, ao exame dos mtodos conhecidos para se
encontrar os fatores do
mdulo de um par de chaves que no caso geral (de mdulos
regulares) so dois
nmeros primos a partir da chave pblica do par. No primeiro
crivo, os mtodos
diretos mais ecientes dentre os atualmente conhecidos como o de
fatorao pelo
algoritmo NFS [31], que tem complexidade exponencial na ordem da
raiz cbica do
mdulo , so os que tem sido usados para balizar parmetros tcnicos
referentes
gerao de chaves, em estudos como o de Loebenberger [32] e em
normas tcnicas
como as da ICP-BR aludidas acima.
Porm, a partir de 2012 surgiram novos mtodos alternativos,
indiretos e potenci-
almente mais ecientes que os diretos, candidatos ao segundo
crivo. Esses mtodos se
tornaram pblicos quando Arjen Lenstra e co-autores os
propuseram, em um artigo
8 Iniciativas de amalgamar regimes tcnico (administrativo) e
jurdico (algum ramo do Direito vi-
gente) objetivando ordenar a virtualizao de prticas sociais que
possam fazer uso de criptograa
assimtrica, em um regime integrado que geralmente se designa por
ICP (ou a correspondente
sigla em ingls, PKI Public Key Infrastructure)
7
-
cientco publicado em fevereiro daquele ano. O contedo desse
artigo foi intensamente
debatido, entre autores e interessados, num dos principais
congressos cientcos sobre
Criptograa, dois meses depois9. Tais mtodos empregam tcnicas
estatsticas para
testes empricos, que na prova de conceito daquele artigo
expuseram fragilidades em
um dos pilares da terceira premissa de conana da assinatura
digital: a saber, o de
que os componentes que geram chaves devem estar sadios.
Essas tcnicas assim aplicadas buscam medir a entropia mdia de
geradores de
chaves numa amostra de chaves pblicas adequadamente
dimensionada, colhida dentre
as que j foram distribudas para uso. No caso de chaves RSA, por
meio de um
clculo exaustivo porm relativamente simples: o do mximo divisor
comum (MDC)
entre mdulos da amostra. Caso esse teste encontre ndice de
colises, na forma de
ocorrncias de primo comum a mais de um mdulo, signicativamente
maior que ndices
esperados [31], ou seja, teoricamente estimados pela mxima
entropia dos geradores, ou
noutras palavras, estimados pela premissa de que os primos
selecionados para compor
cada mdulo devam ser gerados aleatoriamente10, um tal resultado
pe em dvida a
validade da terceira premissa de conana nos ambientes de origem
da amostra testada.
A prova de conceito desta tcnica, publicada por Lenstra et. al.
em 2012, encontrou
ndices de colises de primos muitas ordens de grandeza maior que
os ndices espera-
dos11, mas ela tinha duas srias limitaes. A primeira, no fato
das caractersticas
da amostra utilizada terem sido minimamente divulgadas,
dicultando a anlise das
possveis causas para os ndices de colises encontrados terem sido
inesperadamente
to altos. E a segunda, no custo computacional desconhecido,
concentrado no algo-
ritmo para clculo dos MDCs, onde a tcnica mais simples conhecida
de varredura
dos possveis pares de mdulos na amostra para clculo direto entre
dois mdulos
tem complexidade quadrtica, o que inviabilizaria (devido ao
custo computacional ex-
cessivo para se encontrar colises) essa tcnica como base para
mtodos replicveis e
escalveis, portanto, qualicveis ao terceiro crivo da hiptese
tematizada.
9 RSA Conference 2012, conforme noticiado em
https://www.networkworld.com/article/
2186408/security/alleged-rsa-crypto-flaw-hotly-debated.html
10 Mais precisamente, de forma pseudo-aleatria (por se tratar de
evento em ambiente computacional
determinstico), o que equivale a dizer, com entropia mensurvel
mxima.
11 Na amostra inicialmente coletada, com 6.6 milhes de
certicados X.509 e chaves PGP contendo
mdulos RSA, mais de 270 mil (4,3%) compartilhavam mdulos,
possivelmente entre distintos
titulares, vulnerveis assim a ataques de personicao. Dos 12.934
que puderam ser fatorados
por terem primo comum com algum outro mdulo, afetando 21419
certicados ou chaves PGP,
727 eram de chaves oriundas de cercados-raiz.
8
https://www.networkworld.com/article/2186408/security/alleged-rsa-crypto-flaw-hotly-debated.htmlhttps://www.networkworld.com/article/2186408/security/alleged-rsa-crypto-flaw-hotly-debated.html
-
Porm, ainda em 2012, Ilya Mironov, pesquisador da empresa
Microsoft, aplicando
o mtodo indireto inaugurado por Lenstra, publicou no seu blog
Windows in Theory
um relatrio em duas partes descrevendo estudo similar, sobre
fatorao de mdulos,
que ele havia conduzido com seus colaboradores [35]. Esse
relatrio analisa com mais
profundidade a amostra testada em seu estudo, bem como as
possveis causas dos
altos ndices de colises tambm encontrados. E descreve o
estado-da-arte para clculo
de MDCs de uma quantidade qualquer de mdulos (entre os quais os
fatores comuns
devem ser raros), baseado em resultados anteriores de D Stehl
& P. Zimmerman, T.
Jebelean e D. Bernstein [20], o qual teria sido usado para os
testes nesse estudo.
E nalmente, seis meses depois, Alex Halderman, um dos mais
importantes e desta-
cados pesquisadores em segurana computacional em atividade,
junto com co-autores,
publicou um artigo [27] descrevendo outro estudo similar, onde o
algoritmo eciente
para clculo de MDCs descrito por Mironov implementado, e como
esse algoritmo
pode compor testes que detectam colises de primos comuns entre
mdulos na amostra.
A amostra de Halderman, que parece ser a maior at hoje j testada
(com cerca de 24
milhes de chaves), foi coletada com ajuda de um crawler na
Internet, onde foram en-
contrados ndices de colises de primos tambm muito acima do
esperado, equivalentes
aos encontrados no estudo pioneiro de Lenstra e no segundo
estudo de Mironov.
Cabe aqui ressaltar o detalhe que distingue o trabalho de
Halderman dos dois ante-
riores, que tambm empregam mtodos indiretos ecazes para se obter
chaves privadas
de chaves pblicas. Em um dos Apndices do seu artigo, Halderman
publicou, com
licena livre, o cdigo fonte do algoritmo FastGCD, de
complexidade quasilinear12,
usado para calculo de MDCs entre mdulos RSA amostrados para os
testes em seu
estudo. Com isso, os mtodos indiretos para se testar a premissa
de assimetria em
pares de chaves13 baseados na tcnica proposta por Lenstra,
nalmente atingiram n-
vel de qualicao ao terceiro crivo (descrito no m da seo 1.3) da
hiptese aqui
tematizada, como pretendemos mostrar ao longo deste
trabalho.
12 Ordem de complexidade temporal
O(n(log10n)2log10log10n)[14]
13 Premissa de inviabilidade, com custo cabvel, para se obter a
chave privada a partir da corres-
pondente chave pblica
9
-
1.5 A possibilidade realista de violao da primeira
premissa de conana
Comeando pela seguinte observao: com a soluo eciente para teste
de coliso
de primos disponibilizada por Halderman, atingimos um limiar
indito, na possibilidade
estatisticamente signicativa (para encontrar colises), pois
proporcional inclusive em
custo computacional ao tamanho da amostra, de violao da primeira
premissa de
conana para assinaturas digitais. Possibilidade realista, ante
os ndices encontrados
em testes j publicados14, e violao que se propaga s demais
premissas: a primeira
premissa falha a partir do momento em que um agente A consegue
gerar a chave pri-
vada de um agente B, quando ento o controle de B sobre sua chave
privada deixa de
ser exclusivo. Como B no tem mais controle exclusivo sobre sua
chave privada, no
possvel conar na titularidade de sua chave pblica, assim como no
se pode presu-
mir que B manifesta ou pode manifestar sua vontade no contedo de
um documento
assinado com sua chave privada. Tudo isso sem que B que sabendo,
se a inteno de
A for de fraud-lo ou prejudic-lo, com o desao do nus da prova
pendurado em B
pela corrente jurdica do 2o do art. 10o da MP 2200-2[17].
Como parte desse trabalho, implementamos uma ferramenta de
teste, por mtodo
indireto, baseada no FastGCD de Halderman, com a qual
pretendamos testar amostras
de chaves pblicas coletadas de certicados digitais emitidos sob
o escopo jurdico da
ICP-BR, para avaliar se esto ou no expostas mesma
vulnerabilidade encontrada nos
trs estudos j citados, em forma de ndice de colises de primos
inesperadamente alto.
Aps implementada a ferramenta, ela foi submetida a uma fase
preparatria, em que
rodamos um teste preliminar, destinado a avaliar os limites
prticos da implementao
no ambiente em que foi instalada, e a coletar dados sobre sua
performance nesse ambi-
ente. Esse teste preliminar foi executado sobre a maior amostra
de chaves pblicas que
pudemos coletar, contendo as chaves pblicas RSA encontradas em
um repositrio de
certicados X.509 disponibilizado pelo projeto SSL Obervatory15
da ONG Electronic
Frontier Foundation (EFF).
Nesse teste preliminar, foi tambm encontrado ndice de colises de
primos inespe-
radamente alto, tambm equivalente aos encontrados nos testes
publicados por Halder-
man, Mironov e Lenstra. O que contribui para sustentar a hiptese
de vulnerabilidade
14 ndices que variam entre aproximadamente 0.5 e 1.2% de mdulos
fatorveis, em amostras que
vo de 6 a 24 milhes de chaves RSA, em 3 estudos publicados antes
deste.
15 https://www.eff.org/observatory
10
https://www.eff.org/observatory
-
generalizada no uso do RSA em larga escala , de causa ainda
especulativa, manifesta
em termos de ndices de colises de primos inesperadamente altos e
semelhantes em
amostragens independentes.
Podemos supor que nossa amostra ao menos parcialmente
independente das de
Halderman e de Lenstra pois as chaves pblicas que coletamos
estavam em certicados
quase todos j expirados ao tempo em que o repositrio da EFF foi
acessado, com data
de gravao anterior da coleta de certicados pelo crawler de ambos
(em 2012), os
quais coletaram certicados que via de regra ainda eram vlidos
estando em uso na
web. Dados colhidos com a execuo desse teste preliminar,
inclusive sobre limites do
ambiente em que a ferramenta foi instalada, e sobre sua
performance nesse ambiente
durante a execuo desse teste, esto registrados em captulos
nais.
1.6 Motivao e caminho percorrido
A inteno inicial com este projeto era a de executar testes, ou
disponibilizar a
ferramenta para testes, com amostras do repositrio das chaves
pblicas de certicados
j emitidos sob o regime da ICP-BR. Em 2015 o repositrio completo
seria, em tese16,
duas vezes maior que a amostra utilizada na fase preparatria, e
trs vezes menor do
que a amostra testada por Halderman. Porm, no logramos xito em
vrias tentativas
de obter acesso, seja ao repositrio da ICP-BR, ou mesmo a uma
parte signicativa
dele, seja ao efetivo custodiante desse repositrio, apesar do
que determina o Art. 5
da MP 2200-217.
A estratgia de coleta de uma parte signicativa desse repositrio
por crawling na
Internet no funcionaria para este caso porque a grande maioria
dos certicados gerados
no regime da ICP-BR se destinam a assinatura digital de
documentos, e no a servios
on-line (como por exemplo, via SSL), e portanto, a grande
maioria desses certicados
no precisa car, e por isso no se encontra, on-line. Por uma
leitura tcnica do conceito
de gesto referida nesse Art. 5, dispositivo que est em uma norma
legal equiparvel
a Lei federal, a responsabilidade pela gerncia de todos os
certicados emitidos sob o
11
-
regime da ICP-BR, caberia sua Certicadora Raiz, incorporada pelo
ITI.
Os termos em que foram dirigidas propostas ao ITI, seja para
disponibilizao do
repositrio visando a execuo de testes no ambiente em que foi
implementada a ferra-
menta, seja para disponibilizao da mesma visando execuo de
testes em ambiente
controlado pelo custodiante do repositrio, buscando encontrar
uma forma em que a
modalidade acordada para testes pudesse ser empregada, junto com
providncias ca-
bveis, para robustecer, ao invs de vulnerar, o arcabouo
tcnico-jurdico da ICP-BR
por exemplo, com revogao por motivos tcnicos dos certicados que
colidirem
durante testes , esto tambm aqui registrados, em cpias de
documentos includas
como anexos.
Em consequncia desta indisponibilidade, numa situao em que
sequer tivemos
resposta do custodiante legal, nem mesmo para informar se o
repositrio dos certicados
da ICP-BR existe ou no, adaptamos a ferramenta para testes
individuais com qualquer
chave pblica RSA, contra a amostra de mdulos contida no
repositrio que foi nela
integrado, e inicializado com os mdulos das chaves
disponibilizadas no repositrio da
EFF em certicados j expirados. A ferramenta permite a opo de
prova dos nove,
de deduo da correspondente chave privada se o mdulo da chave
pblica testada
apresentar coliso com algum mdulo do repositrio.
16 Nmero aproximado de certicados ento j emitidos, conforme o
diretor da Associao de Au-
toridades de Registro da ICP-BR, Nivaldo Cleto. A declarao
citada est disponvel no vdeo
https://www.youtube.com/watch?v=L-TWnc2zvBc , no tempo 28:50, do
painel: Privacidade,
Segurana, Criptograa e Identidade digital - Tendncias , no Frum
de Privacidade do CGI-BR,
em 2016.
17 Descrita na seo 7.2 e analisada nas consideraes nais
12
https://www.youtube.com/watch?v=L-TWnc2zvBc
-
Captulo 2
Raiz do Problema
2.1 Identicando a raiz do problema
Neste captulo, vamos averiguar a natureza de uma das
vulnerabilidades expostas
nos trs estudos citados, representada por ndice inesperadamente
alto de colises de
primos entre mdulos RSA, com diagnstico mais plausvel de causa
na insucincia
de entropia para o processo de gerao de chaves em ambientes de
origem da amostra.
Tal suspeita principal foi dissecada num desses estudos, o de
Mironov, enquanto com
Halderman, tais estudos se tornaram replicveis e escalveis, a
partir da livre disponi-
bilizao do algoritmo quasilinear implementado para teste de
colises de primos entre
mdulos, validando assim tambm a hiptese tematizada nessa
monograa, onde tal
vulnerabilidade ganha status de problema para protocolos de
certicao digital. Pro-
blema tcnico de segurana, pois no cenrio atual esses protocolos
vm sendo usados,
em larga escala, com chaves RSA.
J no domnio jurdico, o risco decorrente dessa vulnerabilidade
(ou de seu corres-
pondente problema de segurana) o de falha nas premissas de
conana para uso de
chaves criptogrcas certicadas. Risco que passa a ser bem maior
que o teoricamente
estimvel por avaliaes isoladas, mediante a existncia de
procedimento computaci-
onal violador replicvel e de eccia escalvel, que ultrapassa em
muitas ordens de
grandeza essas estimativas, tornando-as irreais. Mais
precisamente, mediante tcnica
indireta de se fatorar o mdulo de uma chave pblica calculando-se
MDCs entre m-
dulos, para da derivar a chave privada correspondente, caso o
mdulo desta chave
pblica venha a colidir com outro de uma coleo, agregada seja
para testes, seja para
um tal procedimento visando violao dessas premissas.
13
-
necessrio ento que perguntemos como o mtodo indireto
implementado e vali-
dado nos trs estudos citados foi capaz de expor uma
vulnerabilidade que se transforma
em problema de segurana para protocolos de certicao. Existe uma
grande quan-
tidade de possveis explicaes para a ocorrncia de ndices
inesperadamente altos de
colises de primos nesses estudos, conrmado agora tambm em nosso
teste prelimi-
nar, mas neste captulo abordaremos apenas trs dentre as mais
provveis explicaes,
de natureza tcnica, tomando como principal referncia o estudo
publicado por Miro-
nov [35],
Analisaremos primeiramente a conabilidade do prprio algoritmo
RSA. O tama-
nho dos mdulos utilizados para gerao de chaves para esse
algoritmo pode variar e
essa variao poderia, aparentemente, contribuir para elevar o
ndice de colises numa
amostra que contenha mdulos de tamanhos variados. Em seguida,
ser analisada a
possvel relevncia da variao de tamanho dos intervalos entre
primos consecutivos
entre os nmeros inteiros ordenados. E por m, a questo
relacionada insero de
entropia no processo que seleciona nmeros primos para compor
mdulos, atravs do
uso de geradores pseudorandmicos (PRNGs).
2.1.1 O RSA (isoladamente) robusto?
Pode-se culpar o algoritmo criptogrco RSA em si? Como ser que a
quantidade
de primos gerados para compor mdulos em eventos independentes e
de tamanhos
variados, aumenta a probabilidade de um primo se repetir em
diferentes mdulos, e
portanto, de se envolver em colises? Um mdulo RSA um produto de
primos, via
de regra dois1, os quais neste caso so recomendados serem de
tamanho igual. De
tamanhos iguais, esses dois primos devem ter ento metade do
tamanho do mdulo
RSA. O tamanho do mdulo parmetro independente na gerao de
chaves. Con-
sequentemente, nas amostras coletadas para os estudos citados
aparecem mdulos de
tamanhos variados. Nessas amostras, a grande maioria dos mdulos
tinha entre 1024
bits e 2048 bits, e quase sempre em um desses dois tamanhos2. Ao
passo que, nos
1 Para mdulos ditos regulares. Cabe aqui observar que, dentre os
trs estudos citados, apenas
o estudo pioneiro de Lenstra mencionou a possibilidade de mdulos
no regulares ocorrerem na
amostra, ao notar que eram regulares todos os mdulos aderentes
aos padres para chaves RSA
que foram fatorados mediante coliso (conforme nota de rodap 4 em
[30])
2 No primeiro teste do estudo pioneiro de Lenstra, por exemplo,
73,9% dos mdulos tinham 1024
bits, e 21,7% tinham 2048 (mais de 95% com um desses dois
tamanhos). Ao passo que, dentre
as colises encontradas, a porcentagem representativa foi maior
entre os menores (de 1024 bits).
14
-
testes de coliso, a grande maioria dos mdulos fatorados tinha
1024 bits, com pelo
menos um fator primo de at 512 bits. Avaliando supercialmente,
pode-se imaginar
que mdulos de tamanho pequeno teriam implicao na ocorrncia de
altos ndices de
coliso. Ento, concentremo-nos por enquanto neles.
A densidade de nmeros primos de 512 bits aproximadamente
1/ln(2512) 1/350.O que signica que a probabilidade de se escolher
um nmero primo no intervalo de 1 at
2512 de aproximadamente 0.285% e o nmero total de primos nesse
intervalo maior
do que 2503. Para alcanarmos uma probabilidade de pelo menos 50%
de se observar
uma coliso entre primos escolhidos, de maneira puramente
aleatria, no intervalo
entre 2502 at 2503, seria necessrio (pelo paradoxo do
aniversrio3) a gerao de 2250
nmeros primos, quantidade 1065 vezes maior que a quantidade mdia
envolvida nas
amostras estudadas (1010 mdulos), cujo teste pelo MDC produziu
dezenas de milhares
de colises. Devido a essa quase incomensurvel disparidade,
pode-se concluir no s
que a diferena entre tamanhos de mdulos na amostra, entre 1024 e
2048 bits por
exemplo, irrelevante para a anlise desejada, como tambm possvel
concluir que
colises devidas densidade de nmeros primos no intervalo dos
menores pode ser
ignorada.
2.1.2 Intervalos entre nmeros primos
Examinemos um algoritmo tpico para selecionar nmeros primos:
1. Gerar um nmero mpar randmico r de tamanho t bits;
2. Se r for primo, retorna r e para;
3. r r + 2, volte para o passo 2.
Onde a expresso booleana no passo 2 acima um teste por um mtodo
de Monte-
Carlo4 para detectar nmeros primos, calculando-se nmeros de
Jacobi de uma srie
aleatria entre os resduos do candidato r (como por exemplo, o
teste de Miller-Rabin).
No lao externo do algoritmo acima, os nmeros compostos da
sequncia vo sendo
descartados at que se alcance um que passe no teste de
primalidade.
3 Princpio de contagem combinatria que ganha o nome de um
exemplo simples mas antiintuitivo
de sua aplicao . Vide
https://pt.wikipedia.org/wiki/Paradoxo_do_anivers%C3%A1rio
4 Mtodo para construir uma classe de algoritmos que calculam
probabilidades baseadas em uma
srie de amostragens aleatrias,...([38] Pg. 18)
15
https://pt.wikipedia.org/wiki/Paradoxo_do_anivers%C3%A1rio
-
Considerando os candidatos r aptos a passar no teste por serem
primos, sabemos
que a distribuio desses no uniforme, j que depende no s
(estatisticamente) da
densidade de primos no intervalo delimitado pelo tamanho t
escolhido, mas tambm
da distribuio precisa dos primos nesse intervalo. Assim,
qualquer primo de tamanho
t selecionvel por um algoritmo desse tipo com probabilidade
tambm proporcional
ao tamanho do intervalo que o separa do primo antecessor
(supondo a inicializao de
r puramente aleatria).
Teria essa no uniformidade dos intervalos entre primos algum
efeito signicativo
no ndice de colises de primos entre mdulos, encontrados nos
testes?
Para uma estimativa desse efeito, consideremos o seguinte: Seja
p1, p2, . . . , pm, onde
pm so os primeiros m primos. A probabilidade do i-simo nmero
primo ser escolhido
ser:(pi pi1)
pm.
Chamemos essa distribuio de q. A probabilidade de duas amostras
independentesdessa distribuio colidirem, conforme descrita por
Mironov, dada por:
Pra,bq[a = b] =mi=1
Pra,bq[a = pi].P ra,bq[b = pi] =mi=1
(pi pi1)2
p2m
Dada a probabilidade de uma nica coliso, o nmero esperado de
colises entre n
amostras independentes e puramente aleatrias sobre q (n2
)n2/2 vezes maior (por
aproximao linear). Se os primos estivessem distribudos
uniformemente entre os n-
meros inteiros ordenados, ento a probabilidade de coliso seria
1/m e, para garantir
que a quantidade esperada de colises seja de pelo menos 1, o
nmero de amostras n
deve ter tamanho mnimo de2m (o limite do paradoxo do
aniversrio3). Porm, pri-
mos consecutivos no se encontram uniformemente espaados entre os
nmeros inteiros
ordenados, e intervalos relativamente grandes ocorrem.
O matemtico Atle Selberg provou [18], usando a hiptese de
Riemann [21], a
melhor cota (condicional) superior temporal conhecida para o
calculo da soma
mi=1
(pi pi1)2
pi O(log3 pm)
16
-
o que se traduz no seguinte limite para probabilidade de
coliso:
Pra,bq[a = b] = O(log3 pmpm
) = O(log2m log log3m
m)
visto que:
pm m logm.
O limite de Selberg signica que o efeito de espaamentos
irregulares entre primos
consecutivos pode aumentar assintoticamente por um fator de
ordem
O(log2m log log3m)
comparado ao caso simplicado (de espaamento uniforme entre
primos). Assim, exa-
minando essa quota sublinear, possvel concluir que o espaamento
no uniforme
entre primos consecutivos insuciente para explicar a discrepncia
em vrias ordens
de grandeza entre os ndices encontrados em testes de coliso nas
amostas estudadas,
e os ndices teoricamente estimados com tal simplicao (que
considera intervalos
uniformes entre primos consecutivos).
2.1.3 A raz da vulnerabilidade
Observamos at aqui que a probabilidade de coliso de primos
devida ao tamanho
da amostra de mdulos, ou devida variao nos tamanhos dos mdulos,
ou devida ao
espaamento irregular entre dois primos consecutivos dentre os
inteiros ordenados, no
causa signicativa para o ndice de colises encontrado estar
tantas ordens de grandeza
acima do esperado, quando se considera as caractersticas do RSA
como algoritmo
isolado. Qual seria ento o real motivo para os ndices de coliso
encontrados com
testes de MDC entre mdulos RSA em amostras reais?
Resta ento considerar a terceira hiptese: a saber, a de que os
resultados desses
testes reais, comparados aos ndices de coliso teoricamente
antecipveis, esto indi-
cando baixa entropia na gerao de chaves em ambientes de origem
da amostra. O
que apontaria falhas de projeto ou de implementao, ou erros de
programao, nos
softwares que geram as chaves, e no falha matemtica em
estimativas de ndices espe-
rados ou no algoritmo RSA. Ou seja: uma sutil, porm catastrca,
diferena prtica
real entre o pseudorandmico e o puramente randmico.
Se houver falha sistemtica ou aleatoriedade insuciente na
inicializao da fonte de
17
-
entropia que, na etapa de gerao de chaves, inicia o processo
para seleo dos nmeros
primos que iro compor o mdulo da chave, ento duas chamadas
independentes a essa
fonte podero resultar em outputs com ndice inesperadamente alto
de bits coincidentes,
em cujo caso esses bits de inicializao randmica
(pseudorandomica) em instncias
independentes poderiam propagar coincidncias, e convergi-las
para eventuais colises
ao longo do processo de gerao descrito acima, at a seleo de um
mesmo primo.
18
-
Captulo 3
Um problema ou vrios?
3.1 Anlise dos possveis problemas
A hiptese de existncia de mtodo indireto que pode expor
vulnerabilidades no
arcabouo tcnico-jurdico da ICP-BR foi conrmada pela divulgao dos
trs estudos
estatsticos citados, que utilizam, dentre outros recursos,
algoritmo quasilinear para
fatorao (via MDC) de mdulos de chaves RSA. A parte desses
estudos relativa
vulnerabilidade explorvel por fatorao de mdulos foi validada
neste trabalho, pelo
teste preliminar realizado como etapa preparatria.
Dentro do que propomos nele tematizar, caberia ento, na etapa
seguinte deste
trabalho, analisar como esse mtodo e seus resultados podem ser
utilizados para defesa,
para robustecer ao invs de vulnerar, no s o arcabouo normativo
da ICP-BR, mas
tambm os protocolos de certicao disseminados na Internet, em
ICPs sob outros
regimes normativos.
Com respeito parte validada neste trabalho, se a mais provvel
causa (inicialmente
analisada no captulo anterior) para ndices inesperadamente altos
de colises que
viabilizam ataques probabilsticos por fatorao de mdulos de
chaves pblicas est na
m escolha da fonte de entropia em processos que geram primos
para compor mdulos
de chaves RSA, ento deve ser possvel rastrear e identicar as
bibliotecas ou programas
que implementam cdigo ou especicao contendo falhas. Nessa
tarefa, o primeiro
desao seria localizar um ou mais geradores de primos ruins ou
perigosos no
sentido de suspeitos de conterem implementaes falhas disponveis
no mercado.
Nesse desao, a questo inicial a responder : Seria possvel
identicar geradores
ruins ou perigosos a partir da amostragem, ou seja,
examinando-se apenas as chaves e
19
-
certicados que as transportam para a amostra nos testes
realizados? Sem a colabora-
o ou participao do responsvel legal pela gesto do repositrio de
certicados da
ICP-BR, no foi possvel avanar nas etapas seguintes originalmente
planejadas para
este trabalho. Nem o ser em trabalhos futuros, considerando-se o
perl de uso de
certicados sob o regime da ICP-BR (descrito no segundo pargrafo
da seo 1.6),
e o contexto de indisponibilidade, tanto desse repositrio quanto
da colaborao ou
participao do responsvel legal por ele, at aqui absolutas.
Quanto s demais vulnerabilidades encontrveis pelo mtodo indireto
aqui descrito,
h uma outra, de implicaes jurdicas em regimes como o da ICP-BR
potencialmente
mais graves que as decorrentes do risco de fatorao de mdulos via
MDC, aqui abor-
dada. A saber, a ocorrncia de chaves ou de mdulos1 RSA repetidos
em mais de um
certicado, se os titulares no forem o mesmo. No estudo de
Lenstra, por exemplo,
cerca de 4,3% dos 6.185.228 certicados X.509 amostrados tinham
mdulo ou chave
pblica iguais ao de outro certicado, onde o risco
correspondente2 no pde ser avali-
ado no contexto da amostragem, exigindo cautela e discrio
adicionais no tratamento
e custdia da amostra coletada.
Diante da deliberada e absoluta indisponibilidade, at o momento
de concluso
deste trabalho, de uma amostragem signicativa para testes no
contexto normativo da
ICP-BR, cabe ento restringir esse captulo ao que podemos
alcanar. Encerrando-o
com um resumo abrangente da investigao conduzida em estudos j
citados, relativa
ao desao tcnico posto pela vulnerabilidade aqui abordada. A
saber, o desao de
identicar geradores ruins ou perigosos a partir da amostragem
disponvel. O resumo
abaixo, extrado do estudo de Mironov, til no sentido em que
poderia nos servir
como roteiro ou modelo para o contexto da ICP-BR, ou poder nos
servir em trabalho
futuro, em caso de eventual disponibilidade til.
1 Mdulo e expoente da chave pblica repetidos entre certicados
implica repetio tambm da
respectiva chave privada, em cujo caso o risco para titulares
distintos o de personicao,
se um deles vier a saber desta repetio. Repetio apenas do mdulo
muito improvvel,
pois expoentes de chaves pblicas RSA no costumam variar muito:
nos mais de 6 milhes
de certicados X.509 coletados por Lenstra, por exemplo, 98,49%
usavam o mesmo expoente
(65537), e 99,99% usavam um dentre os nove mais comuns. Se
apenas o mdulo for repetido,
com exponentes para a chave pblica distintos, o risco se reduz a
apenas o de vazamento quando
ambas chaves pblicas forem usadas para cifrar uma mesma
mensagem.
2 O risco quando os titulares de chaves ou mdulos duplicados no
so o mesmo, ou no represen-
tarem a mesma entidade, descrito na nota de rodap anterior.
20
-
3.2 Anlise do perl dos primos em mdulos fatora-
dos
Os mdulos fatorados por Mironov [27] foram classicados em dois
grandes grupos:
o primeiro grupo, tambm detectado por Haldeman3, formado por
mdulos gerados
por dispositivo de hardware fornecido por um nico fabricante;
enquanto o segundo,
formado por mdulos cujos certicados ou fatores primos apresentam
pouco em comum,
em termos de dados que permitiriam identicar diretamente o
gerador. razovel
supor que essas classicaes preliminares podem tambm ter usado
metadados de
conexes, coletados pelo crawler que gerou parte da amostra
utilizada nos estudos
de Lenstra e de Haldeman, cujos correspondentes no existem no
repositrio da EFF
utilizado em nossa etapa preparatria. O estudo de Mironov [35],
que tenta renar sua
classicao preliminar, comea apelidando o grupo menor de Zoo.
Uma bateria de testes realizada por Mironov, descrita em seu
artigo, detectou,
dentre vrias curiosidades, esta: para cada um dos menores primos
mpares q, s um
por cento em mdia dos fatores dos 3046 mdulos no grupo Zoo tem
resduo 1modq.
O padro criptogrco ANSI 9.31 especica primos fortes4 para compor
mdulos RSA,
mas primos fortes so muito onerosos de se encontrar. Ento,
muitas implementaes
permitem que se opte por seleo de primos que atendem
parcialmente essa condio, os
chamados primos seguros5(menos onerosos), ou nenhuma (menos
ainda). A seleo
pseudoaleatria de primos fortes p no impediria uma distribuio
estatstica normal
de fatores q pequenos6 para os p 1, mas a seleo de primos
seguros, sim. Todavia,uma outra caracterstica detectada no grupo
Zoo contraria a observao acima como
explicao: dentre os p que fatoram esses mdulos, a maioria no de
primos seguros.
Ento, o que explica essa quase completa escassez de fatores
primos pequenos para os
p 1 no grupo Zoo?
Mironov identica ento essa escassez quase completa de resduos
1modq (para
q = 3, q = 5, q = 7, etc) entre os fatores dos mdulos no grupo
Zoo como uma
espcie de impresso digital (ngerprint), ou trao especco, do
gerador de primos
implementado em uma determinada biblioteca criptogrca, cuja
utilizao larga-
3 Conforme descrito na seo 3.2 do estudo publicado por
Haldeman.
4 Um primo p dito forte (strong) se p 1 e p + 1 tiverem ambos
pelo menos um fator primogrande.
5 Um primo p dito seguro (safe) se p = 2q + 1 onde q tambm
primo.
6 Ou seja, que p tenha resduo 1modq para q = 3, q = 5, q = 7,
etc.
21
-
mente disseminada entre aplicaes que fazem uso do algoritmo RSA
na Internet. E
explica, conforme a seo abaixo.
3.2.1 Gerao de primos na biblioteca OpenSSL
Para analisar o procedimento que estaria produzindo esse trao
especco ao gerar
primos, implementado na biblioteca identicada por Mironov como
principal suspeita
pelas colises no grupo Zoo, replicamos dois pseudocdigos que ele
inclui para sua
anlise. O primeiro pseudocdigo, ele arma corresponder a um
algoritmo perfeita-
mente razovel para selecionar primos classicados como seguros,
no qual lhe parece
estar baseado o segundo, que codica o supracitado procedimento
na respectiva bibli-
oteca do OpenSSL.
1. Gerar um nmero randmico r de tamanho n (bits);
2. enquanto r ou (r 1) so divisveis por qualquer p2 p2048;
3. r r + 2;
4. usar o teste de Miller-Rabin [36] para checar se (r 1)/2
primo,seno v para o passo 1;
5. usar o teste de Miller-Rabin para checar se r primo, seno v
para
o passo 1;
6. retorna r como output (primo).
(obs.: a biblioteca OpenSSL contm uma tabela embutida em seu
cdigo com os pri-
meiros 2048 nmeros primos, referidos aqui por p1 p2048)
3.2.2 Gerao de primos no necessariamente seguros na bibli-
oteca OpenSSL
Para mdulos RSA que no necessitam de primos classicados como
seguros, a
biblioteca OpenSSL aplica o seguinte procedimento para gerar um
nmero primo:
1. Gerar um nmero randmico r de tamanho n bits;
2. enquanto r ou (r 1) forem divisveis por qualquer p2 p2048
;
22
-
3. r r + 2;
4. usar o teste de Miller-Rabin para checar se r primo, seno ir
para
o passo 1;
5. retorna r como output (primo).
Mironov salienta que, neste procedimento, apenas teria sido
retirado o terceiro
passo do algoritmo anterior. O segundo passo se manteve
inalterado7 (apesar de apa-
rente falta de justicativa aqui), o que explica a distribuio
peculiar de fatores primos
dos mdulos no grupo Zoo, para os quais so rarssimas as
ocorrncias de resduos
1mod3, 1mod5, , 1mod17863, mas onde os primos ditos seguros so
minoria. Outrodetalhe destacado por Mironov como importante, o de
que a seleo peculiar de pri-
mos com essa propriedade no representa vulnerabilidade para a
respectiva biblioteca,
apenas uma espcie de trao caracterstico, originado pelo cdigo
especco que dela
gera tais primos.
Explicando: um primo qualquer de 512 bits ter essa propriedade
com probabili-
dade dada por2048i=2
pi 1pm
7, 5% [35] no caso de primos de 512 bits. Isso quer dizer
que o procedimento utilizado para gerar primos no
necessariamente seguros na biblio-
teca OpenSSL computa funo simblica de contradomnio menor do que
a coleo de
primos que poderiam ser selecionados sem o crivo dessa
propriedade. Reduzido, por
exemplo, para 7,5% com primos de 512 bits. Todavia, essa reduo
dos selecionveis
no suciente para causar, sozinha, aumento sensvel na
probabilidade de colises8.
Nem para facilitar, heuristicamente, a fatorao de mdulos RSA com
um algoritmo
especial, que seria efetivo apenas para uma parcela irrisria de
mdulos9.
Assim, esse trao caracterstico, originado no segundo passo do
pseudocdigo refe-
rente ao procedimento para gerar primos no necessariamente
seguros que se encontra
na respectiva biblioteca do OpenSSL, levou Mironov a concluir,
com alto grau de cer-
teza, que 96,72% dos mdulos no grupo Zoo de sua amostra foram
gerados por esta
biblioteca. Concluso que, apesar de derivada de um raciocnio
probabilstico, no
pode ser estendida aos demais mdulos que colidiram na sua
amostra.
7 Nessa observao, precedida da adjetivao perfeitamente razovel
ao apresentar o pseudocdigo
anterior, Mironov d a entender (mas sem explicar) que considera
o segundo passo justicado no
primeiro algoritmo, talvez por razes de performance, mas no no
segundo procedimento.
8 Tendo em vista as probabilidades calculadas na primeira subseo
do captulo anterior.
9 Por exemplo, para 0.05625% dos mdulos de 1024 bits.
23
-
Mironov descarta tambm a mesma origem para os mdulos no primeiro
grupo,
identicado como oriundo de um nico produtor de hardware. Assim
como Haldeman,
em sua publicao Mironov no revela a identidade desse produtor.
Apenas arma
que, pelas evidncias encontradas, ele pde concluir que o
software utilizado para gerar
primos so de natureza distinta nos dois grupos. E conclui
apontando um grande
vilo, responsvel no segundo grupo por essa vulnerabilidade
exposta com o mtodo
indireto inaugurado por Lenstra: a existncia de dispositivos (e
sistemas) que falham
na inicializao adequada de geradores pseudorandmicos.
Voltamos agora um passo, ao desao sendo abordado nesse captulo,
que o de
rastrear e identicar bibliotecas ou programas que implementam
cdigo ou especica-
o contendo falhas capazes de explicar ndices inesperadamente
altos de colises de
primos entre mdulos amostrados. Podemos reetir sobre o que
encontramos, resu-
mido acima, nos trs estudos citados. O estudo pioneiro optou por
relegar tal desao
ou no divulgar detalhes10, enquanto os outros dois descrevem uma
classicao pre-
liminar, onde os mdulos fatorados se dividem em dois grupos, com
o grupo maior
rastrevel a um nico fornecedor de dispositivo de hardware. Este
fornecedor teria sido
noticado a respeito, mas sua identicao no divulgada. E um desses
dois estudos,
publicado no blog Windows on theory em maio de 2012, rastreia o
grupo menor, por
um trao caracterstico comum entre os primos encontrados nas
respectivas fatoraes,
identicando a origem de quase todos biblioteca que gera chaves
RSA no software
OpenSSL.
Esse rastreamento do grupo menor termina ento com uma anlise
sobre a natureza
da falha encontrada na biblioteca identicada. Seria uma falha de
implementao, e no
de especicao do software, apesar da peculiaridade dessa
especicao (que permitiiu
o rastreamento), em evitar fatores pequenos nos antecessores dos
primos selecionveis,
reduzindo assim o escopo para seleo de primos. Com tal falha
classicada como
de implementao, e no de especicao, o rastreamento da causa de
ndices inespe-
radamente altos de colises de primos entre mdulos amostrados
prossegue. Agora,
nos contextos onde tal biblioteca empregada, ou seja, nos
ambientes computacio-
nais em que ela integrada e inicializada para gerar chaves RSA,
em aplicaes que
disponibilizam ou utilizam as correspondentes chaves pblicas
(amostrveis) on-line.
10 Conforme se depreende da nota de rodap 7 em Lenstra[30]
24
-
3.3 Onde e quando o OpenSSL utiliza geradores pseu-
dorandmicos com baixa entropia?
No mesmo estudo, o investigador comenta a prtica comum de
dispositivos gerarem
certicados de chave pblica como parte da sequncia de
inicializao. De fato, e no
s: tambm aplicaes que rodam em background, os geram durante a
sequncia de
boot do sistema onde foram instaladas, quando inicializadas pela
primeira vez. Nesses
casos, a menos que o gerador pseudorandmico utilizado para
alimentar a gerao de
chaves receba uma semente inicializadora de uma fonte de
entropia suciente, o seu
output ser previsvel, de escopo inadequado ou xo. Em que situaes
isso ocorre?
Assunto para o captulo seguinte, onde prosseguiremos com essa
anlise, exami-
nando geradores pseudorandomicos que podem ser livremente
analisados. Especica-
mente, os geradores pseudorandomicos especicados na arquitetura
POSIX que so
nativos nos sistemas operacionais mais difundidos do mesmo
regime de produo de
software onde nasce o OpenSSL, que o de desenvolvimento
colaborativo e licenci-
amento permissivo (FOSS). Antes, porm, oferecemos uma reexo
sobre essa trilha
investigativa, no contexto deste captulo e do prximo.
Para rastrear com sucesso o trao caracterstico encontrado em
fatores primos no
grupo menor de sua amostra de mdulos com colises, e mais
importante, para publicar
sem reservas o que quisesse sobre sua investigao bem sucedida
com tal grupo, Mironov
precisou contar com um recurso essencial. A saber, a
disponibilidade irrestrita do
cdigo fonte de uma potencial suspeita. E para seu sucesso,
inclusive em convencer-nos,
ele contou com o fato da sua principal suspeita disp-lo: uma
biblioteca criptogrca
amplamente difudida, produzida e distribuda com licena
livre.
Mas quanto ao grupo maior? De origem identicada presumivelmente
com bem
mais facilidade a um nico fornecedor, sobre o qual nada nos dado
saber? Nem sobre
sua identidade, nem da sua reao postura tica dos investigadores,
que optaram por
responsible disclosure11? E para o nosso sucesso, em aprender
como as ICPs devem
evoluir aps expostas a novas vulnerabilidades com o mtodo
indireto, nem que seja
por nossas escolhas? Nada. Assim como acerca da monopolista
ICP-BR, at aqui,
nada. Problema tambm, mas este, de causa em conito de interesses
no jogo de poder
11 Modelo para priorizar critrios relativos divulgao de
vulnerabilidades descobertas em
softwares e produtos computacionais: ver
https://en.wikipedia.org/wiki/Responsible_
disclosure
25
https://en.wikipedia.org/wiki/Responsible_disclosurehttps://en.wikipedia.org/wiki/Responsible_disclosure
-
que se sobrepe a questes tcnicas. Problema grave, pois conana na
acepo aqui
denida no pode ser imposta, seja por poder legislativo, nanceiro
ou blico.
Ao encerrar este captulo com tal reexo, a inteno permitir-nos
interpretaes
construtivas para o contexto tematizado neste trabalho. O regime
de licenciamento
permissivo, que essencial trilha investigativa a ser prosseguida
no captulo prximo,
permite no apenas uso e redistribuio do software licenciado, mas
tambm seu es-
tudo, tambm para modicaes e adaptaes, recompilaes e testes
realistas com
o correspondente cdigo fonte. Inclusive contribuies de correes
ao mantenedor, e
redistribuies de variantes, onde todos podem aprender com a
descoberta de erros e
tentativas de corrigir falhas. Prerrogativas vedadas nos
produtos, ofuscados por design,
e aos clientes da empresa para quem trabalha o desbravador dessa
trilha aqui (Mironov
trabalha para a Microsoft). Sigamos ento, na trilha do
aprendizado (tcnico) possvel.
26
-
Captulo 4
Geradores Pseudorandomicos no
Kernel LINUX
Nmeros e sequncias binrias com propriedades mensurveis de
aleatoriedade de-
sempenham um papel crtico e importante na criptograa
computacional moderna.
Algoritmos como One-Time-Pad, DES, RC4, RSA etc, e protocolos
como os das crip-
tomoedas1, tm sua robustez diretamente relacionada com a
implementao adequada
dos geradores de nmeros com tais propriedades [28].
Qualquer denio formal de aleatoriedade, porm, corre o risco de
ser entendida
como paradoxal2, razo pela qual as que se pretendem srias
costumam ser dadas em
discursos ou contextos loscos. Para a Computao, que opera com
circuitos eletr-
nicos e dispositivos programveis via de regra determinsticos,
mas onde o conceito
inevitvel e se torna cada vez mais importante, a sada trabalhar
com uma noo me-
nos ambiciosa de aleatoriedade, restrita s suas propriedades
diretamente mensurveis.
Renunciando-se, por exemplo, tentativa de se cercar ou buscar
garantir propriedades
imensurveis ou de mensurao imprecisa, como a irreprodutibilidade
por exemplo.
Circuitos ou dispositivos programveis concebidos para gerar
sequncias binrias
com propriedades diretamente mensurveis de aleatoriedade so por
isso chamados de
geradores de sequncias pseudoaleatrias, ou mais frequentemente,
geradores de nme-
ros pseudorandmicos, ou abreviadamente, geradores
pseudorandmicos, comumente
designados pelo correspondente acrnimo em ingls: PRNGs.
1 Essenciais na implementao de conceitos fundamentais, como por
exemplo o de Proof of Work
2 Como denir um padro para a propriedade de no se seguir nenhum
padro?
27
-
O objetivo deste captulo prosseguir na trilha investigativa
resumida ao nal do
captulo anterior, explorando os geradores pseudorandmicos
padronizados na arquite-
tura POSIX3, disponibilizados em verses de ncleos de sistemas
operacionais como o
desenvolvido e mantido pela fundao Linux. Especicamente, vamos
analisar as fun-
es random e urandom do kernel Linux, em busca de suas
fragilidades operacionais.
4.1 Propriedades de um gerador pseudorandmico se-
guro
Uma lista das caractersticas externas de um gerador
pseudorandomico ideal pode
ser encontrada, por exemplo, em[10]:
1. Um adversrio que descubra o estado atual do gerador no pode
aprender nada
sobre as sadas geradas previamente.
2. Um adversrio que descubra o estado atual do gerador no pode
aprender nada
sobre as sadas futuras desse gerador.
3. Um gerador inicializado com os mesmos tipos de entrada j
utilizadas em al-
gum momento, deve produzir uma sequncia de bits sem qualquer
relao com a
sequncia produzida anteriormente.
4.1.1 Estrutura dos PRNGs random e urandom no Linux
A estrutura dos geradores PRNG no Linux formada por trs
processos assncronos[26].
No primeiro processo, o sistema operacional coleta dados
variados de eventos no kernel.
O segundo processo denido pela alimentao do repositrio de
entropia (reposit-
rio primrio), utilizando uma funo de mistura. O terceiro
processo ocorre quando
bits em ordem aleatria so solicitados. Nesse processo o output
gerado, seguido da
atualizao do repositrio primrio. A gura 4.1 descreve o uxo de
bytes no gerador
pseudorandmico.
A coleta de entropia subproduto dos eventos originados no kernel
pelo teclado,
pelo mouse, por interrupes do sistema e por acessos ao disco.
Quando um evento
3 Padro de portabilidade e interoperabilidade para sistemas
operacionais (ver, por exemplo,
https://pt.wikipedia.org/wiki/POSIX)
28
https://pt.wikipedia.org/wiki/POSIX
-
Figura 4.1: esquema PRNG [26]
desses ocorre, duas palavras de 32-bits so usadas como entrada
no repositrio primrio,
via processo de mistura. A primeira palavra codica o tempo
medido em jies4 ou em
ciclos granulares de CPU. A segunda palavra codica o tipo de
evento correspondente.
Como estamos tratando de processos assncronos para a alimentao
dos reposit-
rios, o repositrio secundrio s recebe dados a partir do momento
em que o valor de
entropia do repositrio primrio se torna mximo, isto , quando o
contador de entro-
pia deste atinge o valor 4096. Quando o repositrio secundrio
atinge a sua entropia
mxima, o processo no repositrio primrio retomado. O processo de
adio ao con-
tador de entropia5 determinado por um clculo da estimativa de
entropia entrante
no respectivo repositrio.
4.1.2 Outputs dos repositrios
Existem somente trs outputs gerados pelos repositrios presentes
na estrutura dos
geradores PRNG no Linux . A extrao de bits do repositrio primrio
ocorre somente
quando o repositrio secundrio ou o repositrio urandom no tm
entropia suciente e
precisam ser realimentados. A extrao de bits de urandom ocorre
quando um processo
4 Unidade que corresponde ao nmero de milissegundos de diferena
no tempo de relgio em que
o evento ocorreu, e o tempo em que o sistema foi
inicializado.
5 No sentido de medida de incerteza quanto previsibilidade
habilitada pelo contexto, na forma
denida pela Teoria Matemtica da Informao de Claude Shannon
29
-
de usurio ou do kernel pede uma quantidade qualquer de bits
aleatrios pela chamada
/dev/urandom ou get-random-bytes, respectivamente. A extrao de
bits do repositrio
secundrio ocorre quando um usurio usa a chamada /dev/random.
O processo de extrao de entropia (ou seja, de dados aleatrios)
ocorre em trs
etapas.
1. Extrao de bits aleatrios como sada;
2. Decremento do contador de entropia do respectivo repositrio
relativo
sada (na etapa 1);
3. Atualizao do contedo presente no repositrio, envolvendo o
hashing
do contedo dos repositrios utilizando SHA-1 e a adio dos
resultados nos repositrios.
Cada processo citado acima ser abordado com maior detalhamento
nas sees
posteriores.
A principal diferena entre os PRNG em /dev/random e em
/dev/urandom est
no fato de que, caso o contador de entropia do repositrio
secundrio seja menor do
que a quantidade de bits solicitados, a operao de extrao de bits
bloqueada e o
estado do repositrio realimentado com novos dados extrados do
repositrio primrio.
Enquanto com odev/urandom esse bloqueio no ocorre, e a atualizao
de entropia no
repositrio urandom s ocorre aps o m de todo o processo de sada
de dados.
4.1.3 Adio ao contador de entropia
A quantidade de entropia adicionada a um contador estimada a
partir da diferena
de tempo de um evento para outro, sem levar em conta o tipo de
evento capturado.
Mesmo eventos que adicionam zero a esse contador, tm importncia
na atualizao
do estado do gerador. importante ressaltar que o evento de
escrita em disco a partir
de um processo de usurio tem valor zero para o clculo da
estimativa de entropia. O
contador tem seu valor decrementado em n, quando n bits so
extrados do repositrio.
Quando a extrao resultado de uma transferncia entre repositrios,
esse valor n
adicionado ao contador do repositrio destinatrio.
30
-
4.1.4 Atualizao dos repositrios
O mecanismo para atualizao dos repositrios baseado em TGFSR
(Twisted
Generalized Feedback Shift Register). A principal vantagem do
uso dessa tcnica de
prover perodo (rbita) mximo para qualquer semente inicial no
nula, propriedade
necessria ao objetivo de entropia mxima do PRNG. O perodo mximo
de uma
TGFSR com estado de 128 words pode chegar at 2(12832) 1.
Entropia adicionadaa cada atualizao de estado ou sada de dados. O
algoritmo de add(pool,j,g) utilizado
para adio de entropia, onde a varivel pool um vetor de bits de
32 ou 128 palavras,
j o ndice do vetor, e g a nova palavra a ser adicionada no
repositrio.
So utilizados dois polinmios irredutveis no TGFSR de atualizaco
dos reposit-
rios. O polinnio
x128 + x103 + x76 + x51 + x25 + x1 + 1
utilizado para realimentar o repositrio primrio, e o
polinmio
x32 + x26 + x20 + x14 + x7 + x1 + 1
utilizado para realimentar tanto o repositrio secundrio quanto o
repositrio do
PRNG urandom. As potncias que ocorrem nos polinmios indicam os
ndices dos
bits em g que sero operados pela funo xor com os bits nos
respectivos ndices no
parmetro j.
A adio de entropia no LRNG (Linux Random Number Generator) pode
ser
entendida como uma atualizao na semente a cada interao. O TGFSR
pode ser
analisado como uma funo que encripta o input da entropia.. Essa
atualizao de
semente altera as propriedades estruturais dos TGFSR, a ponto de
no mais ser possvel
presumir que o perodo mximo associado ao respectivo polinmio
continue valendo
nesse contexto de operao, pois cada processo passa assim a
computar uma funo
simblica que no mais corresponde a funo algbrica linear sobre o
estado inicial.
4.1.5 Extrao de Bits aleatrios dos repositrios secundrio e
urandom
Extrair bits aleatrios de um repositrio no uma operao trivial
[1]. Tal opera-
o envolve o hashing dos bits extrados, modicao do estado atual
do repositrio,
e subtrao no correspondente contador de entropia pelo nmero de
bits extrados. A
31
-
Figura 4.2: Extrao de bits aleatrios da funo TGFSR [26]
extrao de bits de um tal repositrio realizada em blocos de 10
bytes. O algoritmo
aplica a funo de hash SHA-1 em 16 palavras do repositrio, chama
a funo de adi-
o do TGFSR, na forma: add( pool, j , SHA-1(pool[0...15])), e o
valor resultante da
funo de adio escrito na posio j. Em seguida, aplica-se uma
variante da funo
SHA-1 a SHA-1'6 na metade direita do repositrio e o resultado
adicionado as
posies j 1 e j 2. Por m, aplica-se SHA-1` s 16 palavras
anteriores ao j 2. Agura 4.2 apresenta um diagrama ilustrativo do
referido algortimo de extrao.
Os resultados das operaes de hashing e folding so utilizados em
uma funo de
dobra (ou folding7) que gera um output de 10 bytes. O resultado
ento colocado em
um buer e o processo de realimentao desse buer se repete at o
buer atingir a
quantidade de bits solicitada pelo processo de usurio ou do
kernel. Caso o processo
solicitado a fornecer bits aleatrios gere mais bits do que o
necessrio, esses bits so-
bressalentes so utilizados no processo de atualizao do
repositrio de onde a extrao
solicitada ocorreu.
6 A funo SHA-1` uma variao de SHA-1, onde as 5 ltimas words (ou
10 ltimos bytes) do
repositrio so alteradas a cada iterao passada da extrao de bits.
Essa alterao na funo
de hashing importante para aumentar o custo de ataques de
criptoanlise ao algoritmo
7 Input : W0,W1,W2,W3,W4; Output : W0 W3,W1 W4,W20...15
W216...31
32
-
4.2 Fragilidades no LRNG
Nesta seo, abordamos formas de ataque ao LRNG descritas na
literatura especia-
lizada, considerando a premissa de que estimativas da
complexidade desses ataques, em
termos de custo computacional, servem de aproximao s estimativas
empricas para
perda de entropia por falhas correspondentes na inicializao de
geradores de primos,
descritas no captulo anterior como principais suspeitas por
colises entre mdulos ge-
rados com o OpenSSL, em contextos onde a biblioteca geradora
opera sobre plataforma
GNU/Linux.
4.2.1 Ataque de criptoanlise na propriedade 1. no LRNG
O primeiro tipo de ataque a ser analisado aqui o ataque de
criptoanlise sobre a
propriedade ideal 1. (descrita na Seo 4.1), referente premissa
de imprevisibilidade
de um estado passado, a partir de um estado presente que venha a
se tornar conhecido
pelo atacante. Observamos que o output extrado de um repositrio
calculado como
o ltimo estado do algoritmo de extrao. Ou seja, a extrao
computada aps a
atualizao do estado deste mesmo repositrio. Este fato implica
que se o estado de
um repositrio em um tempo t conhecido, ento possvel descobrir
quais dados
foram extrados daquele repositrio durante sua ltima transio de
estado (em outras
palavras, possvel descobrir o output que foi computado na
transio do tempo t 1para o tempo t). Dessa forma, qualquer atacante
que consiga observar o estado do
LRNG em algum instante, pode computar o ltimo output do
LRNG.
O ataque por criptoanlise tem sua eccia ligada realimentao dos
repositrios
secundrio e urandom. Caso ocorra a realimentao do repositrio, a
aleatoriedade dos
novos dados diculta a possibilidade do atacante prever o estado
atual do repositrio
alvo. Dessa forma, o ataque por criptoanlise melhor empregado
contra o repositrio
urandom, que no bloqueia a operao de extrao de dados quando o
seu contador de
entropia atinge valor menor do que a quantidade de bits
solicitados.
Caso o ataque se inicie em um instante onde o contador de
entropia do repositrio
secundrio esteja alto e a entropia adicionada ao reservatrio
primrio seja previsvel,
o ataque de criptoanlise tambm pode ser relevante contra o
repositrio secundrio.
J sabemos que possvel encontrar um estado(t 1) e a sada desse
estado a partirde um estado(t) conhecido. De forma anloga, chegamos
concluso que possvel
encontrar os estados: estado(t 2), estado(t 3), . . . ,
estado(0) (onde 0 simboliza
33
-
o momento em que a ltima realimentao do repositrio ocorreu) e
suas respectivas
sadas.
Este fato pode estar associado, em tese, s situaes onde estados
relativamente
prximos nessas sequncias, ocorrendo em eventos independentes mas
de natureza si-
milar (por exemplo, durante o boot de plataformas distintas porm
do mesmo modelo
e congurao), acabem por induzir dois geradores de primos a
eventualmente sele-
cionarem o mesmo primo. Onde sadas distintas do LRNG alimentam
instncias de
inicializao nos respectivos geradores, distintas mas que ocorrem
no mesmo intervalo
entre dois primos consecutivos selecionveis. Efeito colateral
que tende a recorrer,
devido previsibilidade da sequncia de estados a partir do
momento zero de um
mesmo evento de boot (em plataformas distintas). Efeito que se
amplicaria se os
intervalos entre primos selecionveis estiverem
despropositadamente esticados, como
caracterizado pela peculiaridade do gerador de primos no
necessariamente seguros do
OpenSSL descrita por Mironov.
4.2.2 Ataque na gerao de Entropia do reservatrio primrio
Um atacante pode inuenciar diretamente a alimentao do repositrio
secundrio.
Quando o contador de entropia no repositrio primrio est cheio,
entropia adicionada
diretamente ao repositrio secundrio. Esse uxo de coleta de
entropia e
