diff --git a/Android.mk b/Android.mk
index 71113df..ba9b0a1 100644
--- a/Android.mk
+++ b/Android.mk
@@ -22,7 +22,8 @@
 common_c_includes := \
 	$(KERNEL_HEADERS) \
 	system/extras/ext4_utils \
-	external/openssl/include
+	external/openssl/include \
+	external/scrypt/lib/crypto
 
 common_shared_libraries := \
 	libsysutils \
@@ -33,6 +34,10 @@
 	liblogwrap \
 	libcrypto
 
+common_static_libraries := \
+	libfs_mgr \
+	libscrypt_static
+
 include $(CLEAR_VARS)
 
 LOCAL_MODULE := libvold
@@ -43,7 +48,7 @@
 
 LOCAL_SHARED_LIBRARIES := $(common_shared_libraries)
 
-LOCAL_STATIC_LIBRARIES := libfs_mgr
+LOCAL_STATIC_LIBRARIES := $(common_static_libraries)
 
 LOCAL_MODULE_TAGS := eng tests
 
@@ -63,7 +68,7 @@
 
 LOCAL_SHARED_LIBRARIES := $(common_shared_libraries)
 
-LOCAL_STATIC_LIBRARIES := libfs_mgr
+LOCAL_STATIC_LIBRARIES := $(common_static_libraries)
 
 include $(BUILD_EXECUTABLE)
 
diff --git a/cryptfs.c b/cryptfs.c
index fd3246b..bad5d8a 100644
--- a/cryptfs.c
+++ b/cryptfs.c
@@ -47,6 +47,7 @@
 #include "hardware_legacy/power.h"
 #include "VolumeManager.h"
 #include "VoldUtil.h"
+#include "crypto_scrypt.h"
 
 #define DM_CRYPT_BUF_SIZE 4096
 #define DATA_MNT_POINT "/data"
@@ -85,6 +86,55 @@
     }
 }
 
