Entschlüsselungsalgorithmus

[Karl]

Hey ho.
Es gibt da so ein Spiel, in dem basierend auf dem Spielernamen (der einfachste Fall wäre _wahrscheinlich_ a) und der erreichten XP-Zahl ein Code erstellt wird.
Diesen kann man dann im Spiel wieder eingeben und wird dekodiert.
Wenn der Code gültig ist, hat man seine gespeicherten XP-Punkte wieder.
Also: Man hat den Schlüssel, auf dessen Basis kodiert wird (Der Spielername), man hat den Code und man hat die XP-Zahl (=auch ein Schlüssel?).
Es muss doch eigentlich machbar sein, daraus zu schließen, wie der Code erstellt wird, oder?
Dass der Code zu schwer zum knacken ist, glaube ich ganz einfach aus dem Grund nicht, dass es sich um eine Warcraft 3 Karte handelt, die auch nur mit beschränkten Mitteln (dem Editor) arbeiten kann :p
Wie könnte man einen Algorithmus schreiben, der das ganze knacken kann?
Im Prinzip hat man ja nur eine Unbekannte und das sollte ja machbar sein.
Der Code beschränkt sich übrigens auf 6 Zeichen.

[keppla]

Wie könnte man einen Algorithmus schreiben, der das ganze knacken kann?

wenn ich dich richtig verstehe, suchst du einen Algorithmus, der dir "den" Algorithmus der zur Entschlüsselung eines Textes anhand des Plaintexts, Cyphertextes und des Keys ausgibt?
Ich bezweifele, dass das geht. Und ich würde stark vermuten, dass, wenn du das schaffst, du kurz später ein Jobangebot von der NSA hast

Im Prinzip hat man ja nur eine Unbekannte und das sollte ja machbar sein.

Ok, was würde denn ein hypothetischer Algorithmus aus folgenden Eingaben (plaintext -> cyphertext) für einen Algorithmus extrahieren?

16 -> 8
12 ->6
8 -> 4

was wäre das Ergebnis für den plaintext "4" (müsste man ja vorhersagen können, wenn man den algorithmus kennt)?
ist es 2, weil der algorithmus sagt "zahl halbieren" oder ist es 4, weil der algorithmus sagt "anzahl der buchstaben des deutschen wortes (umlaute als ae, oe) für die Zahl" oder 23, weil der algorithmus einer der beiden oberen ist, ergänzt um "ausser, wenn es 4 ist, dann ist das Ergebnis 23"?
Zu einer begrenzten Menge von Ergebnissen sind beliebig viele Algorithmen denkbar, die diese Ergebnisse liefern.

[ne0h]

Ich weiss zwar nicht, wo Deine Intentionen liegen, aber wie wärs mit nem simplen Bruteforce Script?

Bei 6 Zeichen Länge und einem Zeichensatz von...hmm....z.B. 62 Zeichen (Was A-Z, a-z und 0-9 einschließen würde) hättest Du also 62 hoch 6 Möglichkeiten, also: 56800235584 Mögliche Kombinationen.

Wenn man dabei betrachtet, dass laut Stand Januar 08 ein normaler Durchschnittsrechner ca. 167 Mill. Möglichkeiten pro Sekunde schafft, dann wäre ein Bruteforce Skript in ca: 56800235584 / 167000000 = 340 Sekunden oder ca 5,7 Minuten fertig.

Also, viel Erfolg!


ne0h

[Karl]

Wie könnte man einen Algorithmus schreiben, der das ganze knacken kann?

wenn ich dich richtig verstehe, suchst du einen Algorithmus, der dir "den" Algorithmus der zur Entschlüsselung eines Textes anhand des Plaintexts, Cyphertextes und des Keys ausgibt?
Ich bezweifele, dass das geht. Und ich würde stark vermuten, dass, wenn du das schaffst, du kurz später ein Jobangebot von der NSA hast

Im Prinzip hat man ja nur eine Unbekannte und das sollte ja machbar sein.

