Jump to content
Tuts 4 You

Weasel by kao


Recommended Posts




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 :



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? ---







Edited by kao
Updated Hall of Fame
  • Like 4
Link to comment
Extreme Coders

This should be the devirtualized code in graph form.



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

Link to comment

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... 

Link to comment
Extreme Coders

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


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));

		private void check()
			if (ans[0] == hash[2] && ans[1] == hash[5] && ans[2] == hash[8] && ans[3] == hash[11] && ans[4] == hash[14])

		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[8] = (int)((uint)arr[8] >> 1);
			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[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[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];
				bitarr[1][arr[55]] = ((arr[36] & 1) != 0);
			bitarr[1].CopyTo(ans, 0);



Edited by Extreme Coders
Added attachment
  • Like 8
Link to comment
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.


  • Like 2
Link to comment
  • 5 weeks later...

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.

Link to comment
  • 4 months later...
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.

Link to comment
  • 1 year later...
  • 1 year later...

System of bilinear equations

Bilinear form

Solution Theory for Systems of Bilinear Equations


Linear + bilinear = value


Edited by CodeExplorer
Link to comment


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
Link to comment
  • 7 months later...
Extreme Coders

Phew! It has been close to 4 years and after a lot of wandering here and there I can proudly announce :) that I'm now able to calculate a valid serial for any name.
Here are a couple.



Time taken to generate a key can vary from 2-5 minutes and takes about 12 GB of Physical RAM running on a Nvidia Tesla T4 GPU (2560 CUDA cores).
Providing more RAM and CUDA cores may further reduce the time but I ran it on Google Colab and that's what they offer.

I plan to do a write-up on my blog later but here it is in short.

Initially, I felt the only way to solve the system of equations within a feasible time frame is through a quantum computer using something like Grover's search but the quantum computers available for public use (IBM Q Experience) at this time do not have enough qubits. So this approach had to be discarded.

On deeper analysis, I found the system of equations is nothing but a system of Multivariate Quadratic (MQ) Polynomials. There's a field of Crypto related to this - Multivariate cryptography. Such cryptosystems are considered hard even for a Quantum Computer to attack let alone a classical machine.

Luckily, there's an ongoing challenge based on the exact same idea - Fukuoka MQ challenge.  It turns out small MQ systems particularly which are under-determined (more unknowns than equations) are solvable by classical machines within an accepting time frame and people have posted tools/algorithms to solve them.

One of them is libFES . There's also a GPU implementation of FES which I have used here.

So that's how it went.

Thanks @kao for the challenge. Really learned a lot!!! Its a silver medal for now.

Considering such systems of equation are solvable, generating a key within 1 sec could also be possible given the MQ challenge site posts that this cryptosystem is based on a signature scheme (Type -IV).

Type I: Encryption, m=2n, F=GF(2)
Type II: Encryption, m=2n, F=GF(28)
Type III: Encryption, m=2n, F=GF(31)
Type IV: Signature, n≈1.5m, F=GF(2)
Type V: Signature, n≈1.5m, F=GF(28)
Type VI: Signature, n≈1.5m, F=GF(31)

Once we calculate the private key, generating the signature within 1s should be possible.

  • Like 3
  • Thanks 1
Link to comment
Extreme Coders

Now it takes about a couple of seconds to generate a password. On the downside occasionally it may fail to generate one.
Instructions to compile and run have been provided in the Git repo.


Colab Notebook:

Kaggle Notebook:

Edited by Extreme Coders
  • Like 3
Link to comment
  • 2 weeks later...
Extreme Coders
2 hours ago, Teddy Rogers said:

Really good write up, thank you for persisting and for posting your work... 👍

Thanks a lot Ted. Also thank to Kao for the KeygenMe. Really an innovative challenge so the time it took was well worth it!


Link to comment

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...