diff options
7 files changed, 538 insertions, 3 deletions
diff --git a/packages/BackupEncryption/proto/key_value_listing.proto b/packages/BackupEncryption/proto/key_value_listing.proto new file mode 100644 index 000000000000..001e697bd804 --- /dev/null +++ b/packages/BackupEncryption/proto/key_value_listing.proto @@ -0,0 +1,40 @@ +/* + * 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 + */ + +syntax = "proto2"; + +package android_backup_crypto; + +option java_package = "com.android.server.backup.encryption.protos"; +option java_outer_classname = "KeyValueListingProto"; + +// An entry of a key-value pair. +message KeyValueEntry { + // Plaintext key of the key-value pair. + optional string key = 1; + // SHA-256 MAC of the plaintext of the chunk containing the pair + optional bytes hash = 2; +} + +// Describes the key/value pairs currently in the backup blob, mapping from the +// plaintext key to the hash of the chunk containing the pair. +// +// This is local state stored on the device. It is never sent to the +// backup server. See ChunkOrdering for how the device restores the +// key-value pairs in the correct order. +message KeyValueListing { + repeated KeyValueEntry entries = 1; +} diff --git a/packages/BackupEncryption/proto/key_value_pair.proto b/packages/BackupEncryption/proto/key_value_pair.proto new file mode 100644 index 000000000000..177fa3025dc8 --- /dev/null +++ b/packages/BackupEncryption/proto/key_value_pair.proto @@ -0,0 +1,31 @@ +/* + * 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 + */ + +syntax = "proto2"; + +package android_backup_crypto; + +option java_package = "com.android.server.backup.encryption.protos"; +option java_outer_classname = "KeyValuePairProto"; + +// Serialized form of a key-value pair, when it is to be encrypted in a blob. +// The backup blob for a key-value database consists of repeated encrypted +// key-value pairs like this, in a randomized order. See ChunkOrdering for how +// these are then reconstructed during a restore. +message KeyValuePair { + optional string key = 1; + optional bytes value = 2; +} diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/kv/DecryptedChunkKvOutput.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/kv/DecryptedChunkKvOutput.java new file mode 100644 index 000000000000..56e1c053d8e3 --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/kv/DecryptedChunkKvOutput.java @@ -0,0 +1,111 @@ +/* + * 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.kv; + +import static com.android.internal.util.Preconditions.checkState; + +import com.android.internal.annotations.VisibleForTesting; +import com.android.server.backup.encryption.chunk.ChunkHash; +import com.android.server.backup.encryption.chunking.ChunkHasher; +import com.android.server.backup.encryption.protos.nano.KeyValuePairProto; +import com.android.server.backup.encryption.tasks.DecryptedChunkOutput; + +import java.io.IOException; +import java.security.InvalidKeyException; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; + +/** + * Builds a key value backup set from plaintext chunks. Computes a digest over the sorted SHA-256 + * hashes of the chunks. + */ +public class DecryptedChunkKvOutput implements DecryptedChunkOutput { + @VisibleForTesting static final String DIGEST_ALGORITHM = "SHA-256"; + + private final ChunkHasher mChunkHasher; + private final List<KeyValuePairProto.KeyValuePair> mUnsortedPairs = new ArrayList<>(); + private final List<ChunkHash> mUnsortedHashes = new ArrayList<>(); + private boolean mClosed; + + /** Constructs a new instance which computers the digest using the given hasher. */ + public DecryptedChunkKvOutput(ChunkHasher chunkHasher) { + mChunkHasher = chunkHasher; + } + + @Override + public DecryptedChunkOutput open() { + // As we don't have any resources there is nothing to open. + return this; + } + + @Override + public void processChunk(byte[] plaintextBuffer, int length) + throws IOException, InvalidKeyException { + checkState(!mClosed, "Cannot process chunk after close()"); + KeyValuePairProto.KeyValuePair kvPair = new KeyValuePairProto.KeyValuePair(); + KeyValuePairProto.KeyValuePair.mergeFrom(kvPair, plaintextBuffer, 0, length); + mUnsortedPairs.add(kvPair); + // TODO(b/71492289): Update ChunkHasher to accept offset and length so we don't have to copy + // the buffer into a smaller array. + mUnsortedHashes.add(mChunkHasher.computeHash(Arrays.copyOf(plaintextBuffer, length))); + } + + @Override + public void close() { + // As we don't have any resources there is nothing to close. + mClosed = true; + } + + @Override + public byte[] getDigest() throws NoSuchAlgorithmException { + checkState(mClosed, "Must close() before getDigest()"); + MessageDigest digest = getMessageDigest(); + Collections.sort(mUnsortedHashes); + for (ChunkHash hash : mUnsortedHashes) { + digest.update(hash.getHash()); + } + return digest.digest(); + } + + private static MessageDigest getMessageDigest() throws NoSuchAlgorithmException { + return MessageDigest.getInstance(DIGEST_ALGORITHM); + } + + /** + * Returns the key value pairs from the backup, sorted lexicographically by key. + * + * <p>You must call {@link #close} first. + */ + public List<KeyValuePairProto.KeyValuePair> getPairs() { + checkState(mClosed, "Must close() before getPairs()"); + Collections.sort( + mUnsortedPairs, + new Comparator<KeyValuePairProto.KeyValuePair>() { + @Override + public int compare( + KeyValuePairProto.KeyValuePair o1, KeyValuePairProto.KeyValuePair o2) { + return o1.key.compareTo(o2.key); + } + }); + return mUnsortedPairs; + } +} diff --git a/packages/BackupEncryption/src/com/android/server/backup/encryption/kv/KeyValueListingBuilder.java b/packages/BackupEncryption/src/com/android/server/backup/encryption/kv/KeyValueListingBuilder.java new file mode 100644 index 000000000000..b3518e144ce3 --- /dev/null +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/kv/KeyValueListingBuilder.java @@ -0,0 +1,77 @@ +/* + * 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.kv; + +import static com.android.internal.util.Preconditions.checkArgument; +import static com.android.internal.util.Preconditions.checkNotNull; + +import com.android.server.backup.encryption.chunk.ChunkHash; +import com.android.server.backup.encryption.protos.nano.KeyValueListingProto; + +import java.util.ArrayList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; + +/** + * Builds a {@link KeyValueListingProto.KeyValueListing}, which is a nano proto and so has no + * builder. + */ +public class KeyValueListingBuilder { + private final List<KeyValueListingProto.KeyValueEntry> mEntries = new ArrayList<>(); + + /** Adds a new pair entry to the listing. */ + public KeyValueListingBuilder addPair(String key, ChunkHash hash) { + checkArgument(key.length() != 0, "Key must have non-zero length"); + checkNotNull(hash, "Hash must not be null"); + + KeyValueListingProto.KeyValueEntry entry = new KeyValueListingProto.KeyValueEntry(); + entry.key = key; + entry.hash = hash.getHash(); + mEntries.add(entry); + + return this; + } + + /** Adds all pairs contained in a map, where the map is from key to hash. */ + public KeyValueListingBuilder addAll(Map<String, ChunkHash> map) { + for (Entry<String, ChunkHash> entry : map.entrySet()) { + addPair(entry.getKey(), entry.getValue()); + } + + return this; + } + + /** Returns a new listing containing all the pairs added so far. */ + public KeyValueListingProto.KeyValueListing build() { + if (mEntries.size() == 0) { + return emptyListing(); + } + + KeyValueListingProto.KeyValueListing listing = new KeyValueListingProto.KeyValueListing(); + listing.entries = new KeyValueListingProto.KeyValueEntry[mEntries.size()]; + mEntries.toArray(listing.entries); + return listing; + } + + /** Returns a new listing which does not contain any pairs. */ + public static KeyValueListingProto.KeyValueListing emptyListing() { + KeyValueListingProto.KeyValueListing listing = new KeyValueListingProto.KeyValueListing(); + listing.entries = KeyValueListingProto.KeyValueEntry.emptyArray(); + return listing; + } +} 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 index e3df3c1eb96f..f67f1007f632 100644 --- a/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/DecryptedChunkOutput.java +++ b/packages/BackupEncryption/src/com/android/server/backup/encryption/tasks/DecryptedChunkOutput.java @@ -19,6 +19,7 @@ package com.android.server.backup.encryption.tasks; import java.io.Closeable; import java.io.IOException; import java.security.InvalidKeyException; +import java.security.NoSuchAlgorithmException; /** * Accepts the plaintext bytes of decrypted chunks and writes them to some output. Also keeps track @@ -30,7 +31,7 @@ public interface DecryptedChunkOutput extends Closeable { * * @return {@code this}, to allow use with try-with-resources */ - DecryptedChunkOutput open() throws IOException; + DecryptedChunkOutput open() throws IOException, NoSuchAlgorithmException; /** * Writes the plaintext bytes of chunk to whatever output the implementation chooses. Also @@ -43,12 +44,13 @@ public interface DecryptedChunkOutput extends Closeable { * 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; + void processChunk(byte[] plaintextBuffer, int length) + throws IOException, InvalidKeyException, NoSuchAlgorithmException; /** * 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(); + byte[] getDigest() throws NoSuchAlgorithmException; } diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/kv/DecryptedChunkKvOutputTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/kv/DecryptedChunkKvOutputTest.java new file mode 100644 index 000000000000..215e1cbc725e --- /dev/null +++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/kv/DecryptedChunkKvOutputTest.java @@ -0,0 +1,164 @@ +/* + * 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.kv; + +import static com.google.common.truth.Truth.assertThat; + +import static org.mockito.ArgumentMatchers.any; +import static org.mockito.Mockito.when; +import static org.testng.Assert.assertThrows; + +import android.os.Debug; +import android.platform.test.annotations.Presubmit; + +import com.android.server.backup.encryption.chunk.ChunkHash; +import com.android.server.backup.encryption.chunking.ChunkHasher; +import com.android.server.backup.encryption.protos.nano.KeyValuePairProto; + +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.mockito.Mock; +import org.mockito.MockitoAnnotations; +import org.robolectric.RobolectricTestRunner; + +import java.security.MessageDigest; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.Comparator; +import java.util.List; +import java.util.stream.Stream; + +@RunWith(RobolectricTestRunner.class) +@Presubmit +public class DecryptedChunkKvOutputTest { + private static final String TEST_KEY_1 = "key_1"; + private static final String TEST_KEY_2 = "key_2"; + private static final byte[] TEST_VALUE_1 = {1, 2, 3}; + private static final byte[] TEST_VALUE_2 = {10, 11, 12, 13}; + private static final byte[] TEST_PAIR_1 = toByteArray(createPair(TEST_KEY_1, TEST_VALUE_1)); + private static final byte[] TEST_PAIR_2 = toByteArray(createPair(TEST_KEY_2, TEST_VALUE_2)); + private static final int TEST_BUFFER_SIZE = Math.max(TEST_PAIR_1.length, TEST_PAIR_2.length); + + @Mock private ChunkHasher mChunkHasher; + private DecryptedChunkKvOutput mOutput; + + @Before + public void setUp() throws Exception { + MockitoAnnotations.initMocks(this); + + when(mChunkHasher.computeHash(any())) + .thenAnswer(invocation -> fakeHash(invocation.getArgument(0))); + mOutput = new DecryptedChunkKvOutput(mChunkHasher); + } + + @Test + public void open_returnsInstance() throws Exception { + assertThat(mOutput.open()).isEqualTo(mOutput); + } + + @Test + public void processChunk_alreadyClosed_throws() throws Exception { + mOutput.open(); + mOutput.close(); + + assertThrows( + IllegalStateException.class, + () -> mOutput.processChunk(TEST_PAIR_1, TEST_PAIR_1.length)); + } + + @Test + public void getDigest_beforeClose_throws() throws Exception { + // TODO: b/141356823 We should add a test which calls .open() here + assertThrows(IllegalStateException.class, () -> mOutput.getDigest()); + } + + @Test + public void getDigest_returnsDigestOfSortedHashes() throws Exception { + mOutput.open(); + Debug.waitForDebugger(); + mOutput.processChunk(Arrays.copyOf(TEST_PAIR_1, TEST_BUFFER_SIZE), TEST_PAIR_1.length); + mOutput.processChunk(Arrays.copyOf(TEST_PAIR_2, TEST_BUFFER_SIZE), TEST_PAIR_2.length); + mOutput.close(); + + byte[] actualDigest = mOutput.getDigest(); + + MessageDigest digest = MessageDigest.getInstance(DecryptedChunkKvOutput.DIGEST_ALGORITHM); + Stream.of(TEST_PAIR_1, TEST_PAIR_2) + .map(DecryptedChunkKvOutputTest::fakeHash) + .sorted(Comparator.naturalOrder()) + .forEachOrdered(hash -> digest.update(hash.getHash())); + assertThat(actualDigest).isEqualTo(digest.digest()); + } + + @Test + public void getPairs_beforeClose_throws() throws Exception { + // TODO: b/141356823 We should add a test which calls .open() here + assertThrows(IllegalStateException.class, () -> mOutput.getPairs()); + } + + @Test + public void getPairs_returnsPairsSortedByKey() throws Exception { + mOutput.open(); + // Write out of order to check that it sorts the chunks. + mOutput.processChunk(Arrays.copyOf(TEST_PAIR_2, TEST_BUFFER_SIZE), TEST_PAIR_2.length); + mOutput.processChunk(Arrays.copyOf(TEST_PAIR_1, TEST_BUFFER_SIZE), TEST_PAIR_1.length); + mOutput.close(); + + List<KeyValuePairProto.KeyValuePair> pairs = mOutput.getPairs(); + + assertThat( + isInOrder( + pairs, + Comparator.comparing( + (KeyValuePairProto.KeyValuePair pair) -> pair.key))) + .isTrue(); + assertThat(pairs).hasSize(2); + assertThat(pairs.get(0).key).isEqualTo(TEST_KEY_1); + assertThat(pairs.get(0).value).isEqualTo(TEST_VALUE_1); + assertThat(pairs.get(1).key).isEqualTo(TEST_KEY_2); + assertThat(pairs.get(1).value).isEqualTo(TEST_VALUE_2); + } + + private static KeyValuePairProto.KeyValuePair createPair(String key, byte[] value) { + KeyValuePairProto.KeyValuePair pair = new KeyValuePairProto.KeyValuePair(); + pair.key = key; + pair.value = value; + return pair; + } + + private boolean isInOrder( + List<KeyValuePairProto.KeyValuePair> list, + Comparator<KeyValuePairProto.KeyValuePair> comparator) { + if (list.size() < 2) { + return true; + } + + List<KeyValuePairProto.KeyValuePair> sortedList = new ArrayList<>(list); + Collections.sort(sortedList, comparator); + return list.equals(sortedList); + } + + private static byte[] toByteArray(KeyValuePairProto.KeyValuePair nano) { + return KeyValuePairProto.KeyValuePair.toByteArray(nano); + } + + private static ChunkHash fakeHash(byte[] data) { + return new ChunkHash(Arrays.copyOf(data, ChunkHash.HASH_LENGTH_BYTES)); + } +} diff --git a/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/kv/KeyValueListingBuilderTest.java b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/kv/KeyValueListingBuilderTest.java new file mode 100644 index 000000000000..acc662860528 --- /dev/null +++ b/packages/BackupEncryption/test/robolectric/src/com/android/server/backup/encryption/kv/KeyValueListingBuilderTest.java @@ -0,0 +1,110 @@ +/* + * 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.kv; + +import static com.google.common.truth.Truth.assertThat; + +import static org.testng.Assert.assertThrows; + +import android.platform.test.annotations.Presubmit; + +import com.android.server.backup.encryption.chunk.ChunkHash; +import com.android.server.backup.encryption.protos.nano.KeyValueListingProto; + +import com.google.common.collect.ImmutableMap; + +import org.junit.Before; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.robolectric.RobolectricTestRunner; + +import java.util.Arrays; + +@RunWith(RobolectricTestRunner.class) +@Presubmit +public class KeyValueListingBuilderTest { + private static final String TEST_KEY_1 = "test_key_1"; + private static final String TEST_KEY_2 = "test_key_2"; + private static final ChunkHash TEST_HASH_1 = + new ChunkHash(Arrays.copyOf(new byte[] {1, 2}, ChunkHash.HASH_LENGTH_BYTES)); + private static final ChunkHash TEST_HASH_2 = + new ChunkHash(Arrays.copyOf(new byte[] {5, 6}, ChunkHash.HASH_LENGTH_BYTES)); + + private KeyValueListingBuilder mBuilder; + + @Before + public void setUp() { + mBuilder = new KeyValueListingBuilder(); + } + + @Test + public void addPair_nullKey_throws() { + assertThrows(NullPointerException.class, () -> mBuilder.addPair(null, TEST_HASH_1)); + } + + @Test + public void addPair_emptyKey_throws() { + assertThrows(IllegalArgumentException.class, () -> mBuilder.addPair("", TEST_HASH_1)); + } + + @Test + public void addPair_nullHash_throws() { + assertThrows(NullPointerException.class, () -> mBuilder.addPair(TEST_KEY_1, null)); + } + + @Test + public void build_noPairs_buildsEmptyListing() { + KeyValueListingProto.KeyValueListing listing = mBuilder.build(); + + assertThat(listing.entries).isEmpty(); + } + + @Test + public void build_returnsCorrectListing() { + mBuilder.addPair(TEST_KEY_1, TEST_HASH_1); + + KeyValueListingProto.KeyValueListing listing = mBuilder.build(); + + assertThat(listing.entries.length).isEqualTo(1); + assertThat(listing.entries[0].key).isEqualTo(TEST_KEY_1); + assertThat(listing.entries[0].hash).isEqualTo(TEST_HASH_1.getHash()); + } + + @Test + public void addAll_addsAllPairsInMap() { + ImmutableMap<String, ChunkHash> pairs = + new ImmutableMap.Builder<String, ChunkHash>() + .put(TEST_KEY_1, TEST_HASH_1) + .put(TEST_KEY_2, TEST_HASH_2) + .build(); + + mBuilder.addAll(pairs); + KeyValueListingProto.KeyValueListing listing = mBuilder.build(); + + assertThat(listing.entries.length).isEqualTo(2); + assertThat(listing.entries[0].key).isEqualTo(TEST_KEY_1); + assertThat(listing.entries[0].hash).isEqualTo(TEST_HASH_1.getHash()); + assertThat(listing.entries[1].key).isEqualTo(TEST_KEY_2); + assertThat(listing.entries[1].hash).isEqualTo(TEST_HASH_2.getHash()); + } + + @Test + public void emptyListing_returnsListingWithoutAnyPairs() { + KeyValueListingProto.KeyValueListing emptyListing = KeyValueListingBuilder.emptyListing(); + assertThat(emptyListing.entries).isEmpty(); + } +} |