RoadRunneR Block Cipher

Introduction

RoadRunneR is a 64-bit block cipher with support for 80 and 128-bit keys. It was designed by Adnan Baysal and Suhap Sahin and published in 2015. The 80-bit variant uses 10 rounds while the 128-bit uses 12. In this post, I’ll show x86 assembly and C code for the 128-bit version. The authors of cipher state in their proposal the main objectives of RoadRunneR:

  • Implementation efficiency in 8-bit CPUs
  • No table and SRAM usage
  • Low decryption overhead
  • Provable security like in wide trail design strategy

RoadRunneR is a perfect choice for devices with very restricted memory resources and for applications requiring reasonable throughput expectations.

Although the cipher is specifically designed for 8-bit CPUs, the code shown here has a mixture of 8-bit and 32-bit code.

Compact code

The following implementation combines both key scheduling and encryption in one function. The mk parameter should point to a 128-bit master key and the data parameter should point to a 64-bit block of plaintext to be encrypted.

#define R(v,n)(((v)<<(n))|((v)>>(8-(n))))
#define X(x,y)t=x,x=y,y=t;

typedef unsigned char B;
typedef unsigned int W;

// S-Layer
void S(void *p) {
    B t, *x=(B*)p;
    
    t = x[3]; 
    x[3] &= x[2]; 
    x[3] ^= x[1];
    x[1] |= x[2];
     
    x[1] ^= x[0];
    x[0] &= x[3]; 
    x[0] ^=  t; 
    t    &= x[1];    
    x[2] ^=  t;
}

// encrypt 64-bits of data using 128-bit key  
void roadrunner(void *mk, void *data) {
    int i, j, r;
    W   t, *x=(W*)data, *k=(W*)mk;
    B   s, *p, k_idx=4;
    
    // apply K-Layer
    x[0] ^= k[0];
    
    // apply 12 rounds of encryption
    for(r=12; r>0; r--) {
      // F round
      t=x[0]; // save original 32-bits
      p=(B*)x;
      for(i=0; i<3; i++) {
        // add constant
        if(i==2) p[3] ^= r;
        // apply S-Layer
        S(p);
        for (j=0; j<4; j++) {      
          // apply L-Layer
          s = R(p[j], 1) ^ p[j];       
          p[j] ^= R(s,  1); 
          // apply K-Layer
          p[j] ^= ((B*)k)[(k_idx%16)+j];
        }
        k_idx+=4;
      }
      // apply S-Layer
      S(p);
      // add upper 32-bits
      x[0]^= x[1]; x[1] = t;
    }
    // permute
    X(x[0], x[1]);
    // apply K-Layer
    x[0] ^= k[1];
}

x86 assembly

; -----------------------------------------------
; RoadRunneR-64/128 block cipher in x86 assembly
;
; size: 135 bytes
;
; global calls use cdecl convention
;
; -----------------------------------------------


    bits 32
    
    %ifndef BIN
      global roadrunner
      global _roadrunner
    %endif

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

