Ataque cronometrado - Timing attack

Na criptografia , um ataque de temporização é um ataque de canal lateral no qual o invasor tenta comprometer um criptosistema analisando o tempo gasto para executar algoritmos criptográficos. Cada operação lógica em um computador leva tempo para ser executada e o tempo pode variar de acordo com a entrada; com medições precisas do tempo de cada operação, um invasor pode trabalhar de volta para a entrada. Encontrar segredos por meio de informações de tempo pode ser significativamente mais fácil do que usar criptanálise de texto simples conhecido, pares de texto cifrado. Às vezes, as informações de tempo são combinadas com a criptoanálise para aumentar a taxa de vazamento de informações.

As informações podem vazar de um sistema por meio da medição do tempo que leva para responder a certas perguntas. O quanto essas informações podem ajudar um invasor depende de muitas variáveis: projeto do sistema criptográfico, a CPU que executa o sistema, os algoritmos usados, diversos detalhes de implementação, contra-medidas de ataque de cronometragem, a precisão das medidas de cronometragem, etc. Ataques de cronometragem podem ser aplicados a qualquer algoritmo que tenha variação de tempo dependente de dados. Remover as dependências de tempo é difícil em alguns algoritmos que usam operações de baixo nível que freqüentemente exibem tempo de execução variado.

Os ataques de temporização costumam ser esquecidos na fase de design porque dependem muito da implementação e podem ser introduzidos involuntariamente com otimizações do compilador . A prevenção de ataques de temporização envolve o projeto de funções de tempo constante e o teste cuidadoso do código executável final.

Evasão

Muitos algoritmos criptográficos podem ser implementados (ou mascarados por um proxy) de uma forma que reduz ou elimina informações de temporização dependentes de dados, um algoritmo de tempo constante . Considere uma implementação em que cada chamada a uma sub-rotina sempre retorna exatamente em x segundos, onde x é o tempo máximo que leva para executar essa rotina em todas as entradas autorizadas possíveis. Em tal implementação, é menos provável que o tempo do algoritmo vaze informações sobre os dados fornecidos para essa chamada. A desvantagem dessa abordagem é que o tempo usado para todas as execuções torna-se o do pior caso de desempenho da função.

A dependência de dados de tempo pode resultar de um dos seguintes:

  • Acesso à memória não local, pois a CPU pode armazenar os dados em cache. O software executado em uma CPU com um cache de dados exibirá variações de tempo dependentes de dados como resultado de pesquisas de memória no cache.
  • Saltos condicionais . CPUs modernas tentam especulativamente executar saltos anteriores por adivinhação. Adivinhar errado (o que não é incomum com dados secretos essencialmente aleatórios) envolve um grande atraso mensurável enquanto a CPU tenta retroceder. Isso requer a gravação de código sem ramificação .
  • Algumas operações matemáticas "complicadas", dependendo do hardware real da CPU:
    • A divisão inteira quase sempre é um tempo não constante. A CPU usa um loop de microcódigo que usa um caminho de código diferente quando o divisor ou o dividendo é pequeno.
    • CPUs sem um deslocador de barril executa turnos e rotações em um loop, uma posição de cada vez. Como resultado, a quantidade a deslocar não deve ser secreta.
    • CPUs mais antigas executam multiplicações de maneira semelhante à divisão.

Exemplos

O tempo de execução para o algoritmo quadrado e multiplicação usado na exponenciação modular depende linearmente do número de bits '1' na chave. Embora o número de '1' bits por si só não seja informação suficiente para facilitar a localização da chave, as execuções repetidas com a mesma chave e entradas diferentes podem ser usadas para realizar análises de correlação estatística de informações de tempo para recuperar a chave completamente, mesmo por um atacante passivo. As medições de tempo observadas geralmente incluem ruído (de fontes como latência de rede ou diferenças de acesso à unidade de disco de acesso para acesso e as técnicas de correção de erros usadas para recuperar de erros de transmissão). No entanto, os ataques de temporização são práticos contra vários algoritmos de criptografia, incluindo RSA , ElGamal e o algoritmo de assinatura digital .

