Einleitung

Grüezi mitenand     Fondue Ist Gut Und Gibt Eine Gute Laune! Im dritten Teil meiner Miniserie geht es um ein weiteres grundlegendes Problem der Kryptographie: dem Discrete Logarithm Problem (DLP). Wir schauen uns dies anhand des ElGamal-Algorithmus an, welcher neben RSA auch ziemlich verbreitet ist. Dies kommt daher, dass RSA bis vor ein paar Jahren patentiert war und sich viele Leute die Lizenzgebühren sparen wollten. Kürzlich habe ich ein nettes Crackme gefunden, welches diesen Algo implementiert hat - das war auch gleich der Anstoss für mich, ein Tutorial zu schreiben. Es handelt sich um pDriLl's Crypto Crackme #3 (Achtung: Die Zip-Datei ist falsch angschrieben). Wie schon beim RSA-Tutorial setze ich voraus, dass sich der Leser selber mit der Theorie befasst. Für den Anfang reichen die folgenden Dokumente: ElGamal - Algorithmus und Beispiel, Der ElGamal-Algorithmus als Signaturverfahren, ElGamal und natürlich Bruce Schneier's Applied Cryptography. Ausserdem wird das in den beiden vorherigen Tutorials Gesagte als bekannt vorausgesetzt. Wer sich eingehend mit der Materie beschäftigen will, sollte sich das Handbook of Applied Cryptography angucken, von welchem auch eine Onlineversion erhältlich ist.

Erste Schritte

Nach dem Disassemblieren des Crackmes probieren wir gleich aus, ob IDA irgendeine MIRACL-Signatur erkennt. Siehe da, 19 Funktionen werden erkannt, unter anderem _mirkill und _power. Das ist doch schon mal ein Anfang! Wir suchen gleich mal die Stelle, wo _mirkill vorkommt und scrollen im Code ein gutes Stück nach oben. Dort treffen wir auf einen alten Bekannten: GetDlgItemTextA. Also starten wir das Programm und setzen einen BPX auf erwähnte API: 0040106A call ebx ; GetDlgItemTextA ; Name einlesen 0040106C mov esi, eax 0040106E cmp esi, 1 ; ln >= 1 ? 00401071 jge short loc_401092 ; ja: springe weiter . 0040109F call ebx ; GetDlgItemTextA ; Serial1 004010A1 cmp eax, 1 ; ls1 >= 1 ? 004010A4 jnb short loc_4010C5 ; ja: springe weiter . 004010D2 call ebx ; GetDlgItemTextA ; Serial2 004010D4 cmp eax, 1 ; ls2 >= 1 ? 004010D7 jnb short loc_4010F8 ; ja: springe weiter Es werden alle Angaben eingelesen, wobei die Längen mindestens Eins betragen müssen. Danach wird der Name mit Sternchen '*' aufgefüllt, bis er 30 Zeichen lang ist: 004010F8 cmp esi, 1Eh ; ln >= 1Eh ? 004010FB mov eax, esi 004010FD jge short loc_401124 004010FF mov edx, 1Eh ; nein: Name mit '*' auffüllen bis ln == 1Eh 00401104 lea edi, Name[esi] 0040110A sub edx, esi 0040110C mov eax, 2A2A2A2Ah 00401111 mov ecx, edx 00401113 mov ebx, ecx 00401115 shr ecx, 2 00401118 repe stosd Beim Runterladen des Crackmes von der FHCF-Seite haben wir gesehen, dass es sich um ElGamal handelt, ausserdem gibt uns pDriLl in der About-Box einen Hinweis auf das DLP. Somit haben wir es wiederum mit Bignmus zu tun. Dem geübten Auge fallen sogleich die acht identischen Calls auf - genau das gleiche hatten wir schon in den beiden vorherigen Crackmes angetroffen, dort wurden jeweils die Bignums initialisiert. Beim Tracen notieren wir alle acht Adressen der Bignums. Wir sehen, dass die Miracl-Zahlenbasis auf 60 eingestellt wird: 0040113F mov dword ptr [ebp+238h], 3Ch ; IOBASE = 60 00401149 call BigInit ; big1 0040114E push 0 00401150 mov [esp+2Ch+var_4], eax 00401154 call BigInit ; big2 00401159 push 0 0040115B mov [esp+30h+var_10], eax 0040115F call BigInit ; big3 00401164 push 0 00401166 mov esi, eax 00401168 call BigInit ; big4 0040116D push 0 0040116F mov ebx, eax 00401171 call BigInit ; big5 00401176 push 0 00401178 mov [esp+3Ch+var_14], eax 0040117C call BigInit ; big6 00401181 push 0 00401183 mov [esp+40h+arg_8], eax 00401187 call BigInit ; big7 0040118C push 0 0040118E mov ebp, eax 00401190 call BigInit ; big8 Es folgen zwei identische Schleifen, in denen die beiden Serials zeichenweise geprüft werden. Alle Zeichen müssen innerhalb '0..9, A..Z, a..z' sein, das erklärt auch die Miracl-Zahlenbasis 60. Gucken wir uns doch kurz an, wie die Bignums im Speicher dargestellt werden, denn in dieser Miraclversion hat das geändert. Neu finden wir an Position zwei (ich rede hier von Dwords) einen Zeiger auf die eigentlichen Bignumdaten: 008CEB80 02 00 00 00 8C EB 8C 00 00 00 00 00 3A 26 AE E3 35 41 00 00 \ / \ / \ Länge Zeiger Bignumdaten in Dwords auf Daten in Little Endian

