Saturday, October 13, 2018

What is ECC(Elliptic Curve Cryptography)?

If you want to see the real math behind secp256k1 and don't want your time to be wasted reading my unfinished article, check out https://www.coindesk.com/math-behind-bitcoin/ and https://www.cryptocompare.com/wallets/guides/how-do-digital-signatures-in-bitcoin-work/ for the math and as much explanation as possible.

The post title is a bit misleading as it is both a real question and a rhetorical one as well. I admit that when it comes to cryptography, I am very much in the dark.

Why though? Because cryptography requires a very solid understanding of algebra and I suppose geometry. The disambiguation of a 'curve' is literally the following on Wikipedia

curve is a geometrical object in mathematics.

And because both Algebra and Geometry fall within the broad subject of Mathematics, and because I said cryptography requires a very solid understanding of algebra, then you can infer I also mean Mathematics in general.
So you can also infer that if I am in the dark with cryptography, then I am actually pretty bad at maths.

How can someone who is bad at math, maintain a blog about reverse engineering? Well, programming in general does not always require the use of math operations more complex than a+b,a*b,a/b. On a fundamental level it's all maths, but the logic can be easy to follow.

Anyway, I set out to understand more about ECC, specifically the secp256k1 parameters which some of you might know are what power Bitcoin. Yes, it's Bitcoin that motivated me to write this post.
To be more specific it was Vanitygen, I've used the program before but the inner workings were...more mysterious and so I wanted to learn a bit more and boy is the rabbit hole deep.

Very often these 'curves' are represented as such a graph as shown below:


But then you are told that it actually looks like a scattered plot that seemingly looks random rather than the curve you see above.

In the Bitcoin wiki(not Wikipedia) has an article on secp256k1 with all the information taken from the SEC whitepaper located on http://www.secg.org/sec2-v2.pdf

And to save you some clicks, here is what it says:

The elliptic curve domain parameters over Fp associated with a Koblitz curve secp256k1 are specified by the sextuple T = (p, a, b, G, n, h) where the finite field Fp is defined by: 
  • p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
  • = 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1
The curve Ey2 = x3+ax+b over Fp is defined by:
  • a = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
  • b = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
The base point G in compressed form is:
  • G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
and in uncompressed form is:
  • G = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Finally the order n of G and the cofactor are:
  • n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
  • h = 01
Properties
  • secp256k1 has characteristic p, it is defined over the prime field ℤp. Some other curves in common use have characteristic 2, and are defined over a binary Galois field GF(2n)(fancy word to mean finite field), but secp256k1 is not one of them.
  • As the a constant is zero, the ax term in the curve equation is always zero, hence the curve equation becomes y2 = x3 + 7.

And finally, from OpenSSL's ec_curve.c file, we have this little structure here that defines the above data

 static const struct {  
   EC_CURVE_DATA h;  
   unsigned char data[0 + 32 * 6];  
 } _EC_SECG_PRIME_256K1 = {  
   {  
     NID_X9_62_prime_field, 0, 32, 1  
   },  
   {  
     /* no seed */  
     /* p */  
     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,  
     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,  
     0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x2F,  
     /* a */  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     /* b */  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  
     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x07,  
     /* x */  
     0x79, 0xBE, 0x66, 0x7E, 0xF9, 0xDC, 0xBB, 0xAC, 0x55, 0xA0, 0x62, 0x95,  
     0xCE, 0x87, 0x0B, 0x07, 0x02, 0x9B, 0xFC, 0xDB, 0x2D, 0xCE, 0x28, 0xD9,  
     0x59, 0xF2, 0x81, 0x5B, 0x16, 0xF8, 0x17, 0x98,  
     /* y */  
     0x48, 0x3a, 0xda, 0x77, 0x26, 0xa3, 0xc4, 0x65, 0x5d, 0xa4, 0xfb, 0xfc,  
     0x0e, 0x11, 0x08, 0xa8, 0xfd, 0x17, 0xb4, 0x48, 0xa6, 0x85, 0x54, 0x19,  
     0x9c, 0x47, 0xd0, 0x8f, 0xfb, 0x10, 0xd4, 0xb8,  
     /* order */  
     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,  
     0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC, 0xE6, 0xAF, 0x48, 0xA0, 0x3B,  
     0xBF, 0xD2, 0x5E, 0x8C, 0xD0, 0x36, 0x41, 0x41  
   }  
 };  

