mcfx's blog

题解、Writeup、游记和碎碎念

De1CTF 2020 Writeup

Crypto

NLFSR

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

#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 here

搜索到 De1CTF2019 的 Mini Purε 一题,本题和该题大致相同,只是已知的明文连续,并且轮数从 6 增加到了 16。同样考虑插值,但是本题中需要插值的多项式达到了 3143^{14} 次,n2n^2 的算法无法通过,并且插值和求 key 需要分开进行。通过找规律可以发现 (实际上把拉格朗日插值的式子化一下也能得到相同结果) ,对于函数 FF,若 FF 的次数不超过 k1k-1kk22 的幂),则 F(n)=i=0k1F(i)j=0,jik1nj(k1)!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)O(k) 求出所有 n^j 的乘积后,再每次除以对应的 n^j 算出。把最后一个 key 设为未知数,然后再套用这个公式,即可得到一个 key 满足的三次方程(实际上三次项系数恒为 0)。可以枚举 key 来解出这个方程。需要找多个 n,求出解的交集,才能保证唯一性。

#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

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

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

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])
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 再询问就可以绕过了。

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 哪种最多就好了。

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

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

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

#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';
    }
}

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

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(或者是不是字母数字),如果是就递归搜索。

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。可以解析文件拿到这些数组和比较值的位置,然后高消。

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='')

日期: 2020-05-06

标签: CTF Writeup

这是一篇旧文,原始文章及评论可在 https://oldblog.mcfx.us/archives/284/ 查看。