前言

这次来了解下Tea的改进版，xTea和xxTea

xTea

原理图：

来自wiki的介绍

翻译过来就是：

在密码学中，XTEA（扩展TEA）是一种用于纠正TEA弱点的分组密码。该密码的设计师是大卫·惠勒和罗杰·尼达姆的的剑桥大学计算机实验室，该算法在未公开的技术报告，1997年（李约瑟和惠勒，1997）提出的。它不受任何专利的约束。[1]

与TEA一样，XTEA是一个64位块 Feistel密码，具有128位密钥和建议的64轮。与TEA的一些差异是显而易见的，包括更复杂的关键时间表以及轮班，异或和补充的重新安排。

C代码如下：

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

说了那么多，反正我对密码学的东西一窍不通，只知道和Tea存在不同就是了，所以。盘它就完事了！

从代码上可以看到和tea相比多了一个参数num_rounds，以及计算的方式发生了变化，其实我感觉和tea差不多,都是左移4位，右移5位。

v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
sum += delta;
v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);

解题

题目代码都差不多，放在文末

我们直接开始盘它，在进encrypt之前看一下参数

rsi

rdi

注意到参数有三，跟进、下断，运行，循环。

循环位置如下：

这次循环的位置就不是非常容易观察出来。

可以看到主要的操作，多了一些有意思的东西。

<<4
>>5
xor 3
<<4
>>5
>>11
xor 3

一轮循环之后，通过观察比对数据，可以总结出以下特征：

1. 一个特征量0x9E3779B9
2. key 128 bit
3. enc 64 bit
4. 一个num_round控制循环次数
5. 4，5，11，3特征操作值

解题脚本在文末

xxTea

原理图：

具体介绍参考Wiki

字有点多懒的复制了

C代码如下：

#include <stdint.h>
  #define DELTA 0x9e3779b9
  #define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))

  void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
      rounds = 6 + 52/n;
      sum = 0;
      z = v[n-1];
      do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
          y = v[p+1]; 
          z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
      } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
      n = -n;
      rounds = 6 + 52/n;
      sum = rounds*DELTA;
      y = v[0];
      do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
          z = v[p-1];
          y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
      } while (--rounds);
    }
  }

将n个字编码或解码为单个块，其中n > 1
一些参数含义如下：

1. v是n字数据向量
2. k是4字密钥
3. n是v长度的绝对值 大于0为编码 解码时取反
4. 如果n为零，则结果为1，不进行编码或解码，否则结果为零
   假定32位“长”和相同的字节序编码和解码

xxTea的加解密是通过参数来进行控制的，因此看代码时只需要关注其一半即可

解题

基础的不说了直接跟进cyrpt部分

先是n和1进行比较

rounds = 6 + 52/n;
根据n算出rounds，其中的mov ecx 34h和add ecx 6都很明显

右移2位并且异或3

在汇编里看起来很明显，咱们F5试一下？

顿时一愣！还是看汇编清楚。

继续往下，可以看到和tea&xtea算法类似的操作：

>>5
<<2
>>3
<<4
xor 3

其中有两层循环一个是rounds次，一个是n-1次
所以总结特征如下：

1. key 128 bit
2. enc => 32*i(i=>2)
3. 特征量`0x9e3779b9`
4. 两层循环，通常记住最外层的循环为rounds=6+52/n
5. 5，2，3，4左右移操作

注意一点xxTea的加密数据最少是64位，长度是可以任意的（32*i）。

总结

Tea&xTea&xxTea

这次学完了这个系列的算法，来总结一下，不要弄混淆了。

相同点：

1. key 128 bit（当然还有很多算法的key=128bit）
2. 特征量0x9e3779b9
3. 主要加密部分进行移位和异或操作

首先如果题目中出现常量0x9e3779b9，那么肯定是Tea相关算法了。

区分：