Ok, was würde denn ein hypothetischer Algorithmus aus folgenden Eingaben (plaintext -> cyphertext) für einen Algorithmus extrahieren?

16 -> 8
12 ->6
8 -> 4

was wäre das Ergebnis für den plaintext "4" (müsste man ja vorhersagen können, wenn man den algorithmus kennt)?
ist es 2, weil der algorithmus sagt "zahl halbieren" oder ist es 4, weil der algorithmus sagt "anzahl der buchstaben des deutschen wortes (umlaute als ae, oe) für die Zahl" oder 23, weil der algorithmus einer der beiden oberen ist, ergänzt um "ausser, wenn es 4 ist, dann ist das Ergebnis 23"?
Zu einer begrenzten Menge von Ergebnissen sind beliebig viele Algorithmen denkbar, die diese Ergebnisse liefern.

Mir ist klar, dass ich am besten mehrere Werte benutzen muss, um den Algorithmus möglichst eindeutig zu finden.
Gehen wir mal davon aus, dass der Algorithmus immer das selbe macht und keine speziellen Ausnahmen oder sonstiges hat.
Wir haben uum Beispiel sowas:
Username: Karl
Code: EHT510
XP: 4
(Gesucht: Der Algorithmus, der aus XP: 4 und Username: Karl -> Code EHT510 macht)
Und dann nochmal einen Datensatz nur mit anderen Informationen.
Vielleicht würde es ja auch schon reichen, einfach die beiden Datensätze auf die Unterschiede hin zu vergleichen.
Aber es gibt ja so viele Möglichkeiten ...
Ich würde mal ins Schwarze tippen, dass nicht alle Buchstaben des Namens gebraucht werden sondern zum Beispiel nur der Erste und der Letzte, aber das sind ja nur irgendwelche Spekulationen :p

Es muss doch möglich sein, die ganzen Datensätze so zu analysieren, dass man rausfinden kann, wie der Algorithmus funktioniert. Zumindest wie er bei diesen Beispielen funktioniert. Wenn man nur XP-Werte bis 9 überprüft, kann es zwar immer noch sein, dass er ab 10 anders arbeitet, aber sowas kann man wohl erstmal außer Acht lassen ...

Edit zu Bruteforce:
Öhm, ich hab nur keine Idee, wie mich hier Bruteforce weiterbringt Ich kann die ausgespuckten paar-Millionen Werte wohl kaum direkt überprüfen. Warcraft 3 macht das sicher nicht mit

[keppla]

Was genau möchtest du von den Lesern erfahren?
Den Algorithmus, der aus dem Namen und den XP den Code macht? Dann solltest du den Lesern ein paar mehr Beispiele nennen, und es vielleicht eher in einem Kryptografieforum fragen (nicht, dass ich dich verscheuchen will, wäre dann nur Offtopic).
Einen Algorithmus, dem du einige Eingaben und einige Ausgaben gibst, und der dir einen Algorithmus ausgibt, der die Eingaben in die Ausgaben verwandelt? Das dürfte so ziemlich der Heilige Gral der Informatik sein (und ich bezweifele weiterhin das es möglich ist).

Vielleicht würde es ja auch schon reichen, einfach die beiden Datensätze auf die Unterschiede hin zu vergleichen.

Wenn du es "händisch" machen willst, und aus irgendeinem Grund nicht einfach die War3-Karte mit einem Karteneditor angucken kasst, würde ich empfehlen, dir Datensätze für den gleichen Namen mit unterschiedlichen XP und welche für unterschiedliche Namen mit gleichen XP organisieren. Auf so eine Art hab ich die Logik hinter den Passwörtern für Mega Man 3 rausbekommen.

[Karl]

Was genau möchtest du von den Lesern erfahren?
Den Algorithmus, der aus dem Namen und den XP den Code macht? Dann solltest du den Lesern ein paar mehr Beispiele nennen, und es vielleicht eher in einem Kryptografieforum fragen (nicht, dass ich dich verscheuchen will, wäre dann nur Offtopic).
Einen Algorithmus, dem du einige Eingaben und einige Ausgaben gibst, und der dir einen Algorithmus ausgibt, der die Eingaben in die Ausgaben verwandelt? Das dürfte so ziemlich der Heilige Gral der Informatik sein (und ich bezweifele weiterhin das es möglich ist).

