[Writeup] TrendMicro 2015

Show problem description

You are trying to sneak into a network, and and impersonate target computer.

Here, you would connect to computers connected via network, and ‘impersonate the computer by exchanging IP address’.

In the target’s network, computers are connected as illustrated below:

You are trying to impersonate computer A by accessing it from computer F.

In here, you can impersonate A by accessing it in the sequence of B -> D -> A, but the IP addresses of computer B and D will be changed.

However, if you access computer A in the order described below, you can impersonate without changing the IP addresses of computers other than A and F.

C -> E -> A -> D -> B -> E -> C -> F -> B -> D -> A

Please sneak into the network as illustrated below, and impersonate computer A from computer P.

Please specify and generate the shortest path as an output.

(In the example above, you may generate the output ‘CEADBECFBDA’.)

If you encounter multiple paths with the same amount of steps, please generate the first value in alphabetical order as the output.

Please submit TMCTF{<Your output>} as your answer.

Solution

I solved this problem using 2-ends BFS (yes, i have quite enough RAM for it:P). A state for this problem represented by the permutation of the assigned IP address of the machines and the last machine to move on. As we will have at most 16 values for 16 machines, we can use 64-bit unsigned int to represent the permutation state, and another 4-bit for last-machine, so uint128 is enough, but finally i was too lazy to do all bitwise operations and use pair struct :D.

3 : TMCTF{CEADBECFBDA}

4 : TMCTF{DGCFAEBGCFBGDHCFBEA}

5 : TMCTF{DHCGAFBHCGBHDJEICGBHDIEJDHBFA}

6 : TMCTF{FKDICHAGBICHBIDKEJCHBIDKEJDKFLEJDIBGA}

7 : TMCTF{FLDJCIAHBJCIBJDLEKCIBJDLEKDLFNGMEKDLFMGNFLDJBHA}

8 : TMCTF{HOFMDKCJAIBKCJBKDMELCJBKDMELDMFOGNELDMFOGNFOHPGNFMDKBIA}

3 : TMCTF{CEADBECFBDA} 4 : TMCTF{DGCFAEBGCFBGDHCFBEA} 5 : TMCTF{DHCGAFBHCGBHDJEICGBHDIEJDHBFA} 6 : TMCTF{FKDICHAGBICHBIDKEJCHBIDKEJDKFLEJDIBGA} 7 : TMCTF{FLDJCIAHBJCIBJDLEKCIBJDLEKDLFNGMEKDLFMGNFLDJBHA} 8 : TMCTF{HOFMDKCJAIBKCJBKDMELCJBKDMELDMFOGNELDMFOGNFOHPGNFMDKBIA}

3 : TMCTF{CEADBECFBDA}
4 : TMCTF{DGCFAEBGCFBGDHCFBEA}
5 : TMCTF{DHCGAFBHCGBHDJEICGBHDIEJDHBFA}
6 : TMCTF{FKDICHAGBICHBIDKEJCHBIDKEJDKFLEJDIBGA}
7 : TMCTF{FLDJCIAHBJCIBJDLEKCIBJDLEKDLFNGMEKDLFMGNFLDJBHA}
8 : TMCTF{HOFMDKCJAIBKCJBKDMELCJBKDMELDMFOGNELDMFOGNFOHPGNFMDKBIA}

