Weasel by kao

July 13, 2016

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 :

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 July 16, 2016 by kao
Updated Hall of Fame

July 13, 2016

This should be the devirtualized code in graph form.

Spoiler

Will write a tutorial when fully completed with keygenning.

July 13, 2016

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

July 14, 2016

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 July 14, 2016 by Extreme Coders
Added attachment

July 14, 2016

Verrry nice! All thumbs up!

July 14, 2016

Excellent work

July 16, 2016

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 2⁵⁰

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

weaselkg.rar

August 16, 2016

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

August 16, 2016

3 hours ago, 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

Wow thank you for this it was a great read

August 16, 2016

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 2⁸⁰. Currently running challenges are targeting keyspace 2¹⁴⁴.
* 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.

January 3, 2017

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?

January 3, 2017

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.

January 3, 2017

Pretty easy, see my solution...

Spoiler

January 4, 2017

7 hours ago, mrexodia said:

Pretty easy, see my solution...

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

June 2, 2018

No solution far now

@kao can you post a solution too?

June 4, 2018

On 6/2/2018 at 6:21 PM, GautamGreat said:

No solution far now

@kao can you post a solution too?

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

June 4, 2018

11 minutes ago, MindSystem said:

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

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

June 15, 2019

System of bilinear equations
https://en.wikipedia.org/wiki/System_of_bilinear_equations

Bilinear form
https://en.wikipedia.org/wiki/Bilinear_form

Solution Theory for Systems of Bilinear Equations
https://arxiv.org/pdf/1303.4988.pdf

https://math.stackexchange.com/questions/1894954/finding-a-solution-to-system-of-bilinear-equations

Linear + bilinear = value

Edited June 16, 2019 by CodeExplorer

June 16, 2019

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 June 16, 2019 by CodeExplorer

January 20, 2020

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.

kao
GCZ4B-QTD22

0xec
FZNUL-THK22

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

Quote

Type I: Encryption, m=2n, F=GF(2)

Type II: Encryption, m=2n, F=GF(2⁸)

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(2⁸)

Type VI: Signature, n≈1.5m, F=GF(31)

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

January 22, 2020

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.

Keygen:
https://github.com/extremecoders-re/weasel-keygen

Colab Notebook:
https://colab.research.google.com/drive/1ncoLENvfWLTMF-7hTzWdBOv9ZpBxEKxC

Kaggle Notebook:
https://www.kaggle.com/extremecoders/weasel-keygen?scriptVersionId=27419227

Edited January 22, 2020 by Extreme Coders

January 22, 2020

@Extreme Coders:
Will be great if you also post a full tutorial on how to do it.

February 2, 2020

Posted a write-up about solving the keygenme.

https://0xec.blogspot.com/2020/02/finally-solving-weasel-keygenme.html

February 4, 2020

On 2/2/2020 at 5:11 PM, Extreme Coders said:

Posted a write-up about solving the keygenme.

https://0xec.blogspot.com/2020/02/finally-solving-weasel-keygenme.html

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

Ted.

February 4, 2020

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!

Sign In

Weasel by kao

Recommended Posts

kao

Extreme Coders

kao

Extreme Coders

kao

Kurapica

Extreme Coders

Extreme Coders

cawk

kao

GIV

Extreme Coders

mrexodia

Extreme Coders

GautamGreat

MindSystem

GautamGreat

CodeExplorer

CodeExplorer

Extreme Coders

Extreme Coders

CodeExplorer

Extreme Coders

Teddy Rogers

Extreme Coders

Create an account or sign in to comment

Create an account

Sign in

Community

Search Engines

Code Search

Type I:	Encryption,	m=2n,	F=GF(2)
Type II:	Encryption,	m=2n,	F=GF(2⁸)
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(2⁸)
Type VI:	Signature,	n≈1.5m,	F=GF(31)