Naja es geht hier auch wahrscheinlich eher um eine relativ einfache Verschlüsselung. Ich vermute halt sowas wie: Nimm den ersten und letzten Buchstaben des Namens, Verschiebe ihn um XP im Alphabet, <irgendwelche anderen Sachen>, usw, fertig.
Ein Algorithmus, der sowas erkennen soll, könnte ja anhand eines Beispieles sagen: Der Algorithmus hat einfach das und das gemacht (was bei einem einzigem Beispiel wohl falsch wäre), wenn er jetzt mehrere Untersucht könnte er doch parallelen finden?
Oder vielleicht sogar alle Methoden ausrechnen, die es gibt, um von den vorhandenen Werten auf den Code zu schließen und dieses dann bei den anderen Werten genauso ausrechnen und dann die Schnittmenge davon zurückgeben. Das heißt, welche Methoden bei allen Werten gefunden wurden.

Wenn du es "händisch" machen willst, und aus irgendeinem Grund nicht einfach die War3-Karte mit einem Karteneditor angucken kasst, würde ich empfehlen, dir Datensätze für den gleichen Namen mit unterschiedlichen XP und welche für unterschiedliche Namen mit gleichen XP organisieren. Auf so eine Art hab ich die Logik hinter den Passwörtern für Mega Man 3 rausbekommen.

Ja, ich hatte mir schon überlegt jeweils 2 XP-Werte für die Namen
a, b, ab, ba anzuschaun.
Und dann natürlich noch ein anderes Beispiel, um das ganze zu überprüfen.
Die Karte einfach öffnen geht theoretisch schon. Nur ist sie protected, das heißt, irgend ein Programm hat sie für den Editor unleserlich gemacht (irgendwas entfernt, was für die Map nicht wichtig ist, oder so).
Das ganze lässt sich natürlich auch mit irgendwelchen Tools wieder rückgängig machen, aber 1. liegt der Code dann nur in der grausamen Scriptsprache des Editors vor (wirklich extrem unübersichtlich) und im schlimmsten Falle noch als Einzeiler.
Und 2. lernt man so ja viel mehr :p
Wenn schon cheaten dann auch ehrenhaft (nein eigentlich will ich ja nicht cheaten, ich hab nur zu viel Zeit)

[lunar]

Naja es geht hier auch wahrscheinlich eher um eine relativ einfache Verschlüsselung. Ich vermute halt sowas wie: Nimm den ersten und letzten Buchstaben des Namens, Verschiebe ihn um XP im Alphabet, <irgendwelche anderen Sachen>, usw, fertig.

Dir ist die Komplexität dieses Problems wohl überhaupt nicht bewusst, oder?

Du verlangst etwas in der Art: Gegeben sei x = 10 und y = 500, wobei x=f(y). Finde dasjenige f heraus, welches diese Bedingung erfüllt. Wenn du auch nur ein bisschen Ahnung von Mathematik hast, weißt du, dass es unendlich viele Lösungen gibt. Selbst wenn man die Anzahl der Datensätze beliebig nach oben dreht, hat diese Aufgabe keine eindeutige Lösung.

Ein Algorithmus, der sowas erkennen soll, könnte ja anhand eines Beispieles sagen: Der Algorithmus hat einfach das und das gemacht (was bei einem einzigem Beispiel wohl falsch wäre), wenn er jetzt mehrere Untersucht könnte er doch parallelen finden?

Vielleicht solltest du, nur um zu begreifen, wie komplex das ganze ist, einfach mal versuchen, einen Algorithmus für deine Beispieldaten zu entwickeln. Also code = f(user, xp), wobei code = EHT510, user = Karl, xp = 4 und code = eht510. Gesucht ist f. Versuche das mal zu lösen, und dann als nächsten Schritt deinen Lösungsweg in einen Algorithmus zu gießen. Dann wirst du erkennen, dass schon das nicht einfach ist.