My final code below:

	#include<iostream>
	#include<algorithm>
	#include<string>
	#include<set>
	#include<map>
	#include<queue>
	using namespace std;

	typedef __uint128_t uint128_t;
	typedef pair<uint128_t, int > state_t;

	template<typename T>
	inline T sw(T x, int a, int b){
	T _a = ((x>>(4*a))&0xF);
	T _b = ((x>>(4*b))&0xF);
	return x-((_a)<<(4a))-((_b)<<(4b))+((_a)<<(4b))+((_b)<<(4a));
	}

	string solve(int len){
	char ms[100]="", mse[100]="";
	map<state_t, pair<int,int> > prev;
	map<state_t, pair<int,int> > next;

	queue<state_t> Q, QBack;
	vector<vector<int> > adj;
	for(int i=0;i<len;i++){
	adj.push_back(vector<int>());
	if(i>0) adj[i].push_back(len+i-1);
	adj[i].push_back(len+i);
	if(i<len-1) adj[i].push_back(len+i+1);
	}
	for(int i=0;i<len;i++){
	adj.push_back(vector<int>());
	if(i>0) adj[len+i].push_back(i-1);
	adj[len+i].push_back(i);
	if(i<len-1) adj[len+i].push_back(i+1);
	}

	uint128_t initial = 0;
	for(uint128_t i=0;i<len2;i++) initial \|= i<<(i4);
	uint128_t target = sw(initial,0,len*2-1);

	prev[make_pair(initial,len*2-1)]=make_pair(-1,0);
	next[make_pair(target, 0)]=make_pair(-1,0);

	Q.push(make_pair(initial,2*len-1));
	QBack.push(make_pair(target, 0));

	bool found=false;
	state_t x_state;
	int lastQ = -1;
	int lastQBack = -1;
	//first stage: find minimum move
	while((Q.size()>0 \|\| QBack.size()>0) && !found){
	while(Q.size()>0 && !found){
	state_t sn = Q.front();
	int qlen = prev[sn].second;
	if(qlen>lastQ) {lastQ++;break;}
	Q.pop();
	uint128_t s = sn.first;
	int c = sn.second;
	for(int j=0, je=adj[c].size();j<je;j++){
	int c2 = adj[c][j];
	uint128_t s2 = sw(s,c,c2);
	state_t new_state = make_pair(s2, c2);
	if(prev.find(new_state)==prev.end()){
	prev[new_state]=make_pair(c,qlen+1);
	Q.push(new_state);
	if(next.find(new_state)!=next.end()){
	if(!found) x_state = new_state;found=true;
	}
	}
	}
	lastQ = qlen;
	}
	while(!found && QBack.size()>0){
	state_t sn = QBack.front();
	int qlen = next[sn].second;
	if(qlen>lastQBack) {lastQBack++;break;}
	QBack.pop();
	uint128_t s = sn.first;
	int c = sn.second;
	for(int j=0, je=adj[c].size();j<je;j++){
	int c2 = adj[c][j];
	uint128_t s2 = sw(s,c,c2);
	state_t new_state = make_pair(s2, c2);
	if(next.find(new_state)==next.end()){
	next[new_state]=make_pair(c,qlen+1);
	QBack.push(new_state);
	}
	}
	lastQBack = qlen;
	}
	}
	string sol = "";
	//second, find the rest moves
	if(found){
	found = false;
	Q=queue<state_t>();
	Q.push(x_state);
	while(Q.size()>0 && !found){
	state_t sn = Q.front();
	int qlen = prev[sn].second;
	Q.pop();
	uint128_t s = sn.first;
	int c = sn.second;
	for(int j=0, je=adj[c].size();j<je;j++){
	int c2 = adj[c][j];
	uint128_t s2 = sw(s,c,c2);
	state_t new_state = make_pair(s2, c2);
	if(prev.find(new_state)==prev.end()){
	prev[new_state]=make_pair(c,qlen+1);
	Q.push(new_state);
	if(s2 == target){
	x_state = new_state;found=true;break;
	}
	}
	}
	}
	if(found){
	int mov = x_state.second;
	uint128_t state = x_state.first;
	while(mov>=0){
	sol.push_back('A'+mov);
	int new_mov = prev[make_pair(state, mov)].first;
	state = sw(state,mov,new_mov);
	mov=new_mov;
	}
	reverse(sol.begin(),sol.end());

	sol = sol.substr(1);
	} else sol="Uknown2";
	} else sol="Unknow1";
	return sol;
	}

	int main(int argc, char *argv[]) {
	for(int i=3;i<=8;i++)
	cout<<i<<" : TMCTF{"<<solve(i)<<"}"<<endl;
	return 0;
	}

