TEA로 만들어 본 3DES 예제 #1 (부제: 어떻게 분산시켜야 하지?)

TEA가 DES는 아닌 것 같으니 3TEA라고 불러야 하나?

2007/07/11 - [프로그래밍/Utility, ETC] - 간단한 암호화 알고리즘: The Tiny Encryption Algorithm (TEA)

보통 EDE 방법으로 구현하는 것 같고, 해당 룰을 따랐다.
TEA의 암호화, 복호화 코드는 위키에서 가져왔다.

#include <stdint.h>

void __tea_encrypt(unsigned int* t, unsigned int* v, unsigned int* k)
{
    unsigned int v0 = v[0], v1 = v[1], sum = 0, i;           /* set up */
    unsigned int delta = 0x9e3779b9;             /* a key schedule constant */
    unsigned int 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 */

    t[0] = v0; t[1] = v1;
}

void __tea_decrypt(unsigned int* t, unsigned int* v, unsigned int* k)
{
    unsigned int v0 = v[0], v1 = v[1], sum = 0xC6EF3720, i;  /* set up */
    unsigned int delta = 0x9e3779b9;            /* a key schedule constant */
    unsigned int 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 */

    t[0] = v0; t[1] = v1;
}

void tea_encrypt(char *dst, char *src, int len, const unsigned long long *key)
{
    int __len = (len + 7) >> 3;
    int i;

    for (i = 0; i < __len; i++) {
        __tea_encrypt((((unsigned int *)dst) + (i << 1)), (((unsigned int *)src) + (i << 1)), (unsigned int *)key);
    }
}

void tea_decrypt(char *dst, char *src, int len, const unsigned long long *key)
{
    int __len = (len + 7) >> 3;
    int i;

    for (i = 0; i < __len; i++) {
        __tea_decrypt((((unsigned int *)dst) + (i << 1)), (((unsigned int *)src) + (i << 1)), (unsigned int *)key);
    }
}

inline void tea_3des_encrypt(char *dst, char *src, int len, const unsigned long long *key1, const unsigned long long *key2, const unsigned long long *key3)
{
    tea_encrypt(dst, src, len, key1);
    tea_decrypt(src, dst, len, key2);
    tea_encrypt(dst, src, len, key3);
}

inline void tea_3des_decrypt(char *dst, char *src, int len, const unsigned long long *key1, const unsigned long long *key2, const unsigned long long *key3)
{
    tea_decrypt(dst, src, len, key3);
    tea_encrypt(src, dst, len, key2);
    tea_decrypt(dst, src, len, key1);
}

그럭저럭 볼만하네.

왜 3TEA, 아니 TEA로 3DES를 구현했냐고?
가장 큰 원인은 TEA를 가지고 뭘 만들고 싶은데, 요게 마음대로 분산되지 않더라고. TEA는 8byte짜리 Block 알고리즘이고, 한 Block에 해당하는 8byte 내에서는 그럭저럭 분산되나 그 밖을 벗어나면 더 이상 분산되지 않는다. (당연하잖아. 암호화 단위가 8byte니까. 암호화된 8byte를 떼서 같은 키를 적용하면 똑같이 복호화되기 때문이지.)

그러니까 'A000000000000000' 의 16byte String을 Encode한 것과 'B000000000000000' 의 16byte String을 Encode 한 것과, '00000000'의 범위에서는 동일한 Encode 값이 나오게 되는건데. (Block 기반 암호화 기법이니까.)

테스트를 위해 작성한 코드. (확인 사살이라고 부른다.) 위에 첨부한 암호화 라이브러리를 사용했다.

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

#include "tea.h"

#define TEA_KEY_1_1     0x1234567890abcdefLL
#define TEA_KEY_1_2     0xfedcba0987654321LL
#define TEA_KEY_2_1     0xabcdef1234567890LL
#define TEA_KEY_2_2     0x0987654321fedcbaLL
#define TEA_KEY_3_1     0x1a2b3c4d5e6f7890LL
#define TEA_KEY_3_2     0x0987f6e5d4c3b2a1LL

const unsigned long long tea_key_1[2] = { TEA_KEY_1_1, TEA_KEY_1_2 };
const unsigned long long tea_key_2[2] = { TEA_KEY_2_1, TEA_KEY_2_2 };
const unsigned long long tea_key_3[2] = { TEA_KEY_3_1, TEA_KEY_3_2 };

int binary_dump(unsigned char *pkt, int size)
{
    int i;

    fprintf(stderr, "Binery Dump Start :\n");
    for (i = 0; i < size; i++) {
        fprintf(stderr, "%02X ", *(pkt + i));
        if (((i + 1) % 16) == 0) fprintf(stderr, " :\n");
    }
    if ((i % 16) != 0) fprintf(stderr, " :\n");

    return 0;
}

int tes_3des_test(char *buf)
{
    char outbuf[1024];
    int srclen = strlen(buf);

    fprintf(stderr, "%s TEA\n", buf);
    tea_encrypt(outbuf, buf, srclen, tea_key_1);
    binary_dump(outbuf, srclen);

    fprintf(stderr, "%s 3DES\n", buf);
    tea_3des_encrypt(outbuf, buf, srclen, tea_key_1, tea_key_2, tea_key_3);
    binary_dump(outbuf, srclen);

    return 0;
}

int main()
{
    char buf[1024];

    memset(buf, 0, 1024);

    strcpy(buf, "A000000000000000");
    tes_3des_test(buf);

    strcpy(buf, "B000000000000000");
    tes_3des_test(buf);

    return 0;
}