+/**
+ * Gets the default device scrypt parameters for key derivation time tuning.
+ * The parameters should lead to about one second derivation time for the
+ * given device.
+ */
+static void get_device_scrypt_params(struct crypt_mnt_ftr *ftr) {
+    const int default_params[] = SCRYPT_DEFAULTS;
+    int params[] = SCRYPT_DEFAULTS;
+    char paramstr[PROPERTY_VALUE_MAX];
+    char *token;
+    char *saveptr;
+    int i;
+
+    property_get(SCRYPT_PROP, paramstr, "");
+    if (paramstr[0] != '\0') {
+        /*
+         * The token we're looking for should be three integers separated by
+         * colons (e.g., "12:8:1"). Scan the property to make sure it matches.
+         */
+        for (token = strtok_r(paramstr, ":", &saveptr); token != NULL && i < 3;
+                i++, token = strtok_r(NULL, ":", &saveptr)) {
+            char *endptr;
+            params[i] = strtol(token, &endptr, 10);
+
+            /*
+             * Check that there was a valid number and it's 8-bit. If not,
+             * break out and the end check will take the default values.
+             */
+            if ((*token == '\0') || (*endptr != '\0') || params[i] < 0 || params[i] > 255) {
+                break;
+            }
+        }
+
+        /*
+         * If there were not enough tokens or a token was malformed (not an
+         * integer), it will end up here and the default parameters can be
+         * taken.
+         */
+        if ((i != 3) || (token != NULL)) {
+            SLOGW("bad scrypt parameters '%s' should be like '12:8:1'; using defaults", paramstr);
+            memcpy(params, default_params, sizeof(params));
+        }
+    }
+
+    ftr->N_factor = params[0];
+    ftr->r_factor = params[1];
+    ftr->p_factor = params[2];
+}
+
 static unsigned int get_fs_size(char *dev)
 {
     int fd, block_size;
@@ -257,6 +307,8 @@
         struct crypt_persist_data *pdata;
         off64_t pdata_offset = offset + CRYPT_FOOTER_TO_PERSIST_OFFSET;
 
+        SLOGW("upgrading crypto footer to 1.1");
+
         pdata = malloc(CRYPT_PERSIST_DATA_SIZE);
         if (pdata == NULL) {
             SLOGE("Cannot allocate persisent data\n");
@@ -283,6 +335,13 @@
         crypt_ftr->minor_version = 1;
     }
 
+    if ((crypt_ftr->major_version == 1) && (crypt_ftr->minor_version)) {
+        SLOGW("upgrading crypto footer to 1.2");
+        crypt_ftr->kdf_type = KDF_PBKDF2;
+        get_device_scrypt_params(crypt_ftr);
+        crypt_ftr->minor_version = 2;
+    }
+
     if ((orig_major != crypt_ftr->major_version) || (orig_minor != crypt_ftr->minor_version)) {
         if (lseek64(fd, offset, SEEK_SET) == -1) {
             SLOGE("Cannot seek to crypt footer\n");
@@ -793,24 +852,37 @@
 
 }
 
-static void pbkdf2(char *passwd, unsigned char *salt, unsigned char *ikey)
-{
+static void pbkdf2(char *passwd, unsigned char *salt, unsigned char *ikey, void *params) {
     /* Turn the password into a key and IV that can decrypt the master key */
     PKCS5_PBKDF2_HMAC_SHA1(passwd, strlen(passwd), salt, SALT_LEN,
                            HASH_COUNT, KEY_LEN_BYTES+IV_LEN_BYTES, ikey);
 }
 
+static void scrypt(char *passwd, unsigned char *salt, unsigned char *ikey, void *params) {
+    struct crypt_mnt_ftr *ftr = (struct crypt_mnt_ftr *) params;
+
+    int N = 1 << ftr->N_factor;
+    int r = 1 << ftr->r_factor;
+    int p = 1 << ftr->p_factor;
+
+    /* Turn the password into a key and IV that can decrypt the master key */
+    crypto_scrypt((unsigned char *) passwd, strlen(passwd), salt, SALT_LEN, N, r, p, ikey,
+            KEY_LEN_BYTES + IV_LEN_BYTES);
+}
+
 static int encrypt_master_key(char *passwd, unsigned char *salt,
                               unsigned char *decrypted_master_key,
-                              unsigned char *encrypted_master_key)
+                              unsigned char *encrypted_master_key,
+                              struct crypt_mnt_ftr *crypt_ftr)
 {
     unsigned char ikey[32+32] = { 0 }; /* Big enough to hold a 256 bit key and 256 bit IV */
     EVP_CIPHER_CTX e_ctx;
     int encrypted_len, final_len;
 
     /* Turn the password into a key and IV that can decrypt the master key */
-    pbkdf2(passwd, salt, ikey);
-  
+    get_device_scrypt_params(crypt_ftr);
+    scrypt(passwd, salt, ikey, crypt_ftr);
+
     /* Initialize the decryption engine */
     if (! EVP_EncryptInit(&e_ctx, EVP_aes_128_cbc(), ikey, ikey+KEY_LEN_BYTES)) {
         SLOGE("EVP_EncryptInit failed\n");
@@ -839,14 +911,15 @@
 
 static int decrypt_master_key(char *passwd, unsigned char *salt,
                               unsigned char *encrypted_master_key,
-                              unsigned char *decrypted_master_key)
+                              unsigned char *decrypted_master_key,
+                              kdf_func kdf, void *kdf_params)
 {
   unsigned char ikey[32+32] = { 0 }; /* Big enough to hold a 256 bit key and 256 bit IV */
   EVP_CIPHER_CTX d_ctx;
   int decrypted_len, final_len;
 
   /* Turn the password into a key and IV that can decrypt the master key */
-  pbkdf2(passwd, salt, ikey);
+  kdf(passwd, salt, ikey, kdf_params);
 
   /* Initialize the decryption engine */
   if (! EVP_DecryptInit(&d_ctx, EVP_aes_128_cbc(), ikey, ikey+KEY_LEN_BYTES)) {
@@ -869,8 +942,47 @@
   }
 }
 
-static int create_encrypted_random_key(char *passwd, unsigned char *master_key, unsigned char *salt)
+static void get_kdf_func(struct crypt_mnt_ftr *ftr, kdf_func *kdf, void** kdf_params)
 {
+    if (ftr->kdf_type == KDF_SCRYPT) {
+        *kdf = scrypt;
+        *kdf_params = ftr;
+    } else {
+        *kdf = pbkdf2;
+        *kdf_params = NULL;
+    }
+}
+
+static int decrypt_master_key_and_upgrade(char *passwd, unsigned char *decrypted_master_key,
+        struct crypt_mnt_ftr *crypt_ftr)
+{
+    kdf_func kdf;
+    void *kdf_params;
+    int ret;
+
+    get_kdf_func(crypt_ftr, &kdf, &kdf_params);
+    ret = decrypt_master_key(passwd, crypt_ftr->salt, crypt_ftr->master_key, decrypted_master_key, kdf,
+            kdf_params);
+    if (ret != 0) {
+        SLOGW("failure decrypting master key");
+        return ret;
+    }
+
+    /*
+     * Upgrade if we're not using the latest KDF.
+     */
+    if (crypt_ftr->kdf_type != KDF_SCRYPT) {
+        crypt_ftr->kdf_type = KDF_SCRYPT;
+        encrypt_master_key(passwd, crypt_ftr->salt, decrypted_master_key, crypt_ftr->master_key,
+                crypt_ftr);
+        put_crypt_ftr_and_key(crypt_ftr);
+    }
+
+    return ret;
+}
+
+static int create_encrypted_random_key(char *passwd, unsigned char *master_key, unsigned char *salt,
+        struct crypt_mnt_ftr *crypt_ftr) {
     int fd;
     unsigned char key_buf[KEY_LEN_BYTES];
     EVP_CIPHER_CTX e_ctx;
@@ -883,7 +995,7 @@
     close(fd);
 
     /* Now encrypt it with the password */
-    return encrypt_master_key(passwd, salt, key_buf, master_key);
+    return encrypt_master_key(passwd, salt, key_buf, master_key, crypt_ftr);
 }
 
 static int wait_and_unmount(char *mountpoint)
@@ -1085,6 +1197,8 @@
   unsigned int orig_failed_decrypt_count;
   char encrypted_state[PROPERTY_VALUE_MAX];
   int rc;
+  kdf_func kdf;
+  void *kdf_params;
 
   property_get("ro.crypto.state", encrypted_state, "");
   if ( master_key_saved || strcmp(encrypted_state, "encrypted") ) {
@@ -1103,7 +1217,7 @@
   orig_failed_decrypt_count = crypt_ftr.failed_decrypt_count;
 
   if (! (crypt_ftr.flags & CRYPT_MNT_KEY_UNENCRYPTED) ) {
-    decrypt_master_key(passwd, crypt_ftr.salt, crypt_ftr.master_key, decrypted_master_key);
+    decrypt_master_key_and_upgrade(passwd, decrypted_master_key, &crypt_ftr);
   }
 
   if (create_crypto_blk_dev(&crypt_ftr, decrypted_master_key,
@@ -1256,8 +1370,7 @@
         /* If the device has no password, then just say the password is valid */
         rc = 0;
     } else {
-        decrypt_master_key(passwd, crypt_ftr.salt, crypt_ftr.master_key,
-                           decrypted_master_key);
+        decrypt_master_key_and_upgrade(passwd, decrypted_master_key, &crypt_ftr);
         if (!memcmp(decrypted_master_key, saved_master_key, crypt_ftr.keysize)) {
             /* They match, the password is correct */
             rc = 0;
@@ -1287,6 +1400,9 @@
     ftr->ftr_size = sizeof(struct crypt_mnt_ftr);
     ftr->keysize = KEY_LEN_BYTES;
 
+    ftr->kdf_type = KDF_SCRYPT;
+    get_device_scrypt_params(ftr);
+
     ftr->persist_data_size = CRYPT_PERSIST_DATA_SIZE;
     if (get_crypt_ftr_info(NULL, &off) == 0) {
         ftr->persist_data_offset[0] = off + CRYPT_FOOTER_TO_PERSIST_OFFSET;
@@ -1592,7 +1708,7 @@
     strcpy((char *)crypt_ftr.crypto_type_name, "aes-cbc-essiv:sha256");
 
     /* Make an encrypted master key */
-    if (create_encrypted_random_key(passwd, crypt_ftr.master_key, crypt_ftr.salt)) {
+    if (create_encrypted_random_key(passwd, crypt_ftr.master_key, crypt_ftr.salt, &crypt_ftr)) {
         SLOGE("Cannot create encrypted master key\n");
         goto error_unencrypted;
     }
@@ -1614,7 +1730,7 @@
         save_persistent_data();
     }
 
-    decrypt_master_key(passwd, crypt_ftr.salt, crypt_ftr.master_key, decrypted_master_key);
+    decrypt_master_key_and_upgrade(passwd, decrypted_master_key, &crypt_ftr);
     create_crypto_blk_dev(&crypt_ftr, decrypted_master_key, real_blkdev, crypto_blkdev,
                           "userdata");
 
@@ -1762,7 +1878,7 @@
       return -1;
     }
 
-    encrypt_master_key(newpw, crypt_ftr.salt, saved_master_key, crypt_ftr.master_key);
+    encrypt_master_key(newpw, crypt_ftr.salt, saved_master_key, crypt_ftr.master_key, &crypt_ftr);
 
     /* save the key */
     put_crypt_ftr_and_key(&crypt_ftr);
diff --git a/cryptfs.h b/cryptfs.h
index bdbce80..421181e 100644
--- a/cryptfs.h
+++ b/cryptfs.h
@@ -49,8 +49,16 @@
 #define CRYPT_MNT_MAGIC 0xD0B5B1C4
 #define PERSIST_DATA_MAGIC 0xE950CD44
 
+#define SCRYPT_PROP "ro.crypto.scrypt_params"
+#define SCRYPT_DEFAULTS { 15, 3, 1 }
+
+/* Key Derivation Function algorithms */
+#define KDF_PBKDF2 1
+#define KDF_SCRYPT 2
+
 #define __le32 unsigned int
-#define __le16 unsigned short int 
+#define __le16 unsigned short int
+#define __le8  unsigned char
 
 struct crypt_mnt_ftr {
   __le32 magic;		/* See above */
@@ -75,6 +83,13 @@
 
   __le32 persist_data_size;       /* The number of bytes allocated to each copy of the
                                    * persistent data table*/
+
+  __le8  kdf_type; /* The key derivation function used. */
+
+  /* scrypt parameters. See www.tarsnap.com/scrypt/scrypt.pdf */
+  __le8  N_factor; /* (1 << N) */
+  __le8  r_factor; /* (1 << r) */
+  __le8  p_factor; /* (1 << p) */
 };
 
 /* Persistant data that should be available before decryption.
@@ -118,6 +133,9 @@
 #ifdef __cplusplus
 extern "C" {
 #endif
+
+  typedef void (*kdf_func)(char *passwd, unsigned char *salt, unsigned char *ikey, void *params);
+
   int cryptfs_crypto_complete(void);
   int cryptfs_check_passwd(char *pw);
   int cryptfs_verify_passwd(char *newpw);