[alg] Voor de 'echte' wiskundeknobbels onder ons !

[Wilde]

Ik ben heeeeel benieuwd of iemand mijn vraagstuk op kan lossen.. Voor de duidelijkheid ik kan het niet ! Ik ben zowiezo benieuwd of het kan maargoed

Je hebt de volgende (delphi) code:

Delphi:

Function TForm1.Geefrestwaarde(X1, X2 : Longword) : Byte;
Var res:byte;
Begin
 asm
  Xor     Edx, Edx
  Mov     eax, X1
  cdq
  mov     ecx, X2
  Idiv     EcX
  Mov      Res, DL
 end;
 GeefRestWaarde := Res;
End;

Function TForm1.Scramblekey2210(Key : String) : String;
VAR
    Charac : Word;
    Teller : Byte;
    EBP10 : Integer;
    EBP04 : Integer;
    Res   : String;
Begin
 EBP04 := 0; Res := '';
 For Teller := 1 to Length(Key) do
  Begin
   Charac := Ord(Key[Teller]);
   If Charac < $41 then Dec(Charac, $30) else Dec(Charac,$37);
   EBP10 := GeefRestWaarde(Charac+$24-EBP04, $24);
   EBP04 := GeefRestWaarde(charac + (Teller-1) + $24 + 2, $24);
   If Ebp10 >= $0A then Inc(EBP10,$37) else Inc(Ebp10,$30);
   Res:=Res + Chr(EBP10);
  End;
ScrambleKey2210 := Res;
End;

Je ziet, een string die je in key meegeeft, wordt omgetoverd met een algoritmetje en geeft deze terug.

Waar ik benieuwd naar ben is of deze procedure is om te keren! Dus wij hebben de uitkomst, en dit moet teruggerekent worden tot wat je normaal in de procedure stopt.

Het is voor een expirement, en ik zou heel het knap vinden als 't iemand lukt de procedure om te draaien !!

.mobreak: code tags toegevoegd, denk daar voortaan zelf aan!

[ Voor 12% gewijzigd door .oisyn op 15-10-2003 00:13 ]

[Voutloos]

Iets terugrekenen kan nooit zo ingewikkeld zijn. Ken geen Delphi dus het kost me nu gewoon te veel tijd. Ik heb wel eens zelf met Java een encryptiealgoritme gemaakt (langer dan dit en dat ook kunnenterugdraaien.)

Verder ruikt dit naar huiswerk. Tevens geef je niet aan waar je probleem zit. Waar ga je de mist in.

De hint, om dit op te lossen: Kijk of er punt 'halverwege' is. Dan de rest wegknippen en tot daaraan toe omdraaien. Soort mergesort op je algoritme zeg maar. Je maakt je probleem dan de helft kleiner.

Dit stuk is recht toe recht aan:

code:

Function TForm1.Geefrestwaarde(X1, X2 : Longword) : Byte;
Var res:byte;
Begin
asm
Xor Edx, Edx
Mov eax, X1
cdq
mov ecx, X2
Idiv EcX
Mov Res, DL
end;
GeefRestWaarde := Res;
End;

Dat moet toch makkelijk om te draaien zijn? Begin is eind en de andere kant op kopieren.

[ Voor 31% gewijzigd door Voutloos op 15-10-2003 00:06 ]

[madwizard]

Aan de 'restwaarde' functie te zien wordt er ergens een modulus van berekend. Meestal kun je dan niet meer van de output terug naar de orginele output omdat je informatie verliest: x % 10 = y, als je y hebt is x niet uniek terug te halen.. Wel kun je zeggen dat x = 10 * k + y (k heel getal). Dus een oplossing is wel te vinden, maar 'omkeren' is misschien een te groot woord.
Dit ziet er trouwens wel heel erg uit als reverse engineering, assembler code (delphi heeft toch wel een modulus operator toch?), ebp10/ebp4

[Wilde]

Well het is in ieder geval geen huiswerk hoor, ik ben al langere tijd werkzaam

Maargoed, om even een antwoord te geven op je vragen:
- De proc. Geefrestwaarde is inderdaad recht toe recht aan, maar hij deelt 2 getallen en geeft de restwaarde terug. Als je het omdraait zal je dus aan de hand van de restwaarde, en X2(want X2 is de factor waardoor je deelt en die is bekend) de X1 moeten uitzoeken.

