php + md5

[darksign]

Man tagad tāda problēma, tiesa gan nezinu cik prātīgi viņu ir risināt uz php (jo php jau nu nekāds ātrais šajā ziņā nav), bet tomēr.. uzdevumu parisināsim, ja sanāks labs algoritms, tad jau mazākā bēda pārrakstīt kādā citā valodā :)

 

Tātad sekojoša lieta:

+ ir dots md5 hash:

3cefe9eb7d4567ebcb495ef1f0a792ac

 

+ ir dots t.s. hints, jeb maza palīdzība (kriptētā teksta burta pozīcija un burts):

5-o, 9-e, 25-a, 37-i

 

Pavisam kriptētā teksta garums ir 41 simboli (latīņu alfabētā).

Vēl ir zināms čarsets:

$charset = 'abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ';

 

Tātad kā domājat, vai ir vispār iespējams šādu te atlauzt, un ar kādiem paņēmieniem.

 

Manas idejas un domas ir nākamajos postos zemāk....

[briedis]

Vari mēģināt pēc pilnās pārlases :) ..bet tas būs fakin ilgi...

..vai gadījumā nesanāk 37 53.pakāpē variantu ko izmēģināt? :)

Edited October 19, 2009 by briedis

[Aleksejs]

pilnajai pārlasei par daudz. Tad jau pēti Čangas darbu par kolīzijām MD5 funkciju saimē.

[darksign]

1) Man bija doma ģenerēt un lauzt ar rainbow tables palīdzību.. ģenerēju veselu dienu, tad mēģināju kost vaļā, bet bez rezultātiem, jo tāpat visu keyspace nenosegšu.. bet ja gribētu, tad lai to tabulu uzģenerētu ar esošiem rīkiem būtu nepieciešami gadi. Viens variants, ir varbūt varu ģenerēt pats ar php vai kādu C valodu to rainbow tables, bet ņemot vērā sekojošos faktus un pieņēmumus, tādējādi sašaurinot variāciju spektru.

 

2) Zināms, ka tur ir rakstīts kaut kāds sakarīgs teikums. (Ceru ka angļu valodā, nevis translitā, bet pagaidām nav lielas nozīmes)

no tā izriet, ka tur ir vairāk, par vienu vārdu (vārds ir simbolu virkne, ko atdala ar atstarpi no pārējās teksta daļas).

Pieņemu, ka 41 simbolu garā teikumā ir vismaz 4 vārdi, tātad tekstā jābūt vismaz 3, vai vairāk atstarpēm, pie tam, atstarpes nav viena otrai blakus.

Pieņemu, ka vārda garums ir no 1 simbola (piem. "I" vai artikuls "a") līdz maksimāli 14 simbolu garš (max garumu vienkārši pieņemu uz intuīciju).

Pieņemu, ka vārds, kas ir vismaz 3 vai vairākus simbolus garš, obligāti satur kādu patskani (angļu val: a,e,i,o,y,u ... te par to y, protams, vēl nedrīkst tik strikti, jo var gadīties, ka ir rakstīts translitā LV val. ...)

 

3) Lai varētu veiksmīgi šādus nosacījumus izpildīt, no sākuma nepieciešams uzrakstīt funkciju, kas ģenerēs attiecīgus teikumus, kas atbilst iepriekš noteiktiem uzstādījumiem, turklāt fiksējot, jau zināmās pozīcijas.

 

4) Pārbadu ar md5 hashiem, veikt tikai pašā pārliecinošākajā momentā, lai nezaudētu datora dārgo laiku... (pēc pirmajiem testiem, ar primitīvu skriptu, viens pats ifs, kas uzliek vienkāršu pārbaudi, saīsina kopējo meklēšanas laiku par vairākiem desmitiem reižu... konkrēti man bija tests uz 7 simboliem, kur ieguvu nekriptēto tekstu (plain text) no vidēji 42 sekunžu laikā, bet optimizējot kodu ar ifiem utt. šo laiku saīsināju uz 0.5 sekundēm, kas jau ir ievērojami)

 

5) tā kā jebkurā gadījumā šis uzdevums nevar tikt atrisināts uz viena datora (uzdevuma risināšanas optimālais laiks ir 2 nedēļas ... ar visu datora aprēķinu, ja vispār tas ir iespējams..), tad

nepieciešams šo visu padarīšanu sadalīt uz vairākiem datoriem. Katram iedot savu daļu rēķināšanai, un vienu kopēju centralizētu datubāzi, uz kuru, skripts nosūtītu rezultātus katras ~10 min, vai ar katru 10 000 aprēķinu, un saņemtu nākamo risināmo apgabalu. Datubāzē tāpat kā līdzīgi ar rainbow tables, būtu jāsaglabā apgabala pirmais un pēdējais hash, un, protams, arī īstais atklātais plain text, ja tāds tiek atrasts.

