LEA Block Cipher

Introduction

LEA is a 128-bit block cipher with support for 128, 192 and 256-bit keys published in 2014. It was designed by Deukjo Hong, Jung-Keun Lee, Dong-Chan Kim, Daesung Kwon, Kwon Ho Ryu, and Dong-Geon Lee.

The only operations used for encryption and the key schedule are 32-bit Addition, eXclusive OR and Rotation (ARX structure): the designers state “the usage of 32-bit and 64-bit processors will grow rapidly compared to 8-bit and 16-bit ones”

Today I’ll just focus on an implementation using 128-bit keys referred to as LEA-128. This just about fits onto the 32-bit x86 architecture. The 256-bit version requires additional registers and is probably better suited for 64-bit mode.

Key Schedule

During generation of subkeys, a number of predefined constants are used.

\textbf{Constants. }
\text{The key schedule uses several constants for generating round keys, which are defined as}

\delta[0] = 0xc3efe9db, \quad \delta[1] = 0x44626b02,
\delta[2] = 0x79e27c8a, \quad \delta[3] = 0x78df30ec,
\delta[4] = 0x715ea49e, \quad \delta[5] = 0xc785da0a,
\delta[6] = 0xe04ef22a, \quad \delta[7] = 0xe5c40957.

\text{They are obtained from hexadecimal expression of } \sqrt{766965},
\text{ where 76, 69 and 65 are ASCII codes of 'L', 'E' and 'A'.}

You can obtain the values using a tool like speedcrunch.

There are 3 different key schedule functions but I only focus on the 128-bit variant for now.

\textbf{Key Schedule with a 128-Bit Key. }
\text{Let } K = (K[0], K[1], K[2], K[3]) \text{ be a 128-bit key. We set } T[i] = K[i]\: for \: 0\leq 4.   \text{ Round key} RK_i = (RK_i[0], RK_i[1],\dots , RK_i[5])\: for\: 0\leq i < 24 \text{ are produced through the following relations:}

T[0]\leftarrow ROL_1(T[0]\oplus ROL_i(\delta[i\:mod\: 4])),\\  T[1]\leftarrow ROL_3(T[1]\oplus ROL_{i+1}(\delta[i\:mod\: 4])),\\  T[2]\leftarrow ROL_6(T[2]\oplus ROL_{i+2}(\delta[i\:mod\: 4])),\\  T[3]\leftarrow ROL_{11}(T[3]\oplus ROL_{i+3}(\delta[i\:mod\: 4])),\\  RK_i\leftarrow (T[0], T[1], T[2], T[3], T[1]).

Encryption

This is a really simple algorithm to implement and there’s not much to say that can’t be found in the specification published by the authors.

So here’s the function in C to perform encryption on 128-bits of plaintext using 128-bit key in one single call. I’d suggest using something like this with counter (CTR) mode so it doesn’t require the decryption procedure.

void lea128_encryptx(void *key, void *data) {
    uint32_t k0, k1, k2, k3, i, t0;
    uint32_t x0, x1, x2, x3;
    uint32_t *x, *k;
    uint32_t c[4];

    x = (uint32_t*)data;
    k = (uint32_t*)key;

    // init constants
    c[0] = 0xc3efe9db; c[1] = 0x88c4d604;
    c[2] = 0xe789f229; c[3] = 0xc6f98763;

    // load 128-bit key
    k0 = k[0]; k1 = k[1];
    k2 = k[2]; k3 = k[3];

    // load 128-bit plain text
    x0 = x[0]; x1 = x[1];
    x2 = x[2]; x3 = x[3];

    // perform encryption
    for (i=0; i<24; i++) {
      t0       = c[i & 3];
      c[i & 3] = ROTR32(t0, 28);
      
      // create subkey
      k0 = ROTR32(k0 + t0, 31);
      k1 = ROTR32(k1 + ROTR32(t0, 31), 29);
      k2 = ROTR32(k2 + ROTR32(t0, 30), 26);
      k3 = ROTR32(k3 + ROTR32(t0, 29), 21);
      
      // encrypt block
      t0 = x0;
      x0 = ROTR32((x0 ^ k0) + (x1 ^ k1),23);
      x1 = ROTR32((x1 ^ k2) + (x2 ^ k1), 5);
      x2 = ROTR32((x2 ^ k3) + (x3 ^ k1), 3);
      x3 = t0;
    }
    // save result
    x[0] = x0; x[1] = x1;
    x[2] = x2; x[3] = x3;
}

