Black Box

[megabreit]

Looking to the disassembly it was time to polish my old C knowledge a bit.

Code: Select all

# include <stdio.h>
# include <values.h>

int main (int argc, char** argv)
{
        signed int i;
        for (i=MININT; i<MAXINT; i++)
        {
        register arg=i;
        register arg1=arg;
        arg=arg>>0x1f;
        arg=~arg;
        arg=arg&arg1;
        arg-=0x6fe5d5;
        arg=arg^0x2eb22189;
        arg=arg*0x1534162;
        arg=arg^0x69f6bc7;
        if (arg==230392619) {printf("%i\n",i);}
        }
}

This one is exactly the same as the source because it generates to same assembler code (the type "register" is important!)
I thought of coding it in some scripting language, but was not sure how to code the arithmetic with 32 bit signed integers.
The result: a rocket fast program (takes a few seconds to complete) and some C back into my brain
Anybody did it in a scripting language? How?

[gfoot]

I used Python, explicitly rounding modulo 2**32 in places. Rather than brute-forcing, having rewritten the steps, I worked back from the answer deciding which inputs at each step gave the right intermediate result. It wasn't too hard, though there were often several possible intermediates; however it always turned out that one was impossible due to an earlier step.

Probably much quicker to brute force it, though, as you say.

[homeas]

@gfoot yes indeed, running the assembler part in Delphi on an old P4 you only need 11 secs -- so it is not really efficient to recalculate backwards (although that looks quite easy too, but surely will take more than 11 s). This challenge was a kind of recreation - after a lot of really hard challenges ...

[man]

Code: Select all

#include <iostream>
int main()
{
	int out = 230392619;
	
	// 1. bruteforce
	/*for( int i = 0; ; ++i )
	{
		int edx = i;
		edx -=	0x6FE5D5;
		edx ^=	0x2EB22189;
		edx *=	0x1534162;
		edx ^=	0x69F6BC7;
		
		if( edx == out )
		{
			std::cout << i << std::endl;
			break;
		}
	}*/

	// 2. inversion
	int x, edx = out;
	edx ^=	0x69F6BC7;
	
	// inversion of the multiplication: can this be done more efficiently?
	for( x = 0 ; x * 0x1534162 != edx ; ++x ); edx = x; 
	
	edx ^=	0x2EB22189;
	edx +=	0x6FE5D5;
	std::cout <<  edx << std::endl;
	

	return 0;
}

Is there a better way to invert the multiplication?

[OKOB]

My solution

Code: Select all

#include "stdafx.h"
#include "stdio.h"

int main(int argc, char* argv[])
{
	unsigned int j;
	for(unsigned int i=0; i<0xFFFFFFFF; i++) {
	_asm {
		push    eax
		push    edx
		mov     eax, i
		mov     edx, eax
		sar     edx, 1Fh
		not     edx
		and     edx, eax
		sub     edx, 0x6FE5D5
		xor     edx, 0x2EB22189
		imul    edx, 0x1534162
		xor     edx, 0x69F6BC7
		mov     j, edx
		pop     edx
		pop     eax
	}
		if(j == 230392619)
			break;
	}
	printf("%d\n", i);
	return 0;
}

[b0bA]

Code: Select all

public class Blackbox {
	public static void main(String[] args) {	
		int x = 0;
		int s = 230392619;
		int i = 0;
		int ul = Integer.MAX_VALUE;		
		while (x!=s) {
			x = ((( ul & i - 7333333 ) ^ 783425929 ) * 22233442 ) ^ 111111111;
			i++;
		}
		System.out.println("Solution:"+(i-1));
	}
}

[kne1p]

Is there a better way to invert the multiplication?

Code: Select all

		int i, d = 0;
 
		i = 230392619;
		i ^= 0x69f6bc7;
		d = i / 0x1534162;
		while (d++ * 0x1534162 != i);
		i = d ^ 0x2eb22189;
		i += 0x6fe5d5;

I guess not, therefore the reverse calculation is only about twice as fast as the normal brute force approach.

[laz0r]

