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

Summary

architecture size
x86 4,424

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.

See 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 )

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