view raw TMCTF2015-prog400.cpp hosted with

by GitHub

Show problem description

(From my memory) Find probability of winning if user decide to hit or stand in international 104-cards blackjack, assume that player already has 2 cards: Aces and 2 and dealer has 3.

Solution

I did not solve this problem in contest time, but after a day thinking i found out that it’s quite easy.

	#include <iostream>
	#include <algorithm>
	#include <set>
	#include <map>
	using namespace std;

	typedef unsigned int uint_t;
	typedef long double real_t;

	uint_t hashParam[11];

	int cardCount;
	int cardLeft[11];

	struct TCardDesk{
	int cards[11];
	bool changed;
	int _score;
	uint_t hash;
	int count;
	TCardDesk(){
	reset();
	}
	inline void reset(){
	changed = false;
	_score = 0;
	hash = 0;
	count = 0;
	memset(cards,0,sizeof(cards));
	}
	inline void addCard(int score){
	count++;
	cardCount--;
	cards[score]++;
	cardLeft[score]--;
	hash += hashParam[score];
	changed = true;
	}
	inline void removeCard(int score){
	count--;
	cardCount++;
	cards[score]--;
	cardLeft[score]++;
	hash -= hashParam[score];
	changed = true;
	}
	inline int score(){
	if(!changed) return _score;
	changed = false;
	int r=0;
	for(int i=1;i<=10;i++) r+=cards[i]*i;//scoring for all cards
	for(int i=cards[1];i>0 && r<=11;i--) r+=10;//scoring for ace
	return _score = r;
	}
	};

	TCardDesk P, D;

	void reset(){
	for(int i=1;i<=9;i++) cardLeft[i]=8;//A to 9
	cardLeft[10]=4*8;//10,J,Q,K
	cardCount = 89+48;
	P.reset();D.reset();
	}

	bool hashUniqueDFS(set<uint_t>& s, TCardDesk& d, int lastUse){
	if(d.score()>21) return false;
	if(s.find(d.hash)!=s.end()){
	printf("Hash conflict\n");
	exit(-1);
	}
	s.insert(d.hash);
	for(int i=lastUse;i<=10;i++){
	if(cardLeft[i]>0){
	d.addCard(i);
	hashUniqueDFS(s,d,i);
	d.removeCard(i);
	}
	}
	return true;
	}

	void hashUnique(){
	set<uint_t> s;
	reset();
	hashUniqueDFS(s,P,1);
	printf("Hash check OK, total size: %lu.\n",s.size());
	}

	real_t skipFactor = 1e-15;

	real_t dealerTurn(real_t factor){
	if(D.score()>21) return 1;
	if(D.score()>=17) return D.score()>=P.score()?0:1;

	if(factor<skipFactor) return 0;

	static map<pair<uint_t,uint_t>, real_t> cache;
	auto it = cache.find(make_pair(P.hash,D.hash));
	if(it!=cache.end()) return it->second;

	real_t total_deal_score = 0;
	int currentCardCount = cardCount;

	for(int i=1;i<=10;i++){
	if(cardLeft[i]>0){
	D.addCard(i);
	total_deal_score += dealerTurn(factor(cardLeft[i]+1)/currentCardCount) (cardLeft[i]+1);//+1 due to addCard
	D.removeCard(i);
	}
	}

	return cache[make_pair(P.hash,D.hash)] = total_deal_score / cardCount;
	}

	real_t playerTurn(real_t factor){
	if(factor<skipFactor) return 0;

	if(P.score()>21) return 0;

	static map<uint_t, real_t> cache;
	auto it = cache.find(P.hash);
	if(it!=cache.end()) return it->second;

	//first case: DEAL
	real_t total_deal_score = 0;
	int currentCardCount = cardCount;
	for(int i=1;i<=10;i++){
	if(cardLeft[i]>0){
	P.addCard(i);
	total_deal_score += playerTurn(factor(cardLeft[i]+1)/currentCardCount) (cardLeft[i]+1);//+1 due to addCard
	P.removeCard(i);
	}
	}

	real_t deal_score = total_deal_score / currentCardCount;

	//second case: STAND
	real_t stand_score = dealerTurn(factor);

	return cache[P.hash] = max(deal_score, stand_score);
	}

	int main(int argc, char *argv[]) {
	hashParam[0]=1;
	for(uint_t i=1;i<=10;i++) hashParam[i] = hashParam[i-1]*97;

	hashUnique();

	reset();
	P.addCard(1);P.addCard(2);
	D.addCard(3);

	printf("TMCTF{HIT:%.4Lf:STAND:%.4Lf}",playerTurn(1.),dealerTurn(1.));

	return 0;
	}

