XOR加密算法研究

0x00 简介

很久前从同学那里拿到了一个没见过的”密码题”,其实更像是RE题目,也不知道是哪个CTF的题目了。只不过RE都是调试,这个是给定了一个C代码,一个原文,两个密文。

其中密文之一是给定明文加密的结果。另一个需要你解开,即FLAG文件。

最终完成后FLAG文件内容是该题目的简介。这种题目叫做”已知明文攻击(known-plaintext attack,KPA)”

FLAG文件内容如下:

The known-plaintext attack (KPA) is an attack model for cryptanalysis where the attacker has samples of both the plaintext (called a crib), and its encrypted version (ciphertext). These can be used to reveal further secret information such as secret keys and code books. The term “crib” originated at Bletchley Park, the British World War II decryption operation. The flag is CTF{6d5eba48508efb13dc87220879306619}

翻译如下:

已知明文攻击(KPA)是一种用于密码分析的攻击模型,在攻击者同时拥有明文(称为crib)和它对应的加密版本(密文)的样本时使用。这种手段可以用来揭示更深层次的信息,比如秘钥和密码本。术语”crib”起源于Bletchley Park,是二战时期英国的一种解密方式。 Flag是CTF{6d5eba48508efb13dc87220879306619}

FLAG文件内的介绍已经很全面了。

0x01 样本

给定的加密程序是这样的:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {
    if (argc != 3) {
        printf("USAGE: %s INPUT OUTPUT\n", argv[0]);
        return 0;
    }
    FILE* input  = fopen(argv[1], "rb");
    FILE* output = fopen(argv[2], "wb");
    if (!input || !output) {
        printf("Error\n");
        return 0;
    }
    char k[] = "xxx";
    char c, p, t = 0;
    int i = 0;
    while ((p = fgetc(input)) != EOF) {
        c = (p + (k[i % strlen(k)] ^ t) + i*i) & 0xff;
        t = p;
        i++;
        fputc(c, output);
    }
    return 0;
}

程序编译完后使用命令参数输入明文和密文的名称。15行之前都是文件操作。先检查参数是否输入全,然后打开明文,创建密文文件。明文流为input,密文流是output。之后就是算法部分了。

while ((p = fgetc(input)) != EOF) {
    c = (p + (k[i % strlen(k)] ^ t) + i*i) & 0xff;
    t = p;
    i++;
    fputc(c, output);
}

算法也很简单。每次get一个字符,然后进行一堆运算,最后用&0xFF截断,保持结果也是一个字符长度。比较有趣的是这堆运算中会使用上一个字符当做salt之类的东西。这么做的话修改明文一个字符会影响密文2个字符(被修改字符和它之后的字符)。

salt会应用到一个字符串上,也就是key了。每次按顺序取出key的一个字符,然后key^salt,得到结果后加在原字符上,再加上i*i就结束了。

但是key程序并未给出,所以第一步就是分析出key值。

0x02 Key的分析

key的应用在这句上:

c = (p + (k[i % strlen(k)] ^ t) + i*i) & 0xff;

//c=结果;p=明文;k[]即key;t为上一个p;i为计数器

有个有趣的问题:明文一共29字节长。i*i简单算算早超过三位数,也就是一定会有被&0xff截断的部分。要是直接把C减掉i*i的话字符溢出,GG。

不过嘛,很简单,我们这么算:

(c + 0xFF - i*i) & 0xFF

原理很简单,虽然不知道进位了多少(百位数字是几)但是是几不重要,有就行,i*i超过100就向前借位即可,算完了再截断。恩…仔细想想就明白了。

c,p,t,i,我们都知道(t初始为0)。按四则运算法则即可得到对应的key了。

不过有一点需要记录下。

0x03 位运算逆推

XOR(异或,即C语言的^运算符)的逆运算是什么?

我们来看看:

     1 1 0 0 0 1 0 1 <--input
XOR  0 1 0 1 1 1 0 0 <--key
______________________________
     0 1 1 0 0 1 1 0 <--output

其实很容易就看出来了:input XOR key = output XOR key

即XOR的逆运算也是XOR。很讲道理嘛(虽然+和-,*和/互为逆运算)。

这里只是记录下XOR而已。我想说的是AND和OR的问题:

  1. AND和OR可以逆推么:不可以

    动手算算就知道了

  2. 那为什么算法不用AND和OR呢?用XOR不是会被逆推么?

    为什么不呢?要是动手算了AND和OR的话,就会发现不能逆推是因为一个有时(其实是几乎)一个output会对应多个input,这不仅会导致无法逆推,更会导致多个input算完得到同一结果。而我们应用算法的要求应该是输入输出一一对应才对。这样的话,除了特殊使用AND和OR(比如用AND和OR将0x6E转换为0xE6),一般不会普遍的在算法里应用AND和OR了吧。

0x04 GetKey

直接贴代码就行了吧。

enc = [0x9E,0x97,0x40,0x81,0xD0,0xBC,0x93,0xB2,0x98,0xFF,0xE7,0xC3,0x4E,0x31,0x69,0x5F,0x35,0xE1,0xE3,0xDC,0x09,0xEA,0xA3,0xA0,0xC3,0xFA,0x05,0x52,0xA6,0x53]
msg = [0x48,0x69,0x21,0x20,0x54,0x68,0x69,0x73,0x20,0x69,0x73,0x20,0x6F,0x6E,0x6C,0x79,0x20,0x74,0x65,0x73,0x74,0x20,0x6D,0x65,0x73,0x73,0x61,0x67,0x65,0x0A]
salt = [0x00] + msg

end = [None] * 29

for i in range(29):
    end[i]=( 0xff & (enc[i] + 0xff00 - i*i - msg[i]) ) ^ salt[i]

for x in end:
    print "%c" % x

#Result:
#VeryLongKeyYouWillNeverGuess

把key填入代码中,编译,输入给的明文,得到了一样的密文。

0x05 解密FLAG文件

先写出解密程序:

PS:其实是我不会python文件操作才写的C…

#include "stdio.h"
#include "string.h"
#include "stdlib.h"

int main(int argc, char const *argv[])
{
    if (argc != 3) {
        printf("USAGE: %s INPUT OUTPUT\n", argv[0]);
        return 0;
    }
    FILE* input  = fopen(argv[1], "rb");
    FILE* output = fopen(argv[2], "wb");
    if (!input || !output) {
        printf("Error\n");
        return 0;
    }

    char key[]="VeryLongKeyYouWillNeverGuess";
    char p,c,t=0;
    int i=0;
    while((p=fgetc(input)) != EOF){
        c = 0xff & (p + 0xff00 - i*i - (key[i%strlen(key)]^t) );
        t = c;
        ++i;
        fputc(c,output);
        //printf("%c",c);
    }
    return 0;
}

FLAG文件内容是介绍和FALG,在开头就贴上了。

0x06 总结

之前一直是爆破RE的算法,但是这次看这个key的长度明显爆破无力。首次尝试逆算法,以后可以尝试逆推RE算法了吧:)

收获的要素:

  1. P & 0xFF用于保持长度,可用P + 0xFF00做逆运算。(P为字符)
  2. XOR的逆运算仍然是XOR
  3. AND和OR无法逆推,但是一般也不用于算法。算法中的AND和OR一般都是用于特殊操作(比如第一条的操作)

–END–

Table of Contents