Funktionen erkennen

Ein kommentiertes Listing ist sehr hilfreich, aber eben, zuerst muss der nackte Code dokumentiert werden! Da wir in diesem Falle wissen, dass es sich um ElGamal handelt, ist es ein bisschen einfacher. Aber generell muss jede Funktion einzeln erkannt werden. Dazu gibt es mehrere Möglichkeiten:       * Erfahrung       * Suchen der Funktion in der Miracl-Dokumentation anhand der Argumente       * Kleine Zahlen als Argumente übergeben und Ergebnis prüfen Beim Erkennen eines Algos wendet man meistens alle drei Verfahren an, wobei natürlich die Erfahrung am wichtigsten ist. Spielen wir doch das einmal anhand unseres Algos durch: 00401272 push offset byte_40D820 ; Zeiger auf Serial 1 00401277 push ebp ; Zeiger auf Bignum 00401278 call sub_404220 Wenn Strings im Spiel sind, kann es sich nur um deren Einlesen als Bignum oder umgekehrt um die Ausgabe einer Bignum in Stringform handeln. Da wir hier aber am Anfang unseres Algos stecken, wird es wohl das erstere sein. Es werden zwei Argumente übergeben, ein String und eine Bignum. Sehen wir doch einmal in der Miracldokumentation nach, was das sein könnte. Es hat nicht viele Funktionen, die mit Strings zu tun haben, eine davon ist cinstr: Function: int cinstr (x, s) Description: Inputs a flash number from a character string, using as number base the current value of the instance variable IOBASE. Parameters: A big/flash number x and a string s. Jetzt können wir gleich unsere Vermutung live im Debugger bestätigen, indem wir uns das Ergebnis dieser Funktion angucken. Das Problem besteht nun darin, dass es sich hier um Base 60 handelt. Die Serial wird also als Base 60 eingelesen, intern aber ganz normal als Hex-Bignum gespeichert. Deshalb müssen wir diese Serial vorher selber irgendwie umwandeln, damit wir dann vergleichen können. Dazu nehme ich meistens das RSA-Tool, da man dort bequem zwischen Base 10 - 16 - 60 und 64 umschalten kann. Ein Beispiel: Serial (Base 60) = "PakOunDU" --> "4135E3AE263A" (Base 16). Unsere Bignum müsste dann im Speicher folgendermassen aussehen: 02 00 00 00 xx..xx 3A 26 AE E3 35 41 00 00. Soweit so gut, die erste Funktion hätten wir bereits entziffert! Deshalb ändern wir gleich deren Name im Listing, ich hab hier StrToBig verwendet. Die nächste unbekannte Funktion ist dort, wo unser Name verwendet wird: 00401294 push ebx ; Zeiger auf Bignum 00401295 push offset String ; Zeiger auf Name 0040129A push ecx ; Länge Name 0040129B mov dword ptr [eax+238h], 10h 004012A5 call sub_4040B0 Wir gehen genau gleich vor wie oben. Zuerst suchen wir in der Miracldokumentation nach einer Funktion, wo alle Argumente passen. Wir stossen auf bytes_to_big: Function: void bytes_to_big (len, ptr, x) Description: Converts a binary octet string to a big number. Binary to big conversion. Parameters: A pointer to a byte array ptr of length len, and a big result x. Ok, probieren wir das gleich mal aus mit unserem Namen und gucken, was als Ergebnis rauskommt: 0094B040 08 00 00 00 4C B0 94 00 00 00 00 00 2A 2A 2A 2A ....L°”.....**** 0094B050 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A 2A **************** 0094B060 2A 2A 6C 67 65 67 75 67 69 66 00 00 00 00 00 00 **lgegugif...... Das kommt hin, unser Name wird eins-zu-eins übernommen. Schon wieder eine Funktion, die wir im Listing benennen können. Die nächste Funktion nimmt vier Bignums als Argumente: 004012F3 push eax ; Zeiger auf Bignum (Ergebnis) 004012F4 push esi ; Zeiger auf Bignum (Primzahl) 004012F5 push ebx ; Zeiger auf Bignum 2 004012F6 push ecx ; Zeiger auf Bignum 1 004012F7 call sub_403550 Bevor wir nun loslegen, sollte überlegt werden, womit wir es hier zu tun haben: ElGamal. Von der Theorie her wissen wir, dass dabei Primzahlen und die Funktion PowMod eine entscheidende Rolle spielen. Aus diesem Grund gucke ich bei Strings, die in Bignmus umgewandelt werden, stets, ob es sich um Primzahlen handelt. Denn Primzahlen fungieren meistens als Modulus in den Berechnungen. Und wirklich, hier wird der Funktion als drittes Argument eine Primzahl übergeben. In der Miracldokumentation finden wir nres_lucas, power, powltr und powmod, alle benötigen vier Argumente. Die erste kommt nicht in Frage, da wir nichts mit N-Residuen zu tun haben, die zweite hätte IDA erkannt, und eines der Argumente der dritten Funktion ist ein Integer. Bleibt also nur powmod übrig. Das passt auch haargenau, da das dritte Argument der Modulus ist - natürlich eine Primzahl bei ElGamal. Function: void powmod (x, y, z, w) big x, y, z, w; Description: Raise a big number to a big power modulus another big. ... Parameters: Four big numbers x, y, z and w. On exit w = x^y mod z. Wie schon vorher muss nun das Ganze im Debugger überprüft werden. Diesmal müssen wir jedoch Bignums ändern, wobei zu beachten ist, dass nicht nur die Bignumdaten sondern auch deren Länge angepasst werden! Ich nehme immer die gleichen Werte: 3^2 mod 5 = 4, weil dies alles unterschiedliche Zahlen sind und so nichts verwechselt werden kann. Das Ergebnis stimmt! Bleiben noch zwei Funktionen, aber inzwischen sollte das Vorgehen wohl klar sein, sodass ich ein wenig abkürze. Die nächste Funktion hat sechs Argumente, in der Dokumentation finden wir nur zwei Möglichkeiten: mad und powmod2. Schnell wird klar, dass es sich um die zweite Funktion handeln muss, denn sie berechnet nichts anderes als: y^a * a^b mod p, und genau damit wird eine ElGamal-Signatur verifiziert. Die letzte Funktion hat zwei Argumente, darunter das Ergebnis der vorherigen Berechnung. Mit ein wenig Phantasie erkennt man eine Vergleichsfunktion, zumal grad anschliessend ein test eax, eax steht. Wer es ein paarmal gemacht hat, findet sich meistens schnell zurecht. Natürlich haben wir es hier relativ einfach, denn inzwischen sind wir mit der Miracl-Bibliothek ziemlich gut vertraut. In echten Programmen kommen jedoch oft uns unbekannte Kryptobibliotheken mit ebensolchen Funktionen zum Einsatz. Die Erfahrung zeigt aber, dass - hat man einmal das Format der Bignums rausgefunden - das Erkennen der Funktionen keine grösseren Probleme mit sich bringt. Oft haben diese Bibliotheken einen fast identischen Funktionsschatz wie Miracl, aber da keine Dokumentation zur Verfügung steht, muss oft geraten und ausprobiert werden. Handelt es sich sogar um Elliptische Kurven, hört der Spass ziemlich bald auf, und man kommt meistens nicht um das Coden von Testprogrammen herum.

