Jump to content
Tuts 4 You
  • 3
kao

Weasel by kao

Question

kao

 

PATCH IS NOT AN ACCEPTABLE SOLUTION. PATCH IS NOT AN ACCEPTABLE SOLUTION. PATCH IS NOT AN ACCEPTABLE SOLUTION. 

 

Difficulty : 5/10 (Professional problem to solve)
Language : .NET
Platform : Windows
OS Version : All
Protection : Custom VM + some crypto.

Description :

Learn something new today! If you already know how to deal with simple Virtual Machines, hopefully the crypto will keep you busy for a while.. :) 

However, it's designed to be broken, so better get cracking!

Goals :

Bronze medal: devirtualize the code. To claim the prize, you must provide human-understandable serial checking code that works exactly the same as original. Short tutorial must be written, explaining how you did that.

Silver medal: provide a valid serial for your name. Considering the length of serial, I guess you'll just bruteforce it. All is fair in love and reversing...

Gold medal: create a keygen that is able to generate valid serial(-s) for any name. Key generation should not take more than a second. Longer tutorial must be written, explaining how protection works and how you defeated it.

Sample serials :

kao : QQRR9-DL6JF
tuts4you : RU7FB-ZLANC

Screenshot :

kpC0F1o.png

 

Hall of Fame (in chronological order) :
Extreme Coders: Bronze medal for devirtualized code;
li0nsar3c00l: Bronze medal for devirtualized code + pseudo-tutorial (posted on RTN forum);

---- perhaps you? ---

 

 

weasel_by_kao.zip

 

 

 

Edited by kao
Updated Hall of Fame (see edit history)
  • Like 4

Share this post


Link to post

18 answers to this question

Recommended Posts

  • 1
Extreme Coders

This should be the devirtualized code in graph form.

Spoiler

graph.png

Will write a tutorial when fully completed with keygenning. :) 

Share this post


Link to post
  • 0
kao

Well done, even though the code is still a long way from being "suitable for human consumption". :) Realistically, if you can't understand it, you can't keygen it.

 

P.S. Thanks for using spoiler tags, I really appreciate that! No need to spoil the fun for others... 

Share this post


Link to post
  • 0
Extreme Coders

Here is the devirtualized code. Keygenning this will be quite a effort. I will give it a try nevertheless.

Spoiler

using System;
using System.Collections;
using System.Security.Cryptography;
using System.Text;

namespace weasel_vm
{
	internal class Program
	{
		private byte[] ans;
		private int[] arr;
		private BitArray[] bitarr;

		// The big array
		private byte[] hardcoded = hardcodedarray.hardcoded;
		private byte[] hash;
		private string username = "kao";
		private string password = "QQRR9-DL6JF";

		public static void Main(string[] args)
		{
			Program obj = new Program();
			obj.hash = MD5.Create().ComputeHash(Encoding.UTF8.GetBytes(obj.username));
			obj.doIt();
			obj.check();
			Console.ReadKey(true);
		}

		private void check()
		{
			if (ans[0] == hash[2] && ans[1] == hash[5] && ans[2] == hash[8] && ans[3] == hash[11] && ans[4] == hash[14])
			{
				Console.WriteLine("Success");
				return;
			}
			Console.WriteLine("Failure");
		}

		private void doIt()
		{
			bitarr = new BitArray[3];
			bitarr[0] = new BitArray(hardcoded);
			arr = new int[64];
			ans = new byte[5];
			bitarr[2] = new BitArray(56);
			arr[41] = 0;
			arr[15] = 0;
			while (arr[15] < password.Length)
			{
				arr[8] = "23456789ABCDEFGHJKLMNPQRSTUVWXYZ".IndexOf(password[arr[15]]);
				if (arr[8] != -1)
				{
					arr[1] = 0;
					while ((long)arr[1] < 5L)
					{
						bitarr[2][arr[41]] = ((arr[8] & 1) != 0);
						arr[41]++;
						arr[8] = (int)((uint)arr[8] >> 1);
						arr[1]++;
					}
				}
				arr[15]++;
			}
			bitarr[1] = new BitArray(40);
			arr[61] = 0;
			arr[55] = 0;
			arr[24] = 0;
			while ((long)arr[24] < 40L)
			{
				arr[36] = (bitarr[0][arr[61]] ? 1 : 0);
				arr[61]++;
				arr[18] = 0;
				while ((long)arr[18] < 50L)
				{
					arr[19] = (bitarr[0][arr[61]] ? 1 : 0);
					if (arr[19] != 0)
					{
						arr[19] = (bitarr[2][arr[18]] ? 1 : 0);
						arr[36] += arr[19];
					}
					arr[61]++;
					arr[18]++;
				}
				arr[11] = 0;
				while ((long)arr[11] < 49L)
				{
					arr[47] = arr[11] + 1;
					while ((long)arr[47] < 50L)
					{
						arr[19] = (bitarr[0][arr[61]] ? 1 : 0);
						if (arr[19] != 0)
						{
							arr[19] = (bitarr[2][arr[11]] ? 1 : 0);
							arr[57] = (bitarr[2][arr[47]] ? 1 : 0);
							arr[57] *= arr[19];
							arr[36] += arr[57];
						}
						arr[61]++;
						arr[47]++;
					}
					arr[11]++;
				}
				bitarr[1][arr[55]] = ((arr[36] & 1) != 0);
				arr[55]++;
				arr[24]++;
			}
			bitarr[1].CopyTo(ans, 0);
		}
	}
}

 