roadrunner:
_roadrunner:
    pushad
    mov    edi, [esp+32+4]    ; k = mk
    mov    esi, [esp+32+8]    ; x = data
    xor    ebx, ebx           ; k_idx = 0
    ; apply K-Layer
    ; x[0] ^= ((W*)mk)[0];
    mov    ebp, [edi]         ; t = ((W*)mk)[0]
    xor    [esi], ebp         ; x[0] ^= t 
    ; apply 12 rounds of encryption
    ; for(r=12; r>0; r--) {
    push   12             
    pop    ecx
rr_L0:    
    ; F round
    pushad                    ; save all registers: for(r=12
    mov    ebp, [esi]         ; t = x[0]
    mov    edx, ecx           ; edx = r
    mov    cl, 3              ; i = 3
rr_L1:
    inc    ebx                ; k_idx = (k_idx + 4) % 16
    and    ebx, 3
    pushad                    ; save all registers: for(i=3
    ; add constant
    cmp    cl, 1              ; if (i == 1)
    jne    rr_L2
    xor    [esi+3], dl        ; p[3] ^= r
rr_L2:
    lea    edi, [edi+ebx*4]   ; edi = &k[k_idx]
    ; apply S-Layer
    ; S(p);
    call   S
    ; for (j=3; j>=0; j--) { 
    mov    cl, 4              ; j = 4 
    ; apply L-Layer
rr_L3:
    ; s = R(p[j], 1) ^ p[j]; 
    mov    al, [esi]          ; s = p[j]
    rol    al, 1              ; s = R(s, 1)
    xor    al, [esi]          ; s^= p[j]
    ; s = R(s, 1) ^ p[j];
    rol    al, 1              ; s = R(s, 1) 
    xor    al, [esi]          ; s^= p[j]
    
    ; apply K-Layer
    ; p[j] = s ^ ((B*)k)[(k_idx%16)+j];
    xor    al, byte[edi]
    mov    [esi], al
    cmpsb
    loop   rr_L3              ; j>0; j--
    
    popad                     ; restore registers: for(i=3
    loop   rr_L1              ; i>0; i--
    
    ; apply S-Layer
    ; S(p);    
    call   S
    ; add upper 32-bits
    ; x[0]^= x[1];
    lodsd
    xor    eax, [esi]
    mov    [esi-4], eax
    
    ; x[1] = t;
    mov    [esi], ebp
    mov    [esp+_ebx], ebx    ; save k_idx
    popad                     ; restore registers: for(r=12
    loop   rr_L0              ; r>0; r--
    
    ; permute
    ; X(x[0], x[1]);
    lodsd
    xchg   eax, [esi]
    
    ; apply K-layer
    ; x[0] ^= ((W*)mk)[1];    
    xor    eax, [edi+4]
    mov    [esi-4], eax  
    
    popad
    ret    

; S-Layer    
S:
    pushad
    mov    ebx, esi      ; ebx = esi
    lodsd
    mov    edx, eax      ; t = ROTR32(x[0], 16); 
    ror    edx, 16
    and    [ebx+3], dl   ; x[3] &= t[0];
    xor    [ebx+3], ah   ; x[3] ^= x[1];
    or     [ebx+1], dl   ; x[1] |= t[0];    
    xor    [ebx+1], al   ; x[1] ^= x[0];
    mov    dl, [ebx+3]
    and    [ebx+0], dl   ; x[0] &= x[3];
    xor    [ebx+0], dh   ; x[0] ^= t[1];
    and    dh, [ebx+1]   ; t[1] &= x[1];
    xor    [ebx+2], dh   ; x[2] ^= t[1]; 
    popad
    ret

S Layer

Using bit-slice techniques for an S-box layer has become popular lately as more research into lightweight cryptography for resource constrained environments progresses. Block ciphers such as NOEKEON, PRIDE, RECTANGLE and Fantomas/Robin all use a bit-sliced S-box layer. Some advantages of using a bit-slice S-box layer in both hardware and software implementations include protection against side-channel analysis, and elimination of S-Box array that would require ROM/RAM. Authors say the S-box for RoadRunneR was found through a brute force search of assembly code combinations. The search space was restricted to 4 input words, a single temporary word, and the following instructions: AND, OR, XOR, NOT, and MOV.

Finding Optimal Bitsliced Implementations of 4×4-bit S-boxes. describes this process in more detail. The following values for the 4 x 4 S-Layer are used.

// S-Layer
void sbox(uint8_t *x)
{
    uint8_t t;
    
    t = x[3];

    x[3] &= x[2];
    x[3] ^= x[1];
    x[1] |= x[2];
    x[1] ^= x[0];
    x[0] &= x[3];
    x[0] ^=  t; 
       t &= x[1];
    x[2] ^=  t;
}

Cryptographic Analysis of All 4 x 4 – Bit S-Boxes

L Layer

A linear function on each byte of the state to provide diffusion. Such a linear function is normally implemented using an XOR of rotated or shifted values. It’s commonly seen in many block ciphers and hash algorithms like Serpent, SM3 and SM4.

K Layer

This is not referenced in the original paper, but is essentially Key Whitening AKA Key Addition, which was first implemented by Ron Rivest in DES-X. The theory is that by XOR’ing bits of the key against plaintext during the encryption process, this helps strengthen the final ciphertext against exhaustive brute force attacks. It’s a technique used in many SPN block ciphers. For example, it’s known as AddRoundKey in the Advanced Encryption Standard (AES).

SLK Function

Combining Layers S, L and K is the following function.

// SLK function 
void SLK(w32_t *x, uint8_t *sk)
{
    int     i;
    uint8_t t;
    uint8_t *p=x->b;
    
    // apply S-Layer
    sbox(p);
    
    for (i=3; i>=0; i--) {      
      // apply L-Layer
      t   = ROTL8(*p, 1) ^ *p;       
      *p ^= ROTL8(t,  1); 
      
      // apply K-Layer
      *p++ ^= *sk++;
    }
}

The F-Function

The main function consists of a 4-round Substitution–permutation network (SPN) structure. The first three rounds have the same function called SLK, which is the application of S, L and K layers already described. The final round only applies the S layer. In addition to aforementioned layers is the addition of a round constant after the second call to SLK. This is simply the round number XOR’ed against the least significant byte of the state, which for the 128-bit key variant would be from 12 down to 1.

It is, as the authors describe, intended to protect against simple Slide Attacks. Biryukov and Wagner state the following in Advanced Slide Attacks.

The most obvious type of slide attack is usually easy to prevent by destroying self-similarity in iterative ciphers, for example by adding iteration counters or random constants.

// F round
void F(w64_t *blk, void *key, 
    uint8_t *key_idx, uint8_t ci)
{
    int      i;
    uint32_t t;
    uint8_t  *rk=(uint8_t*)key;
    w32_t    *x=(w32_t*)blk;
    
    // save 32-bits
    t = x->w;
    
    for (i=3; i>0; i--) {
      // add round constant
      if (i==1) x->b[3] ^= ci;
      // apply S,L,K layers
      SLK (x, rk + *key_idx);      
      // advance master key index
      *key_idx = (*key_idx + 4) & 15;
    }
    
    // apply S-Layer
    sbox(x->b);
    
    // add upper 32-bits
    blk->w[0]^= blk->w[1];
    blk->w[1] = t;
}

Encryption

The variable key_idx which acts as a master key index is initialized to 4, skipping the first 4 bytes which are XOR’d against the plaintext as part of K-Layer before 12 rounds of F. Note how rnd is initialized to 12 and passed to F. This is the round constant used to protect against simple slide attacks.

// encrypt 64-bits of data using 128-bit key  
void road64_encrypt(void *data, void *key)
{
    int      rnd;
    uint8_t  key_idx;
    uint32_t t;
    w64_t    *x=(w64_t*)data;
    uint32_t *rk=(uint32_t*)key;

    // initialize master key index
    key_idx = 4;
    
    // apply K-Layer
    x->w[0] ^= rk[0];
    
    // apply rounds
    for (rnd=RR_ROUNDS; rnd>0; rnd--) {
      F(x, rk, &key_idx, rnd);
    }
    // P-Layer?
    XCHG(x->w[0], x->w[1]);
    // apply K-Layer
    x->w[0] ^= rk[1];
}

Sources here.

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

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