Password Algorithms: AOL Instant Messenger

Introduction

AOL instant messenger is used by 0.73% of IM market according to OPSWAT
It’s still in development and because of changes in how the password is stored, this analysis will be presented in 2 entries.

Storage

In 6.x, when a user checks the ‘Save Password’ box, the application will store theĀ currentĀ username and password in NTUSER.DAT

From command prompt, you can run REG.exe to dump the entries.

C:\reg query "HKCU\Software\America Online\AIM6\Passwords"

HKEY_CURRENT_USER\Software\America Online\AIM6\Passwords
    joe.bloggs@emaildomain.com  REG_SZ  zo+VVoi9LWCtc0B8z9ZnfojNdjVuv08DXid8yK++LYI=

Based on the characters in the string, it appears to be base64 encoded.
Here, i’m using openssl and redirect the output to a file before hexdumping.

echo zo+VVoi9LWCtc0B8z9ZnfojNdjVuv08DXid8yK++LYI= | openssl enc -base64 -d > aim.bin & hexdump aim.bin

00000000: ce 8f 95 56 88 bd 2d 60 - ad 73 40 7c cf d6 67 7e ...V.... .s....g.
00000010: 88 cd 76 35 6e bf 4f 03 - 5e 27 7c c8 af be 2d 82 ..v5n.O. ........
00000020: 82

This doesn’t appear to contain anything intelligible to the eye so we’ll need to look deeper in the application itself.

Generation

After some digging in the binaries, the blob stored in the registry contains a salt and ciphertext derived from Blowfish, here’s the structure.

#define MAX_SALT_LEN 8
#define MAX_PASS_LEN 16

typedef struct _AIM_PASSWORD_BLOB {
  u8 Salt[MAX_SALT_LEN];
  u8 Password[2*MAX_PASS_LEN+1];
} AIM_PASSWORD_BLOB, *PAIM_PASSWORD_BLOB;

The password is stored in UNICODE format.
The salt is generated by first initializing the seed to current time, then calling rand() 8 times to fill 64-bit buffer.
Everytime the user logs in and out, the password entry is updated with new salt.

// generate 64-bit salt using time(0) as seed
void gen_salt(PAIM_PASSWORD_BLOB pBlob) {
    srand(time(0));

    for (int i = 0; i < MAX_SALT_LEN; i++) {
      pBlob->Salt[i] = rand() & 0xff;
    }
}

Blowfish has a variable key length and the encryption algorithm uses all 448-bits of key to encrypt the users password.
Below only illustrates how the static key is created.

// used to create the 56 bytes of key
const u8 aim_kbox[256] =
  { 0x59, 0x3a, 0x7c, 0x77, 0xf3, 0x2b, 0xab, 0x1f,
    0x99, 0x98, 0x86, 0x6c, 0x59, 0xaa, 0x9d, 0x7f,
    0x58, 0x3f, 0x6a, 0xb9, 0x0b, 0x47, 0x29, 0x35,
    0xaa, 0x6d, 0xea, 0x95, 0xe2, 0xfb, 0xe4, 0x02,
    0xcb, 0xf7, 0x0c, 0x6e, 0x19, 0x92, 0xe6, 0x1c,
    0x96, 0xc4, 0x9b, 0x63, 0xd0, 0x30, 0x4d, 0xaf,
    0x0e, 0x4d, 0xa7, 0xc8, 0x89, 0xc7, 0xb8, 0x57,
    0xd9, 0x23, 0x01, 0xa6, 0xae, 0xa3, 0xcc, 0xa7,
    0xc0, 0x69, 0xc0, 0x38, 0x09, 0xde, 0xb3, 0xa5,
    0x31, 0x55, 0xbf, 0x6e, 0x4a, 0xec, 0x98, 0x4b,
    0xbd, 0xb3, 0x1c, 0x6e, 0x84, 0x11, 0x2c, 0x08,
    0x9a, 0x63, 0xbb, 0x0e, 0xb0, 0xe5, 0x24, 0x3d,
    0x22, 0xd6, 0xc1, 0x5c, 0x29, 0xd7, 0xb9, 0xc1,
    0x52, 0x95, 0x19, 0x16, 0x2f, 0xa7, 0x27, 0x5d,
    0x4c, 0xba, 0xf3, 0x32, 0x64, 0xeb, 0x2e, 0x50,
    0xd5, 0x74, 0x3f, 0x57, 0x52, 0x8b, 0x94, 0xcd,
    0xd8, 0x87, 0x36, 0x62, 0xe3, 0x45, 0xa1, 0x78,
    0xe1, 0xca, 0xd2, 0xe2, 0xe7, 0x29, 0xa1, 0xec,
    0xa3, 0xa7, 0x51, 0x9c, 0x92, 0x1e, 0x66, 0x38,
    0x72, 0x9f, 0xb6, 0x08, 0xfb, 0x5b, 0xc3, 0x5d,
    0xca, 0xc4, 0x48, 0xd3, 0x9e, 0xef, 0x12, 0xd2,
    0xc6, 0x3d, 0x11, 0x5b, 0xda, 0x3a, 0xaf, 0x01,
    0xaa, 0xc5, 0x60, 0x35, 0x74, 0x72, 0x7b, 0xc7,
    0x5a, 0x2c, 0x48, 0xaa, 0x12, 0x1f, 0x5a, 0xf8,
    0xe0, 0xd5, 0x1f, 0x35, 0xc1, 0x9e, 0xb5, 0xd8,
    0xe9, 0x36, 0xff, 0x07, 0x70, 0xa2, 0xf9, 0xa3,
    0x49, 0x5b, 0x48, 0x84, 0x73, 0xae, 0x16, 0x06,
    0x73, 0x63, 0x1c, 0xc4, 0x01, 0x9d, 0x00, 0xa3,
    0x02, 0x01, 0xe2, 0x13, 0xb6, 0x1a, 0x32, 0x91,
    0x33, 0xfc, 0xc4, 0x70, 0x12, 0x28, 0x26, 0xda,
    0x68, 0xb0, 0x31, 0x12, 0xf8, 0x9c, 0xde, 0xfb,
    0xa6, 0x8b, 0x5b, 0xde, 0x2f, 0x9e, 0x5e, 0x68 };