소스에서 보다시피, tea_3des_encrypt, decrypt 함수들을 호출한 이후에는 입력된 Buffer가 오염된다. (별도 버퍼를 안썼거든. 귀찮아서.) 그래서 tes_3des_test에서 tea_3des_encrypt 뒤에는 buf 값이 깨져버리기 때문에, tea_encrypt와 호출 순서를 바꾸려고 해도 할 수 없다. 이건 주의해야 하고.

결과는?

# ./test
A000000000000000 TEA
Binery Dump Start :
8A 4A 6D 0F F6 73 F9 C8 DD 90 AD 30 FA 0A B5 F3  :
A000000000000000 3DES
Binery Dump Start :
A9 0E 3C 4E 31 A6 F7 7C 8F 3F A6 BA 61 FA 06 CE  :
B000000000000000 TEA
Binery Dump Start :
5D 60 78 27 F7 72 FA 77 DD 90 AD 30 FA 0A B5 F3  :
B000000000000000 3DES
Binery Dump Start :
D6 D1 7C 1F 75 93 19 A7 8F 3F A6 BA 61 FA 06 CE  :
#

예상대로 분산되지 않는다.

그렇다고 3DES 방식으로 암호화하면 분산되.. 지 않는다. 생각없이 만들면 이렇다니까. 약간의 트릭이 더 필요할듯.
.. 그런데 생각해보니까 Block 방식이 아닌 알고리즘으로 TEA를 바꾸면 되잖아? Stream 방식으로. 이렇게 변경하는 것이 어려울까? (이게 Stream 방식이냐? 라고 물어본다면 글쎄요, 모르겠수, 라고 대답하리오.;)

일단 최초 소스코드에서 tea_encrypt와 tea_decrypt를 변경해보자.

void tea_encrypt(char *dst, char *src, int len, const unsigned long long *key)
{
    int __len = (len + 7) >> 3;
    int i;
    unsigned long long __key[2] = { *key, *(key + 1) };

    for (i = 0; i < __len; i++) {
        __tea_encrypt((((unsigned int *)dst) + (i << 1)), (((unsigned int *)src) + (i << 1)), (unsigned int *)__key);

        __key[0] ^= *((unsigned long long *)((unsigned int *)dst + (i << 1)));
        __key[1] ^= *((unsigned long long *)((unsigned int *)dst + (i << 1)));
    }
}

void tea_decrypt(char *dst, char *src, int len, const unsigned long long *key)
{
    int __len = (len + 7) >> 3;
    int i;
    unsigned long long __key1[2] = { *key, *(key + 1) };
    unsigned long long __key2[2];

    for (i = 0; i < __len; i++) {
        __key2[0] = __key1[0] ^
            *((unsigned long long *)((unsigned int *)src + (i << 1)));
        __key2[1] = __key1[1] ^
            *((unsigned long long *)((unsigned int *)src + (i << 1)));

        __tea_decrypt((((unsigned int *)dst) + (i << 1)), (((unsigned int *)src) + (i << 1)), (unsigned int *)__key1);

        __key1[0] = __key2[0];
        __key1[1] = __key2[1];
    }
}

그리고 테스트 소스에서, 혹시 모르니까 decrypt 해서 결과를 한번 비교해보고. tea_3des_test 함수만 적당히 변경하면 될듯.

int tes_3des_test(char *buf)
{
    char outbuf[1024];
    char outbuf2[1024];
    int srclen = strlen(buf);

    memset(outbuf, 0, 1024);
    memset(outbuf2, 0, 1024);

    fprintf(stderr, "%s TEA\n", buf);
    tea_encrypt(outbuf, buf, srclen, tea_key_1);
    binary_dump(outbuf, srclen);
    tea_decrypt(outbuf2, outbuf, srclen, tea_key_1);
    fprintf(stderr, "%s TEA, DECRYPT\n", outbuf2);

    fprintf(stderr, "%s 3DES\n", buf);
    tea_3des_encrypt(outbuf, buf, srclen, tea_key_1, tea_key_2, tea_key_3);
    binary_dump(outbuf, srclen);
    tea_3des_decrypt(outbuf2, outbuf, srclen, tea_key_1, tea_key_2, tea_key_3);
    fprintf(stderr, "%s 3DES, DECRYPT\n", outbuf2);

    return 0;
}

결과는?

# ./test
A000000000000000 TEA
Binery Dump Start :
8A 4A 6D 0F F6 73 F9 C8 17 F3 6B 6E 84 FE CA 05  :
A000000000000000 TEA, DECRYPT
A000000000000000 3DES
Binery Dump Start :
A9 0E 3C 4E 31 A6 F7 7C 09 60 A4 03 56 16 37 D9  :
A000000000000000 3DES, DECRYPT
B000000000000000 TEA
Binery Dump Start :
5D 60 78 27 F7 72 FA 77 3B C6 EC A3 BE 55 B6 61  :
B000000000000000 TEA, DECRYPT
B000000000000000 3DES
Binery Dump Start :
D6 D1 7C 1F 75 93 19 A7 E8 7B 66 85 D1 AC F0 7C  :
B000000000000000 3DES, DECRYPT
#

오. 과연 분산된다.

그냥 되잖아. .. TEA를 3DES로 왜 만들었지? 그냥 복잡도가 증가했으니 좋아졌다고 생각하면 될까;
결론은, 뻘짓이라는건가.

2009/09/04 - [프로그래밍/Utility, ETC] - TEA로 만들어 본 3DES 예제 #2 (부제: 어떻게 분산시켜야 하지?)
2009/09/05 - [프로그래밍/Utility, ETC] - CD-KEY 만들기. (부제: 왜 TEA로 그렇게 삽질을 했을까?)