美国某高中生CTF竞赛的逆向分析题目
本帖最后由 疯如初 于 2020-10-31 04:52 编辑# picoCTF - 2020 - otp write-up
# 前言
picoCTF是美国CMU大学举办的面向高中生的CTF竞赛，应该算是初学者水平的题。前几天做了里面的一道题感觉出的挺好的，也不算很难，有点小坑但不多。
# 题目来源和下载
来源：https://play.picoctf.org/events/3/challenges/challenge/92
好像每个人的下载后的文件都会不一样
我的文件（otp 和 flag.txt）：
# 工具
IDA Pro
# 分析
## 查壳
无壳
## key 正确的条件
以下代码说明key必须要满足这两个条件：
- length () 等于 100
- s1 等于 s2 （"mngjlepdcbcmjmmjipmmegfkjbicaemoemkkpjgnhgomlknmoepmfbcoffikhplmadmganmlojndmfahbhaancamdhfdkiancdjf"）
In Disassembly,
.text:0000557E7FE4E99D cmp , 64h ; 'd'
.text:0000557E7FE4E9A4 jnz short loc_557E7FE4E9C6 ; if ( i == 100
.text:0000557E7FE4E9A4 ; line 35
.text:0000557E7FE4E9A6 mov eax, ; && !strncmp(
.text:0000557E7FE4E9A6 ; s1,
.text:0000557E7FE4E9A6 ; "mngjlepdcbcmjmmjipmmegfkjbicaemoemkkpjgnhgomlknmoepmfbcoffikhplmadmganmlojndmfahbhaancamdhfdkiancdjf",
.text:0000557E7FE4E9A6 ; 0x64uLL) )
.text:0000557E7FE4E9A6 ; line 36-39
.text:0000557E7FE4E9AC movsxdrdx, eax ; n = i =
.text:0000557E7FE4E9AF lea rax,
.text:0000557E7FE4E9B3 lea rsi, s2 ; "mngjlepdcbcmjmmjipmmegfkjbicaemoemkkpjg"...
.text:0000557E7FE4E9BA mov rdi, rax ; s1
.text:0000557E7FE4E9BD call _strncmp ; test if s1 equal s2
.text:0000557E7FE4E9C2 test eax, eax
.text:0000557E7FE4E9C4 jz short loc_557E7FE4E9D9 ; if i = 100 and s1 = s2，then key is correct
In Pseudocode,
if ( i == 100
&& !strncmp(
s1,
"mngjlepdcbcmjmmjipmmegfkjbicaemoemkkpjgnhgomlknmoepmfbcoffikhplmadmganmlojndmfahbhaancamdhfdkiancdjf",
0x64uLL) )
## 分析算法 (输入: dest; 输出: s1)
分析从 0000557E7FE4E89E 到 0000557E7FE4E99B 的汇编
In Disassembly,
.text:0000557E7FE4E89E ; ---------------------------------------------------------------------------
.text:0000557E7FE4E89E
.text:0000557E7FE4E89E loc_557E7FE4E89E: ; CODE XREF: main+14A↓j
.text:0000557E7FE4E89E cmp , 0 ; if ( i )
.text:0000557E7FE4E89E ; line 21
.text:0000557E7FE4E8A5 jnz short loc_557E7FE4E8E4
.text:0000557E7FE4E8A7 mov eax, ; when i equal 0
.text:0000557E7FE4E8A7 ; line 30
.text:0000557E7FE4E8AD cdqe
.text:0000557E7FE4E8AF movzx eax,
.text:0000557E7FE4E8B7 movsx eax, al
.text:0000557E7FE4E8BA mov edi, eax
.text:0000557E7FE4E8BC call jumble
.text:0000557E7FE4E8C1 mov edx, eax
.text:0000557E7FE4E8C3 mov eax, edx
.text:0000557E7FE4E8C5 sar al, 7
.text:0000557E7FE4E8C8 shr al, 4
.text:0000557E7FE4E8CB add edx, eax
.text:0000557E7FE4E8CD and edx, 0Fh
.text:0000557E7FE4E8D0 sub edx, eax
.text:0000557E7FE4E8D2 mov eax, edx
.text:0000557E7FE4E8D4 mov edx, eax
.text:0000557E7FE4E8D6 mov eax,
.text:0000557E7FE4E8DC cdqe
.text:0000557E7FE4E8DE mov , dl
.text:0000557E7FE4E8E2 jmp short loc_557E7FE4E935
.text:0000557E7FE4E8E4 ; ---------------------------------------------------------------------------
.text:0000557E7FE4E8E4
.text:0000557E7FE4E8E4 loc_557E7FE4E8E4: ; CODE XREF: main+97↑j
.text:0000557E7FE4E8E4 mov eax, ; when i not equal 0
.text:0000557E7FE4E8E4 ; line 23-26
.text:0000557E7FE4E8EA cdqe
.text:0000557E7FE4E8EC movzx eax,
.text:0000557E7FE4E8F4 movsx eax, al
.text:0000557E7FE4E8F7 mov edi, eax ; edi = dest
.text:0000557E7FE4E8F9 call jumble ; line 23
.text:0000557E7FE4E8FE movsx edx, al
.text:0000557E7FE4E901 mov eax,
.text:0000557E7FE4E907 sub eax, 1
.text:0000557E7FE4E90A cdqe
.text:0000557E7FE4E90C movzx eax,
.text:0000557E7FE4E911 movsx eax, al ; eax = s1
.text:0000557E7FE4E914 add edx, eax ; edx = v5
.text:0000557E7FE4E914 ; line 24
.text:0000557E7FE4E916 mov eax, edx
.text:0000557E7FE4E918 sar eax, 1Fh
.text:0000557E7FE4E91B shr eax, 1Ch ; line 25
.text:0000557E7FE4E91E add edx, eax
.text:0000557E7FE4E920 and edx, 0Fh
.text:0000557E7FE4E923 sub edx, eax ; line 26
.text:0000557E7FE4E925 mov eax, edx
.text:0000557E7FE4E927 mov edx, eax
.text:0000557E7FE4E929 mov eax,
.text:0000557E7FE4E92F cdqe
.text:0000557E7FE4E931 mov , dl ; = s1
.text:0000557E7FE4E935
.text:0000557E7FE4E935 loc_557E7FE4E935: ; CODE XREF: main+D4↑j
.text:0000557E7FE4E935 add , 1 ; ++i
.text:0000557E7FE4E93C
.text:0000557E7FE4E93C loc_557E7FE4E93C: ; CODE XREF: main+8B↑j
.text:0000557E7FE4E93C mov eax, ; for ( i = 0; (unsigned int)valid_char(dest); ++i )
.text:0000557E7FE4E93C ; line 19-32
.text:0000557E7FE4E942 cdqe
.text:0000557E7FE4E944 movzx eax,
.text:0000557E7FE4E94C movsx eax, al
.text:0000557E7FE4E94F mov edi, eax ; edi = dest
.text:0000557E7FE4E951 call valid_char ; valid_char(dest)
.text:0000557E7FE4E956 test eax, eax
.text:0000557E7FE4E958 jnz loc_557E7FE4E89E
.text:0000557E7FE4E95E mov , 0 ; j
.text:0000557E7FE4E968 jmp short loc_557E7FE4E98F
.text:0000557E7FE4E96A ; ---------------------------------------------------------------------------
.text:0000557E7FE4E96A
.text:0000557E7FE4E96A loc_557E7FE4E96A: ; CODE XREF: main+18D↓j
.text:0000557E7FE4E96A mov eax,
.text:0000557E7FE4E970 cdqe
.text:0000557E7FE4E972 movzx eax,
.text:0000557E7FE4E977 add eax, 61h ; 'a'
.text:0000557E7FE4E97A mov edx, eax
.text:0000557E7FE4E97C mov eax,
.text:0000557E7FE4E982 cdqe
.text:0000557E7FE4E984 mov , dl
.text:0000557E7FE4E988 add , 1
.text:0000557E7FE4E98F
.text:0000557E7FE4E98F loc_557E7FE4E98F: ; CODE XREF: main+15A↑j
.text:0000557E7FE4E98F mov eax, ; for ( j = 0; j < i; ++j )
.text:0000557E7FE4E98F ; line 33-34
.text:0000557E7FE4E995 cmp eax,
.text:0000557E7FE4E99B jl short loc_557E7FE4E96A
In Pseudocode,
for ( i = 0; (unsigned int)valid_char(dest); ++i )// test if dest is 1-9 or a-f
{
if ( i )
{
v4 = jumble(dest);
v5 = s1 + v4;
v6 = (unsigned int)((s1 + v4) >> 31) >> 28;
s1 = ((v6 + v5) & 0xF) - v6;
}
else
{
s1 = (char)jumble(dest) % 16;
}
}
for ( j = 0; j < i; ++j )
s1 += 97;
通过分析得知输入为dest，输出为s1
接下来就可以在制作逆向算法时直接把部分以上算法直接复制进去用于穷举了。
## 求 Key （关键部分）
写出Java代码：通过已知的s1（也就是s2）求出dest（正确的key）
#### 求 dest
s2 = "m" = 109
s1 = s2 - 97 = 12
输出所有可能的s1
寻找当s1等于12时，dest的值
public static void main(String[] args)
{
System.out.println("dest|s1");
int[] a1s = {48,49,50,51,52,53,54,55,56,57,97,98,99,100,101,102};
for(int i = 0; i < 16; i++)
{
System.out.println(a1s + "|" +jumble(a1s) % 16);
}
}
public static int jumble(int a1)
{
int v2 = a1;
if ( a1 > 96 ) // a-f
v2 = a1 + 9; // j-o
int v3 = 2 * (v2 % 16);
if ( (char)v3 > 15 )
++v3;
return v3;
}
Output:
dest|s1
48|0
49|2
50|4
51|6
52|8
53|10
54|12
55|14
56|1
57|3
97|5
98|7
99|9
100|11
101|13
102|15
结论：当 dest 等于 54 (char “6”), s1 等于 12.
#### Find dest
s2 = "n" = 110
输出所有可能的s1
寻找当s1等于110时，dest的值
public static void main(String[] args)
{
s1 = 12;
System.out.println("dest|s1");
int[] a1s = {48,49,50,51,52,53,54,55,56,57,97,98,99,100,101,102};
for(int i = 0; i < 16; i++)
{
getMS1IndexNotEqual0(a1s,1);
System.out.println(a1s + "|" +s1);
}
}
static int[] s1 = new int;
//find dest
//mD = dest
public static int getMS1IndexNotEqual0(int mD, int i)
{
if(i == 0)
{
return -1;
}
int v4 = jumble(mD);
int v5 = s1 + v4;
int v6 = (v5 >> 31) >>> 28;
s1 = ((v6 + v5) & 0xF) - v6;
s1 += 97;
return s1;
}
public static int jumble(int a1)
{
int v2 = a1;
if ( a1 > 96 ) // a-f
v2 = a1 + 9; // j-o
int v3 = 2 * (v2 % 16);
if ( (char)v3 > 15 )
++v3;
return v3;
}
Output:
dest|s1
48|109
49|111
50|97
51|99
52|101
53|103
54|105
55|107
56|110
57|112
97|98
98|100
99|102
100|104
101|106
102|108
结论：当 dest 等于 56 (char “8”), s1 等于 110.
#### 通过编程自动求 dest （dest - dest）
public static void auto()
{
s1 = 12;
String s2 = "mngjlepdcbcmjmmjipmmegfkjbicaemoemkkpjgnhgomlknmoepmfbcoffikhplmadmganmlojndmfahbhaancamdhfdkiancdjf";
char[] a1s = {48,49,50,51,52,53,54,55,56,57,97,98,99,100,101,102};
boolean hasResult = false;
for(int i2 = 1; i2 < 100; i2++)
{
hasResult = false;
for(int i = 0; i < 16; i++)
{
int s1Add97 = getMS1IndexNotEqual0(a1s,i2);
if(s2.charAt(i2) == (char)s1Add97)
{
hasResult = true;
System.out.print(a1s);
break;
}
}
if(hasResult == false)
System.out.println("NO");
}
}
static int[] s1 = new int;
//find dest
//mD = dest
public static int getMS1IndexNotEqual0(int mD, int i)
{
if(i == 0)
{
return -1;
}
int v4 = jumble(mD);
int v5 = s1 + v4;
int v6 = (v5 >> 31) >>> 28;
s1 = ((v6 + v5) & 0xF) - v6;
//s1 += 97;
return (s1+97);
}
Output:
8c91cd2ff85e90efbe041faf4b572413470a5eb5f47ff9f13dec686b091e46829c55eff9d23ccdb53c0ea76b277b74ea836
#### dest结论
第一字符是 "6",
所以完整的dest是 "68c91cd2ff85e90efbe041faf4b572413470a5eb5f47ff9f13dec686b091e46829c55eff9d23ccdb53c0ea76b277b74ea836"，也就是key
#### 测试 key
!
## 求最终 Flag
逆向得知key是 "68c91cd2ff85e90efbe041faf4b572413470a5eb5f47ff9f13dec686b091e46829c55eff9d23ccdb53c0ea76b277b74ea836"
flag.txt中的内容是 "18a07fbdbcd1af759895328ec4d82d2b411dc7876c34a0ab61eda8f2efa5bb0f198a3aa0ac47ff9a0cf3d913d3138678ce4b"
异或这两个值，得到 "7069636f4354467b63757374306d5f6a756d626c33735f3472336e745f345f67304f645f316433415f33336561643136667d"
将异或的结果 ("7069636f4354467b63757374306d5f6a756d626c33735f3472336e745f345f67304f645f316433415f33336561643136667d") 从十六进制转成ASCII, 得到 "picoCTF{cust0m_jumbl3s_4r3nt_4_g0Od_1d3A_33ead16f}", 也就是最终的Flag
#### java code
public static void main (String[] args) {
String str1 = "68c91cd2ff85e90efbe041faf4b572413470a5eb5f47ff9f13dec686b091e46829c55eff9d23ccdb53c0ea76b277b74ea836";
String str2 = "18a07fbdbcd1af759895328ec4d82d2b411dc7876c34a0ab61eda8f2efa5bb0f198a3aa0ac47ff9a0cf3d913d3138678ce4b";
String xorRes = doXor(str1,str2);
String flag = hexToString(xorRes);
}
public static String doXor(String str1, String str2)
{
String xorRes = StringXor(str1, str2);
System.out.println(xorRes);
return xorRes;
}
public static String StringXor(String str1, String str2) {
BigInteger big1 = new BigInteger(str1, 16);
BigInteger big2 = new BigInteger(str2, 16);
return big1.xor(big2).toString(16);
}
public static String hexToString(String hex)
{
byte[] s = DatatypeConverter.parseHexBinary(hex);
String ret = new String(s);
System.out.println(ret);
return ret;
}
Output:
7069636f4354467b63757374306d5f6a756d626c33735f3472336e745f345f67304f645f316433415f33336561643136667d
picoCTF{cust0m_jumbl3s_4r3nt_4_g0Od_1d3A_33ead16f}
: https://frc6.com/usr/uploads/2020/10/783240209.zip
: https://frc6.com/usr/uploads/2020/10/813829368.png
# 参考
这是英文版的wp，因为逆向的时候是随手拿英文写的记录。
https://frc6.com/index.php/archives/39/
剩余所有的write-up，还有一道sql注入，两道栈溢出：
https://github.com/frc123/CTF/tree/main/picoCTF/2020%20Mini%20Competition
https://frc6.com/index.php/tag/picoctf_2020mini/
会慢慢改成中文发出来的
### 同系列的write-up
OTP Implementation（逆向）：https://www.52pojie.cn/thread-1288992-1-1.html
Gussing Game 1（pwn-ROP）：https://www.52pojie.cn/thread-1294291-1-1.html
xixicoco 发表于 2020-10-22 16:28
@楼主，阅读密码是多少
20201111 “随手拿英文写的” asiafox 发表于 2020-10-24 11:27
楼主你确定这个是高中的题目？
确实是面向高中生的，这是他们的介绍
The largest cybersecurity hacking contest for middle and high school students has expanded to help learners of all experience levels.
但这个是挑战题 谢谢分享 谢谢分享！ 感谢分享 @楼主，阅读密码是多少 谢谢分享 虽然不懂。但是要支持。 牛逼牛逼，前来观摩！