diff --git a/services/backup/java/com/android/server/backup/BackupManagerService.java b/services/backup/java/com/android/server/backup/BackupManagerService.java
index 9277cce2..1e7c18a 100644
--- a/services/backup/java/com/android/server/backup/BackupManagerService.java
+++ b/services/backup/java/com/android/server/backup/BackupManagerService.java
@@ -83,7 +83,6 @@
 import com.android.internal.backup.IBackupTransport;
 import com.android.internal.backup.IObbBackupService;
 import com.android.server.EventLogTags;
-import com.android.server.SystemService;
 import com.android.server.backup.PackageManagerBackupAgent.Metadata;
 
 import java.io.BufferedInputStream;
@@ -142,11 +141,16 @@
     private static final boolean DEBUG = true;
     private static final boolean MORE_DEBUG = false;
 
+    // Historical and current algorithm names
+    static final String PBKDF_CURRENT = "PBKDF2WithHmacSHA1";
+    static final String PBKDF_FALLBACK = "PBKDF2WithHmacSHA1And8bit";
+
     // Name and current contents version of the full-backup manifest file
     static final String BACKUP_MANIFEST_FILENAME = "_manifest";
     static final int BACKUP_MANIFEST_VERSION = 1;
     static final String BACKUP_FILE_HEADER_MAGIC = "ANDROID BACKUP\n";
-    static final int BACKUP_FILE_VERSION = 1;
+    static final int BACKUP_FILE_VERSION = 2;
+    static final int BACKUP_PW_FILE_VERSION = 2;
     static final boolean COMPRESS_FULL_BACKUPS = true; // should be true in production
 
     static final String SHARED_BACKUP_AGENT_PACKAGE = "com.android.sharedstoragebackup";
@@ -452,6 +456,8 @@
     private final SecureRandom mRng = new SecureRandom();
     private String mPasswordHash;
     private File mPasswordHashFile;
+    private int mPasswordVersion;
+    private File mPasswordVersionFile;
     private byte[] mPasswordSalt;
 
     // Configuration of PBKDF2 that we use for generating pw hashes and intermediate keys
@@ -812,6 +818,27 @@
         }
         mDataDir = Environment.getDownloadCacheDirectory();
 
+        mPasswordVersion = 1;       // unless we hear otherwise
+        mPasswordVersionFile = new File(mBaseStateDir, "pwversion");
+        if (mPasswordVersionFile.exists()) {
+            FileInputStream fin = null;
+            DataInputStream in = null;
+            try {
+                fin = new FileInputStream(mPasswordVersionFile);
+                in = new DataInputStream(fin);
+                mPasswordVersion = in.readInt();
+            } catch (IOException e) {
+                Slog.e(TAG, "Unable to read backup pw version");
+            } finally {
+                try {
+                    if (in != null) in.close();
+                    if (fin != null) fin.close();
+                } catch (IOException e) {
+                    Slog.w(TAG, "Error closing pw version files");
+                }
+            }
+        }
+
         mPasswordHashFile = new File(mBaseStateDir, "pwhash");
         if (mPasswordHashFile.exists()) {
             FileInputStream fin = null;
@@ -1112,13 +1139,13 @@
         }
     }
 