Algorithmus

Nachdem wir nun alle Funktionen entziffert haben, kann das Listing kommentiert, studiert und im Debugger abgearbeitet werden: 00401272 push offset Serial1 00401277 push ebp 00401278 call StrToBig ; Serial1 in Big (Base60) --> (bigS1) 0040127D mov edx, [esp+2Ch+arg_4] 00401281 push offset Serial2 00401286 push edx 00401287 call StrToBig ; Serial2 in Big (Base60) --> (bigS2) 0040128C mov eax, [esp+34h+var_C] 00401290 mov ecx, [esp+34h+var_8] 00401294 push ebx 00401295 push offset Name 0040129A push ecx 0040129B mov dword ptr [eax+238h], 10h ; IOBASE = 16 004012A5 call bytes_to_big ; Name in Big (Base16) --> (bigM) 004012AA push offset aAc2db4fec8c629 ; "AC2DB4FEC8C62992DB4F" 004012AF push esi 004012B0 call StrToBig ; Modulus1 --> (bigP1) 004012B5 push ebx 004012B6 push esi 004012B7 push 2 004012B9 push ebx 004012BA call _power ; bigM = bigM ^ 2 mod bigP1 004012BF push offset aB54f430648c6b2 ; "B54F430648C6B2A10FFB" 004012C4 push esi 004012C5 call StrToBig ; Modulus (Primzahl) --> (bigP) 004012CA mov edx, [esp+60h+var_10] 004012CE push offset a2e0c2db4fec8c6 ; "2E0C2DB4FEC8C6299A0C" 004012D3 push edx 004012D4 call StrToBig ; G --> (bigG) 004012D9 mov edi, [esp+68h+var_4] 004012DD add esp, 44h 004012E0 push offset a4e0f2acad51c4c ; "4E0F2ACAD51C4CCDFB51" 004012E5 push edi 004012E6 call StrToBig ; Y --> (bigY) 004012EB mov eax, [esp+2Ch+var_14] 004012EF mov ecx, [esp+2Ch+var_10] 004012F3 push eax 004012F4 push esi 004012F5 push ebx 004012F6 push ecx 004012F7 call PowMod ; bigG ^ bigM mod bigP --> (big5) 004012FC mov edx, [esp+3Ch+arg_8] 00401300 mov eax, [esp+3Ch+arg_4] 00401304 push edx 00401305 push esi 00401306 push eax 00401307 push ebp 00401308 push ebp 00401309 push edi 0040130A call PowMod2 ; bigY^bigS1 * bigS1^bigS2 mod bigP --> (big6) 0040130F mov ecx, [esp+54h+arg_8] 00401313 mov edx, [esp+54h+var_14] 00401317 push ecx 00401318 push edx 00401319 call BigCompare ; big5 == big6 ? 0040131E add esp, 38h 00401321 test eax, eax Die beiden Serials werden zu bigS1 und bigS2, danach wird der Name in Bignum umgewandelt und eine PowMod durchgeführt:       bigM = bigM ^ 2 mod AC2DB4FEC8C62992DB4F. Dann werden drei Konstanten in Bignum umgewandelt (wobei die erste eine Primzahl ist) und folgendes berechnet:       big5 = bigG ^ bigM mod bigP       big6 = bigY ^ bigS1 * bigS1 ^ bigS2 mod bigP Diese beiden Zahlen müssen gleich sein, damit die Erfolgsmeldung erscheint.