view raw TMCTF2015-prog500.cpp hosted with

by GitHub

Show problem description

Think about two different alphabetical strings with the same lengths.

After you encode the strings with Base64 respectively, if you find characters located in the same position between the two strings, then you may want to extract them.

You may find examples where the final strings are ‘2015’ and ‘Japan’ if you place the extracted characters from left to right in order.

Example:

CaEkMbVnD→(Base64)→Q2FFa01iVm5E
GePoMjXNW→(Base64)→R2VQb01qWE5X

aBckjTiRgbpS→(Base64)→YUJja2pUaVJnYnBT
URehZQjLyvwk→(Base64)→VVJlaFpRakx5dndr

Character ‘a’ may appear in the extracted string like the example above, character ‘f’* will never appear.

Please find a list of characters that would not appear in the extracted string, even if you specify any alphabetical characters in the input.

Once you come up with a list of characters, please sort the characters in the order of ASCII table and generate a SHA1 hash value in lower case.

This is the flag you are looking for.

Please submit the flag in the format of ‘TMCTF{<flag>}’.

*Note: Previous description suggested ‘A’ will never appear. We apologise for any inconvenience.

Solution

Alphabetical character

[a-z|A-Z]

[a-z|A-Z] has hex range

41-5A, 61-7A

41-5A, 61-7A, or binary range

0100 0001 - 0101 1010, 0110 0001 - 0111 1010

0100 0001 - 0101 1010, 0110 0001 - 0111 1010.

In base64 encoding, a group of 3 input byte will be grouped into 4 output base64 byte (3*8 bit = 4*6 bit), we can now calculate the value range for each base64 byte:

1st base64 byte: 010000-010110 + 011000-011110 = .... lol, should we do it by hand?

1st base64 byte: 010000-010110 + 011000-011110 = .... lol, should we do it by hand?

	<?php
	$cs=str_split("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
	foreach ($cs as $i) {
	test($i);
	foreach ($cs as $j) {
	test($i.$j);
	foreach ($cs as $k) {
	test($i.$j.$k);
	}
	}
	}
	$sol=[];
	foreach (array_merge($cs,["+","/"]) as $i) {
	if(!isset($a[$i])) $sol[]=$i;
	}
	usort($sol, function($a,$b){return ord($a)-ord($b);});
	echo implode("",$sol)."\n";
	echo 'TMCTF{'.sha1(implode("",$sol)).'}';
	function test($s){
	global $a;
	foreach(str_split(base64_encode($s)) as $c) $a[$c]=1;
	}
	?>

view raw TMCTF2015-crypto500.php hosted with

by GitHub

+/f

TMCTF{eb2cb19785a3c3bdbba6e1657fbb901097fedc63}

+/f TMCTF{eb2cb19785a3c3bdbba6e1657fbb901097fedc63}

+/f
TMCTF{eb2cb19785a3c3bdbba6e1657fbb901097fedc63}

[Writeup] TrendMicro 2015

Like this:

Related

[Writeup] TrendMicro 2015

Share this:

Like this:

Related