Em 2003, Boneh e Brumley demonstraram um ataque de temporização prático baseado em rede em servidores da web habilitados para SSL , com base em uma vulnerabilidade diferente relacionada ao uso de RSA com otimizações de teoremas de remanescentes chineses . A distância real da rede era pequena em seus experimentos, mas o ataque recuperou com sucesso uma chave privada do servidor em questão de horas. Essa demonstração levou à ampla implantação e uso de técnicas de ocultação em implementações SSL. Nesse contexto, a ocultação tem como objetivo remover as correlações entre a chave e o tempo de criptografia.

Algumas versões do Unix usam uma implementação relativamente cara da função de biblioteca crypt para hashing de uma senha de 8 caracteres em uma string de 11 caracteres. Em hardware mais antigo, esse cálculo demorava deliberada e mensuravelmente muito tempo: até dois ou três segundos em alguns casos. O programa de login nas primeiras versões do Unix executava a função crypt apenas quando o nome de login era reconhecido pelo sistema. Esta informação vazou através do tempo sobre a validade do nome de login, mesmo quando a senha estava incorreta. Um invasor pode explorar esses vazamentos aplicando primeiro a força bruta para produzir uma lista de nomes de login conhecidos como válidos e, em seguida, tentar obter acesso combinando apenas esses nomes com um grande conjunto de senhas conhecidas por serem usadas com frequência. Sem qualquer informação sobre a validade dos nomes de login, o tempo necessário para executar tal abordagem aumentaria em ordens de magnitude, tornando-o efetivamente inútil. Versões posteriores do Unix consertaram esse vazamento executando sempre a função crypt, independentemente da validade do nome de login.

Dois processos isolados com segurança em execução em um único sistema com memória cache ou memória virtual podem se comunicar causando deliberadamente falhas de página e / ou perdas de cache em um processo e, em seguida, monitorar as alterações resultantes nos tempos de acesso do outro. Da mesma forma, se um aplicativo é confiável, mas seu paging / cache é afetado pela lógica de ramificação, pode ser possível para um segundo aplicativo determinar os valores dos dados em comparação com a condição de ramificação monitorando as alterações de tempo de acesso; em exemplos extremos, isso pode permitir a recuperação de bits de chave criptográfica.

Os ataques Meltdown e Spectre de 2017 que forçaram os fabricantes de CPU (incluindo Intel, AMD, ARM e IBM) a redesenhar suas CPUs dependem de ataques de temporização. Desde o início de 2018, quase todos os sistemas de computador do mundo são afetados pelo Spectre, tornando-o o exemplo mais poderoso de um ataque temporizado da história.

Algoritmo

O código C a seguir demonstra uma comparação típica de string insegura que para o teste assim que um caractere não corresponde. Por exemplo, ao comparar "ABCDE" com "ABxDE", ele retornará após 3 iterações de loop: 

bool insecureStringCompare(const void *a, const void *b, size_t length) {
  const char *ca = a, *cb = b;
  for (size_t i = 0; i < length; i++)
    if (ca[i] != cb[i])
      return false;
  return true;
}

Em comparação, a seguinte versão é executada em tempo constante, testando todos os caracteres e usando uma operação bit a bit para acumular o resultado: 

bool constantTimeStringCompare(const void *a, const void *b, size_t length) {
  const char *ca = a, *cb = b;
  bool result = true;
  for (size_t i = 0; i < length; i++)
    result &= ca[i] == cb[i];
  return result;
}

No mundo das funções da biblioteca C, a primeira função é análoga a memcmp(), enquanto a última é análoga às do NetBSD consttime_memequal()ou do OpenBSD timingsafe_bcmp()e timingsafe_memcmp. Em outros sistemas, a função de comparação de bibliotecas criptográficas como OpenSSL e libsodium pode ser usada.

Notas

Ataques temporizados são mais fáceis de montar se o adversário conhece os detalhes internos da implementação do hardware e, mais ainda, o sistema criptográfico em uso. Uma vez que a segurança criptográfica nunca deve depender da obscuridade de nenhum dos dois (ver segurança através da obscuridade , especificamente o princípio de Maxim de Shannon e o princípio de Kerckhoffs ), a resistência a ataques de temporização também não. No mínimo, um exemplar pode ser adquirido e submetido à engenharia reversa. Ataques de temporização e outros ataques de canal lateral também podem ser úteis na identificação, ou possivelmente na engenharia reversa, de um algoritmo criptográfico usado por algum dispositivo.

Referências

Leitura adicional