1 /* 2 * Copyright (C) 2018 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.server.backup.encryption.chunking.cdc; 18 19 import static com.android.internal.util.Preconditions.checkArgument; 20 21 import java.nio.ByteBuffer; 22 import java.nio.charset.StandardCharsets; 23 import java.security.InvalidKeyException; 24 25 import javax.crypto.SecretKey; 26 27 /** 28 * Helper for mixing fingerprint with key material. 29 * 30 * <p>We do this as otherwise the Rabin fingerprint leaks information about the plaintext. i.e., if 31 * two users have the same file, it will be partitioned by Rabin in the same way, allowing us to 32 * infer that it is the same as another user's file. 33 * 34 * <p>By mixing the fingerprint with the user's secret key, the chunking method is different on a 35 * per key basis. Each application has its own {@link SecretKey}, so we cannot infer that a file is 36 * the same even across multiple applications owned by the same user, never mind across multiple 37 * users. 38 * 39 * <p>Instead of directly mixing the fingerprint with the user's secret, we first securely and 40 * deterministically derive a secondary chunking key. As Rabin is not a cryptographically secure 41 * hash, it might otherwise leak information about the user's secret. This prevents that from 42 * happening. 43 */ 44 public class FingerprintMixer { 45 public static final int SALT_LENGTH_BYTES = 256 / Byte.SIZE; 46 private static final String DERIVED_KEY_NAME = "RabinFingerprint64Mixer"; 47 48 private final long mAddend; 49 private final long mMultiplicand; 50 51 /** 52 * A new instance from a given secret key and salt. Salt must be the same across incremental 53 * backups, or a different chunking strategy will be used each time, defeating the dedup. 54 * 55 * @param secretKey The application-specific secret. 56 * @param salt The salt. 57 * @throws InvalidKeyException If the encoded form of {@code secretKey} is inaccessible. 58 */ FingerprintMixer(SecretKey secretKey, byte[] salt)59 public FingerprintMixer(SecretKey secretKey, byte[] salt) throws InvalidKeyException { 60 checkArgument(salt.length == SALT_LENGTH_BYTES, "Requires a 256-bit salt."); 61 byte[] keyBytes = secretKey.getEncoded(); 62 if (keyBytes == null) { 63 throw new InvalidKeyException("SecretKey must support encoding for FingerprintMixer."); 64 } 65 byte[] derivedKey = 66 Hkdf.hkdf(keyBytes, salt, DERIVED_KEY_NAME.getBytes(StandardCharsets.UTF_8)); 67 ByteBuffer buffer = ByteBuffer.wrap(derivedKey); 68 mAddend = buffer.getLong(); 69 // Multiplicand must be odd - otherwise we lose some bits of the Rabin fingerprint when 70 // mixing 71 mMultiplicand = buffer.getLong() | 1; 72 } 73 74 /** 75 * Mixes the fingerprint with the derived key material. This is performed by adding part of the 76 * derived key and multiplying by another part of the derived key (which is forced to be odd, so 77 * that the operation is reversible). 78 * 79 * @param fingerprint A 64-bit Rabin fingerprint. 80 * @return The mixed fingerprint. 81 */ mix(long fingerprint)82 long mix(long fingerprint) { 83 return ((fingerprint + mAddend) * mMultiplicand); 84 } 85 86 /** The addend part of the derived key. */ getAddend()87 long getAddend() { 88 return mAddend; 89 } 90 91 /** The multiplicand part of the derived key. */ getMultiplicand()92 long getMultiplicand() { 93 return mMultiplicand; 94 } 95 } 96