1. Tea的主加密部分为<<4,>>5,xor，循环32轮
2. xTea的主加密部分<<4,>>5,>>11,xor,循环次数不定，但通常也为32轮，需要传入3个参数
3. xxTea的主加密部分>>5,<<2,>>3,<<4,xor,循环次数为6+52/n，enc长度大于64

我想拿这三者结合起来，魔改一下，出个题，看看自己到底掌握了没有。

腾讯的加密算法是16轮的Tea算法 参考

题目代码和解题代码

说明：在上一篇的解题脚本中出现了一点错误，现修正如下，其实是格式化输出的问题。

printf("flag{%x-%x}\n",flagLong[0],flagLong[1]);

修改为

printf("flag{%X-%.08X}\n",flagLong[0],flagLong[1]);

xTea题目：

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

/* take 64 bits of data in v[0] and v[1] and 128 bits of key[0] - key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}


int getStr(char *buffer,int maxLen){
    char c;  // 读取到的一个字符
    int len = 0;  // 当前输入的字符串的长度
    // 一次读取一个字符，保存到buffer
    // 直到遇到换行符(\n)，或者长度超过maxLen时，停止读取
    while( (c=getchar()) != '\n' ){
        buffer[len++]=c;  // 将读取到的字符保存到buffer
        if(len>=maxLen){
            break;
        }
    }
    buffer[len]='\0';  // 读取结束，在末尾手动添加字符串结束标志
    fflush(stdin);  // 刷新输入缓冲区
    return len;
}

/*将大写字母转换成小写字母*/  
int tolower(int c)  
{  
    if (c >= 'A' && c <= 'Z')  
    {  
        return c + 'a' - 'A';  
    }  
    else  
    {  
        return c;  
    }  
} 

//将十六进制的字符串转换成整数  
int htoi(char s[])  
{  
    int i = 0;  
    int n = 0;  
    if (s[0] == '0' && (s[1]=='x' || s[1]=='X'))  
    {  
        i = 2;  
    }  
    else  
    {  
        i = 0;  
    }  
    for (; (s[i] >= '0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z') || (s[i] >='A' && s[i] <= 'Z');++i)  
    {  
        if (tolower(s[i]) > '9')  
        {  
            n = 16 * n + (10 + tolower(s[i]) - 'a');  
        }  
        else  
        {  
            n = 16 * n + (tolower(s[i]) - '0');  
        }  
    }  
    return n;  
} 

void reverse(char *s, int start, int end)
{ 
    char t; 
    while(end>start){
        t=s[start]; 
        s[start]=s[end]; 
        s[end]=t;
        start++; 
        end--; 
    }  
}

