02 Dec

Deobfuscating AutoIt scripts

Every once in a while, someone posts an interesting challenge concerning protected or obfuscated AutoIt scripts. Today I’d like to show some basic approaches to AutoIt deobfuscation. As a target I’ll use a very simple protection called AutoGuardIt and the crackme from Tuts4You thread. If you don’t have access to Tuts4You, here is the alternative download link: https://www.mediafire.com/?qs52emp7tkk472g

In general, there is nothing hard in decompiling AutoIt scripts. The Autoit script interpreter is designed in such a way that it’s really easy to convert P-Code back to the script form. There’s also a tidy.exe utility which takes ugly hand-written script and reformats it to make it really pretty. All of this makes writing deobfuscators much easier because you can start with well-formatted AutoIt script and your deobfuscator can consist of simple regexps and string replaces. It will not be very pretty code but it will work.

While I was preparing this blog post, SmilingWolf came up with a full-featured solution written in Python. It’s a nice solution but it doesn’t explain how or why it works. So, in this article I will explain how the protection works, show the basic techniques and sample source code to defeat each of the protection steps. Making a full-featured deobfuscator is left as an exercise for the reader.

Required tools

  • C# compiler. All my examples were tested under Visual Studio 2010 but any recent version should do
  • MyAutToExe. I’m using my personal modification of myAutToExe. You can download it from Bitbucket: https://bitbucket.org/kao/myauttoexe
  • Tool for testing regexps. I’m using http://regexr.com/
  • Some brains. You can’t become a reverser if you can’t think for yourself.

Decompiling the script

There are 2 public tools for extracting compiled AutoIt script: MyAutToExe and Exe2Aut.

Exe2Aut uses dynamic approach for obtaining script – it runs the file and gets decrypted and decompressed script from process memory. That’s usually the easiest way but you really don’t want to run the malware on your computer.

MyAutToExe uses static approach – it analyzes file and tries to locate, decrypt and decompress the script on its own. That’s more safe approach but it’s easier to defeat using different packers, modified script markers and so on. To extract script from this crackme, I used my own MyAutToExe (see “Required tools” section above).

Analyzing the obfuscation

Once the script is extracted and decompiled, it looks quite strange and unreadable:

Let’s look at each of the obfuscation techniques and see how it works and how it can be defeated.

Integer decomposition

AutoGuardIt takes constants and converts them to series of math operations. Example:

Deobfuscator should be able to take the expression, evaluate it and replace the expression with the correct value.

The biggest problem here is the precedence of operations (multiply and divide should be processed before addition and subtraction), so you can’t start from the beginning of line and do it one step at a time. This would be wrong:

After some thinking and few Google searches, I found a LoreSoft.MathExpressions library that does all the heavy lifting for me. :)

The following C# code snippet will find all math expressions, extract them, evaluate them and replace expression with the actual value:

Pseudo-random integers

This is quite strange protection that relies on a fact that AutoIt’s Random function is actually pseudo-random number generator. If you seed it with the same seed, you get the same results. Example:

In general, it’s a very bad idea because there’s no guarantee that random number generator will not change in the next version of AutoIt. But for now it works..

Since I was already using myAutToExe, I decided to use RanRot_MT.dll from the package.

a = StringLen(“xyz”)

Small integers can be obfuscated by using function StringLen:

To clean them up, a simple regex can be used:

End result:

Chr(x)

Some strings in the executable are split into bytes, and each byte is then encoded as call to Chr function:

Another simple regex will kill all of those:

The result will be valid but still hardly readable string:

And one more simple search-replace will fix that:

End result:

If 1 Then

Once you remove the integer obfuscations, you’ll see a lot of useless statements like this:

This condition is always true, so we can remove both If and EndIf lines and improve readability.

The problem here is that If‘s can be nested and you can’t just remove first EndIf that you encounter. Consider this example:

Taking all that into account, I came up with this ugly but working* code:

* – see below for some scenarios where this code might fail.

If a = a Then

