Tokyo Westerns CTF 3rd 2017 Liar's Trap

liarstrip.py

import telnetlib
import commands
import random, time

host = 'ppc2.chal.ctf.westerns.tokyo'
port = 42453

#host = 'localhost'
#port = 1234

start = time.time()
print start

while True:
 tn = telnetlib.Telnet(host,port)

 data = tn.read_until("What's secret?")
 data = data.split("\n")

 user_data = []
 print data

 for a in range(1,101):
  print a,data[a].split(" ")[2]
  user_data.append( int(data[a].split(" ")[2]) )

 print user_data

 now = 0

 gpdata = """P = 115792089237316195423570985008687907853269984665640564039457584007913129639747
b = vector(100)
c = vector(100)
newton_interpolate(xp, fx) = {
  le = length(xp);
  ci = vector(le);
  for(i=1,length(ci),ci[i] = fx[i]);


  for (i = 1, length(ci)-1,
    forstep(k = length(ci)-1, i,-1,
     ci[k+1] = (ci[k+1] - ci[k]) / (xp[k+1] - xp[k-i+1]);
    );
  );

  ans = ci[1];
  p = 1;
  for(i=2,length(ci),
  p = p * (x - xp[i-1]);
  ans = ans + p * ci[i];
  );
  return (ans);
}
pick(v)={v[random(#v)+1]}
{
while(1,
"""
 for a in range(100):
   gpdata += "b[%d] = Mod(%d,P);\n" % (a+1,a+1)
 for a in range(100):
   gpdata += "c[%d] = Mod(%d,P);\n" % (a+1,user_data[ a ])
  #gpdata += 'print ("c confirmed.");\n'
 gpdata += """
bb = vector(26);
cc = vector(26);
for(i=1,26,
buf = -1;
while( buf == -1,q=random(#b)+1;buf=b[q];);
bb[i]=buf;b[q]=-1;cc[i]=c[q];);
f = newton_interpolate(bb,cc);
if(poldegree(f)==24,x=0;print(poldegree(f));print(eval(f));quit);
)}"""
 #print gpdata
 f = open("gpdata_test","w")
 f.write(gpdata)
 f.close()
 print "launch gp."
 ans = commands.getoutput("timeout 28 gp gpdata_test")
 print ans
 if "Goodbye!" not in ans:
   print "timeout..."
   continue

 ans = ans.split("\n")
 if ans[-3] == "24":
   print ans[-2],ans[-3]
   ans = ans[-2].split("Mod(")[1].split(",")[0]
   tn.write(ans + "\n")
   print "[+] elapsed time: ", (time.time()-start)
   tn.interact()
   exit(0)

# [+] elapsed time:  1259.93635201
# 
# OK. I'll give you the flag
# TWCTF{Error_correction_to_Shamir's_Secret_Sharing}
# *** Connection closed by remote host ***

問題自体はShamir's secret sharing（ https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing ）だが、誤りデータ（liar）が38個含まれている。このため、secretを計算する際に１人でもliarが混じると、正しいsecretを得ることができない。そのため、liarの混じっていないデータの組み合わせを探し出し、正しいsecretを得るまで頑張る必要があるが、導出されたsecretが正しいか判別する方法が難しい。
上記スクリプトでは、26個のデータを用いて補間を行うことで、正しいsecretの判別を行っている（本来、secretの復元に必要なデータの数は25）。補間された多項式の次数が25であれば１人以上のliarが含まれており、24であればliarがおらず正しいsecretが得られることになる（誤ったデータが存在する場合、多項式の次数が本来より上がる）。今回は誤りがランダムなので問題ないが、誤りが別の多項式に基づくデータだった場合（25人以上のliarが結託して別のsecretを導出させようとしている場合など）、この手法では誤りとなる可能性がある。
あとは、ひたすらliarのいない組み合わせを引くまで乱択を繰り返す。1回の接続が30秒に制限されているので結構厳しいが、純粋に確率の問題なので、再接続を繰り返し30分くらいかければflagにたどり着ける。
今回は演算をPARI/GPで行った。polinterpolateでの補間でも問題なく解は出たが、以前SECCON 2016 Qual AlphaComplex2を解いている過程でPARI/GPでニュートン補間の関数を書いており、polinterpolateよりも少し速かったので、こちらを使った。