PHP challenge 6: Leksikon sortering (update 2)

Vikdal · 20. november 2007

Heh, så veldig tricky kan det vel ikke være. Hverfall ikke om den løsningen jeg sitter med i hode nå virker hvertfall.

Det som derimot kan bli morsomt er at det kanskje går opp for folk hvor raskt man kan knekke et passord (riktignok om man vet litt om begrensninger på passordet). Husker jeg registrete meg på en side engang hvor det stod at passordet måtte være minst 5, maks 13 tegn og kun bestå av tall og bokstaver

Edit: Kanskje en fordel å legge til at dette er en stund siden og FØR jeg kunne programmere

Endret 20. november 2007 av Nero Burningwr00m

Rasks · 20. november 2007

du mener at passordet kan innholde 1,2 eller 3 tegn? da blir det jo faktisk 47988 kombinasjoner, fin oppgave forresten!

MC2 · 20. november 2007

du mener at passordet kan innholde 1,2 eller 3 tegn? da blir det jo faktisk 47988 kombinasjoner, fin oppgave forresten!

Ja det stemmer. Var litt rask med kalkulatoren.

loathsome · 20. november 2007

Er det noe "time-limit" på scriptet? Vil jo ta litt tid å sjekke opp 47988 ganger (med mindre jeg hiver inn noe form for caching)

MC2 · 20. november 2007

Er det noe "time-limit" på scriptet? Vil jo ta litt tid å sjekke opp 47988 ganger (med mindre jeg hiver inn noe form for caching)

Jeg tror ikke jeg forsto deg helt riktig nå... men vinneren er jo den med scriptet som cracker raskest. Hvis alle scriptene cracker passordene veldig fort så kommer jeg nok å benke med flere passord, ellers så forventer jeg at vi ser stor forskjell på bare en benking.

gxi · 21. november 2007

Jeg jobber med en til Challenge 2. Håper det blir noen andre, siden det vil jo være litt kjedelig om jeg er den eneste som blir deltaker. Litt kjedelig å lage en som spiller mot seg selv.. begge gjør liksom akkurat det samme av en eller annen "merkelig grunn"

loathsome · 21. november 2007

Jeg har løst oppgaven, men det går ganske tregt (Avhengig av hvilket passord det er). Skal se om jeg får optimalisert det, men tror ikke jeg har tid til det.

Loomy · 21. november 2007

MD5-crackeren var easy peazy, med mindre det er en lureoppgave og jeg har oversett noe

Uansett tror jeg nok det må benches hardt og brutalt for å kåre en vinner. Skal sjekke tidene på koden min nå og prøve å skvise ut noen millisekunder her og der.

Kagee · 21. november 2007

Da har jeg begynt på oppgave 2, men jeg gruer meg litt - husker at jeg for et par uker tilbake brukte ei hel natt på å skrive ned "reglene/logikken" for 3-på-rad. Tror ikke engang jeg ble ferdig....

Endret 22. november 2007 av Kagee

jeg_lyver_mye · 21. november 2007

På oppgave 4... har jeg lov til å kjøre alle kombinasjoner? Også lagre det i MySQL?

Forså å lage et script som bare sjekker opp mot MySQL.

MC2 · 21. november 2007

På oppgave 4... har jeg lov til å kjøre alle kombinasjoner? Også lagre det i MySQL?
Forså å lage et script som bare sjekker opp mot MySQL.

Det kan nok være litt urettferdig og vil nok ødelegge litt av poenget med oppgaven

jeg_lyver_mye · 21. november 2007

Men lov...?

MC2 · 21. november 2007

Men lov...?

Uff, jeg må nok si nei. Det jeg ville få frem i oppgaven var permutasjoner.. Og hvis flere leverer slik løsning vil nok andre faktorer enn programlogikk avgjøre farten.

Endret 21. november 2007 av MC2

LNaitsirhC · 21. november 2007

Oops. Bare se bort ifra den eposten jeg sendte deg. Missforstod oppgaven. Skal sende en ny funksjon imorgen.