-En om je andere vraag te beantwoorden: ik ga hier dus ook de mist in: hoe reken je dit terug om zegmaar

[Apollo_Futurae]

Het is laat en ik ben lui, dus ik heb geen zin om Delphi of Assembler te lezen .
Zou je je probleem ook in wiskundige vorm kunnen gieten? (Wat is gegeven, wat kun je gebruiken, wat moet er bepaald worden?)

[Voutloos]

Wilde schreef op 15 October 2003 @ 00:11:
Well het is in ieder geval geen huiswerk hoor, ik ben al langere tijd werkzaam

Maargoed, om even een antwoord te geven op je vragen:
- De proc. Geefrestwaarde is inderdaad recht toe recht aan, maar hij deelt 2 getallen en geeft de restwaarde terug. Als je het omdraait zal je dus aan de hand van de restwaarde, en X2(want X2 is de factor waardoor je deelt en die is bekend) de X1 moeten uitzoeken.

-En om je andere vraag te beantwoorden: ik ga hier dus ook de mist in: hoe reken je dit terug om zegmaar

Ok niet gezien dat er een modulo tussen staat. Alleen is het dan niet zo dat de input niet uitmaakt zolang het maar dezelfde modulo-output geeft?
_{Waarschijnlijk onzin, maar ben dus geen ster in delphi.}

edit:

En als je het toch al voor Apollo_Futurae doet, heb ik er ook wat aan

[ Voor 5% gewijzigd door Voutloos op 15-10-2003 00:28 ]

[madwizard]

Ik neem ook maar aan dat de input de karakters '0' t/m '9' en 'A' t/m 'Z' bevat, tenminste dat blijkt uit de code..
Hier een C++ versie (hopelijk klopt ie zo, tis laat ), ik heb geen delphi..

C++:

#include <iostream>
#include <string>

using namespace std;

string scramble(string src)
{
    unsigned char c;
    unsigned int  b4 = 0, b10;
    string        res;
    res.resize(src.size());

    for (unsigned int i=0;i<src.size();i++)
    {
        c = src[i];
        c -= (c < 0x41) ? 0x30 : 0x37;      //  c: '0'..'9' -> 0..9, 'A'..'Z' -> 10..35
        b10 = (c + 0x24 - b4) % 0x24;
        b4  = (c + i + 0x24 + 2) % 0x24;
        b10 += (b10 >= 0x0A) ? 0x37 : 0x30; //  c: 0..9 -> '0'..'9', 10..35 -> 'A'..'Z'
        res[i] = b10;
    }
    return res;
}

int main()
{
    string s = "test";
    cout << scramble(s) << endl;
    return 0;
}

Is volgens mij wel te doen om omgekeerde functie te maken, maar zoals ik al zei, het is volgens mij een one way functie, je krijgt nooit orginele strings terug.

[ Voor 12% gewijzigd door madwizard op 15-10-2003 00:39 ]

[Soultaker]

Ik vind die Delphi code wat lastig lezen, maar op basis van madwizard's code lijkt de functie me perfect omkeerbaar. Ik zal eens een poging wagen...

edit:
Aanvulling op de code van madwizard:

C++:

string descramble(string src)
{
    unsigned char c;
    unsigned int  b4 = 0, b10;
    string        res;
    res.resize(src.size());

    for (unsigned int i=0;i<src.size();i++)
    {
        c = src[i];
        c -= (c < 0x41) ? 0x30 : 0x37;
        b10 = (c + b4) % 0x24;
        b4  = (b10 + i + 0x24 + 2) % 0x24;
        b10 += (b10 >= 0x0A) ? 0x37 : 0x30;
        res[i] = b10;
    }
    return res;
}

Werkt uitstekend, zolang je alleen alfanumerieke karaters ('A'..'Z', '0'..'9') gebruikt. Beter descramblen is onmogelijk, omdat slechts 26 waarden van de 256 beschikbare waarden per character verwerkt worden.

Welke software wilde je hier mee hacken trouwens? Het lijkt me duidelijk dat de Delphi code afgeleid is uit een binary file (vanwege de identifiers en de assembly code).

[ Voor 84% gewijzigd door Soultaker op 15-10-2003 01:20 ]

[TD-er]

Soultaker schreef op 15 October 2003 @ 01:04:
[...]Welke software wilde je hier mee hacken trouwens? Het lijkt me duidelijk dat de Delphi code afgeleid is uit een binary file (vanwege de identifiers en de assembly code).

