Move backup encryption to separate APK

Test: atest -c --rebuild-module-info BackupEncryptionRoboTests
Change-Id: I5a8ac3a9c010bd3c516464dee333cef406c5dcfa

39 files changed, 2993 insertions, 0 deletions

diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/Chunk.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/Chunk.java
new file mode 100644
index 000000000000..ba328609a77e
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/Chunk.java
@@ -0,0 +1,70 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunk;
+
+import android.util.proto.ProtoInputStream;
+
+import java.io.IOException;
+
+/**
+ * Information about a chunk entry in a protobuf. Only used for reading from a {@link
+ * ProtoInputStream}.
+ */
+public class Chunk {
+    /**
+     * Reads a Chunk from a {@link ProtoInputStream}. Expects the message to be of format {@link
+     * ChunksMetadataProto.Chunk}.
+     *
+     * @param inputStream currently at a {@link ChunksMetadataProto.Chunk} message.
+     * @throws IOException when the message is not structured as expected or a field can not be
+     *     read.
+     */
+    static Chunk readFromProto(ProtoInputStream inputStream) throws IOException {
+        Chunk result = new Chunk();
+
+        while (inputStream.nextField() != ProtoInputStream.NO_MORE_FIELDS) {
+            switch (inputStream.getFieldNumber()) {
+                case (int) ChunksMetadataProto.Chunk.HASH:
+                    result.mHash = inputStream.readBytes(ChunksMetadataProto.Chunk.HASH);
+                    break;
+                case (int) ChunksMetadataProto.Chunk.LENGTH:
+                    result.mLength = inputStream.readInt(ChunksMetadataProto.Chunk.LENGTH);
+                    break;
+            }
+        }
+
+        return result;
+    }
+
+    private int mLength;
+    private byte[] mHash;
+
+    /** Private constructor. This class should only be instantiated by calling readFromProto. */
+    private Chunk() {
+        // Set default values for fields in case they are not available in the proto.
+        mHash = new byte[]{};
+        mLength = 0;
+    }
+
+    public int getLength() {
+        return mLength;
+    }
+
+    public byte[] getHash() {
+        return mHash;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkHash.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkHash.java
new file mode 100644
index 000000000000..1630eb8ff4e8
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkHash.java
@@ -0,0 +1,90 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunk;
+
+import com.android.internal.util.Preconditions;
+
+import java.util.Arrays;
+import java.util.Base64;
+
+/**
+ * Represents the SHA-256 hash of the plaintext of a chunk, which is frequently used as a key.
+ *
+ * <p>This class is {@link Comparable} and implements {@link #equals(Object)} and {@link
+ * #hashCode()}.
+ */
+public class ChunkHash implements Comparable<ChunkHash> {
+    /** The length of the hash in bytes. The hash is a SHA-256, so this is 256 bits. */
+    public static final int HASH_LENGTH_BYTES = 256 / 8;
+
+    private static final int UNSIGNED_MASK = 0xFF;
+
+    private final byte[] mHash;
+
+    /** Constructs a new instance which wraps the given SHA-256 hash bytes. */
+    public ChunkHash(byte[] hash) {
+        Preconditions.checkArgument(hash.length == HASH_LENGTH_BYTES, "Hash must have 256 bits");
+        mHash = hash;
+    }
+
+    public byte[] getHash() {
+        return mHash;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (!(o instanceof ChunkHash)) {
+            return false;
+        }
+
+        ChunkHash chunkHash = (ChunkHash) o;
+        return Arrays.equals(mHash, chunkHash.mHash);
+    }
+
+    @Override
+    public int hashCode() {
+        return Arrays.hashCode(mHash);
+    }
+
+    @Override
+    public int compareTo(ChunkHash other) {
+        return lexicographicalCompareUnsignedBytes(getHash(), other.getHash());
+    }
+
+    @Override
+    public String toString() {
+        return Base64.getEncoder().encodeToString(mHash);
+    }
+
+    private static int lexicographicalCompareUnsignedBytes(byte[] left, byte[] right) {
+        int minLength = Math.min(left.length, right.length);
+        for (int i = 0; i < minLength; i++) {
+            int result = toInt(left[i]) - toInt(right[i]);
+            if (result != 0) {
+                return result;
+            }
+        }
+        return left.length - right.length;
+    }
+
+    private static int toInt(byte value) {
+        return value & UNSIGNED_MASK;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkListingMap.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkListingMap.java
new file mode 100644
index 000000000000..a44890118717
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkListingMap.java
@@ -0,0 +1,109 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunk;
+
+import android.annotation.Nullable;
+import android.util.proto.ProtoInputStream;
+
+import java.io.IOException;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Chunk listing in a format optimized for quick look-up of chunks via their hash keys. This is
+ * useful when building an incremental backup. After a chunk has been produced, the algorithm can
+ * quickly look up whether the chunk existed in the previous backup by checking this chunk listing.
+ * It can then tell the server to use that chunk, through telling it the position and length of the
+ * chunk in the previous backup's blob.
+ */
+public class ChunkListingMap {
+    /**
+     * Reads a ChunkListingMap from a {@link ProtoInputStream}. Expects the message to be of format
+     * {@link ChunksMetadataProto.ChunkListing}.
+     *
+     * @param inputStream Currently at a {@link ChunksMetadataProto.ChunkListing} message.
+     * @throws IOException when the message is not structured as expected or a field can not be
+     *     read.
+     */
+    public static ChunkListingMap readFromProto(ProtoInputStream inputStream) throws IOException {
+        Map<ChunkHash, Entry> entries = new HashMap();
+
+        long start = 0;
+
+        while (inputStream.nextField() != ProtoInputStream.NO_MORE_FIELDS) {
+            if (inputStream.getFieldNumber() == (int) ChunksMetadataProto.ChunkListing.CHUNKS) {
+                long chunkToken = inputStream.start(ChunksMetadataProto.ChunkListing.CHUNKS);
+                Chunk chunk = Chunk.readFromProto(inputStream);
+                entries.put(new ChunkHash(chunk.getHash()), new Entry(start, chunk.getLength()));
+                start += chunk.getLength();
+                inputStream.end(chunkToken);
+            }
+        }
+
+        return new ChunkListingMap(entries);
+    }
+
+    private final Map<ChunkHash, Entry> mChunksByHash;
+
+    private ChunkListingMap(Map<ChunkHash, Entry> chunksByHash) {
+        mChunksByHash = Collections.unmodifiableMap(new HashMap<>(chunksByHash));
+    }
+
+    /** Returns {@code true} if there is a chunk with the given SHA-256 MAC key in the listing. */
+    public boolean hasChunk(ChunkHash hash) {
+        return mChunksByHash.containsKey(hash);
+    }
+
+    /**
+     * Returns the entry for the chunk with the given hash.
+     *
+     * @param hash The SHA-256 MAC of the plaintext of the chunk.
+     * @return The entry, containing position and length of the chunk in the backup blob, or null if
+     *     it does not exist.
+     */
+    @Nullable
+    public Entry getChunkEntry(ChunkHash hash) {
+        return mChunksByHash.get(hash);
+    }
+
+    /** Returns the number of chunks in this listing. */
+    public int getChunkCount() {
+        return mChunksByHash.size();
+    }
+
+    /** Information about a chunk entry in a backup blob - i.e., its position and length. */
+    public static final class Entry {
+        private final int mLength;
+        private final long mStart;
+
+        private Entry(long start, int length) {
+            mStart = start;
+            mLength = length;
+        }
+
+        /** Returns the length of the chunk in bytes. */
+        public int getLength() {
+            return mLength;
+        }
+
+        /** Returns the start position of the chunk in the backup blob, in bytes. */
+        public long getStart() {
+            return mStart;
+        }
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkOrderingType.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkOrderingType.java
new file mode 100644
index 000000000000..8cb028e46e9d
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/ChunkOrderingType.java
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunk;
+
+import static com.android.server.backup.encryption.chunk.ChunksMetadataProto.CHUNK_ORDERING_TYPE_UNSPECIFIED;
+import static com.android.server.backup.encryption.chunk.ChunksMetadataProto.EXPLICIT_STARTS;
+import static com.android.server.backup.encryption.chunk.ChunksMetadataProto.INLINE_LENGTHS;
+
+import android.annotation.IntDef;
+
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+
+/** IntDef corresponding to the ChunkOrderingType enum in the ChunksMetadataProto protobuf. */
+@IntDef({CHUNK_ORDERING_TYPE_UNSPECIFIED, EXPLICIT_STARTS, INLINE_LENGTHS})
+@Retention(RetentionPolicy.SOURCE)
+public @interface ChunkOrderingType {}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/EncryptedChunkOrdering.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/EncryptedChunkOrdering.java
new file mode 100644
index 000000000000..edf1b9abb822
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunk/EncryptedChunkOrdering.java
@@ -0,0 +1,68 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunk;
+
+import java.util.Arrays;
+
+/**
+ * Holds the bytes of an encrypted {@link ChunksMetadataProto.ChunkOrdering}.
+ *
+ * <p>TODO(b/116575321): After all code is ported, remove the factory method and rename
+ * encryptedChunkOrdering() to getBytes().
+ */
+public class EncryptedChunkOrdering {
+    /**
+     * Constructs a new object holding the given bytes of an encrypted {@link
+     * ChunksMetadataProto.ChunkOrdering}.
+     *
+     * <p>Note that this just holds an ordering which is already encrypted, it does not encrypt the
+     * ordering.
+     */
+    public static EncryptedChunkOrdering create(byte[] encryptedChunkOrdering) {
+        return new EncryptedChunkOrdering(encryptedChunkOrdering);
+    }
+
+    private final byte[] mEncryptedChunkOrdering;
+
+    /** Get the encrypted chunk ordering */
+    public byte[] encryptedChunkOrdering() {
+        return mEncryptedChunkOrdering;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (!(o instanceof EncryptedChunkOrdering)) {
+            return false;
+        }
+
+        EncryptedChunkOrdering encryptedChunkOrdering = (EncryptedChunkOrdering) o;
+        return Arrays.equals(
+                mEncryptedChunkOrdering, encryptedChunkOrdering.mEncryptedChunkOrdering);
+    }
+
+    @Override
+    public int hashCode() {
+        return Arrays.hashCode(mEncryptedChunkOrdering);
+    }
+
+    private EncryptedChunkOrdering(byte[] encryptedChunkOrdering) {
+        mEncryptedChunkOrdering = encryptedChunkOrdering;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/BackupWriter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/BackupWriter.java
new file mode 100644
index 000000000000..baa820cbd558
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/BackupWriter.java
@@ -0,0 +1,43 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import java.io.IOException;
+
+/** Writes backup data either as a diff script or as raw data, determined by the implementation. */
+public interface BackupWriter {
+    /** Writes the given bytes to the output. */
+    void writeBytes(byte[] bytes) throws IOException;
+
+    /**
+     * Writes an existing chunk from the previous backup to the output.
+     *
+     * <p>Note: not all implementations support this method.
+     */
+    void writeChunk(long start, int length) throws IOException;
+
+    /** Returns the number of bytes written, included bytes copied from the old file. */
+    long getBytesWritten();
+
+    /**
+     * Indicates that no more bytes or chunks will be written.
+     *
+     * <p>After calling this, you may not call {@link #writeBytes(byte[])} or {@link
+     * #writeChunk(long, int)}
+     */
+    void flush() throws IOException;
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ByteRange.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ByteRange.java
new file mode 100644
index 000000000000..004d9e3b45f1
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ByteRange.java
@@ -0,0 +1,80 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.internal.util.Preconditions;
+
+/** Representation of a range of bytes to be downloaded. */
+final class ByteRange {
+    private final long mStart;
+    private final long mEnd;
+
+    /** Creates a range of bytes which includes {@code mStart} and {@code mEnd}. */
+    ByteRange(long start, long end) {
+        Preconditions.checkArgument(start >= 0);
+        Preconditions.checkArgument(end >= start);
+        mStart = start;
+        mEnd = end;
+    }
+
+    /** Returns the start of the {@code ByteRange}. The start is included in the range. */
+    long getStart() {
+        return mStart;
+    }
+
+    /** Returns the end of the {@code ByteRange}. The end is included in the range. */
+    long getEnd() {
+        return mEnd;
+    }
+
+    /** Returns the number of bytes included in the {@code ByteRange}. */
+    int getLength() {
+        return (int) (mEnd - mStart + 1);
+    }
+
+    /** Creates a new {@link ByteRange} from {@code mStart} to {@code mEnd + length}. */
+    ByteRange extend(long length) {
+        Preconditions.checkArgument(length > 0);
+        return new ByteRange(mStart, mEnd + length);
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (!(o instanceof ByteRange)) {
+            return false;
+        }
+
+        ByteRange byteRange = (ByteRange) o;
+        return (mEnd == byteRange.mEnd && mStart == byteRange.mStart);
+    }
+
+    @Override
+    public int hashCode() {
+        int result = 17;
+        result = 31 * result + (int) (mStart ^ (mStart >>> 32));
+        result = 31 * result + (int) (mEnd ^ (mEnd >>> 32));
+        return result;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("ByteRange{mStart=%d, mEnd=%d}", mStart, mEnd);
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ChunkEncryptor.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ChunkEncryptor.java
new file mode 100644
index 000000000000..48abc8cc4088
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ChunkEncryptor.java
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+
+import java.security.InvalidAlgorithmParameterException;
+import java.security.InvalidKeyException;
+import java.security.NoSuchAlgorithmException;
+import java.security.SecureRandom;
+
+import javax.crypto.BadPaddingException;
+import javax.crypto.Cipher;
+import javax.crypto.IllegalBlockSizeException;
+import javax.crypto.NoSuchPaddingException;
+import javax.crypto.SecretKey;
+import javax.crypto.spec.GCMParameterSpec;
+
+/** Encrypts chunks of a file using AES/GCM. */
+public class ChunkEncryptor {
+    private static final String CIPHER_ALGORITHM = "AES/GCM/NoPadding";
+    private static final int GCM_NONCE_LENGTH_BYTES = 12;
+    private static final int GCM_TAG_LENGTH_BYTES = 16;
+
+    private final SecretKey mSecretKey;
+    private final SecureRandom mSecureRandom;
+
+    /**
+     * A new instance using {@code mSecretKey} to encrypt chunks and {@code mSecureRandom} to
+     * generate nonces.
+     */
+    public ChunkEncryptor(SecretKey secretKey, SecureRandom secureRandom) {
+        this.mSecretKey = secretKey;
+        this.mSecureRandom = secureRandom;
+    }
+
+    /**
+     * Transforms {@code plaintext} into an {@link EncryptedChunk}.
+     *
+     * @param plaintextHash The hash of the plaintext to encrypt, to attach as the key of the chunk.
+     * @param plaintext Bytes to encrypt.
+     * @throws InvalidKeyException If the given secret key is not a valid AES key for decryption.
+     * @throws IllegalBlockSizeException If the input data cannot be encrypted using
+     *     AES/GCM/NoPadding. This should never be the case.
+     */
+    public EncryptedChunk encrypt(ChunkHash plaintextHash, byte[] plaintext)
+            throws InvalidKeyException, IllegalBlockSizeException {
+        byte[] nonce = generateNonce();
+        Cipher cipher;
+        try {
+            cipher = Cipher.getInstance(CIPHER_ALGORITHM);
+            cipher.init(
+                    Cipher.ENCRYPT_MODE,
+                    mSecretKey,
+                    new GCMParameterSpec(GCM_TAG_LENGTH_BYTES * 8, nonce));
+        } catch (NoSuchAlgorithmException
+                | NoSuchPaddingException
+                | InvalidAlgorithmParameterException e) {
+            // This can not happen - AES/GCM/NoPadding is supported.
+            throw new AssertionError(e);
+        }
+        byte[] encryptedBytes;
+        try {
+            encryptedBytes = cipher.doFinal(plaintext);
+        } catch (BadPaddingException e) {
+            // This can not happen - BadPaddingException can only be thrown in decrypt mode.
+            throw new AssertionError("Impossible: threw BadPaddingException in encrypt mode.");
+        }
+
+        return EncryptedChunk.create(/*key=*/ plaintextHash, nonce, encryptedBytes);
+    }
+
+    private byte[] generateNonce() {
+        byte[] nonce = new byte[GCM_NONCE_LENGTH_BYTES];
+        mSecureRandom.nextBytes(nonce);
+        return nonce;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ChunkHasher.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ChunkHasher.java
new file mode 100644
index 000000000000..02d498ccd726
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/ChunkHasher.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+
+import java.security.InvalidKeyException;
+import java.security.NoSuchAlgorithmException;
+
+import javax.crypto.Mac;
+import javax.crypto.SecretKey;
+
+/** Computes the SHA-256 HMAC of a chunk of bytes. */
+public class ChunkHasher {
+    private static final String MAC_ALGORITHM = "HmacSHA256";
+
+    private final SecretKey mSecretKey;
+
+    /** Constructs a new hasher which computes the HMAC using the given secret key. */
+    public ChunkHasher(SecretKey secretKey) {
+        this.mSecretKey = secretKey;
+    }
+
+    /** Returns the SHA-256 over the given bytes. */
+    public ChunkHash computeHash(byte[] plaintext) throws InvalidKeyException {
+        try {
+            Mac mac = Mac.getInstance(MAC_ALGORITHM);
+            mac.init(mSecretKey);
+            return new ChunkHash(mac.doFinal(plaintext));
+        } catch (NoSuchAlgorithmException e) {
+            // This can not happen - AES/GCM/NoPadding is available as part of the framework.
+            throw new AssertionError(e);
+        }
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/Chunker.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/Chunker.java
new file mode 100644
index 000000000000..c9a6293ed060
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/Chunker.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.security.GeneralSecurityException;
+
+/** Splits an input stream into chunks, which are to be encrypted separately. */
+public interface Chunker {
+    /**
+     * Splits the input stream into chunks.
+     *
+     * @param inputStream The input stream.
+     * @param chunkConsumer A function that processes each chunk as it is produced.
+     * @throws IOException If there is a problem reading the input stream.
+     * @throws GeneralSecurityException if the consumer function throws an error.
+     */
+    void chunkify(InputStream inputStream, ChunkConsumer chunkConsumer)
+            throws IOException, GeneralSecurityException;
+
+    /** Function that consumes chunks. */
+    interface ChunkConsumer {
+        /**
+         * Invoked for each chunk.
+         *
+         * @param chunk Plaintext bytes of chunk.
+         * @throws GeneralSecurityException if there is an issue encrypting the chunk.
+         */
+        void accept(byte[] chunk) throws GeneralSecurityException;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DecryptedChunkFileOutput.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DecryptedChunkFileOutput.java
new file mode 100644
index 000000000000..ae2e150de4bc
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DecryptedChunkFileOutput.java
@@ -0,0 +1,87 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import static com.android.internal.util.Preconditions.checkState;
+
+import android.annotation.Nullable;
+
+import com.android.internal.annotations.VisibleForTesting;
+import com.android.server.backup.encryption.tasks.DecryptedChunkOutput;
+
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+
+/** Writes plaintext chunks to a file, building a digest of the plaintext of the resulting file. */
+public class DecryptedChunkFileOutput implements DecryptedChunkOutput {
+    @VisibleForTesting static final String DIGEST_ALGORITHM = "SHA-256";
+
+    private final File mOutputFile;
+    private final MessageDigest mMessageDigest;
+    @Nullable private FileOutputStream mFileOutputStream;
+    private boolean mClosed;
+    @Nullable private byte[] mDigest;
+
+    /**
+     * Constructs a new instance which writes chunks to the given file and uses the default message
+     * digest algorithm.
+     */
+    public DecryptedChunkFileOutput(File outputFile) {
+        mOutputFile = outputFile;
+        try {
+            mMessageDigest = MessageDigest.getInstance(DIGEST_ALGORITHM);
+        } catch (NoSuchAlgorithmException e) {
+            throw new AssertionError(
+                    "Impossible condition: JCE thinks it does not support AES.", e);
+        }
+    }
+
+    @Override
+    public DecryptedChunkOutput open() throws IOException {
+        checkState(mFileOutputStream == null, "Cannot open twice");
+        mFileOutputStream = new FileOutputStream(mOutputFile);
+        return this;
+    }
+
+    @Override
+    public void processChunk(byte[] plaintextBuffer, int length) throws IOException {
+        checkState(mFileOutputStream != null, "Must open before processing chunks");
+        mFileOutputStream.write(plaintextBuffer, /*off=*/ 0, length);
+        mMessageDigest.update(plaintextBuffer, /*offset=*/ 0, length);
+    }
+
+    @Override
+    public byte[] getDigest() {
+        checkState(mClosed, "Must close before getting mDigest");
+
+        // After the first call to mDigest() the MessageDigest is reset, thus we must store the
+        // result.
+        if (mDigest == null) {
+            mDigest = mMessageDigest.digest();
+        }
+        return mDigest;
+    }
+
+    @Override
+    public void close() throws IOException {
+        mFileOutputStream.close();
+        mClosed = true;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DiffScriptBackupWriter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DiffScriptBackupWriter.java
new file mode 100644
index 000000000000..69fb5cbf606d
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DiffScriptBackupWriter.java
@@ -0,0 +1,75 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/** Writes backup data to a diff script, using a {@link SingleStreamDiffScriptWriter}. */
+public class DiffScriptBackupWriter implements BackupWriter {
+    /**
+     * The maximum size of a chunk in the diff script. The diff script writer {@code mWriter} will
+     * buffer this many bytes in memory.
+     */
+    private static final int ENCRYPTION_DIFF_SCRIPT_MAX_CHUNK_SIZE_BYTES = 1024 * 1024;
+
+    private final SingleStreamDiffScriptWriter mWriter;
+    private long mBytesWritten;
+
+    /**
+     * Constructs a new writer which writes the diff script to the given output stream, using the
+     * maximum new chunk size {@code ENCRYPTION_DIFF_SCRIPT_MAX_CHUNK_SIZE_BYTES}.
+     */
+    public static DiffScriptBackupWriter newInstance(OutputStream outputStream) {
+        SingleStreamDiffScriptWriter writer =
+                new SingleStreamDiffScriptWriter(
+                        outputStream, ENCRYPTION_DIFF_SCRIPT_MAX_CHUNK_SIZE_BYTES);
+        return new DiffScriptBackupWriter(writer);
+    }
+
+    @VisibleForTesting
+    DiffScriptBackupWriter(SingleStreamDiffScriptWriter writer) {
+        mWriter = writer;
+    }
+
+    @Override
+    public void writeBytes(byte[] bytes) throws IOException {
+        for (byte b : bytes) {
+            mWriter.writeByte(b);
+        }
+
+        mBytesWritten += bytes.length;
+    }
+
+    @Override
+    public void writeChunk(long start, int length) throws IOException {
+        mWriter.writeChunk(start, length);
+        mBytesWritten += length;
+    }
+
+    @Override
+    public long getBytesWritten() {
+        return mBytesWritten;
+    }
+
+    @Override
+    public void flush() throws IOException {
+        mWriter.flush();
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DiffScriptWriter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DiffScriptWriter.java
new file mode 100644
index 000000000000..49d15712d4cc
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/DiffScriptWriter.java
@@ -0,0 +1,36 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/** Writer that formats a Diff Script and writes it to an output source. */
+interface DiffScriptWriter {
+    /** Adds a new byte to the diff script. */
+    void writeByte(byte b) throws IOException;
+
+    /** Adds a known chunk to the diff script. */
+    void writeChunk(long chunkStart, int chunkLength) throws IOException;
+
+    /** Indicates that no more bytes or chunks will be added to the diff script. */
+    void flush() throws IOException;
+
+    interface Factory {
+        DiffScriptWriter create(OutputStream outputStream);
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/EncryptedChunk.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/EncryptedChunk.java
new file mode 100644
index 000000000000..cde59fa189de
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/EncryptedChunk.java
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.internal.util.Preconditions;
+import com.android.server.backup.encryption.chunk.ChunkHash;
+
+import java.util.Arrays;
+import java.util.Objects;
+
+/**
+ * A chunk of a file encrypted using AES/GCM.
+ *
+ * <p>TODO(b/116575321): After all code is ported, remove the factory method and rename
+ * encryptedBytes(), key() and nonce().
+ */
+public class EncryptedChunk {
+    public static final int KEY_LENGTH_BYTES = ChunkHash.HASH_LENGTH_BYTES;
+    public static final int NONCE_LENGTH_BYTES = 12;
+
+    /**
+     * Constructs a new instance with the given key, nonce, and encrypted bytes.
+     *
+     * @param key SHA-256 Hmac of the chunk plaintext.
+     * @param nonce Nonce with which the bytes of the chunk were encrypted.
+     * @param encryptedBytes Encrypted bytes of the chunk.
+     */
+    public static EncryptedChunk create(ChunkHash key, byte[] nonce, byte[] encryptedBytes) {
+        Preconditions.checkArgument(
+                nonce.length == NONCE_LENGTH_BYTES, "Nonce does not have the correct length.");
+        return new EncryptedChunk(key, nonce, encryptedBytes);
+    }
+
+    private ChunkHash mKey;
+    private byte[] mNonce;
+    private byte[] mEncryptedBytes;
+
+    private EncryptedChunk(ChunkHash key, byte[] nonce, byte[] encryptedBytes) {
+        mKey = key;
+        mNonce = nonce;
+        mEncryptedBytes = encryptedBytes;
+    }
+
+    /** The SHA-256 Hmac of the plaintext bytes of the chunk. */
+    public ChunkHash key() {
+        return mKey;
+    }
+
+    /** The nonce with which the chunk was encrypted. */
+    public byte[] nonce() {
+        return mNonce;
+    }
+
+    /** The encrypted bytes of the chunk. */
+    public byte[] encryptedBytes() {
+        return mEncryptedBytes;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (!(o instanceof EncryptedChunk)) {
+            return false;
+        }
+
+        EncryptedChunk encryptedChunkOrdering = (EncryptedChunk) o;
+        return Arrays.equals(mEncryptedBytes, encryptedChunkOrdering.mEncryptedBytes)
+                && Arrays.equals(mNonce, encryptedChunkOrdering.mNonce)
+                && mKey.equals(encryptedChunkOrdering.mKey);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(mKey, Arrays.hashCode(mNonce), Arrays.hashCode(mEncryptedBytes));
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/EncryptedChunkEncoder.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/EncryptedChunkEncoder.java
new file mode 100644
index 000000000000..16beda32af17
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/EncryptedChunkEncoder.java
@@ -0,0 +1,46 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.server.backup.encryption.chunk.ChunkOrderingType;
+
+import java.io.IOException;
+
+/** Encodes an {@link EncryptedChunk} as bytes to write to the encrypted backup file. */
+public interface EncryptedChunkEncoder {
+    /**
+     * Encodes the given chunk and asks the writer to write it.
+     *
+     * <p>The chunk will be encoded in the format [nonce]+[encrypted data].
+     *
+     * <p>TODO(b/116575321): Choose a more descriptive method name after the code move is done.
+     */
+    void writeChunkToWriter(BackupWriter writer, EncryptedChunk chunk) throws IOException;
+
+    /**
+     * Returns the length in bytes that this chunk would be if encoded with {@link
+     * #writeChunkToWriter}.
+     */
+    int getEncodedLengthOfChunk(EncryptedChunk chunk);
+
+    /**
+     * Returns the {@link ChunkOrderingType} that must be included in the backup file, when using
+     * this decoder, so that the file may be correctly decoded.
+     */
+    @ChunkOrderingType
+    int getChunkOrderingType();
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/InlineLengthsEncryptedChunkEncoder.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/InlineLengthsEncryptedChunkEncoder.java
new file mode 100644
index 000000000000..7b38dd4a1dc3
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/InlineLengthsEncryptedChunkEncoder.java
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.server.backup.encryption.chunk.ChunkOrderingType;
+import com.android.server.backup.encryption.chunk.ChunksMetadataProto;
+
+import java.io.IOException;
+
+/**
+ * Encodes an {@link EncryptedChunk} as bytes, prepending the length of the chunk.
+ *
+ * <p>This allows us to decode the backup file during restore without any extra information about
+ * the boundaries of the chunks. The backup file should contain a chunk ordering in mode {@link
+ * ChunksMetadataProto#INLINE_LENGTHS}.
+ *
+ * <p>We use this implementation during key value backup.
+ */
+public class InlineLengthsEncryptedChunkEncoder implements EncryptedChunkEncoder {
+    public static final int BYTES_LENGTH = Integer.SIZE / Byte.SIZE;
+
+    private final LengthlessEncryptedChunkEncoder mLengthlessEncryptedChunkEncoder =
+            new LengthlessEncryptedChunkEncoder();
+
+    @Override
+    public void writeChunkToWriter(BackupWriter writer, EncryptedChunk chunk) throws IOException {
+        int length = mLengthlessEncryptedChunkEncoder.getEncodedLengthOfChunk(chunk);
+        writer.writeBytes(toByteArray(length));
+        mLengthlessEncryptedChunkEncoder.writeChunkToWriter(writer, chunk);
+    }
+
+    @Override
+    public int getEncodedLengthOfChunk(EncryptedChunk chunk) {
+        return BYTES_LENGTH + mLengthlessEncryptedChunkEncoder.getEncodedLengthOfChunk(chunk);
+    }
+
+    @Override
+    @ChunkOrderingType
+    public int getChunkOrderingType() {
+        return ChunksMetadataProto.INLINE_LENGTHS;
+    }
+
+    /**
+     * Returns a big-endian representation of {@code value} in a 4-element byte array; equivalent to
+     * {@code ByteBuffer.allocate(4).putInt(value).array()}. For example, the input value {@code
+     * 0x12131415} would yield the byte array {@code {0x12, 0x13, 0x14, 0x15}}.
+     *
+     * <p>Equivalent to guava's Ints.toByteArray.
+     */
+    static byte[] toByteArray(int value) {
+        return new byte[] {
+            (byte) (value >> 24), (byte) (value >> 16), (byte) (value >> 8), (byte) value
+        };
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/LengthlessEncryptedChunkEncoder.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/LengthlessEncryptedChunkEncoder.java
new file mode 100644
index 000000000000..567f75d59513
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/LengthlessEncryptedChunkEncoder.java
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import com.android.server.backup.encryption.chunk.ChunkOrderingType;
+import com.android.server.backup.encryption.chunk.ChunksMetadataProto;
+
+import java.io.IOException;
+
+/**
+ * Encodes an {@link EncryptedChunk} as bytes without including any information about the length of
+ * the chunk.
+ *
+ * <p>In order for us to decode the backup file during restore it must include a chunk ordering in
+ * mode {@link ChunksMetadataProto#EXPLICIT_STARTS}, which contains the boundaries of the chunks in
+ * the encrypted file. This information allows us to decode the backup file and divide it into
+ * chunks without including the length of each chunk inline.
+ *
+ * <p>We use this implementation during full backup.
+ */
+public class LengthlessEncryptedChunkEncoder implements EncryptedChunkEncoder {
+    @Override
+    public void writeChunkToWriter(BackupWriter writer, EncryptedChunk chunk) throws IOException {
+        writer.writeBytes(chunk.nonce());
+        writer.writeBytes(chunk.encryptedBytes());
+    }
+
+    @Override
+    public int getEncodedLengthOfChunk(EncryptedChunk chunk) {
+        return chunk.nonce().length + chunk.encryptedBytes().length;
+    }
+
+    @Override
+    @ChunkOrderingType
+    public int getChunkOrderingType() {
+        return ChunksMetadataProto.EXPLICIT_STARTS;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/OutputStreamWrapper.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/OutputStreamWrapper.java
new file mode 100644
index 000000000000..4aea60121810
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/OutputStreamWrapper.java
@@ -0,0 +1,25 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import java.io.OutputStream;
+
+/** An interface that wraps one {@link OutputStream} with another for filtration purposes. */
+public interface OutputStreamWrapper {
+    /** Wraps a given {@link OutputStream}. */
+    OutputStream wrap(OutputStream outputStream);
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/RawBackupWriter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/RawBackupWriter.java
new file mode 100644
index 000000000000..b211b0fc9470
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/RawBackupWriter.java
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import java.io.IOException;
+import java.io.OutputStream;
+
+/** Writes data straight to an output stream. */
+public class RawBackupWriter implements BackupWriter {
+    private final OutputStream mOutputStream;
+    private long mBytesWritten;
+
+    /** Constructs a new writer which writes bytes to the given output stream. */
+    public RawBackupWriter(OutputStream outputStream) {
+        this.mOutputStream = outputStream;
+    }
+
+    @Override
+    public void writeBytes(byte[] bytes) throws IOException {
+        mOutputStream.write(bytes);
+        mBytesWritten += bytes.length;
+    }
+
+    @Override
+    public void writeChunk(long start, int length) throws IOException {
+        throw new UnsupportedOperationException("RawBackupWriter cannot write existing chunks");
+    }
+
+    @Override
+    public long getBytesWritten() {
+        return mBytesWritten;
+    }
+
+    @Override
+    public void flush() throws IOException {
+        mOutputStream.flush();
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/SingleStreamDiffScriptWriter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/SingleStreamDiffScriptWriter.java
new file mode 100644
index 000000000000..0e4bd58345d5
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/SingleStreamDiffScriptWriter.java
@@ -0,0 +1,130 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking;
+
+import android.annotation.Nullable;
+
+import com.android.internal.util.Preconditions;
+
+import java.io.IOException;
+import java.io.OutputStream;
+import java.nio.charset.Charset;
+import java.util.Locale;
+
+/**
+ * A {@link DiffScriptWriter} that writes an entire diff script to a single {@link OutputStream}.
+ */
+public class SingleStreamDiffScriptWriter implements DiffScriptWriter {
+    static final byte LINE_SEPARATOR = 0xA;
+    private static final Charset UTF_8 = Charset.forName("UTF-8");
+
+    private final int mMaxNewByteChunkSize;
+    private final OutputStream mOutputStream;
+    private final byte[] mByteBuffer;
+    private int mBufferSize = 0;
+    // Each chunk could be written immediately to the output stream. However,
+    // it is possible that chunks may overlap. We therefore cache the most recent
+    // reusable chunk and try to merge it with future chunks.
+    private ByteRange mReusableChunk;
+
+    public SingleStreamDiffScriptWriter(OutputStream outputStream, int maxNewByteChunkSize) {
+        mOutputStream = outputStream;
+        mMaxNewByteChunkSize = maxNewByteChunkSize;
+        mByteBuffer = new byte[maxNewByteChunkSize];
+    }
+
+    @Override
+    public void writeByte(byte b) throws IOException {
+        if (mReusableChunk != null) {
+            writeReusableChunk();
+        }
+        mByteBuffer[mBufferSize++] = b;
+        if (mBufferSize == mMaxNewByteChunkSize) {
+            writeByteBuffer();
+        }
+    }
+
+    @Override
+    public void writeChunk(long chunkStart, int chunkLength) throws IOException {
+        Preconditions.checkArgument(chunkStart >= 0);
+        Preconditions.checkArgument(chunkLength > 0);
+        if (mBufferSize != 0) {
+            writeByteBuffer();
+        }
+
+        if (mReusableChunk != null && mReusableChunk.getEnd() + 1 == chunkStart) {
+            // The new chunk overlaps the old, so combine them into a single byte range.
+            mReusableChunk = mReusableChunk.extend(chunkLength);
+        } else {
+            writeReusableChunk();
+            mReusableChunk = new ByteRange(chunkStart, chunkStart + chunkLength - 1);
+        }
+    }
+
+    @Override
+    public void flush() throws IOException {
+        Preconditions.checkState(!(mBufferSize != 0 && mReusableChunk != null));
+        if (mBufferSize != 0) {
+            writeByteBuffer();
+        }
+        if (mReusableChunk != null) {
+            writeReusableChunk();
+        }
+        mOutputStream.flush();
+    }
+
+    private void writeByteBuffer() throws IOException {
+        mOutputStream.write(Integer.toString(mBufferSize).getBytes(UTF_8));
+        mOutputStream.write(LINE_SEPARATOR);
+        mOutputStream.write(mByteBuffer, 0, mBufferSize);
+        mOutputStream.write(LINE_SEPARATOR);
+        mBufferSize = 0;
+    }
+
+    private void writeReusableChunk() throws IOException {
+        if (mReusableChunk != null) {
+            mOutputStream.write(
+                    String.format(
+                                    Locale.US,
+                                    "%d-%d",
+                                    mReusableChunk.getStart(),
+                                    mReusableChunk.getEnd())
+                            .getBytes(UTF_8));
+            mOutputStream.write(LINE_SEPARATOR);
+            mReusableChunk = null;
+        }
+    }
+
+    /** A factory that creates {@link SingleStreamDiffScriptWriter}s. */
+    public static class Factory implements DiffScriptWriter.Factory {
+        private final int mMaxNewByteChunkSize;
+        private final OutputStreamWrapper mOutputStreamWrapper;
+
+        public Factory(int maxNewByteChunkSize, @Nullable OutputStreamWrapper outputStreamWrapper) {
+            mMaxNewByteChunkSize = maxNewByteChunkSize;
+            mOutputStreamWrapper = outputStreamWrapper;
+        }
+
+        @Override
+        public SingleStreamDiffScriptWriter create(OutputStream outputStream) {
+            if (mOutputStreamWrapper != null) {
+                outputStream = mOutputStreamWrapper.wrap(outputStream);
+            }
+            return new SingleStreamDiffScriptWriter(outputStream, mMaxNewByteChunkSize);
+        }
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunker.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunker.java
new file mode 100644
index 000000000000..18011f620b24
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/ContentDefinedChunker.java
@@ -0,0 +1,136 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking.cdc;
+
+import static com.android.internal.util.Preconditions.checkArgument;
+
+import com.android.server.backup.encryption.chunking.Chunker;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.security.GeneralSecurityException;
+import java.util.Arrays;
+
+/** Splits a stream of bytes into variable-sized chunks, using content-defined chunking. */
+public class ContentDefinedChunker implements Chunker {
+    private static final int WINDOW_SIZE = 31;
+    private static final byte DEFAULT_OUT_BYTE = (byte) 0;
+
+    private final byte[] mChunkBuffer;
+    private final RabinFingerprint64 mRabinFingerprint64;
+    private final FingerprintMixer mFingerprintMixer;
+    private final BreakpointPredicate mBreakpointPredicate;
+    private final int mMinChunkSize;
+    private final int mMaxChunkSize;
+
+    /**
+     * Constructor.
+     *
+     * @param minChunkSize The minimum size of a chunk. No chunk will be produced of a size smaller
+     *     than this except possibly at the very end of the stream.
+     * @param maxChunkSize The maximum size of a chunk. No chunk will be produced of a larger size.
+     * @param rabinFingerprint64 Calculates fingerprints, with which to determine breakpoints.
+     * @param breakpointPredicate Given a Rabin fingerprint, returns whether this ought to be a
+     *     breakpoint.
+     */
+    public ContentDefinedChunker(
+            int minChunkSize,
+            int maxChunkSize,
+            RabinFingerprint64 rabinFingerprint64,
+            FingerprintMixer fingerprintMixer,
+            BreakpointPredicate breakpointPredicate) {
+        checkArgument(
+                minChunkSize >= WINDOW_SIZE,
+                "Minimum chunk size must be greater than window size.");
+        checkArgument(
+                maxChunkSize >= minChunkSize,
+                "Maximum chunk size cannot be smaller than minimum chunk size.");
+        mChunkBuffer = new byte[maxChunkSize];
+        mRabinFingerprint64 = rabinFingerprint64;
+        mBreakpointPredicate = breakpointPredicate;
+        mFingerprintMixer = fingerprintMixer;
+        mMinChunkSize = minChunkSize;
+        mMaxChunkSize = maxChunkSize;
+    }
+
+    /**
+     * Breaks the input stream into variable-sized chunks.
+     *
+     * @param inputStream The input bytes to break into chunks.
+     * @param chunkConsumer A function to process each chunk as it's generated.
+     * @throws IOException Thrown if there is an issue reading from the input stream.
+     * @throws GeneralSecurityException Thrown if the {@link ChunkConsumer} throws it.
+     */
+    @Override
+    public void chunkify(InputStream inputStream, ChunkConsumer chunkConsumer)
+            throws IOException, GeneralSecurityException {
+        int chunkLength;
+        int initialReadLength = mMinChunkSize - WINDOW_SIZE;
+
+        // Performance optimization - there is no reason to calculate fingerprints for windows
+        // ending before the minimum chunk size.
+        while ((chunkLength =
+                        inputStream.read(mChunkBuffer, /*off=*/ 0, /*len=*/ initialReadLength))
+                != -1) {
+            int b;
+            long fingerprint = 0L;
+
+            while ((b = inputStream.read()) != -1) {
+                byte inByte = (byte) b;
+                byte outByte = getCurrentWindowStartByte(chunkLength);
+                mChunkBuffer[chunkLength++] = inByte;
+
+                fingerprint =
+                        mRabinFingerprint64.computeFingerprint64(inByte, outByte, fingerprint);
+
+                if (chunkLength >= mMaxChunkSize
+                        || (chunkLength >= mMinChunkSize
+                                && mBreakpointPredicate.isBreakpoint(
+                                        mFingerprintMixer.mix(fingerprint)))) {
+                    chunkConsumer.accept(Arrays.copyOf(mChunkBuffer, chunkLength));
+                    chunkLength = 0;
+                    break;
+                }
+            }
+
+            if (chunkLength > 0) {
+                chunkConsumer.accept(Arrays.copyOf(mChunkBuffer, chunkLength));
+            }
+        }
+    }
+
+    private byte getCurrentWindowStartByte(int chunkLength) {
+        if (chunkLength < mMinChunkSize) {
+            return DEFAULT_OUT_BYTE;
+        } else {
+            return mChunkBuffer[chunkLength - WINDOW_SIZE];
+        }
+    }
+
+    /** Whether the current fingerprint indicates the end of a chunk. */
+    public interface BreakpointPredicate {
+
+        /**
+         * Returns {@code true} if the fingerprint of the last {@code WINDOW_SIZE} bytes indicates
+         * the chunk ought to end at this position.
+         *
+         * @param fingerprint Fingerprint of the last {@code WINDOW_SIZE} bytes.
+         * @return Whether this ought to be a chunk breakpoint.
+         */
+        boolean isBreakpoint(long fingerprint);
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixer.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixer.java
new file mode 100644
index 000000000000..e9f30505c112
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/FingerprintMixer.java
@@ -0,0 +1,95 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking.cdc;
+
+import static com.android.internal.util.Preconditions.checkArgument;
+
+import java.nio.ByteBuffer;
+import java.nio.charset.StandardCharsets;
+import java.security.InvalidKeyException;
+
+import javax.crypto.SecretKey;
+
+/**
+ * Helper for mixing fingerprint with key material.
+ *
+ * <p>We do this as otherwise the Rabin fingerprint leaks information about the plaintext. i.e., if
+ * two users have the same file, it will be partitioned by Rabin in the same way, allowing us to
+ * infer that it is the same as another user's file.
+ *
+ * <p>By mixing the fingerprint with the user's secret key, the chunking method is different on a
+ * per key basis. Each application has its own {@link SecretKey}, so we cannot infer that a file is
+ * the same even across multiple applications owned by the same user, never mind across multiple
+ * users.
+ *
+ * <p>Instead of directly mixing the fingerprint with the user's secret, we first securely and
+ * deterministically derive a secondary chunking key. As Rabin is not a cryptographically secure
+ * hash, it might otherwise leak information about the user's secret. This prevents that from
+ * happening.
+ */
+public class FingerprintMixer {
+    public static final int SALT_LENGTH_BYTES = 256 / Byte.SIZE;
+    private static final String DERIVED_KEY_NAME = "RabinFingerprint64Mixer";
+
+    private final long mAddend;
+    private final long mMultiplicand;
+
+    /**
+     * A new instance from a given secret key and salt. Salt must be the same across incremental
+     * backups, or a different chunking strategy will be used each time, defeating the dedup.
+     *
+     * @param secretKey The application-specific secret.
+     * @param salt The salt.
+     * @throws InvalidKeyException If the encoded form of {@code secretKey} is inaccessible.
+     */
+    public FingerprintMixer(SecretKey secretKey, byte[] salt) throws InvalidKeyException {
+        checkArgument(salt.length == SALT_LENGTH_BYTES, "Requires a 256-bit salt.");
+        byte[] keyBytes = secretKey.getEncoded();
+        if (keyBytes == null) {
+            throw new InvalidKeyException("SecretKey must support encoding for FingerprintMixer.");
+        }
+        byte[] derivedKey =
+                Hkdf.hkdf(keyBytes, salt, DERIVED_KEY_NAME.getBytes(StandardCharsets.UTF_8));
+        ByteBuffer buffer = ByteBuffer.wrap(derivedKey);
+        mAddend = buffer.getLong();
+        // Multiplicand must be odd - otherwise we lose some bits of the Rabin fingerprint when
+        // mixing
+        mMultiplicand = buffer.getLong() | 1;
+    }
+
+    /**
+     * Mixes the fingerprint with the derived key material. This is performed by adding part of the
+     * derived key and multiplying by another part of the derived key (which is forced to be odd, so
+     * that the operation is reversible).
+     *
+     * @param fingerprint A 64-bit Rabin fingerprint.
+     * @return The mixed fingerprint.
+     */
+    long mix(long fingerprint) {
+        return ((fingerprint + mAddend) * mMultiplicand);
+    }
+
+    /** The addend part of the derived key. */
+    long getAddend() {
+        return mAddend;
+    }
+
+    /** The multiplicand part of the derived key. */
+    long getMultiplicand() {
+        return mMultiplicand;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/Hkdf.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/Hkdf.java
new file mode 100644
index 000000000000..6f4f549ab2d7
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/Hkdf.java
@@ -0,0 +1,115 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking.cdc;
+
+import static com.android.internal.util.Preconditions.checkNotNull;
+
+import java.security.InvalidKeyException;
+import java.security.NoSuchAlgorithmException;
+
+import javax.crypto.Mac;
+import javax.crypto.spec.SecretKeySpec;
+
+/**
+ * Secure HKDF utils. Allows client to deterministically derive additional key material from a base
+ * secret. If the derived key material is compromised, this does not in of itself compromise the
+ * root secret.
+ *
+ * <p>TODO(b/116575321): After all code is ported, rename this class to HkdfUtils.
+ */
+public final class Hkdf {
+    private static final byte[] CONSTANT_01 = {0x01};
+    private static final String HmacSHA256 = "HmacSHA256";
+    private static final String AES = "AES";
+
+    /**
+     * Implements HKDF (RFC 5869) with the SHA-256 hash and a 256-bit output key length.
+     *
+     * <p>IMPORTANT: The use or edit of this method requires a security review.
+     *
+     * @param masterKey Master key from which to derive sub-keys.
+     * @param salt A randomly generated 256-bit byte string.
+     * @param data Arbitrary information that is bound to the derived key (i.e., used in its
+     *     creation).
+     * @return Raw derived key bytes = HKDF-SHA256(masterKey, salt, data).
+     * @throws InvalidKeyException If the salt can not be used as a valid key.
+     */
+    static byte[] hkdf(byte[] masterKey, byte[] salt, byte[] data) throws InvalidKeyException {
+        checkNotNull(masterKey, "HKDF requires master key to be set.");
+        checkNotNull(salt, "HKDF requires a salt.");
+        checkNotNull(data, "No data provided to HKDF.");
+        return hkdfSha256Expand(hkdfSha256Extract(masterKey, salt), data);
+    }
+
+    private Hkdf() {}
+
+    /**
+     * The HKDF (RFC 5869) extraction function, using the SHA-256 hash function. This function is
+     * used to pre-process the {@code inputKeyMaterial} and mix it with the {@code salt}, producing
+     * output suitable for use with HKDF expansion function (which produces the actual derived key).
+     *
+     * <p>IMPORTANT: The use or edit of this method requires a security review.
+     *
+     * @see #hkdfSha256Expand(byte[], byte[])
+     * @return HMAC-SHA256(salt, inputKeyMaterial) (salt is the "key" for the HMAC)
+     * @throws InvalidKeyException If the salt can not be used as a valid key.
+     */
+    private static byte[] hkdfSha256Extract(byte[] inputKeyMaterial, byte[] salt)
+            throws InvalidKeyException {
+        // Note that the SecretKey encoding format is defined to be RAW, so the encoded form should
+        // be consistent across implementations.
+        Mac sha256;
+        try {
+            sha256 = Mac.getInstance(HmacSHA256);
+        } catch (NoSuchAlgorithmException e) {
+            // This can not happen - HmacSHA256 is supported by the platform.
+            throw new AssertionError(e);
+        }
+        sha256.init(new SecretKeySpec(salt, AES));
+
+        return sha256.doFinal(inputKeyMaterial);
+    }
+
+    /**
+     * Special case of HKDF (RFC 5869) expansion function, using the SHA-256 hash function and
+     * allowing for a maximum output length of 256 bits.
+     *
+     * <p>IMPORTANT: The use or edit of this method requires a security review.
+     *
+     * @param pseudoRandomKey Generated by {@link #hkdfSha256Extract(byte[], byte[])}.
+     * @param info Arbitrary information the derived key should be bound to.
+     * @return Raw derived key bytes = HMAC-SHA256(pseudoRandomKey, info | 0x01).
+     * @throws InvalidKeyException If the salt can not be used as a valid key.
+     */
+    private static byte[] hkdfSha256Expand(byte[] pseudoRandomKey, byte[] info)
+            throws InvalidKeyException {
+        // Note that RFC 5869 computes number of blocks N = ceil(hash length / output length), but
+        // here we only deal with a 256 bit hash up to a 256 bit output, yielding N=1.
+        Mac sha256;
+        try {
+            sha256 = Mac.getInstance(HmacSHA256);
+        } catch (NoSuchAlgorithmException e) {
+            // This can not happen - HmacSHA256 is supported by the platform.
+            throw new AssertionError(e);
+        }
+        sha256.init(new SecretKeySpec(pseudoRandomKey, AES));
+
+        sha256.update(info);
+        sha256.update(CONSTANT_01);
+        return sha256.doFinal();
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpoint.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpoint.java
new file mode 100644
index 000000000000..e867e7c1b801
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/IsChunkBreakpoint.java
@@ -0,0 +1,78 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking.cdc;
+
+import static com.android.internal.util.Preconditions.checkArgument;
+
+import com.android.server.backup.encryption.chunking.cdc.ContentDefinedChunker.BreakpointPredicate;
+
+/**
+ * Function to determine whether a 64-bit fingerprint ought to be a chunk breakpoint.
+ *
+ * <p>This works by checking whether there are at least n leading zeros in the fingerprint. n is
+ * calculated to on average cause a breakpoint after a given number of trials (provided in the
+ * constructor). This allows us to choose a number of trials that gives a desired average chunk
+ * size. This works because the fingerprint is pseudo-randomly distributed.
+ */
+public class IsChunkBreakpoint implements BreakpointPredicate {
+    private final int mLeadingZeros;
+    private final long mBitmask;
+
+    /**
+     * A new instance that causes a breakpoint after a given number of trials on average.
+     *
+     * @param averageNumberOfTrialsUntilBreakpoint The number of trials after which on average to
+     *     create a new chunk. If this is not a power of 2, some precision is sacrificed (i.e., on
+     *     average, breaks will actually happen after the nearest power of 2 to the average number
+     *     of trials passed in).
+     */
+    public IsChunkBreakpoint(long averageNumberOfTrialsUntilBreakpoint) {
+        checkArgument(
+                averageNumberOfTrialsUntilBreakpoint >= 0,
+                "Average number of trials must be non-negative");
+
+        // Want n leading zeros after t trials.
+        // P(leading zeros = n) = 1/2^n
+        // Expected num trials to get n leading zeros = 1/2^-n
+        // t = 1/2^-n
+        // n = log2(t)
+        mLeadingZeros = (int) Math.round(log2(averageNumberOfTrialsUntilBreakpoint));
+        mBitmask = ~(~0L >>> mLeadingZeros);
+    }
+
+    /**
+     * Returns {@code true} if {@code fingerprint} indicates that there should be a chunk
+     * breakpoint.
+     */
+    @Override
+    public boolean isBreakpoint(long fingerprint) {
+        return (fingerprint & mBitmask) == 0;
+    }
+
+    /** Returns the number of leading zeros in the fingerprint that causes a breakpoint. */
+    public int getLeadingZeros() {
+        return mLeadingZeros;
+    }
+
+    /**
+     * Calculates log base 2 of x. Not the most efficient possible implementation, but it's simple,
+     * obviously correct, and is only invoked on object construction.
+     */
+    private static double log2(double x) {
+        return Math.log(x) / Math.log(2);
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64.java
new file mode 100644
index 000000000000..1e14ffa5ad77
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64.java
@@ -0,0 +1,113 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.chunking.cdc;
+
+/** Helper to calculate a 64-bit Rabin fingerprint over a 31-byte window. */
+public class RabinFingerprint64 {
+    private static final long DEFAULT_IRREDUCIBLE_POLYNOMIAL_64 = 0x000000000000001BL;
+    private static final int POLYNOMIAL_DEGREE = 64;
+    private static final int SLIDING_WINDOW_SIZE_BYTES = 31;
+
+    private final long mPoly64;
+    // Auxiliary tables to speed up the computation of Rabin fingerprints.
+    private final long[] mTableFP64 = new long[256];
+    private final long[] mTableOutByte = new long[256];
+
+    /**
+     * Constructs a new instance over the given irreducible 64-degree polynomial. It is up to the
+     * caller to determine that the polynomial is irreducible. If it is not the fingerprinting will
+     * not behave as expected.
+     *
+     * @param poly64 The polynomial.
+     */
+    public RabinFingerprint64(long poly64) {
+        mPoly64 = poly64;
+    }
+
+    /** Constructs a new instance using {@code x^64 + x^4 + x + 1} as the irreducible polynomial. */
+    public RabinFingerprint64() {
+        this(DEFAULT_IRREDUCIBLE_POLYNOMIAL_64);
+        computeFingerprintTables64();
+        computeFingerprintTables64Windowed();
+    }
+
+    /**
+     * Computes the fingerprint for the new sliding window given the fingerprint of the previous
+     * sliding window, the byte sliding in, and the byte sliding out.
+     *
+     * @param inChar The new char coming into the sliding window.
+     * @param outChar The left most char sliding out of the window.
+     * @param fingerPrint Fingerprint for previous window.
+     * @return New fingerprint for the new sliding window.
+     */
+    public long computeFingerprint64(byte inChar, byte outChar, long fingerPrint) {
+        return (fingerPrint << 8)
+                ^ (inChar & 0xFF)
+                ^ mTableFP64[(int) (fingerPrint >>> 56)]
+                ^ mTableOutByte[outChar & 0xFF];
+    }
+
+    /** Compute auxiliary tables to speed up the fingerprint computation. */
+    private void computeFingerprintTables64() {
+        long[] degreesRes64 = new long[POLYNOMIAL_DEGREE];
+        degreesRes64[0] = mPoly64;
+        for (int i = 1; i < POLYNOMIAL_DEGREE; i++) {
+            if ((degreesRes64[i - 1] & (1L << 63)) == 0) {
+                degreesRes64[i] = degreesRes64[i - 1] << 1;
+            } else {
+                degreesRes64[i] = (degreesRes64[i - 1] << 1) ^ mPoly64;
+            }
+        }
+        for (int i = 0; i < 256; i++) {
+            int currIndex = i;
+            for (int j = 0; (currIndex > 0) && (j < 8); j++) {
+                if ((currIndex & 0x1) == 1) {
+                    mTableFP64[i] ^= degreesRes64[j];
+                }
+                currIndex >>>= 1;
+            }
+        }
+    }
+
+    /**
+     * Compute auxiliary table {@code mTableOutByte} to facilitate the computing of fingerprints for
+     * sliding windows. This table is to take care of the effect on the fingerprint when the
+     * leftmost byte in the window slides out.
+     */
+    private void computeFingerprintTables64Windowed() {
+        // Auxiliary array degsRes64[8] defined by: <code>degsRes64[i] = x^(8 *
+        // SLIDING_WINDOW_SIZE_BYTES + i) mod this.mPoly64.</code>
+        long[] degsRes64 = new long[8];
+        degsRes64[0] = mPoly64;
+        for (int i = 65; i < 8 * (SLIDING_WINDOW_SIZE_BYTES + 1); i++) {
+            if ((degsRes64[(i - 1) % 8] & (1L << 63)) == 0) {
+                degsRes64[i % 8] = degsRes64[(i - 1) % 8] << 1;
+            } else {
+                degsRes64[i % 8] = (degsRes64[(i - 1) % 8] << 1) ^ mPoly64;
+            }
+        }
+        for (int i = 0; i < 256; i++) {
+            int currIndex = i;
+            for (int j = 0; (currIndex > 0) && (j < 8); j++) {
+                if ((currIndex & 0x1) == 1) {
+                    mTableOutByte[i] ^= degsRes64[j];
+                }
+                currIndex >>>= 1;
+            }
+        }
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKey.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKey.java
new file mode 100644
index 000000000000..f356b4f102e2
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKey.java
@@ -0,0 +1,117 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.keys;
+
+import static com.android.internal.util.Preconditions.checkNotNull;
+
+import android.annotation.IntDef;
+import android.content.Context;
+import android.security.keystore.recovery.InternalRecoveryServiceException;
+import android.security.keystore.recovery.RecoveryController;
+import android.util.Slog;
+
+import javax.crypto.SecretKey;
+
+/**
+ * Wraps a {@link RecoveryController}'s {@link SecretKey}. These are kept in "AndroidKeyStore" (a
+ * provider for {@link java.security.KeyStore} and {@link javax.crypto.KeyGenerator}. They are also
+ * synced with the recoverable key store, wrapped by the primary key. This allows them to be
+ * recovered on a user's subsequent device through providing their lock screen secret.
+ */
+public class RecoverableKeyStoreSecondaryKey {
+    private static final String TAG = "RecoverableKeyStoreSecondaryKey";
+
+    private final String mAlias;
+    private final SecretKey mSecretKey;
+
+    /**
+     * A new instance.
+     *
+     * @param alias The alias. It is keyed with this in AndroidKeyStore and the recoverable key
+     *     store.
+     * @param secretKey The key.
+     */
+    public RecoverableKeyStoreSecondaryKey(String alias, SecretKey secretKey) {
+        mAlias = checkNotNull(alias);
+        mSecretKey = checkNotNull(secretKey);
+    }
+
+    /**
+     * The ID, as stored in the recoverable {@link java.security.KeyStore}, and as used to identify
+     * wrapped tertiary keys on the backup server.
+     */
+    public String getAlias() {
+        return mAlias;
+    }
+
+    /** The secret key, to be used to wrap tertiary keys. */
+    public SecretKey getSecretKey() {
+        return mSecretKey;
+    }
+
+    /**
+     * The status of the key. i.e., whether it's been synced to remote trusted hardware.
+     *
+     * @param context The application context.
+     * @return One of {@link Status#SYNCED}, {@link Status#NOT_SYNCED} or {@link Status#DESTROYED}.
+     */
+    public @Status int getStatus(Context context) {
+        try {
+            return getStatusInternal(context);
+        } catch (InternalRecoveryServiceException e) {
+            Slog.wtf(TAG, "Internal error getting recovery status", e);
+            // Return NOT_SYNCED by default, as we do not want the backups to fail or to repeatedly
+            // attempt to reinitialize.
+            return Status.NOT_SYNCED;
+        }
+    }
+
+    private @Status int getStatusInternal(Context context) throws InternalRecoveryServiceException {
+        int status = RecoveryController.getInstance(context).getRecoveryStatus(mAlias);
+        switch (status) {
+            case RecoveryController.RECOVERY_STATUS_PERMANENT_FAILURE:
+                return Status.DESTROYED;
+            case RecoveryController.RECOVERY_STATUS_SYNCED:
+                return Status.SYNCED;
+            case RecoveryController.RECOVERY_STATUS_SYNC_IN_PROGRESS:
+                return Status.NOT_SYNCED;
+            default:
+                // Throw an exception if we encounter a status that doesn't match any of the above.
+                throw new InternalRecoveryServiceException(
+                        "Unexpected status from getRecoveryStatus: " + status);
+        }
+    }
+
+    /** Status of a key in the recoverable key store. */
+    @IntDef({Status.NOT_SYNCED, Status.SYNCED, Status.DESTROYED})
+    public @interface Status {
+        /**
+         * The key has not yet been synced to remote trusted hardware. This may be because the user
+         * has not yet unlocked their device.
+         */
+        int NOT_SYNCED = 1;
+
+        /**
+         * The key has been synced with remote trusted hardware. It should now be recoverable on
+         * another device.
+         */
+        int SYNCED = 2;
+
+        /** The key has been lost forever. This can occur if the user disables their lock screen. */
+        int DESTROYED = 3;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyManager.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyManager.java
new file mode 100644
index 000000000000..c89076b9928f
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RecoverableKeyStoreSecondaryKeyManager.java
@@ -0,0 +1,120 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.keys;
+
+import android.content.Context;
+import android.security.keystore.recovery.InternalRecoveryServiceException;
+import android.security.keystore.recovery.LockScreenRequiredException;
+import android.security.keystore.recovery.RecoveryController;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import libcore.util.HexEncoding;
+
+import java.security.SecureRandom;
+import java.security.UnrecoverableKeyException;
+import java.util.Optional;
+
+import javax.crypto.SecretKey;
+
+/**
+ * Manages generating, deleting, and retrieving secondary keys through {@link RecoveryController}.
+ *
+ * <p>The recoverable key store will be synced remotely via the {@link RecoveryController}, allowing
+ * recovery of keys on other devices owned by the user.
+ */
+public class RecoverableKeyStoreSecondaryKeyManager {
+    private static final String BACKUP_KEY_ALIAS_PREFIX =
+            "com.android.server.backup/recoverablekeystore/";
+    private static final int BACKUP_KEY_SUFFIX_LENGTH_BITS = 128;
+    private static final int BITS_PER_BYTE = 8;
+
+    /** A new instance. */
+    public static RecoverableKeyStoreSecondaryKeyManager getInstance(Context context) {
+        return new RecoverableKeyStoreSecondaryKeyManager(
+                RecoveryController.getInstance(context), new SecureRandom());
+    }
+
+    private final RecoveryController mRecoveryController;
+    private final SecureRandom mSecureRandom;
+
+    @VisibleForTesting
+    public RecoverableKeyStoreSecondaryKeyManager(
+            RecoveryController recoveryController, SecureRandom secureRandom) {
+        mRecoveryController = recoveryController;
+        mSecureRandom = secureRandom;
+    }
+
+    /**
+     * Generates a new recoverable key using the {@link RecoveryController}.
+     *
+     * @throws InternalRecoveryServiceException if an unexpected error occurred generating the key.
+     * @throws LockScreenRequiredException if the user does not have a lock screen. A lock screen is
+     *     required to generate a recoverable key.
+     */
+    public RecoverableKeyStoreSecondaryKey generate()
+            throws InternalRecoveryServiceException, LockScreenRequiredException,
+                    UnrecoverableKeyException {
+        String alias = generateId();
+        mRecoveryController.generateKey(alias);
+        SecretKey key = (SecretKey) mRecoveryController.getKey(alias);
+        if (key == null) {
+            throw new InternalRecoveryServiceException(
+                    String.format(
+                            "Generated key %s but could not get it back immediately afterwards.",
+                            alias));
+        }
+        return new RecoverableKeyStoreSecondaryKey(alias, key);
+    }
+
+    /**
+     * Removes the secondary key. This means the key will no longer be recoverable.
+     *
+     * @param alias The alias of the key.
+     * @throws InternalRecoveryServiceException if there was a {@link RecoveryController} error.
+     */
+    public void remove(String alias) throws InternalRecoveryServiceException {
+        mRecoveryController.removeKey(alias);
+    }
+
+    /**
+     * Returns the {@link RecoverableKeyStoreSecondaryKey} with {@code alias} if it is in the {@link
+     * RecoveryController}. Otherwise, {@link Optional#empty()}.
+     */
+    public Optional<RecoverableKeyStoreSecondaryKey> get(String alias)
+            throws InternalRecoveryServiceException, UnrecoverableKeyException {
+        SecretKey secretKey = (SecretKey) mRecoveryController.getKey(alias);
+        return Optional.ofNullable(secretKey)
+                .map(key -> new RecoverableKeyStoreSecondaryKey(alias, key));
+    }
+
+    /**
+     * Generates a new key alias. This has more entropy than a UUID - it can be considered
+     * universally unique.
+     */
+    private String generateId() {
+        byte[] id = new byte[BACKUP_KEY_SUFFIX_LENGTH_BITS / BITS_PER_BYTE];
+        mSecureRandom.nextBytes(id);
+        return BACKUP_KEY_ALIAS_PREFIX + HexEncoding.encodeToString(id);
+    }
+
+    /** Constructs a {@link RecoverableKeyStoreSecondaryKeyManager}. */
+    public interface RecoverableKeyStoreSecondaryKeyManagerProvider {
+        /** Returns a newly constructed {@link RecoverableKeyStoreSecondaryKeyManager}. */
+        RecoverableKeyStoreSecondaryKeyManager get();
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyGenerator.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyGenerator.java
new file mode 100644
index 000000000000..a425c720b9b8
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyGenerator.java
@@ -0,0 +1,47 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.keys;
+
+import java.security.NoSuchAlgorithmException;
+import java.security.SecureRandom;
+
+import javax.crypto.KeyGenerator;
+import javax.crypto.SecretKey;
+
+/** 256-bit AES key generator. Each app should have its own separate AES key. */
+public class TertiaryKeyGenerator {
+    private static final int KEY_SIZE_BITS = 256;
+    private static final String KEY_ALGORITHM = "AES";
+
+    private final KeyGenerator mKeyGenerator;
+
+    /** New instance generating keys using {@code secureRandom}. */
+    public TertiaryKeyGenerator(SecureRandom secureRandom) {
+        try {
+            mKeyGenerator = KeyGenerator.getInstance(KEY_ALGORITHM);
+            mKeyGenerator.init(KEY_SIZE_BITS, secureRandom);
+        } catch (NoSuchAlgorithmException e) {
+            throw new AssertionError(
+                    "Impossible condition: JCE thinks it does not support AES.", e);
+        }
+    }
+
+    /** Generates a new random AES key. */
+    public SecretKey generate() {
+        return mKeyGenerator.generateKey();
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTracker.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTracker.java
new file mode 100644
index 000000000000..ec90f6c8c95e
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/TertiaryKeyRotationTracker.java
@@ -0,0 +1,113 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.keys;
+
+import android.content.Context;
+import android.content.SharedPreferences;
+import android.util.Slog;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.util.Locale;
+
+/**
+ * Tracks when a tertiary key rotation is due.
+ *
+ * <p>After a certain number of incremental backups, the device schedules a full backup, which will
+ * generate a new encryption key, effecting a key rotation. We should do this on a regular basis so
+ * that if a key does become compromised it has limited value to the attacker.
+ *
+ * <p>No additional synchronization of this class is provided. Only one instance should be used at
+ * any time. This should be fine as there should be no parallelism in backups.
+ */
+public class TertiaryKeyRotationTracker {
+    private static final int MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION = 31;
+    private static final String SHARED_PREFERENCES_NAME = "tertiary_key_rotation_tracker";
+
+    private static final String TAG = "TertiaryKeyRotationTracker";
+    private static final boolean DEBUG = false;
+
+    /**
+     * A new instance, using {@code context} to commit data to disk via {@link SharedPreferences}.
+     */
+    public static TertiaryKeyRotationTracker getInstance(Context context) {
+        return new TertiaryKeyRotationTracker(
+                context.getSharedPreferences(SHARED_PREFERENCES_NAME, Context.MODE_PRIVATE));
+    }
+
+    private final SharedPreferences mSharedPreferences;
+
+    /** New instance, storing data in {@code mSharedPreferences}. */
+    @VisibleForTesting
+    TertiaryKeyRotationTracker(SharedPreferences sharedPreferences) {
+        mSharedPreferences = sharedPreferences;
+    }
+
+    /**
+     * Returns {@code true} if the given app is due having its key rotated.
+     *
+     * @param packageName The package name of the app.
+     */
+    public boolean isKeyRotationDue(String packageName) {
+        return getBackupsSinceRotation(packageName) >= MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION;
+    }
+
+    /**
+     * Records that an incremental backup has occurred. Each incremental backup brings the app
+     * closer to the time when its key should be rotated.
+     *
+     * @param packageName The package name of the app for which the backup occurred.
+     */
+    public void recordBackup(String packageName) {
+        int backupsSinceRotation = getBackupsSinceRotation(packageName) + 1;
+        mSharedPreferences.edit().putInt(packageName, backupsSinceRotation).apply();
+        if (DEBUG) {
+            Slog.d(
+                    TAG,
+                    String.format(
+                            Locale.US,
+                            "Incremental backup for %s. %d backups until key rotation.",
+                            packageName,
+                            Math.max(
+                                    0,
+                                    MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION
+                                            - backupsSinceRotation)));
+        }
+    }
+
+    /**
+     * Resets the rotation delay for the given app. Should be invoked after a key rotation.
+     *
+     * @param packageName Package name of the app whose key has rotated.
+     */
+    public void resetCountdown(String packageName) {
+        mSharedPreferences.edit().putInt(packageName, 0).apply();
+    }
+
+    /** Marks all enrolled packages for key rotation. */
+    public void markAllForRotation() {
+        SharedPreferences.Editor editor = mSharedPreferences.edit();
+        for (String packageName : mSharedPreferences.getAll().keySet()) {
+            editor.putInt(packageName, MAX_BACKUPS_UNTIL_TERTIARY_KEY_ROTATION);
+        }
+        editor.apply();
+    }
+
+    private int getBackupsSinceRotation(String packageName) {
+        return mSharedPreferences.getInt(packageName, 0);
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDb.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDb.java
new file mode 100644
index 000000000000..9f6c03a6f393
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDb.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.storage;
+
+import android.content.Context;
+
+/**
+ * Backup encryption SQLite database. All instances are threadsafe.
+ *
+ * <p>The database is automatically opened when accessing one of the tables. After the caller is
+ * done they must call {@link #close()}.
+ */
+public class BackupEncryptionDb {
+    private final BackupEncryptionDbHelper mHelper;
+
+    /** A new instance, using the storage defined by {@code context}. */
+    public static BackupEncryptionDb newInstance(Context context) {
+        BackupEncryptionDbHelper helper = new BackupEncryptionDbHelper(context);
+        helper.setWriteAheadLoggingEnabled(true);
+        return new BackupEncryptionDb(helper);
+    }
+
+    private BackupEncryptionDb(BackupEncryptionDbHelper helper) {
+        mHelper = helper;
+    }
+
+    public TertiaryKeysTable getTertiaryKeysTable() {
+        return new TertiaryKeysTable(mHelper);
+    }
+
+    /** Deletes the database. */
+    public void clear() throws EncryptionDbException {
+        mHelper.resetDatabase();
+    }
+
+    /**
+     * Closes the database if it is open.
+     *
+     * <p>After calling this, the caller may access one of the tables again which will automatically
+     * reopen the database.
+     */
+    public void close() {
+        mHelper.close();
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDbContract.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDbContract.java
new file mode 100644
index 000000000000..5e8a8d9fc2ae
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDbContract.java
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.storage;
+
+import android.provider.BaseColumns;
+
+/** Contract for the backup encryption database. Describes tables present. */
+class BackupEncryptionDbContract {
+    /**
+     * Table containing tertiary keys belonging to the user. Tertiary keys are wrapped by a
+     * secondary key, which never leaves {@code AndroidKeyStore} (a provider for {@link
+     * java.security.KeyStore}). Each application has a tertiary key, which is used to encrypt the
+     * backup data.
+     */
+    static class TertiaryKeysEntry implements BaseColumns {
+        static final String TABLE_NAME = "tertiary_keys";
+
+        /** Alias of the secondary key used to wrap the tertiary key. */
+        static final String COLUMN_NAME_SECONDARY_KEY_ALIAS = "secondary_key_alias";
+
+        /** Name of the package to which the tertiary key belongs. */
+        static final String COLUMN_NAME_PACKAGE_NAME = "package_name";
+
+        /** Encrypted bytes of the tertiary key. */
+        static final String COLUMN_NAME_WRAPPED_KEY_BYTES = "wrapped_key_bytes";
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDbHelper.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDbHelper.java
new file mode 100644
index 000000000000..c70634248dca
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/BackupEncryptionDbHelper.java
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.storage;
+
+import static com.android.server.backup.encryption.storage.BackupEncryptionDbContract.TertiaryKeysEntry;
+
+import android.content.Context;
+import android.database.sqlite.SQLiteDatabase;
+import android.database.sqlite.SQLiteException;
+import android.database.sqlite.SQLiteOpenHelper;
+
+/** Helper for creating an instance of the backup encryption database. */
+class BackupEncryptionDbHelper extends SQLiteOpenHelper {
+    private static final int DATABASE_VERSION = 1;
+    static final String DATABASE_NAME = "backupencryption.db";
+
+    private static final String SQL_CREATE_TERTIARY_KEYS_ENTRY =
+            "CREATE TABLE "
+                    + TertiaryKeysEntry.TABLE_NAME
+                    + " ( "
+                    + TertiaryKeysEntry._ID
+                    + " INTEGER PRIMARY KEY,"
+                    + TertiaryKeysEntry.COLUMN_NAME_SECONDARY_KEY_ALIAS
+                    + " TEXT,"
+                    + TertiaryKeysEntry.COLUMN_NAME_PACKAGE_NAME
+                    + " TEXT,"
+                    + TertiaryKeysEntry.COLUMN_NAME_WRAPPED_KEY_BYTES
+                    + " BLOB,"
+                    + "UNIQUE("
+                    + TertiaryKeysEntry.COLUMN_NAME_SECONDARY_KEY_ALIAS
+                    + ","
+                    + TertiaryKeysEntry.COLUMN_NAME_PACKAGE_NAME
+                    + "))";
+
+    private static final String SQL_DROP_TERTIARY_KEYS_ENTRY =
+            "DROP TABLE IF EXISTS " + TertiaryKeysEntry.TABLE_NAME;
+
+    BackupEncryptionDbHelper(Context context) {
+        super(context, DATABASE_NAME, /*factory=*/ null, DATABASE_VERSION);
+    }
+
+    public void resetDatabase() throws EncryptionDbException {
+        SQLiteDatabase db = getWritableDatabaseSafe();
+        db.execSQL(SQL_DROP_TERTIARY_KEYS_ENTRY);
+        onCreate(db);
+    }
+
+    @Override
+    public void onCreate(SQLiteDatabase db) {
+        db.execSQL(SQL_CREATE_TERTIARY_KEYS_ENTRY);
+    }
+
+    @Override
+    public void onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) {
+        db.execSQL(SQL_DROP_TERTIARY_KEYS_ENTRY);
+        onCreate(db);
+    }
+
+    @Override
+    public void onDowngrade(SQLiteDatabase db, int oldVersion, int newVersion) {
+        db.execSQL(SQL_DROP_TERTIARY_KEYS_ENTRY);
+        onCreate(db);
+    }
+
+    /**
+     * Calls {@link #getWritableDatabase()}, but catches the unchecked {@link SQLiteException} and
+     * rethrows {@link EncryptionDbException}.
+     */
+    public SQLiteDatabase getWritableDatabaseSafe() throws EncryptionDbException {
+        try {
+            return super.getWritableDatabase();
+        } catch (SQLiteException e) {
+            throw new EncryptionDbException(e);
+        }
+    }
+
+    /**
+     * Calls {@link #getReadableDatabase()}, but catches the unchecked {@link SQLiteException} and
+     * rethrows {@link EncryptionDbException}.
+     */
+    public SQLiteDatabase getReadableDatabaseSafe() throws EncryptionDbException {
+        try {
+            return super.getReadableDatabase();
+        } catch (SQLiteException e) {
+            throw new EncryptionDbException(e);
+        }
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/EncryptionDbException.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/EncryptionDbException.java
new file mode 100644
index 000000000000..82f7dead1b50
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/EncryptionDbException.java
@@ -0,0 +1,26 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.storage;
+
+import java.io.IOException;
+
+/** Thrown when there is a problem reading or writing the encryption database. */
+public class EncryptionDbException extends IOException {
+    public EncryptionDbException(Throwable cause) {
+        super(cause);
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/TertiaryKey.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/TertiaryKey.java
new file mode 100644
index 000000000000..39a2c6ebb9c3
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/TertiaryKey.java
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.storage;
+
+/** Wrapped bytes of a tertiary key. */
+public class TertiaryKey {
+    private final String mSecondaryKeyAlias;
+    private final String mPackageName;
+    private final byte[] mWrappedKeyBytes;
+
+    /**
+     * Creates a new instance.
+     *
+     * @param secondaryKeyAlias Alias of the secondary used to wrap the key.
+     * @param packageName The package name of the app to which the key belongs.
+     * @param wrappedKeyBytes The wrapped key bytes.
+     */
+    public TertiaryKey(String secondaryKeyAlias, String packageName, byte[] wrappedKeyBytes) {
+        mSecondaryKeyAlias = secondaryKeyAlias;
+        mPackageName = packageName;
+        mWrappedKeyBytes = wrappedKeyBytes;
+    }
+
+    /** Returns the alias of the secondary key used to wrap this tertiary key. */
+    public String getSecondaryKeyAlias() {
+        return mSecondaryKeyAlias;
+    }
+
+    /** Returns the package name of the application this key relates to. */
+    public String getPackageName() {
+        return mPackageName;
+    }
+
+    /** Returns the wrapped bytes of the key. */
+    public byte[] getWrappedKeyBytes() {
+        return mWrappedKeyBytes;
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/TertiaryKeysTable.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/TertiaryKeysTable.java
new file mode 100644
index 000000000000..d8d40c402a84
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/storage/TertiaryKeysTable.java
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2018 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.storage;
+
+import static com.android.server.backup.encryption.storage.BackupEncryptionDbContract.TertiaryKeysEntry;
+
+import android.content.ContentValues;
+import android.database.Cursor;
+import android.database.sqlite.SQLiteDatabase;
+import android.util.ArrayMap;
+
+import java.util.Collections;
+import java.util.Map;
+import java.util.Optional;
+
+/** Database table for storing and retrieving tertiary keys. */
+public class TertiaryKeysTable {
+    private final BackupEncryptionDbHelper mHelper;
+
+    TertiaryKeysTable(BackupEncryptionDbHelper helper) {
+        mHelper = helper;
+    }
+
+    /**
+     * Adds the {@code tertiaryKey} to the database.
+     *
+     * @return The primary key of the inserted row if successful, -1 otherwise.
+     */
+    public long addKey(TertiaryKey tertiaryKey) throws EncryptionDbException {
+        SQLiteDatabase db = mHelper.getWritableDatabaseSafe();
+        ContentValues values = new ContentValues();
+        values.put(
+                TertiaryKeysEntry.COLUMN_NAME_SECONDARY_KEY_ALIAS,
+                tertiaryKey.getSecondaryKeyAlias());
+        values.put(TertiaryKeysEntry.COLUMN_NAME_PACKAGE_NAME, tertiaryKey.getPackageName());
+        values.put(
+                TertiaryKeysEntry.COLUMN_NAME_WRAPPED_KEY_BYTES, tertiaryKey.getWrappedKeyBytes());
+        return db.replace(TertiaryKeysEntry.TABLE_NAME, /*nullColumnHack=*/ null, values);
+    }
+
+    /** Gets the key wrapped by {@code secondaryKeyAlias} for app with {@code packageName}. */
+    public Optional<TertiaryKey> getKey(String secondaryKeyAlias, String packageName)
+            throws EncryptionDbException {
+        SQLiteDatabase db = mHelper.getReadableDatabaseSafe();
+        String[] projection = {
+            TertiaryKeysEntry._ID,
+            TertiaryKeysEntry.COLUMN_NAME_SECONDARY_KEY_ALIAS,
+            TertiaryKeysEntry.COLUMN_NAME_PACKAGE_NAME,
+            TertiaryKeysEntry.COLUMN_NAME_WRAPPED_KEY_BYTES
+        };
+        String selection =
+                TertiaryKeysEntry.COLUMN_NAME_SECONDARY_KEY_ALIAS
+                        + " = ? AND "
+                        + TertiaryKeysEntry.COLUMN_NAME_PACKAGE_NAME
+                        + " = ?";
+        String[] selectionArguments = {secondaryKeyAlias, packageName};
+
+        try (Cursor cursor =
+                db.query(
+                        TertiaryKeysEntry.TABLE_NAME,
+                        projection,
+                        selection,
+                        selectionArguments,
+                        /*groupBy=*/ null,
+                        /*having=*/ null,
+                        /*orderBy=*/ null)) {
+            int count = cursor.getCount();
+            if (count == 0) {
+                return Optional.empty();
+            }
+
+            cursor.moveToFirst();
+            byte[] wrappedKeyBytes =
+                    cursor.getBlob(
+                            cursor.getColumnIndexOrThrow(
+                                    TertiaryKeysEntry.COLUMN_NAME_WRAPPED_KEY_BYTES));
+            return Optional.of(new TertiaryKey(secondaryKeyAlias, packageName, wrappedKeyBytes));
+        }
+    }
+
+    /** Returns all keys wrapped with {@code tertiaryKeyAlias} as an unmodifiable map. */
+    public Map<String, TertiaryKey> getAllKeys(String secondaryKeyAlias)
+            throws EncryptionDbException {
+        SQLiteDatabase db = mHelper.getReadableDatabaseSafe();
+        String[] projection = {
+            TertiaryKeysEntry._ID,
+            TertiaryKeysEntry.COLUMN_NAME_SECONDARY_KEY_ALIAS,
+            TertiaryKeysEntry.COLUMN_NAME_PACKAGE_NAME,
+            TertiaryKeysEntry.COLUMN_NAME_WRAPPED_KEY_BYTES
+        };
+        String selection = TertiaryKeysEntry.COLUMN_NAME_SECONDARY_KEY_ALIAS + " = ?";
+        String[] selectionArguments = {secondaryKeyAlias};
+
+        Map<String, TertiaryKey> keysByPackageName = new ArrayMap<>();
+        try (Cursor cursor =
+                db.query(
+                        TertiaryKeysEntry.TABLE_NAME,
+                        projection,
+                        selection,
+                        selectionArguments,
+                        /*groupBy=*/ null,
+                        /*having=*/ null,
+                        /*orderBy=*/ null)) {
+            while (cursor.moveToNext()) {
+                String packageName =
+                        cursor.getString(
+                                cursor.getColumnIndexOrThrow(
+                                        TertiaryKeysEntry.COLUMN_NAME_PACKAGE_NAME));
+                byte[] wrappedKeyBytes =
+                        cursor.getBlob(
+                                cursor.getColumnIndexOrThrow(
+                                        TertiaryKeysEntry.COLUMN_NAME_WRAPPED_KEY_BYTES));
+                keysByPackageName.put(
+                        packageName,
+                        new TertiaryKey(secondaryKeyAlias, packageName, wrappedKeyBytes));
+            }
+        }
+        return Collections.unmodifiableMap(keysByPackageName);
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/BackupEncrypter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/BackupEncrypter.java
new file mode 100644
index 000000000000..95d0d97b4073
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/BackupEncrypter.java
@@ -0,0 +1,90 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.tasks;
+
+import static java.util.Collections.unmodifiableList;
+
+import android.annotation.Nullable;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+import com.android.server.backup.encryption.chunking.EncryptedChunk;
+
+import java.io.IOException;
+import java.security.GeneralSecurityException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Set;
+
+import javax.crypto.SecretKey;
+
+/** Task which reads data from some source, splits it into chunks and encrypts new chunks. */
+public interface BackupEncrypter {
+    /** The algorithm which we use to compute the digest of the backup file plaintext. */
+    String MESSAGE_DIGEST_ALGORITHM = "SHA-256";
+
+    /**
+     * Splits the backup input into encrypted chunks and encrypts new chunks.
+     *
+     * @param secretKey Key used to encrypt backup.
+     * @param fingerprintMixerSalt Fingerprint mixer salt used for content-defined chunking during a
+     *     full backup. Should be {@code null} for a key-value backup.
+     * @param existingChunks Set of the SHA-256 Macs of chunks the server already has.
+     * @return a result containing an array of new encrypted chunks to upload, and an ordered
+     *     listing of the chunks in the backup file.
+     * @throws IOException if a problem occurs reading from the backup data.
+     * @throws GeneralSecurityException if there is a problem encrypting the data.
+     */
+    Result backup(
+            SecretKey secretKey,
+            @Nullable byte[] fingerprintMixerSalt,
+            Set<ChunkHash> existingChunks)
+            throws IOException, GeneralSecurityException;
+
+    /**
+     * The result of an incremental backup. Contains new encrypted chunks to upload, and an ordered
+     * list of the chunks in the backup file.
+     */
+    class Result {
+        private final List<ChunkHash> mAllChunks;
+        private final List<EncryptedChunk> mNewChunks;
+        private final byte[] mDigest;
+
+        public Result(List<ChunkHash> allChunks, List<EncryptedChunk> newChunks, byte[] digest) {
+            mAllChunks = unmodifiableList(new ArrayList<>(allChunks));
+            mDigest = digest;
+            mNewChunks = unmodifiableList(new ArrayList<>(newChunks));
+        }
+
+        /**
+         * Returns an unmodifiable list of the hashes of all the chunks in the backup, in the order
+         * they appear in the plaintext.
+         */
+        public List<ChunkHash> getAllChunks() {
+            return mAllChunks;
+        }
+
+        /** Returns an unmodifiable list of the new chunks in the backup. */
+        public List<EncryptedChunk> getNewChunks() {
+            return mNewChunks;
+        }
+
+        /** Returns the message digest of the backup. */
+        public byte[] getDigest() {
+            return mDigest;
+        }
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/BackupStreamEncrypter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/BackupStreamEncrypter.java
new file mode 100644
index 000000000000..45798d32885a
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/BackupStreamEncrypter.java
@@ -0,0 +1,127 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.tasks;
+
+import android.util.Slog;
+
+import com.android.server.backup.encryption.chunk.ChunkHash;
+import com.android.server.backup.encryption.chunking.ChunkEncryptor;
+import com.android.server.backup.encryption.chunking.ChunkHasher;
+import com.android.server.backup.encryption.chunking.EncryptedChunk;
+import com.android.server.backup.encryption.chunking.cdc.ContentDefinedChunker;
+import com.android.server.backup.encryption.chunking.cdc.FingerprintMixer;
+import com.android.server.backup.encryption.chunking.cdc.IsChunkBreakpoint;
+import com.android.server.backup.encryption.chunking.cdc.RabinFingerprint64;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.security.GeneralSecurityException;
+import java.security.MessageDigest;
+import java.security.SecureRandom;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import javax.crypto.SecretKey;
+
+/**
+ * Splits backup data into variable-sized chunks using content-defined chunking, then encrypts the
+ * chunks. Given a hash of the SHA-256s of existing chunks, performs an incremental backup (i.e.,
+ * only encrypts new chunks).
+ */
+public class BackupStreamEncrypter implements BackupEncrypter {
+    private static final String TAG = "BackupStreamEncryptor";
+
+    private final InputStream mData;
+    private final int mMinChunkSizeBytes;
+    private final int mMaxChunkSizeBytes;
+    private final int mAverageChunkSizeBytes;
+
+    /**
+     * A new instance over the given distribution of chunk sizes.
+     *
+     * @param data The data to be backed up.
+     * @param minChunkSizeBytes The minimum chunk size. No chunk will be smaller than this.
+     * @param maxChunkSizeBytes The maximum chunk size. No chunk will be larger than this.
+     * @param averageChunkSizeBytes The average chunk size. The mean size of chunks will be roughly
+     *     this (with a few tens of bytes of overhead for the initialization vector and message
+     *     authentication code).
+     */
+    public BackupStreamEncrypter(
+            InputStream data,
+            int minChunkSizeBytes,
+            int maxChunkSizeBytes,
+            int averageChunkSizeBytes) {
+        this.mData = data;
+        this.mMinChunkSizeBytes = minChunkSizeBytes;
+        this.mMaxChunkSizeBytes = maxChunkSizeBytes;
+        this.mAverageChunkSizeBytes = averageChunkSizeBytes;
+    }
+
+    @Override
+    public Result backup(
+            SecretKey secretKey, byte[] fingerprintMixerSalt, Set<ChunkHash> existingChunks)
+            throws IOException, GeneralSecurityException {
+        MessageDigest messageDigest =
+                MessageDigest.getInstance(BackupEncrypter.MESSAGE_DIGEST_ALGORITHM);
+        RabinFingerprint64 rabinFingerprint64 = new RabinFingerprint64();
+        FingerprintMixer fingerprintMixer = new FingerprintMixer(secretKey, fingerprintMixerSalt);
+        IsChunkBreakpoint isChunkBreakpoint =
+                new IsChunkBreakpoint(mAverageChunkSizeBytes - mMinChunkSizeBytes);
+        ContentDefinedChunker chunker =
+                new ContentDefinedChunker(
+                        mMinChunkSizeBytes,
+                        mMaxChunkSizeBytes,
+                        rabinFingerprint64,
+                        fingerprintMixer,
+                        isChunkBreakpoint);
+        ChunkHasher chunkHasher = new ChunkHasher(secretKey);
+        ChunkEncryptor encryptor = new ChunkEncryptor(secretKey, new SecureRandom());
+        Set<ChunkHash> includedChunks = new HashSet<>();
+        // New chunks will be added only once to this list, even if they occur multiple times.
+        List<EncryptedChunk> newChunks = new ArrayList<>();
+        // All chunks (including multiple occurrences) will be added to the chunkListing.
+        List<ChunkHash> chunkListing = new ArrayList<>();
+
+        includedChunks.addAll(existingChunks);
+
+        chunker.chunkify(
+                mData,
+                chunk -> {
+                    messageDigest.update(chunk);
+                    ChunkHash key = chunkHasher.computeHash(chunk);
+
+                    if (!includedChunks.contains(key)) {
+                        newChunks.add(encryptor.encrypt(key, chunk));
+                        includedChunks.add(key);
+                    }
+                    chunkListing.add(key);
+                });
+
+        Slog.i(
+                TAG,
+                String.format(
+                        "Chunks: %d total, %d unique, %d new",
+                        chunkListing.size(), new HashSet<>(chunkListing).size(), newChunks.size()));
+        return new Result(
+                Collections.unmodifiableList(chunkListing),
+                Collections.unmodifiableList(newChunks),
+                messageDigest.digest());
+    }
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/DecryptedChunkOutput.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/DecryptedChunkOutput.java
new file mode 100644
index 000000000000..e3df3c1eb96f
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/DecryptedChunkOutput.java
@@ -0,0 +1,54 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.tasks;
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.security.InvalidKeyException;
+
+/**
+ * Accepts the plaintext bytes of decrypted chunks and writes them to some output. Also keeps track
+ * of the message digest of the chunks.
+ */
+public interface DecryptedChunkOutput extends Closeable {
+    /**
+     * Opens whatever output the implementation chooses, ready to process chunks.
+     *
+     * @return {@code this}, to allow use with try-with-resources
+     */
+    DecryptedChunkOutput open() throws IOException;
+
+    /**
+     * Writes the plaintext bytes of chunk to whatever output the implementation chooses. Also
+     * updates the digest with the chunk.
+     *
+     * <p>You must call {@link #open()} before this method, and you may not call it after calling
+     * {@link Closeable#close()}.
+     *
+     * @param plaintextBuffer An array containing the bytes of the plaintext of the chunk, starting
+     *     at index 0.
+     * @param length The length in bytes of the plaintext contained in {@code plaintextBuffer}.
+     */
+    void processChunk(byte[] plaintextBuffer, int length) throws IOException, InvalidKeyException;
+
+    /**
+     * Returns the message digest of all the chunks processed by {@link #processChunk}.
+     *
+     * <p>You must call {@link Closeable#close()} before calling this method.
+     */
+    byte[] getDigest();
+}
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/EncryptedRestoreException.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/EncryptedRestoreException.java
new file mode 100644
index 000000000000..487c0d92f6fd
--- /dev/null
+++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/EncryptedRestoreException.java
@@ -0,0 +1,32 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.backup.encryption.tasks;
+
+/** Wraps any exception related to encryption which occurs during restore. */
+public class EncryptedRestoreException extends Exception {
+    public EncryptedRestoreException(String message) {
+        super(message);
+    }
+
+    public EncryptedRestoreException(Throwable cause) {
+        super(cause);
+    }
+
+    public EncryptedRestoreException(String message, Throwable cause) {
+        super(message, cause);
+    }
+}