Kagee · 22. november 2007

Du skriver på oppgave 2 at "Vinneren av hver kamp er den som vinner flest av 11 spill, mens uavgjorte spill ikke telles."

Men jeg når tester med

$a->best_of(11,50);
//$a->play();

virker det som om en av spillerne vinner selv om det blir uavgjort (alltid 11 win)

hildenae@hilden-thinkcentre:/media/data/Kildekode/php_challenge/2$ php 2_idioter.php
peter_griffin won 7 times!
homer_simpson won 4 times!
...and 2 draws!

hildenae@hilden-thinkcentre:/media/data/Kildekode/php_challenge/2$ php 2_idioter.php
peter_griffin won 8 times!
homer_simpson won 3 times!
...and 4 draws!

Endret 22. november 2007 av Kagee

MC2 · 22. november 2007

Du skriver på oppgave 2 at "Vinneren av hver kamp er den som vinner flest av 11 spill, mens uavgjorte spill ikke telles."

Men jeg når tester med
$a->best_of(11,50);
//$a->play();
virker det som om en av spillerne vinner selv om det blir uavgjort (alltid 11 win)
hildenae@hilden-thinkcentre:/media/data/Kildekode/php_challenge/2$ php 2_idioter.php
peter_griffin won 7 times!
homer_simpson won 4 times!
...and 2 draws!

hildenae@hilden-thinkcentre:/media/data/Kildekode/php_challenge/2$ php 2_idioter.php
peter_griffin won 8 times!
homer_simpson won 3 times!
...and 4 draws!

Den setningen var kanskje litt dårlig formulert, men det er sånn at vinneren er den som vinner flest ganger, opptil 11. Altså uavgjorte kamper telles ikke, så av de 11 må enten en av spillerene vinne. Var det bedre forklart?

MC2 · 25. november 2007

Siden jeg bare fikk inn en spiller (peros2k) på challenge 2 så må jeg dessverre avlyse den. Men jeg husker at noen andre jobbet med den oppgaven, så hvis det er interesse for å åpne den igjen seinere er det bare å si ifra.

gxi · 25. november 2007

Jeg har et konsept, men jeg måtte gjøre en ripup av den siden jeg fant en rekke svakheter. Gi meg 2-3 dager til, så skal jeg fikse den.

peros2k · 27. november 2007

Fått benka md5'en?

MC2 · 28. november 2007

Sorry folkens, jeg har hatt otrolig mye bullshit juridisk papirarbeid å gå gjennom, men her er resultatene.

Det var veldig kult at så mange deltok denne gangen og det er selvfølgelig en selvfølge at det var mye bra kode! Og det var noen veldig kreative løsninger.

Alle algoritmene ble benket 8·50=400 ganger med disse hashene:

	[0] => d5e2a2c9141206704cdace7df654ca7e	hei
[1] => cfcd208495d565ef66e7dff9f98764da	0
[2] => c4ca4238a0b923820dcc509a6f75849b	1
[3] => eccbc87e4b5ce2fe28308fd9f2a7baf3	3
[4] => e1eee5e2b42d45443cdc82db1a3bc465	034
[5] => a35aea60fe097c885568babb48ee7d1e	1b
[6] => bcedc450f8481e89b1445069acdc3dd9	wow
[7] => 0cc175b9c0f1b6a831c399e269772661	a

Resultater:

Daniel
	Total:			  36.7975025177
	Average:			0.735950050354
	Standard deviation: 0.0352020583838
	Max:				0.977779865265
	Min:				0.724782943726


Kagee
	Total:			  10.0919473171
	Average:			0.201838946342
	Standard deviation: 0.00136753938106
	Max:				0.207407951355
	Min:				0.199916124344


LNaitsirhC
	Total:			  173.200452089
	Average:			3.46400904179
	Standard deviation: 0.0562789638316
	Max:				3.68528795242
	Min:				3.43253397942


Rasks
	Total:			  23.7560808659
	Average:			0.475121617317
	Standard deviation: 0.00275554420094
	Max:				0.486339092255
	Min:				0.471465110779


