MHASH_CRC32

Tato funkce je většinou využívána ke kontrole integrity například při přenášení souborů. Je taktéž hojně využívána při komprimaci (CRC se spočítá před komprimací a musí být shodné s CRC po komprimaci).

Poslední jednosměrnou hashovací funkcí, na kterou se podrobněji podíváme, je funkce CRC-32 (Cyclic Redundancy Check). Tato funkce je většinou využívána ke kontrole integrity například při přenášení souborů. Je taktéž hojně využívána při komprimaci (CRC se spočítá před komprimací a musí být shodné s CRC po komprimaci). Pokud je CRC shodné, existuje velká pravděpodobnost že archiv nebyl porušen.

Účelně jsem použil slovo velká, ale ne stoprocentní, neboť u použití CRC-32 je teoretická pravděpodobnost rovna hodnotě 2 32 : 1 ( 4 294 967 296 : 1) že budou dva soubory (řetězce) stejné. V praxi je pravděpodobnost ale podstatně menší. Pravděpodobnost klesá s přibývající velikostí souboru, ale i přesto můžeme CRC považovat za slušnou kontrolu, neboť u náhodných chyb slouží dostatečně, neboť je stavěná hlavně pro porovnávání souborů a dat, musí být navržena tak, aby se projevila změna i při prohození 2 bitů a toto prohození se projevilo jako plně odlišný výsledek (otisk).

Základem výpočtu CRC je tabulka, 32bitových konstant, která tvoří základ pro výpočet. Obsah takové tabulky můžeme předvypočítat a umístit přímo do zdrojového kódu, nebo ji můžeme vypočítat až po startu programu – za běhu.

Oficiální funkce pro výpočet tabulky vypadá následovně:

void Init_CRC32Table()
{
   DWORD ulPolynomial = 0x04c11db7;
   for(int i = 0; i <= 0xFF; i++) {
      CRC32Table[i]=Reflect(i, 8) << 24;
      for (int j = 0; j < 8; j++)
         CRC32Table[i] = (CRC32Table[i] << 1) ^ (CRC32Table[i] & (1 << 31) ? ulPolynomial : 0);
      CRC32Table[i] = Reflect(CRC32Table[i], 32);
   }
}

// Převrácení (Reflection) je vyžadováno oficiálním CRC-32 standardem.
// Můžete vytvářet CRC i bez něj, ale nebude splňovat standard.

DWORD Reflect(DWORD ref, char ch)
{
   DWORD value = 0;

   // Prohodí bit 0 za bit 7
   // bit 1 za bit 6, atd.
   for(int i = 1; i < (ch + 1); i++) {
      if(ref & 1)
         value |= 1 << (ch - i);
      ref >>= 1;
   }
   return value;
}

void Init_CRC32Table()

