捏浦吸踢艾釜贰零贰贰解题与复现

2022-07-17

Previously

首次500人+的个人竞技大混战突入前百，感觉还是不错的。

就是解出来的题还是以misc占大头，难受，一个是自己还是只会传统逆向，碰着花活就挂，一个是对go之类的其它语言还是不甚了解，回头害得研究orz。

以及，有道小分密码因为睡过头没来得及研究，寄

以及，只有前三十名才有可能拿fufu，寄中寄

Crypto

换成温佬应该已经AK了吧（

注意看leak：

def leak(par, c):
    assert len(par) == 5
    (p,q,n,e,d) = par

    print("Here's something for you.")
    print("n =",n)
    print("e =",e)
    print("c_mod_p =",c % p)
    print("c_mod_q =",c % q)

可知我们能得到的数据只有c mod p，c mod q，n和e。由于RSA的运算中明文和密文都是在模n意义下得到，这里可以直接用中国剩余定理进行攻击（毕竟题目描述都很直白了，而p*q=n刚好满足中国剩余定理的过程，就变成了求解模n意义下的同余方程组）。

那么，先通过对n开方和sympy等库的函数猜测出构成n的质因子，通过中国剩余定理解出c关于p和q的同余方程得到密文：

from Crypto.Util.number import *
from Crypto import *
from gmpy2 import *
from sympy import *

n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791
p = prevprime(int(sqrt(n)))  #通过n开方猜测质因子
q = next_prime(p)
print(p*q==n)

inp = invert(q,p)  #相当于只有两个式子
inq = invert(p,q)

a1 = 32087476819370469840242617415402189007173583393431940289526096277088796498999849060235750455260897143027010566292541554247738211165214410052782944239055659645055068913404216441100218886028415095562520911677409842046139862877354601487378542714918065194110094824176055917454013488494374453496445104680546085816
a2 = 59525076096565721328350936302014853798695106815890830036017737946936659488345231377005951566231961079087016626410792549096788255680730275579842963019533111895111371299157077454009624496993522735647049730706272867590368692485377454608513865895352910757518148630781337674813729235453169946609851250274688614922

c = ( ( a1*inp*q ) + ( a2*inq*p ) )%n

print(c)
print(p)
print(q)

然后将得到的c、p、q代入rsa求解得到明文：

from libnum import *
from sympy import *
def exgcd_(a, b):
    if b == 0:
        return 1, 0
    else:
        k = a // b
        remainder = a % b
        x1, y1 = exgcd_(b, remainder)
        x, y = y1, x1 - k * y1
    return x, y

