9

Recebi uma resposta um tanto quanto interessante nesta pergunta:

Qual a possibilidade de encontrar uma determinada string de 192 caracteres em 10 minutos?

Porém não compreendi o que se trata o timing-attack.

Como parece ser algo mais complexo e que foge do contexto original daquela pergunta, resolvi abrir outra.

Sei que é uma vulnerabilidade, mas mais especificamente do que?

2 Respostas 2

12

Ele é um problema que afeta qualquer coisa que não possui tempo constante, acredito que melhor explicar com exemplos, talvez alguém responda a parte mais teórica.

Suponha este tipo de código, em PHP:

function tem_simbolo_na_senha($texto)
{

    $texto = str_split($texto);

    foreach ($texto as $letra) {

        if ($letra == "#" || $letra == "@" || $letra == "%" || $letra == "&") {
            return true;
        }

    }

    return false;

}

Alguém criou porque o sistema exige que o usuário digite um simbolo na senha, isso é um #, @, % ou um &, então precisa verificar se a senha tem um caractere deste tipo. Se você viu o erro neste códio então já sabe o que o timming-attack é, em sua base.

O problema do código acima é que o return é emitido antes ou depois dependendo do texto. Isso é quanto antes houver um simbolo mais rápido será retornado true, portanto considere essas duas senhas:

$texto = 'yuqkdp69yHryACb778mvZsbFegIBU#';
                                       ^
$texto = 'yuqk#p69yHryACb778mvZsbFigIBUh';
               ^

Se mensuramos a média de tempo para que cada uma verificação seja feita teríamos:

yuqk#p69yHryACb778mvZsbFigIBUh demorou 1.6998052597046E-6
yuqkdp69yHryACb778mvZsbFegIBU# demorou 5.058741569519E-6

Veja isto, aqui.

Em todos os testes o yuqkdp69yHryACb778mvZsbFegIBU# é mais lento.


Isso não é apenas para "o que você cria", os recursos padrões da linguagem também são vulneráveis, imagine isto:

if($usuario === 'inkeliz'){
}

Agora observe a implementação do PHP para o ===:

ZEND_API int ZEND_FASTCALL zend_is_identical(zval *op1, zval *op2) /* {{{ */
{
    if (Z_TYPE_P(op1) != Z_TYPE_P(op2)) {
        return 0;
    }
    switch (Z_TYPE_P(op1)) {
    //...
        case IS_STRING:
            return (Z_STR_P(op1) == Z_STR_P(op2) ||
                (Z_STRLEN_P(op1) == Z_STRLEN_P(op2) &&
                 memcmp(Z_STRVAL_P(op1), Z_STRVAL_P(op2), Z_STRLEN_P(op1)) == 0));
    //...
        default:
            return 0;
    }
}

Código fonte

Não possuo muito conhecimento em C. Mas, até onde sei se ambos forem apontados para mesmo endereço da memoria Z_STR_P(op1) == Z_STR_P(op2) ele retornará true, de imediato. Se não, eles devem ter o mesmo tamanho Z_STRLEN_P(op1) == Z_STRLEN_P(op2) e então vai usar o memcmp.

Se formos mais em baixo vamos ver que o memcmp é:

int
memcmp(s1, s2, n)
    CONST VOID *s1;         /* First string. */
    CONST VOID *s2;         /* Second string. */
    size_t      n;                      /* Length to compare. */
{
    unsigned char u1, u2;

    for ( ; n-- ; s1++, s2++) {
    u1 = * (unsigned char *) s1;
    u2 = * (unsigned char *) s2;
    if ( u1 != u2) {
        return (u1-u2);
    }
    }
    return 0;
}

Segundo este código fonte.

Observe a semelhança deste código para o primeiro exemplo, do PHP, é praticamente idêntico! Ele dará um return se o u1 != u2, ou seja no primeiro bit diferente ele irá emitir algo diferente de 0.

Portanto:

$usuario === 'inkeliz'

Considerando isto:

ixxxxxx

Irá demorar mais do que isto:

axxxxxx

Portanto de pouco em pouco nós conseguimos:

iaxxxxx
ibxxxxx
...
inxxxxx
inaxxxx
...
inkxxxx

O inkelia será muito mais demorado do que o axxxxxx, o memcmp vai abandonar o barco somente na última letra enquanto no segundo caso ele entrega na primeira diferença, na primeira letra.


Então como podemos fazer algo que não seja vulnerável? Mantendo o tempo igual, ou o mais próximo disso, um tempo que não tenha relação com o input de fato.

No primeiro exemplo poderiamos fazer:

function tem_simbolo_na_senha($texto)
{

    $return = 0;

    $tamanho = mb_strlen($texto, '8bit');

    for($i = 0; $i < $tamanho; $i++){

        $return |= (int)($texto[$i] === "#" xor $texto[$i] === "@" xor $texto[$i] === "%" xor $texto[$i] === "&");

    }

    return $return !== 0;

}

Isso iria fazer com que:

1 - yuqkdp69yHryACb778mvZsbFegIBU# demorou 6.3819885253906E-6
1 - yuqk#p69yHryACb778mvZsbFigIBUh demorou 6.4213275909424E-6
1 - yuqksp69yHryACb778m#Zs#Fi#IBUh demorou 6.2981128692627E-6
0 - yuqksp69yHryACb778mvZsbFigIBUh demorou 6.1065435409546E-6
1 - yuqksp69yHryACb778mvZsb%igIBUh demorou 5.9833765029907E-6
1 - yuqksp69yHryACb778mvZsbFigIBU& demorou 6.1017274856567E-6
1 - yuqksp@9yHryACb778mvZsbFigIBUh demorou 6.4485788345337E-6

Veja isto

Ou seja, o tempo de processamento independe do input, independe de onde está o caractere especial. É lógico os tempos médio em alguns casos podem ser diferentes, mas não está relacionado ao input, se ainda sim for influenciado será uma influencia muito menor.

Porque isso é melhor?

  1. O $return guarda o retorno, mas não emite ele de imediato, assim percorrendo todo o resto, independente de se encontrar outro ou não.

  2. O xor exige que todas condições do if sejam executadas, se continuasse com o || ele irá encerrar assim que a primeira condição retornasse true.


Já o caso da comparação é diferentes, a maior parte das linguagens de programação possuem uma biblioteca de criptografia, elas sempre incluem uma função segura de comparação, o PHP possui o hash_equals, o Golang tem o ConstantTimeCompare, o Phyton tem o hmac.compare_digest...

Mas em geral fazemos:

while(tamanho_string){

    retorno |= 'A' ^ 'B'

    return retorno

}

No caso do PHP seria:

function comparacao_segura($input, $segredo){

    $return = 0;

    $tamanhoSegredo = mb_strlen($segredo, '8bit');
    $tamanhoInput = mb_strlen($input, '8bit');

    if($tamanhoSegredo !== $tamanhoInput){
        return false;
    }

    for ($i = 0; $i < $tamanhoSegredo; $i++) {      
        $return |= (unpack('C', $input[$i])[1] ^ unpack('C', $segredo[$i])[1]);
    }

    return $return === 0; 

}

Isso é seguro porque?

  1. Simples, ele vai executar por toda string, não dando um return quando um bit é diferente.

  2. O $return sempre será atualizado, independente se ele é ou não verdadeiro, logo não cria um Branching Timing Attacks e o tempo será igual.

Se nunca viu operações bitwise antes, então essa seria o funcionamento por trás:

Dado comparacao_segura("A...", "B..."), ele vai:

A = 65
B = 66

Depois o que faz é um xor:

65 ^ 66

Que é na verdade:

  0100 0010
  0100 0001
= 0000 0011

Então ele faz um ou (|) com o valor que estava previamente armazenado, no caso:

 0000 0000
 0000 0011
= 0000 0011

Que no final será diferente de 0.

Se forem iguais, o ^ dará 00000000 em todas as comparações, logo o or de 00000000 com 00000000 será 0000000 e portanto será === 0.

Qual é a falha?

Ele expõe o tamanho do segredo, isso em geral não é visto como um problema, inclusive a implementação do Phyton tem este problema, dito na documentação.

Existe como "corrigir" isto?

Não exatamente, devido ao strlen, mas é possível chegar próximo:

function comparacao_mais_segura($input, $segredo){

    $return = 0;

    $tamanhoInput = mb_strlen($input, '8bit');
    $tamanhoSegredo = mb_strlen($segredo, '8bit');

    for ($i = 0; $i < $tamanhoInput; $i++) {        
        $return |= (unpack('C', $input[$i])[1] ^ unpack('C', $segredo[$i % $tamanhoSegredo])[1]);
    }

    return $return === 0; 

}

Isso é um pouco matemático, logo a alteração é:

$i % $tamanhoSegredo

Isso quer dizer que em comparacao_mais_segura('ABCDEF', 'AB'), na primeira vez será 0 % 2 = 0, depois, 1 % 2 = 1, depois 2 % 2 = 0, depois 3 % 2 = 1....

Porém em geral o Length timing attack, como é chamado, não é considerado um problema tão grave, uma vez que conhecer o tamanho não faz saber o seu conteúdo.


Uma outra questão é não fazer isto, que é considerado vulnerável por "Branching Timing Attack":

if(algo){
    funcao()
}else{
    outra_coisa()
}

Suponha que o encontrou_cadastro procura pelo e-mail do usuário no banco de dados (ex. "SELECT * FROM Tabela WHERE Email = ?").

if(encontrou_cadastro($_POST['email'])){

    compara_senha($_POST['senha'])

}

Mesmo que o tempo da query seja rápida o suficiente,que por si já não é, ainda existe um problema.

Isso é um tanto lógico, a função compara_senha() somente será chamada se for encontrado o usuário, portanto é possível que alguém, baseado no tempo, consiga descobrir se um e-mail está cadastrado ou não.

Neste caso se o [email protected] estiver cadastrado ele irá comparar a senha, se não irá executar nada. Logo, se a página "demorar" é porque este e-mail existe, se não ele não existe, mesmo que claramente não diga isto ao usuário ele é capaz de saber.