Variation of previous protection. In such cases, using regexp is much more efficient than simple string comparison

Do Until 1

It’s pretty much the same protection as If 1 Then and it can be defeated the exact same way.

While 1 / ExitLoop / WEnd

Another protection of the same kind, just uses 3 lines of code instead of 2. Same approach, just make sure you match the correct lines and remove all 3 of them.

For $random=0 to 123.456 / ExitLoop / Next

Another protection, very similar to previous ones.

Here one must be very careful not to remove the real for cycles from program, so it’s better to use regexps. Apart from that, it’s pretty much the same code again.

Assign/Execute

This type of protection relies on AutoIt’s Assign function. First, an alias to a function is defined:

Later, alias is used to call the function:

Deobfuscation is a simple operation: find all calls to Assign, extract the variable name and the function name, then replace all references to the variable with the function name:

BinaryToString

As you can see in the example above, some strings in the script are replaced with calls to BinaryToString. Here’s a another example of the same protection where part of code is replaced with BinaryToString + call to Execute.

Merging all 3 lines into one and converting hex strings to bytes gives us the following code:

which using the methods described earlier can be deobfuscated as:

Functions returning constants

Some strings are not only encoded using BinaryToString but also moved to a separate function.

Deobfuscated code will look like this:

It’s quite tricky to find the correct return value for each function and replace function calls with correct values. In addition to that, regexes aren’t really suitable for such tasks. :) The code I wrote is really ugly, so I’m not going to show it. Go, figure it out yourself! :)

Switch control-flow obfuscation

This is actually the hardest one of them all. The example code looks like this:

You must find the initial value of the variable. Then you must find the correct start/end of the Switch, all the switch cases and all other assignments to the control variable. Then you’ll be able to reorder all the code. It’s a moderately hard problem for which I don’t have a pretty solution. :)

Here’s my code which seems to work:

After cleanup, the deobfuscated code looks like this:

Unused variable assignments

There are random variable assignments sprinkled all over the code.

They are only assigned once and never used. To clean them up, one can locate the assignments using regex, count how many times this variable appears in the code and remove it, if it’s only assigned once. Something like this:

You can remove string and integer assignments using very similar regex.

Lather, rinse, repeat

If you run each of the mentioned deobfuscations only once, you’ll end up with half-deobfuscated code. Also, there isn’t one specific order in which the deobfuscations should be applied. Of course, you could just run the entire loop 100 times, but it’s just ugly.

Therefore, I prefer to run the code in the loop like this:

It will run all the deobfuscations until there’s nothing left to clean up. Then run tidy.exe on the output and you’ll get a nicely readable script.. :)

Possible problems and gotchas

Deobfuscators based on string matching are very easy to implement. However, one must be very careful to write correct regular expressions and string comparisons. My example code works very well on this specific crackme. However, it will mess up with code like this:

You can work around such issues by using more specific regexes with anchors. During my research, I used http://regexr.com/ a lot, and I find it really helpful. Give it a try!

Conclusion

In this article I showed basic approaches that can be used to deobfuscate (not only) AutoIt scripts. They are extremely simple and work well for one-time tasks. For more complex tasks, deobfuscators based on abstract syntax trees or disassembled P-Code are much more efficient but more time-consuming to create.

Have fun!

15 Nov

Why morons shouldn’t be writing about security, part 2

I read Kotaku’s article called “FBI Says Alleged Hackers Used FIFA To Steal Millions From EA” this morning. And it reminded me of the crap articles Catalin Cimpanu writes at Softpedia.

What’s wrong with Kotaku’s article?

Well, pretty much everything.

First, this group did not steal from Electronic Arts. If fact, not a single penny of real currency was taken from EA.

According to an unsealed FBI indictment, Clark and his co-defendants allegedly built a tool that would send false signals to EA’s servers to spoof matches, generating these FIFA coins at a rapid rate. The FBI alleges that Clark and crew then sold the coins to third-party sellers, earning millions.