Das DLP lösen

Aus dem Listing erkennen wir die Verifikation einer ElGamal-Signatur:       g ^ M mod p = (y^a * a^b) mod p, wobei M vom Namen abhängt und a und b den beiden Serialhälften entspricht. Frischen wir doch in Kurzform unsere ElGamal-Kenntnisse auf: Primzahl und zwei Zufallszahlen:     Öffentlicher Schlüssel:     Privater Schlüssel:     Signatur:         Verifikation der Signatur:     p, g und x (g < p, x < p), y = g^x mod p y, g und p x a = g^k mod p, mit k relativ prim zu (p-1) M = (a*x + k*b) mod (p-1) g ^ M mod p = (y^a * a^b) mod p Wir haben die Verifikation der ElGamal-Signatur, müssen jedoch die Signatur (a, b) selber berechnen, denn diese entspricht unseren beiden Serials. Dies gelingt nur, indem auf irgendeine Weise x gewonnen werden kann aus der Gleichung y = g^x mod p. Dies ist das bereits erwähnte Diskrete Logarithmenproblem DLP. Um das zu lösen gibt es verschiedene Algorithmen: Pollard-Rho, Pohlig-Hellman, Index Calculus und andere mehr. Eine Pollard-Rho Implementation finden wir in Miracl, für unser 80-bit DLP (= Grösse von p) bringt sie aber keine gültigen Ergebnisse. Pollard-Rho ist gut, wenn die Primfaktoren von (p-1) klein sind, was hier leider nicht der Fall ist. Also müssen wir einen anderen Algo ausprobieren. Ein wenig "googlen" und schon stossen wir auf eine interessante Seite, die den Pohlig-Hellman Algorithmus per Java-Applet implementiert hat: Discrete Logarithm Calculator. Genau das brauchen wir! Zu beachten ist einzig, dass alle Werte dezimal eingegeben werden müssen. Wir erhalten folgendes (in Hex):           g = 2E0C2DB4FEC8C6299A0C           p = B54F430648C6B2A10FFB           y = 4E0F2ACAD51C4CCDFB51           x = 3F6536A02CD18F3B67D3 Somit können wir die Serials berechnen aus den beiden Signatur-Gleichungen. Damit es einfacher wird, setzen wir (das frei wählbare) k = 1, damit wird der erste Teil der Serial konstant und die Bedingung k muss relativ prim sein zu (p-1) ist auch erfüllt. Relativ prim bedeutet, dass die beiden Zahlen keine gemeinsamen Primfaktoren besitzen. Den ersten Teil der Serial erhalten wir folgendermassen (mit k = 1 und g < p):           a = g^k mod p = g^1 mod p = g Den zweiten Teil der Serial erhalten wir aus der zweiten Signaturgleichung, die wir nach b auflösen (mit k = 1):           M = (a*x + k*b) mod (p-1)     -->     b = (M - x*a) mod (p-1) Zu beachten ist, dass M immer grösser als das Produkt x*a bleibt, da sonst das Ergebnis der Gleichung negativ wird. Das heisst, im umgekehrten Fall muss p zu M addiert werden.