Although it isn't clear what 'NID_X9_62_prime_field, 0, 32, 1' is, those are field_type, seed_len, param_len and cofactor in ec_curve.c.
Right off the bat, we can identify that we have no seed, it even says so in the description, 

My very first question looking at everything was, what the hell is G ? What is a generator 'G'? Well, if you look closely it's actually the two x and y coordinates.

The order, is apparently the maximum number of valid private keys that could be generated using this curve.

Now, there is a very basic formula posted out there on the internet is 'public key = private key * base point(which would be G)'
Cool! But not really, apparently it's not that simple. Apparently the calculation involes x,y but also a and b and p, because 'a' is 0, it's essentially omitted. More on the calculation here https://www.coindesk.com/math-behind-bitcoin/

I'll update the post as we try(and likely fail often) to deconstruct everything related to ECC, so until then:

to be continued...


Saturday, September 23, 2017

Binary instrumentation and recompilation of game logic to improve performance.

Fancy title, I know.

I have been interested in recompilation of game logic for specific processors for a while now.

It's probably a no brainer that games are compiled with generic compiler settings for a generic x86 processor, rather than optimizing for a specific microarchitecture(for obvious reasons).
It's also a no brainer that Intel beats AMD in performance when it comes to microarches prior to Zen. This makes a lot of old processors "useless" for gaming as games become more complex and thus require more CPU processing.

But what if you could either reduce or optimize a certain CPU intensive part of the logic so that it executes faster.

I understand that most games today might be more graphically intensive and thus require more GPU horsepower, and thus overclocking the GPU may provide more performance gain, but this won't be the case forever I think.

Battlefield 1 for PC has horrible performance, even on my i5-4670k. It requires so much CPU cycles, that the GPU is actually starved of data. DICE should fix this, but they haven't.

Monday, December 19, 2016

Been away for a while.

Over the past couple of months some major changes have happened to my life. The biggest one was the sudden passing of my father. He died in a car crash, this affected me deeply. Obviously due to this, and a sudden disinterest in RE before that made me step away for some time.

In the meantime, Denuvo was cracked, so no point in pursuing that anymore. x64dbg has progressed marvelously with ever increasing features, bug fixes and usability improvements, so I believe it has officially surpassed Ollydbg, not to mention x64 support which is the de facto standard these days.

Tuesday, July 5, 2016

Useless post.


Going to dig in a bit. Presumably what I am looking at is the Origin DRM, so what I am looking at is not Denuvo. And yes, that is a (useless) screenshot of the first thing I see when I load up an Origin game in x64dbg. So it's nothing special.

Quite frankly, I am angry, the shitposting on reddit regarding Denuvo, the false promises, the contradicting information of what Denuvo does, how it works etc.
How about I post what I find in addition to screenshots(or videos?) that at least proves/disproves something or sheds some light on the functionality.

Saturday, April 16, 2016

Might take a look at Unravel.

Unlike the other games, this one seems interesting as I want to play it. It uses Denuvo. This shouldn't be interpreted as if I am going to crack it, that will likely be impossible as I have never studied Denuvo moreover x64dbg still lacks a tracer and the underlying TitanEngine engine is wonky(aka the tools aren't mature enough;no offense mrexodia).

Some progress on Crysis 3.

In light of the news that Crytek open sourced their entire engine,  I am able to study the Crysis 3 machine code and identify critical code and structures. 

One particular bugging problem was clipping/culling of characters in Singleplayer or Multiplayer at a really short distance,  in multiplayer this is unacceptable. There is no option enabled to fix this,  so obviously I had to dig in the code,  but it is C++ and it's also lots of math,  I mean this is 3D programming,  which I am both unfamiliar with.  So I opted to use Cheat Engine to find the variable responsible for this,  which led me to a piece of code that held a float type which upon change showed that in part affected the drawing at distance.  Unfortunately multiple subsystems used this value and it fucked up the game,  the code which I couldn't have identified without the CryEngine source code was the CCamera class constructor,  and the particular value might be related to the Z buffer or Frustum plane.  If I can find where they are calculated perhaps I can fix this drawing issue. 

I also managed to enable all CryEngine commands though not all are modifiable,  one in particular is the Nanovision blur command,  which might help people in the Multiplayer. 

Sunday, April 3, 2016

Great article on API hooking!