[Karl]

Dass es nicht einfach ist, ist mir klar. Sonst hätte ich schon ein fertiges Programm
Dass es keine eindeutige Lösung gibt, ist mir eigentlich auch klar, wobei, wenn ein Algorithmus bei sagen wir 10 Beispielwerten funktioniert, könnte er ja auch bei den anderen Werten funktionieren
Das eigentliche Problem, das ich habe, wäre: Wie untersuche ich die verschiedenen Werte auf irgendeinen Zusammenhang hin?
Am besten nämlich so, dass das Programm auch nach einer gewissen Zeit zu Ende ist ...
Alle möglichen Zusammenhänge zu überprüfen, geht ja nicht, dann bräuchte das Programm genau unendlich Sekunden
Das Programm müsste eher selbst einen Zusammenhang herstellen, bzw ziemlich viele, wenn es jeden Datensatz aus XP, Name und Code einzeln betrachtet.

Ich glaub halt einfach nicht dran, dass das so unlösbar ist, es wurden doch schon genug Verschlüsselungen solcher Art geknackt, oder?

Sagen wir mal ich habe 100 Sätze, alle Kodiere ich nach folgendem Schema:
Ich schreibe die Buchstaben als Zahlen.
Ich addiere zu den Zahlen jeweils das doppelte vom vorherigem Wert, wobei beim erstem Wert +1 addiert wird.
Ein Computer müsste doch jetzt in der Lage sein, das Muster, nach dem die Sätze kodiert werden, rauszufinden?
Wenn nicht, würde mir nämlich ernsthaft die Frage stellen, warum es extra ein Fachgebiet für Kryptografie gibt.
Und viel anders ist mein Problem ja auch nicht.[/img]

[sma]

Eine bijektive Abbildung zwischen einem Namen und einer Nummer und einem sechsstelligen Code anhand von wenigen Beispielen zu finden, ist schwer. Sehr schwer. Für einfacher würde ich halten, den Code des Editors, dort wo der Code geprüft wird, mit einem Disassembler aufzuspüren und dann zu versuchen, den Algorithmus aus dem Maschinencode zu extrahieren. Doch auch das ist schwer. Eben nur weniger schwer.

Ansonsten: Warcraft 3 ist doch ein recht altes Spiel. Hat das vielleicht schon jemand herausbekommen? Google sagt, es gibt einen inoffiziellen Karteneditor. Und es gibt wohl eine Community rund um das Ändern dieses Spiels. Wusste gar nicht, dass Warcraft sogar eine eigene kleine Programmiersprache benutzt hat...

Stefan

[Karl]

Okay, wenn ihr alle sagt, dass es so schwer ist, glaub ich's euch halt auch mal :p
Ja, Warcraft 3 hat einen Editor mit Scriptsprache (Welche sich auch mit einer GUI bedienen lässt), Jass genannt. Ich find sie total schrecklich :p
Wie oben beschrieben, ist es relativ leicht möglich, die Karte wieder lesbar zu machen (fragt sich nur, wie gut). Ja, man kann das im Prinzip nachschaun Aber ich wollte halt mal versuchen, den Code zu knacken.

[lunar]

@Karl
Kryptographie beschäftigst sich mit der Theorie und dem Entwurf von Chiffren. Das hat mit deinem Problem genau gar nichts zu tun.

Du beschreibst das Reverse Engineering eines Algorithmus basierend auf Ein- und Ausgabedaten. Das ist – wie sma – schon sagte, sehr, sehr schwer.

Natürlich wurden schon viele proprietäre, geheime Algorithmen nachprogrammiert, wie man an den zahllosen Key-Generatoren, Kopüierschutzknackern und Cracks sieht. Allerdings geht man da ganz anders ran: Anstatt Zeit auf das Entwickeln einer bijektiven Abbildung der Daten zu verschwenden, löst man das technisch, in dem man Debugger, Decompiler und andere Tools auf das Originalprogramm loslässt.