vm.rar

Edited by Extreme Coders
Added attachment (see edit history)
  • Like 8

Share this post


Link to post
  • 0
kao

Verrry nice! All thumbs up! :) 

Share this post


Link to post
  • 0
Kurapica

Excellent work

Share this post


Link to post
  • 0
Extreme Coders

Just wanted to post a quick update:

The problem seems to be NP complete and does not look to be keygennable at least not in polynomial time, 1 second is way too unrealistic.Using boolean logic the algorithm can be converted to a sat instance.
Attached are two files. A python sat solver + an smt-lib2 representation of the same problem which tries to find the serial for the name "0xec". However for the computational complexity involved this will take a very very large amount of time. 

As I said NP complete problems can be verified quickly, but finding a solution to them in reasonable time is infeasible.

Bruteforce is also not possible as the size of the keyspace is  250

Ofcourse the above are my personal beliefs, and I would be more than happy to be proved wrong.

weaselkg.rar

  • Like 2

Share this post


Link to post
  • 0
kao

Hey,
I appreciate that you looked into it. In all honesty, I slightly rushed the release due to Labyrenth coming up.

My reasoning was (probably) flawed:
* Similar challenges have been solved with keyspace up to 280. Currently running challenges are targeting keyspace 2144.
* Run-of-the-mill SAT solvers are not suitable for solving this kind of problems. To solve them efficiently, special algorithms are required.

Yet, I still underestimated the difficulty of solving challenge with a significantly reduced keyspace. :( I really apologize for that.

Share this post


Link to post
  • 0
GIV
On 16.08.2016 at 11:58 AM, Extreme Coders said:

As promised, here is the write-up, although I was unsuccessful in fully solving this.
Nevertheless this was an interesting challenge. Will wait for others to keygen this.

https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html

Hi.

I read your blog post.

You cannot use CUDA or OpenCL to speed the compute process?

 

Share this post


Link to post
  • 0
Extreme Coders

I don't think brute-forcing is the correct way to solve the problem. The keyspace is just too big. 
There must be some mathematical approach beyond my limited knowledge.

  • Like 1

Share this post


Link to post
  • 0
mrexodia

Pretty easy, see my solution...

Spoiler

30gTyia.png

pGoKvj8.png

 

  • Like 2
  • Haha 1

Share this post


Link to post
  • 0
Extreme Coders
7 hours ago, mrexodia said:

Pretty easy, see my solution...

Impressive work!!! :) 
Why it didn't occur to me ?

Share this post


Link to post
  • 0
CodeExplorer
Posted (edited)

Share this post


Link to post
  • 0
CodeExplorer
Posted (edited)

https://0xec.blogspot.com/2016/08/solving-weasel-keygenme-by-kao.html

On 6/4/2018 at 6:01 PM, GautamGreat said:

I already read that, that is not a proper solution. 

 

  for (int b = 0; b < 49; b++)
   for (int c = b + 1; c < 50; c++)
    if (huge[y++])
     if (calc[b] & calc[c]) bit = !bit;

the expression will be negated only if calc=1 and calc[c]=1 and huge[y++]
this is easier in reverse order from the end to the begin:
last time checks last two bits: calc[49]&calc[48]

Still trying to find solution.
 

Edited by CodeExplorer (see edit history)

Share this post


Link to post
  • -4
GautamGreat

No solution far now

@kao can you post a solution too?

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...