Exactly! Guys received FIFA coins from EA (it’s an in-game currency) which they later sold on underground sites. Money came from persons entirely unrelated to Electronic Arts and it was given voluntarily. And that, by definition, is not a theft.

The article continues with a plenty of other funny statements like

.. worked with the defendants to get Xbox development kits and reverse-engineer a pirated copy of FIFA 14 using a program called Interactive Disassembler. This process took several months, Alcala said, but it allowed them to create a tool for mining FIFA coins.

I just love the IDA reference in here. :D These guys used disassembler, they must be real evil hackers! All in all, this article is a fun read but it got all the basic facts wrong.

Mr. Jason Schreier, please stop writing about things you have no clue about. Stick to your video game reviews or something.

What is really happening?

Thankfully, UK journalists have much better idea of what’s happening in US courts, and they wrote a much better article. According to the indictment, the charges are “conspiracy to commit wire fraud“, a stupid catch-all term used in US courts for pretty much everything done over the Internet.

That document is equally funny read and shows how desperate the prosecutors must be to make any charges stick. Let’s see:

  • the defendant assisted in creating a program (…) which sent electronic messages to EA’s servers fraudulently representing that thousands of FUT matches had been completed in the EA’s FIFA video game. EA’s servers materially relied on the completed match messages and credited various accounts maintained by the defendant and his co-conspirators with FIFA coins. – this is the only part of the indictment that actually makes sense. Kinda. There’s one teeny tiny detail – RANE Developments got virtual goods from EA. And the legal status of virtual goods is very unclear in the United States. If virtual goods are not “money or property” in the eyes of law, then there was no fraud.
  • the defendant and co-conspirators continued to create and execute new methods to circumvent the security measures by EA in EA’s effort to prevent fraudulent activity associated with the company’s FIFA video game. – that might be a breach of EULA but not a crime;
  • executed their “application” through a video game console, which they modified to circumvent security and copyright protections, and on game development kits, which they obtained from unlicensed sources. – we’re getting desperate, let’s charge them with modding their consoles!
  • executed their “application” through cloud computer servers, which allowed them to run more copies of the software and obtain significantly more FIFA coins. – if nothing else helps, let’s charge them with renting cloud computer servers! Oh, wait, what? :)

Naturally, the defendant has pled not guilty to the charge. And if his lawyer is any good, I’m guessing he’ll walk out of the court as a free man.

07 Nov

About FLARE 2016 contest

This year’s FLARE reverse engineering contest is over. I managed to finish it on time – but I really had to force myself to keep going several times. This graph tells it all:
flare2016-progress

You can get all the challenges from the official site (password: flare) and there are already a number of writeups all over the web.

I’m not going to reinvent the wheel, so here’s just my take on few of the challenges. :)

#1 – Challenge1

Time spent: 9 mins. Not much to say, it’s designed to be a warmup.. Custom Base64, that’s it.

#2 – DudeLocker

Time spent: 1h 20mins. The buzzword for year 2016 is “ransomware”. Every self-respecting reversing challenge has to have one. It was fun and kinda easy for me – but in my opinion it was too hard for level 2.

#3 – unknown

Time spent: 7h 45mins. Since challenge starts at 3AM in Europe, one needs to get some sleep..

As for the task – reverser has to figure out the correct filename from PDB entry and then the challenge becomes solvable. No, it doesn’t have anything to do with actual reversing, just a random crap obstacle thrown into your way.

#4 – flareon2016challenge

Time spent: 1h 20mins. “Play me a song, have me play along..” Given a DLL, one must figure out the correct order in which to call exported functions to play a song. Original idea, kinda refreshing.. :)

#5 – smokestack

Time spent: 1h 45mins. And, of course, every challenge has to have custom Virtual Machine. This one was just the right difficulty and offering several ways to break it. Nice.

#6 – khaki

Time spent: 2h 20mins. Obfuscated python bytecode. Considering that it was my first time directly patching python bytecode, I enjoyed it a lot. In my opinion, one of the most interesting of challenges this year.

Fun fact – opcode for nop in Python is 0x09.

#7 – hashes

