diff options
Diffstat (limited to 'packages/BackupEncryption/src')
41 files changed, 3196 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/KeyWrapUtils.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/KeyWrapUtils.java new file mode 100644 index 000000000000..a043c1fe687f --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/KeyWrapUtils.java @@ -0,0 +1,132 @@ +/* + * 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.keys; + +import com.android.server.backup.encryption.protos.nano.WrappedKeyProto; + +import java.security.InvalidAlgorithmParameterException; +import java.security.InvalidKeyException; +import java.security.NoSuchAlgorithmException; +import java.util.Locale; + +import javax.crypto.Cipher; +import javax.crypto.IllegalBlockSizeException; +import javax.crypto.NoSuchPaddingException; +import javax.crypto.SecretKey; +import javax.crypto.spec.GCMParameterSpec; + +/** Utility functions for wrapping and unwrapping tertiary keys. */ +public class KeyWrapUtils { + private static final String AES_GCM_MODE = "AES/GCM/NoPadding"; + private static final int GCM_TAG_LENGTH_BYTES = 16; + private static final int BITS_PER_BYTE = 8; + private static final int GCM_TAG_LENGTH_BITS = GCM_TAG_LENGTH_BYTES * BITS_PER_BYTE; + private static final String KEY_ALGORITHM = "AES"; + + /** + * Uses the secondary key to unwrap the wrapped tertiary key. + * + * @param secondaryKey The secondary key used to wrap the tertiary key. + * @param wrappedKey The wrapped tertiary key. + * @return The unwrapped tertiary key. + * @throws InvalidKeyException if the provided secondary key cannot unwrap the tertiary key. + */ + public static SecretKey unwrap(SecretKey secondaryKey, WrappedKeyProto.WrappedKey wrappedKey) + throws InvalidKeyException, NoSuchAlgorithmException, + InvalidAlgorithmParameterException, NoSuchPaddingException { + if (wrappedKey.wrapAlgorithm != WrappedKeyProto.WrappedKey.AES_256_GCM) { + throw new InvalidKeyException( + String.format( + Locale.US, + "Could not unwrap key wrapped with %s algorithm", + wrappedKey.wrapAlgorithm)); + } + + if (wrappedKey.metadata == null) { + throw new InvalidKeyException("Metadata missing from wrapped tertiary key."); + } + + if (wrappedKey.metadata.type != WrappedKeyProto.KeyMetadata.AES_256_GCM) { + throw new InvalidKeyException( + String.format( + Locale.US, + "Wrapped key was unexpected %s algorithm. Only support" + + " AES/GCM/NoPadding.", + wrappedKey.metadata.type)); + } + + Cipher cipher = getCipher(); + + cipher.init( + Cipher.UNWRAP_MODE, + secondaryKey, + new GCMParameterSpec(GCM_TAG_LENGTH_BITS, wrappedKey.nonce)); + + return (SecretKey) cipher.unwrap(wrappedKey.key, KEY_ALGORITHM, Cipher.SECRET_KEY); + } + + /** + * Wraps the tertiary key with the secondary key. + * + * @param secondaryKey The secondary key to use for wrapping. + * @param tertiaryKey The key to wrap. + * @return The wrapped key. + * @throws InvalidKeyException if the key is not good for wrapping. + * @throws IllegalBlockSizeException if there is an issue wrapping. + */ + public static WrappedKeyProto.WrappedKey wrap(SecretKey secondaryKey, SecretKey tertiaryKey) + throws InvalidKeyException, IllegalBlockSizeException, NoSuchAlgorithmException, + NoSuchPaddingException { + Cipher cipher = getCipher(); + cipher.init(Cipher.WRAP_MODE, secondaryKey); + + WrappedKeyProto.WrappedKey wrappedKey = new WrappedKeyProto.WrappedKey(); + wrappedKey.key = cipher.wrap(tertiaryKey); + wrappedKey.nonce = cipher.getIV(); + wrappedKey.wrapAlgorithm = WrappedKeyProto.WrappedKey.AES_256_GCM; + wrappedKey.metadata = new WrappedKeyProto.KeyMetadata(); + wrappedKey.metadata.type = WrappedKeyProto.KeyMetadata.AES_256_GCM; + return wrappedKey; + } + + /** + * Rewraps a tertiary key with a new secondary key. + * + * @param oldSecondaryKey The old secondary key, used to unwrap the tertiary key. + * @param newSecondaryKey The new secondary key, used to rewrap the tertiary key. + * @param tertiaryKey The tertiary key, wrapped by {@code oldSecondaryKey}. + * @return The tertiary key, wrapped by {@code newSecondaryKey}. + * @throws InvalidKeyException if the key is not good for wrapping or unwrapping. + * @throws IllegalBlockSizeException if there is an issue wrapping. + */ + public static WrappedKeyProto.WrappedKey rewrap( + SecretKey oldSecondaryKey, + SecretKey newSecondaryKey, + WrappedKeyProto.WrappedKey tertiaryKey) + throws InvalidKeyException, IllegalBlockSizeException, + InvalidAlgorithmParameterException, NoSuchAlgorithmException, + NoSuchPaddingException { + return wrap(newSecondaryKey, unwrap(oldSecondaryKey, tertiaryKey)); + } + + private static Cipher getCipher() throws NoSuchPaddingException, NoSuchAlgorithmException { + return Cipher.getInstance(AES_GCM_MODE); + } + + // Statics only + private KeyWrapUtils() {} +} 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/RestoreKeyFetcher.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RestoreKeyFetcher.java new file mode 100644 index 000000000000..6fb958bd1c1e --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/keys/RestoreKeyFetcher.java @@ -0,0 +1,71 @@ +/* + * 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.keys; + +import android.security.keystore.recovery.InternalRecoveryServiceException; + +import com.android.server.backup.encryption.keys.RecoverableKeyStoreSecondaryKeyManager.RecoverableKeyStoreSecondaryKeyManagerProvider; +import com.android.server.backup.encryption.protos.nano.WrappedKeyProto; + +import java.security.InvalidAlgorithmParameterException; +import java.security.KeyException; +import java.security.NoSuchAlgorithmException; +import java.security.UnrecoverableKeyException; +import java.util.Optional; + +import javax.crypto.NoSuchPaddingException; +import javax.crypto.SecretKey; + +/** Fetches the secondary key and uses it to unwrap the tertiary key during restore. */ +public class RestoreKeyFetcher { + + /** + * Retrieves the secondary key with the given alias and uses it to unwrap the given wrapped + * tertiary key. + * + * @param secondaryKeyManagerProvider Provider which creates {@link + * RecoverableKeyStoreSecondaryKeyManager} + * @param secondaryKeyAlias Alias of the secondary key used to wrap the tertiary key + * @param wrappedTertiaryKey Tertiary key wrapped with the secondary key above + * @return The unwrapped tertiary key + */ + public static SecretKey unwrapTertiaryKey( + RecoverableKeyStoreSecondaryKeyManagerProvider secondaryKeyManagerProvider, + String secondaryKeyAlias, + WrappedKeyProto.WrappedKey wrappedTertiaryKey) + throws KeyException, InvalidAlgorithmParameterException, NoSuchAlgorithmException, + NoSuchPaddingException { + Optional<RecoverableKeyStoreSecondaryKey> secondaryKey = + getSecondaryKey(secondaryKeyManagerProvider, secondaryKeyAlias); + if (!secondaryKey.isPresent()) { + throw new KeyException("No key:" + secondaryKeyAlias); + } + + return KeyWrapUtils.unwrap(secondaryKey.get().getSecretKey(), wrappedTertiaryKey); + } + + private static Optional<RecoverableKeyStoreSecondaryKey> getSecondaryKey( + RecoverableKeyStoreSecondaryKeyManagerProvider secondaryKeyManagerProvider, + String secondaryKeyAlias) + throws KeyException { + try { + return secondaryKeyManagerProvider.get().get(secondaryKeyAlias); + } catch (InternalRecoveryServiceException | UnrecoverableKeyException e) { + throw new KeyException("Could not retrieve key:" + secondaryKeyAlias, e); + } + } +} 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); + } +} |