def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)
        # q = gcd(a, b) = gcd(b, a%b)
        x, y = y, (x - (a // b) * y)
        return x, y, q

def fastpower_(a,b,n):
    ans = 1
    while n > 0:
        if n % 2 ==1:
            ans= ans * a % b
        a = a * a % b
        n = n // 2
    return ans % b

p = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202891
q = 141264221379693044160345378758459195879285464451894666001807667429134348549398732060237738374405784248735752195059908618618110595213605790125890251970818437656069617772772793421437649079362238861287098916200835889507111259332056471215428085418047179545017193159169629731673653136069647622114441162534727202901
e = 65537
c = 11585753035364453623378164545833713948934121662572481093551492504984285077422719062455876099192809170965528989978916297975142142402092047776685650391890015591851053625214326683661927557815767412532952834312578481775648269348260126890551800182341487341482624921905494384205411870866282984671167687789838745481283560185866063970417999748309023918055613674098243729965218609202078551918246640314724590879724609275497227193516782920583249761139685192331805838597293957173545581106446048233248746840771791319643962479707861560044363232580020690857525268858245122996322707454824806268698526881569554077998480289824923073346
n = 19955580242010925349026385826277356862322608500430230515928936214328341334162349408990409245298441768036250429913772953915537485025323789254947881868366911379717813713406996010824562645958646441589124825897348626601466594149743648589703323284919806371555688798726766034226044561171215392728880842964598154362131942585577722616354074267803330013886538511795383890371097812191816934883393255463554256887559394146851379087386846398690114807642170885445050850978579391063585254346364297374019309370189128443081285875218288166996242359495992824824109894071316525623741755423467173894812627595135675814789191820979950786791
phin = totient(n)
# print(n)
# print(phin)
x= exgcd_(e, phin)[0]
d = x % phin
m = fastpower_(c, n, d)
print(n2s(int(m)))

中等数学

RSA，但是生成了一组贵物pq：

p=getPrime(1024)
q=next_prime(p+(p>>500))
#Zuni: 听说密码学是小学数学来着？

很寄，所以结合题目描述，要解方程。但是这种方程组不是小学数学，所以出题人该打（

电脑不顺手，直接用手算。

然后得到了一个不用暴力，只需要nxtprime的方法（虽然gmpy的next_prime本质上也是暴力），于是码出来（感谢0HB佬提醒，RSA类题目过程涉及实数运算的记得整除）：

from gmpy2 import *
from sympy import *

n = 13776679754786305830793674359562910178503525293501875259698297791987196248336062506951151345232816992904634767521007443634017633687862289928715870204388479258679577315915061740028494078672493226329115247979108035669870651598111762906959057540508657823948600824548819666985698501483261504641066030188603032714383272686110228221709062681957025702835354151145335986966796484545336983392388743498515384930244837403932600464428196236533563039992819408281355416477094656741439388971695931526610641826910750926961557362454734732247864647404836037293509009829775634926600458845832805085222154851310850740227722601054242115507
q = next_prime(int(sqrt(n+(n>>500)))) # 既然r要尽可能小，那假设p既定，q-(sqrt(n+(n>>500))也要尽可能小
p = n//q
print('p is :', p)
print('q is :', q)

当然你也可以用sqrt(n)硬梭（虽然我梭了一万年都没梭出来），总之，能求出p和q就行。然后放进你常用的rsa脚本求解就行了。

NepCTF{never_ignore_basic_math}

misc

花花画画画花花

osz文件为osu谱面，打开进入编辑器快进看到flag

注意不明显的下划线，以及，这里的flag可以有中文。

少见的bbbbase

只能说，对于misc工具还是孤陋寡闻了。Nep的教程里出现了一堆使用插件，必可活用于下次.jpg

使用stegdetect，输入.\stegdetect.exe -tjopi -s 10.0 少见的bbbbase.jpg指令，得知图片为jphide隐写，遂用Jphs打开。

输出无后缀文件，保险起见winhex打开，得到一串编码KkYWdvCQcLYewSUUy5TtQc9AMa。

联想到题目名，排除base64等常见密码的可能，转而去找base61、base58、base92等非常见base，最后使用相对常见的base58得出答案。

NepCTF{Real_qiandao~}

签到题

图片大小不对劲，winhex打开，发现其内部藏有大量zip文件。

用kali的binwalk拆解后发现入题解所言是套娃，于是直接上脚本拆解：

from zipfile import *
from re import *
zipname = "G:\\Hank Another\\带学\\CTF\\比赛\\NepCTF2022\\misc\\签到题\\_xxx.jpg.extracted\\"+"232.zip"
while True:
    if zipname != "G:\\Hank Another\\带学\\CTF\\比赛\\NepCTF2022\\misc\\签到题\\_xxx.jpg.extracted\\1.zip":
        ts1 = ZipFile(zipname)
        #print ts1.namelist()[0]
        res = search('[0-9]*',ts1.namelist()[0])
        print (res.group())
        passwd = str.encode(res.group())
        ts1.extractall("G:\\Hank Another\\带学\\CTF\\比赛\\NepCTF2022\\misc\\签到题\\_xxx.jpg.extracted\\",pwd=passwd)
        zipname = "G:\\Hank Another\\带学\\CTF\\比赛\\NepCTF2022\\misc\\签到题\\_xxx.jpg.extracted\\"+ts1.namelist()[0]
    else:
        print ("find")

拆解到只剩一层时发现压缩包内含流量包，压缩包含加密。winhex再次打开发现文件头并没有加密标记，但目录区有加密标记，为伪加密，直接改掉标记拆包。

打开流量包，发现是键盘usb流量，通过.\tshark.exe -T json -r keyboard.pcap > usbdata.json指令处理后得到操作数据的json文件，但指令无法直接提取操作内容，故手动提取得到usbdata.txt：

然后脚本开跑，得出操作。

from numpy import *
mappings = { 0x04:"a",  0x05:"b",  0x06:"c", 0x07:"d", 0x08:"e", 0x09:"f", 0x0A:"g",  0x0B:"h", 0x0C:"i",  0x0D:"j", 0x0E:"k", 0x0F:"l", 0x10:"m", 0x11:"n",0x12:"o",  0x13:"p", 0x14:"q", 0x15:"r", 0x16:"s", 0x17:"t", 0x18:"u",0x19:"v", 0x1A:"w", 0x1B:"x", 0x1C:"y", 0x1D:"z", 0x1E:"1", 0x1F:"2", 0x20:"3", 0x21:"4", 0x22:"5",  0x23:"6", 0x24:"7", 0x25:"8", 0x26:"9", 0x27:"0", 0x28:"\n", 0x2a:"[DEL]",  0X2B:"    ", 0x2C:" ",  0x2D:"-", 0x2E:"=", 0x2F:"[",  0x30:"]",  0x31:"\\", 0x32:"`", 0x33:";",  0x34:"'", 0x36:",",  0x37:"." }
shiftmappings = { 0x04:"A",  0x05:"B",  0x06:"C", 0x07:"D", 0x08:"E", 0x09:"F", 0x0A:"G",  0x0B:"H", 0x0C:"I",  0x0D:"J", 0x0E:"K", 0x0F:"L", 0x10:"M", 0x11:"N",0x12:"O",  0x13:"P", 0x14:"Q", 0x15:"R", 0x16:"S", 0x17:"T", 0x18:"U",0x19:"V", 0x1A:"W", 0x1B:"X", 0x1C:"Y", 0x1D:"Z", 0x1E:"!", 0x1F:"@", 0x20:"#", 0x21:"$", 0x22:"%",  0x23:"^", 0x24:"&", 0x25:"*", 0x26:"(", 0x27:")", 0x28:"\n", 0x2a:"[DEL]",  0X2B:"    ", 0x2C:" ",  0x2D:"_", 0x2E:"+", 0x2F:"{",  0x30:"}",  0x31:"|", 0x32:"~", 0x33:":",  0x34:"[double quo]", 0x36:"<",  0x37:">" }

nums = []
shiftag = []
keys = open('usbdata.txt')
for line in keys:
    if line[0]!='0' or (line[1]!='0' and line[1]!='2') or line[3]!='0' or line[4]!='0' or line[9]!='0' or line[10]!='0' or line[12]!='0' or line[13]!='0' or line[15]!='0' or line[16]!='0' or line[18]!='0' or line[19]!='0' or line[21]!='0' or line[22]!='0':
         continue
    nums.append(int(line[6:8],16))
    shiftag.append(int(line[0:2],16))
keys.close()
output = ""
for i in range(len(nums)):
    if nums[i] == 0:
        continue
    if nums[i] in mappings:
        if shiftag[i]:
            output += shiftmappings[nums[i]]
        else:
            output += mappings[nums[i]]
    else:
        output += '[unknown]'
print ('output :\n' + output)

馅饼？陷阱！

偏简单的社工。模拟了一个网友被骗，自己需要靠照片找银行的情况。

通过照片二上“尚德源”的招牌和“琼”字头车牌，确认地区为海南，用google地图进一步确认店铺名称为“尚德源茶园酒店”，以及所在地海南省三亚市天涯区新风街。结合附近地址，如饺子城等店铺确认位置后，找到附近有对应银行为光大银行，银行官网网址即为flag。

Reverse

快来签到

die发现repsych.asm，谷歌搜索，发现是一个用于将位图隐藏到ida控制流图的插件。

抬高ida的流图nodes上限，再缩小主函数显示比例，答案出现。

We_Can_Gone

exe文件，用32位ida打开，并未发现明显主函数。发现报错字段：“no goroutines (main called runtime.Goexit) - deadlock!”，确认是go语言，于是用IDAGolangHelper把它的汇编形式变得阳间点。

但是我们怎么确认主函数的位置捏？如果你在汇编里头铁搜索，你八成只能找得到一点残渣：

这时候就得去字节码部分搜，去找数据。这一搜索还真找着了，地址4AF360附近有一个false：

至少找到要用的字符串了，方向多没关系，挨个试一遍，最后发现这个false与off_4D2334关联，而off_4D2334又与sub_499630关联，于是我们终于找到了个类似主函数的东西。

首先判定，长度是否为23，是否符合flag格式，然后是和某个数组进行比对是否一致。但是这个数组在未运行时神龙见首不见尾，我们直接进行动态调试让它现形（随便输一个总长23的flag，在循环判断的地方下断点）：

NepCTF{U9et_t0_th3TRUE}

simple_judge

官方题解给出的源码是这样：

#include<bits/stdc++.h>
#include<unistd.h>
using namespace std;
char passage[100000];
int num;
int read_n(int len){
  int i=1;
  while(i<=len){
    scanf("%c",passage+i);
    i++;
  }
  return len;
}
int mask(int x){
  return 1<<x;
}
int get_bit(int x){
  if(1+x/8>num+1){
    printf("too short\n");
    exit(0);
  }
  //printf("%c\n",(passage[1+x/8]));
  return !!(passage[1+x/8]&mask(x%8));
} 
bool judge_xor(int x,int y){
  if(x==y)return 0;
  return (get_bit(x)^get_bit(y));
}
bool judge_or(int x,int y){
  if(x==y)return 0;
  return get_bit(x)||get_bit(y);
}
int main(){
  freopen("data.txt","r",stdin);
  int len;
  cin>>len;
  getchar();
  num=read_n(len);
  if(num!=len)printf("wrong\n");
  printf("I will check your input passage\nplease make sure ./data.txt exists and follow the input format\n");
  //printf(passage+1);
  int n;
  scanf("%d\n",&n);
  //printf("%d\n",n);
  for(int i=1;i<=n;i++){
    int op,x,y;
    scanf("%d %d %d",&op,&x,&y);
    if(op==1){
      if(!judge_or(x,y)){
        printf("Wrong passage on %d\n",i);
        exit(0);
      }
    }
    else{
      if(!judge_xor(x,y)){
        printf("Wrong passage on %d\n",i);
        exit(0);
      }
    }
  }
  printf("Great!,But you may check your input if it is passage!\n");
  return 0;
}

但在ida里其实这俩长得一毛一样：

_BOOL8 __fastcall sub_C24(int a1)
{
  int v1; // ebx

  if ( a1 / 8 + 1 > dword_24A16E0 + 1 )
  {
    puts("too short");
    exit(0);
  }
  v1 = *((char *)&unk_2489040 + a1 / 8 + 1);
  return (v1 & (unsigned int)sub_C0D(a1 % 8)) != 0;
}

_BOOL8 __fastcall sub_CEC(unsigned int a1, unsigned int a2)
{
  if ( a1 == a2 )
    return 0LL;
  return sub_C24(a1) || sub_C24(a2);
}

bool __fastcall sub_CAC(int a1, int a2)
{
  _BOOL4 v3; // ebx

  if ( a1 == a2 )
    return 0;
  v3 = sub_C24(a1);
  return v3 != sub_C24(a2);
}

__int64 __fastcall main(__int64 a1, char **a2, char **a3)
{
  unsigned int i; // [rsp+0h] [rbp-10h]
  unsigned int v5; // [rsp+8h] [rbp-8h]
  unsigned int v6; // [rsp+Ch] [rbp-4h]

  sub_7AA(a1, a2, a3);
  freopen("passage.txt", "r", stdin);
  dword_24A16E0 = read(0, &unk_2489041, (size_t)&off_1869F);
  puts("I will check your input passage\nplease make sure ./passage.txt exists.");
  freopen("data", "r", stdin);
  for ( i = 0; (int)i <= (int)&off_2E06BF; ++i )
  {
    v5 = dword_3720[3 * i + 1];
    v6 = dword_3720[3 * i + 2];
    if ( dword_3720[3 * i] == 1 )
    {
      if ( !sub_CEC(v5, v6) )
      {
        printf("Wrong passage on %d\n", i);
        exit(0);
      }
    }
    else if ( !sub_CAC(v5, v6) )
    {
      printf("Wrong passage on %d\n", i);
      exit(0);
    }
  }
  puts("Great!,But you may check your input if it is passage!");
  return 0LL;
}

无非就是在题设中dword_3720给定了操作，基本都是用按字节操作去求某些东西，一道算法题。这里就要扯到一个我曾经打OI时没注意到的一个知识盲区——2-SAT。

可以证明，当k>2时，k-SAT是NP完全的。因此一般讨论的是k=2的情况，即2-SAT问题。

我们通俗的说，就是给你n个变量ai，每个变量能且只能取0/1的值。同时给出若干条件，形式诸如(not)a[i]opt(not)a[j]=0/1，其中opt表示and,or,xor中的一种，而求解2-SAT的解就是求出满足所有限制的一组a。

————摘自hl666的文章

这么说来，我们之前提到过的搜索算法似乎很适合求解这种贵物。题目本身就是一个2-SAT问题，看起来只需要把2-SAT问题转换为一张有向图就行了。但……怎么转换呢？

于是我去翻了各种2-SAT的模板题……这simple个锤子，出题人吃了吗，没吃吃我一拳（

虽然这2-SAT的结构还算简单，就只有或和异或，但这鬼屎数据量简直屎到劲，根本提不出来（从0x3720到0x1869B，IDA直呼太大了进不去）。更不要说这张奇大无比的图它还有环，还有环口牙！！！而且自己测试的时候官解都挂了……离谱。

（后来发现是提数据的时候逼到ida软件本体读取上限了，看来得用其它工具）