{

DWORD ulPolynomial = 0x04c11db7;

for(int i = 0; i <= 0xFF; i++) {

CRC32Table[i]=Reflect(i, 8) << 24;

for (int j = 0; j < 8; j++)

CRC32Table[i] = (CRC32Table[i] << 1) ^ (CRC32Table[i] & (1 << 31) ? ulPolynomial : 0);

CRC32Table[i] = Reflect(CRC32Table[i], 32);

}

// Převrácení (Reflection) je vyžadováno oficiálním CRC-32 standardem.

// Můžete vytvářet CRC i bez něj, ale nebude splňovat standard.

DWORD Reflect(DWORD ref, char ch)

{

DWORD value = 0;

// Prohodí bit 0 za bit 7

// bit 1 za bit 6, atd.

for(int i = 1; i < (ch + 1); i++) {

if(ref & 1)

value |= 1 << (ch - i);

ref >>= 1;

}

return value;

}

CRC nejprve nastavíme na hodnotu 0xFFFFFFFF a potom v cyklu procházíme celý řetězec(buffer) bajt po bajtu. Nejnižších 8 bitů XORtujeme s vstupními daty. Tím získáme indexi pro tabulku. Potom rotujeme vždy 8 bitů vpravo a XORtujeme s konstantou z tabulky (podle indexu).

Nakonec k celému CRC vytvoříme inverzní CRC¨hodnotu.

V PHP by kód mohl vypadat následně:

Nejprve musíme umístit předvypočítanou tabulku přímo do zdrojového kódu:

$CrcTable = array( 
  0x000000000, 0x077073096, 0x0ee0e612c, 0x0990951ba, 
… 
);

$CrcTable = array(

0x000000000, 0x077073096, 0x0ee0e612c, 0x0990951ba,

…

);

a samotná funkce by vypadala následovně:

function uCRC32($Buf) 
{ 
  global $CrcTable; 
  //zjistíme délku řetězce, abychom jej mohli celý projít 
  $BufLen = strlen($Buf); 
  //nastavíme hodnotu na 0xFFFFFFFF 
  $crc = 0xFFFFFFFF;   

  for($i = 0; $i < $BufLen; $i++) { 
  //nejprve získáme index 
  $index = ($crc ^ Ord($Buf[$i])) & 0xFF; 
  //rotujeme a XORtujeme s konstantou z tabulky 
  $crc = (($crc >> 8) & 0x00FFFFFF) ^ $CRCTable[$index]; 
  } 
  return $crc; 
}

function uCRC32($Buf)

{

global $CrcTable;

//zjistíme délku řetězce, abychom jej mohli celý projít

$BufLen = strlen($Buf);

//nastavíme hodnotu na 0xFFFFFFFF

$crc = 0xFFFFFFFF;

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

//nejprve získáme index

$index = ($crc ^ Ord($Buf[$i])) & 0xFF;

//rotujeme a XORtujeme s konstantou z tabulky

$crc = (($crc >> 8) & 0x00FFFFFF) ^ $CRCTable[$index];

}

return $crc;

}

Pokud ale chcete vytvořit CRC otisk v PHP nemusíte naštěstí nic počítat, ale stačí vám použít standardní funkci obsaženou v knihovně mhash:

$input[] = "při použití podobných řetězců musí zase vzniknout naprosto jiný otisk"; 
$input[] = "při použití podobných řetězců musí zase vzniknout naprosto jiný otisk."; 
foreach($input as $value) 
print bin2hex(mhash (MHASH_CRC32, $value)) . '<br />';

$input[] = "při použití podobných řetězců musí zase vzniknout naprosto jiný otisk";

$input[] = "při použití podobných řetězců musí zase vzniknout naprosto jiný otisk.";

foreach($input as $value)

print bin2hex(mhash (MHASH_CRC32, $value)) . '<br />';

Výstup vypadá potom takto:

4c8e3a91
883c080e

1 2	4c8e3a91 883c080e

Shrnutí

Pokud bychom tedy shrnuly všechny tři popsané hashovací funkce a srovnali je ještě s docela rozšířenou funkcí HAVAL, dospěli bychom k následující tabulce:

Název kódování	Vlastnosti
CRC-32	Nízká bezpečnost, rychlý
MD5	Všší bezpečnost
SHA	Všší bezpečnost
HAVAL	128 bitový klíč, nejvyšší bezpečnost

Je nutné si uvědomit, že žádná hashovací funkce není stoprocentní a u každé této funkce existuje možnost prolomení jejího hashe. U většiny funkcí jsou k dispozici přímo vyvinuté softwares, u jiných je to otázka času.

Nic vám však nebrání použít libovolnou kombinaci těchto funkcí na váš vstupní řetězec. Pokud tedy chcete útočníkovy přidělat starostí není nic jednoduššího, než nakombinovat dvě funkce, nebo jednu funkci použít dvakrát po sobě:

$str = md5(md5("heslo"));  
//nebo
$str = sha1(md5("heslo"));

$str = md5(md5("heslo"));

//nebo

$str = sha1(md5("heslo"));

Takovýto způsob je sice výhodný, ale je zase výpočetně mnohem náročnější, proto dobře rozmýšlejte, než se do něčeho takového pustíte.

MHASH_CRC32

Shrnutí

Comments are closed for this page