Isso depende do contexto para ser considerado ou não um problema. Se o seu website já informa "e-mail já cadastrado" ao tentar se cadastrar, então o e-mail não é uma informação secreta, logo usar o código acima não é um problema de segurança, o e-mail não é secreto.

Se isto for um problema, então faça algo como:

if(encontrou_cadastro($_POST['email'])){
    compara_senha($_POST['senha'], senha_do_banco())
}else{
    compara_senha($_POST['senha'], 'hahs-de-uma-senha-idiota')
}

Assim ambos os casos vão usar o compara_senha, anulando suas diferentes, supondo que eles utilizem comparações seguras. :D


Existem soluções genéricas, que é de fazer um sleep. Isso é usado não conseguimos manter uma função em tempo constante então fazemos isso "na força bruta". Determinamos que a função deve sempre demorar 200ms, assim independente do que ocorra demorará 200ms. O problema disso é:

  1. Definir um tempo fixo longo demais expõe um possível DoS.
  2. Definir um tempo fixo curto demais acaba com a "proteção".
  3. Isto apenas afeta remotamente, mas não localmente, logo um "local timing attack" ainda é totalmente possível, afinal a função em si não é constant-time.

Quando se fala em "local timing attack" a coisa piora, isso porque existe muito mais informações, é possível saber onde o dado está armazenado (ex. na RAM, no cache L1, L2, L3) somente baseado no tempo, cada um possui velocidades diferentes, logo isto é físico e não de software. Neste caso existem mais ataques, que inclusive são o "maior problema" para criptografia, mas desse assunto não entendo tanto. :(

1
  • Muito boa a explicação, parabéns. Commented 26/05/2017 às 13:15
6

Existe um ditado popular:

Mente vazia, oficina do diabo.

Que poderia ser modificado para se encaixar perfeitamente nesta pergunta:

Tempo Ocioso, Oficina do Tinhoso(ou do Hacker, ou do mal elemento em questão)

Mas deixa de gracinha =) e vamos lá:

Resumidamente, com tradução livre, adaptado para questão, da Wikipédiaen:

Na criptografia, Timing Attack é um ataque Side Channel no qual o invasor tenta comprometer um sistema de criptografia, analisando o tempo necessário para executar algoritmos criptográficos. Cada operação lógica em um computador leva tempo para executar, e o tempo pode se diferenciar com base na entrada.

Sendo assim, informações podem vazar de um sistema através da medição do tempo que leva para responder as determinadas consultas(query). O quanto essas informações podem ajudar um atacante depende de muitas variáveis: design do sistema de criptografia, a CPU executando o sistema, os algoritmos utilizados, detalhes de implementação variados, contramedidas de ataque de tempo, a precisão das medições de tempo, etc...

O que é o Timing Attack?

Timing Attack, como o nome diz, é um tipo de ataque à sistemas baseado no tempo. Basicamente o ataque consiste em tentar descobrir informações relevantes de um sistema analisando o tempo que o sistema leva para realizar determinadas operações.

Como o computador funciona com um processador baseado em ciclos, o tempo gasto para realizar o mesmo conjunto de operações mais de uma vez é praticamente idêntico. Então se a pessoa consegue interagir com o sistema passando um dado de entrada diferente, ele consegue analisar o tempo que levou para processar aquela informação.

Mais especificamente do que?

Normalmente, este tipo de ataque está associado ao roubo de dados(como exemplo, descoberta de senhas). Quando, por exemplo, uma pessoa tenta explorar o formulário de "login" do sistema passando senhas diferentes e analisando o tempo que o sistema levou para dizer que a senha é inválida.

A ideia central deste ataque é explorar um comportamento dos sistemas durante a comparação de strings. Normalmente as linguagens de programação oferecem um mecanismo para comparação de strings que percorre caractere por caractere, comparando-os e retornando false assim que encontra uma diferença. Ou seja, se o primeiro caractere de duas strings já forem diferentes, a operação levará pouquíssimo tempo para descobrir que as strings são diferentes. Porém, se as duas strings forem grandes e os 100 primeiros caracteres forem iguais, mas o 101º for diferente, então a operação levará mais tempo, pois precisará percorrer 100 caracteres até perceber a diferença.

Como se prevenir deste ataque?

Uma solução é fazer com que determinada operação sensível ao tempo seja realizada em um tempo que não ajude ninguém a descobrir informações, por exemplo, realizando a operação em um tempo constante ou então realizando em um tempo totalmente aleatório. E foi feita, no PHP 5.6, foi criada a função hash_equals da extensão hash. Ela faz exatamente isso que é preciso, ou seja, uma comparação segura quanto ao tempo para comparar hashes de senhas.

Onde ele se aplica?

Por ser uma brecha de segurança, ele se aplica a quase Não tenho certeza todos os sistemas. Por exemplo, toda aplicação que precise fazer comparações de strings(algo que quase todos sistemas fazem, uma vez que em um sistema de login, há a necessidade de se comparar um hash) estão vulneráveis a não ser que já tenha tomado as devidas providências de segurança.

Veja mais perguntas e definições relacionadas:

Fonte

Você deve fazer log-in para responder a esta pergunta.