Time spent: 5days 2h 22mins. This is where I got really annoyed and stopped playing.

Not only they throw in a Linux challenge into the mix, they use Go programming language and compile binary in a way that requires libgo.so.7 – which is not available on certain Linux distributions (like Debian).

So, one has to figure out which bloody Linux distribution has support for it, install that in a Virtual Machine, then find a way to install Go language, then fight with SELinux – and all that just to be able to debug the binary provided by challenge. That’s just frigging stupid. How hard it is to tell the OS requirements before the challenge starts? >:(

Once I got over my enrage and disgust, it was actually pretty easy. My “solution” generated ~60GB of data files – just because I let my hash generation code run while still analyzing the challenge code.. ;)

#8 – CHIMERA

Time spent: 2h 10mins. The actual check was hidden in the DOS stub. There were some nice hints and neat and clean code, I loved everything about this challenge! :)

The fact that I got to boot up my Windows XP virtual machine and use debug.exe – that was just an icing on the cake.

#9 – GUI

Time spent: 1h 35mins. Mandatory .NET assembly thrown in the mix. Apparently FLARE team was running out of ideas, so they just used ConfuserEx. Three times.

To solve it, all you need to know is that DNSpy exists. I have no idea why this challenge was put as #9, difficulty wise it was more appropriate as #3..#5.

#10 – flava

Time spent: 35.5 days. Difficulty: 9, fun factor: 0.

This was just frigging stupid. I know, it’s a final challenge. But it required so much of a very specialized knowledge, that it’s insane.

First you need to get through 3 layers of JavaScript obfuscation. Hard but doable. Then you’ll arrive at some serious crypto. Normal person can’t know this is bugged Diffie-Hellman key exchange which was used by Angler exploit kit and got broken by Kaspersky Labs. So, if you’re not a crypto wizard or you don’t focus on exploit kit research, you’re screwed.

Once you figure out this crap, you still have to get through 3 layers of Flash. First SWF is easy but second one is obfuscated and solving involves a lot of guesswork. You’re supposed to guess that RC4 key is reused and decrypting other binary data with the same key stream will get you the required values to get to 3rd layer. How you’re supposed to figure that one out? Well, just “do some random stuff and hope it works™”.

The final layer has slightly obfuscated ActionScript code but nothing JPEXS can’t handle. It is there just to generate the answer.

Conclusion

If I compare this year’s FLARE with LabyREnth, LabyREnth wins hands down. In my opinion LabyREnth’s Windows track was much more fun and tasks were much more reverse engineering related. But that’s just my opinion..

I wish to express my deepest gratitude to fellow reversers who kept me going when I got really angry and upset: Extreme Coders, fasya and Levis. Your hints were invaluable, thank you so much!

27 Sep

Why I’m not using x64dbg

x64dbg is (probably) the most user-friendly x64 debugger right now. It’s pretty, it’s open-source and it usually works. But I find it very hard to switch from WinDbg to x64dbg for several reasons. Some of them are purely emotional (don’t worry, I’m not going to bore you to death explaining those) but most of them are technical and related to the way x64dbg is being developed.

So, here goes slightly exaggerated but still serious list of my grievances. :)

Insane system requirements

Both DNSpy and x64dbg suffer from this disease. They love to use the “latest and greatest” of technologies, meaning Visual Studio 2017, .NET 4.6 and what not. That’s perfectly fine when you’re writing normal software. But debugger is not a normal software.

If I have a customer with a software crashing on his production servers, I can’t tell him “You need to install Windows 7 SP2 and 3 different VS redistributables and reboot your machine twice just for me to run my debugger”. No, I really can’t.

Debugger must run on any and all systems out-of-the box. Olly does that. WinDbg does that. And it wouldn’t be hard to link x64bdg with static VS runtime libs and target WinXP while using all the modern goodies. But for some reason it’s not done that way.

Updated 30-Sep-2016: Mr. eXoDia let me know that now x64dbg is distributed together with the necessary runtime DLLs. We can remove this grievance off of my list. Hooray! :)

