Project Nayuki

Tiny Encryption Algorithm in x86 assembly

The Tiny Encryption Algorithm (TEA) is what it claims to be – a cipher that can be implemented with only a small amount of code. It is a block cipher with a block size of 64 bits and a key size of 128 bits. Despite its simplicity, it is designed to be a serious cipher; it does not compare with simple ciphers like ROT13.

As an exercise, I decided to implement TEA in x86 assembly language to understand x86 programming better and to see just how small the TEA implementation would be. I am pleased to say that the exercise was successful and the resulting code is small and clean.

The x86 code, explained

.globl tea_encrypt_x86

This function would be called from C using this prototype:
void tea_encrypt(uint32_t *msg, uint32_t *key);

    pushl  %ebp
    movl   %esp, %ebp
    subl   $12, %esp

Enter and allocate 3 words of local storage on the stack.

    movl   %ebx, 0(%esp)
    movl   %esi, 4(%esp)
    movl   %edi, 8(%esp)

Preserve the caller-save registers, as per the cdecl calling convention.

    movl    8(%ebp), %eax  /* Message */
    movl   12(%ebp), %edx  /* Key */

Load the base of the message array into EAX temporarily, and the base of the key array into EDX.

    movl   0(%eax), %esi
    movl   4(%eax), %edi

Load both 32-bit words of the message and keep them in ESI and EDI.

    movl   $0x9E3779B9, %ecx  /* 'sum' */

Initialize the round constant called sum and keep it in ECX.


Beginning of loop.

    movl   %edi, %ebx
    shll   $4, %ebx
    addl   0(%edx), %ebx
    leal   (%edi,%ecx), %eax
    xorl   %eax, %ebx
    movl   %edi, %eax
    shrl   $5, %eax
    addl   4(%edx), %eax
    xorl   %eax, %ebx
    addl   %ebx, %esi

Encrypt the 0th message word. EAX and EBX are used as temporaries. Summary in C code:
esi += ((edi << 4) + key[0]) ^ (edi + ecx) ^ ((edi >> 5) + key[1]);

    movl   %esi, %ebx
    shll   $4, %ebx
    addl   8(%edx), %ebx
    leal   (%esi,%ecx), %eax
    xorl   %eax, %ebx
    movl   %esi, %eax
    shrl   $5, %eax
    addl   12(%edx), %eax
    xorl   %eax, %ebx
    addl   %ebx, %edi

Encrypt the 1st message word in the same way. C code:
edi += ((esi << 4) + key[2]) ^ (esi + ecx) ^ ((esi >> 5) + key[3]);

    addl   $0x9E3779B9, %ecx
    cmpl   $0x6526B0D9, %ecx
    jne    .tea_encrypt_top

Advance the round constant. Loop if 32 iterations have not been completed yet. (Note: 3310 × 9E3779B916 ≡ 6526B0D916 mod 232.)

    movl   8(%ebp), %eax
    movl   %esi, 0(%eax)
    movl   %edi, 4(%eax)

End of loop. Store the message words back to the array passed in by the caller.

    movl   0(%esp), %ebx
    movl   4(%esp), %esi
    movl   8(%esp), %edi

Restore the callee-save registers.

    addl   $12, %esp
    popl   %ebp

Deallocate stack space and exit.

Source code

This code offers a function that performs TEA encryption, and includes a main() function that runs a demo. To use the code, compile it on Linux with the command gcc tea-test.c tea-x86.s -o tea-test and run with ./tea-test.

An x86-64 version is also provided, substituting tea.s with tea-x8664.s. The structure of the code and especially the core arithmetic is essentially similar, but the register usage has been rearranged and the calling convention was necessarily changed.

Lessons learned


More info