Full x86 assembly

You might notice the constants are different from C sources. For whatever reason, the last 3 are rotated a number of bits left before entering the encryption loop as you can see above.

Obviously a compiler will be smart enough to see this and automatically optimize but for assembly code, we must rotate them manually. They’re stored on the stack using PUSHAD. So, EDI, ESI, EBP and ESP are used for TD array.

ESP has to be initialized after the PUSHAD for obvious reasons. We don’t want to cause an exception.

bits 32

struc pushad_t
  _edi resd 1
  _esi resd 1
  _ebp resd 1
  _esp resd 1
  _ebx resd 1
  _edx resd 1
  _ecx resd 1
  _eax resd 1
  .size:
endstruc

%define k0 ebx
%define k1 edx
%define k2 edi
%define k3 ebp

%define x0 dword[esi+4*0]
%define x1 dword[esi+4*1]
%define x2 dword[esi+4*2]
%define x3 dword[esi+4*3]

%define t0 ecx

%define LEA128_RNDS 24

lea128_encryptx:
_lea128_encryptx:
    pushad
    ; initialize 4 constants
    mov    edi, 0xc3efe9db   ; td[0]
    mov    esi, 0x88c4d604   ; td[1]
    mov    ebp, 0xe789f229   ; td[2]
    pushad
    mov    dword[esp+_esp], 0xc6f98763   ; td[3]
    mov    esi, [esp+64+4]   ; esi = key
    ; load key
    lodsd
    xchg   eax, k0
    lodsd
    xchg   eax, k1
    lodsd
    xchg   eax, k2
    lodsd
    xchg   eax, k3
    mov    esi, [esp+64+8]   ; esi = block
    xor    eax, eax          ; i = 0
lea_l0:
    push   eax
    ; t0 = c[i % 4];
    and    al, 3
    mov    t0, [esp+eax*4+4]
    ; c[i & 3] = ROTR32(t, 28);
    ror    t0, 28
    mov    [esp+eax*4+4], t0
    ; **************************************
    ; create sub key
    ; **************************************
    ; k0 = ROTR32(k0 + t0, 1);
    add    k0, t0
    ror    k0, 31
    ; k1 = ROTR32(k1 + ROTR32(t0, 31), 29);
    ror    t0, 31
    add    k1, t0
    ror    k1, 3
    ; k2 = ROTR32(k2 + ROTR32(t0, 30), 26);
    ror    t0, 1
    add    k2, t0
    ror    k2, 6
    ; k3 = ROTR32(k3 + ROTR32(t0, 29), 21);
    ror    t0, 1
    add    k3, t0
    ror    k3, 11
    ; **************************************
    ; encrypt block
    ; **************************************
    ; t0 = x0;
    push   x0
    ; x0 = ROTR32((x0 ^ k0) + (x1 ^ k1),23);
    mov    t0, x1
    xor    x0, k0
    xor    t0, k1
    add    x0, t0
    ror    x0, 23
    ; x1 = ROTR32((x1 ^ k2) + (x2 ^ k1), 5);
    mov    t0, x2
    xor    x1, k2
    xor    t0, k1
    add    x1, t0
    ror    x1, 5
    ; x2 = ROTR32((x2 ^ k3) + (x3 ^ k1), 3);
    mov    t0, x3
    xor    x2, k3
    xor    t0, k1
    add    x2, t0
    ror    x2, 3
    ; x3 = t0;
    pop    x3
    ; i++;
    inc    eax
    ; i<LEA128_RNDS
    cmp    al, LEA128_RNDS
    jnz    lea_l0

    popad
    popad
    ret

Summary

The assembly generated by MSVC using /O2 /Os is 232 bytes for the single call (encryption only) and 266 for 2 separate functions. The hand written x86 assembly for just the single call is currently 149 bytes.

See lx.asm for x86 assembly or lea.c for C source

Thanks to 0x4d_ for \LaTeX formulas.

Advertisements
This entry was posted in assembly, cryptography, encryption, programming and tagged , , , . Bookmark the permalink.

One Response to LEA 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 )

w

Connecting to %s