jonepet
	Total:			  18.4752135277
	Average:			0.369504270554
	Standard deviation: 0.00229983061766
	Max:				0.380570888519
	Min:				0.366122961044


peros2k
	Total:			  19.5634434223
	Average:			0.391268868446
	Standard deviation: 0.0337674196978
	Max:				0.624979972839
	Min:				0.383324861526

I tillegg deltok også Hellkeepa med en løsning som er litt annerledes, derfor ikke tatt med i konkurransen.

Hellkeepa
	Average:			2.98941993713
	Standard deviation: 0.206195195557
	Max:				3.13522195816
	Min:				2.84361791611

Som vi ser er Kagee vinneren etterfulgt av jonepet og peros2k kort etterpå. Vi gratulerer Kagee! :fun: og hannes algoritme:

<?php 
function Kagee($md5_sjekksum) {
/*
Scriptet baserer seg på brute force 
i og med at det genererer alle mulige sjekksummer,
fra og med a til 999, sammenligner m5d-haset
og avslutter (setter $stop = TRUE;) når er
resultat er funnet.

Den begynner med å sjekke om sjekksumen er en tom
string, selv om dette ikke står i oppgaven,
for deretter å sjekke a-9, aa-99 og til slutt aaa-999
*/

$mulige_tegn = array(
'a','b','c','d','e','f','g','h','i','j',
'k','l','m','n','o','p','q','r','s','t',
'u','v','w','x','y','z','0','1','2','3',
'4','5','6','7','8','9');

$antall_mulige_tegn = count($mulige_tegn);

// MD5-sjekksummen for en tom string
$md5_tom_string = 'd41d8cd98f00b204e9800998ecf8427e';

// Denne variabelen settes til TRUE når vi har
// funnet et riktig resultat
$stop = FALSE;

// Sjekk om koden er '';
if ($md5_sjekksum == $md5_tom_string) { 
	$stop = TRUE;
//		 echo "Koden er en tom string ('')\n";
return "";
}

// Sjekk passord på 1 tegn
if (!$stop) {
	for ($teller_1 = 0; $teller_1 <= 35; $teller_1++) {
		$md5 = md5($mulige_tegn[$teller_1]);
		if ( $md5 == $md5_sjekksum ) {
			$stop = TRUE;
//				 echo 'Kode funnet via listesøk: ' . $mulige_tegn[ $teller_1 ] . "\n";
return $mulige_tegn[$teller_1];
			break;
		}
	}
}

// Sjekk passord på 2 tegn
if (!$stop) {
	for ($teller_1 = 0; $teller_1 <= 35; $teller_1++) {
		if ($stop) { break; }
		for ($teller_2 = 0; $teller_2 <= 35; $teller_2++) {
			$md5 = md5($mulige_tegn[$teller_1].$mulige_tegn[$teller_2]);
			if ($md5 == $md5_sjekksum) {
				$stop = TRUE;
//					 echo 'Kode funnet via listesøk: ' . $mulige_tegn[ $teller_1 ] . $mulige_tegn[ $teller_2 ] . "\n";
return $mulige_tegn[$teller_1].$mulige_tegn[$teller_2];
				break;
			}
		}
	}
}

if (!$stop) {
	for ($teller_1 = 0; $teller_1 <= 35; $teller_1++) {
		if ($stop) { break; }
		for ($teller_2 = 0; $teller_2 <= 35; $teller_2++) {
			if ($stop) { break; }
			for ($teller_3 = 0; $teller_3 <= 35; $teller_3++) {
				$md5 = md5($mulige_tegn[$teller_1].$mulige_tegn[$teller_2].$mulige_tegn[$teller_3]);
				if ($md5 == $md5_sjekksum) { 
					$stop = TRUE; 
//						 echo 'Kode funnet via listesøk: '.$mulige_tegn[$teller_1].$mulige_tegn[$teller_2].$mulige_tegn[$teller_3]."\n"; 
return $mulige_tegn[$teller_1].$mulige_tegn[$teller_2].$mulige_tegn[$teller_3];
					break;
				}
			}
		}
	}
}

// Listesøket fungerte ikke, og vi
// antar at brukeren oppgav en ugyldig sjekksum/kode
if (!$stop) { echo "Dette verktøyet kan kun knekke MD5-sjekksummer som består av [a-z0-9] med 0-3 tegn \n"; }

}