Dat leek mij ook al.
Als je kijkt naar de eerste assembler code die doet een Xor Edx, Edx
Mijn assembler kennis is al erg ver weggezakt, maar ik meen me te herinneren dat de waarde in Edx dan ge XOR-ed wordt met een standaard (A) register en weer in Edx wordt opgeslagen. Zal wel bedoeld zijn om de waarde wat kleiner te maken, zodat je een longword uiteindelijk in een byte kwijt kunt.... soort subnet-operatie
Ik zie nergens dat de A wordt geinitialiseerd.

edit:

Ik zit me net te bedenken dat Edx waarschijnlijk een byte van een word is en een xor van 2 gelijke waarden levert een 0 op. (Ik heb dan ook eigenlijk nog nooit x86 assembly gehad)

Maar goed, als het als doel heeft om een werkende key te genereren dan is dat dus zeker mogelijk, voor de rest, wat de rest ook al gezegd heeft
Maar goed, als je dit kunt opsporen in de applicatie kun je 'm ook zo aanpassen dat 'ie alles accepteerd.

[ Voor 10% gewijzigd door TD-er op 15-10-2003 01:32 ]

[_Squatt_]

TD-er schreef op 15 October 2003 @ 01:29:
Mijn assembler kennis is al erg ver weggezakt, maar ik meen me te herinneren dat de waarde in Edx dan ge XOR-ed wordt met een standaard (A) register en weer in Edx wordt opgeslagen.

Er staat mij bij dat 'xor edx, edx' gewoon een snellere manier is om edx op 0 te zetten (in plaats van 'mov edx, 0').

edit:
Dat had je inmiddels zelf bedacht

[ Voor 10% gewijzigd door _Squatt_ op 15-10-2003 01:35 ]

[Soultaker]

TD-er schreef op 15 October 2003 @ 01:29:
Ik zit me net te bedenken dat Edx waarschijnlijk een byte van een word is en een xor van 2 gelijke waarden levert een 0 op. (Ik heb dan ook eigenlijk nog nooit x86 assembly gehad)

Dat klopt, maar edx is gewoon een 32-bits waarde (net als eax, ebx, ecx). Er staat dus gewoon "mov $0, edx", maar dan anders.

[ Voor 3% gewijzigd door Soultaker op 15-10-2003 01:39 ]

[.oisyn]

De reden is overigens dat een "mov edx, 0" 5 bytes kost, terwijl een "xor edx, edx" slechts 1 byte is

[RickN]

Wel een beetje sneu dat TS het probleem in e.o.a lulverhaaltje giet, met een paar vleiende woorden, zodat het voor hem opgelost wordt, en dan ook nog denkt dat we stekenblind zijn en dat niet doorhebben

[madwizard]

Die xor edx, edx kan helemaal weg, aangezien daarna cdq wordt gebruikt die toch al edx helemaal overschrijft. En ecx is ook niet nodig..

GAS:

mov   eax, [X1]
cdq
idiv  [X2]
mov   [res], dl

Als het echt uit een programma komt zal optimalisatie wel uit hebben gestaan bij het compileren

[Verwijderd]

De reden is overigens dat een "mov edx, 0" 5 bytes kost, terwijl een "xor edx, edx" slechts 1 byte is

soms nog belangrijker : mov edx,0 kost niet alleen meer bytes, die 0 moet ook worden opgeslagen als 32 bits getal (kost nog eens 4) en geheugenoperaties zijn altijd langzamer dan registeroperaties. xor edx,edx is dus nog eens een stukje sneller ook...

[Soultaker]

offtopic:
Die 5 bytes waren al inclusief de immediate value (1 byte voor de opcode + register, 4 bytes voor de 0).

[Tomatoman]

Even terug naar de opmerking van RickN (zonder dat ik het als een feit overneem):

RickN schreef op 15 October 2003 @ 09:26:
Wel een beetje sneu dat TS het probleem in e.o.a lulverhaaltje giet, met een paar vleiende woorden, zodat het voor hem opgelost wordt, en dan ook nog denkt dat we stekenblind zijn en dat niet doorhebben

Voordat we hier een beetje gaan zitten helpen met illegaal reverse engineeren moet de topicstarter de volgende vragen maar eens beantwoorden:• Waar komt de gegeven code vandaan?• Waarom wil je de code 'omkeren'?• Is dit een legale activiteit?