Uncertain direction and feature bloat

Antoine de Saint Exupery said:

Perfection is finally attained not when there is no longer anything to add, but when there is no longer anything to take away

These are really wise words and Olly is designed that way. It does all the basic stuff and has stable SDK that enables plugin authors to implement all the extras.

On the contrary, Mr. eXoDia is adding features left and right and the direction of x64dbg development looks more like this:
BrownianMovement

For example, why does a debugger need 3 (yes, three!) different assembler engines?
assemble

Want another example? Let’s just look at the latest weekly digest.. How about this:

… change to the info box. Basically the pointer values in the instruction were not resolved (so if the instruction contained qword ptr ds:[rsp+30] it would not show the value of rsp+30). Personally this is quite useless

Yes, Mr. eXoDia, you’re right. It is useless for everyone but few people.

And how about:

The commands plugload and plugunload have been added. This is useful for plugin developers who want to test plugins without having to restart x64dbg all the time.

How many people in the entire world will actually benefit from that? 5? 10?

So, why add such bloat? Once you add something, that something must be maintained. And it’s very hard to remove stuff later, as it might break something else. So, please don’t..

Broken features

When I am on a job and need to debug something, last thing I want to spend my time on, is fighting with debugger bugs. And my customers certainly don’t want to pay me for doing that.

Oleh Yuschuk got it exactly right with the OllyDbg. There were few releases – but they were properly tested and rock solid. From what I can see, x64dbg is going the other way:
compiles_ship_it

Frequent commits like “Fixed search for constant references”, “Fixed intermodular calls in module”, “Fixed FS/GS memory branch destinations” is not something you want to see in any software, let alone a debugger.

Well, it wouldn’t matter much, if there was some known-stable version I could put in my tool collection and use it anytime anywhere. But no, Mr. eXoDia thinks that “No more excuses to not update every day!” is a way to go. Instead of using tried-and-tested version, I should use a probably buggy and unstable one? Dafuq?

Conclusion

So, those are my 3 biggest complaints about x64dbg. I’d love to love x64dbg. I’d love to use x64dbg for everything. But right now I just can’t.

How about you?

21 Sep

IDA bug in PE export processing

Hi, I’m back from vacation. And now I’m catching up on all the things that have happened during that time. So, here’s a short writeup regarding publicly-known IDA bug and how it will (not) affect reversers.

It was supposed to be a long post showing how to use PatchDiff to locate patched code and then backport it. But, as you’ll see later, that’s not necessary at all. Maybe another time..

Initial research by Palo Alto

When checking my RSS feed, I stumbled upon the article by Palo Alto researchers called “The Dukes R&D Finds a New Anti-Analysis Technique“. It stated:

Using the exported functions by ordinal meant the exported function name was unnecessary, which allowed the developer of this DLL to leave the names for the exported functions blank … The less obvious reason is that it takes advantage of a bug in the popular IDA disassembler that was recently fixed in the latest version of IDA.

Bug in IDA?! How nice, I want to test this!

Testing the bug

Palo Alto report contained most of the information to reproduce the issue. But IDA 6.95 changelog was even more detailed about what was fixed:

BUGFIX: PE: IDA would not detect DLL exports with empty names
BUGFIX: PE: IDA would show no exports if the export directory’s DLL name was an empty string

Armed with the detailed description, I used MASM32 package and their Examples to build a DLL file.

Empty DLL name

First, I took hex editor and changed DLL name in export directory.
export_dll_name_1
export_dll_name_2
Now the exported DLL name is 0-length string. Let’s see what IDA does..

I started with IDA 6.95 Demo you can download from official site. No surprises here, the bug is fixed:
export_dll_name_IDA695

Then I took legit copy of IDA 6.90. As already demonstrated by Palo Alto, it’s buggy:
export_dll_name_IDA690

Naturally, I wanted to see how old this bug is. So, I took a copy of IDA 6.80. Surprise, surprise, it’s not buggy!
export_dll_name_IDA680
So, it looks like this bug was introduced in IDA 6.90.