As I was browsing RE related blogs and articles I stumbled upon this gem.

Amazing article that gave me more insight on how to perform more stealthy hooking.

Monday, March 28, 2016

Analyzing the SecuROM 8.10.X VM Part 2

This will be a small post that I will update here-after once I discover more.

If you go back to the previous article, I mentioned the part where SecuROM walks all 100 possible VM contexts and finds the first free one. Well, the table starts at address 0x3BF7C2FC, since all the contexts are allocated from a single Heap(likely created by HeapCreate and later, memory is allocated using RtlAllocateHeap with said heap handle) they are contiguous, so I subtracted the address of one context with the previous in the table and came up with a size of 0x460(1120) bytes for each VM context, this includes the VM Context structure and the scratchpad, which is the area where the virtual registers are written, as well as code being written and executed.

Address 0x3BF7C2F8 is the spinlock value.

Now, when analyzing the first VM program, on the surface it felt like it wouldn't do much, but I actually saw that before it zeroes out the busy flag, it recursively(although I could be wrong) called the VM a dozen more times with different arguments, that much code will take very long to trace. In addition to this, it also writes and executes code off the scratchpad.

Now, let's analyze the first obfuscated VM handler from the previous post:
mov esi,dword ptr ds:[ebx+4]
add esi,dword ptr ds:[ebx+0C]
add esi,4
push dword ptr ds:[esi]
pop edi
mov dword ptr ds:[ebx+400],4
sub esi,dword ptr ds:[ebx+400]
push dword ptr ds:[esi]
pop esi
mov cl,byte ptr ds:[ebx+10]
push eax
xor eax,esi
xor eax,dword ptr ss:[esp]
add esp,4
shl eax,10
shr eax,18
xor al,2A
add byte ptr ds:[ebx+10],al
mov eax,3BF7C894
push edi
push eax
mov eax,esi
shl eax,18
shr eax,18
ror al,cl
xor al,78
shl eax,2
add eax,ebx
mov edi,eax
pop eax
push eax
pop dword ptr ds:[edi]
pop edi
push edi
pop eax
sub al,cl
xor eax,00B42D00
add dword ptr ds:[ebx+4],8 <-- Update VM EIP with 8 bytes.
jmp eax <-- Jump to computed handler.

mov esi,dword ptr ds:[ebx+4]
add esi,dword ptr ds:[ebx+0C]
add esi,4

This part fetches the current VM EIP(which is a delta from the VM entry point), adds the entry point to compute the pointer to the opcodes. "add esi, 4" increments the VM EIP by 4 bytes.

push dword ptr ds:[esi]
pop edi

Translates to exactly mov edi, dword ptr ds:[esi] which moves the new opcode into register EDI.

mov dword ptr ds:[ebx+400],4
sub esi,dword ptr ds:[ebx+400]

This here is both boring and interesting, it's boring because it decrements the VM EIP by 4 bytes, but it's interesting that instead of fetching the opcode first, then incrementing by 4 bytes to get the next one, it does it backwards. It's also interesting, because offset 0x400 in the VM context is referenced elsewhere lots of times. Anyway, to basically simplify this, it's the equivalent of "sub esi, 4".

push dword ptr ds:[esi]
pop esi

Translates to "mov esi, dword ptr ds:[esi]". Again, moving an opcode into register ESI.

mov cl,byte ptr ds:[ebx+10] moves the modifier from the VM context into 8-bit register CL.

push eax
xor eax, esi
xor eax,dword ptr ss:[esp]
add esp,4

While eax isn't referenced before, it contains the address of the start of the handler, in my case it was 0x38F78918.
The address of the handler is xor'ed with the opcode we extracted into ESI. 38F78918 ^ 687ADD02 = 508D541A. And because push eax, pushed 38F78918 to the stack, xor eax,dword ptr ss:[esp] translates to 508D541A ^ 38F78918 = 687ADD02.
To summarize this uses the xor method of swapping values, which can be translated as mov eax, esi.

shl eax,10
shr eax,18
xor al,2A
add byte ptr ds:[ebx+10],al

So one of the opcodes we previously moved into ESI, then into EAX is used as a modifier, by adding it to the previous one(which by default is always 0x95). The shifts there essentially chopping off bits to extract the 3rd byte of the opcode and adds it to the default value to equal 0x72(1 byte add).