?>

Her er deltagerne:

Daniel

<?php
function Daniel($hash)
{
$charbank = array();

for($num = 97; $num < 123; $num++)
{
	$charbank[] = chr($num);
}

for($num = 48; $num < 58; $num++)
{
	$charbank[] = chr($num);
}

for($num1 = 0; $num1 < 36; $num1++)
{
	$tmp = '';
	if($num1 >= 0) $tmp .= $charbank[$num1];
	if(md5($tmp) == $hash)
	{
		return $tmp;
		break 1;
	}

	for($num2 = 0; $num2 < 36; $num2++)
	{
		$tmp = '';
		if($num1 >= 0) $tmp .= $charbank[$num1];
		if($num2 >= 0) $tmp .= $charbank[$num2];
		if(md5($tmp) == $hash)
		{
			return $tmp;
			break 2;
		}

		for($num3 = 0; $num3 < 36; $num3++)
		{
			$tmp = '';
			if($num1 >= 0) $tmp .= $charbank[$num1];
			if($num2 >= 0) $tmp .= $charbank[$num2];
			if($num3 >= 0) $tmp .= $charbank[$num3];
			if(md5($tmp) == $hash)
			{
				return $tmp;
				break 3;
			}
		}
	}
}
}
?>

Hellkeepa:

<?php

/**
* Looks up the given MD5-hash, and returns it's original value.
*
* @param string $Hash
* @return string
*
* @author Hellkeepa ([email protected])
* @copyright Protected by Norwegian Law.
* @version 1.0
*/
function Hellkeepa ($Hash) {
// Define URI to check hash against.
$URI = 'http://milw0rm.com/md5/search.php';

// Define cURL options.
$Options = array (
		CURLOPT_POST => true,
		CURLOPT_HEADER => false,
		CURLOPT_USERAGENT => "Hellkeepa's MD5-cracker",
		CURLOPT_FORBID_REUSE => false,
		CURLOPT_ENCODING => "text/html",
		CURLOPT_POSTFIELDS => "hash=$Hash",
		CURLOPT_RETURNTRANSFER => true
);

// Open connection, and set options.
$Handle = curl_init ($URI);
curl_setopt_array ($Handle, $Options);

// Execute query, and retrieve results.
$Res = curl_exec ($Handle);

// Clean up result.
$End = 2126 - strpos ($Res, "\n", 2126);
$Res = substr ($Res, 2126, $End);

// Retrieve original string and return it.
$Res = preg_match ('#\>([^<]+)\</TD\>#', $Res, $Matches);
return $Matches[1];
}

?>

jonepet

<?php
function jonepet($input) {
	function testString($input, $string) {
		return (md5($string) === $input);
	}

	$maxLength = 3;
	$charset = 'abcdefghijklmnopqrstuvwxyz0123456789';

	$currentString = $charset[0];
	$editPosition = 0;
	$currentStringIndex = array();
	$currentPosition = 0;
	$currentCharsetIndex = 0;
	$charsetMaxValue = strlen($charset)-1;

	$collision = false;
	while (($currentPosition < $maxLength) && ($collision === false)) {
		$index =& $currentStringIndex[$currentPosition];
		$editPosition = $currentPosition;
		if ($index > $charsetMaxValue) {
			$index = 0;
			$currentString[$currentPosition] = $charset[0];
			++$currentPosition;
		} else {
			$currentPosition && --$currentPosition;
		}
		$currentString[$editPosition] = $charset[$index];
		++$index;

		testString($input, $currentString) && ($collision = $currentString);
	}

	return $collision;
}
?>

LNaitsirhC

