Asmcodes: Blowfish block cipher

Introduction

Blowfish is a 64-bit block symmetric cipher supporting keys up to 448-bits. It was designed and published in 1994 by American cryptgrapher Bruce Schneier and intended as a drop-in replacement for DES which many at the time suspected of being insecure against government agencies such as the NSA.

Key setup

int bf_setkey (BF_KEY *key, void* input, size_t len)
{
  int i, j, k_idx=0;
  BF_LONG ri, in[2];
  uint8_t *data=(uint8_t*)input;

  // init key
  memcpy (key, &bf_init, sizeof (BF_KEY));

  // keys should be at least 4-bytes
  if (len < BF_KEY_MIN) return 0;
  
  // no more than 56-bytes
  len=(len > BF_KEY_MAX) ? BF_KEY_MAX : len;
  
  // mix key bytes with bf key
  for (i=0; i<(BF_ROUNDS+2); i++) {
    ri=0;
    for (j=0; j<4; j++) {
      ri <<= 8;
      ri |= data[k_idx++ % len];
    }
    key->p[i] ^= ri;
  }

  in[0] = 0L;
  in[1] = 0L;
  
  // encrypt key
  for (i = 0; i < sizeof(BF_KEY)/sizeof(BF_LONG); i += 2) {
    bf_encrypt(key, in, in);
    key->p[i+0] = SWAP32(in[0]);
    key->p[i+1] = SWAP32(in[1]);
  }
  return 1;
}

Assembly..

_bf_setkey:
bf_setkey:
    pushad

    mov    edx, [esp+32+4]  ; key
    
    ; memcpy (key, &bf_init, sizeof (BF_KEY));
    mov    edi, edx
    lea    esi, [bf_init]
    mov    ecx, BF_KEY_size / 4
    rep    movsd
    ; ============================
    mov    esi, [esp+32+ 8]  ; input
    mov    ebx, [esp+32+12]  ; keylen
    mov    edi, edx          ; bf_key
    xor    edx, edx
    push   BF_ROUNDS+2
    pop    ecx
    push   edi
mix_key:
    push   ecx
    push   4
    pop    ecx
    xor    eax, eax
load_key_word:
    ; ri <<= 8;
    shl    eax, 8
    ; ri |= k[k_idx++ % len];
    or     al, byte [esi+edx]
    inc    edx
    cmp    edx, ebx
    sbb    ebp, ebp
    and    edx, ebp
    loop   load_key_word
    pop    ecx
    ; p[i] ^= ri;
    xor    [edi], eax
    scasd
    loop   mix_key
    pop    edi
    mov    ebx, edi
    ; ==============================
    xor    eax, eax
    push   eax       ; in[0] = 0
    push   eax       ; in[1] = 0
    mov    esi, esp
    mov    ecx, BF_KEY_size / 8
encrypt_key:
    ; bf_encrypt(key, in, in);
    push   esi         ; in
    push   esi         ; in
    push   ebx         ; key
    call   bf_encrypt
    add    esp, 3*4
    ; p[i+0] = bswap(in[0]);
    mov    eax, [esi]
    bswap  eax
    stosd
    ; p[i+1] = bswap(in[1]);
    mov    eax, [esi+4]
    bswap  eax
    stosd
    loop   encrypt_key
    ; release in variable
    pop    eax
    pop    eax
    
    popad
    ret

Round Function

void bf_round (BF_KEY *key, BF_LONG *l, BF_LONG *r, int i) {
  BF_LONG tl=*l, tx;
  
  tl ^= key->p[i];
  tx  = key->sbox1[((tl >> 24) & 0xFF)];
  tx += key->sbox2[((tl >> 16) & 0xFF)];
  tx ^= key->sbox3[((tl >>  8) & 0xFF)];
  tx += key->sbox4[((tl      ) & 0xFF)];
  tx ^= *r;
  *r = tl;
  *l = tx;
}

Encrypting

// encrypt 8 bytes / 64-bits of plain text
void bf_encrypt (BF_KEY *key, void* input, void* output)
{
  BF_LONG l, r, *in, *out;
  int i;
  
  in  = (BF_LONG*)input;
  out = (BF_LONG*)output;
  
  l = SWAP32(in[0]);
  r = SWAP32(in[1]);

  for (i=0; i<BF_ROUNDS; i++) {
    bf_round (key, &l, &r, i);
  }
  
  l ^= key->p[BF_ROUNDS];
  r ^= key->p[BF_ROUNDS+1];

  out[0] = SWAP32(r);
  out[1] = SWAP32(l);
}
; perform main round of blowfish
bf_round:
    ; l ^= key->p[i];
    xor  l, [esi+4*ebp+p]
    mov  eax, l
    rol  eax, 16
    ; t  = key->sbox1[((l >> 24) & 0xFF)];
    mov  dl, ah
    mov  t, [esi+4*edx+sbox1]
    ; t += key->sbox2[((l >> 16) & 0xFF)];
    mov  dl, al
    add  t, [esi+4*edx+sbox2]
    ; t ^= key->sbox3[((l >>  8) & 0xFF)];
    mov  dl, bh
    xor  t, [esi+4*edx+sbox3]
    ; t += key->sbox4[((l      ) & 0xFF)];
    mov  dl, bl
    add  t, [esi+4*edx+sbox4]
    xor  r, t
    xchg r, l
    ret
    
_bf_encrypt:
bf_encrypt:
    pushad
    
    mov    esi, [esp+32+8] ; input
    
    ; load plaintext
    
    ; l = in[0];
    lodsd
    bswap  eax
    xchg   eax, l
    
    ; r = in[1];
    lodsd
    bswap  eax
    xchg   eax, r
    
    mov    esi, [esp+32+4] ; key
    
    xor    ebp, ebp
    xor    edx, edx

enc_loop:
    call   bf_round
    inc    ebp
    cmp    ebp, BF_ROUNDS
    jnz    enc_loop
    
    xor    l, [esi+BF_ROUNDS*4+p]
    xor    r, [esi+(BF_ROUNDS+1)*4+p]
    
    ; save
    mov    edi, [esp+32+12]
    
    ; out[0] = r;
    xchg   eax, r
    bswap  eax
    stosd
    
    ; out[1] = l;
    xchg   eax, l
    bswap  eax
    stosd
    
    popad
    ret

Results

architecture size
x86 4,424

Conclusion

I like blowfish because it withstands most cryptanalytic attacks but since the p and s boxes were generated randomly, it’s unsuitable for low resource devices. That said, one might be able to modify existing algorithm to generate those sboxes.

Incidentally, HC-256 stream cipher uses a similar round function to generate sboxes but is still unsuitable for some resource constrained devices.

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 )

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