Šāda pieeja ļautu:

+ redzēt, ka vispār kaut kas notiek, ka dators nav vienkārši uzkāries

+ redzēt un prognozēt procesa darbības tempu

+ pievienot jebkuru skaitu jaunus datorus konkrētā hash laušanai

+ izmantot arī uz citām valodām programmētās programmas, salīdzināt to ātrdarbību, turklāt vēl nezaudējot jau ieguldīto laiku, jeb pārbaudītos plain textus nevajadzētu uzlabojot algoritmu pārbaudīt no sākuma.

[darksign]

Pašam iesākumam, te būs ļoti ļoti nepabeigts skripts, kas visas manas izteiktās idejas pat vēl ne tuvumā nevar izpildīt, bet varbūt kāds var palīdzēt viņu optimizēt.

 

Metu iekšā ar visiem komentāriem, un aizkomentētām koda daļām...

 

 

<?php
echo "Started<br />"; //vnk.. lai nu kaut kas redzams, ka saakas
set_time_limit(0);


#########################################################
/*                   Configuration                     */
include_once('func.mysql.php'); //Seit ir datubaazes pieejas funkcijas.. ja vajag ieposteeshu arii to, bet nekas noziimiigs...

$plain = "t st a "; //tests, lai paarbaudiitu vaardu chekoshanu utt...
$md5 = md5($plain);

// this is the hash we are trying to crack
//define('HASH', '098f6bcd4621d373cade4e832627b4f6');   //test
define('HASH', $md5);
//define('HASH', '3cefe9eb7d4567ebcb495ef1f0a792ac');    //iistais mekleetais hash, bet to komenteejam valjaa tikai tad, kad zinam, ka algoritms ir pietiekami speeciigs, lai buutu veerts meegjinaat...

// algorithm of hash
// see http://php.net/hash_algos for available algorithms
define('HASH_ALGO', 'md5');
//define('MIN_WORD_COUNT', 4);
define('MIN_WORD_COUNT', 1); //minimaalais vaarda garums
define('MAX_WORD_LENGTH', 14); //maksimaalais vaarda garums

//FIXME: min length of password to try
define('PASSWORD_MIN_LENGTH', 7); //minimaalais garums, .. testa rezimaa meegjinam liidz 10 simboliem
//define('PASSWORD_MIN_LENGTH', 41); //minimaalais, .. reaalais..

// max length of password to try
define('PASSWORD_MAX_LENGTH', 7); //maksimaalais garums, .. testa rezimaa meegjinam liidz 10 simboliem
//define('PASSWORD_MAX_LENGTH', 41); //maksimaalais, .. reaalais ..

// available characters to try for password
// uncomment additional charsets for more complex passwords
$charset = 'abcdefghijklmnopqrstuvwxyz '; // testeejam ar mazaaku charsetu (27)
//$charset = 'abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ';  //reaalais charsets
//$charset .= '0123456789';
//$charset .= 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
//$charset .= '~`!@#$%^&*()-_\/\'";:,.+=<>? ';
#########################################################

/// pieliekam klāt patternu  indeksu ar -1 uzreiz, lai ātrāka rēķināšana, nevis veelaak reekjinaat nost -1
//dotais pattern
/*
$pattern = array(
                 4 => 'o',
                 8 => 'e',
                 24 => 'a',
                 36 => 'i'
               );          */
 //testa patterns
// /*
$pattern = array(
                 0 => 't',
                 1 => ' ',
                 2 => 's',
                 5 => 'a',
               );
//*/

function rgPattern($str, $pattern)
{
//   //papildus parametrs, vārdi nedrīkst būt garāki par n simboliem
//   $words = explode(" ", $str);
//   foreach($words as $key=>$value)
//   {
//      if(strlen($value) > MAX_WORD_LENGTH)
//      {
//         return false;
//      }
//   }

  $w = "";
  $arr = str_split($str);
  foreach($arr as $key=>$value)
  {
     if($value != " ")
     {
        $w .= $value;
     }
     elseif(strlen($w) > MAX_WORD_LENGTH)  //sheit aatraak straadaa, nekaa ieprieksh foreach ciklaa, tapeec paarvietoju sheit
     {
        return false;
     }
     if(!(($pattern[$key] == "") || ($value == $pattern[$key])))
     {
        return false;
     }
  }
  return true;
}
//$sql = "INSERT INTO `md5proccess` (`current_word`,`rinda`,`isOK`) VALUES ('".$password."','".$rinda."','0');";
//$sql = "UPDATE `md5proccess` SET `isOK`='1' WHERE `current_word`='".$password."' LIMIT 1;";
////////////////

