Jump to content
Tuts 4 You

Weasel by kao

kao

By kao
in KeygenMe

 Share

Recommended Posts

kao

kao

Posted
Posted (edited)

 

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
  • Like 4
Extreme Coders

Extreme Coders

Posted
Posted

This should be the devirtualized code in graph form.

Spoiler

graph.png

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

kao

kao

Posted
  • Author
Posted

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

Extreme Coders

Extreme Coders

Posted
Posted (edited)

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
  • Like 8
kao

kao

Posted
  • Author
Posted

Verrry nice! All thumbs up! :) 

Kurapica

Kurapica

Posted
Posted

Excellent work

Extreme Coders

Extreme Coders

Posted
Posted

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
  • 5 weeks later...
kao

kao

Posted
  • Author
Posted

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.

  • 4 months later...
GIV

GIV

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

 

Extreme Coders

Extreme Coders

Posted
Posted

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.

mrexodia

mrexodia

Posted
Posted

Pretty easy, see my solution...

Spoiler

30gTyia.png

pGoKvj8.png

 

  • Like 3
  • Haha 2
Extreme Coders

Extreme Coders

Posted
Posted
7 hours ago, mrexodia said:

Pretty easy, see my solution...

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

  • 1 year later...
GautamGreat

GautamGreat

Posted
Posted

No solution far now

@kao can you post a solution too?

  • 1 year later...
CodeExplorer

CodeExplorer

Posted
Posted (edited)

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 by CodeExplorer
CodeExplorer

CodeExplorer

Posted
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
  • 7 months later...
Extreme Coders

Extreme Coders

Posted
Posted

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(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
Extreme Coders

Extreme Coders

Posted
Posted (edited)

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 by Extreme Coders
  • Like 3
CodeExplorer

CodeExplorer

Posted
Posted

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

  • 2 weeks later...
Extreme Coders

Extreme Coders

Posted
Posted
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!
 

 

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
 Share
Go to topic listing
×
×
  • Create New...