Asmcodes: RC6 Block cipher

RC6 is a symmetric block cipher designed by Ron Rivest, Matthew Robshaw, Ray Sidney and Yiqun Lisa Yin published in 1998. It was one of the 5 finalists considered for Advanced Encryption Standard.

Although I haven’t personally seen it used anywhere, it’s encumbered by patents in the USA and until the patent expires or RSA security yield all royalty rights, we’re unlikely to see it used in many applications.

Jacob Applebaum alleged in a presentation To Protect And Infect at the 30th Chaos Communication Conference that it’s currently being used or was used by the US military for spyware.

The following assembly code was a joint effort between Peter Ferrie and myself.

Key Expansion

void rc6_setkey (RC6_KEY *key, void *K, uint32_t keylen)
{  
  uint32_t i, j, k, A, B, L[8], *kptr=(uint32_t*)K; 
  
  // initialize L with key
  for (i=0; i<keylen/4; i++) {
    L[i] = kptr[i];
  }
  
  A=RC6_P;
  
  // initialize S with constants
  for (i=0; i<RC6_KR; i++) {
    key->x[i] = A;
    A += RC6_Q;
  }
  
  A=B=i=j=k=0;
  
  // mix with key
  for (; k < RC6_KR*3; k++)
  { 
    A = key->x[i] = ROTL32(key->x[i] + A+B, 3);  
    B = L[j]      = ROTL32(L[j] + A+B, A+B);
    
    i++;
    i %= RC6_KR;
    
    j++;
    j %= keylen/4;
  } 
}
_rc6_setkeyx:
rc6_setkey:
    pushad
    lea    esi, [esp+32+ 4]
    lodsd
    xchg   edx, eax            ; rc6key
    lodsd
    xchg   ecx, eax
    lodsd
    xchg   ecx, eax            ; keylen
    xchg   esi, eax            ; key
    
    sub    esp, ecx
    mov    edi, esp
    
    shr    ecx, 2              ; /= 4
    mov    ebx, ecx            ; save keylen/4
    ; copy key to local buffer
    rep    movsd

    mov    eax, RC6_P
    mov    esi, edx
    mov    edi, edx
    mov    cl, RC6_KR
init_key:
    stosd
    add    eax, RC6_Q
    loop   init_key
    
    xor    edi, edi    ; i=0
    xor    ebp, ebp    ; j=0
    xchg   ecx, eax    ; A=0
    cdq                ; B=0
    mov    ch, (-RC6_KR*3) & 255

sk_l1:
    ; A = key->S[i] = ROTL(key->S[i] + A+B, 3); 
    add    eax, edx
    add    eax, [esi+edi*4]
    rol    eax, 3
    mov    [esi+edi*4], eax
    ; B = L[j] = ROTL(L[j] + A+B, A+B);
    add    edx, eax
    mov    cl, dl
    add    edx, [esp+4*ebp]
    rol    edx, cl
    mov    [esp+4*ebp], edx

    ; i++
    inc    edi          
    ; i %= (RC6_ROUNDS*2)+4
    cmp    edi, RC6_KR  
    jb     sk_l2
    xor    edi, edi

sk_l2:    
    ; j++
    inc    ebp       
    ; j %= RC6_KEYLEN/4
    cmp    ebp, ebx
    jb     sk_l3
    xor    ebp, ebp

sk_l3:
    inc    ch
    jnz    sk_l1
      
    lea    esp, [esp+ebx*4]
    popad
    ret

Encryption/Decryption

By inverting bits of key, it may be possible to perform encryption/decryption with same code but for now, it just depends on flag what code executes. Maybe later this can be reduced much further.

void rc6_crypt (RC6_KEY *key, void *input, void *output, int enc)
{
  rc6_blk *in, *out;
  uint32_t A, B, C, D, T0, T1, i;
  uint32_t *k=(uint32_t*)key->x;
  
  in =(rc6_blk*)input;
  out=(rc6_blk*)output;
  
  // load plaintext/ciphertext
  A=in->v32[0];
  B=in->v32[1];
  C=in->v32[2];
  D=in->v32[3];
  
  if (enc==RC6_ENCRYPT)
  {
    B += *k; k++;
    D += *k; k++;
  } else {
    k += 43;
    C -= *k; k--;
    A -= *k; k--;
  }
  
  for (i=0; i<RC6_ROUNDS; i++)
  {
    if (enc==RC6_ENCRYPT)
    {
      T0 = ROTL32(B * (2 * B + 1), 5);
      T1 = ROTL32(D * (2 * D + 1), 5);
      
      A = ROTL32(A ^ T0, T1) + *k; k++;
      C = ROTL32(C ^ T1, T0) + *k; k++;
      // rotate 32-bits to the left
      T0 = A;
      A  = B;
      B  = C;
      C  = D;
      D  = T0;
    } else {
      T0 = ROTL32(A * (2 * A + 1), 5);
      T1 = ROTL32(C * (2 * C + 1), 5); 
      
      B  = ROTR32(B - *k, T0) ^ T1; k--;
      D  = ROTR32(D - *k, T1) ^ T0; k--;
      // rotate 32-bits to the right
      T0 = D;
      D  = C;
      C  = B;
      B  = A;
      A  = T0;
    }
  }
  
  if (enc==RC6_ENCRYPT)
  {
    A += *k; k++;
    C += *k; k++;
  } else {
    D -= *k; k--;
    B -= *k; k--;
  }
  // save plaintext/ciphertext
  out->v32[0]=A;
  out->v32[1]=B;
  out->v32[2]=C;
  out->v32[3]=D;
}

