over 9 years ago

沒什麼好說的,就是個正常的 ICPC BFS 題。
前面要先做一個滿足某條件 hash 的 proof of work,可以用 hashcat 輕鬆解決。

solve.py
import socket
import hashlib
import struct
import sys
import subprocess
import time

st = socket.socket(socket.AF_INET,socket.SOCK_STREAM)
st.connect(('218.2.197.243',6000))

print st.recv(4096)
s = st.recv(4096)
print s
s = s[s.find('SHA1'):]
salt = s[6:22]
sha1 = s[45:45+40]
f = open('hash','w')
f.write(sha1+":"+salt)
f.close()
s = subprocess.check_output("./hashcat-0.47/hashcat hash -m 120 -a 3 -1 '?l?d?u' '?1?1?1?1'",shell=True)
s = s[s.find(salt):][17:21]
print s
st.send(s+'\n')
print st.recv(4096)
s = st.recv(4096).split('\n')[1]
try:
  for tt in range(10000):
    print '('+s+')'
    f = open('input','w')
    f.write(s+'\n')
    f.close()
    subprocess.check_output("./solve")
    ss = open('sol','r').read().split('\n')
    for i in range(len(ss)-1):
      if i==len(ss)-2 and ss[i-1]==ss[i]:
        break
      s = ss[i]
      print '# '+s+']'
      st.send(s+'\n')
      print st.recv(4096)
    s = None
    while s == None:
      zzz = st.recv(4096)
      print zzz
      for x in zzz.split('\n'):
        if 'L' in x:
          s = x
          break
except:
  while True:
    print st.recv(4096)
    time.sleep(1)
solve.cpp
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

char str[30];
int dis[1<<21][21];
int pre[1<<21][21][2];
int que[30000000][2];
int n,sr;
int sol[100][2];

inline void add(int U,int x,int &p,int pu,int px){
    if(dis[U][x]==-1){
        dis[U][x] = dis[pu][px]+1;
        pre[U][x][0] = pu;
        pre[U][x][1] = px;
        que[++p][0] = U;
        que[p][1] = x;
    }
}
                                                                                                                               [66/172]
void print(int U,int x){
    for( int i=n-1; i>=0; i-- ){
        if(i==n-x-1){
            if((U>>i)&1){
                puts("ERROR");
                while(1);
            }
            printf(" ");
        }else{
            printf("%c","LR"[(U>>i)&1]);
        }
    }
    puts("");
}

int calc(int S,int x,int T){
    int p,q,sx=x;
    int U,d,dU,l1,l2,r1,r2,m;
    dis[S][x] = 0;
    p = 0;
    q = -1;
    que[0][0] = S;
    que[0][1] = x;
    while(p!=q){
        q++;
        U = que[q][0];
        x = que[q][1];
        //print(U,x);
        if(U==T){
            m = dis[T][x];
            sr = 0;
            while(U!=S || x!=sx){
                sol[sr][0] = U;
                sol[sr++][1] = x;
                dU = U;
                U = pre[dU][x][0];
                x = pre[dU][x][1];
            }
            sol[sr][0] = U;
            sol[sr++][1] = x;
            return m;
        }
        m = 1<<(n-1-x);
        l1 = m<<1;
        l2 = m<<2;
        r1 = m>>1;
        r2 = m>>2;
        if(x>0){
            dU = ((U&l1)>>1)|(U&(~l1));
            add(dU,x-1,p,U,x);
            if(x>1){
                dU = ((U&l2)>>2)|(U&(~l2));
                add(dU,x-2,p,U,x);
            }
        }
        if(x<n-1){
            dU = ((U&r1)<<1)|(U&(~r1));
            add(dU,x+1,p,U,x);
            if(x<n-2){
                dU = ((U&r2)<<2)|(U&(~r2));
                add(dU,x+2,p,U,x);
            }
        }
    }
    return -1;
}

int main(){
    int x,d,xl,xr;
    FILE *fi = fopen("input","r");
    fgets(str,sizeof(str),fi);
    fclose(fi);
    d = 0;
    xl = xr = 0;
    for( int i=0; str[i]!='\n'; i++ ){
        d<<=1;
        if(str[i]==' '){
            x = i;
        }else if(str[i]=='L'){
            xl++;
        }else{
            d++;
            xr++;
        }
    }
    n = xl+xr+1;
    memset(dis,-1,sizeof(dis));
    calc(d,x,((1<<xr)-1)<<(xl+1));
    printf("%d\n",sr);
    FILE* fs = fopen("sol","w");
    for( int i=sr-1; i>0; i-- ){
        print(sol[i][0],sol[i][1]);
        fprintf(fs,"%d\n",sol[i-1][1]+1);
    }
    print(sol[0][0],sol[0][1]);
    fprintf(fs,"%d\n",xl+1);
    fclose(fs);
    return 0;
}
$ python solve.py
Welcome to the game server!


Proof of work to start the game.
SHA1("efJcaYiCX7AyV7nY" + X).hexdigest() == "ce486d471280a169930efdd1512c85d81e28df72", X is a string of alphanumeric
Input X:
HRVN
Hey, shall we play a game?
Give me a solution to help them get their destination and I will send you your precious.
Please wait while we're generating new round for you

(RRLR LRRLRLLLRL)
# 6]
RRLRL RRLRLLLRL

# 7]
RRLRLR RLRLLLRL

# 5]
RRLR RLRLRLLLRL

# 3]
RR RLRLRLRLLLRL

# 4]
RRR LRLRLRLLLRL

# 6]
RRRRL LRLRLLLRL

# 8]
RRRRLRL LRLLLRL

# 10]
RRRRLRLRL LLLRL

# 12]
RRRRLRLRLLL LRL

# 14]
RRRRLRLRLLLRL L

# 13]
RRRRLRLRLLLR LL

# 11]
RRRRLRLRLL RLLL

# 10]
RRRRLRLRL LRLLL

# 12]
RRRRLRLRLRL LLL

# 11]
RRRRLRLRLR LLLL

# 9]
RRRRLRLR RLLLLL

# 7]
RRRRLR RLRLLLLL

# 5]
RRRR RLRLRLLLLL

# 6]
RRRRR LRLRLLLLL

# 8]
RRRRRRL LRLLLLL

# 10]
RRRRRRLRL LLLLL

# 9]
RRRRRRLR LLLLLL

# 7]
RRRRRR RLLLLLLL

# 8]
Congratulations

[Please wait while we're generating new round for you
Round 2
LRLRRLRRLLR LRL
(LRLRRLRRLLR LRL)
...
(After 100 rounds of game)
...
Congratulations
Your flag is BCTF{wh0-s4ys-h4cke7s-c4nn0t-d0-4lg0rIthm}

(100 輪真的好久...)

← BCTF 混沌密码锁 Writeup BCTF 內網探險 Writeup →