XTEA Block Cipher

Introduction

TEA Extensions (XTEA) is a 64-bit block cipher with support for 128-bit keys. It was published in 1998 as a response to weaknesses found in the Tiny Encryption Algorithm (TEA) which was discussed previously in this post. XTEA compared to its predecessor contains a more complex key-schedule and rearrangement of shifts, XORs, and additions. Only Encryption is implemented here, that can then be used in Counter (CTR) mode to create a stream cipher. XTEA is not considered a secure block cipher and shouldn’t be considered for any project that requires a high level of security. Moreover, the following code is not optimized for performance. It’s a simplified version intended to be used only as a reference.

Encryption

This version uses 32 rounds by default. Despite i being initialized to 64, it’s possible to perform encryption of each 32-bit value via swapping and an if statement. mk should point to a 128-bit key while data should point to a 64-bit block of plaintext to encrypt.

// uses 32 rounds by default
void xtea(void *key, void *data) {
    int      i;
    uint32_t x0, x1, t, sum=0;
    
    uint32_t *k=(uint32_t*)key;
    uint32_t *x=(uint32_t*)data;
    
    // load 64-bit plain text
    x0 = x[0]; x1 = x[1];
    
    for (i=64; i>0; i--) {
      t = sum;
      // add constant every 2nd round
      if (i & 1) {
        sum += 0x9E3779B9;
        t = sum >> 11;          
      }
      x0 += ((((x1 << 4) ^ 
        (x1 >> 5)) + x1) ^ 
        (sum + k[t & 3]));
         
      XCHG(x0, x1);
    }
    // save 64-bit cipher text
    x[0] = x0; x[1] = x1;
}

x86 assembly

bits 32
        
    %define x0  eax
    %define x1  ebx    

    %define t0  ebp
    %define t1  esi
    
    %define k   edi
    
    %define sum edx
    
xtea:    
_xtea:
    pushad
    mov    edi, [esp+32+4]   ; edi = key
    mov    esi, [esp+32+8]   ; esi = data
    push   64
    pop    ecx
    xor    edx, edx          ; sum = 0
    push   esi
    lodsd
    xchg   eax, x1
    lodsd
    xchg   eax, x1
xtea_enc:
    mov    t0, x1            ; t0   = x1 << 4
    shl    t0, 4
    
    mov    t1, x1            ; t1   = x1 >> 5
    shr    t1, 5    
    
    xor    t0, t1            ; t0  ^= t1
    add    t0, x1            ; t0  += x1;
    
    mov    t1, sum           ; t1   = sum
    test   cl, 1
    jz     xtea_l1
    
    add    sum, 0x9E3779B9   ; sum += 0x9E3779B9   
    mov    t1, sum     
    shr    t1, 11            ; t1 = sum >> 11  
xtea_l1:    
    and    t1, 3             ; t1  &= 3
    mov    t1, [k+4*t1]      ; t1 = sum + k[t1]
    add    t1, sum
    
    xor    t0, t1            ; t0 ^= t1
    
    add    x0, t0            ; x0 += t0
    xchg   x0, x1            ; XCHG(x0, x1); 
    loop   xtea_enc    
    
    pop    edi               ; edi = x
    stosd                    ; x[0] = x0
    xchg   eax, x1
    stosd                    ; x[1] = x1
    popad
    ret

ARM / AArch32

ARM allows each instruction to have conditional execution and that allows us to eliminate the branch used in x86 assembly.

    .arch armv7-a
    .text
    
    .equ ROUNDS, 32
    
    .global xtea

    // xtea(void*mk, void*data);
xtea:
    // save registers
    push   {r2-r8, lr}
    
    mov    r7, #(ROUNDS * 2)

    // load 64-bit plaintext
    ldm    r1, {r2, r4}         // x0  = x[0], x1 = x[1];
    mov    r3, #0               // sum = 0;
    ldr    r5, =#0x9E3779B9     // c   = 0x9E3779B9;
L0:
    mov    r6, r3               // t0 = sum;
    tst    r7, #1               // if (i & 1)
  
    addne  r3, r5               // sum += 0x9E3779B9;
    lsrne  r6, r3, #11          // t0 = sum >> 11

    and    r6, #3               // t0 %= 4
    ldr    r6, [r0, r6, lsl #2] // t0 = k[t0];
    add    r8, r3, r6           // t1 = sum + t0
    mov    r6, r4, lsl #4       // t0 = (x1 << 4)
    eor    r6, r4, lsr #5       // t0^= (x1 >> 5)
    add    r6, r4               // t0+= x1
    eor    r6, r8               // t0^= t1
    mov    r8, r4               // backup x1
    add    r4, r6, r2           // x1 = t0 + x0

    // XCHG(x0, x1)
    mov    r2, r8               // x0 = x1
    subs   r7, r7, #1           // i--
    bne    L0                   // i>0
    
    // store 64-bit ciphertext
    stm    r1, {r2, r4}
    pop    {r2-r8, pc}

Because the link register (LR) is saved upon entry point, and restored to the program counter (PC) at end, this returns execution directly to the caller.

ARM64 / AArch64

// XTEA in ARM64 assembly
// 92 bytes

    .arch armv8-a
    .text
 
    .equ ROUNDS, 32
 
    .global xtea

    // xtea(void*mk, void*data);
xtea:
    mov    w7, ROUNDS * 2 

    // load 64-bit plain text
    ldp    w2, w4, [x1]         // x0  = x[0], x1 = x[1];
    mov    w3, wzr              // sum = 0;
    ldr    w5, =0x9E3779B9      // c   = 0x9E3779B9;
L0:
    mov    w6, w3               // t0 = sum;
    tbz    w7, 0, L1            // if ((i & 1)==0) goto L1;

    // the next 2 only execute if (i % 2) is not zero
    add    w3, w3, w5           // sum += 0x9E3779B9;
    lsr    w6, w3, 11           // t0 = sum >> 11
L1:
    and    w6, w6, 3            // t0 %= 4
    ldr    w6, [x0, x6, lsl 2]  // t0 = k[t0];
    add    w8, w3, w6           // t1 = sum + t0
    mov    w6, w4, lsl 4        // t0 = (x1 << 4)
    eor    w6, w6, w4, lsr 5    // t0^= (x1 >> 5)
    add    w6, w6, w4           // t0+= x1
    eor    w6, w6, w8           // t0^= t1
    mov    w8, w4               // backup x1
    add    w4, w6, w2           // x1 = t0 + x0

    // XCHG(x0, x1)
    mov    w2, w8               // x0 = x1
    subs   w7, w7, 1
    bne    L0                   // i > 0
    stp    w2, w4, [x1]
    ret

Summary

It’s safe to assume people searching the internet for a “Tiny Encryption Algorithm” will come accross TEA/XTEA, but for a variety of reasons, it is not suitable to use anymore. The Chaskey block cipher is a good alternative with support for 128-bit blocks.

sources here.

Advertisements
This entry was posted in arm, assembly, programming, security, x86 and tagged , , , , , , . Bookmark the permalink.

1 Response to XTEA Block Cipher

  1. Pingback: Shellcode: Encryption Algorithms in ARM Assembly | modexp

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s