avatar
Articles
58
Tags
5
Categories
8
Home
Archives
Tags
Categories
Link
About
List
L0x1c's Sky garden
Home
Archives
Tags
Categories
Link
About
List
xctf
|CTF
Word count:1.7k|Reading time: 8 min
|Post View:

image-20200309165739244

线性移位反馈寄存器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
do
{
    v5 = 0;
    v6 = 8i64;
    do
    {
        v7 = v4 & 0x17FA06;
        for (i = 0; v7; v7 >>= 1)
            i ^= v7 & 1;
        v4 = (i ^ 2 * v4) & 0x1FFFFF;
        v9 = v3 & 0x2A9A0D;
        for (j = 0; v9; v9 >>= 1)
            j ^= v9 & 1;
        v3 = (j ^ 2 * v3) & 0x3FFFFF;
        v11 = v2 & 0x5E5E6A;
        for (k = 0; v11; v11 >>= 1)
            k ^= v11 & 1;
        v2 = (k ^ 2 * v2) & 0x7FFFFF;
        v13 = 2 * v5;
        v14 = v3;
        if (v4 & 1)
            v14 = v2;
        v5 = v14 & 1 ^ v13;
        --v6;
    } while (v6);
    byte_140008980[v1++] = v5;
}
	while ( v1 < 0x100000 );

&同时为1才为1 >>==为右移/左移赋值，上面可以看出来先是三个lfsr，下面的把这个三个v4,v3,v2这三个输出组合了一下

img

这个一个线性移位反馈寄存器

img

他先进行了v7 = v4 & 0x17FA06; 0x17FA06 = b1 0111 1111 1010 0000 0110（21个bit）

然后有1的位置就是它的一个抽头 img

现在v4是这个lfsr移位前的状态，v7 = v4 & 0x17FA06 就是要看所有的抽头处的情况 我们假设v4＝ 0x123456 = b1 0010 0011 0100 0101 0110 进行异或后的结果就是：0b100100011000000000000 也就是v7 那么v7里面有1的地方就要进行一个异或img

有一个1，结果就是1 有两个1，结果就是0 有三个1，结果就是1 也就是，v10里面1的个数，决定着补上去的那一位是什么

img

v4，v3，v2分别对应三个lfsr这一次的输出

v14 = v3； if ( v4 & 1 ) v14 = v2;

来把这三个1bit的输出，组合成一个1bit的结果，然后把这1bit的结果要添加到v5这个字节上

那么3个lfsr的输出组合了一下:

1
2
3
4
r1 0 0 0 0 1 1 1 1
r2 0 0 1 1 0 0 1 1
r3 0 1 0 1 0 1 0 1
组合:0 0 1 1 0 1 0 1

可以看到r1一样的概率是0.5 r2，r3的概率是0.75 正常来说结果应该和rx的概率都是0.5才不会被区分出来，所以可以穷举所有的r2，把r2的输出，和它组合后的输出对比一下，看两者相同的概率，正常来说（如果r2和res不相关的话），这个概率应该是一个以50%为均值的正态分布，但是这边r2是跟res相关的，会有某个r2的概率在75%左右，所以只要找到在穷举的所有r2中，找到那个概率最大的，那肯定就是r2，r3也是一样的思路，r1的话，跟输出不相关，所以不能用这种方法，如果已经求出来r2,r3，可以穷举r1，然后跟r2,r3组合一下，看输出的结果跟那个output是否吻合，吻合的话，就是对的

文章：http://blog.leanote.com/post/xp0intjnu@gmail.com/66c91498d13b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h> 
#include <stdint.h> 
// #include <omp.h>
void lfsr(int init, int mask1, int mask2, uint8_t* seq, int len) 
{ 
	for (int j = 0; j < len; j++) 
	{ 
		uint8_t byte = 0;        
		uint8_t bit = 8;        
		do 
		{ 
			uint8_t output = 0;            
			int x = init & mask1;            
			while (x) { output ^= x & 1;                
			x >>= 1; 
			}            
			init = (output ^ (init << 1)) & mask2;            
			byte = (byte << 1) ^ output;            
			bit--; } while (bit);        
			seq[j] = byte; 
	} 
}
double correlation(uint8_t* A, uint8_t* B, int len) 
{ 
	int N = len * 8;    
	int d = 0;    
	for (int i = 0; i < len; i++) 
	{ 
		uint8_t bit = 8;        
		uint8_t a = A[i];        
		uint8_t b = B[i];        
		do 
		{ 
			if ((a & 1) == (b & 1))                
				d++;            
			a >>= 1;            
			b >>= 1;            
			bit--; 
		} 
		while (bit); 
	}    
	return (double)d / N; 
}
uint8_t mixed_output[] = { 95, 83, 107, 255, 209, 96, 188, 166, 230, 219, 223, 72, 150, 155, 169,    138, 126, 0, 91, 20, 19, 109, 82, 12, 249, 91, 39, 107, 104, 55, 207,    65, 155, 197, 204, 81, 76, 22, 83, 208, 215, 13, 254, 14, 43, 87, 29,    42, 161, 92, 2, 109, 110, 232, 201, 147, 19, 53, 216, 82, 144, 169,    34, 193, 106, 0, 253, 224, 7, 46, 24, 16, 226, 127, 164, 162, 54, 98,    144, 141, 182, 174, 252, 64, 130, 19, 163, 242, 176, 78, 79, 3, 19, 11,    160, 121, 149, 44, 53, 17, }; // 100
void guess2() 
{
	int len = 100;    
	uint8_t seq[100] = {};
	int possible_r2 = 0;    
	double max_p = 0.0;        
	int r2; // #pragma omp parallel for    
	for (r2 = 0; r2 < (1<<22); r2++) 
	{       
		lfsr(r2, 0x2A9A0D, 0x3FFFFF, seq, 100);               
	double corr = correlation(seq, mixed_output, len);        
	if (corr > max_p) 
	{            
		possible_r2 = r2;            
		max_p = corr;        
	}    
	}    
	printf("%d %f", possible_r2, max_p); // 3324079 
}
	void guess3() {
		int len = 100;    
		uint8_t seq[100] = {};
		int possible_r3 = 0;    
		double max_p = 0.0;        
		int r3; // #pragma omp parallel for    
		for (r3 = 0; r3 < (1<<23); r3++) 
		{        
			lfsr(r3, 0x5E5E6A, 0x7FFFFF, seq, 100);
		double corr = correlation(seq, mixed_output, len);        
		if (corr > max_p) 
		{ 
			possible_r3 = r3;            
			max_p = corr; 
		}
	}   
	printf("%d %f", possible_r3, max_p); // 4958299 
}
	void brute_force() {
		uint8_t seq_r1[100] = {};    
		uint8_t seq_r2[100] = {};    
		uint8_t seq_r3[100] = {};
		int r2 = 3324079;    
		int r3 = 4958299;        
		lfsr(r2, 0x2A9A0D, 0x3FFFFF, seq_r2, 100);    
		lfsr(r3, 0x5E5E6A, 0x7FFFFF, seq_r3, 100);        
		for (int r1 = 1427994; r1 < (1 << 21); r1++) {
			lfsr(r1, 0x17FA06, 0x1FFFFF, seq_r1, 100);            
			for (int i = 0; i < 100; i++) 
			{
				int byte = 0;                
				for (int bit = 7; bit >= 0; bit--) {
					int x1 = (seq_r1[i] >> bit) & 1;
					int x2 = (seq_r2[i] >> bit) & 1;                
					int x3 = (seq_r3[i] >> bit) & 1;                
					byte = (byte << 1) ^ ((x1 * x3) ^ ((x1 ^ 1) * x2));
				}
				if (byte != mixed_output[i]) break;            
				if (i == 99) printf("%d", r1);  // 1427994        
			}    
		} 
	}
				int main() {    
					guess2();    
					guess3();    
					brute_force();
					int r1 = 1427994;    
					int r2 = 3324079;    
					int r3 = 4958299;    
					printf("flag{%x%x%x}", r1, r2, r3); // flag{15ca1a32b8af4ba85b}
				}

cycle graph

大概看了说明，根据学过的数据结构不难分析这是一个链式存储结构, 那么我们用od进行载入

image-20200307215237773

这里可以看出判断长度

image-20200307215303513

将eax记录到flag{}中的第一位,继续

image-20200307215321069

第二轮是esi的记录，依次即可，遍历路径

天津垓

缺少cygwin1.dll,直接去找了，放到同一个文件下，IDA 直接爆破出第一个结果

image-20200307215421014

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
#include<windows.h>
#include<iostream>
using namespcae std;
int main()
{
    str key = "Rising_Hopper!";
    int ShuJu[] = { 17,8,6,10,15,20,42,59,47,3,47,4,16,72,62,0,7,16 };
    for (int i = 0; i <= 17;i++)
    {
        for (int j = 0x20; j <= 0x7e; j++)
        {
        if ((~(j & key[i % 14]) & (j | key[i % 14])) == arr[i])
        {  
            printf("%c", j);
        }
      }
  }
  return 0;
  system("pause");
} //Caucasus@s_ability

得到数据， Caucasus@s_ability ，直接用x64dbg dump数据，使用插件Scylla

image-20200307215456517

v27数据为v78 v1为输入 v0为输入长度， v79给了

image-20200307215512644

上面的数据挨个除以19683，就是flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<stdio.h>
#include<windows.h>
int main()
{
	int n = 0;
	char key[] = "Rising_Hopper!";
	int arr[] = { 0x1ea272,0x206fc4,0x1d2203,0x1eef55,0x24f111,0x193a7c,0x1f3c38,0x21566d,0x2323bf,0x2289f9,0x1d2203,0x21098a,0x1e08ac,0x223d16,0x1f891b,0x2370a2,0x1e558f,0x223d16,0x1c883d,0x1f891b,0x2289f9,0x1c883d,0xeb773,0xe6a90,0xe6a90,0xe6a90,0xb1ccf,0x1c883d,0x2289f9,0x22d6dc,0x223d16,0x21566d,0x21098a,0x1eef55,0x1e558f,0x223d16,0x1c883d,0x22d6dc,0x1f3c38,0x1d2203,0x21098a,0x1c883d,0x24a42e,0x1e558f,0x223d16,0x21566d,0xd83e7,0x21566d,0x21098a,0x1e558f,0x258ad7 };
	for (int i = 0; i <= 50;i++)
	{
		for (int j = 0x20; j <= 0x7e; j++)
		{
			if (0x4ce3 *j% (unsigned int)0x8000000B == arr[i])
			{
				printf("%c",j);
				n++;
			}
		}

		
	}
	printf("\n%d", n);
	system("pause");

}

fxck！

一个base58加上brainfuck下断点这里可以看到是base58，看一下未被进行加密运算后的内存的密码表，可以看到base58的替换表

image-20200309013146351

可以看到密码表：ABCDEFGHJKLMNPQRSTUVWXYZ123456789abcdefghijkmnopqrstuvwxyzbrainfuck不太了解，直接跑了下由于下面有一个cmp的函数位置，直接看了

image-20200309103025376

image-20200309103037493

直接找到s1的地址对应edi的 转过去

image-20200309103055996

进行解密 替换好密码表然后base58即可

Author: L0x1c
Link: https://l0x1c.github.io/2020/04/26/2020-3-25/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
CTF-RE
Donate
  • 微信
    微信
  • 支付寶
    支付寶
Recommend
2020-04-27
RE加密算法
2020-04-26
GO逆向
2020-04-26
公益赛
2020-04-26
Flare-ON
2020-04-26
PE
2020-04-26
VN招新赛
简