CHAM Block Cipher

Introduction

CHAM: A Family of Lightweight Block Ciphers for Resource-Constrained Devices was published in December 2017 at the 20th Annual International Conference on Information Security and Cryptology held in South Korea.

CHAM consists of three ciphers, CHAM-64/128, CHAM-128/128, and CHAM-128/256 which are based on the Generalized Feistel Network (GFN) structure.

This post will focus on CHAM-128/128 which is the 128-bit block cipher with 128-bit key variant operating on 4 branches of 32 bits each. The only operations used are 32-bit modular addition, Rotation and XOR (ARX)

The design of CHAM draws inspiration from Speck and Simon block ciphers by the NSA. A cursory glance of the algorithm would suggest CHAM is not ideal for hardware due to its use of modular addition which is inefficient to implement on hardware.

Take this quote from the designers of the permutation function Keccak:

..the designer of an adder must choose between complexity (area, consumption) or gate delay (latency): It is either compact or fast, but not at the same time

Here are parameters for all 3 variants. N is the block length, K is the key length, R is the number of rounds, W is the width of a word and K/W is the number of words per key.

Key schedule

For the 128-bit version, there are 8 round keys of 32-bits each, or 32-bytes in total.

void cham128_setkey(void *in, void *out)
{
    int i;
    uint32_t *k=(uint32_t*)in;
    uint32_t *rk=(uint32_t*)out;

    for (i=0; i<KW; i++) {
      rk[i] = k[i] ^ ROTL32(k[i], 1) ^ ROTL32(k[i], 8);
      rk[(i + KW) ^ 1]	= k[i] ^ ROTL32(k[i], 1) ^ ROTL32(k[i], 11);
    }
}

The assembly may not be completely optimized here, but it’s best I can do at the moment.

%define K 128   ; key length
%define N 128   ; block length
%define R 80    ; number of rounds
%define W 32    ; word length
%define KW K/W  ; number of words per key
     
cham128_setkeyx:
_cham128_setkeyx:
    pushad
    mov    esi, [esp+32+4]  ; k  = in
    mov    edi, [esp+32+8]  ; rk = out    
    xor    eax, eax         ; i  = 0
sk_l0:
    mov    ebx, [esi+eax*4] ; ebx = k[i]
    mov    ecx, ebx         ; ecx = k[i]
    mov    edx, ebx         ; edx = k[i]    
    rol    ebx, 1           ; ROTL32(k[i], 1)
    rol    ecx, 8           ; ROTL32(k[i], 8)    
    xor    edx, ebx         ; k[i] ^ ROTL32(k[i], 1) 
    xor    edx, ecx    
    mov    [edi+eax*4], edx ; rk[i] = edx
    xor    edx, ecx         ; reset edx
    rol    ecx, 3           ; k[i] ^ ROTL32(k[i], 11)
    xor    edx, ecx    
    lea    ebx, [eax+KW]
    xor    ebx, 1
    mov    [edi+ebx*4], edx ; rk[(i + KW) ^ 1] = edx
    inc    al
    cmp    al, KW
    jnz    sk_l0    
    popad
    ret

Encryption

There are 80 rounds in total, which is significantly more than the 32 used for Speck.

void cham128_encrypt(void *keys, void *data)
{
    int i;
    uint32_t x0, x1, x2, x3;
    uint32_t t;
    uint32_t *rk=(uint32_t*)keys;
    uint32_t *x=(uint32_t*)data;
    
    x0 = x[0]; x1 = x[1];
    x2 = x[2]; x3 = x[3];

    for (i=0; i<R; i++)
    {
      if ((i & 1) == 0) {
        x0 = ROTL32((x0 ^ i) + (ROTL32(x1, 1) ^ rk[i & 7]), 8);
      } else {
        x0 = ROTL32((x0 ^ i) + (ROTL32(x1, 8) ^ rk[i & 7]), 1);
      }
      XCHG(x0, x1);
      XCHG(x1, x2);
      XCHG(x2, x3);
    }
    x[0] = x0; x[1] = x1;
    x[2] = x2; x[3] = x3;
}

Only the encryption here, since if you were to implement with CTR mode, decryption isn’t necessary.

%define x0 ebp
%define x1 ebx
%define x2 edx
%define x3 esi
%define rk edi

cham128_encryptx:
_cham128_encryptx:
    pushad
    mov    esi, [esp+32+8] ; x = data
    push   esi
    lodsd
    xchg   eax, x0
    lodsd
    xchg   eax, x1
    lodsd
    xchg   eax, x2
    lodsd
    xchg   eax, x3
    xor    eax, eax ; i = 0
    ; initialize sub keys
enc_l0: 
    mov    edi, [esp+32+8] ; k = keys
    jmp    enc_lx    
enc_l1:
    test   al, 7    ; i & 7
    jz     enc_l0
enc_lx:    
    push   eax      ; save i
    mov    cx, 0x0108
    test   al, 1    ; if ((i & 1)==0)
    jnz    enc_l2
    
    xchg   cl, ch
enc_l2:
    xor    x0, eax          ; x0 ^= i
    mov    eax, x1
    rol    eax, cl          ; 
    xor    eax, [edi]       ; ROTL32(x1, r0) ^ *rk++
    scasd
    add    x0, eax
    xchg   cl, ch
    rol    x0, cl
    
    xchg   x0, x1          ; XCHG(x0, x1);
    xchg   x1, x2          ; XCHG(x1, x2);
    xchg   x2, x3          ; XCHG(x2, x3);
    
    pop    eax      ; restore i
    inc    al       ; i++
    cmp    al, R    ; i<R
    jnz    enc_l1
    
    pop    edi
    xchg   eax, x0
    stosd           ; x[0] = x0;
    xchg   eax, x1
    stosd           ; x[1] = x1;
    xchg   eax, x2
    stosd           ; x[2] = x2;
    xchg   eax, x3
    stosd           ; x[3] = x3;
    popad
    ret

The total size of assembly at moment is 128 bytes, although I will try optimize more later.

Summary

CHAM is a relatively new block cipher clearly influenced by block ciphers Speck and Simon. Although the strong variants of Speck and Simon remain unbroken, that hasn’t prevented some in the cryptographic community being cynical about the intentions of the NSA.

Orr Dunkelman, a computer science professor at the University of Haifa commented. “I don’t trust the designers” and “There are quite a lot of people in NSA who think their job is to subvert standards. My job is to secure standards.”

Daniel Bernstein also commented: NSA says:We need a “generalist” cipher that works well everywhere, so here are 20 incompatible Simon+Speck variants https://eprint.iacr.org/2015/585

As most of the attacks appear ad-hominem, is it fair to dismiss Speck and Simon even when the rationale behind the designs have been published?

When asked if it could beat Simon and Speck encryption, NSA officials are reported to have said: “We firmly believe they are secure.” which neither confirms nor denies NSA can break these type of ciphers.

Then again, if the NSA are capable of breaking Speck and Simon, they may also know how to break other ARX designs like ChaCha, LEA and CHAM?

A final vote on whether Speck/Simon are accepted as part of an ISO standard takes place in February 2018.

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

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

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