[Karl]

@Karl
Kryptographie beschäftigst sich mit der Theorie und dem Entwurf von Chiffren. Das hat mit deinem Problem genau gar nichts zu tun.

Du beschreibst das Reverse Engineering eines Algorithmus basierend auf Ein- und Ausgabedaten. Das ist – wie sma – schon sagte, sehr, sehr schwer.

Natürlich wurden schon viele proprietäre, geheime Algorithmen nachprogrammiert, wie man an den zahllosen Key-Generatoren, Kopüierschutzknackern und Cracks sieht. Allerdings geht man da ganz anders ran: Anstatt Zeit auf das Entwickeln einer bijektiven Abbildung der Daten zu verschwenden, löst man das technisch, in dem man Debugger, Decompiler und andere Tools auf das Originalprogramm loslässt.

Dass Kryptografie sich eheer mit der Theorie und dem Entwurf von Chiffren beschäftigt, ist mir schon klar. Aber mir hat sich die Frage gestellt: Warum der ganze Aufwand, wenn man nichtmal die einfachen Algorithmen knacken kann?
Ein paar Verschiebungen da, ne Fibonacci-Folge hier, ein bisschen hiervon, etwas davon - Und schon kann das kein Computer mehr knacken?
Okay, mir ist auch klar, dass es zum Beispiel um Verfahren geht, wie man Schlüssel zwischen 2 Rechnern so sicher wie möglich austauscht ... Aber wenn's doch so schwer ist, eine Verschlüsselung zu knacken, warum wird dann immer so viel Aufwand betrieben?

[lunar]

Dass Kryptografie sich eheer mit der Theorie und dem Entwurf von Chiffren beschäftigt, ist mir schon klar.

Nicht eher, sondern ausschließlich. Das Brechen von Verschlüsselungen nennt man Kryptanalyse.

Ein paar Verschiebungen da, ne Fibonacci-Folge hier, ein bisschen hiervon, etwas davon - Und schon kann das kein Computer mehr knacken?

Nicht Computer brechen Chiffren, Menschen brechen Chiffren. Ein Computer kann das Brechen eines Algorithmus nur automatisieren.

... Aber wenn's doch so schwer ist, eine Verschlüsselung zu knacken, warum wird dann immer so viel Aufwand betrieben?

Dein Algorithmus ist nicht per se schwer herauszufinden. Mit ein bisschen Reverse Engineering kommt man da mehr oder weniger leicht drauf, deswegen existieren ja schon alternative Editoren.

Aber du hast ja auch nie nach dem Herausfinden selbst gefragt, sondern danach, den Algorithmus nur aus den Daten abzuleiten. Das ist schwer.

Im Übrigen willst du die Verschlüsselung ja nicht brechen, sondern den Algorithmus bestimmen. Brechen wäre, wenn du aus dem Code etwa den Benutzernamen herleiten wolltest. Du willst nur und ausschließlich Reverse Engineering betreiben.

[Karl]

Nicht eher, sondern ausschließlich. Das Brechen von Verschlüsselungen nennt man Kryptanalyse.

Okay vielleicht hat's n speziellen Namen aber irgendwo in die Richtung Kryptografie gehörts ja schon :p Auch wenn's "andersrum" ist.

Nicht Computer brechen Chiffren, Menschen brechen Chiffren. Ein Computer kann das Brechen eines Algorithmus nur automatisieren.

Man kann's auch übertreiben :p

Dein Algorithmus ist nicht per se schwer herauszufinden. Mit ein bisschen Reverse Engineering kommt man da mehr oder weniger leicht drauf, deswegen existieren ja schon alternative Editoren.

Aber du hast ja auch nie nach dem Herausfinden selbst gefragt, sondern danach, den Algorithmus nur aus den Daten abzuleiten. Das ist schwer.