<?php
function LNaitsirhC($x) {
$tall1 = 0;
while($tall1 < 37){
	$tall2 = 0;
	while($tall2 < 37){
		$tall3 = 1;
		while($tall3 < 37){
			  if ($tall1 == 0 && $tall2 == 0){$tall4 = ".$tall3.";}
			  elseif ($tall1 == 0){$tall4 = ".$tall2..$tall3.";}
			else {$tall4 = ".$tall1..$tall2..$tall3.";}
			$bytt = str_replace(".1.", "a", $tall4);
			$bytt = str_replace(".2.", "b", $bytt);
			$bytt = str_replace(".3.", "c", $bytt);
			$bytt = str_replace(".4.", "d", $bytt);   
			$bytt = str_replace(".5.", "e", $bytt);
			$bytt = str_replace(".6.", "f", $bytt);
			$bytt = str_replace(".7.", "g", $bytt);
			$bytt = str_replace(".8.", "h", $bytt);   
			$bytt = str_replace(".9.", "i", $bytt);
			$bytt = str_replace(".10.", "j", $bytt);
			$bytt = str_replace(".11.", "k", $bytt);
			$bytt = str_replace(".12.", "l", $bytt);   
			$bytt = str_replace(".13.", "m", $bytt);
			$bytt = str_replace(".14.", "n", $bytt);
			$bytt = str_replace(".15.", "o", $bytt);
			$bytt = str_replace(".16.", "p", $bytt);		   
			$bytt = str_replace(".17.", "q", $bytt);
			$bytt = str_replace(".18.", "r", $bytt);
			$bytt = str_replace(".19.", "s", $bytt);
			$bytt = str_replace(".20.", "t", $bytt);   
			$bytt = str_replace(".21.", "u", $bytt);
			$bytt = str_replace(".22.", "v", $bytt);
			$bytt = str_replace(".23.", "w", $bytt);
			$bytt = str_replace(".24.", "x", $bytt);   
			$bytt = str_replace(".25.", "y", $bytt);
			$bytt = str_replace(".26.", "z", $bytt);
			$bytt = str_replace(".27.", "0", $bytt);
			$bytt = str_replace(".28.", "1", $bytt);   
			$bytt = str_replace(".29.", "2", $bytt);
			$bytt = str_replace(".30.", "3", $bytt);
			$bytt = str_replace(".31.", "4", $bytt);
			$bytt = str_replace(".32.", "5", $bytt);   
			$bytt = str_replace(".33.", "6", $bytt);
			$bytt = str_replace(".34.", "7", $bytt);
			$bytt = str_replace(".35.", "8", $bytt);
			$bytt = str_replace(".36.", "9", $bytt);

			if (md5($bytt) == $x){
				return $bytt;
			}
			else {
				$tall3++;
			}
		}
		$tall2++;
	}
	$tall1++;
}
}
?>

peros2k

<?php

function peros2k($md5) {
$arr = array_merge(str_split("etaoinshrdlcumwfgypbvk0123456789jxqz"), array(""));
foreach ($arr as $a)
foreach($arr as $b)
	foreach($arr as $c)
		if (md5("$a$b$c") === $md5)
			return "$a$b$c";
}

?>

Rasks

<?php
function Rasks($hash) {
$array = array("a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"); 

foreach($array as $a) {
	if(md5($a) == $hash) {
		return $a;
		break;
	}

	foreach($array as $b) {
		if(md5($a.$b) == $hash) {
			return $a.$b;
			break 2;
		}

		foreach($array as $c) {
			if(md5($a.$b.$c) == $hash) {
				return $a.$b.$c;
				break 3;

			}
		}
	}
}
}
?>

Som sagt var det veldig artig at så mange deltok, men jeg må dessverre melde at jeg har gått tom for oppgaver som ikke er alt for vanskelige, så det er bare å brainstorme ideer

Endret 28. november 2007 av MC2

PHP challenge 6: Leksikon sortering (update 2)

Anbefalte innlegg

Lenke til kommentar

Videoannonse

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Opprett konto

Logg inn

Hvem er aktive 0 medlemmer