I found the first few thousand values and worked out that the bit in position n is periodic in 2^n, so after working out what the last 16 bits had to be, I ended up with having to be congruent to 20148 mod 32768. That was enough to brute force in 15 mins.

[aurora]

i used brute force ... i had a machine lying around with a fast CPU and enough RAM to fit the entire system in. i used a tinycore linux and a ramdisk, to reduce IO. the shell script i used:

Code: Select all

#!/usr/bin/env bash
max=2147483647
threads=100
steps=$((max / threads + 1))

function test {
        local s=$1
        local e=$2
        local t=$3

        while [[ $s -lt $e ]]; do
                v=`./onetest $s`
                echo "$s = $v" | tee status.$t.log | grep 230392619
                s=$((s + 1))
        done
}

for (( i=0; i<$threads; i++ )); do
        s=$((i * steps))
        e=$(((i + 1) * steps))
        ((test $s $e $i &) &)
done

still took long enough ...

[ftfish]

I guess not, therefore the reverse calculation is only about twice as fast as the normal brute force approach.

Well, what you have to solve is the linear congruence equation: x*22233442 == 186968300 (mod 4294967296).
This can be done with knowledge of elementary number theory (extended euclidean algorithm). The time complexity is just O(logN) instead of O(N) where N is the largest number above.

[AMindForeverVoyaging]

(the type "register" is important!)

Actually, it works just fine without.


This was a great challenge!

At first, I tried to get the GLIBC version 2.0, since seemingly that was used for creating the binary. I found that version on the GNU ftp server. However it would not compile - there was always some error with some time header file(s) that I was not able to fix.

So I got myself a disassembler (I used IDA Pro Free), looked at the instructions, and decided to reverse engineer the code. This worked out quite nicely. My solution:

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#define SAR_CONSTANT    0x1F
#define SUB_CONSTANT    0x6FE5D5
#define XOR_CONSTANT_1  0x2EB22189
#define MUL_CONSTANT    0x1534162
#define XOR_CONSTANT_2  0x69F6BC7

inline int onetest(int input)
{
	int temp;
	temp = input;
	
	input = (input >> SAR_CONSTANT);   // SAR
	input = (~input);                  // NOT
	input = (input & temp);			   // AND
	input = (input - SUB_CONSTANT);    // SUB
	input = (input ^ XOR_CONSTANT_1);  // 1st XOR
	input = (input * MUL_CONSTANT);    // IMUL
	input = (input ^ XOR_CONSTANT_2);  // 2nd XOR
	
	return input;
}

int main(int argc, char** argv)
{
	unsigned int i;
	
	for (i=0; i<0xFFFFFFFF; i++)
	{
		if ( onetest(i) == 230392619 )
			printf("Solution: %d\n", i);
	}
	
	return 0;
}

[captainfox]

Nice challenge!

Tried it with IDA too, my decompiler returned a somewhat packed version of the calculation.

Brute force script ran about 6 seconds on my machine before spitting out the answer:

Code: Select all

#include <stdio.h>

int main(int argc, char **argv, char **envp) {
	for (int i = 0; i <= 2147483647; i++) {
		if ((22233442 * (((i & ~(i >> 31)) - 7333333) ^ 0x2EB22189) ^ 0x69F6BC7) == 230392619) {
			printf("%d\n", i);
			break;
		}
	}
}

[godefv]

I guess not, therefore the reverse calculation is only about twice as fast as the normal brute force approach.

Well, what you have to solve is the linear congruence equation: x*22233442 == 186968300 (mod 4294967296).
This can be done with knowledge of elementary number theory (extended euclidean algorithm). The time complexity is just O(logN) instead of O(N) where N is the largest number above.

+1
the extended euclidean algorithm got the division for me as well. it is actually the same problem as in the previous challenge Patience with the only difference being decompiling java class or elf binary.
This doesn't involve coding at all ! We could just calculate the answer by hand quite easily :p

I used gdb to disassemble the elf and used the value from the assembler code.

[Hippo]

After finding boomerang could decompile it ... I wrote bruteforce to inverse the multiplication. It was that fast that I have not figured the euclidian algorithm will help.