int main()
{
    uint32_t v[2]={1,2},k[4]={2,2,3,4};
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    int flagLen = 0;
    bool success = false;
    char flag[33];
    memset(flag, 0, sizeof(flag));//清空字符串
    setbuf(stdin,0);
    setbuf(stdout,0);
    setbuf(stderr,0);

    printf("Please input you flag:");
    flagLen = getStr(flag,32);

    //check formant
    uint8_t vv[5] = {0};
    strncpy(vv,flag,4);
    uint8_t five = 123;
    uint8_t last = 125;
    uint8_t *v1,*v2;
    if(((uint8_t)flag[5] - five)>0){
        printf("five error!");
        return -1;
    }

    if(((uint8_t)flag[flagLen-1] + last) == 250){
        ;
    }else{
        printf("last error!");
        return -1;
    }

    if(strcmp(vv,"flag")){
        printf("header error!");
        return -1;
    }
    int mallocSize = flagLen - 6;
    char *tokstr = (char *)malloc(sizeof(char)*mallocSize+1);
    memset(tokstr, 0, sizeof(tokstr));//清空字符串
    strncpy(tokstr,flag+5,mallocSize);

    v1 = strtok(tokstr,"-");

    v2 = strtok(NULL,"-");

    //exchange scale
    uint32_t flagLong[2];
    flagLong[0] = (uint32_t)htoi((char *)v1);
    flagLong[1] = (uint32_t)htoi((char *)v2);
    // printf("%d",sizeof(int));  4 byte == 32 bit

    // printf("加密前原始数据：%x %x\n",flagLong[0],flagLong[1]);
    encipher(32,flagLong, k);
    // printf("加密后的数据：%x %x\n",flagLong[0],flagLong[1]);
    // check flag
    uint8_t check_enc[4];
    uint8_t check_index[4] = {3,1,0,2};
    uint8_t i=0;
    check_enc[0] = 0x8c;
    check_enc[1] = 0xa2;
    check_enc[2] = 0x26;
    check_enc[3] = 0x46;
    for(i=0;i<4;i++){
        uint8_t t = (uint8_t)(flagLong[0]>>(8*i));
        // printf("%x\t",t);
        if(check_enc[i]!=flagLong[check_index[i]]){
            success = false;
        }
    }

    char check_enc_last[9] = "61ba69e3";
    // snprintf(check_enc_last,9,"%x",flagLong[1]);//3e96ab16
    reverse(check_enc_last,0,7);
    uint32_t enc_hex = htoi(check_enc_last);

    // printf("%x",enc_hex);
    if(flagLong[1] == enc_hex){
        success = true;
    }
    if(!success){
        printf("You Lost!\n");
    }else{
        printf("You Win!\n");
    }


    return 0;
}

解题代码：

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

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}
int main()
{
    uint32_t k[4]={2,2,3,4};
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位

    //exchange scale
    uint32_t flagLong[2];
    flagLong[0] = 0x26a2468c;
//enc  26a2468c 3e96ab16
    flagLong[1] = 0x3e96ab16;
    decipher(32,flagLong,k);
    printf("flag{%X-%.08X}\n",flagLong[0],flagLong[1]);

    return 0;
}

xxTea题目：

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

#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))

void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
        rounds = 6 + 52/n;
        sum = 0;
        z = v[n-1];
        do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
            y = v[p+1]; 
            z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
        } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
        n = -n;
        rounds = 6 + 52/n;
        sum = rounds*DELTA;
        y = v[0];
        do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
            z = v[p-1];
            y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
        } while (--rounds);
    }
}


int getStr(char *buffer,int maxLen){
    char c;  // 读取到的一个字符
    int len = 0;  // 当前输入的字符串的长度
    // 一次读取一个字符，保存到buffer
    // 直到遇到换行符(\n)，或者长度超过maxLen时，停止读取
    while( (c=getchar()) != '\n' ){
        buffer[len++]=c;  // 将读取到的字符保存到buffer
        if(len>=maxLen){
            break;
        }
    }
    buffer[len]='\0';  // 读取结束，在末尾手动添加字符串结束标志
    fflush(stdin);  // 刷新输入缓冲区
    return len;
}

/*将大写字母转换成小写字母*/  
int tolower(int c)  
{  
    if (c >= 'A' && c <= 'Z')  
    {  
        return c + 'a' - 'A';  
    }  
    else  
    {  
        return c;  
    }  
} 

//将十六进制的字符串转换成整数  
int htoi(char s[])  
{  
    int i = 0;  
    int n = 0;  
    if (s[0] == '0' && (s[1]=='x' || s[1]=='X'))  
    {  
        i = 2;  
    }  
    else  
    {  
        i = 0;  
    }  
    for (; (s[i] >= '0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z') || (s[i] >='A' && s[i] <= 'Z');++i)  
    {  
        if (tolower(s[i]) > '9')  
        {  
            n = 16 * n + (10 + tolower(s[i]) - 'a');  
        }  
        else  
        {  
            n = 16 * n + (tolower(s[i]) - '0');  
        }  
    }  
    return n;  
} 

