Semplici confronti tra stringhe non sicuri contro gli attacchi temporali [duplicato]

14

Come ho appreso in un commento per Come crittografare in PHP, correttamente? , mi è stato detto che l'utilizzo di un confronto di stringhe come il seguente in PHP è suscettibile agli attacchi temporali. Quindi non dovrebbe essere usato per confrontare due MAC o hash (anche hash delle password) per l'uguaglianza.

if ($hash1 === $hash2) {
   //mac verification is OK
   echo "hashs are equal"
} else {
  //something bad happenend
  echo "hashs verification failed!";
}

Qualcuno può descrivermi quale sia esattamente il problema, come sarebbe un attacco e possibilmente fornire una soluzione sicura che eviti questo particolare problema. Come dovrebbe essere fatto correttamente? È questo un particolare problema di PHP o altri linguaggi come ad es. Python, Java, C ++, C ecc. Hanno gli stessi problemi?

    
posta evildead 12.03.2015 - 20:27
fonte

3 risposte

15

Il problema qui è che le funzioni di confronto di stringhe generiche ritornano non appena trovano una differenza tra le stringhe. Se il primo byte è diverso, ritornano dopo aver osservato solo un byte delle due stringhe. Se l'unica differenza è nell'ultimo byte, elaborano entrambe le intere stringhe prima di tornare. Questo accelera le cose in generale, che normalmente è buono. Ma significa anche qualcuno che può dire quanto tempo ci vuole per confrontare le stringhe può fare una buona ipotesi dove la prima differenza è.

