elikaski/ecc_attacksAtaques conhecidos em Criptografia de Curva Elíptica
Nos últimos anos, a abordagem da Criptografia de Curvas Elípticas tornou-se popular devido à sua alta eficiência e forte segurança. O objetivo deste artigo é apresentar este tema de uma forma relativamente mais clara do que a que existe hoje na internet.
Neste artigo apresentarei o que são curvas elípticas, as operações básicas que podem ser realizadas nelas e como podem ser utilizadas em contexto criptográfico. A maior parte deste artigo consiste em exemplos de ataques conhecidos a implementações incorretas ou utilizações erradas das mesmas. Ao longo do artigo, tento separar a explicação numa parte intuitiva e de alto nível, e numa parte matemática que entra em mais detalhes. O leitor é convidado a focar-se na parte que lhe interessar naquele ponto e a saltar as partes que lhe interessam menos.
Boa leitura!
Em geral, uma curva elíptica é algum tipo de linha curva. Um exemplo disso é a parábola, cuja equação é da forma $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ e tem este aspeto:
No contexto da criptografia, é habitual utilizar curvas elípticas cuja equação é da forma
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Por exemplo, uma curva elíptica correspondente à equação $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ tem este aspeto:
A equação da curva define a relação entre a coordenada 𝑥 de um ponto na curva e a sua coordenada 𝑦. Num contexto criptográfico, restringimos 𝑥, 𝑦, 𝑎, 𝑏 a números inteiros e restringimos os cálculos a serem feitos módulo algum número primo grande. Portanto, a equação da curva elíptica é:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Isto significa que temos um número finito de pontos na curva. Em linguagem matemática, a curva é definida sobre um corpo finito de ordem 𝑝. Como resultado, agora nem todos os valores de 𝑥 terão necessariamente um ponto correspondente na curva, porque pode acontecer que a coordenada 𝑦 correspondente não seja um número inteiro.
O conjunto de pontos na curva consiste em pares de números inteiros (𝑥, 𝑦) que satisfazem a equação da curva. Além destes pontos, é definido outro ponto especial chamado "Infinito", e é denotado por 𝒪. Em linguagem matemática, este ponto é o elemento neutro do conjunto de pontos na curva em relação à operação de adição, que definiremos na próxima secção. O número de pontos na curva (incluindo o ponto 𝒪) é chamado de "ordem da curva".
Outra observação é que as curvas elípticas são simétricas em relação ao eixo X. Isso significa que se o ponto 𝑃 = (𝑥, 𝑦) está na curva, então o ponto −𝑃 = (𝑥, −𝑦) também está na curva. Na verdade, esses pontos são considerados "inversos" um do outro (daí a marcação −𝑃 para o segundo ponto), e o resultado da operação de adição entre eles é definido como o elemento neutro 𝒪.
Um teorema chamado Teorema de Hasse fornece uma estimativa de #𝐸, a ordem da curva, e é da ordem de grandeza de Θ(𝑝). Mais precisamente:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Dados dois pontos na curva, é possível definir uma operação de adição entre eles, resultando num terceiro ponto que também está na curva. Para encontrar este ponto geometricamente, traçamos uma linha entre os dois pontos dados e continuamo-la até que intersete a curva num terceiro ponto. Este ponto é refletido em relação ao eixo 𝑋, e o ponto resultante é definido como o resultado da adição.
Aqui está um diagrama que mostra como, dados os pontos 𝑃 e 𝑄, o ponto 𝑃 + 𝑄 pode ser encontrado:
Uma questão que pode surgir desta descrição é: o que acontece se a linha traçada entre os dois pontos não intersetar a curva novamente? Neste caso, diz-se que a linha interseta a curva no "infinito", e o resultado da adição é o ponto 𝒪. Repare que este caso acontece se a linha traçada for vertical, ou seja, se estivermos a tentar adicionar um ponto 𝑃 ao seu ponto inverso, −𝑃:
Duas identidades básicas derivam daqui. Para todo o ponto 𝑃, vale que:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Outra questão que surge da descrição geométrica é: como adicionamos um ponto a si próprio? Vimos que, para adicionar dois pontos diferentes 𝑃 e 𝑄, traçamos uma linha entre eles e observamos o ponto de interseção da sua continuação com a curva. Intuitivamente, deixaremos 𝑃 constante e observaremos a linha que é criada à medida que movemos 𝑄 "cada vez mais perto" de 𝑃, até 𝑄 se fundir com 𝑃. O que obteremos é uma linha cada vez mais "tangente" à curva no ponto 𝑃, e é exatamente essa a linha que observaremos quando quisermos adicionar 𝑃 a si próprio:
Para adicionar um ponto 𝑃 a si próprio, traçamos uma tangente à curva no ponto 𝑃 e continuamo-la até que intersete a curva num segundo ponto. Este ponto é refletido em relação ao eixo 𝑋, e o ponto resultante é definido como o resultado da adição. É habitual marcar o resultado da adição como 𝑃 + 𝑃 = 2𝑃. Novamente, se a tangente não intersetar a curva num segundo ponto, então diz-se que interseta a curva no "infinito", e o resultado da adição neste caso é o ponto 𝒪.
Estas descrições geométricas visuais ilustram bem e ajudam-nos a compreender como funciona a adição de pontos. Mas como é que realmente a calculamos? Equações matemáticas, claro!
Dados os pontos $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ e $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$, o resultado da sua adição é o ponto $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ tal que:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
Onde 𝜆 é definido como o declive da linha que liga os pontos, se forem diferentes, e o declive da tangente à curva no ponto, se o ponto for adicionado a si próprio. Formalmente:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
Os cálculos matemáticos por trás da adição de pontos não são críticos para o resto do artigo. Para esse efeito, podemos encarar a adição de pontos como uma caixa negra que recebe dois pontos na curva e devolve um terceiro ponto que também está na curva.
Vimos que é possível adicionar um ponto 𝑃 a si próprio e denotámos o ponto resultante por 2𝑃. Se adicionarmos novamente o ponto 𝑃 a este resultado, chegaremos a um ponto denotado por 3𝑃, e assim por diante. Desta forma, é possível definir a "multiplicação" de um ponto por uma constante, adicionando repetidamente o ponto a si próprio (de forma semelhante à multiplicação entre números):
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
Aparentemente, para multiplicar um ponto por um número 𝑛, precisamos de realizar 𝑛 operações de adição entre pontos. Isto porque, dado um ponto inicial, é difícil saber antecipadamente onde o "último" ponto cairá, sem o alcançar "passo a passo". Tal cálculo seria muito ineficiente, porque 𝑛 poderia ser muito grande.
Para este efeito, existe o algoritmo Double And Add, no qual começamos no ponto 𝑃 e, para cada bit na representação binária de 𝑛, o ponto atual é multiplicado por 2 (ou seja, é adicionado a si próprio) e é adicionado ao resultado se o valor do bit for 1. A complexidade de tempo de execução deste algoritmo é 𝑂(log 𝑛) e permite multiplicar eficientemente pontos por números muito grandes.
Uma propriedade importante da multiplicação de pontos que usaremos mais tarde é que, para todo o ponto 𝑃 e par de números 𝑎, 𝑏, vale:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
Intuitivamente, suponha que começamos no ponto 𝑃, damos 𝑎 passos a partir dele e chegamos ao ponto 𝑎𝑃. A partir deste ponto, damos 𝑏 passos de "tamanho" 𝑎 e chegamos ao ponto 𝑏(𝑎𝑃). Alternativamente, noutro cenário, poderíamos começar no ponto 𝑃, dar 𝑏 passos com ele e chegar ao ponto 𝑏𝑃. A partir deste ponto, damos 𝑎 passos de "tamanho" 𝑏 e chegamos ao ponto 𝑎(𝑏𝑃).
Em ambos os cenários, demos o mesmo total de 𝑎𝑏 passos a partir do ponto 𝑃, portanto, em ambos os cenários, chegámos ao mesmo ponto final. Matematicamente, multiplicar um ponto por uma constante é associativo.
Se começarmos num ponto 𝑃 e o adicionarmos a si próprio vezes sem conta, em cada um desses passos chegaremos a um novo ponto na curva. Como há um número finito de pontos na curva, em algum momento voltaremos a pontos que já alcançámos antes e estaremos numa espécie de ciclo, ou "círculo". Mais precisamente, em algum momento chegaremos ao ponto -𝑃, no passo seguinte chegaremos ao ponto 𝒪, e no passo a seguir voltaremos a chegar ao ponto 𝑃, de onde partimos.
O ponto que cria tal "círculo" é chamado de Gerador, porque todo o "círculo" pode ser gerado a partir dele, e é habitual marcá-lo com a letra 𝐺. O número de pontos no "círculo" (incluindo o ponto 𝒪) é chamado de "ordem do gerador 𝐺", e é geralmente denotado por 𝑛. Cada ponto na curva forma um "círculo" de algum tipo. Matematicamente, o conjunto de pontos neste "círculo" é um grupo cíclico.
Uma propriedade interessante que resulta disto é que multiplicar um ponto 𝐺 pela sua ordem 𝑛 dá-nos o ponto do infinito:
𝑛𝐺 = 𝒪
“Dados os pontos 𝑃 e 𝑄 tais que 𝑄 = 𝑥𝑃 para algum 𝑥, é difícil encontrar 𝑥.”
E por palavras, suponha que alguém partiu de algum ponto inicial, deu um certo número de passos a partir dele e chegou a um ponto final. Dados o ponto inicial e o ponto final, como sabemos quantos passos essa pessoa deu?
A resposta a esta pergunta não é assim tão intuitiva, porque é difícil prever antecipadamente, a partir de um ponto inicial, quais os pontos que serão alcançados ao dar passos a partir dele. Uma solução ingénua poderia ser começar nós próprios em 𝑃, avançar a partir dele um passo de cada vez e contar os passos que damos, até chegarmos a 𝑄. A complexidade desta solução é 𝑂(𝑥) e é inviável se se souber que 𝑥 é um número grande, por exemplo se 𝑥 tiver 256 bit.
Este problema é chamado de Problema do Logaritmo Discreto em Curvas Elípticas (ECDLP), e é um problema difícil. Mas quão difícil é?
Num contexto criptográfico, é habitual medir a "dificuldade de problemas", ou a "força de um sistema criptográfico", com uma métrica chamada Security Level. Nesta métrica, diz-se que um problema tem "𝑛 bits de segurança" se o melhor ataque conhecido resolver o problema em $𝑂(2^𝑛)$ passos.
Atualmente, o melhor algoritmo que resolve o problema ECDLP fá-lo com uma complexidade de $𝑂(\sqrt n)$, onde 𝑛 é a ordem do ponto 𝑃, e fá-lo usando um ataque Meet In The Middle. Quando é selecionado um ponto com uma ordem suficientemente grande, resolvê-lo é inviável, daí a força do problema.
Por exemplo, se escolhermos 𝑛 com tamanho de 256 bit, obtemos que o problema ECDLP tem um nível de segurança de 128 bit de segurança. Para comparação, para alcançar o mesmo nível de segurança de 128 bit no RSA, que se baseia no problema da fatoração de inteiros, é necessária uma chave pública com tamanho de 3072 bit. Isto torna o uso de curvas elípticas relativamente mais eficiente a nível computacional.
Depois de toda esta introdução ao mundo das curvas elípticas, passaremos a ver o que pode ser feito com elas num contexto criptográfico. Como sabemos, os sistemas criptográficos baseiam-se geralmente num "problema difícil" que é difícil de resolver. Por exemplo, o RSA com o problema de fatorar um número que mencionámos, ou o protocolo Diffie-Hellman com o problema do logaritmo discreto. Um sistema criptográfico que se baseie no problema ECDLP numa curva elíptica pertence à família da Criptografia de Curvas Elípticas, ou, para abreviar, ECC.
Vamos começar com uma história. Imagine que está numa festa - uma sala cheia de pessoas, onde toda a gente pode falar com toda a gente e toda a gente ouve toda a gente. Nesta sala estão também Alice e Bob, que nunca se conheceram antes. Alice gosta de Bob e quer convidá-lo para sair. Alice é um pouco tímida, por isso quer contar a Bob esta mensagem secreta sem que os outros convidados da festa a ouçam. Alice e Bob não combinaram nada antecipadamente, e tudo o que Alice disser a Bob será ouvido por todos os outros convidados da festa. Como pode Alice contar a mensagem a Bob sem que mais ninguém a oiça?
Se respondeu "curvas elípticas", então está certo!
Alice selecionará alguma curva elíptica e um gerador nela, e irá dizê-los a Bob. Especificamente, Alice passará a Bob (e a todos os outros na sala) os dois parâmetros da curva 𝑎, 𝑏, o módulo 𝑝 e o gerador 𝐺. Além disso, Alice selecionará algum valor $𝑑_𝐴$ no intervalo $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$, onde 𝑛 é a ordem de 𝐺. O valor $𝑑_𝐴$ é chamado de chave privada de Alice. Alice calculará o ponto $𝐴 = 𝑑_𝐴𝐺$, que é chamado de chave pública de Alice, e irá dizê-lo a Bob. Da mesma forma, Bob selecionará uma chave privada $𝑑_𝐵$, calculará o ponto $𝐵 = 𝑑_𝐵𝐺$, que é chamado de chave pública de Bob, e irá dizê-lo a Alice.
Alice pegará na chave pública de Bob, multiplicará esse ponto pela sua chave privada e chegará a um terceiro ponto $𝑃_𝐴 = 𝑑_𝐴𝐵$. Da mesma forma, Bob pegará na chave pública de Alice, multiplicá-la-á pela sua chave privada e chegará a um terceiro ponto seu $𝑃_𝐵 = 𝑑_𝐵𝐴$. Se examinarmos os pontos a que Alice e Bob chegaram separadamente, descobrimos que chegaram ao mesmo ponto! Este facto provém da propriedade associativa da multiplicação de um ponto por uma constante que vimos antes:
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
No final de todo o processo, Alice e Bob conseguiram chegar a um acordo sobre algum ponto na curva, e em nenhuma fase qualquer um deles passou esse ponto à outra pessoa. A informação que todos ouviram é: 𝑎, 𝑏, 𝑝, 𝐺, 𝐴, 𝐵. Uma pessoa que esteja na sala a ouvir esta informação não consegue encontrar o ponto sobre o qual Alice e Bob chegaram a acordo com ela.
Isto porque, se outra pessoa na sala quisesse encontrar esse ponto, precisaria de conhecer ou a chave privada de Alice ou a chave privada de Bob para multiplicar 𝐵 ou 𝐴 por elas. Para encontrar a chave privada de Alice, por exemplo, essa pessoa olharia para $𝐴 = 𝑑_𝐴𝐺$, pois esta é a única informação que foi enviada e que "contém" a chave privada de Alice. Dados 𝐺 e $𝑑_𝐴𝐺$, encontrar $𝑑_𝐴$ é equivalente a resolver o problema do logaritmo discreto em curvas elípticas, que, como foi mencionado, é um problema difícil.
Este belo protocolo chama-se: Diffie-Hellman de Curva Elíptica (ECDH).
Ainda não acabámos a nossa história. Embora Alice e Bob tenham chegado a acordo sobre um ponto secreto partilhado, Alice ainda não convidou Bob para o encontro que tanto queria.
Depois de as partes terem chegado a acordo sobre um ponto secreto partilhado, podem usá-lo como chave de encriptação de qualquer método de encriptação, por exemplo AES, e a partir desse ponto comunicar de forma segura através de encriptação.
É comum tirar uma das coordenadas 𝑥 ou 𝑦 do ponto e usá-la. Para manter a segurança, é recomendado aplicar hash ao valor selecionado e usar apenas o resultado do hash como chave de encriptação. Na prática, por vezes o valor é demasiado grande para ser usado como chave de encriptação. Por exemplo, se a função hash usada for SHA-1, o seu comprimento de saída é de 160 bit, enquanto a encriptação AES requer apenas 128 bit. Nesse caso, é habitual usar apenas 128 bits dos 160 e descartar o resto.
De qualquer forma, neste ponto Alice e Bob chegam a acordo sobre uma chave de encriptação, e são os únicos que a conhecem. A partir deste ponto, comunicam através de encriptação, e qualquer pessoa que esteja a ouvir na sala não consegue compreender o que estão a dizer.
Aqui está um diagrama do protocolo:
Usando a chave acordada, Alice encripta a mensagem "Hey Bob, gostarias de sair para um café amanhã à noite?", e passa a mensagem encriptada a Bob. Bob desencripta a mensagem com a chave que ele também conhece. Alice espera que Bob diga que sim, mas isso não faz parte do protocolo.
No conhecido protocolo Diffie-Hellman (DH), as partes transmitem abertamente um número primo 𝑝 e um gerador 𝑔 que está no grupo correspondente ao valor 𝑝. Alice gera aleatoriamente uma chave privada 𝑎 e transmite abertamente a sua chave pública $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$. Da mesma forma, Bob gera aleatoriamente uma chave privada 𝑏 e transmite abertamente a sua chave pública $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$. Alice então pega na chave pública de Bob e eleva-a à potência da sua chave privada, calculando assim o valor $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. Da mesma forma, Bob calcula o valor $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$. No final do processo, Alice e Bob conseguiram chegar a acordo sobre um valor comum 𝐾, sem o transmitirem entre si.
Um atacante que os esteja a ouvir não consegue encontrar 𝐾 dados os valores transmitidos 𝑝, 𝑔, 𝐴, 𝐵. Para o fazer, terá de encontrar a chave privada de Alice ou a de Bob. Para calcular a chave privada de Alice, por exemplo, teria de encontrar 𝑎 dados 𝑔 e $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$, o que é um problema difícil. Este problema é chamado de Problema do Logaritmo Discreto (DLP).
Existe uma semelhança muito clara entre o DH, que se baseia no DLP, e o ECDH, que se baseia no ECDLP (são basicamente o mesmo, apenas com um prefixo EC). Em ambos os protocolos, duas partes que falam entre si podem chegar a acordo sobre algum valor secreto partilhado, sem que tenham combinado nada antecipadamente. Qualquer pessoa que ouça as mensagens entre as partes ficará exposta à informação pública que elas trocam entre si, mas não conseguirá chegar ao valor secreto partilhado entre elas.### Segundo Uso de Curvas Elípticas - Assinando uma Mensagem Continuando a nossa história, digamos que Alice e Bob saíram para o encontro e passaram uma noite agradável juntos. No dia seguinte, Alice recebe uma mensagem dizendo "Oi Alice, aqui é o Bob, eu me diverti muito com você ontem e adoraria te encontrar de novo neste fim de semana". Alice suspeita que não foi Bob quem enviou a mensagem, porque ela sabe que Bob se divertiu tanto com ela ontem que não vai esperar até o fim de semana para vê-la, mas vai querer encontrá-la amanhã! Como Alice pode verificar que foi Bob quem escreveu a mensagem?
Se você respondeu "curvas elípticas", então você acertou novamente!
A dificuldade do problema ECDLP também pode ser usada para assinar mensagens. Durante o encontro, Alice e Bob concordaram em uma curva elíptica e um gerador 𝐺 nela. Bob gerou um valor $𝑑_𝐵$, chamado de chave privada de Bob, e calculou o ponto $𝑃_𝐵 = 𝑑_𝐵𝐺$, chamado de chave pública de Bob. Bob deu a Alice sua chave pública para que ela pudesse usá-la depois para verificar se uma mensagem que ela recebe foi de fato assinada por ele.
Digamos que Bob queira assinar uma determinada mensagem 𝑚. Ele calculará o valor $z = hash(m)$ usando alguma função hash segura, e manterá uma quantidade de bits do resultado igual ao comprimento em bits de n, a ordem do gerador 𝐺. Bob gerará um valor aleatório 𝑘 no intervalo $1 ≤ 𝑘 ≤ 𝑛 − 1$. Bob então calculará o ponto $𝑘𝐺 = (𝑥_1, 𝑦_1)$, pegará sua coordenada 𝑥 e calculará $𝑟 = 𝑥1\ \ \ \ (mod\ n)$. Por fim, Bob calculará o valor $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$.
A assinatura da mensagem 𝑚 é definida como o par de valores calculados 𝑟 e 𝑠.
Suponha que Alice recebeu uma determinada mensagem 𝑚, e sua assinatura consiste em um par de valores 𝑟 e 𝑠. Alice quer ter certeza de que foi realmente Bob quem assinou a mensagem. Alice calculará o valor $z = hash(m)$ da mesma forma que Bob. Alice então calculará os valores $𝑢_1 = 𝑧𝑠^{−1}$ e $𝑢_2 = 𝑟𝑠^{−1}$. Por fim, Alice usará a chave pública de Bob $𝑃_𝐵$ e calculará o ponto $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$. A assinatura será considerada válida se valer que $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$. A razão para isso estar correto é que vale:
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
Se a assinatura for válida, a coordenada 𝑥 desse ponto deve ser de fato 𝑟, conforme definido na assinatura da mensagem. Deve-se notar que a ordem do gerador 𝐺, que é denotada pela letra 𝑛, deve ser um número primo, e isso é necessário para que seja de fato possível calcular os números inversos nos algoritmos de assinatura e verificação.
Pode-se ver que somente a pessoa que possui a chave privada $𝑑_𝐵$ pode criar uma assinatura válida para a chave pública $𝑃_𝐵$. Um atacante que não possui o valor $𝑑_𝐵$ não pode calcular o valor 𝑠 correspondente a $𝑃_𝐵$ na assinatura. Se o atacante quiser criar uma assinatura que corresponda a uma determinada mensagem, ele terá que resolver o problema ECDLP, ou seja, encontrar a chave privada $𝑑_𝐵$ dados $𝐺$ e $𝑃_𝐵 = 𝑑_𝐵𝐺$, o que é um problema difícil.
Esse protocolo de assinatura é chamado de Algoritmo de Assinatura Digital de Curva Elíptica, ou ECDSA para abreviar. O protocolo garante que as mensagens assinadas não foram alteradas ou forjadas e, além disso, garante que a pessoa que assinou a mensagem não pode negar que a criou.
Diferentemente do protocolo ECDH, em que as partes não precisavam combinar nada antecipadamente, no protocolo ECDSA as partes devem concordar antecipadamente sobre uma chave pública. Somente depois que cada parte souber com certeza que a chave pública que possui de fato pertence à pessoa com quem deseja se comunicar, o protocolo pode ser usado. Caso contrário, não faz sentido verificar a assinatura com a chave pública que cada parte possui.
De volta à nossa história. Alice sabe com certeza que a chave pública $𝑃_𝐵$ em sua posse pertence mesmo a Bob, pois Bob a deu explicitamente a ela durante o encontro. Alice tenta verificar a mensagem com ela e descobre que não há correspondência. é claro! Outra pessoa criou a mensagem e a assinou, exatamente como Alice suspeitava.
Aqui está um diagrama do protocolo:
No protocolo ElGamal para assinatura de mensagens, as partes concordam em um número primo grande 𝑝 e um número gerador 𝑔. A parte que assina gera algum valor 𝑑 no intervalo $1 ≤ 𝑑 < 𝑝 − 1$, chamado de chave privada, calcula o valor $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$, chamado de chave pública, e o publica.
Para assinar uma determinada mensagem, eles calculam o valor $z = hash(m)$ e geram um valor aleatório 𝑘 no intervalo $1 ≤ 𝑘 < 𝑝 − 1$ que seja coprimo a $(p-1)$. Eles calculam $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ e $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$. A assinatura da mensagem m é definida como o par de valores calculados 𝑟 e 𝑠.
A parte que recebeu uma determinada mensagem 𝑚, e cuja assinatura consiste em um par de valores 𝑟 e 𝑠, usa a chave pública 𝑦 para verificar a assinatura calculando os valores $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ e $𝑢_2 = 𝑔^𝑧$. A assinatura será considerada válida se $𝑢_1 = 𝑢_2$. Isso porque, de acordo com a definição de 𝑠, temos:
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, portanto $𝑘𝑠 = 𝑧 − 𝑑𝑟$, logo $𝑧 = 𝑘𝑠 + 𝑑𝑟$. Portanto:
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
Um atacante não pode criar uma assinatura válida para a chave pública 𝑦 sem conhecer a chave privada 𝑑. Para obter a chave privada a partir da chave pública, o atacante precisaria resolver o problema DLP, que é um problema difícil.
Aqui também há uma clara semelhança entre ECDSA, que se baseia em ECDLP, e ElGamal, que se baseia em DLP. Em ambos os casos, as partes precisam combinar uma chave pública antecipadamente, e é necessário gerar um valor aleatório 𝑘 toda vez que quisermos assinar uma nova mensagem. Além disso, em ambos os casos, um atacante que escuta as mensagens entre as partes não consegue deduzir informações úteis que lhe permitam forjar assinaturas.
Vimos como as curvas elípticas podem ser usadas em sistemas criptográficos para combinar um valor secreto e para assinar mensagens. Como em tudo na vida, quando se trata de colocar algo em prática, as coisas nem sempre funcionam como planejado. No restante do artigo, apresentarei diferentes maneiras de atacar sistemas criptográficos baseados em ECC que foram usados incorretamente pelo usuário, ou implementados de forma insegura.
Naturalmente, divido esta parte em ataques a ECDH e ataques a ECDSA. Em ambos os casos, diremos que "obtivemos sucesso" no ataque se encontrarmos a chave privada de uma das partes, e pararemos por aí. No caso do ECDH, isso é suficiente porque, a partir da chave privada, é possível chegar ao valor secreto compartilhado e a todas as informações criptografadas com ele depois. No caso do ECDSA, isso é suficiente porque a chave privada pode ser usada para assinar mensagens como quisermos.
O SageMath é um software matemático gratuito e de código aberto. Ele pode ser escrito com quase a mesma sintaxe do Python, e também pode ser usado como uma biblioteca Python. Essa biblioteca implementa funções úteis relacionadas a curvas elípticas e, portanto, é muito útil para os cálculos que precisamos fazer no contexto de ECC. Como parte deste artigo, forneço trechos de código escritos nessa biblioteca. Descobri que é mais fácil instalá-lo no sistema operacional Ubuntu, especificamente na versão 22.04. Para instalá-lo, basta executar o comando: sudo apt install sagemath.
Para executar um arquivo que contém código, salve o arquivo com a extensão .sage e execute o comando: sage file.sage.
Além disso, um interpretador pode ser usado, de forma semelhante ao interpretador do Python, executando o comando: sage. Também é possível criar arquivos .py nos quais a biblioteca sage.all é importada, e executá-los com o comando python3 file.py. Observe que, ao executar um arquivo com o comando sage, a notação ^ é interpretada como potência, enquanto ao executar com python3, essa notação é interpretada como xor.
Neste artigo, utilizo principalmente as seguintes funções no SageMath:
E.gens() - encontrando geradores na curva EG.order() - calculando a ordem do gerador Gn*G -multiplicação do gerador G pelo número nn.factor() - fatorar o número n em seus fatores - a função retorna uma lista de pares (𝑝, 𝑒) em que 𝑝 é um fator primo, e 𝑒 é seu expoente, ou seja, o número de vezes que 𝑝 aparece na decomposição de ncrt - resolvendo um sistema de equações do teorema chinês do restoTalvez o uso incorreto de ECDH mais fácil de atacar seja escolher um gerador com uma ordem n muito pequena.
Como mencionado, é possível resolver o problema ECDLP com uma complexidade de $O(\sqrt{n})$. Quando 𝑛 é muito pequena, por exemplo 32 bits, então se torna viável resolver esse problema. Existem diversos algoritmos que resolvem o problema, incluindo Baby-Step Giant-Step, Pollard's Rho e Pollard's Lambda. Esses algoritmos podem ser executados como uma caixa-preta com a ajuda do SageMath, usando a função discrete_log:```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
Neste trecho de código, escolhemos os parâmetros da curva aleatoriamente sob a limitação de que `𝑝` tem 32 bits de comprimento. Essa limitação nos garante que o número de pontos na curva é $O(2^{32})$ e, portanto, a ordem de cada ponto nela é no máximo $O(2^{32})$ também. Depois disso, criamos a curva, escolhemos um gerador nela, geramos uma chave privada aleatória e calculamos a chave pública. Por fim, a partir do gerador e da chave pública, calculamos o logaritmo discreto para encontrar a chave privada e verificamos que a chave encontrada está de fato correta. Este código leva apenas alguns segundos, no máximo, para encontrar a chave privada.
## A Ordem do Gerador é um Número Suave
Como mencionado, a ordem de um gerador é definida como o número de pontos no "círculo" formado quando somamos o ponto gerador a si mesmo repetidamente, e é denotada por `𝑛`. Se `𝑛` é um número composto que pode ser fatorado em fatores primos menores, então é possível resolver o ECDLP de forma eficiente. Esse número é chamado de Número Suave e, para os propósitos deste artigo, é um número que pode ser fatorado em fatores primos suficientes, cada um pequeno o bastante para que nosso ataque funcione. A definição formal de Número Suave é um pouco diferente e não é relevante para nós.
Intuitivamente, isso é feito "atacando" cada um dos fatores primos separadamente. Dado um ponto gerador `𝐺` que forma um "círculo" muito grande, e algum ponto `𝑃` no "círculo" tal que `𝑃 = 𝑘𝐺`. O grande "círculo" pode ser desmontado em vários "círculos" pequenos, cada um do tamanho de um fator primo de `𝑛`. Em cada "círculo" pequeno, podemos mapear `G` e `P` para outros pontos correspondentes `G'` e `P'` localizados no "círculo" pequeno, que satisfazem `𝑃′ = 𝑘′𝐺′`. Como o "círculo" é pequeno, é relativamente fácil resolver o problema e encontrar `𝑘′`. Finalmente, podemos combinar todos os pequenos `𝑘′`s que encontramos no `𝑘` desejado no "círculo" original.
O algoritmo que realiza o que descrevi é chamado de Algoritmo de Pohlig-Hellman. Sua complexidade de tempo é $O(\sqrt{p_{max}})$, onde $p_{max}$ é o maior fator primo na decomposição de `𝑛`. Isso também faz sentido, porque a parte mais "pesada" do algoritmo é resolver o problema ECDLP no maior "círculo" entre os "círculos" menores. Por exemplo, `n` pode ser um número de 128 bits e se decompõe em fatores primos tais que o maior deles é um número de 30 bits. O algoritmo reduz a complexidade de resolver o problema de $2^{64}$ para $2^{15}$, transformando-o de inviável para viável.
Felizmente, a função `discrete_log` do SageMath executa esse algoritmo em sua implementação. Para executar o ataque, você pode simplesmente chamar a função:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
Neste trecho de código, definimos uma curva elíptica e um gerador nela, e imprimimos os fatores primos da sua ordem. A saída é:``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
Pode-se ver que, embora a ordem do gerador tenha 128 bits, ela se decompõe em fatores primos de tal forma que o maior fator primo tem 32 bits.
Depois disso, assim como no ataque anterior - escolhemos uma chave privada aleatória, calculamos uma chave pública a partir dela e, então, dados o gerador e a chave pública, calculamos a chave privada e verificamos se ela está correta.
Embora estejamos prontos, ainda não vimos como os “pequenos” círculos são definidos, como mapear os pontos `𝐺` e `𝑃` para seus pontos correspondentes `𝐺′` e `𝑃′` e como combinar todas as pequenas soluções em uma grande solução. Vou tentar explicar isso intuitivamente aqui, porque o próximo ataque também se baseia nessa parte.
Suponha que temos um “círculo” de ordem `3𝑥5𝑥7 = 105`, e seu gerador é `𝐺`. Definiremos um ponto `𝐺′ = (5𝑥7)𝐺 = 35𝐺` e observaremos o “círculo” gerado a partir dele. Se partirmos de `𝐺′` um “passo”, ou seja, somarmos `𝐺′` a ele mesmo, será como avançar 35 passos a partir do ponto `35𝐺` no “círculo” original, e chegaremos ao ponto `2𝐺′ = 70𝐺`. Se avançarmos mais um “passo”, chegaremos ao ponto `3𝐺′ = 105𝐺 = 𝒪`, e se avançarmos a partir dele mais um “passo”, chegaremos ao ponto `4𝐺′ = 35𝐺 = 𝐺′`, ou seja, de volta ao ponto inicial. O “círculo” formado por `G′` tem ordem `3`, e isso não é coincidência, pois em um “círculo” de ordem `105` é possível dar exatamente `3` “passos” do tamanho `35`. Da mesma forma, poderíamos criar um “círculo” de ordem `5` definindo o ponto `𝐺′ = (3𝑥7)𝐺 = 21𝐺`, e um círculo de ordem `5` definindo `𝐺′ = (3𝑥5)𝐺 = 15𝐺`.
Quando olhamos para isso pelo lado inverso, fica mais interessante. Suponha que no “círculo” original tenhamos dado `𝑛` passos a partir do ponto `G` e tenhamos chegado ao ponto `𝑛𝐺`. Se também no “círculo” pequeno dermos `𝑛` passos a partir do ponto `𝐺′`, chegaríamos ao ponto `𝑛′𝐺′` tal que `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`. E por que isso é interessante? Porque a ordem de `𝐺′` é muito menor do que a ordem de `𝐺` e, portanto, dados `𝐺′` e `𝑛′𝐺′`, podemos encontrar `𝑛′` com relativa facilidade. Se fizermos isso, e também para os outros dois fatores primos da ordem do “círculo”, que são `5` e `7`, teríamos os seguintes valores:
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
Com base nesses três valores, `𝑛` pode ser facilmente encontrado usando o Teorema Chinês dos Restos, e assim resolver o problema original.
## A Ordem Do Gerador É Quase Um Número Suave, E A Chave Privada É Pequena
Suponha que, de forma semelhante ao ataque anterior, obtenhamos uma curva em que a ordem do gerador se decompõe em fatores primos, mas, desta vez, o maior fator primo é grande demais para que seja prático resolver o ECDLP dela. Por exemplo, se a ordem do gerador for `256 bit`, mas o maior fator primo for `128 bit`.
O Algoritmo de Pohlig-Hellman exigirá cerca de $O(2^{64})$ operações para encontrar a chave privada, o que é inviável.
Se soubermos que a chave privada usada é relativamente pequena, ela ainda pode ser encontrada com eficiência.
Vamos supor que a chave privada tenha `64 bit` (em vez de `256 bit`). Quando a chave pública é criada, o gerador é multiplicado pela chave privada e você obtém algum ponto no “círculo” que o gerador cria. Embora o “círculo” tenha cerca de $2^{256}$ pontos, esse ponto “cairá” em algum lugar entre os “primeiros” $2^{64}$ pontos. Não há “interação” entre a chave privada e os pontos do “círculo” que correspondem a valores maiores.
É possível executar o algoritmo de Pohlig-Hellman, mas “descartar” os “círculos” grandes demais, desde que o produto das ordens dos “círculos” restantes seja pelo menos do tamanho da chave privada. Se forem encontrados fatores primos pequenos suficientes, cujo produto seja de pelo menos `64 bit`, então os “círculos” correspondentes serão suficientes para realizar o mesmo ataque que vimos anteriormente.
Se antes tínhamos uma vida fácil em termos de escrita de código, desta vez teremos que implementar as coisas nós mesmos, porque a função `discrete_log` do SageMath não sabe que queremos “descartar” alguns dos fatores primos. O trecho de código a seguir faz isso:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
Neste trecho de código definimos uma curva elíptica e um gerador nela, e imprimimos os fatores primos da sua ordem. A saída é:``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
A ordem do gerador é `256 bit`, e ela se decompõe em vários fatores primos, de modo que os dois maiores sejam `77 bit` e `107 bit`. Eles são grandes o suficiente para que seja impraticável resolver o ECDLP. Em seguida, uma chave privada de `64 bit` é gerada aleatoriamente, e uma chave pública é calculada. No próximo passo, "coletamos" fatores primos suficientes até obtermos uma ordem com comprimento de pelo menos `64 bit`. A saída é:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
Pode-se ver que os dois maiores fatores são redundantes, e o maior fator que nos resta é 40 bit. No próximo passo, para cada um dos fatores que nos restam, calculamos os pontos 𝐺′ e 𝑃′ como expliquei anteriormente, e para cada um deles resolvemos o ECDLP. Os resultados e os fatores primos são mantidos nas listas subsolutions e subgroups, respetivamente. Finalmente, todos os resultados são combinados usando o Teorema Chinês do Resto na chave privada, e verificamos que esta está de facto correta.
Examinando a definição de adição de pontos em curvas elípticas, notamos uma propriedade interessante: na adição de pontos não se usa o valor 𝑏, mas apenas os valores 𝑎 e 𝑝. Isto significa que adicionar pontos que estão numa curva também pode ser significativo para outra curva, que difere dela apenas nesse valor de 𝑏. Isto é, claro, também verdadeiro para multiplicar um ponto por um número. Se o utilizador não verificar que o ponto que recebe da outra parte como chave pública está de facto na sua curva, então fica exposto a um Ataque de Curva Inválida.
Suponhamos que duas partes concordaram numa determinada curva elíptica $E_1$. Um atacante pode criar uma curva maliciosa $𝐸_2$, que tem os mesmos valores 𝑎 e 𝑝 que $𝐸_1$ mas um valor 𝑏 diferente. Na curva $𝐸_2$, o atacante escolherá um ponto 𝑃 cuja ordem seja pequena, por exemplo 3. Claro que o ponto 𝑃 não estará em $𝐸_1$, porque satisfaz uma equação com um valor 𝑏 diferente do de $𝐸_1$. O atacante enviará o ponto 𝑃 como sua chave pública ao utilizador. Digamos que o utilizador não se preocupa em verificar que o ponto que recebe está de facto na curva $𝐸_1$ que as partes combinaram. O utilizador pegará na chave pública que recebeu do atacante, multiplicá-la-á pela sua chave privada e chegará a um ponto que deverá ser o segredo partilhado, como vimos na definição do protocolo ECDH. Do ponto de vista do utilizador, ele calculará a operação de multiplicação na curva $𝐸_1$. Mas como o ponto 𝑃 não está de todo nela, e sim em $𝐸_2$, o utilizador estará, na realidade, a calcular a operação de multiplicação na curva $𝐸_2$. Depois, o utilizador usará o ponto de segredo partilhado para continuar a comunicação com o atacante. Suponhamos que as partes usam a coordenada 𝑥 do ponto como chave de encriptação AES. Nesse caso, o utilizador encriptará alguma mensagem e enviá-la-á ao atacante.
Como a ordem de 𝑃 é 3, existem apenas 3 possibilidades para o ponto partilhado que o utilizador pode calcular. O atacante percorrerá esses pontos possíveis e descobrirá qual deles corresponde à chave que descriptografa com sucesso a mensagem encriptada que o utilizador enviou. Dado esse ponto e o ponto inicial 𝑃, o atacante pode deduzir o resto da divisão da chave privada do utilizador pelo número 3. O atacante pode enviar ao utilizador pontos 𝑃 maliciosos adicionais, com ordens crescentes, por exemplo 5, 7, e assim por diante. Desta forma, o atacante pode recolher valores suficientes que representam restos de divisões da chave privada do utilizador por números pequenos. Finalmente, o atacante pode usar o Teorema Chinês do Resto para calcular a chave privada do utilizador, da mesma forma que vimos no ataque anterior.
Eis uma explicação mais intuitiva: um atacante pode fornecer ao utilizador um ponto num "círculo" muito pequeno, por exemplo de comprimento 2. O utilizador avançará neste "círculo" qualquer número de passos e chegará ao ponto de destino. O atacante conhece o ponto de destino do utilizador, que pode ser uma de 2 possibilidades. Portanto, o atacante consegue dizer se o utilizador deu um número par ou ímpar de passos no círculo. O atacante pode fornecer ao utilizador pontos adicionais em "círculos" de comprimentos 3, 5, 7, e assim por diante. Até que o atacante tenha fatores suficientes, cada um contendo pouca informação sobre o número de passos que o utilizador deu. Finalmente, o atacante pode combinar todos esses valores no número exato de passos que o utilizador deu, que é a sua chave privada.
O código a seguir demonstra o ataque:```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
Neste trecho de código, uma curva e um gerador são selecionados, o usuário gera aleatoriamente uma chave privada e a utiliza em todos os usos do protocolo ECDH. A função `find_curves_with_small_subgroup` encontra pares de pontos e ordens, tais que a ordem de cada ponto é relativamente pequena, e o ponto está em alguma curva que difere da curva original apenas pelo valor de `𝑏`. O código gera esses pares até que pares suficientes sejam encontrados. Para cada par, a chave pública é enviada ao usuário e uma mensagem criptografada é recebida dele.
Uma busca exaustiva (força bruta) é realizada sobre a mensagem criptografada para encontrar o valor da chave privada do usuário, módulo a ordem atual. Todos esses resultados são salvos e, por fim, usamos o Teorema Chinês do Resto para calcular a chave privada do usuário e verificar se ela está correta. Neste caso, as partes concordaram que a comunicação será feita em AES, com a chave de criptografia sendo a coordenada `x` do ponto secreto compartilhado, e o IV sendo sua coordenada `𝑦`.
A complexidade do ataque é $𝑂(𝑛_{𝑚𝑎𝑥})$ onde $𝑛_{𝑚𝑎𝑥}$ é a maior ordem entre as ordens dos pontos maliciosos. Isso ocorre porque a parte mais "pesada" do ataque é a força bruta sobre o maior "círculo" entre os pequenos "círculos", e, para a sorte do atacante, ele pode controlar esse valor quase completamente. Portanto, este ataque é relativamente eficiente em termos de complexidade. Como mencionado, a raiz do problema neste caso é que o usuário não verifica se o ponto que recebeu está sequer na curva com a qual está trabalhando. Além disso, o usuário usa a mesma chave privada em cada novo uso do ECDH, o que não é tão seguro.
## A Curva É Singular
Uma das propriedades importantes que uma curva elíptica deve ter para ser criptograficamente segura é ser não singular. Uma curva não singular é uma curva cujo determinado valor, chamado de "discriminante" da curva, é não nulo. Isso vale quando seus parâmetros `𝑎` e `𝑏` satisfazem a desigualdade:
$4a^3 + 27b^2 ≠ 0$
Uma curva que não satisfaz essa desigualdade possui um ponto "problemático" chamado de `ponto singular`. Existem dois tipos desses pontos: nó e cúspide. Um ponto do tipo nó existe em uma curva que tem uma espécie de laço que se intersecta no ponto singular, e duas tangentes diferentes à curva podem ser traçadas passando por esse ponto.
Um ponto do tipo cúspide é um ponto onde a curva é "afiada", como se duas linhas saíssem dela, mas há apenas uma tangente à curva nesse ponto.
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
Em um ponto do tipo nó existe uma raiz dupla, então a equação da curva pode ser escrita como:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
A curva pode ser "deslocada" para a esquerda substituindo a variável $x$ pela variável $(𝑥 + 𝑥_0)$ e alcançar a forma:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
Agora o ponto singular está na origem dos eixos. O valor numérico de $t = (x_0-x_1)$ pode ser usado para criar um mapeamento entre pontos na curva e inteiros, de modo que a operação de adição entre pontos na curva seja equivalente à operação de multiplicação entre números. Para cada ponto `(𝑥, 𝑦)`, associaremos o número
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$. Em particular, a um par de pontos `𝐺` e `𝑄` tal que `𝑄 = 𝑛𝐺`, podemos mapear números `𝑔` e `𝑞` tais que $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$, e isso é um problema de DLP "normal". Para ilustrar esse processo, adicionei um link para um exemplo com números pequenos nas referências no final do artigo. No mapeamento que fizemos, usamos a equação das retas $y+\sqrt{t}x$ e $y-\sqrt{t}x$, e essas são as retas que correspondem às duas tangentes que podem ser traçadas no ponto singular (depois de "deslocarmos" a curva), o que é basicamente a razão pela qual esse ataque pode ser usado.
Esse tipo de problema de DLP pode ser resolvido de forma eficiente com a ajuda do algoritmo de Pohlig-Hellman, que já vimos anteriormente, porque ele também pode ser usado em inteiros em vez de pontos na curva. No contexto de pontos, vimos que o algoritmo é útil quando a ordem do gerador é um número liso. Diferentemente de um "círculo" de pontos em uma curva, que pode ter qualquer ordem, no campo dos inteiros módulo um número primo `𝑝` a ordem é `𝑝 − 1`. Se `𝑝 − 1` for um número liso, então o algoritmo resolverá o problema de DLP de forma eficiente, encontrando assim a chave privada `n`.
O trecho de código a seguir faz isso:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
Neste trecho de código, definimos os parâmetros de uma curva elíptica e verificamos que ela é de fato singular. Encontramos as raízes do polinômio correspondente à curva e identificamos qual delas é a raiz dupla. Usamos a raiz dupla para "mover" a curva e chegamos aos pontos "movidos" 𝐺 e 𝑄. Em seguida, calculamos $\sqrt{t}$ a partir das raízes que encontramos e o usamos para mapear os pontos 𝐺 e 𝑄 para os números 𝑔 e 𝑞. Imprimimos a decomposição de 𝑝 − 1 em seus fatores primos (para verificar que o DLP pode de fato ser resolvido com eficiência). Finalmente, calculamos o DLP e interpretamos o resultado como uma string.
A saída é: ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
Desta vez, escondi uma mensagem na própria chave privada. Deve-se notar que, por ser uma curva singular, não é possível no SageMath criá-la de forma normal, definir pontos nela e realizar operações com eles como fizemos antes. Neste código, defini as coordenadas dos pontos como variáveis constantes. Para calcular o ponto `𝑄`, multipliquei a chave privada pelo gerador usando minha própria implementação do algoritmo Double And Add.
## A curva é supersingular
Dada uma curva elíptica módulo `𝑝` e um gerador cuja ordem é `𝑛`, o grau de mergulho da curva em relação ao gerador é definido como o menor número `k` que satisfaz a equação $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$. Com certas transformações, o problema ECDLP pode ser reduzido a um problema DLP em um corpo de ordem $𝑝^𝑘$. O valor `𝑘` geralmente é um número muito grande (aproximadamente do mesmo tamanho que o próprio `𝑝`), mas quando é relativamente pequeno (digamos, menor que `6`), a curva é chamada de `supersingular` e torna-se viável resolver esse problema DLP com eficiência. Esse ataque é chamado de ataque MOV, nomeado em homenagem aos seus três inventores (Menezes-Okamoto-Vanstone).
As transformações que mencionei são funções que recebem dois pontos e retornam algum número no corpo dos números complexos. As transformações que podem ser usadas são o Weil Pairing ou o Tate Pairing, e vamos usá-las como uma caixa-preta. Tal transformação `𝑇` satisfaz a seguinte propriedade para cada par de pontos `𝑃`, `𝑄`:
$T(mP, nQ)=T(P,Q)^{mn}$
Portanto, dados dois pontos `𝐺` e `𝑄 = 𝑚𝐺`, podemos selecionar aleatoriamente um terceiro ponto `𝑅` e calcular os dois valores: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
A partir daqui, podemos resolver o problema DLP para `𝑔` e `𝑞` em um corpo de ordem $p^k$, encontrando assim a chave privada `𝑚`. Incluí um link para uma explicação mais detalhada da matemática por trás desse ataque, nas referências no final do artigo.
O trecho de código a seguir realiza esse ataque:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
Neste trecho de código definimos uma curva e seu gerador, e calculamos seu valor de Embedding Degree, que é 2 neste caso, portanto é prático realizar o ataque. Definimos uma curva idêntica à curva original, exceto que os cálculos são feitos módulo $𝑝^𝑘$ em vez de módulo $𝑝$. Os dois pontos 𝐺 e 𝑄 também estão na nova curva. Então encontramos um terceiro ponto cuja ordem divide 𝑛.
Usando o terceiro ponto, mapeamos os pontos 𝐺 e 𝑄 para os números 𝑔 e 𝑞 e calculamos o logaritmo discreto para eles. Finalmente, verificamos se o resultado obtido está de fato correto.
A saída é:``` Found k: 2 Calculating private key... success! The private key is: Festivus
Do ponto de vista computacional, hoje existem algoritmos de Index Calculus que podem resolver o problema DLP de forma relativamente eficiente, e o fazem com complexidade de $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$. Essa expressão pode parecer assustadora, mas comparada aos algoritmos ECDLP cuja complexidade é $O(\sqrt{p})=e^{O(log\ p)}$, pode-se ver que é mais fácil resolver o problema DLP, assumindo que o Grau de Incorporação (denotado por `𝑘`) seja de fato pequeno.
## A Curva É Anômala
Se uma determinada curva tem a propriedade de que a ordem da curva (o número de pontos sobre ela) é exatamente igual ao módulo `𝑝`, então ela é chamada de `Curva Anômala` e é vulnerável a um ataque chamado Ataque de Smart. Esse ataque usa `números 𝑝-ádicos`. Tal número pode ser representado como uma soma de potências de `p` (positivas e negativas) com coeficientes. Formalmente, tal número `s` é uma série da forma:
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
Quando os coeficientes são inteiros no intervalo $0 ≤ 𝑎_𝑖 < 𝑝$, e a soma pode ser infinita na direção das potências positivas de `𝑝`. Nesses números, "olhamos" os dígitos da direita para a esquerda em vez de da esquerda para a direita e, portanto, tal série pode convergir para algum valor. Esses números pertencem a um sistema numérico diferente daquele com o qual estamos familiarizados e se comportam de maneira muito diferente das regras matemáticas "normais". Um artigo inteiro e separado poderia ser escrito apenas sobre esse tópico e, para aqueles que se interessam por ele, incluí nas referências ao final do artigo um link para um vídeo que o apresenta de forma relativamente clara.
De qualquer forma, nesse ataque uma nova curva é criada a partir da curva dada, que é definida sobre os números p-ádicos. Dados dois pontos `𝐺` e `𝑄 = 𝑚𝐺` na curva original, mapeamos esses pontos para pontos correspondentes na nova curva. A partir das coordenadas dos pontos obtidos é fácil calcular `𝑚`.
O código a seguir executa o ataque:```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
Neste trecho de código, uma função de lift é definida, que recebe um ponto na curva original e faz corresponder a ele um ponto na nova curva. Em seguida, definimos uma curva elíptica e um gerador nela, e verificamos que a ordem da curva é de fato p. Escolhemos uma chave privada e calculamos a chave pública correspondente. Então realizamos o ataque. Definimos uma nova curva sobre os números p-ádicos e mapeamos os pontos originais 𝐺 e 𝑃 para os pontos correspondentes na nova curva usando a função de lift e multiplicando-os por 𝑝.
Para cada novo ponto, calculamos a razão entre sua coordenada 𝑥 e sua coordenada 𝑦. O quociente desses dois valores é a solução ECDLP dos pontos originais.
A saída é:``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
A razão pela qual esse cálculo funciona está relacionada ao fato de que o número de pontos na curva é exatamente `𝑝`. Essa propriedade nos permite realizar vários mapeamentos, o último dos quais mapeia pontos em uma curva sobre números 𝑝-ádicos para números módulo $p^2$. Esse mapeamento tem a propriedade de que a razão entre o par de números correspondentes aos dois pontos originais é exatamente o resultado do logaritmo dos dois pontos. Deixaremos todos esses mapeamentos como uma caixa-preta, mas no final do artigo adicionei referências às explicações matemáticas relevantes.
# Ataques ECDSA
## Não Aplicar Hash à Mensagem Antes de Assiná-la
Vimos que, no processo de assinatura de uma mensagem, primeiro o hash da mensagem é calculado, e os bits mais altos do hash são usados no cálculo da assinatura. Vamos supor que, em alguma implementação de assinatura e verificação de assinatura, essa etapa de hash seja ignorada e, em vez de usar os bits mais altos do hash, os bits sejam retirados da mensagem como ela é. Nessa implementação, a única parte da mensagem que afeta sua assinatura é o início da mensagem. Em outras palavras, se tivermos uma mensagem e sua assinatura, podemos manter o início da mensagem e alterar o restante dela, e a assinatura permanecerá válida. É um ataque realmente simples.
Suponha, por exemplo, que você escreva a seguinte mensagem ao seu banco e a assine sem aplicar hash:```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
O banco verificará esta mensagem com sucesso e executará a ação. Algum ... atacante ... poderia criar a seguinte mensagem:``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
E use a assinatura que você acabou de criar. A assinatura também será válida para esta mensagem, e o banco realizará a ação. Não é bom (bem, depende de quem).
O código a seguir demonstra o ataque:```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
Neste trecho de código, a biblioteca ecdsa é usada, juntamente com uma curva conhecida. Definimos uma classe que deveria implementar uma função hash, mas não o faz, e em vez disso deixa a mensagem como está. Portanto, ao assinar uma mensagem, apenas os primeiros bits da mensagem original são usados, em vez dos bits do seu hash. Em seguida, a mensagem é assinada e verificada com sucesso. Uma mensagem maliciosa é então criada, e o código verifica que a assinatura da mensagem original também corresponde à mensagem maliciosa.
Em tal cenário, podemos não ter obtido a chave privada para gerar nossas próprias assinaturas novas, mas, dada uma assinatura, podemos assinar quantas mensagens quisermos, desde que elas comecem com o mesmo prefixo.
k em Assinaturas DiferentesComo parte do processo de assinatura de mensagens, o usuário é obrigado a gerar aleatoriamente um valor 𝑘 e usá-lo para assinar a mensagem. É muito importante usar valores 𝑘 diferentes em assinaturas diferentes. Caso contrário - dadas duas mensagens assinadas em que o usuário usou o mesmo valor 𝑘 em vez de gerá-lo novamente, um atacante poderia calcular a chave privada do usuário.
Como mencionado, durante a assinatura de mensagens, o usuário envia publicamente $r=x_1\ \ \ \ (mod\ p)$ e $s=k^{-1}(z+rd_A)$. Supondo que o usuário assinou duas mensagens diferentes correspondentes a $𝑧_1$ e $𝑧_2$, e enviou publicamente dois pares de valores $𝑟, 𝑠_1$ e $𝑟, 𝑠_2$, ou seja, usou o mesmo valor 𝑘 nessas duas assinaturas. Observamos que:
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
A partir disso, o atacante pode encontrar o valor de 𝑘 calculando:
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
Depois que o atacante encontra 𝑘, ele pode calcular a chave privada do usuário a partir de uma das assinaturas. Observe que:
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
Dados os valores de 𝑟, 𝑠 e 𝑧 de uma mensagem e sua assinatura, e o valor de 𝑘 que o atacante encontrou, o atacante pode calcular $d_A=r^{-1}(ks-z)$. A partir desse ponto, o atacante pode assinar qualquer mensagem que desejar, em nome do usuário cuja chave privada ele obteve.
O seguinte trecho de código executa esse ataque:```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
Neste trecho de código, a biblioteca `ecdsa` é utilizada, juntamente com uma curva conhecida. Definimos uma chave privada e a usamos para assinar duas mensagens. O valor de `𝑘` é gerado aleatoriamente, mas permanece o mesmo para as duas assinaturas. Dadas as duas mensagens e suas assinaturas, o código realiza o cálculo que vimos para encontrar `𝑘`. Por fim, usamos o valor de `𝑘` que encontramos para calcular a chave privada como vimos. A saída é:```
Success!
The secret is: Mistakes were made
É interessante notar que esse ataque foi realmente usado em 2010, quando a Sony implementou de forma insegura o seu mecanismo de assinatura no software do console PlayStation. A Sony usava um valor estático de 𝑘 para suas assinaturas, o que permitiu que atacantes obtivessem a chave privada da Sony usando o cálculo acima. Isso levou à capacidade de assinar qualquer código e fazer o PlayStation concordar em executá-lo. Posteriormente, essa capacidade foi usada para instalar jogos piratas e não oficiais no console.
k de Forma InseguraSe o usuário escolher 𝑘 de forma insuficientemente aleatória, a chave privada pode ser descoberta. Por exemplo, se o atacante souber que 𝑘 está em um intervalo muito pequeno de valores, ou se alguns bytes de 𝑘 forem conhecidos pelo atacante, então é possível, por meio de uma simples força bruta, encontrar a chave privada do usuário a partir de uma única mensagem assinada. O atacante executará o cálculo que vimos no ataque anterior para os diferentes valores de 𝑘, até alcançar o valor correto e obter a chave privada a partir dele.
Para superar esse problema, às vezes os usuários geram aleatoriamente algum valor, calculam seu hash com alguma função hash e usam o resultado como 𝑘. Esse método pode causar problemas. Suponha, por exemplo, que a ordem do gerador 𝑛 seja 256 bit, e a função hash selecionada seja SHA-1. A saída dessa função é um número de 160 bit. Em cálculos módulo 𝑛, sabe-se que o valor de 𝑘 contém 96 zeros no início, o que significa que 𝑘 é um número relativamente pequeno. Nessa situação, diz-se que os valores de 𝑘 são biased, e, dadas várias mensagens assinadas com a mesma chave privada, a chave privada pode ser encontrada.
O ataque é baseado em uma estrutura algébrica chamada Lattice. Informalmente, um lattice pode ser pensado como um conjunto de vetores em um espaço 𝑚-dimensional, que pode ser expresso como uma combinação linear de vetores "base" com coeficientes inteiros. Matematicamente, se $\{b_1,\dots,b_d\}$ são os vetores base sobre $ℝ^𝑚$, então o Lattice correspondente a eles é $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$. Nessa estrutura, existe o problema conhecido: dada a base de um lattice, encontrar o vetor mais curto que existe no lattice. Nesse contexto, informalmente, um "vetor curto" é um vetor cujos elementos estão o mais próximo possível de zero. Esse problema é chamado de Shortest Vector Problem (SVP) e é considerado NP-difícil. Existem algoritmos que resolvem um problema semelhante, porém mais fácil - encontrar algum vetor curto, ou seja, um vetor relativamente "próximo" ao vetor mais curto no lattice. Esse problema é chamado de Closest Vector Problem (CVP), e um dos algoritmos que o resolve é chamado de algoritmo Lenstra-Lenstra-Lovász (LLL). Neste ataque, usaremos esse algoritmo como uma caixa preta.
Dadas 𝑑 mensagens assinadas, é possível construir um lattice que contém o vetor $(𝑘_1, \dots , 𝑘_𝑑)$, onde cada elemento do vetor é um valor 𝑘 que corresponde a uma assinatura. O algoritmo LLL encontrará uma aproximação do vetor mais curto nesse lattice. Como se sabe que os valores de 𝑘 são pequenos, há uma alta probabilidade de que o vetor curto encontrado pelo algoritmo contenha pelo menos um elemento k correto. Uma vez encontrado um 𝑘 correto, a chave privada pode ser calculada como vimos no ataque anterior.
Para construir esse lattice, é necessário definir seus vetores base. Incluí nas referências no final do artigo um link para um artigo que explica como esses vetores base são definidos. Tecnicamente, os vetores base do lattice podem ser representados como uma matriz, de modo que cada linha dela consista nos elementos de um vetor base. Para melhorar a precisão do algoritmo LLL, recomenda-se adicionar a essa matriz duas colunas que contenham informações sobre o tamanho esperado dos valores de 𝑘 e a razão entre 𝑘 e 𝑛. Essa melhoria também é explicada na referência que anexei. O trecho de código a seguir demonstra esse ataque:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
Neste trecho de código, uma curva padrão é usada, uma chave privada é selecionada e a chave pública correspondente é calculada a partir dela. 3 mensagens são criadas e assinadas com 3 valores aleatórios de `k` que são resultado da função hash SHA-1. Em seguida, criamos a matriz correspondente à base do reticulado, conforme explicado no artigo, e executamos o algoritmo LLL sobre ela. Depois, percorremos as linhas da matriz resultante e verificamos se um valor correto de algum `𝑘` é encontrado em uma delas.
A verificação é realizada calculando a chave privada a partir do possível `𝑘`, como vimos no ataque anterior, e verificando se a chave recebida está de fato correta. Por fim, garantimos que a chave privada encontrada está de fato correta. A saída é:```
success!
The secret is: I am Jack's broken heart
A complexidade deste ataque é igual à complexidade do algoritmo LLL, que é $O(d^6\ \log^3B)$, onde 𝐵 indica o comprimento do viés de 𝑘 ($2^{160}$
no nosso caso), e 𝑑 indica o número de mensagens assinadas (3 no nosso caso). Surge a questão de qual é o número mínimo de mensagens assinadas que precisamos usar para conseguir executar o ataque. A resposta é
$\displaystyle d=O(\frac {\log n}{\log n-\log B})$ onde 𝑛 é a ordem do gerador e 𝐵 é o viés. Uma explicação para isso aparece no segundo link nas referências que anexei a este tópico no final do artigo.
Na prática, uma variação deste ataque também pode ser executada em casos em que os bits superiores de 𝑘 são conhecidos, ou apenas quaisquer bits de 𝑘. O ataque pode ser executado mesmo se o valor de apenas um bit for conhecido, ou mesmo se o valor de apenas um bit for conhecido com probabilidade maior que 50%! Mas, é claro, nesses casos, são necessárias muito mais mensagens assinadas para realizar o ataque.
Vimos que, no processo de verificação de assinatura, a parte que assina envia o par de valores 𝑟 e 𝑠 para a parte que verifica. Em navegadores que implementam o protocolo HTTPS, por exemplo, é comum enviar esse par de valores em um certificado, que também pode conter dados sobre a curva que a parte que assina utilizou. A parte que verifica precisa garantir que os dados da curva encontrados no certificado correspondam à curva previamente acordada. Se não corresponderem, isso pode ser problemático.
Suponha que em uma determinada curva Alice tenha uma chave privada $d_A$ e uma chave pública $𝑃_𝐴$ que corresponda a ela, o que significa que $𝑃_𝐴 = 𝑑_𝐴𝐺$ para o gerador 𝐺 nesta curva. Com a chave privada $𝑑_𝐴$, Alice pode assinar suas mensagens como vimos na definição do protocolo ECDSA. Suponha que a parte que verifica a assinatura também receba o gerador 𝐺 do usuário e não verifique se o gerador recebido do usuário é de fato o gerador acordado. Um atacante pode enviar como gerador o ponto que é a chave pública de Alice, $𝐺^′ = 𝑃_𝐴$. O atacante escolherá como chave privada "falsa" o valor $𝑑_𝐴^′ = 1$ e, portanto, é claro que $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$. Isso significa que o atacante pode "provar" que possui a chave privada que corresponde à chave pública de Alice. Assim, um atacante pode criar qualquer mensagem que desejar e calcular para ela um par de valores 𝑟 e 𝑠 da maneira usual com $𝑑_𝐴^′$, e a assinatura resultante será verificada com sucesso.
Intuitivamente, no processo de verificação de assinatura, a parte que assina prova que é de fato a "proprietária" da chave pública, que é na verdade um ponto de "destino" na curva. Isso ocorre porque somente o signatário sabe quantos passos dar a partir do ponto inicial para alcançar o ponto de destino. Se a parte que verifica não verificar se o ponto inicial recebido do usuário é de fato o ponto inicial verdadeiro, então um atacante pode decidir que o ponto inicial é o ponto de destino e que o número de passos a partir dele é zero. Todas as outras partes da verificação de assinatura permanecem as mesmas, e a assinatura será verificada com sucesso. Esse ataque é chamado de Curveball.
Esse ataque pode ser generalizado com valores adicionais. O atacante escolherá algum valor 𝑥 e calculará $𝐺^′ = 𝑥𝑃_𝐴$. A chave privada falsa será $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$. Então, claramente, vale que $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$.
O código a seguir demonstra o ataque:```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)
Neste trecho de código escolhemos um gerador conhecido, uma chave privada e uma chave pública. Assinamos uma mensagem e garantimos que ela foi verificada com sucesso. Em seguida, criamos uma chave privada falsa e um gerador falso, de modo que ambos correspondam à chave pública original. Uma mensagem maliciosa é assinada com a chave falsa e, por fim, a assinatura falsa é verificada com sucesso com a chave pública original. O problema deste código é que o algoritmo de verificação não verifica se o gerador `𝐺` corresponde à chave pública. Embora neste ataque não tenhamos descoberto a chave privada do usuário, um atacante pode explorar a implementação incorreta da verificação de assinaturas e criar uma assinatura que seja verificada com sucesso. No entanto, o atacante não pode criar assinaturas "reais" que sejam de fato verificadas com sucesso em uma implementação correta da verificação de assinaturas.
É interessante notar que esta é uma vulnerabilidade real que existia na arquitetura Windows CryptoAPI. Na função responsável por verificar a assinatura de um certificado, havia verificação insuficiente dos parâmetros da curva, nos casos em que eles eram incluídos no próprio certificado. Em particular, não havia verificação de que o gerador é de fato o gerador que corresponde à chave pública. Um atacante poderia criar certificados falsos considerados confiáveis porque pareciam ter sido assinados por uma Autoridade Certificadora confiável. Isso era feito adicionando campos de curva maliciosos ao certificado e escolhendo o gerador da maneira que descrevi. A vulnerabilidade foi descoberta pela organização NSA, corrigida em 2020 e recebeu o número CVE-2020-0601.
# Conclusão
## Visão Geral dos Ataques a ECDH
| Tipo de Problema | O Problema | O Ataque | Como o Ataque Funciona | Complexidade do Ataque |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Selecionar uma curva com um gerador inseguro | A ordem do gerador `n` é pequena demais | Baby-Step Giant-Step | Encontro no Meio (Meet In The Middle) | $𝑂(\sqrt n)$ |
| Selecionar uma curva com um gerador inseguro | A ordem do gerador `n` é um número suave (smooth) | Pohlig-Hellman | Decompor `𝑛` em fatores primos, atacar cada um deles separadamente e combinar os resultados usando o Teorema Chinês do Resto | $O(\sqrt{p_{max}})$ em que $p_{max}$ é o maior fator primo na decomposição de `𝑛` |
| Selecionar uma curva com um gerador inseguro + selecionar uma chave privada insegura | A ordem do gerador `n` é quase um número suave, e a chave privada é pequena | Pohlig-Hellman Aprimorado | Decompor `𝑛` em fatores primos, descartar fatores grandes demais, atacar cada um deles separadamente e combinar os resultados usando o Teorema Chinês do Resto | $O(\sqrt{p_{max}})$ em que $p_{max}$ é o maior fator primo na decomposição de `𝑛` |
| Implementação incorreta de ECDH | Não verificar se um ponto está na curva | Ataque de Curva Inválida | Enviar pontos com ordens pequenas em curvas maliciosas como chave pública, atacar cada um deles separadamente e combinar os resultados usando o Teorema Chinês do Resto | $𝑂(𝑛_{𝑚𝑎𝑥})$ em que $𝑛_{𝑚𝑎𝑥}$ é a maior ordem entre as ordens dos pontos maliciosos |
| Selecionar parâmetros de curva de forma insegura | A curva é singular | Reduzir ECDLP a DLP | Mapear pontos para números de uma forma que converte a adição de pontos em multiplicação de inteiros | $O(\sqrt{p_{max}})$ em que $p_{max}$ é o maior fator primo na decomposição de $(p-1)$ |
| Selecionar parâmetros de curva de forma insegura | A curva é supersingular | Reduzir ECDLP a DLP | Mapear pontos para números de uma forma que converte a adição de pontos em multiplicação de inteiros | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ em que `k` é o grau de imersão (embedding degree) em relação ao gerador |
| Selecionar parâmetros de curva de forma insegura | A curva é anômala | Ataque de Smart | Uma série de mapeamentos entre pontos em uma curva para pontos em uma curva sobre números `p-adic`, e de volta para inteiros | $O(1)$ |
## Visão Geral dos Ataques a ECDSA
| Tipo de Problema | O Problema | O Ataque | Como o Ataque Funciona | Complexidade do Ataque |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| Implementação incorreta de assinatura e verificação | Não aplicar hash na mensagem antes de assiná-la | Dada uma mensagem assinada, forjar mensagens adicionais que correspondem à mesma assinatura | Manter o prefixo da mensagem como está e modificar o restante dela | $O(1)$ |
| Uso incorreto do algoritmo de assinatura | Reutilizar o mesmo valor de `k` em assinaturas diferentes | Encontrar a chave privada do usuário | Encontrar o valor de `k` e calcular a chave privada do usuário a partir dele | $O(1)$ |
| Uso incorreto do algoritmo de assinatura | Gerar valores de `k` de forma insegura | Dadas várias mensagens assinadas, encontrar a chave privada do usuário | Reduzir o problema a encontrar um vetor curto em um reticulado (lattice), encontrar o valor de `k` e calcular a chave privada do usuário a partir dele | $O(d^6\ \log^3B)$ em que `B` é o viés (bias) de `k`, e `d` é o número de mensagens assinadas |
| Implementação incorreta da verificação | Não verificar se o gerador é válido | Forjar assinaturas que são verificadas com sucesso (Curveball) | Selecionar gerador e chave privada falsos que correspondam à chave pública de outro usuário | $O(1)$ |
## Proteção Contra Esses Ataques
Deve-se notar que, em ECDH, ambas as partes precisam concordar com a curva no início do protocolo. Se um usuário está se comunicando com um atacante, e o atacante é quem fornece os parâmetros da curva, então o atacante pode fornecer parâmetros inseguros. Como resultado, o atacante pode obter a chave privada do usuário. Se o usuário sempre usa a mesma chave privada, então o atacante pode descriptografar todas as conversas entre esse usuário e qualquer outro usuário. É por isso que é muito importante não permitir que usuários desconhecidos forneçam os parâmetros da curva se eles não puderem ser confiáveis. Além disso, você precisa garantir que todo ponto recebido de um usuário estrangeiro esteja de fato na curva acordada. E, é claro, você deve garantir que a curva selecionada em si não seja vulnerável a um dos ataques conhecidos que vimos. Além disso, é melhor usar uma nova chave privada sempre que você usar o protocolo ECDH.
Da mesma forma, em ECDSA, deve-se ter cuidado para implementar corretamente os algoritmos de assinatura e verificação. Não pule o hash da mensagem, a geração aleatória e segura do valor `𝑘` em toda vez que o protocolo for usado e, é claro, na verificação de assinatura, se o gerador for recebido do usuário — garanta que ele seja de fato o que foi acordado anteriormente.
## Referências
- Neste artigo usei gráficos do livro Understanding Cryptography, de Christof Paar:\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf
- Um site que ilustra como são as curvas elípticas criptográficas:\
https://graui.de/code/elliptic2/
- Explicação detalhada das operações de adição e multiplicação em curvas elípticas:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- Palestra sobre introdução a curvas elípticas e adição de pontos — por Christof Paar:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ
- Palestra sobre geradores, ECDLP, dificuldade dos problemas, ECDH, Double And Add — por Christof Paar:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY
- Explicação do Nível de Segurança de diferentes algoritmos de criptografia:\
https://en.wikipedia.org/wiki/Security_level
- Explicação de ECDH:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
- Explicação de ECDSA:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
- Explicação de assinaturas com ElGamal:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme
- Explicação do Teorema Chinês do Resto:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- Explicação da relação entre o discriminante de uma curva singular e o fato de ela ter uma raiz dupla:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity
- Um exemplo com números pequenos do mapeamento entre pontos e números em curvas singulares:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434
- Explicações sobre números 𝑝-ádicos:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA
- Explicação da matemática por trás do ataque MOV:\
https://risencrypto.github.io/WeilMOV/
- Explicações da matemática por trás do Ataque de Smart (é bastante complicado, você foi avisado):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf
- Explicação do ataque baseado em reticulados e do algoritmo LLL:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
O ataque é baseado na parte 4 de um artigo de Joachim Breitner e Nadia Heninger:\
https://eprint.iacr.org/2019/023.pdf
- Explicação do problema CVP:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)
- Explicação do algoritmo LLL:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm