一个有趣的加密小算法及其逆向

七夕特别节目~

前两天在强网杯的逆向safe_m2m中无意中发现了这么一段代码：

关键代码是：

1	v5 ^= ((v5 ^ (unsigned int)(32 * v5)) >> 17) ^ (32 * v5) ^ ((((v5 ^ (unsigned int)(32 * v5)) >> 17) ^ v5 ^ (32 * v5)) << 13);

整理一下：

1	c = p ^ (p << 5) ^ ((p ^ (p << 5)) >> 17) ^ ((((p ^ (p << 5)) >> 17) ^ p ^ (p << 5)) << 13);

已知c，求p。且由于运算量过大（循环100016次），不可爆破。

乍一看无从下手，这怎么逆向啊？

观察了一会，发现可以进行变量代换。

设x = p ^ (p << 5)，有：

1	c = x ^ (x >> 17) ^ (((x >> 17) ^ x) << 13);

继续设y = x ^ (x >> 17)，有：

1	c = y ^ (y << 13);

综上，有如下的关系：

1
2
3

x = p ^ (p << 5)
y =  x ^ (x >> 17)
c = y ^ (y << 13)

这样，算式变得简单多了。

但是，对于这种类型的等式，假设已知x（int），应该如何求p（int）呢？

其实很简单，如果这个变量不是一个int，而是一个数组，我感觉很容易想到解法，但是这样的形式不太容易想。

答案是以bit为一个单位进行运算。

对于低5位bit：

由于p << 5的低5位bit均为0，所以 p ^ (p << 5)的低5位bit的值就是p低5位bit的值。可以写作p[i] = x[i]

对于x的高27位（32-5）bit：

有x[i] = p[i] ^ p[i - 5]，即p[i] = x[i] ^ p[i - 5]。x是已知的，同时由于上一步知道了p[0]~p[4]的值，所以p[i - 5]也是可以逐步求出的。

以上便是左移形式的算式的求解，右移形式的求解与之类似，不在赘述。

可能大佬们觉得很简单，但这是我第一次接触这种以bit为基本单位进行依次求解的算式，会有种比较新奇的感觉。

顺便今天七夕闲得没事干，于是写了点相关的加解密代码。

前面的示例中嵌套了3次，实际上可以嵌套无数次（效率另说），以增强逆向的难度。

我感觉嵌套了3次的还勉强能看出可以进行变量代换，但是如果嵌套了七八次，甚至更多次数，就很难进行分析了。下面的代码是嵌套了8次的：

1
2
3

unsigned int encrypt1(unsigned int p){
        return ((((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) ^ ((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) >> 21)) ^ (((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) ^ ((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) >> 21)) >> 18)) ^ ((((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) ^ ((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) >> 21)) ^ (((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) ^ ((((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) ^ (((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) ^ ((((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) ^ (((p ^ (p >> 30)) ^ ((p ^ (p >> 30)) << 13)) << 30)) << 9)) >> 29)) >> 21)) >> 18)) << 16));
}

上面的这个代码扔进ida里，如果没有事先了解这个形式的算式，要是很容易逆出来，那您绝对是大佬~

当然我知道古典密码加解密毫无安全性可言，同时这个算法的效率也不高（也或许是我的代码优化得不够到位？？），根本毫无用武之地。不过，当个简单一点的CTF题或许不错？

菜鸟七夕闲得慌，就随手一写，希望大佬们可以轻喷~~

下面是代码，共三个文件。前两个是算法，最后一个是函数生成器，如果你希望加大难度，可以使用第三个脚本生成相应的encrypt1()和decrypt()，不过嵌套次数也别太大了，我测试过嵌套次数为15的，可以正常运行，比这个数字更大的没测试，不过问题应该不大，顶多效率很差就是了。

QiXi-algorithm.c

首先是核心算法，对一个unsigned int加密后解密。

/**************************************************************************
 * Title:	A very interesting little encryption algorithm and its reverse
 * Author: 	iyzyi
 * WebSite: http://iyzyi.com 
 * Date:   	25 Aug 2020 (七夕快乐)
 **************************************************************************/

#include <stdio.h>
#include <math.h>

unsigned int encrypt1(unsigned int p){
	//下列算式出自2020强网杯逆向safe_m2m，只修改了变量名，其余均未改动。 
	return ((p ^ (unsigned int)(32 * p)) >> 17) ^ (32 * p) ^ ((((p ^ (unsigned int)(32 * p)) >> 17) ^ p ^ (32 * p)) << 13) ^ p;
}

unsigned int encrypt2(unsigned int p){
	//为了便于理解，这里给出等价形式，但是加密的时候不要选用此函数
	unsigned int x = p ^ (p << 5);
	unsigned int y = x ^ (x >> 17);
	unsigned int c = y ^ (y << 13);
	return c;
}

unsigned int getAnsOfPowerOfTwo(int a, int b){
	//求2的幂的和
	unsigned int ans = 0;
	int i;
	for (i = a; i < b; i++){
		ans += pow(2, i);
	}
	return ans;
}

unsigned int getBit(const unsigned int n, int i){
	//取某一位的bit 
	unsigned int t =  pow(2, i);
	return (t & n) >> i;
}

unsigned int rightShiftXor(const unsigned int n, int m){
	unsigned int r = n & getAnsOfPowerOfTwo(0, 32 - m);
	unsigned int l = n & getAnsOfPowerOfTwo(32 - m, 32);
	unsigned int t = l;
	int i, t_i;
	for (i = 31 - m; i >= 0; i--){
		t_i = getBit(t, i + m) ^ getBit(n, i);
		t += t_i << i;
	}
	return t;
}

unsigned int leftShiftXor(const unsigned int n, int m){
	unsigned int r = n & getAnsOfPowerOfTwo(0, m);
	unsigned int l = n & getAnsOfPowerOfTwo(m, 32);
	unsigned int t = r;
	int i, t_i;
	for (i = m; i < 32; i++){
		t_i = getBit(t, i - m) ^ getBit(n, i);
		t += t_i << i;
	}
	return t;
}

unsigned int decrypt(c){
	unsigned int y = leftShiftXor(c, 13);
	unsigned int x = rightShiftXor(y, 17);
	unsigned int p = leftShiftXor(x, 5);
	return p;
}

int main(){
	unsigned int p0 = 0xfedcba98;
	
	unsigned int c1 = encrypt1(p0);
	printf("encrypt1(0x%x) = 0x%x\n", p0, c1);
	unsigned int c2 = encrypt2(p0);
	printf("encrypt2(0x%x) = 0x%x\n", p0, c2);
	
	unsigned int c = c1;
	unsigned int p = decrypt(c);
	printf("\ndecrypt(0x%x) = 0x%x\n", c, p); 
	
	if (c1 == c2 && p0 == p){
		printf("\nTRUE");
	}
	return 0;
}

QiXi-file.c

然后是对文件进行加解密的代码：

/**************************************************************************
 * Title:	A very interesting little encryption algorithm and its reverse
 * Author: 	iyzyi
 * WebSite: http://iyzyi.com 
 * Date:   	25 Aug 2020 (七夕快乐)
 **************************************************************************/

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdint.h> 

unsigned int encrypt1(unsigned int p){
	//下列算式出自2020强网杯逆向safe_m2m，这里只修改了变量名，其余均未改动。 
	return ((p ^ (unsigned int)(32 * p)) >> 17) ^ (32 * p) ^ ((((p ^ (unsigned int)(32 * p)) >> 17) ^ p ^ (32 * p)) << 13) ^ p;
}

unsigned int encrypt2(unsigned int p){
	//为了便于理解，这里给出等价形式，但是加密的时候不要选用此函数
	unsigned int x = p ^ (p << 5);
	unsigned int y = x ^ (x >> 17);
	unsigned int c = y ^ (y << 13);
	return c;
}

unsigned int getAnsOfPowerOfTwo(int a, int b){
	//求2的幂的和
	unsigned int ans = 0;
	int i;
	for (i = a; i < b; i++){
		ans += pow(2, i);
	}
	return ans;
}

unsigned int getBit(const unsigned int n, int i){
	//取某一位的bit 
	unsigned int t =  pow(2, i);
	return (t & n) >> i;
}

unsigned int rightShiftXor(const unsigned int n, int m){
	unsigned int r = n & getAnsOfPowerOfTwo(0, 32 - m);
	unsigned int l = n & getAnsOfPowerOfTwo(32 - m, 32);
	unsigned int t = l;
	int i, t_i;
	for (i = 31 - m; i >= 0; i--){
		t_i = getBit(t, i + m) ^ getBit(n, i);
		t += t_i << i;
	}
	return t;
}

unsigned int leftShiftXor(const unsigned int n, int m){
	unsigned int r = n & getAnsOfPowerOfTwo(0, m);
	unsigned int l = n & getAnsOfPowerOfTwo(m, 32);
	unsigned int t = r;
	int i, t_i;
	for (i = m; i < 32; i++){
		t_i = getBit(t, i - m) ^ getBit(n, i);
		t += t_i << i;
	}
	return t;
}

unsigned int decrypt(unsigned int c){
	unsigned int y = leftShiftXor(c, 13);
	unsigned int x = rightShiftXor(y, 17);
	unsigned int p = leftShiftXor(x, 5);
	return p;
}

int encryptFile(char *sourceFile){
	char targetFile[256];
	strcpy (targetFile, sourceFile);
	strcat (targetFile, ".encrypt");

	FILE *fpSource, *fpTarget;
	fpSource = fopen(sourceFile, "rb");
	fpTarget = fopen(targetFile, "w+b");
	if(fpSource==NULL){
        printf("文件[%s]打开失败\n", sourceFile);
        return 0;
    }
    if(fpTarget==NULL){
        printf("文件[%s]创建/打开失败\n", targetFile);
        return 0;
    }
    
	unsigned int data[2] = {0, 0}, readCount = 0, num = 0;
	uint8_t temp[2];
	while ((readCount = fread(temp, 1, 1, fpSource)) > 0){
		data[0] += temp[0] << 8 * num;
		num ++;
		if (num == 4){
			data[0] = encrypt1(data[0]);
			fwrite(data, 4, 1, fpTarget);

			num = 0;
			data[0] = 0;
		}
	}
	if (num != 0){
		data[0] = encrypt1(data[0]);
		fwrite(data, 4, 1, fpTarget);
	}
	fclose(fpSource);
	fclose(fpTarget);
}

int decryptFile(char *sourceFile){
	char targetFile[256];
	strcpy (targetFile, sourceFile);
	strcat (targetFile, ".decrypt");

	FILE *fpSource, *fpTarget;
	fpSource = fopen(sourceFile, "rb");
	fpTarget = fopen(targetFile, "w+b");
	if(fpSource == NULL){
        printf("文件[%s]打开失败\n", sourceFile);
        return 0;
    }
    if(fpTarget == NULL){
        printf("文件[%s]创建/打开失败\n", targetFile);
        return 0;
    }
    
	unsigned int data[2] = {0, 0}, temp[2] = {0, 0}, readCount = 0, num = 0;
	while ((readCount = fread(temp, 1, 1, fpSource)) > 0){
		data[0] += temp[0] << 8 * num;
		num ++;
		if (num == 4){
			data[0] = decrypt(data[0]);
			fwrite(data, 4, 1, fpTarget);

			num = 0;
			data[0] = 0;
		}
	}
	if (num != 0){
		data[0] = decrypt(data[0]);
		fwrite(data, 4, 1, fpTarget);
	} 
	fclose(fpSource);
	fclose(fpTarget);
}

int main(int argc, char *argv[]){
	//解密后与加密前的文件的md5可能不同,是因为最后4个字节可能有多余的填充字节0x00. 
	char plain[] = "D:\\桌面\\Seer-master.zip";
	encryptFile(plain);
	
	char cipher[] = "D:\\桌面\\Seer-master.zip.encrypt";
	decryptFile(cipher);
		
	return 0;
}

QiXi-builder.py

最后是一个生成加解密函数的python脚本，可以控制嵌套次数：

'''
 * Title:	A very interesting little encryption algorithm and its reverse
 * Author: 	iyzyi
 * WebSite: 	http://iyzyi.com 
 * Date:   	25 Aug 2020 (七夕快乐)
 * Usage:   将QiXi-file或QiXi-algorithm中的encrypt1()、decrypt()替换成本程序生成的encrypt1()、decrypt()
'''

import random

class QiXi_builder:

    def __init__(self, num):
        self.num = num
        self.shift_symbol= []
        self.shift_param = []

        shift = ['<<', '>>']
        for i in range(self.num):
            fn = random.randint(0, 1)
            self.shift_symbol.append(shift[fn])

            n = random.randint(0+1, 31-1)
            self.shift_param.append(n)

        self.encyrpt1_builder()
        self.encrypt2_builder()
        self.decrypt_builder()



    def encyrpt1_builder(self):
        encyrpt1 = []
        for i in range(self.num):
            if i == 0:
                t = '(p ^ (p {} {}))'.format(self.shift_symbol[i], self.shift_param[i])
                encyrpt1.append(t)
            else:
                t = '({} ^ ({} {} {}))'.format(encyrpt1[i-1], encyrpt1[i-1], self.shift_symbol[i], self.shift_param[i])
                encyrpt1.append(t)

        template1 = '''unsigned int encrypt1(unsigned int p){
	return %s;
}''' % encyrpt1[self.num - 1]

        print(template1)
        return template1



    def encrypt2_builder(self):
        # 为了便于理解encrypt1，所以也生成这个等价的函数。但是加密的时候最好不要选用此函数。
        encrypt2 = ''
        for i in range(self.num):
            if i == 0:
                t = '	unsigned int t{} = p ^ (p {} {});\n'.format(i+1, self.shift_symbol[i], self.shift_param[i])
            elif i == self.num - 1:
                t = '	unsigned int c = t{} ^ (t{} {} {});\n'.format(i, i, self.shift_symbol[i], self.shift_param[i])
            else:
                t = '	unsigned int t{} = t{} ^ (t{} {} {});\n'.format(i+1, i, i, self.shift_symbol[i], self.shift_param[i])
            encrypt2 += t
        
        template2 = '''unsigned int encrypt2(unsigned int p){
%s	return c;
}''' % encrypt2

        print(template2)
        return template2



    def decrypt_builder(self):
        decrypt = ''
        for i in range(self.num-1, -1, -1):
            symbol = 'left' if self.shift_symbol[i] == '<<' else 'right'
            if i == 0:
                t = '	unsigned int p = {}ShiftXor(t{}, {});\n'.format(symbol, i+1, self.shift_param[i])
            elif i == self.num - 1:
                t = '	unsigned int t{} = {}ShiftXor(c, {});\n'.format(i, symbol, self.shift_param[i])
            else:
                t = '	unsigned int t{} = {}ShiftXor(t{}, {});\n'.format(i, symbol, i+1, self.shift_param[i])
            decrypt += t

        template3 = '''unsigned int decrypt(unsigned int c){
%s	return p;
}''' % decrypt

        print(template3)
        return template3



QiXi_builder(8)        #参数为嵌套次数

写的有些赶（想赶在七夕结束之前），没有过多检查。如果本文有谬误，劳请大佬们斧正~~