[PHP] Brute force tekst ontcijferen

[Verwijderd]

Voor een opdracht op school moeten we een tekst decoderen, ik wilde hiervoor graag een PHP scriptje proberen te maken die gewoon alle mogelijkheden naloopt, maar ik weet niet precies hoe het op te zetten. De code die we krijgen ziet er ongeveer zo uit:

MJHE\ KOE[P KOEM[ NE\A[ JUI]E

Het is dus eigenlijk een vrij simpele codering, elk teken staat gewoon voor een letter in het alfabet.
Er zijn dus in totaal 29 tekens die gebruikt worden, het alfabet (26) + \ ] [ (3)
Iemand een idee hoe dit in PHP te realiseren?

[NMe]

Wat heb je zelf al geprobeerd en wat lukte er niet aan? Het is natuurlijk niet de bedoeling dat wij je huiswerk gaan zitten maken.

[sirdupre]

Volgens mij duurt dat nog best lang om te brute-forcen. En wil je alle uitkomsten nalopen met de hand? Dat zijn er namelijk nogal wat .

Volgens mij kan je beter met tekenfrequenties aan de slag enzo. Als je weet welke taal de invoer is, gaat dat denk ik wel wat sneller, als je de frequenties van je invoer matcht met de frequenties van die taal. Vervolgens kan je met een slimme localsearch techniek en een woordenlijst ofzo de computer waarschijnlijk wel laten checken wat een zeer waarschijnlijke vertaling is.

[Verwijderd]

Ik heb problemen met het uitvogelen van die mogelijkheden, heb nu 2 loopjes waarin ik elk teken dat voorkomt in die tekst vervang met een letter uit het alfabet, maar dan krijg ik dus geen mogelijke ontcijfering!

PHP:

        foreach($uniquechars as $uc) {
            foreach($this->alfabet as $ac) {
                echo "we gaan $uc vervangen met $ac\n";
                echo strtr($this->theString, $uc, $ac);
            }       
        }

Ik moet gewoon ff op weg geholpen worden want ben even de kluts kwijt:D

[NMe]

Je hoeft (in de simpelste vorm) toch alleen maar een string te doorlopen, en voor elk mogelijk karakter te kijken of het dat karakter is op die plaats? Je hebt daar geen replace voor nodig, maar gewoon een vergelijking, om vervolgens ergens anders de totale string bij te houden?

edit:
Niet goed begrepen.

[ Voor 7% gewijzigd door NMe op 03-05-2006 13:14 ]

[Suaver]

Misschien handig om eerst te kijken welke letters vaak voorkomen in je syntax? En dan al kleine mogelijke dingen invullen bijv de 'e'.

[J2pc]

[hier stond een wazig verhaal]

Een mooie recursieve methode maken die je string doorloopt, de woorden vergelijkt met een woordenlijst en rekening houdt met vergelijkingen van vorige woorden.

Op die manier hou je een aantal mogelijk opties over, waarvan je dan zelf de goede uit kan kiezen.

[ Voor 76% gewijzigd door J2pc op 03-05-2006 11:08 ]

[Verwijderd]

Ja maar hoe maak je zo'n recursieve functie in PHP ?? Zit nu al een hele tijd te proberen maar kom er nog niet uit

[Verwijderd]

Als je dit wilt brute forcen moet je 29! = 8841761993739701954543616000000 mogelijkheden doorlopen. Dat lijkt me niet erg handig.

Je kunt inderdaad het beste met tekenfrequenties iets doen, beginnen met de meest waarschijnlijke sleutel en steeds minder waarschijnlijker sleutels uitproberen.

[Verwijderd]

Er kunnen nooit zoveel mogelijkheden zijn, je gebruikt nooit alle tekens, plus je kan ook een klein stukje uit de tekst pakken en die gaan decoderen. Het gaat er trouwens ook niet om dat het veel mogelijkheden zijn (dat snap ik ), maar gewoon hoe die mogelijkheden te berekenen!

[Janoz]

Nou, ga ze allemaal maar eens even tellen. 29! zal het wel niet zijn, maar het zal wel in die orde van grootte zijn. Waarom denk je dat brute force methoden over het algemeen zo lang duren? Denk aan al die distributed projecten als DPC waarbij 100-den computers over de hele wereld lopen te rekenen op een klein stringetje.

Waar ik me eerder druk over zou maken is bepalen wanneer je daadwerkelijk een antwoord hebt. Ik neem niet aan dat je alle 29! mogelijkheden met de hand gaat controleren?

[Verwijderd]

Neee ik wil gewoon de string die gedecodeerd is checken op bepaalde woorden (bijvoorbeeld "de" "het" "een") en dan kijken of het een positief resultaat is.

[Janoz]

Worden de spaties niet gecodeerd? In dat geval zou je namelijk een 3 letter term kunnen gebruiken en deze vervolgens met een dictionary attack kunnen aanvallen. Hetzelfde met andere kortere woorden.

Owh, en de term die je door google kunt gooien is permutatie of permutation.

[ Voor 17% gewijzigd door Janoz op 03-05-2006 12:25 ]

[Verwijderd]

Er zitten geen spaties of andere leestekens in de tekst.

[Verwijderd]

Verwijderd schreef op woensdag 03 mei 2006 @ 12:25:
Er zitten geen spaties of andere leestekens in de tekst.

Er zitten wel degelijk spaties in hetgeen je hier post.

[Verwijderd]

Ja oke de tekst is opgesplitst in blokken van 5 karakters, maar in de originele tekst zitten geen spaties, dus alles achter elkaar

[Janoz]

Je zult dus een mapping moeten maken tussen de tekens. Het aantal manieren waarop je een lijst met 29 tekens kunt husselen is inderdaad 29!.

Stel elke hussel + controle zou 1 micro seconde duren (dus niet mili), dan zal je script nog steeds 29!/(1000000 * 60 * 60 * 24 * 365) = 280.370.433.591.441.589 jaar nodig hebben om alle mogelijkheden te controleren.

Het lijkt me daarom handig om het hele idee maar even uit je hoofd te zetten en inderdaad tot de conclusie komen dat een simpele brute force oplossing zo goed als onmogelijk is.

[Gerco]

Als het een schoolopdracht is, lijkt het me niet de bedoeling dat je er enkele duizenden millenia aan gaat besteden. Er is dus een makkelijker manier om de opdracht te volbrengen dan brute force (of is het een cryptografie prakticum? In dat geval kan het een strikvraag zijn, inzicht kweken heet dat).

Geef eens wat meer informatie over de opleiding en opdracht, want als dit alles is, zul je aan een computer niet veel hebben en met handmatige analyse waarschijnlijk een stuk sneller klaar zijn.

[ Voor 9% gewijzigd door Gerco op 03-05-2006 13:09 ]

[Verwijderd]

Is het niet gewoon een Caesar codering waarbij er een x aantal plaatsen in het alfabet is opgeschoven?

[Creepy]

Verwijderd schreef op woensdag 03 mei 2006 @ 13:10:
Is het niet gewoon een Caesar codering waarbij er een x aantal plaatsen in het alfabet is opgeschoven?

Dat lijkt er wel op ja. Spaties in de gecodeerde tekst zijn ook spaties in de daadwerkelijke tekst. Dus maximaal 29 opties op te proberen dat is (erg) goed te bruteforces. Welke optie je moet hebben is handmatig makkelijk te controleren of je controleert of er bepaalde bekende woorden in staan (de het een etc.)

* Creepy moet wakker worden. Dat is dus niet het geval..

Wel frappant.. geen spaties in de tekst en geen spaties in 1 van de 29 tekens. Er lijkt iets niet helemaal te kloppen aan de informatie die we nu hebben.

[ Voor 51% gewijzigd door Creepy op 03-05-2006 13:19 ]

[Verwijderd]

Creepy schreef op woensdag 03 mei 2006 @ 13:15:
[...]

Dat lijkt er wel op ja. Dus maximaal 29 opties op te proberen dat is gied te bruteforces. Welke optie je moet hebben is handmatig makkelijk te controleren of je controleert of er bepaalde bekende woorden in staan (de het een etc.)

Jep, en de [, ] en / zij toegevoegd om te voorkomen dat er gewoon een standaard script van het net gejat wordt denk ik zo.

[Verwijderd]

Andere optie: er zitten geen spaties in. De TS heeft het voor de vorm opgesplitst in 4 blokken van 5. Is het nu een tekst of slechts één woord?

In het laatste geval, pak een dictionairy, gebruik enkel de woorden met 20 letters, kies een veel voorkomend karakter uit de gecodeerde tekst en probeer dat te matchen.

edit:

Dat had wel een post mogen zijn...

Er worden ook maar 14 van de 29 karakters gebruikt.

[ Voor 16% gewijzigd door Verwijderd op 03-05-2006 13:26 ]

[frickY]

Met alleen deze informatie is het onmogelijk om de gegeven cipher te bruteforcen. Je hebt of meer informatie over de key nodig, of over het gebruikte algoritme
Er kan nu net zo goed gebruik gemaakt zijn van een shift-algoritme, als van een blok-cipher, of welke andere coderingsmethode dan ook. Je zult nooit kunnen verifiïeren of je eventueel gevonden antwoord correct is.

//Edit

Het is dus eigenlijk een vrij simpele codering, elk teken staat gewoon voor een letter in het alfabet.

Doh.. over het hoofd gezien
In dat geval gewoon een dictionary pakken

[ Voor 23% gewijzigd door frickY op 03-05-2006 13:31 ]

[Gerco]

Het is in ieder geval geen eenvoudige transpositie, ik heb net alle offsets van 1 t/m 29 uitgeprobeerd en elke keer kwam er onzin uit. Dat was ook veel te makkelijk geweest natuurlijk

[DamadmOO]

Kijk gewoon even naar de ascii tabel en ik heb zo'n gevoel dat je dan snel genoeg je antwoord hebt.
Ze hebben niet voor niks de [, de \ en de ] gebruikt

[ Voor 4% gewijzigd door DamadmOO op 03-05-2006 13:43 . Reden: ansi != ascii :P ]

[marko77]

Gerco schreef op woensdag 03 mei 2006 @ 13:33:
Het is in ieder geval geen eenvoudige transpositie, ik heb net alle offsets van 1 t/m 29 uitgeprobeerd en elke keer kwam er onzin uit. Dat was ook veel te makkelijk geweest natuurlijk

Dat heb ik idd ook geprobeerd, en daar komt niets uit.

Hebben ze niet meer informatie gegeven over de gebruikte encryptie techniek oid? op deze manier blijf je namelijk gissen en voor een schoolopdracht gaat het dan al gauw te lang duren imo

[Janoz]

Verwijderd schreef op woensdag 03 mei 2006 @ 13:22:
Er worden ook maar 14 van de 29 karakters gebruikt.

Maar dat betekend nog niet dat je ook maar uit 14 karakters moet kiezen. dan nog heb je 29! / 14! mogelijkheden.

* Janoz sluit zich aan bij het 'het is een strikvraag om inzicht te kweken' kamp. (mits er ineens wel een berg informatie boven tafel komt die de TS vergeten is te melden)

[Verwijderd]

Weet je de uitkomst van te voren? Zo niet dan is dat juist het moeilijkste, dat je altijd met de hand moet controleren of het de juiste uitkomst is. Dan is ineens niet de computer de bottleneck, ookal zou hij alle mogelijke teksten binnen 10 seconden kunnen genereren, dan ben jij nog een eeuwigheid bezig om alle mogelijke antwoorden te controlleren.

Toch zijn deze encryptie methodes te kraken zonder dat je ontelbare mogelijkheden met de hand moet controlleren. Dat is namelijk met behulp van statistiek. Dit is een vak apart en lijkt me ook niet helemaal de bedoeling dat je dat moet programmeren...

[ Voor 3% gewijzigd door Verwijderd op 03-05-2006 21:38 ]

[OnTracK]

Ik denk dat je nog het meeste kan met dit stukje: "KOE[P KOEM[" in combinatie met een dictionary (als tenminste het een simpele codering is waarbij een letter altijd een andere vaste letter oplevert.

Zoek twee (onderdelen van) woorden die met dezelfde drie letters beginnen, waarvan de 4e letter van het eerste woord, de 5e letter van het tweede woord is.

[ Voor 66% gewijzigd door OnTracK op 03-05-2006 21:45 ]

[Verwijderd]

Het nummer 29 (de eerste priem groter dan 26) zou kunnen betekenen dat het gaat om een "multiplicative cipher". Als je er een algoritme voor schrijft om dat te ontcijferen, hoef je maar 28 pogingen te doen: voor elke mogelijke key 1.

[ Voor 41% gewijzigd door Verwijderd op 03-05-2006 22:39 ]

[Gomez12]

Gaat het hier om een voorbeeldje of is dit de daadwerkelijk tekst??? Indien dit de tekst is, dan heb je maar 29*14 ( aantal verschillende letters ) = 406 combinaties om af te gaan, even uitwerken in php en met de hand nalopen, ben je er volgens mij zo.

Indien de echte tekst een stuk langer is (vb 1 a4'tje) dan moet je gewoon wat statistiek van de taal erbij pakken zodat je eerst kan kijken naar de veel voorkomende letters in de taal ( e ) en dan kijken wat in jouw stuk tekst de veel voorkomende letters zijn, probeer dit overeen te laten komen en dan van waarschijnlijk naar onwaarschijnlijk gaan en kijk dan eens hoever je komt.
Bijv de q kan je in 1e instantie vergeten, wordt heel weinig gebruikt.

Is het trouwens echt zo dat 1 gecodeerde letter 1 gedecodeerde letter is? Wat zijn dan de 3 extra tekens...
Of kan het ook gewoon 2 gecodeerde letters 1 gedecodeerde letter zijn.

Of je zoekt even op de methode van cheatah klinkt ook heel interessant ( alhoewel ik er zo snel geen goede uitleg van kan vinden ( na 1 sec googlen ))

[vbmot]

Verwijderd schreef op woensdag 03 mei 2006 @ 21:37:
Dat is namelijk met behulp van statistiek. Dit is een vak apart en lijkt me ook niet helemaal de bedoeling dat je dat moet programmeren...

Zo moeilijk lijkt het me in dit geval niet. Je moet zoveel mogelijk over de tekst te weten zien te komen (taal, bron, schrijver, uit welke tijd het komt). Vervolgens pak je een stuk tekst dat zoveel mogelijk overeenkomsten heeft en je kijkt naar het percentage waarmee elk karakter in de tekst voorkomt. Daarna bepaal je de percentages van elk karakter uit de te ontcijferen tekst. Vervolgens kun je gaan zoeken naar vergelijkbare percentages en/of gewoon de volgorde aflopen. Bijv: meest voorkomende karakter uit normale tekst is 'e' met 30% [ik zeg maar wat]. Vervolgens vervang je het meest voorkomende karakter uit de te kraken tekst door 'e'. Ongetwijfeld zijn er hele geavanceerde algoritmes voor, maar ik denk dat je hier al best ver mee komt. Het is natuurlijk wel zo dat dit bij wat langere teksten veel beter werkt dan bij een kort zinnetje.

M'n handen jeuken om even snel iets te coden, maar het is al laat en ik moet morgen werken (nog meer code dus ). Succes in elk geval!

[Janoz]

@OnTrack: De spaties in het gegeven voorbeeld is niet een scheiding tussen een woord. Het zijn niet allemaal woorden van 5 letters.

@Gomez12: Er zijn, zoals ook wel eerder aangegeven in dit topic, wel heel wat meer dan 406 mogelijkheden. Voor de M kun je uit 29 mogelijkheden kiezen. Vervolgens kun je voor de J uit de overgebleven 28 mogelijkheden kiezen. Voor die 2 letters zijn het aantal mogelijkheden dus al 29*28. Dan komen er dus nog 12 letters.

[OnTracK]

Janoz schreef op donderdag 04 mei 2006 @ 09:43:
@OnTrack: De spaties in het gegeven voorbeeld is niet een scheiding tussen een woord. Het zijn niet allemaal woorden van 5 letters.

Daarom zei ik ook "onderdelen van woorden"

Inderdaad, ik heb het een beetje vreemd geformuleerd, maar het zoeken van gelijke opeenvolgende letters in een dictionary opzoeken lijkt me makkelijker dan willekeurige letters. Nu er dus series van tekens overeenkomen heb je al snel een beperkte lijst met woorden waarmee je verder kunt werken, met het extra "[" teken erbij beperk je dit zelfs zóveel dat (ik vermoed dat) je maar enkele "delen van" woorden overhoud.

[ Voor 4% gewijzigd door OnTracK op 04-05-2006 10:58 ]