Empty export name

For completeness sake, I repeated the experiment with empty exported API name.
export_api_name_1
export_api_name_2
The results were identical, the bug is only present in IDA 6.90.

How it affects you?

If you’re using IDA Free, latest version is 6.95. You’re good.
If you’re using legit IDA, you have received the updated version 6.95. You’re good.
If you’re using the latest publicly leaked version of IDA (6.80), it didn’t have the bug. So, you’re good, too.

To sum it up – it’s a fun bit of information but no one is really affected. Good news, I guess. :)

Example DLL files if you want to verify your tools: https://www.mediafire.com/?c9t6hm4icd3kk46

17 Aug

Gone for summer vacation

Last few months were quite busy for me.

On the good side: I solved 2 tracks of Labyrenth CTF – Windows and Documents. Unfortunately they still haven’t published the Honor Roll, so I have no clue if I placed 1st, 2nd or 44th..

On the bad side: there are lots of changes happening in my office. I don’t mind changes per se but the uncertainty of the future of the company.. Well, that’s not great.

So, I’m leaving for summer vacation. I’ll spend almost 4 weeks on islands with very spotty mobile coverage and almost certainly without Internet access. Will be back in mid-September, relaxed and ready to do some serious reversing again.

Have fun and talk to you all later!

01 Aug

Breaking B0rken ElGamal KeygenMe, part 2

In part 1 of the tutorial, I explained how badly initialized PRNG causes a serious problems and allows us to find the private key. In this part of tutorial, I’ll show how to use another weakness in crackme to find private key without using bruteforce.

Looking deeper in the keygenme

If you analyze serial check in more details, you’ll notice part of code that processes blacklisted names and keys:

It looks like we have 2 blacklisted names & corresponding serials. We can quickly patch crackme and verify that these names and serials really work.

But did you also notice that those serials look a lot alike? That’s weird.. Let’s take a closer look at them:

First part of the serial is exactly the same! Let’s go back to ElGamal basics and think a bit.

Revisiting ElGamal signing algorithm

I’m sure you already remember the algorithm from my previous blog post. But here it is again.. :)

To sign a message M, one would:

  • Make a hash of message, H(M). In this crackme, it’s SHA1 of the username
  • Generate a random number K where K<P-1
  • Calculate R=G^K (mod P)
  • Calculate S=(H(M)-RX)*K^(-1) (mod P-1)
  • The signature will be the pair C(R,S).

So, in our case, R is always the same. G and P are hardcoded in the crackme. That means.. K is always the same. And that doesn’t sound right! :)

Quick look in Wikipedia confirms that it’s a really bad idea:

The signer must be careful to choose a different k uniformly at random for each signature and to be certain that k, or even partial information about k, is not leaked. Otherwise, an attacker may be able to deduce the secret key x with reduced difficulty, perhaps enough to allow a practical attack. In particular, if two messages are sent using the same value of k and the same key, then an attacker can compute x directly.[1]

The problem of reusing k and the attack itself is explained in Stinson’s “Cryptography Theory And Practice”, pages 290-291. Unfortunately, normal person has no chance to understand that “explanation”.

Few Google searches later I found 2 writeups from Boston Key Party CTF 2015 which were slightly better:

So, let’s try to get something useful out of them.

Reused K and recovering private key

As I said earlier, cryptography is a dark magic – if you don’t spend years studying it, you can’t understand it. So, I just took the code from those CTF writeups and added few more comments to it. And no, I still don’t know why it works. :)

Conclusion

Wise man once said:

Knowledge is of two kinds. We know a subject ourselves, or we know where we can find information upon it.

You don’t need to be a crypto wizard to solve crackmes – you just need to know where to find the necessary information. But if you’re implementing cryptography in your software, better ask someone who understands those things.

Have fun!

22 Jul

Breaking B0rken ElGamal KeygenMe by SmilingWolf

Some weeks ago I found a nice keygenme on URET forum. The description looked interesting enough:

Yet another company is making wild claims! Your mission: prove that people shouldn’t trust companies promoting “revolutionary” crypto algos. Keygen this son of a crypto nightmare and write a DETAILED tutorial!

Rules:
1) The only acceptable solution is a keygen
2) No patching of course

It was not solved for few weeks, so I decided to take a look at it. :)

Crash-course in ElGamal signature scheme

I hate cryptography. It’s complex, it’s confusing and unless you’re prepared to study this field for years, you can’t really understand why stuff works this or that way.

So, here’s a short version, just enough to solve this keygenme. It’s based on the explanation in InfoSec Institute’s tutorial.

Key generation

  • Generate a random prime number P with chosen length.
  • Generate two random numbers, G and X, with G<P and X<P.
  • Calculate Y=G^X mod P.
  • Public key consists of 3 numbers: (P, G and Y), Private key is X.

All 3 numbers of public key are hardcoded in keygenme and are 256 bits long. We can find them in disassembly:

Private key X is.. well, private. :) Without it we can’t generate correct keys for a name of our choice. So, the challenge would be to recover the private key somehow.

Signing

To sign a message M, one would:

  • Make a hash of message, H(M). In this crackme, it’s SHA1 of the username
  • Generate a random number K where K<P-1
  • Calculate R=G^K (mod P)
  • Calculate S=(H(M)-RX)*K^(-1) (mod P-1)
  • The signature will be the pair C(R,S).

Verification

To verify a given pair C(R,S), one would:

  • Compute V1=G^M (mod P)
  • Compute V2=Y^R * R^S (mod P)
  • If V1==V2, the signature is valid

Breaking ElGamal

Strength of ElGamal algorithm lies in the Discrete Logarithm Problem (DLP). What it means is that easy to calculate Y=G^X mod P, but it’s bloody hard to find out X, if you know P, G and Y.

In the InfoSec Institute’s tutorial the author is using figugegl’s DLPTool to solve the problem for 128-bit integers. However, it’s not even possible to enter 256-bit integers in that tool. And the rest of the suggested tools can’t handle such large integers either.

So, we must find another way to break the keygenme. After all, it’s called “B0rken ElGamal”, so there must be a weakness somewhere!

Inside the keygenme

The keygenme itself is an application that generates ElGamal keys. It would be logical to assume that SmilingWolf used this same application to generate keys for the keygenme. So, let’s examine the application and see how ElGamal is implemented in it.

I’ll skip the boring “unpack modified UPX part”, as it’s been explained dozens of times already.

So, here’s the relevant code for key generation:

Looks legit, right? :) Well, not so fast.

Random numbers don’t just magically appear out of thin air. They are generated using random number generators. If the generators are flawed, the numbers are not really random. You can read a lot about such attacks on Wikipedia.

So, let’s examine random number generator used in this keygenme.

If you search for those constants, you’ll see that it’s a very standard PRNG which is not great but supposed to be reliable enough. You could bruteforce all 2^32 possibilities but it will take a long time. Another dead end?

Well, not really. Any PRNG must be initialized somehow, see random_seed variable above. So, let’s see how SmilingWolf is initializing his PRNG..

Hmm, that’s weird. Normally PRNG is initialized using rdtsc instruction or something even less predictable than that. And what exactly is arg_0? It’s a handle of the DialogBox – not random at all!

Finally, we’ve found a reason why this ElGamal implementation is broken! :)

Bruteforcing the private key

Now that we know the weakness, we can write a bruteforcer that will go through all possibilities of random seeds and generate all possible ElGamal keys. Once we generate a key that has the same P, G and Y as in the keygenme, we will also know the correct private key X. But generating all these numbers is a slow process!

Let’s look back at the code and see what we can optimize.

1) We don’t need to generate all the numbers. It’s enough if we find correct P – the rest of numbers will match automatically. So, let’s remove the rest of the code.