mov eax,3BF7C894
push edi
push eax
mov eax,esi
shl eax,18
shr eax,18
ror al,cl
xor al,78
shl eax,2

The constant being moved to EAX will be discussed later on as it is saved on the stack for later use. We will focus on mov eax, esi which moves the value 687ADD02 which we figured out how it was produced earlier, into register EAX, the next two shifts essentially extract the 4th byte, which is 0x2 and right rotate it with the default modifier 0x95 stored into CL. Since 0x95 is larger than the 32 bits, the value should wrap around, in the end we get a value of 0x10, which I suppose can be translated as al << 3. The value is then xor'ed with 0x78 and produced 0x68 which is then left shifted by 0x2 to produce 0x1A0.

add eax,ebx
mov edi,eax
pop eax
push eax

So what happened before, all that junk above just to compute offset 0x1A0, then the value from EBX is added to 0x1A0, EBX contains the address of the VM context. Now remember the constant before, 0x3BF7C894, it's moved to EAX via the first pop eax, and then it's pushed again. So pop eax, push eax can be translated as mov eax, dword ptr ss:[esp].

pop dword ptr ds:[edi]

The constant is stored to where EDI points to via that pop. It points to offset 0x1A0 in the VM context.

pop edi
push edi
pop eax

So what happens here? Well, pop edi moves one of the opcodes into EDI, then pushes it onto the stack again and pops it right back into EAX. So we can translated this as either mov eax, dword ptr ss:[esp] or if we take into account the pop edi instruction, then mov eax, edi. The opcode was 3852A852.

sub al,cl
xor eax,00B42D00

So, the last byte of opcode 3852A852 is subtracted by CL(0x95) and produces value 3852A8BD. which is xor'ed by 00B42D00 and the final value in EAX is 38E685BD.

add dword ptr ds:[ebx+4],8 <-- Update VM EIP with 8 bytes.
jmp eax <-- Jump to computed handler.

Pretty self-explanatory. VM EIP is incremented by 8 bytes, and we jump to the address in EAX, which is the next handler.

So what this handler did in a nutshell, is not only store the constant 3BF7C894 into 0x1A0(this could be a virtual register), but also compute the address of the next handler. So we can probably simplify this handler to "mov reg, imm" or as "mov reg1A0, 3BF7C894".


UPDATE:

Let's look at the handler that we jump to, which is the second handler. First thing to notice is this is a 12 byte opcode, and not 8 as with the previous one.

mov esi, dword ptr [ebx + 4]
add esi, dword ptr [ebx + 0xc]

Standard VM EIP delta, with the VM address being added to it.

add esi, 4
mov edi, dword ptr [esi]

One opcode being loaded into EDI, note again how ESI was incremented by 4, so it's loading the second DWORD opcode. The value is 02C4EC00.

mov dword ptr [ebx + 0x400], 4
sub esi, dword ptr [ebx + 0x400]
push dword ptr [esi + 8]

As ESI is decremented by 4, then a value at offset 0x8  is pushed on the stack, which is the 3rd opcode. So it's stored for later use.

push esi
xor esi, dword ptr [esi]
xor esi, dword ptr [esp]
add esp, 4

Again, standard swap using the xor trick. So essentially, this is mov esi, dword ptr ds:[esi]. We just loaded the first opcode.

mov cl, byte ptr [ebx + 0x10]

The modifier in the VM context is loaded into CL.

push eax
xor eax, esi
xor eax, dword ptr [esp]
add esp, 4

This piece translates to exactly, mov eax, esi.

shl eax, 0x10
shr eax, 0x18
xor al, 0x40
add byte ptr [ebx + 0x10], al

The value in EAX is E518721C, (0xE518721C << 0x10) >> 0x18 = 0x72 ^ 0x40 = 0x32 - we are extracting the third byte, decrypting it with the xor and updating the modifier.

push eax
xor eax, edi
xor eax, dword ptr [esp]
add esp, 4

Don't even need to see this in action to know that it is doing mov eax, edi.

xor eax, 0x2c4ec60

So 02C4EC00 ^ 02C4EC60 = 0x60.

sub esp, 4
mov dword ptr [esp], eax

This can simply be interpreted as push eax.

push esi
pop eax

Seems like we are moving what was in ESI to EAX e.g mov eax, esi.

shl eax, 0
shr eax, 0x18
rol al, cl
xor al, 0x36
shl eax, 2