The assembly code makes use of direction flag for moving key forwards or backwards depending on enc variable.

%define A esi
%define B ebx
%define C edx
%define D ebp

_rc6_cryptx:
rc6_crypt:
    pushad

    mov    edi, [esp+32+4] ; rc6 key
    mov    esi, [esp+32+8] ; input
    
    ; load ciphertext
    lodsd
    xchg   eax, D
    lodsd
    xchg   eax, B
    lodsd
    xchg   eax, C
    lodsd
    xchg   eax, D
    xchg   eax, A
    
    push   RC6_ROUNDS
    pop    eax
    mov    ecx, [esp+32+16] ; enc
    jecxz  r6c_l1
    
    ; B += key->x[0];
    add    B, [edi]
    scasd
    ; D += key->x[1];
    add    D, [edi]
    jmp    r6c_l2

r6c_l1:
    ; move to end of key
    lea    edi, [edi+eax*8+12]
    ; load backwards
    std
    
    ; C -= key->x[43];
    sub    C, [edi]
    ; A -= key->x[42];
    scasd
    sub    A, [edi]
    xchg   D, A
    xchg   C, B

r6c_l2:
    scasd
r6c_l3:
    push   eax
    push   ecx
    dec    ecx
    pushfd
    
    ; T0 = ROTL(B * (2 * B + 1), 5);
    lea    eax, [B+B+1]
    imul   eax, B
    rol    eax, 5
    ; T1 = ROTL(D * (2 * D + 1), 5);
    lea    ecx, [D+D+1]
    imul   ecx, D
    rol    ecx, 5
    popfd
    jnz    r6c_l4

    ; A = ROTL(A ^ T0, T1) + key->x[i];
    xor    A, eax
    rol    A, cl
    add    A, [edi]  ; key->x[i]
    scasd
    ; C = ROTL(C ^ T1, T0) + key->x[i+1];
    xor    C, ecx
    xchg   eax, ecx
    rol    C, cl
    add    C, [edi]  ; key->x[i+1]
    jmp    r6c_l5
r6c_l4:    
    ; B = ROTR(B - key->x[i + 1], t) ^ u;
    sub    C, [edi]
    scasd
    ror    C, cl   ; t
    xor    C, eax  ; u
    ; D = ROTR(D - key->x[i], u) ^ t;
    xchg   eax, ecx ; swap u and t
    sub    A, [edi]
    ror    A, cl   ; u
    xor    A, eax  ; t
r6c_l5:
    scasd
    ; swap
    xchg   D, eax
    xchg   C, eax
    xchg   B, eax
    xchg   A, eax
    xchg   D, eax
    ; decrease counter
    pop    ecx
    pop    eax
    dec    eax    ; _I--
    jnz    r6c_l3

    jecxz  r6c_l6
    ; out[0] += key->x[42];
    add    A, [edi]
    ; out[2] += key->x[43];
    add    C, [edi+4]
    jmp    r6c_l7
r6c_l6:
    xchg   D, A
    xchg   C, B
    ; out[3] -= key->x[1];
    sub    D, [edi]
    ; out[1] -= key->x[0];
    sub    B, [edi-4]
    cld
    
r6c_l7:
    ; save ciphertext
    mov    edi, [esp+32+12] ; output
    xchg   eax, A
    stosd
    xchg   eax, B
    stosd
    xchg   eax, C
    stosd
    xchg   eax, D
    stosd
    popad
    ret

Results

Impressive where size is constrained.

architecture size
x86 247
x64 n/a

Check out sources here and here

Compiling with: cl /Os /O2 /Gr /Oy- /Fa /c /GS- rc6.c results in ~400 bytes

If you didn’t care about performance and specifically need a lightweight cipher with good security. Increase the rounds and this is a winner.

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

One Response to Asmcodes: RC6 Block cipher

  1. Pingback: Asmcodes: Serpent | Odzhan

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s