#define SWAP(x, y) u8 t; t = x;x = y;y = t;

void gen_static_key(u8 output[]) {

  u8 kbox[256];

  memcpy(kbox, aim_kbox, sizeof(aim_kbox));

  for (int i = 0; i < 128; i++) {
    SWAP(kbox[ kbox[i] ], kbox[ kbox[i+1] ])
  }
  memcpy(output, kbox, 56);
}

The end result of gen_static_key() is a 56-byte blowfish key.
The user’s 8-byte salt will replace the first 8-bytes of this static key before being passed to BF_set_key()

It’s not necessary to use gen_static_key() after the first time since it doesn’t use any entropy at all.

Recovery

The final decoding routine using C++ looks something like:

#define MAX_SALT_LEN 8
#define MAX_PASS_LEN 16
#define MAX_KEY_LEN 56

typedef struct _AIM_PASSWORD_BLOB {
  u8 Salt[MAX_SALT_LEN];
  u8 Password[2*MAX_PASS_LEN+1];
} AIM_PASSWORD_BLOB, *PAIM_PASSWORD_BLOB;

void base64_decode(PAIM_PASSWORD_BLOB output, char blob_string[]) {
    BIO *b64, *mem;

    b64 = BIO_new(BIO_f_base64());
    BIO_set_flags(b64, BIO_FLAGS_BASE64_NO_NL);
    mem = BIO_new_mem_buf(blob_string, strlen(blob_string));
    mem = BIO_push(b64, mem);

    BIO_read(mem, output, strlen(blob_string));
    BIO_free_all(mem);
}

const u8 static_key[48] =
  { 0x99, 0x00, 0x86, 0xa5, 0x27, 0xaa, 0x9d, 0x7f,
    0x58, 0xaa, 0xae, 0xb9, 0x0b, 0x47, 0x3a, 0x35,
    0xaa, 0xe0, 0xea, 0x95, 0x66, 0xfb, 0xe4, 0x9f,
    0xcb, 0xf7, 0x16, 0x1c, 0xa3, 0x92, 0xe6, 0x1c,
    0x96, 0x06, 0x9b, 0x5b, 0x29, 0x30, 0xbf, 0xaf,
    0xec, 0x11, 0x29, 0xc8, 0x89, 0x5b, 0xb8, 0x57 };

std::wstring AIM_Decrypt(char base64_blob[]) {
    BF_KEY key;
    u8 aim_key[MAX_KEY_LEN];
    AIM_PASSWORD_BLOB blob;
    wchar_t password[2*MAX_PASS_LEN+1];

    memset(&blob, 0, sizeof(AIM_PASSWORD_BLOB));
    memset(password, 0, sizeof(password));

    base64_decode(&blob, base64_blob);

    memcpy(&aim_key, blob.Salt, MAX_SALT_LEN);
    memcpy(&aim_key[MAX_SALT_LEN], static_key, sizeof(static_key));

    BF_set_key(&key, sizeof(aim_key), aim_key);

    BF_LONG *in = (BF_LONG*)blob.Password;
    BF_LONG *out = (BF_LONG*)password;

    for (int i = 0;i < MAX_PASS_LEN * 2 / sizeof(BF_LONG);i += 2) {
      memcpy(&out[i], &in[i], sizeof(BF_LONG)*2);
      BF_decrypt(&out[i], &key);
    }
    return std::wstring(password);
}

The string returned from AIM_Decrypt is in UNICODE format.

Conclusion

This protection isn’t great since you could easily decrypt entries just by reading NTUSER.DAT in the windows profile of AIM user.

A better solution might be CryptProtectData() and Base64.

Comments and questions welcome.