$time_start = microtime(true);
echo "<xmp>";
$charset_length = strlen($charset);
echo "charset_length = ".$charset_length."\n";
$rinda = 0;
function check($password)
{
  global $rinda;
  $rinda++;
  $sql = "INSERT INTO `md5proccess` (`current_word`,`rinda`,`isOK`) VALUES ('".$password."','".$rinda."','0');";
  sqlQuery($sql);
  //echo $rinda.": ".$password."\n";
  if (hash(HASH_ALGO, $password) == HASH)
  {
     global $time_start;
     $sql = "UPDATE `md5proccess` SET `isOK`='1' WHERE `current_word`='".$password."' AND `rinda`='".$rinda."' LIMIT 1;";
     sqlQuery($sql);
     echo 'FOUND MATCH (rindas = '.$rinda.'), password: "'.$password."\"\r\n";
     $time_end = microtime(true);
     $time = $time_end - $time_start;
     echo "Found in " . $time . " seconds\r\n";
     echo "</xmp>";
     exit;
  }
}


function recurse($width, $position, $base_string)
{
   global $charset, $charset_length, $pattern;

   for ($i = 0; $i < $charset_length; $i++)
   {
      $str = $base_string . $charset[$i];
      if(rgPattern($str, $pattern)) //ja ir zināms pattern, tad 5 simboliem aizņem apm 0.05 sec, bet bez patterna 41 sec!!!
      {
         if ($position  < $width - 1)
         {
             recurse($width, $position + 1, $str);
         }
         else
         {
              //izskatās, ka paroles minimālais garums rekursīvi meklējot neko neietekmē šajā koda vietā
              //if(strlen($str) < PASSWORD_MIN_LENGTH)
              //{
              //   echo strlen($str). " = [XX]> $str \n";
              //}else
              //   echo strlen($str). " = [OK]> $str \n";
               $words = explode(" ", $str);
               if(count($words) >= MIN_WORD_COUNT)  //min 3 vārdi
               {
                  check($str);
               }

         }
      }
   }
}

echo 'target hash: '.HASH."\r\n";
recurse(PASSWORD_MAX_LENGTH, 0, '');

echo "Execution complete, no password found\r\n";

$time_end = microtime(true);
$time = $time_end - $time_start;

echo "Wasted " . $time . " seconds\r\n";
echo "</xmp>";

?>

 

Tā kā tas skripts ir rakstīts vakarā un pa nakti labots, tad, pielauju ka tur ir vēl daudz dikti daudz kļūdas, neoptimāli varianti utt.. tā kā visi kas jūtas gudri, vai zinoši par vienas vai otras funkcijas ātrdarbību tā vai šitādi izmantojot, lūdzu padalieties ar savām zināšanām...

 

 

p.s. šis te skripts patreizējā stadijā, atkomentējot tās testa daļas, var atlauzt (uz mana datora) 8 simbolu garu paroli ~8 sekundēs, ar lower-apha-space (26 mazie alfabēta + atstarpe = 27). 7 simboliem bija nepieciešamas 0.5 sekundes.

 

Bet tas ir daudz par lēnu, jo reālajā ir 41 simbols. Turklāt, ja kādu interesē, pa brīvdienām biju uzlicis lai darbojas un meklē uz reālo hash, un ieraksta katru plain textu, kas atbildīs tekstūrai jeb patternam datubāzē (nemaz nemēģinot salīdzināt md5 hash). Nu un pēc ~28h darbošanās, vēl nebija neviens ieraksts datubāzē ierakstījies (jo tā teksta ģenerēšana pilnīgā brutaforcē, vismaz tā kā es to darīju ir galīgi garām.., iespējams vajag mazliet gudrāk.. piemēram vārdus ņemt no kādas angļu wordlistes + spēlējoties ar case .. lieliem, maziem burtiem), līdz ar to arī nokilloju procesos, un mēģinam viņu optimizēt utt...

 

 

Laipni aicinātas visas idejas... un labojumi esošam skriptam, vai pavisam jauni skripti :))

Edited October 19, 2009 by darksign

[darksign]

Ir kādas idejas?

[Aleksejs]

Man šķiet, ka pie tik liela apjoma - drīzāk vajadzētu iziet uz teikumu ģenerēšanu no vārdnīcas ar Tevis dotajiem nosacījumiem (ka otrais burts ir o utt)

[darksign]

varbūt ir kāds labs vārdu ģenerators zināms, kas ģenerē vārdus pēc regular expression vai taml.. ?