Entschlüsselungsalgorithmus

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Entschlüsselungsalgorithmus

Beitragvon Karl » Freitag 30. Mai 2008, 19:53

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.
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Re: Entschlüsselungsalgorithmus

Beitragvon keppla » Freitag 30. Mai 2008, 22:41

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
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Beitragvon ne0h » Freitag 30. Mai 2008, 22:46

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! :wink:


ne0h
Karl
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Re: Entschlüsselungsalgorithmus

Beitragvon Karl » Freitag 30. Mai 2008, 23:30

keppla hat geschrieben:
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 :D
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Re: Entschlüsselungsalgorithmus

Beitragvon keppla » Samstag 31. Mai 2008, 01:22

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
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Re: Entschlüsselungsalgorithmus

Beitragvon Karl » Samstag 31. Mai 2008, 14:09

keppla hat geschrieben: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.


keppla hat geschrieben: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 :D (nein eigentlich will ich ja nicht cheaten, ich hab nur zu viel Zeit)
lunar

Re: Entschlüsselungsalgorithmus

Beitragvon lunar » Samstag 31. Mai 2008, 14:33

Karl hat geschrieben: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
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Beitragvon Karl » Samstag 31. Mai 2008, 15:00

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 :o
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
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Samstag 31. Mai 2008, 15:19

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
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Beitragvon Karl » Samstag 31. Mai 2008, 15:28

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

Beitragvon lunar » Samstag 31. Mai 2008, 15:35

@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
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Beitragvon Karl » Samstag 31. Mai 2008, 15:55

lunar hat geschrieben:@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

Beitragvon lunar » Samstag 31. Mai 2008, 16:40

Karl hat geschrieben: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
User
Beiträge: 252
Registriert: Freitag 29. Juni 2007, 17:49

Beitragvon Karl » Samstag 31. Mai 2008, 17:49

lunar hat geschrieben: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.

lunar hat geschrieben:Nicht Computer brechen Chiffren, Menschen brechen Chiffren. Ein Computer kann das Brechen eines Algorithmus nur automatisieren.

Man kann's auch übertreiben :p


lunar hat geschrieben: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
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Sonntag 1. Juni 2008, 08:58

Karl hat geschrieben: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

Wer ist online?

Mitglieder in diesem Forum: __deets__, Google [Bot], schurmak, snafu