Keygen

Unser Keygen wird relativ einfach (das sage ich jedesmal!). Wir lesen den Namen ein und füllen ihn mit '*' auf bis seine Länge 30 beträgt. Nach der Umwandlung in Bignum wird er quadriert und dividiert. Dann berechnen wir a (= konstant) sowie b und zeigen beide in Base60 an. #include <miracl.h> #include "ms32.lib" void CalculateSerial (HWND hWnd) { // initialize miracl: 100 digits per big, base 16 miracl *mip = mirsys (100, 16); big bigA, bigB, bigG, bigX, bigHash, bigP; int i, iStrLen, iVarK; char szName[32] = "", szSerial[16] = ""; // get input and check length iStrLen = GetDlgItemText (hWnd, EDF_NAME, szName, 32); if (iStrLen == 0) { SetDlgItemText (hWnd, EDF_SERIAL1, NULL); SetDlgItemText (hWnd, EDF_SERIAL2, NULL); return; } // adjust namelength for (i = iStrLen; i < 30; i++) szName[i] = '*'; iStrLen = i; // initialize big numbers bigA = mirvar (0); bigB = mirvar (0); bigG = mirvar (0); bigP = mirvar (0); bigX = mirvar (0); bigHash = mirvar (0); // bigHash ^ 2 % AC2DB4FEC8C62992DB4Fh bytes_to_big (iStrLen, szName, bigHash); instr (bigP, "AC2DB4FEC8C62992DB4F"); power (bigHash, 2, bigP, bigHash); // const bignums g, p, x, y instr (bigG, "2E0C2DB4FEC8C6299A0C"); instr (bigP, "B54F430648C6B2A10FFB"); instr (bigX, "3F6536A02CD18F3B67D3"); // b = (hash - xa) % (p-1), hash += p if hash < xa multiply (bigX, bigG, bigX); decr (bigP, 1, bigP); divide (bigX, bigP, bigP); if (compare (bigHash, bigX) == -1) add (bigHash, bigP, bigHash); subtract (bigHash, bigX, bigB); divide (bigB, bigP, bigP); // show serial mip->IOBASE = 60; cotstr (bigG, szSerial); SetDlgItemTextA (hWnd, EDF_SERIAL1, szSerial); cotstr (bigB, szSerial); SetDlgItemTextA (hWnd, EDF_SERIAL2, szSerial); // miracl cleanup mirkill (bigA); mirkill (bigB); mirkill (bigG); mirkill (bigP); mirkill (bigX); mirkill (bigHash); mirexit (); return; }