In uno scenario di attacco, un attaccante ha il controllo totale di $mac1 (è preso dal messaggio fatto dall'attaccante), mentre $mac2 è il vero MAC valido per il messaggio dell'attaccante. $mac2 deve rimanere segreto dall'attaccante, oppure può incollarlo sul suo messaggio e quindi falsificare un messaggio valido. L'attaccante, analizzando il tempo necessario per ottenere una risposta, può probabilmente capire dove si trova la prima differenza tra il suo MAC e quello reale. Può provare tutte le possibilità per quell'unico byte, trovare quello corretto e quindi lavorare sul prossimo byte sicuro sapendo che i primi k byte sono corretti. Alla fine, ha provato solo 256 * len MAC (se len è la lunghezza del MAC) invece del 256 ^ len avrebbe dovuto provare.

    
risposta data 12.03.2015 - 21:50
fonte
16

Aggiungerò un elenco con funzioni costanti di tempo per diverse lingue:

PHP :

Discussione: link

bool hash_equals ( string $known_string , string $user_string )

link

Java Discussione: link

public static boolean  MessageDigest.isEqual(byte[] digesta, byte[] digestb)

link

C / C ++ Discussione: link

int util_cmp_const(const void * a, const void *b, const size_t size) 
{
  const unsigned char *_a = (const unsigned char *) a;
  const unsigned char *_b = (const unsigned char *) b;
  unsigned char result = 0;
  size_t i;

  for (i = 0; i < size; i++) {
    result |= _a[i] ^ _b[i];
  }

  return result; /* returns 0 if equal, nonzero otherwise */
}

Altro Ho trovato qui: link

Python (2.x):

#Taken from Django Source Code

def constant_time_compare(val1, val2):
    """
    Returns True if the two strings are equal, False otherwise.

    The time taken is independent of the number of characters that match.

    For the sake of simplicity, this function executes in constant time only
    when the two strings have the same length. It short-circuits when they
    have different lengths.
    """
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= ord(x) ^ ord(y)
    return result == 0

Python 3.x

#This is included within the stdlib in Py3k for an C alternative for Python 2.7.x see https://github.com/levigross/constant_time_compare/
from operator import _compare_digest as constant_time_compare

# Or you can use this function taken from Django Source Code

def constant_time_compare(val1, val2):
    """
    Returns True if the two strings are equal, False otherwise.

    The time taken is independent of the number of characters that match.

    For the sake of simplicity, this function executes in constant time only
    when the two strings have the same length. It short-circuits when they
    have different lengths.
    """
    if len(val1) != len(val2):
        return False
    result = 0
    for x, y in zip(val1, val2):
        result |= x ^ y
    return result == 0

Haskell

import Data.Bits
import Data.Char
import Data.List
import Data.Function

-- Thank you Yan for this snippet 

constantTimeCompare a b =
  ((==) 'on' length) a b && 0 == (foldl1 (.|.) joined)
  where
    joined = zipWith (xor 'on' ord) a b

Rubino

def secure_compare(a, b)
     return false if a.empty? || b.empty? || a.bytesize != b.bytesize
     l = a.unpack "C#{a.bytesize}"

     res = 0
     b.each_byte { |byte| res |= byte ^ l.shift }
     res == 0
   end

Java (generale)

// Taken from http://codahale.com/a-lesson-in-timing-attacks/
public static boolean isEqual(byte[] a, byte[] b) {
    if (a.length != b.length) {
        return false;
    }

    int result = 0;
    for (int i = 0; i < a.length; i++) {
      result |= a[i] ^ b[i]
    }
    return result == 0;
}
    
risposta data 12.03.2015 - 23:49
fonte
2

Gli attacchi temporali contro i confronti tra stringhe non sono specifici di PHP. Funzionano in qualsiasi contesto in cui una stringa fornita dall'utente viene confrontata con una stringa segreta utilizzando l'algoritmo di confronto standard "cortocircuito" (il controllo si ferma sul primo byte non corrispondente). Questo vale per PHP, Python, C e persino per i sistemi di database come MySQL.

L'approccio standard a questo problema è quello di iterare sempre su tutti i byte della stringa, indipendentemente dal contenuto. Come pseudo codice:

function safe_string_comp(str_1, str_2):
    if byte_length(str_1) =/= byte_length(str_2):
        return FALSE
    else:
        comparison_bit := 0  // 0 if the strings match, 1 otherwise
        for i := 0, i < byte_length(str_1), i := i + 1:
           comparison_bit := comparison_bit | (str_1[i] ^ str_2[i])

        return comparison_bit == 0

Il simbolo | denota l'operatore bit-saggio OR , e ^ è il bit-saggio XOR .

Le versioni recenti di PHP (> = 5.6.0) hanno già una funzione predefinita chiamata hash_equals . Se non è disponibile, l'algoritmo di cui sopra deve essere implementato. Quindi una funzione di comparazione delle stringhe sicura per il tempo può apparire come questa:

<?php

/**
 * Count the number of bytes in a string.
 *
 * Note that the strlen() function is ambiguous, because it will either return the number of *bytes* or the
 * number of *characters* with regard to mb_internal_encoding(), depending on whether the Mbstring extension
 * has overloaded the string functions:
 * http://php.net/manual/en/mbstring.overload.php
 *
 * For example, the non-overloaded strlen() function returns 2 for the string "\xC3\x84". However, if the
 * function is overloaded and the internal encoding set to UTF-8, the same string is interpreted as a single
 * character, namely the "Ä" umlaut. So the function returns 1 in this case.
 */
function byte_length($binary_string)
{
    if (extension_loaded('mbstring'))
        return mb_strlen($binary_string, '8bit');
    else
        return strlen($binary_string);
}



/**
 * Timing-safe string comparison.
 *
 * The standard string comparison algorithm stops as soon as it finds a non-matching byte. This leaks information
 * about the string contents through time differences, because the longer the common prefix, the longer the
 * comparison takes (e. g. checking "aaax" against "aaaa" theoretically requires slightly more time than checking
 * "xaaa" against "aaaa").

 * To avoid this problem in security contexts like MAC verification, iterate over *all* bytes of the strings
 * regardless of the content.
 */
function secure_string_equals($string_1, $string_2)
{
    // Use built-in hash_equals() function if available (PHP >= 5.6.0)
    if (function_exists('hash_equals'))
    {
        return hash_equals($string_1, $string_2);
    }
    else
    {
        $equals = false;

        if (!is_string($string_1) || !is_string($string_2))
        {
            trigger_error('One of the arguments is not a string.', E_USER_ERROR);
        }

        if (byte_length($string_1) == byte_length($string_2))
        {
            // 0 if the strings are equal, 1 otherwise
            $comparison_bit = 0;
            for ($byte_index = 0; $byte_index < byte_length($string_1); $byte_index++)
            {
                $comparison_bit |= ord($string_1[$byte_index]) ^ ord($string_2[$byte_index]);
            }

            $equals = ($comparison_bit == 0);
        }

        return $equals;
    }
}
    
risposta data 13.03.2015 - 00:30
fonte

Leggi altre domande sui tag