神奇的Base WriteUp

题目链接: SOCTF - 综合实训平台

下载题目附件, 打开发现为Base64_changed.exe. 使用ExeInfoPe查看其为win32应用. greps命令找不到flag字符串, 使用IDA.exe尝试打开进行静态分析.

ida静态分析

直接使用f5插件分析, 主函数如下:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  void *v3; // esi
  int v4; // eax
  char *v5; // esi
  int v6; // eax

  v3 = malloc(0x64u);
  printf("Please Input the flag:");
  scanf_s("%s", v3, 100);
  v4 = sub_401030(v3);
  v5 = (char *)sub_4018B0(v4);
  v6 = strcmp("8&]Z:&)&=%$T+3%4,6PU:#1M544Q5$,]", v5);
  if ( v6 )
    v6 = -(v6 < 0) | 1;
  if ( v6 )
    printf("wrong\n");
  else
    printf("right\n");
  free(v5);
  system("pause");
  return 0;
}

发现关键字符串"8&]Z:&)&=%$T+3%4,6PU:#1M544Q5$,]"和两个关键子函数sub_401030和sub_4018B0.

• 函数sub_401030如下所示:

_BYTE *__thiscall sub_401030(const char *this)
{
  //...
  v18 = this;
  v1 = 0;
  v2 = strlen(this);
  v14 = v2;
  v3 = 4 * (v2 / 3);
  if ( v2 % 3 )
    v3 = 4 * (v2 / 3) + 4;
  v4 = v3;
  v5 = malloc((v3 + 1) | -__CFADD__(v3, 1));
  v12 = v5;
  v5[v4] = 0;
  if ( v2 > 0 )
  {
    v17 = v2 + 1;
    v15 = 3 - (_DWORD)v18;
    v6 = (char *)v18;
    v16 = (v2 - 1) / 3u + 1;
    do
    {
      v7 = 0;
      v8 = v6[2] | ((v6[1] | (*v6 << 8)) << 8); // v8为24位数, 在用户输入中取三个为一组, 是base64编码的典型特征
      v13 = (signed int)&v6[v15] > v14;
      v9 = 18;
      do
      {
        v5 = v12;
        if ( v7 >= v17 && v13 )
          v12[v1] = 61;
        else
          v12[v1] = byte_403160[(((v8 >> v9) & 0x3F) + 14) % 64];
        v9 -= 6;
        ++v1;
        ++v7;
      }
      while ( v9 > -6 );
      v17 -= 3;
      v6 = (char *)(v18 + 3);
      v10 = v16-- == 1;
      v18 += 3;
    }
    while ( !v10 );
  }
  return v5;
}

可以看出, 该函数对用户输入进行了一种变体的base64编码. 其中33行处的byte_403160数组为编码用的字典, 内部的(x + 14) % 64运算相当于字典整体向前循环偏移14位.

在IDA中跳转到地址0x403160处可以得到字典如下:

.rdata:00403160 ; char byte_403160[]
.rdata:00403160 byte_403160     db 41h                  ; DATA XREF: sub_401030:loc_40112C↑r
.rdata:00403161 aBcdefghijklmno db 'BCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/abcdefghijklmnopqrstuvwxyz',0

• 函数sub_4018B0如下所示:

_BYTE *__thiscall sub_4018B0(const char *this)
{
  // ...
  v14 = this;
  v1 = strlen(this);
  v2 = v1 / 3;
  v3 = v1 % 3;
  v4 = 4 * v2;
  v13 = v3;
  if ( v3 )
    v4 = 4 * v2 + 4;
  v5 = malloc((v4 + 1) | -__CFADD__(v4, 1));
  v15 = v4 - 2;
  v5[v4] = 0;
  v6 = 0;
  if ( v15 > 0 )
  {
    v7 = (int)(v14 + 1);
    do
    {
      v8 = *(_BYTE *)(v7 - 1);
      v7 += 3;
      v9 = *(_BYTE *)(v7 - 3);
      v5[v6] = (v8 >> 2) + 32;
      v5[v6 + 1] = ((v9 >> 4) + 32) | 16 * (v8 & 3);
      v10 = *(_BYTE *)(v7 - 2) >> 6;
      v5[v6 + 3] = (*(_BYTE *)(v7 - 2) & 0x3F) + 32;
      v5[v6 + 2] = (v10 | 4 * (v9 & 0xF)) + 32;
      v6 += 4;
    }
    while ( v6 < v15 );
    v3 = v13;
  }
  result = v5;
  v12 = v3 - 1;
  if ( v12 )
  {
    if ( v12 == 1 )
      v5[v6 - 1] = 61; // 0x3D
  }
  else
  {
    *(_WORD *)&v5[v6 - 2] = 15677; // 0x3D3D
  }
  return result;
}

该函数的作用是将输入的每三个字符一组(设为char1, char2, char3), 按照数值划分成四个ascii字符(设为enc1, enc2, enc3, enc4). 即将base64编码中的字典直接替换为ascii字符.

需要注意的是, 在25行的((v9 >> 4) + 32) | 16 * (v8 & 3);中可以看出, 每组第二个字符(enc2)的最高位一定为1, 这会使得逆向求解char1时出现一对多的情况.

实现编码和解码算法

通过对程序进行静态分析, 可以模拟出程序中的两个编码函数如下所示:

window.encrypt = function(input = "") {// 第二个编码函数, sub_4018B0
    let buffer = [];
    let len = input.length;
    let _input = input.split("");
    let v2 = Number.parseInt(len / 3);
    let v3 = len % 3;
    let bufferLen = 4 * v2;
    let v8 = 0;
    let v9 = 0;
    let v10 = 0;

    if (v3)
        bufferLen = 4 * v2 + 4;

    buffer = new Array(bufferLen);
    let v15 = bufferLen - 2;
    let i = 0;
    let j = 1;

    if (v15 > 0) {
        for (i; i < v15; i += 4) {
            v8 = _input[j - 1].charCodeAt();
            if (j < len)
                v9 = _input[j].charCodeAt();
            else
                v9 = 0x0;
            if (j + 1 < len)
                v10 = _input[j + 1].charCodeAt();
            else
                v9 = 0x0;
            buffer[i] = (v8 >> 2) + 32; // enc1是char1的高6位 + 32
            buffer[i + 1] = ((v9 >> 4) + 32) | (v8 & 3) << 4; // enc2是char1的低2位后接(char2的高4位 + 32), 因为不是给整体进行+32, 所以这里编码后会出现多对一的情况.
            buffer[i + 2] = ((v10 >> 6) | ((v9 & 0xF)) << 2) + 32; // enc3是char2的低4位后接char3的高2位 + 32
            buffer[i + 3] = (v10 & 0x3F) + 32; // enc4是char3的低6位 + 32
            j += 3;
        }
    }
    let v12 = v3 - 1;
    if (v12) {
        if (v12 == 1) {
            buffer[i - 1] = 61;
        }
    } else {
        buffer[i - 2] = 61;
        buffer[i - 1] = 61;
    }
    return (buffer.map(ele => String.fromCharCode(ele)).join(""));
}

window.decrypt = function(input = "") { // 逆向解码函数
    let buffer = [];
    let len = input.length;
    let _input = input.split("").map(ele => ele.charCodeAt());
    let v2 = Number.parseInt(len / 4);
    let v3 = len % 4;
    let bufferLen = 3 * v2;
    let enc1 = 0;
    let enc2 = 0;
    let enc3 = 0;
    let enc4 = 0;

    if (v3)
        bufferLen = 3 * v2 + 3;
    buffer = new Array(bufferLen);
    let v15 = bufferLen - 3;
    let i = 0;
    let j = 0;

    if (v15 > 0) {
        for (i; i <= v15; i += 3) {
            enc1 = _input[j];
            if (j + 1 < len)
                enc2 = _input[j + 1];
            if (j + 2 < len)
                enc3 = _input[j + 2];
            if (j + 3 < len)
                enc4 = _input[j + 3];
            if (enc3 == 61 && j == len - 4) {
                enc3 = 32;
            }
            if (enc4 == 61 && j == len - 4) {
                enc4 = 32;
            }

            buffer[i] = ((enc1 - 32) << 2) | ((enc2 >> 4) & 0x3);// 由于编码时+32的缘故, 求解char1低2位时, 1和3无法区分, 0和2无法区分.
            buffer[i + 1] = ((enc2 & 0xf) << 4) | (((enc3 - 32) >> 2) & 0xf);
            buffer[i + 2] = ((enc3 & 0x3) << 6) | ((enc4 -32) & 0x3f);
            j += 4;
        }
    }
    return (buffer.map(ele => String.fromCharCode(ele)).join(""));
}

let _keyStr = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789+/abcdefghijklmnopqrstuvwxyz";

window.encode = function(input) { // 第一个编码函数, sub_401030
    let output = '', i = 0, chr1, chr2, chr3, enc1, enc2, enc3, enc4;

    while (i < input.length) {
        chr1 = input.charCodeAt(i++);
        chr2 = input.charCodeAt(i++);
        chr3 = input.charCodeAt(i++);
        enc1 = (( chr1 >> 2 ) + 14 ) % 64; // (x + 14) % 64表示在字典中索引时循环后移14位
        enc2 = ((((chr1 & 3) << 4) | (chr2 >> 4)) + 14 ) % 64;
        enc3 = ((((chr2 & 15) << 2) | (chr3 >> 6)) + 14) % 64;
        enc4 = ((chr3 & 63) + 14 ) % 64;

        output = output + _keyStr.charAt(enc1) + _keyStr.charAt(enc2);
        if (Number.isNaN(chr2)) {
            output = output + "==";
        } else if (Number.isNaN(chr3)) {
            output = output + _keyStr.charAt(enc3) + "=";
        } else {
            output = output + _keyStr.charAt(enc3) + _keyStr.charAt(enc4);
        }
    }
    return output;
}

window.decode = function(input) {
    let output = '', i = 0, chr1, chr2, chr3, enc1, enc2, enc3, enc4;

    while (i < input.length) {
        enc1 = (_keyStr.indexOf(input.charAt(i++)) + 64 - 14) % 64; // 循环后移 64 -14 位
        enc2 = (_keyStr.indexOf(input.charAt(i++)) + 64 - 14) % 64; // 可以恢复
        enc3 = _keyStr.indexOf(input.charAt(i++));
        enc4 = _keyStr.indexOf(input.charAt(i++));
        if (enc3 >= 0) // 由于enc3和enc4可能是后补充的"=", 需要单独拿出讨论. 注意, 
            enc3 = (enc3 + 64 - 14) % 64; // 字典中没有'='
        if (enc4 >= 0)
            enc4 = (enc4 + 64 - 14) % 64;
        chr1 = (enc1 << 2) | (enc2 >> 4);
        chr2 = ((enc2 & 15) << 4) | (enc3 >> 2);
        chr3 = ((enc3 & 3) << 6) | enc4;

        output = output + String.fromCharCode(chr1);
        if (enc3 >= 0) {
            output = output + String.fromCharCode(chr2);
        }
        if (enc4 >= 0) {
            output = output + String.fromCharCode(chr3);
        }
    }
    return output;
}

求解flag

按照上文分析, 由于正向编码时会出现多对一的情况, 所以需要尝试列举出所有情况, 并一一提交测试:

ps: 起初我直接使用console.log(decode(decrypt("8&]Z:&)&=%$T+3%46PU:#1M544Q5$,]")));对编码字符进行逆向运算, 得到了一个解为flag{BAsE>4aBB64}, 但是提交时系统提示不正确. 遂去网上查找了相关WriteUp才想起来可能会有多个解存在

let input = "8&]Z:&)&=%$T+3%4,6PU:#1M544Q5$,]";
let buffer = [];
let res = [];
let len = input.length;
let _input = input.split("").map(ele => ele.charCodeAt());
let v2 = Number.parseInt(len / 4);
let v3 = len % 4;
let bufferLen = 3 * v2;
let enc1 = 0;
let enc2 = 0;
let enc3 = 0;
let enc4 = 0;
let t1 = 0;
let t2 = 0;

if (v3)
    bufferLen = 3 * v2 + 3;

buffer = new Array(3);
let v15 = bufferLen - 3;
let i = 0;
let j = 0;

if (v15 > 0) {
    for (i; i <= v15; i += 3) {
        enc1 = _input[j];
        if (j + 1 < len)
            enc2 = _input[j + 1];
        if (j + 2 < len)
            enc3 = _input[j + 2];
        if (j + 3 < len)
            enc4 = _input[j + 3];
        if (enc3 == 61 && j == len - 4) {
            enc3 = 32;
        }
        if (enc4 == 61 && j == len - 4) {
            enc4 = 32;
        }
        t1 = ((enc1 - 32) << 2);
        t2 = ((enc2 >> 4) & 0x3);
        buffer[0] = ((enc1 - 32) << 2) | ((enc2 >> 4) & 0x3);// 1和3不区分, 0和2不区分
        buffer[1] = ((enc2 & 0xf) << 4) | (((enc3 - 32) >> 2) & 0xf);
        buffer[2] = ((enc3 & 0x3) << 6) | ((enc4 - 32) & 0x3f);
        res.push(Array.from(buffer));
        if (t2 == 0) {
            buffer[0] = t1 | 2;
            res.push(Array.from(buffer));
        } else if (t2 == 1) {
            buffer[0] = t1 | 3;
            res.push(Array.from(buffer));
        } else if (t2 == 2) {
            buffer[0] = t1 | 0;
            res.push(Array.from(buffer));
        } else if (t2 == 3) {
            buffer[0] = t1 | 1;
            res.push(Array.from(buffer));
        }
        j += 4;
    }
}
res = res.map(e => e.map(ele => String.fromCharCode(ele)).join(""));
let output = "";
//毫无优雅可言的爆破
for (let i = 0; i < 2; i++) {
    for (let j = 2; j < 4; j++) {
        for (let k = 4; k < 6; k++) {
            for (let l = 6; l < 8; l++) {
                for (let m = 8; m < 10; m++) {
                    for (let n = 10; n < 12; n++) {
                        for (let o = 12; o < 14; o++) {
                            for (let p = 14; p < 16; p++) {
                                output = decode(res[i] + res[j] + res[k] + res[l] + res[m] + res[n] + res[o] + res[p]);
                                if (output.search(/flag\{.*\}/) >= 0) {
                                    console.log(output);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

/** 输出:
flag{BAsE>4aBB64}
flag{BAsE>4aBA¶4}
flag{BAsE>4_BB64}
flag{BAsE>4_BA¶4}
flag{BAsE64aBB64}
flag{BAsE64aBA¶4}
flag{BAsE64_BB64}
flag{BAsE64_BA¶4}
flag{BCE>4aBB64}
flag{BCE>4aBA¶4}
flag{BCE>4_BB64}
flag{BCE>4_BA¶4}
flag{BCE64aBB64}
flag{BCE64aBA¶4}
flag{BCE64_BB64}
flag{BCE64_BA¶4}
**/

得到flag{BAsE64_BB64}

参考链接: Base64_changed(一道比赛逆向题) | LiuLian (liul14n.top)