Nachwort

Neben ElGamal beruhen noch andere Kryptosysteme auf dem Diskreten Logarithmenproblem, unter anderem auch DSA. Was die Sache ein bisschen komplizierter macht ist der Umstand, dass es kein so bequemes Tool gibt wie das RSA-Tool für RSA. Man muss schon sehr ausgiebig suchen gehen, um die entsprechenden Sourcecodes zu finden. 80-Bit DLP's sind noch gut lösbar, ab 100 Bit wirds mühsam, und ab 130 Bit kann man es schon ziemlich vergessen. Wer diesen Tut verstanden hat, kann jetzt problemlos das TMG Trial Crackme #3 lösen und sich auch an pDriLl's DSA-Keygenme wagen, obwohl dies doch um einiges schwieriger ist! Ich hab den Miracl Pollard-Rho-Code in ein GUI gesteckt, das Programm liegt der Zip-Datei bei. Es funktioniert meistens sehr gut, wenn alle Primfaktoren von (p-1) klein sind. Zu beachten ist, dass alle Werte in Grossbuchstaben und in Hex eingegeben werden. Das Ergebnis ist gültig, wenn der Check ganz unten dem originalen Y entspricht. Die Primfaktorzerlegung von (p-1) muss selber gemacht werden, ich nehm immer das RSA-Tool dazu. Ausserdem spielt die Reihenfolge der Primfaktoren eine Rolle! Ich bin grad dran, etwas gescheiteres zu coden, aber solche Projekte bleiben meistens schon im Anfangsstadium stecken... Den kompletten Sourcecode, das Crackme und das DLP-Tool findet ihr in der Zip-Datei. Sollte irgendwas noch unklar, nicht gut erklärt oder sogar falsch sein, bitte mailt mir. Für Fragen, Kritik, Morddrohungen, Heiratsanträge oder Lob stehe ich gerne zur Verfügung, auch Geldgeschenke oder Naturalien werden gerne angenommen! Ich freu mich auf jeden Fall schon aufs nächste Fondue... -={ figugegl }=- Grüsse an ^mac^, scarebyte, TNP, die Idler vom Board und alle die mich kennen!

Abspann

Leute, falls noch Fragen auftauchen, kommt auf unsere Homepage, in unser Forum oder in unseren IRC-Chan #newbiez in Efnet! Dank geht an alle, die bereits an unserem Projekt mitgearbeitet haben, alle Mitglieder und Freunde von TNP und an alle bewußten und unbewußten Lehrmeister "all around the world". Für spezielle Sachen, z.B. wenn Ihr ein Tutorial verfaßt habt und es gern veröffentlichen wollt, schickts an unsere E-Mail-Adresse tN-p@gmx.net.