This piece is is decrypting the value using the modifier. The first left shift is redundant, the whole operation is as follows: E5 << CL(0x8C) | E5 >> 32 - CL(0x8C) = 0x5E ^ 0x36 = 0x68 << 2 = 0x1A0. Woohoo, so it's our virtual register where we stored our constant before.

push eax
add dword ptr [esp], ebx
pop eax

The value in EAX is now 0x1A0. It is pushed on the stack, EBX is added to it(it contains the VM context address) and is popped back into EAX.

push edi
xor edi, eax
xor edi, dword ptr [esp]
add esp, 4

Translates to mov edi, eax.

pop eax
push eax
neg eax
sub dword ptr [edi], eax

By this point, pop eax moves into eax the value 0x60 that was pushed earlier on. Pushes it on the stack again.. It negates it which is to say -0x60 or 0-0x60 = FFFFFFA0 and substracts it from the virtual register reg1A0 which holds the constant 3BF7C894 to equal 3BF7C8F4.

mov dword ptr [ebx + 0x400], 0x2152f
mov eax, dword ptr [ebx + 0x400]
pop eax

Completely redundant operation. You move the value from EBX+400 to eax, but then do pop eax, which moves the value 0x60 to EAX overwriting the previous value. Which is also irrelevant, because it's overwritten in the next sequence.

pop eax
rol al, cl
xor eax, 0x2c4ec60
add dword ptr [ebx + 4], 0xc
jmp eax

So the first instruction moves the value 3A2245FD which is also the third opcode, rotates the last byte 0xFD with CL(0x8C) to produce the value 3A2245DF and then it's xor'ed with 02C4EC60, so 3A2245DF  ^ 02C4EC60 = 38E6A9BF.
VM EIP is then incremented by 12!!! bytes and we jump to the next handler at address 38E6A9BF.

So this handler essentially does add reg1A0, 0x60, or "add vmreg, imm"?






Tuesday, March 22, 2016

Anti-dumping trick or coincidence?

In MSVC the way to name/rename a thread is to call RaiseException with special parameters. More information can be found on MSDN.

The exception value is specific, it's 0x406D1388. If you see this exception value, it likely means that an application is trying to set a name for it's thread.

This is the case in CryEngine, however in my dumped exe, the code was failing. The exception handler used was _except_handler3, which is some generic handler in MSVCRT? Which also uses a secondary, user-provided handler table.
_except_handler3 has an internal check with VirtualQuery and checks the page access of this handler table. Specifically, 'MEMORY_BASIC_INFORMATION's 'Protect' member. Since the (user supplied)handler table was in the .rdata section, the protection should have been PAGE_READONLY, but in my case, it was PAGE_WRITECOPY. It was not set as read-only, because when I rebuilt the imports, some of the pointers were in the .rdata section, thus the import reconstructor made it writeable, this causes _except_handler3's page protection check to fail, thus it never calls any of the handlers, and the thread renaming exception never gets handled leading to a crash early on.

But here's the problem, if I make the .rdata section just read-only, the PE loader fails early as it cannot write the imports to the OriginalFirstThunk addresses. So essentially, I need proper import rebuilding.

UPDATE: Upon consulting with other people who pretty much solved my problem, I learned that it is normal for the IAT to reside in .rdata or a read-only section, the loader shouldn't choke, so we're not quite sure what the exact cause was, but upon closer inspection, the IAT RVA and IAT Size were set to 0 in the PE header. Upon fixing this, all was well.

Thursday, March 17, 2016

For those of you that have time to spare.

As we have more or less shifted to x64, we find ourselves in need of new tools, in this case, free debuggers. I don't think we will ever see Olly64 come to fruit, the developer has not posted any updates in years, so with that in mind, I urge those that have the time and like to contribute to open source projects, to check out x64dbg, it has the potential to replace Olly, both 32 and 64-bit. Unfortunately, the devs need help, there's like only 2-3 active contributors, and lots of features are missing from the debugger to make it more useful.
It comes with the Snowman decompiler built-in, although I've found it to be less than accurate. There are also plans to have graphs, just like IDA, but so far nobody has come forth to contribute.

With your contributions, you will be indirectly helping in defeating future and current x64 protections(one being Denuvo/VMProtect). Of course, if you loathe piracy, then the other reason is malware research.

Addendum: You can also join the development channel on #x64dbg@irc.freenode.net.