void reverse(char *s, int start, int end)
{ 
    char t; 
    while(end>start){
        t=s[start]; 
        s[start]=s[end]; 
        s[end]=t;
        start++; 
        end--; 
    }  
}

int main()
{
    uint32_t v[2]={1,2},k[4]={2,2,3,4};
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    int flagLen = 0;
    bool success = false;
    char flag[33];
    memset(flag, 0, sizeof(flag));//清空字符串
    setbuf(stdin,0);
    setbuf(stdout,0);
    setbuf(stderr,0);

    printf("Please input you flag:");
    flagLen = getStr(flag,32);

    //check formant
    uint8_t vv[5] = {0};
    strncpy(vv,flag,4);
    uint8_t five = 123;
    uint8_t last = 125;
    uint8_t *v1,*v2;
    if(((uint8_t)flag[5] - five)>0){
        printf("five error!");
        return -1;
    }

    if(((uint8_t)flag[flagLen-1] + last) == 250){
        ;
    }else{
        printf("last error!");
        return -1;
    }

    if(strcmp(vv,"flag")){
        printf("header error!");
        return -1;
    }
    int mallocSize = flagLen - 6;
    char *tokstr = (char *)malloc(sizeof(char)*mallocSize+1);
    memset(tokstr, 0, sizeof(tokstr));//清空字符串
    strncpy(tokstr,flag+5,mallocSize);

    v1 = strtok(tokstr,"-");

    v2 = strtok(NULL,"-");

    //exchange scale
    uint32_t flagLong[2];
    flagLong[0] = (uint32_t)htoi((char *)v1);
    flagLong[1] = (uint32_t)htoi((char *)v2);
    // printf("%d",sizeof(int));  4 byte == 32 bit

    // printf("加密前原始数据：%x %x\n",flagLong[0],flagLong[1]);
    btea(flagLong,2, k);
    // printf("加密后的数据：%x %x\n",flagLong[0],flagLong[1]);
    // check flag
    uint8_t check_enc[4];
    uint8_t check_index[4] = {3,1,0,2};
    uint8_t i=0;
    check_enc[0] = 0x57;
    check_enc[1] = 0x8b;
    check_enc[2] = 0x36;
    check_enc[3] = 0x9b;
    for(i=0;i<4;i++){
        uint8_t t = (uint8_t)(flagLong[0]>>(8*i));
        // printf("%x\t",t);
        if(check_enc[i]!=flagLong[check_index[i]]){
            success = false;
        }
    }

    char check_enc_last[9] = "6b45a63b";
    // snprintf(check_enc_last,9,"%x",flagLong[1]);//b36a54b6
    reverse(check_enc_last,0,7);
    uint32_t enc_hex = htoi(check_enc_last);

    // printf("%x",enc_hex);
    if(flagLong[1] == enc_hex){
        success = true;
    }
    if(!success){
        printf("You Lost!\n");
    }else{
        printf("You Win!\n");
    }


    return 0;
}

解题代码：

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))

void btea(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n > 1) {          /* Coding Part */
        rounds = 6 + 52/n;
        sum = 0;
        z = v[n-1];
        do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
            y = v[p+1]; 
            z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
        } while (--rounds);
    } else if (n < -1) {  /* Decoding Part */
        n = -n;
        rounds = 6 + 52/n;
        sum = rounds*DELTA;
        y = v[0];
        do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
            z = v[p-1];
            y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
        } while (--rounds);
    }
}

int main()
{
    uint32_t k[4]={2,2,3,4};
    // v为要加密的数据是两个32位无符号整数
    // k为加密解密密钥，为4个32位无符号整数，即密钥长度为128位
    //exchange scale
    uint32_t flagLong[2];
    flagLong[0] = 0x368b9b57;
    flagLong[1] = 0xb36a54b6;
    btea(flagLong,-2,k);
    printf("flag{%X-%.08X}\n",flagLong[0],flagLong[1]);

    return 0;
}

完。