Im Übrigen willst du die Verschlüsselung ja nicht brechen, sondern den Algorithmus bestimmen. Brechen wäre, wenn du aus dem Code etwa den Benutzernamen herleiten wolltest. Du willst nur und ausschließlich Reverse Engineering betreiben.

Kommt das nicht auf das Selbe hinaus?
Wie soll ich den Usernamen bestimmen können, wenn ich nicht den Algorithmus kenne? Bzw den "Umkehralgorithmus"?

[sma]

Jass genannt. Ich find sie total schrecklich :p

Was ist daran total schrecklich? Das ist doch eine total gewöhnliche prozedurale Programmiersprache. Sie ist vielleicht ein bisschen geschwätzig, aber man soll darin ja wohl auch keine längeren Programme schreiben, sondern doch wohl eher kurze Scripte, die zu bestimmten Ereignissen im Spiel ausgeführt werden, oder?

Stefan

[Karl]

Jass genannt. Ich find sie total schrecklich :p

Was ist daran total schrecklich? Das ist doch eine total gewöhnliche prozedurale Programmiersprache. Sie ist vielleicht ein bisschen geschwätzig, aber man soll darin ja wohl auch keine längeren Programme schreiben, sondern doch wohl eher kurze Scripte, die zu bestimmten Ereignissen im Spiel ausgeführt werden, oder?

Stefan

Nur leider sind die nicht immer so kurz und übersichtlich ... Es ist schon so, dass man auch komplexere Maps in Warcraft 3 programmieren kann.
Es gibt sogar 2D-Shooter usw. Ich hab mal ein Moorhuhn-Klon in Warcraft3 gespielt
Dass ich sie total schrecklich finde sollte eigentlich nur eine kleine Anmerkung sein, zum Beispiel den Algorithmus für die Verschlüsselung zu entnehmen, sollte trotzdem kein allzu großes Problem sein.

[gurke111]

Man sollte in diesem Thread darauf hinweisen, dass ein "versteckter Algorithmus" keineswegs bestandteil ernstzunehmender Kryptographie ist. Es gibt da den Begriff "public cryptography". Wie ein solches Verschlüsselungssystem funktioniert, darf und soll jeder wissen. Nur, wenn jeder weiß, wie ein solcher Algorithmus arbeitet, ist die Sicherheit überhaupt für jedermann einzuschätzen und nachweisbar. Ein solches System ist von sich aus und auch bei allgemeiner Kenntnis über die Funktionsweise ideal sicher. Da gibt es keine geheimen Parameter (außer einem Schlüssel natürlich).

Ein Beispiel dazu ist AES:

Der Algorithmus ist frei verfügbar und darf ohne Lizenzgebühren eingesetzt sowie in Software bzw. Hardware implementiert werden. AES ist in den USA für staatliche Dokumente mit höchster Geheimhaltungsstufe zugelassen.

[lunar]

Kerhoffs Law. Dieses Pirnzip ist übrigens mehr als hundert Jahre alt, und schon im ersten Weltkrieg gab es iirc keine Chiffren mehr, die auf der Geheimhaltung des Algorithmus beruhten. Heute ist das für id meisten verbreiteten Algorithmen erfüllt...

Deswegen habe ich ja auch versucht, Karl auszureden, dass das Ganze was mit Kryptologie zu tun hat. Es geht hier um das Reverse Engineering eines Programms und nicht um das Brechen einer Verschlüsselung.

[skypa]

Demnach warcraft3.exe einfach mal durch IDA Pro durch jagen und versuchen sich ein Bild davon zu machen was da alles passiert. Richtig?!

[keppla]

Demnach warcraft3.exe einfach mal durch IDA Pro durch jagen und versuchen sich ein Bild davon zu machen was da alles passiert. Richtig?!

falsch. Es ging hier um eine Karte von Warcraft. Diese Karte müsste man reverse engineeren.
Oder, wie vom OP vorgeschlagen, einfach mal ein paar codes angucken, und sehen, ob man das Prinzip erkennt. Nur, dass diese Arbeit kaum Automatisiert werden kann.