2) First 32 bits of 256 bit integer will almost certainly not change when searching for nearest prime. Therefore, we could get rid of bigint_find_nearest_prime call which is the slowest piece of code. This means we won’t be looking for number FE6D5B4400B30374A403F88CFBA3642435FB269AEC2BE5C8C2F331545EF37AB3, but any number starting with FE6D5B44…

3) Multiplication by 2. Another unnecessary step. Let’s just divide P by 2 and look for that number. Instead of looking for FE6D5B44…, we’ll look for 7F36ADA2…

4) Copying bigints. Unnecessary.

There’s not much left, I’m satisfied.

Now, how to bruteforce random seed? It’s a window handle. Window handles are always even. Also, they consist of 2 parts, high word and low word. Low word is the actual handle. It is almost never higher than 0x2000. High word is the “uniquifier” – just a counter. It’s usually quite small – on my PC it’s never larger than 0x800.

Taking all these assumptions into account, my pseudo-code for bruteforcer would look like this:

I implemented the bruteforcer in MASM32 with 95% of code ripped from keygenme and let it run. In less than 2 hours I had one (of the several possible) seed:

Once we know X, implementing keygen is a child’s play. Again, lots of ripped code and small UI around it. Problem solved!

Keygen for download: https://mega.nz/#!JtgVUDwb!xs3SgCDK3t5h3MabOfoNsDFYCj1mpHcI7GbQT-K1_RE

Further reading

InfoSec Institute’s tutorial about ElGamal: http://resources.infosecinstitute.com/breaking-software-protection-elgamal-signature-scheme/
Interactive webpage showing how ElGamal works with small numbers: https://asecuritysite.com/encryption/elgamal

Final thoughts

As SmilingWolf told me after solving his keygenme – there is another way how to break this keygenme. There’s one more thing broken in this implementation that makes generating keys really easy. :) So, if you’re interested, try to figure out what is it and how to abuse it.

28 Jun

Bugs in Enigma Virtual Box

While working on a new version of my static EnigmaVB unpacker, I tried to generate test files to cover most of the Enigma Virtual Box features. In the process, I ran into quite a few bugs in Enigma Virtual Box v7.40.

So, here’s a short list:

Registry virtualization

1. Importing REG file with wrapped lines:

Data get truncated at the end of first line.

2. Importing REG file with entry type REG_NONE:

It gets virtualized as a string value “hex(0):”

File virtualization

1. If size of any embedded file > 4GB: creates invalid x86 executable;
2. If total size of all embedded files > 4GB: creates invalid x86 executable;
3. If size of main EXE > 2 GB: creates executable that seems to be valid but won’t run;
..and that’s only for x86 executables. I wonder how many more issue will surface when I start testing x64 executables. ;)

TLS callbacks

Since Enigma Virtual Box uses TLS callbacks to initialize its hooks and handlers, it will (accidentally?) break any executable that also uses TLS callbacks. However, it preserves TLS StartAddressOfRawData, EndAddressOfRawData and AddressofIndex fields. Very weird.. :)

Have fun (and remember to test your software properly)!

20 Jun

Six-factor authentication (it’s not)

Today I read an article in The Register called Tor torpedoed! Tesco Bank app won’t run with privacy tool installed.

It’s a fun read about Tesco’s Android banking app and how it refuses to run when Tor application is installed on your mobile. But what really caught my attention, is this comment to the article:

I did a count of my account with a certain bank and when I use a PC which does not store their funky cookies, I get 6 (yes really, 6) steps for authentication.

  • Initial Customer code
  • Security password as there is no cookie so PC is not recognised
  • pre-agreed image
  • pre-agreed phrase
  • Customer Number
  • Security code

and if I use a Windows PC it whinges that I don’t have cRapport which would ‘improve my security’
So 6-Factor security isn’t good enough and you want an extra package to help???????

Sir, if you ever read what a multi-factor authentication is, you wouldn’t be stating such nonsense. All six of the steps you mentioned are of the same factor – “something you know”. As such, they provide no additional security, as one keylogger/screengrabber will capture them all.

Why your bank insists on you jumping over so many redundant hoops, remains a mystery..