TEA 微型加密演算法

發表於 2024-12-29 分類於 crypto

這個週末突然想到要重新架設卡巴拉島私服自己玩玩，主要是想整理一下架設流程，不然每一次架設都要安裝有的沒的東西，還要環境配置，非常的累。

由於微軟有建置可以在 Linux 上跑的 SQL Server，因此這次架設的主要目的就是將伺服器所需的 DB MSSQL Server 搬到 Linux 上。在解決問題的過程中意外碰到這個演算法，就順便紀錄一下。

TEA - 微型加密演算法

正如其名，這是一個簡單輕巧的對稱加密演算法，實作非常的簡單。

以下是直接從維基百科複製過來的程式實作：

#include <stdint.h>

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);  
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

void decrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0xC6EF3720, i;  /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i<32; i++) {                         /* basic cycle start */
        v1 -= ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
        v0 -= ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        sum -= delta;                                   
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

這個演算法的主要就是對兩個 32bits 的資料用 128bits 的 key 進行多輪的 XOR 運算來完成加密 (常見的是 32 次或 64 次)

算法挑選了一個 MagicNumber 0x9E3779B9 (透過 floor( ${2^{32}/\phi}$ ) 算出)

算出 MagicNumber 的 $\phi$ 是黃金比例數，它被視作 nothing-up-my-sleeve number，以證明算出的 MagicNumber 不是出於惡意目的而被挑選

演算法的 MagicNumber 會作為 delta 對要做 XOR 操作的資料 (sum) 進行加減操作
有時候 MagicNumber 可能是 0x61C88647，他跟 0x9E3779B9 一樣，只是加減的方向相反

區塊加密

如同 AES 會對 128bits 的資料塊進行加密，TEA 加密是對兩個 32bits 的區塊 (共 64bits) 進行加密

要應用在實際的資料上面，需要對原始資料分塊進行處理，這邊就簡單寫一個對一般資料進行加解密的程式

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

// TEA 演算法...
void encrypt (uint32_t* v, uint32_t* k);
void decrypt (uint32_t* v, uint32_t* k);

void tea_encrypt(void *dst, void *src, int length, void *key) {
    int padding = length % 8; // 對齊 8bytes

    memset(dst, 0, length + padding);

    for (int i = 0; i < length; i += 8) {
        uint32_t block[2] = {0};
        int size = (length-i) > 8 ? 8 : length-i;

        memcpy(block, src+i, size);
        encrypt(block, key);
        memcpy(dst+i, block, 8);
    }
}

void tea_decrypt(void *dst, void *src, int length, void *key) {
    memset(dst, 0, length);

    for (int i = 0; i < length; i += 8) {
        uint32_t block[2] = {0};

        memcpy(block, src+i, 8);
        decrypt(block, key);
        memcpy(dst+i, block, 8);
    }
}

int main()
{
    char message[] = "hello world!"; // 12+1 bytes
    char encrypted[16] = { 0 };
    char decrypted[16] = { 0 }; // 因為區塊解密, 所以是 16bytes, 實際上只有 12bytes 的文字
    char key[16] = { // 隨便填個 key
        0x0A, 0x3B, 0x16, 0x42,
        0x68, 0xB9, 0xC6, 0xA3,
        0x4A, 0xF8, 0xFF, 0x9E,
        0xEF, 0xA0, 0x00, 0x01,
    };
    
    tea_encrypt(encrypted, message, strlen(message), key);
    tea_decrypt(decrypted, encrypted, 16, key);
    
    printf(decrypted); // hello world!

    return 0;
}

為了順利進行區塊加密的操作，因此加密前需要將資料長度與區塊長度做對齊。
假設有一筆 17bytes 的資料要做加密，那就必須填充到 24bytes 才可以做 TEA 加密。

弱點

根據維基上的描述，TEA 有等效密鑰的問題，每一個密鑰會跟三個密鑰等效。因此 128bits 的密鑰等效長度實際上只有 126bits (4個彼此等效的密鑰相當於密鑰內有 2bits 失去作用)。

其他改良版本： XTEA、XXTEA

由於 TEA 有前面所述的弱點，因此出現了 XTEA ，針對前面提到的弱點進行改良。

後續又出現了第三個改良版本： XXTEA，主要是增強安全性。

後記

因為以前架過楓之谷伺服器的關係，所以很早就知道 AES 加密，這東東光看到那個原理頭就很痛了，所以我沒有深入研究，實作上也是用框架提供的加密函式庫進行 AES 加密。

這次會發現這個加密演算法是因為要架卡巴拉島私服。因為我不想為了架設私服在我的電腦裝一堆有的沒的程式佔空間，想說微軟有發布 SQL Server 的 Linux Docker Image，就試著把 SQL Server 搬到 Linux Docker 上跑，搬到一半就踩到坑。

當初私服能架起來是因為 DB 都在同一台電腦，登入可以直接使用 Windows 認證。DB 轉到 Linux 之後，就只能夠使用憑證或是密碼登入 (要另外掛 AD 認證非常麻煩)，雖然伺服器配置文件上可以打密碼，但是密碼正常打沒辦法連線到 SQL Server。所以我就開著 IDA Free 去執行檔裡面尋找答案，最後發現他有對密碼的資料進行額外處理…

直到我找到密碼載入的位置，才發現他有對密碼進行加解密。我知道加密演算法通常都會有 MagicNumber 可以識別，所以就透過找到的常數 0xC6EF3720 (解密的 sum 起始值，是 delta 左移 5bits 的結果) 成功識別加密演算法。

知道演算法之後，就可以逆向對密碼加密並寫在伺服器配置檔裡面，雖然過程中還額外踩了不少坑，但最後還是成功連線到 DB 並啟動伺服器 :)

TEA - 微型加密演算法

區塊加密

弱點

其他改良版本： XTEA、XXTEA

後記

參考資料