-    private SecretKey buildPasswordKey(String pw, byte[] salt, int rounds) {
-        return buildCharArrayKey(pw.toCharArray(), salt, rounds);
+    private SecretKey buildPasswordKey(String algorithm, String pw, byte[] salt, int rounds) {
+        return buildCharArrayKey(algorithm, pw.toCharArray(), salt, rounds);
     }
 
-    private SecretKey buildCharArrayKey(char[] pwArray, byte[] salt, int rounds) {
+    private SecretKey buildCharArrayKey(String algorithm, char[] pwArray, byte[] salt, int rounds) {
         try {
-            SecretKeyFactory keyFactory = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1");
+            SecretKeyFactory keyFactory = SecretKeyFactory.getInstance(algorithm);
             KeySpec ks = new PBEKeySpec(pwArray, salt, rounds, PBKDF2_KEY_SIZE);
             return keyFactory.generateSecret(ks);
         } catch (InvalidKeySpecException e) {
@@ -1129,8 +1156,8 @@
         return null;
     }
 
-    private String buildPasswordHash(String pw, byte[] salt, int rounds) {
-        SecretKey key = buildPasswordKey(pw, salt, rounds);
+    private String buildPasswordHash(String algorithm, String pw, byte[] salt, int rounds) {
+        SecretKey key = buildPasswordKey(algorithm, pw, salt, rounds);
         if (key != null) {
             return byteArrayToHex(key.getEncoded());
         }
@@ -1158,13 +1185,13 @@
         return result;
     }
 
-    private byte[] makeKeyChecksum(byte[] pwBytes, byte[] salt, int rounds) {
+    private byte[] makeKeyChecksum(String algorithm, byte[] pwBytes, byte[] salt, int rounds) {
         char[] mkAsChar = new char[pwBytes.length];
         for (int i = 0; i < pwBytes.length; i++) {
             mkAsChar[i] = (char) pwBytes[i];
         }
 
-        Key checksum = buildCharArrayKey(mkAsChar, salt, rounds);
+        Key checksum = buildCharArrayKey(algorithm, mkAsChar, salt, rounds);
         return checksum.getEncoded();
     }
 
@@ -1176,7 +1203,7 @@
     }
 
     // Backup password management
-    boolean passwordMatchesSaved(String candidatePw, int rounds) {
+    boolean passwordMatchesSaved(String algorithm, String candidatePw, int rounds) {
         // First, on an encrypted device we require matching the device pw
         final boolean isEncrypted;
         try {
@@ -1220,7 +1247,7 @@
         } else {
             // hash the stated current pw and compare to the stored one
             if (candidatePw != null && candidatePw.length() > 0) {
-                String currentPwHash = buildPasswordHash(candidatePw, mPasswordSalt, rounds);
+                String currentPwHash = buildPasswordHash(algorithm, candidatePw, mPasswordSalt, rounds);
                 if (mPasswordHash.equalsIgnoreCase(currentPwHash)) {
                     // candidate hash matches the stored hash -- the password matches
                     return true;
@@ -1235,11 +1262,37 @@
         mContext.enforceCallingOrSelfPermission(android.Manifest.permission.BACKUP,
                 "setBackupPassword");
 
-        // If the supplied pw doesn't hash to the the saved one, fail
-        if (!passwordMatchesSaved(currentPw, PBKDF2_HASH_ROUNDS)) {
+        // When processing v1 passwords we may need to try two different PBKDF2 checksum regimes
+        final boolean pbkdf2Fallback = (mPasswordVersion < BACKUP_PW_FILE_VERSION);
+
+        // If the supplied pw doesn't hash to the the saved one, fail.  The password
+        // might be caught in the legacy crypto mismatch; verify that too.
+        if (!passwordMatchesSaved(PBKDF_CURRENT, currentPw, PBKDF2_HASH_ROUNDS)
+                && !(pbkdf2Fallback && passwordMatchesSaved(PBKDF_FALLBACK,
+                        currentPw, PBKDF2_HASH_ROUNDS))) {
             return false;
         }
 
+        // Snap up to current on the pw file version
+        mPasswordVersion = BACKUP_PW_FILE_VERSION;
+        FileOutputStream pwFout = null;
+        DataOutputStream pwOut = null;
+        try {
+            pwFout = new FileOutputStream(mPasswordVersionFile);
+            pwOut = new DataOutputStream(pwFout);
+            pwOut.writeInt(mPasswordVersion);
+        } catch (IOException e) {
+            Slog.e(TAG, "Unable to write backup pw version; password not changed");
+            return false;
+        } finally {
+            try {
+                if (pwOut != null) pwOut.close();
+                if (pwFout != null) pwFout.close();
+            } catch (IOException e) {
+                Slog.w(TAG, "Unable to close pw version record");
+            }
+        }
+
         // Clearing the password is okay
         if (newPw == null || newPw.isEmpty()) {
             if (mPasswordHashFile.exists()) {
@@ -1257,7 +1310,7 @@
         try {
             // Okay, build the hash of the new backup password
             byte[] salt = randomBytes(PBKDF2_SALT_SIZE);
-            String newPwHash = buildPasswordHash(newPw, salt, PBKDF2_HASH_ROUNDS);
+            String newPwHash = buildPasswordHash(PBKDF_CURRENT, newPw, salt, PBKDF2_HASH_ROUNDS);
 
             OutputStream pwf = null, buffer = null;
             DataOutputStream out = null;
@@ -1300,6 +1353,19 @@
         }
     }
 
+    private boolean backupPasswordMatches(String currentPw) {
+        if (hasBackupPassword()) {
+            final boolean pbkdf2Fallback = (mPasswordVersion < BACKUP_PW_FILE_VERSION);
+            if (!passwordMatchesSaved(PBKDF_CURRENT, currentPw, PBKDF2_HASH_ROUNDS)
+                    && !(pbkdf2Fallback && passwordMatchesSaved(PBKDF_FALLBACK,
+                            currentPw, PBKDF2_HASH_ROUNDS))) {
+                if (DEBUG) Slog.w(TAG, "Backup password mismatch; aborting");
+                return false;
+            }
+        }
+        return true;
+    }
+
     // Maintain persistent state around whether need to do an initialize operation.
     // Must be called with the queue lock held.
     void recordInitPendingLocked(boolean isPending, String transportName) {
@@ -2721,11 +2787,9 @@
 
                 // Verify that the given password matches the currently-active
                 // backup password, if any
-                if (hasBackupPassword()) {
-                    if (!passwordMatchesSaved(mCurrentPassword, PBKDF2_HASH_ROUNDS)) {
-                        if (DEBUG) Slog.w(TAG, "Backup password mismatch; aborting");
-                        return;
-                    }
+                if (!backupPasswordMatches(mCurrentPassword)) {
+                    if (DEBUG) Slog.w(TAG, "Backup password mismatch; aborting");
+                    return;
                 }
 
                 // Write the global file header.  All strings are UTF-8 encoded; lines end
@@ -2733,7 +2797,7 @@
                 // final '\n'.
                 //
                 // line 1: "ANDROID BACKUP"
-                // line 2: backup file format version, currently "1"
+                // line 2: backup file format version, currently "2"
                 // line 3: compressed?  "0" if not compressed, "1" if compressed.
                 // line 4: name of encryption algorithm [currently only "none" or "AES-256"]
                 //
@@ -2841,7 +2905,7 @@
                 OutputStream ofstream) throws Exception {
             // User key will be used to encrypt the master key.
             byte[] newUserSalt = randomBytes(PBKDF2_SALT_SIZE);
-            SecretKey userKey = buildPasswordKey(mEncryptPassword, newUserSalt,
+            SecretKey userKey = buildPasswordKey(PBKDF_CURRENT, mEncryptPassword, newUserSalt,
                     PBKDF2_HASH_ROUNDS);
 
             // the master key is random for each backup
@@ -2888,7 +2952,7 @@
             // stated number of PBKDF2 rounds
             IV = c.getIV();
             byte[] mk = masterKeySpec.getEncoded();
-            byte[] checksum = makeKeyChecksum(masterKeySpec.getEncoded(),
+            byte[] checksum = makeKeyChecksum(PBKDF_CURRENT, masterKeySpec.getEncoded(),
                     checksumSalt, PBKDF2_HASH_ROUNDS);
 
             ByteArrayOutputStream blob = new ByteArrayOutputStream(IV.length + mk.length
@@ -3231,11 +3295,9 @@
             FileInputStream rawInStream = null;
             DataInputStream rawDataIn = null;
             try {
-                if (hasBackupPassword()) {
-                    if (!passwordMatchesSaved(mCurrentPassword, PBKDF2_HASH_ROUNDS)) {
-                        if (DEBUG) Slog.w(TAG, "Backup password mismatch; aborting");
-                        return;
-                    }
+                if (!backupPasswordMatches(mCurrentPassword)) {
+                    if (DEBUG) Slog.w(TAG, "Backup password mismatch; aborting");
+                    return;
                 }
 
                 mBytes = 0;
@@ -3256,8 +3318,12 @@
                 if (Arrays.equals(magicBytes, streamHeader)) {
                     // okay, header looks good.  now parse out the rest of the fields.
                     String s = readHeaderLine(rawInStream);
-                    if (Integer.parseInt(s) == BACKUP_FILE_VERSION) {
-                        // okay, it's a version we recognize
+                    final int archiveVersion = Integer.parseInt(s);
+                    if (archiveVersion <= BACKUP_FILE_VERSION) {
+                        // okay, it's a version we recognize.  if it's version 1, we may need
+                        // to try two different PBKDF2 regimes to compare checksums.
+                        final boolean pbkdf2Fallback = (archiveVersion == 1);
+
                         s = readHeaderLine(rawInStream);
                         compressed = (Integer.parseInt(s) != 0);
                         s = readHeaderLine(rawInStream);
@@ -3265,7 +3331,8 @@
                             // no more header to parse; we're good to go
                             okay = true;
                         } else if (mDecryptPassword != null && mDecryptPassword.length() > 0) {
-                            preCompressStream = decodeAesHeaderAndInitialize(s, rawInStream);
+                            preCompressStream = decodeAesHeaderAndInitialize(s, pbkdf2Fallback,
+                                    rawInStream);
                             if (preCompressStream != null) {
                                 okay = true;
                             }
@@ -3325,7 +3392,71 @@
             return buffer.toString();
         }
 
-        InputStream decodeAesHeaderAndInitialize(String encryptionName, InputStream rawInStream) {
+        InputStream attemptMasterKeyDecryption(String algorithm, byte[] userSalt, byte[] ckSalt,
+                int rounds, String userIvHex, String masterKeyBlobHex, InputStream rawInStream,
+                boolean doLog) {
+            InputStream result = null;
+
+            try {
+                Cipher c = Cipher.getInstance("AES/CBC/PKCS5Padding");
+                SecretKey userKey = buildPasswordKey(algorithm, mDecryptPassword, userSalt,
+                        rounds);
+                byte[] IV = hexToByteArray(userIvHex);
+                IvParameterSpec ivSpec = new IvParameterSpec(IV);
+                c.init(Cipher.DECRYPT_MODE,
+                        new SecretKeySpec(userKey.getEncoded(), "AES"),
+                        ivSpec);
+                byte[] mkCipher = hexToByteArray(masterKeyBlobHex);
+                byte[] mkBlob = c.doFinal(mkCipher);
+
+                // first, the master key IV
+                int offset = 0;
+                int len = mkBlob[offset++];
+                IV = Arrays.copyOfRange(mkBlob, offset, offset + len);
+                offset += len;
+                // then the master key itself
+                len = mkBlob[offset++];
+                byte[] mk = Arrays.copyOfRange(mkBlob,
+                        offset, offset + len);
+                offset += len;
+                // and finally the master key checksum hash
+                len = mkBlob[offset++];
+                byte[] mkChecksum = Arrays.copyOfRange(mkBlob,
+                        offset, offset + len);
+
+                // now validate the decrypted master key against the checksum
+                byte[] calculatedCk = makeKeyChecksum(algorithm, mk, ckSalt, rounds);
+                if (Arrays.equals(calculatedCk, mkChecksum)) {
+                    ivSpec = new IvParameterSpec(IV);
+                    c.init(Cipher.DECRYPT_MODE,
+                            new SecretKeySpec(mk, "AES"),
+                            ivSpec);
+                    // Only if all of the above worked properly will 'result' be assigned
+                    result = new CipherInputStream(rawInStream, c);
+                } else if (doLog) Slog.w(TAG, "Incorrect password");
+            } catch (InvalidAlgorithmParameterException e) {
+                if (doLog) Slog.e(TAG, "Needed parameter spec unavailable!", e);
+            } catch (BadPaddingException e) {
+                // This case frequently occurs when the wrong password is used to decrypt
+                // the master key.  Use the identical "incorrect password" log text as is
+                // used in the checksum failure log in order to avoid providing additional
+                // information to an attacker.
+                if (doLog) Slog.w(TAG, "Incorrect password");
+            } catch (IllegalBlockSizeException e) {
+                if (doLog) Slog.w(TAG, "Invalid block size in master key");
+            } catch (NoSuchAlgorithmException e) {
+                if (doLog) Slog.e(TAG, "Needed decryption algorithm unavailable!");
+            } catch (NoSuchPaddingException e) {
+                if (doLog) Slog.e(TAG, "Needed padding mechanism unavailable!");
+            } catch (InvalidKeyException e) {
+                if (doLog) Slog.w(TAG, "Illegal password; aborting");
+            }
+
+            return result;
+        }
+
+        InputStream decodeAesHeaderAndInitialize(String encryptionName, boolean pbkdf2Fallback,
+                InputStream rawInStream) {
             InputStream result = null;
             try {
                 if (encryptionName.equals(ENCRYPTION_ALGORITHM_NAME)) {
@@ -3342,59 +3473,13 @@
                     String masterKeyBlobHex = readHeaderLine(rawInStream); // 9
 
                     // decrypt the master key blob
-                    Cipher c = Cipher.getInstance("AES/CBC/PKCS5Padding");
-                    SecretKey userKey = buildPasswordKey(mDecryptPassword, userSalt,
-                            rounds);
-                    byte[] IV = hexToByteArray(userIvHex);
-                    IvParameterSpec ivSpec = new IvParameterSpec(IV);
-                    c.init(Cipher.DECRYPT_MODE,
-                            new SecretKeySpec(userKey.getEncoded(), "AES"),
-                            ivSpec);
-                    byte[] mkCipher = hexToByteArray(masterKeyBlobHex);
-                    byte[] mkBlob = c.doFinal(mkCipher);
-
-                    // first, the master key IV
-                    int offset = 0;
-                    int len = mkBlob[offset++];
-                    IV = Arrays.copyOfRange(mkBlob, offset, offset + len);
-                    offset += len;
-                    // then the master key itself
-                    len = mkBlob[offset++];
-                    byte[] mk = Arrays.copyOfRange(mkBlob,
-                            offset, offset + len);
-                    offset += len;
-                    // and finally the master key checksum hash
-                    len = mkBlob[offset++];
-                    byte[] mkChecksum = Arrays.copyOfRange(mkBlob,
-                            offset, offset + len);
-
-                    // now validate the decrypted master key against the checksum
-                    byte[] calculatedCk = makeKeyChecksum(mk, ckSalt, rounds);
-                    if (Arrays.equals(calculatedCk, mkChecksum)) {
-                        ivSpec = new IvParameterSpec(IV);
-                        c.init(Cipher.DECRYPT_MODE,
-                                new SecretKeySpec(mk, "AES"),
-                                ivSpec);
-                        // Only if all of the above worked properly will 'result' be assigned
-                        result = new CipherInputStream(rawInStream, c);
-                    } else Slog.w(TAG, "Incorrect password");
+                    result = attemptMasterKeyDecryption(PBKDF_CURRENT, userSalt, ckSalt,
+                            rounds, userIvHex, masterKeyBlobHex, rawInStream, false);
+                    if (result == null && pbkdf2Fallback) {
+                        result = attemptMasterKeyDecryption(PBKDF_FALLBACK, userSalt, ckSalt,
+                                rounds, userIvHex, masterKeyBlobHex, rawInStream, true);
+                    }
                 } else Slog.w(TAG, "Unsupported encryption method: " + encryptionName);
-            } catch (InvalidAlgorithmParameterException e) {
-                Slog.e(TAG, "Needed parameter spec unavailable!", e);
-            } catch (BadPaddingException e) {
-                // This case frequently occurs when the wrong password is used to decrypt
-                // the master key.  Use the identical "incorrect password" log text as is
-                // used in the checksum failure log in order to avoid providing additional
-                // information to an attacker.
-                Slog.w(TAG, "Incorrect password");
-            } catch (IllegalBlockSizeException e) {
-                Slog.w(TAG, "Invalid block size in master key");
-            } catch (NoSuchAlgorithmException e) {
-                Slog.e(TAG, "Needed decryption algorithm unavailable!");
-            } catch (NoSuchPaddingException e) {
-                Slog.e(TAG, "Needed padding mechanism unavailable!");
-            } catch (InvalidKeyException e) {
-                Slog.w(TAG, "Illegal password; aborting");
             } catch (NumberFormatException e) {
                 Slog.w(TAG, "Can't parse restore data header");
             } catch (IOException e) {
diff --git a/tests/LegacyRestoreTest/README b/tests/LegacyRestoreTest/README
new file mode 100644
index 0000000..cdd157e
--- /dev/null
+++ b/tests/LegacyRestoreTest/README
@@ -0,0 +1,18 @@
+The file "jbmr2-encrypted-settings-abcd.ab" in this directory is an encrypted
+"adb backup" archive of the settings provider package.  It was generated on a
+Nexus 4 running Android 4.3 (API 18), and so predates the Android 4.4 changes
+to the PBKDF2 implementation.  The archive's encryption password, entered on-screen,
+is "abcd" (with no quotation marks).
+
+'adb restore' decrypts and applies the restored archive successfully on a device
+running Android 4.3, but fails to restore correctly on a device running Android 4.4,
+reporting an invalid password in logcat.  This is the situation reported in bug
+<https://code.google.com/p/android/issues/detail?id=63880>.
+
+The file "kk-fixed-encrypted-settings-abcd.ab" is a similar encrypted "adb backup"
+archive, using the same key, generated on a Nexus 4 running Android 4.4 with a fix
+to this bug in place.  This archive should be successfully restorable on any
+version of Android which incorporates the fix.
+
+These archives can be used as an ongoing test to verify that historical encrypted
+archives from various points in Android's history can be successfully restored.
diff --git a/tests/LegacyRestoreTest/jbmr2-encrypted-settings-abcd.ab b/tests/LegacyRestoreTest/jbmr2-encrypted-settings-abcd.ab
new file mode 100644
index 0000000..192dcf5
--- /dev/null
+++ b/tests/LegacyRestoreTest/jbmr2-encrypted-settings-abcd.ab
Binary files differ
diff --git a/tests/LegacyRestoreTest/kk-fixed-encrypted-settings-abcd.ab b/tests/LegacyRestoreTest/kk-fixed-encrypted-settings-abcd.ab
new file mode 100644
index 0000000..bf2b558
--- /dev/null
+++ b/tests/LegacyRestoreTest/kk-fixed-encrypted-settings-abcd.ab
Binary files differ