diff options
Diffstat (limited to 'packages/BackupEncryption/src')
4 files changed, 721 insertions, 0 deletions
diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/BackupFileBuilder.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/BackupFileBuilder.java new file mode 100644 index 000000000000..3d3fb552bb58 --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/chunking/BackupFileBuilder.java @@ -0,0 +1,232 @@ +/* + * 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.checkArgument; +import static com.android.internal.util.Preconditions.checkNotNull; +import static com.android.internal.util.Preconditions.checkState; + +import android.annotation.Nullable; +import android.util.Slog; + +import com.android.server.backup.encryption.chunk.ChunkHash; +import com.android.server.backup.encryption.chunk.ChunkListingMap; +import com.android.server.backup.encryption.protos.nano.ChunksMetadataProto; + +import java.io.IOException; +import java.io.OutputStream; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Writes batches of {@link EncryptedChunk} to a diff script, and generates the associated {@link + * ChunksMetadataProto.ChunkListing} and {@link ChunksMetadataProto.ChunkOrdering}. + */ +public class BackupFileBuilder { + private static final String TAG = "BackupFileBuilder"; + + private static final int BYTES_PER_KILOBYTE = 1024; + + private final BackupWriter mBackupWriter; + private final EncryptedChunkEncoder mEncryptedChunkEncoder; + private final ChunkListingMap mOldChunkListing; + private final ChunksMetadataProto.ChunkListing mNewChunkListing; + private final ChunksMetadataProto.ChunkOrdering mChunkOrdering; + private final List<ChunksMetadataProto.Chunk> mKnownChunks = new ArrayList<>(); + private final List<Integer> mKnownStarts = new ArrayList<>(); + private final Map<ChunkHash, Long> mChunkStartPositions; + + private long mNewChunksSizeBytes; + private boolean mFinished; + + /** + * Constructs a new instance which writes raw data to the given {@link OutputStream}, without + * generating a diff. + * + * <p>This class never closes the output stream. + */ + public static BackupFileBuilder createForNonIncremental(OutputStream outputStream) { + return new BackupFileBuilder( + new RawBackupWriter(outputStream), new ChunksMetadataProto.ChunkListing()); + } + + /** + * Constructs a new instance which writes a diff script to the given {@link OutputStream} using + * a {@link SingleStreamDiffScriptWriter}. + * + * <p>This class never closes the output stream. + * + * @param oldChunkListing against which the diff will be generated. + */ + public static BackupFileBuilder createForIncremental( + OutputStream outputStream, ChunksMetadataProto.ChunkListing oldChunkListing) { + return new BackupFileBuilder( + DiffScriptBackupWriter.newInstance(outputStream), oldChunkListing); + } + + private BackupFileBuilder( + BackupWriter backupWriter, ChunksMetadataProto.ChunkListing oldChunkListing) { + this.mBackupWriter = backupWriter; + // TODO(b/77188289): Use InlineLengthsEncryptedChunkEncoder for key-value backups + this.mEncryptedChunkEncoder = new LengthlessEncryptedChunkEncoder(); + this.mOldChunkListing = ChunkListingMap.fromProto(oldChunkListing); + + mNewChunkListing = new ChunksMetadataProto.ChunkListing(); + mNewChunkListing.cipherType = ChunksMetadataProto.AES_256_GCM; + mNewChunkListing.chunkOrderingType = ChunksMetadataProto.CHUNK_ORDERING_TYPE_UNSPECIFIED; + + mChunkOrdering = new ChunksMetadataProto.ChunkOrdering(); + mChunkStartPositions = new HashMap<>(); + } + + /** + * Writes the given chunks to the output stream, and adds them to the new chunk listing and + * chunk ordering. + * + * <p>Sorts the chunks in lexicographical order before writing. + * + * @param allChunks The hashes of all the chunks, in the order they appear in the plaintext. + * @param newChunks A map from hash to {@link EncryptedChunk} containing the new chunks not + * present in the previous backup. + */ + public void writeChunks(List<ChunkHash> allChunks, Map<ChunkHash, EncryptedChunk> newChunks) + throws IOException { + checkState(!mFinished, "Cannot write chunks after flushing."); + + List<ChunkHash> sortedChunks = new ArrayList<>(allChunks); + Collections.sort(sortedChunks); + for (ChunkHash chunkHash : sortedChunks) { + // As we have already included this chunk in the backup file, don't add it again to + // deduplicate identical chunks. + if (!mChunkStartPositions.containsKey(chunkHash)) { + // getBytesWritten() gives us the start of the chunk. + mChunkStartPositions.put(chunkHash, mBackupWriter.getBytesWritten()); + + writeChunkToFileAndListing(chunkHash, newChunks); + } + } + + long totalSizeKb = mBackupWriter.getBytesWritten() / BYTES_PER_KILOBYTE; + long newChunksSizeKb = mNewChunksSizeBytes / BYTES_PER_KILOBYTE; + Slog.d( + TAG, + "Total backup size: " + + totalSizeKb + + " kb, new chunks size: " + + newChunksSizeKb + + " kb"); + + for (ChunkHash chunkHash : allChunks) { + mKnownStarts.add(mChunkStartPositions.get(chunkHash).intValue()); + } + } + + /** + * Returns a new listing for all of the chunks written so far, setting the given fingerprint + * mixer salt (this overrides the {@link ChunksMetadataProto.ChunkListing#fingerprintMixerSalt} + * in the old {@link ChunksMetadataProto.ChunkListing} passed into the + * {@link #BackupFileBuilder). + */ + public ChunksMetadataProto.ChunkListing getNewChunkListing( + @Nullable byte[] fingerprintMixerSalt) { + // TODO: b/141537803 Add check to ensure this is called only once per instance + mNewChunkListing.fingerprintMixerSalt = + fingerprintMixerSalt != null + ? Arrays.copyOf(fingerprintMixerSalt, fingerprintMixerSalt.length) + : new byte[0]; + mNewChunkListing.chunks = mKnownChunks.toArray(new ChunksMetadataProto.Chunk[0]); + return mNewChunkListing; + } + + /** Returns a new ordering for all of the chunks written so far, setting the given checksum. */ + public ChunksMetadataProto.ChunkOrdering getNewChunkOrdering(byte[] checksum) { + // TODO: b/141537803 Add check to ensure this is called only once per instance + mChunkOrdering.starts = new int[mKnownStarts.size()]; + for (int i = 0; i < mKnownStarts.size(); i++) { + mChunkOrdering.starts[i] = mKnownStarts.get(i).intValue(); + } + mChunkOrdering.checksum = Arrays.copyOf(checksum, checksum.length); + return mChunkOrdering; + } + + /** + * Finishes the backup file by writing the chunk metadata and metadata position. + * + * <p>Once this is called, calling {@link #writeChunks(List, Map)} will throw {@link + * IllegalStateException}. + */ + public void finish(ChunksMetadataProto.ChunksMetadata metadata) throws IOException { + checkNotNull(metadata, "Metadata cannot be null"); + + long startOfMetadata = mBackupWriter.getBytesWritten(); + mBackupWriter.writeBytes(ChunksMetadataProto.ChunksMetadata.toByteArray(metadata)); + mBackupWriter.writeBytes(toByteArray(startOfMetadata)); + + mBackupWriter.flush(); + mFinished = true; + } + + /** + * Checks if the given chunk hash references an existing chunk or a new chunk, and adds this + * chunk to the backup file and new chunk listing. + */ + private void writeChunkToFileAndListing( + ChunkHash chunkHash, Map<ChunkHash, EncryptedChunk> newChunks) throws IOException { + checkNotNull(chunkHash, "Hash cannot be null"); + + if (mOldChunkListing.hasChunk(chunkHash)) { + ChunkListingMap.Entry oldChunk = mOldChunkListing.getChunkEntry(chunkHash); + mBackupWriter.writeChunk(oldChunk.getStart(), oldChunk.getLength()); + + checkArgument(oldChunk.getLength() >= 0, "Chunk must have zero or positive length"); + addChunk(chunkHash.getHash(), oldChunk.getLength()); + } else if (newChunks.containsKey(chunkHash)) { + EncryptedChunk newChunk = newChunks.get(chunkHash); + mEncryptedChunkEncoder.writeChunkToWriter(mBackupWriter, newChunk); + int length = mEncryptedChunkEncoder.getEncodedLengthOfChunk(newChunk); + mNewChunksSizeBytes += length; + + checkArgument(length >= 0, "Chunk must have zero or positive length"); + addChunk(chunkHash.getHash(), length); + } else { + throw new IllegalArgumentException( + "Chunk did not exist in old chunks or new chunks: " + chunkHash); + } + } + + private void addChunk(byte[] chunkHash, int length) { + ChunksMetadataProto.Chunk chunk = new ChunksMetadataProto.Chunk(); + chunk.hash = Arrays.copyOf(chunkHash, chunkHash.length); + chunk.length = length; + mKnownChunks.add(chunk); + } + + private static byte[] toByteArray(long value) { + // Note that this code needs to stay compatible with GWT, which has known + // bugs when narrowing byte casts of long values occur. + byte[] result = new byte[8]; + for (int i = 7; i >= 0; i--) { + result[i] = (byte) (value & 0xffL); + value >>= 8; + } + return result; + } +} diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/client/CryptoBackupServer.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/client/CryptoBackupServer.java new file mode 100644 index 000000000000..d7f7dc7d0472 --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/client/CryptoBackupServer.java @@ -0,0 +1,67 @@ +/* + * 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.client; + +import com.android.server.backup.encryption.protos.nano.WrappedKeyProto; + +import java.util.Map; + +/** + * Contains methods for communicating with the parts of the backup server relevant to encryption. + */ +public interface CryptoBackupServer { + /** + * Uploads an incremental backup to the server. + * + * <p>Handles setting up and tearing down the connection. + * + * @param packageName the package to associate the data with + * @param oldDocId the id of the previous backup doc in Drive + * @param diffScript containing the actual backup data + * @param tertiaryKey the wrapped key used to encrypt this backup + * @return the id of the new backup doc in Drive. + */ + String uploadIncrementalBackup( + String packageName, + String oldDocId, + byte[] diffScript, + WrappedKeyProto.WrappedKey tertiaryKey); + + /** + * Uploads non-incremental backup to the server. + * + * <p>Handles setting up and tearing down the connection. + * + * @param packageName the package to associate the data with + * @param data the actual backup data + * @param tertiaryKey the wrapped key used to encrypt this backup + * @return the id of the new backup doc in Drive. + */ + String uploadNonIncrementalBackup( + String packageName, byte[] data, WrappedKeyProto.WrappedKey tertiaryKey); + + /** + * Sets the alias of the active secondary key. This is the alias used to refer to the key in the + * {@link java.security.KeyStore}. It is also used to key storage for tertiary keys on the + * backup server. Also has to upload all existing tertiary keys, wrapped with the new key. + * + * @param keyAlias The ID of the secondary key. + * @param tertiaryKeys The tertiary keys, wrapped with the new secondary key. + */ + void setActiveSecondaryKeyAlias( + String keyAlias, Map<String, WrappedKeyProto.WrappedKey> tertiaryKeys); +} diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/EncryptedBackupTask.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/EncryptedBackupTask.java new file mode 100644 index 000000000000..ef13f23e799d --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/EncryptedBackupTask.java @@ -0,0 +1,243 @@ +/* + * 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.annotation.Nullable; +import android.annotation.TargetApi; +import android.os.Build.VERSION_CODES; +import android.util.Slog; + +import com.android.server.backup.encryption.chunk.ChunkHash; +import com.android.server.backup.encryption.chunking.BackupFileBuilder; +import com.android.server.backup.encryption.chunking.EncryptedChunk; +import com.android.server.backup.encryption.client.CryptoBackupServer; +import com.android.server.backup.encryption.protos.nano.ChunksMetadataProto; +import com.android.server.backup.encryption.protos.nano.WrappedKeyProto; + +import java.io.ByteArrayOutputStream; +import java.io.IOException; +import java.security.GeneralSecurityException; +import java.security.InvalidAlgorithmParameterException; +import java.security.InvalidKeyException; +import java.security.NoSuchAlgorithmException; +import java.security.SecureRandom; +import java.util.Arrays; +import java.util.HashMap; +import java.util.HashSet; +import java.util.List; +import java.util.Map; +import java.util.Set; +import java.util.concurrent.CancellationException; +import java.util.concurrent.atomic.AtomicBoolean; + +import javax.crypto.BadPaddingException; +import javax.crypto.Cipher; +import javax.crypto.IllegalBlockSizeException; +import javax.crypto.NoSuchPaddingException; +import javax.crypto.SecretKey; +import javax.crypto.ShortBufferException; +import javax.crypto.spec.GCMParameterSpec; + +/** + * Task which reads encrypted chunks from a {@link BackupEncrypter}, builds a backup file and + * uploads it to the server. + */ +@TargetApi(VERSION_CODES.P) +public class EncryptedBackupTask { + 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 static final int BITS_PER_BYTE = 8; + + private static final String TAG = "EncryptedBackupTask"; + + private final CryptoBackupServer mCryptoBackupServer; + private final SecureRandom mSecureRandom; + private final String mPackageName; + private final ByteArrayOutputStream mBackupDataOutput; + private final BackupEncrypter mBackupEncrypter; + private final AtomicBoolean mCancelled; + + /** Creates a new instance which reads data from the given input stream. */ + public EncryptedBackupTask( + CryptoBackupServer cryptoBackupServer, + SecureRandom secureRandom, + String packageName, + BackupEncrypter backupEncrypter) { + mCryptoBackupServer = cryptoBackupServer; + mSecureRandom = secureRandom; + mPackageName = packageName; + mBackupEncrypter = backupEncrypter; + + mBackupDataOutput = new ByteArrayOutputStream(); + mCancelled = new AtomicBoolean(false); + } + + /** + * Creates a non-incremental backup file and uploads it to the server. + * + * @param fingerprintMixerSalt Fingerprint mixer salt used for content-defined chunking during a + * full backup. May be {@code null} for a key-value backup. + */ + public ChunksMetadataProto.ChunkListing performNonIncrementalBackup( + SecretKey tertiaryKey, + WrappedKeyProto.WrappedKey wrappedTertiaryKey, + @Nullable byte[] fingerprintMixerSalt) + throws IOException, GeneralSecurityException { + + ChunksMetadataProto.ChunkListing newChunkListing = + performBackup( + tertiaryKey, + fingerprintMixerSalt, + BackupFileBuilder.createForNonIncremental(mBackupDataOutput), + new HashSet<>()); + + throwIfCancelled(); + + newChunkListing.documentId = + mCryptoBackupServer.uploadNonIncrementalBackup( + mPackageName, mBackupDataOutput.toByteArray(), wrappedTertiaryKey); + + return newChunkListing; + } + + /** Creates an incremental backup file and uploads it to the server. */ + public ChunksMetadataProto.ChunkListing performIncrementalBackup( + SecretKey tertiaryKey, + WrappedKeyProto.WrappedKey wrappedTertiaryKey, + ChunksMetadataProto.ChunkListing oldChunkListing) + throws IOException, GeneralSecurityException { + + ChunksMetadataProto.ChunkListing newChunkListing = + performBackup( + tertiaryKey, + oldChunkListing.fingerprintMixerSalt, + BackupFileBuilder.createForIncremental(mBackupDataOutput, oldChunkListing), + getChunkHashes(oldChunkListing)); + + throwIfCancelled(); + + String oldDocumentId = oldChunkListing.documentId; + Slog.v(TAG, "Old doc id: " + oldDocumentId); + + newChunkListing.documentId = + mCryptoBackupServer.uploadIncrementalBackup( + mPackageName, + oldDocumentId, + mBackupDataOutput.toByteArray(), + wrappedTertiaryKey); + return newChunkListing; + } + + /** + * Signals to the task that the backup has been cancelled. If the upload has not yet started + * then the task will not upload any data to the server or save the new chunk listing. + */ + public void cancel() { + mCancelled.getAndSet(true); + } + + private void throwIfCancelled() { + if (mCancelled.get()) { + throw new CancellationException("EncryptedBackupTask was cancelled"); + } + } + + private ChunksMetadataProto.ChunkListing performBackup( + SecretKey tertiaryKey, + @Nullable byte[] fingerprintMixerSalt, + BackupFileBuilder backupFileBuilder, + Set<ChunkHash> existingChunkHashes) + throws IOException, GeneralSecurityException { + BackupEncrypter.Result result = + mBackupEncrypter.backup(tertiaryKey, fingerprintMixerSalt, existingChunkHashes); + backupFileBuilder.writeChunks(result.getAllChunks(), buildChunkMap(result.getNewChunks())); + + ChunksMetadataProto.ChunkOrdering chunkOrdering = + backupFileBuilder.getNewChunkOrdering(result.getDigest()); + backupFileBuilder.finish(buildMetadata(tertiaryKey, chunkOrdering)); + + return backupFileBuilder.getNewChunkListing(fingerprintMixerSalt); + } + + /** Returns a set containing the hashes of every chunk in the given listing. */ + private static Set<ChunkHash> getChunkHashes(ChunksMetadataProto.ChunkListing chunkListing) { + Set<ChunkHash> hashes = new HashSet<>(); + for (ChunksMetadataProto.Chunk chunk : chunkListing.chunks) { + hashes.add(new ChunkHash(chunk.hash)); + } + return hashes; + } + + /** Returns a map from chunk hash to chunk containing every chunk in the given list. */ + private static Map<ChunkHash, EncryptedChunk> buildChunkMap(List<EncryptedChunk> chunks) { + Map<ChunkHash, EncryptedChunk> chunkMap = new HashMap<>(); + for (EncryptedChunk chunk : chunks) { + chunkMap.put(chunk.key(), chunk); + } + return chunkMap; + } + + private ChunksMetadataProto.ChunksMetadata buildMetadata( + SecretKey tertiaryKey, ChunksMetadataProto.ChunkOrdering chunkOrdering) + throws InvalidKeyException, IllegalBlockSizeException, BadPaddingException, + InvalidAlgorithmParameterException, NoSuchAlgorithmException, + ShortBufferException, NoSuchPaddingException { + ChunksMetadataProto.ChunksMetadata metaData = new ChunksMetadataProto.ChunksMetadata(); + metaData.cipherType = ChunksMetadataProto.AES_256_GCM; + metaData.checksumType = ChunksMetadataProto.SHA_256; + metaData.chunkOrdering = encryptChunkOrdering(tertiaryKey, chunkOrdering); + return metaData; + } + + private byte[] encryptChunkOrdering( + SecretKey tertiaryKey, ChunksMetadataProto.ChunkOrdering chunkOrdering) + throws InvalidKeyException, IllegalBlockSizeException, BadPaddingException, + NoSuchPaddingException, NoSuchAlgorithmException, + InvalidAlgorithmParameterException, ShortBufferException { + Cipher cipher = Cipher.getInstance(CIPHER_ALGORITHM); + + byte[] nonce = generateNonce(); + + cipher.init( + Cipher.ENCRYPT_MODE, + tertiaryKey, + new GCMParameterSpec(GCM_TAG_LENGTH_BYTES * BITS_PER_BYTE, nonce)); + + byte[] orderingBytes = ChunksMetadataProto.ChunkOrdering.toByteArray(chunkOrdering); + // We prepend the nonce to the ordering. + byte[] output = + Arrays.copyOf( + nonce, + GCM_NONCE_LENGTH_BYTES + orderingBytes.length + GCM_TAG_LENGTH_BYTES); + + cipher.doFinal( + orderingBytes, + /*inputOffset=*/ 0, + /*inputLen=*/ orderingBytes.length, + output, + /*outputOffset=*/ GCM_NONCE_LENGTH_BYTES); + + return output; + } + + 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/tasks/KvBackupEncrypter.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/KvBackupEncrypter.java new file mode 100644 index 000000000000..d20cd4c07f88 --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/KvBackupEncrypter.java @@ -0,0 +1,179 @@ +/* + * 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 com.android.internal.util.Preconditions.checkState; + +import android.annotation.Nullable; +import android.app.backup.BackupDataInput; + +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.kv.KeyValueListingBuilder; +import com.android.server.backup.encryption.protos.nano.KeyValueListingProto; +import com.android.server.backup.encryption.protos.nano.KeyValuePairProto; + +import java.io.IOException; +import java.security.GeneralSecurityException; +import java.security.InvalidKeyException; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.security.SecureRandom; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.HashMap; +import java.util.List; +import java.util.Map; +import java.util.Optional; +import java.util.Set; + +import javax.crypto.IllegalBlockSizeException; +import javax.crypto.SecretKey; + +/** + * Reads key value backup data from an input, converts each pair into a chunk and encrypts the + * chunks. + * + * <p>The caller should pass in the key value listing from the previous backup, if there is one. + * This class emits chunks for both existing and new pairs, using the provided listing to + * determine the hashes of pairs that already exist. During the backup it computes the new listing, + * which the caller should store on disk and pass in at the start of the next backup. + * + * <p>Also computes the message digest, which is {@code SHA-256(chunk hashes sorted + * lexicographically)}. + */ +public class KvBackupEncrypter implements BackupEncrypter { + private final BackupDataInput mBackupDataInput; + + private KeyValueListingProto.KeyValueListing mOldKeyValueListing; + @Nullable private KeyValueListingBuilder mNewKeyValueListing; + + /** + * Constructs a new instance which reads data from the given input. + * + * <p>By default this performs non-incremental backup, call {@link #setOldKeyValueListing} to + * perform incremental backup. + */ + public KvBackupEncrypter(BackupDataInput backupDataInput) { + mBackupDataInput = backupDataInput; + mOldKeyValueListing = KeyValueListingBuilder.emptyListing(); + } + + /** Sets the old listing to perform incremental backup against. */ + public void setOldKeyValueListing(KeyValueListingProto.KeyValueListing oldKeyValueListing) { + mOldKeyValueListing = oldKeyValueListing; + } + + @Override + public Result backup( + SecretKey secretKey, + @Nullable byte[] unusedFingerprintMixerSalt, + Set<ChunkHash> unusedExistingChunks) + throws IOException, GeneralSecurityException { + ChunkHasher chunkHasher = new ChunkHasher(secretKey); + ChunkEncryptor chunkEncryptor = new ChunkEncryptor(secretKey, new SecureRandom()); + mNewKeyValueListing = new KeyValueListingBuilder(); + List<ChunkHash> allChunks = new ArrayList<>(); + List<EncryptedChunk> newChunks = new ArrayList<>(); + + Map<String, ChunkHash> existingChunksToReuse = buildPairMap(mOldKeyValueListing); + + while (mBackupDataInput.readNextHeader()) { + String key = mBackupDataInput.getKey(); + Optional<byte[]> value = readEntireValue(mBackupDataInput); + + // As this pair exists in the new backup, we don't need to add it from the previous + // backup. + existingChunksToReuse.remove(key); + + // If the value is not present then this key has been deleted. + if (value.isPresent()) { + EncryptedChunk newChunk = + createEncryptedChunk(chunkHasher, chunkEncryptor, key, value.get()); + allChunks.add(newChunk.key()); + newChunks.add(newChunk); + mNewKeyValueListing.addPair(key, newChunk.key()); + } + } + + allChunks.addAll(existingChunksToReuse.values()); + + mNewKeyValueListing.addAll(existingChunksToReuse); + + return new Result(allChunks, newChunks, createMessageDigest(allChunks)); + } + + /** + * Returns a listing containing the pairs in the new backup. + * + * <p>You must call {@link #backup} first. + */ + public KeyValueListingProto.KeyValueListing getNewKeyValueListing() { + checkState(mNewKeyValueListing != null, "Must call backup() first"); + return mNewKeyValueListing.build(); + } + + private static Map<String, ChunkHash> buildPairMap( + KeyValueListingProto.KeyValueListing listing) { + Map<String, ChunkHash> map = new HashMap<>(); + for (KeyValueListingProto.KeyValueEntry entry : listing.entries) { + map.put(entry.key, new ChunkHash(entry.hash)); + } + return map; + } + + private EncryptedChunk createEncryptedChunk( + ChunkHasher chunkHasher, ChunkEncryptor chunkEncryptor, String key, byte[] value) + throws InvalidKeyException, IllegalBlockSizeException { + KeyValuePairProto.KeyValuePair pair = new KeyValuePairProto.KeyValuePair(); + pair.key = key; + pair.value = Arrays.copyOf(value, value.length); + + byte[] plaintext = KeyValuePairProto.KeyValuePair.toByteArray(pair); + return chunkEncryptor.encrypt(chunkHasher.computeHash(plaintext), plaintext); + } + + private static byte[] createMessageDigest(List<ChunkHash> allChunks) + throws NoSuchAlgorithmException { + MessageDigest messageDigest = + MessageDigest.getInstance(BackupEncrypter.MESSAGE_DIGEST_ALGORITHM); + // TODO:b/141531271 Extract sorted chunks code to utility class + List<ChunkHash> sortedChunks = new ArrayList<>(allChunks); + Collections.sort(sortedChunks); + for (ChunkHash hash : sortedChunks) { + messageDigest.update(hash.getHash()); + } + return messageDigest.digest(); + } + + private static Optional<byte[]> readEntireValue(BackupDataInput input) throws IOException { + // A negative data size indicates that this key should be deleted. + if (input.getDataSize() < 0) { + return Optional.empty(); + } + + byte[] value = new byte[input.getDataSize()]; + int bytesRead = 0; + while (bytesRead < value.length) { + bytesRead += input.readEntityData(value, bytesRead, value.length - bytesRead); + } + return Optional.of(value); + } +} |