diff --git a/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/HmacSha256.java b/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/HmacSha256.java
new file mode 100644
index 0000000..cc7a300
--- /dev/null
+++ b/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/HmacSha256.java
@@ -0,0 +1,111 @@
+/*
+ * Copyright 2021 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.nearby.common.bluetooth.fastpair;
+
+import static com.android.server.nearby.common.bluetooth.fastpair.AesCtrMultipleBlockEncryption.KEY_LENGTH;
+
+import androidx.annotation.VisibleForTesting;
+
+import java.security.GeneralSecurityException;
+
+import javax.crypto.Mac;
+import javax.crypto.spec.SecretKeySpec;
+
+/**
+ * HMAC-SHA256 utility used to generate key-SHA256 based message authentication code. This is
+ * specific for Fast Pair GATT connection exchanging data to verify both the data integrity and the
+ * authentication of a message. It is defined as:
+ *
+ * <ol>
+ *   <li>SHA256(concat((key ^ opad),SHA256(concat((key ^ ipad), data)))), where
+ *   <li>key is the given secret extended to 64 bytes by concat(secret, ZEROS).
+ *   <li>opad is 64 bytes outer padding, consisting of repeated bytes valued 0x5c.
+ *   <li>ipad is 64 bytes inner padding, consisting of repeated bytes valued 0x36.
+ * </ol>
+ *
+ */
+final class HmacSha256 {
+    @VisibleForTesting static final int HMAC_SHA256_BLOCK_SIZE = 64;
+
+    private HmacSha256() {}
+
+    /**
+     * Generates the HMAC for given parameters, this is specific for Fast Pair GATT connection
+     * exchanging data which is encrypted using AES-CTR.
+     *
+     * @param secret 16 bytes shared secret.
+     * @param data the data encrypted using AES-CTR and the given nonce.
+     * @return HMAC-SHA256 result.
+     */
+    static byte[] build(byte[] secret, byte[] data) throws GeneralSecurityException {
+        // Currently we only accept AES-128 key here, the second check is to secure we won't
+        // modify KEY_LENGTH to > HMAC_SHA256_BLOCK_SIZE by mistake.
+        if (secret.length != KEY_LENGTH) {
+            throw new GeneralSecurityException("Incorrect key length, should be the AES-128 key.");
+        }
+        if (KEY_LENGTH > HMAC_SHA256_BLOCK_SIZE) {
+            throw new GeneralSecurityException("KEY_LENGTH > HMAC_SHA256_BLOCK_SIZE!");
+        }
+
+        return buildWith64BytesKey(secret, data);
+    }
+
+    /**
+     * Generates the HMAC for given parameters, this is specific for Fast Pair GATT connection
+     * exchanging data which is encrypted using AES-CTR.
+     *
+     * @param secret 16 bytes shared secret.
+     * @param data the data encrypted using AES-CTR and the given nonce.
+     * @return HMAC-SHA256 result.
+     */
+    static byte[] buildWith64BytesKey(byte[] secret, byte[] data) throws GeneralSecurityException {
+        if (secret.length > HMAC_SHA256_BLOCK_SIZE) {
+            throw new GeneralSecurityException("KEY_LENGTH > HMAC_SHA256_BLOCK_SIZE!");
+        }
+
+        Mac mac = Mac.getInstance("HmacSHA256");
+        SecretKeySpec keySpec = new SecretKeySpec(secret, "HmacSHA256");
+        mac.init(keySpec);
+
+        return mac.doFinal(data);
+    }
+
+    /**
+     * Constant-time HMAC comparison to prevent a possible timing attack, e.g. time the same MAC
+     * with all different first byte for a given ciphertext, the right one will take longer as it
+     * will fail on the second byte's verification.
+     *
+     * @param hmac1 HMAC want to be compared with.
+     * @param hmac2 HMAC want to be compared with.
+     * @return true if and ony if the give 2 HMACs are identical and non-null.
+     */
+    static boolean compareTwoHMACs(byte[] hmac1, byte[] hmac2) {
+        if (hmac1 == null || hmac2 == null) {
+            return false;
+        }
+
+        if (hmac1.length != hmac2.length) {
+            return false;
+        }
+        // This is for constant-time comparison, don't optimize it.
+        int res = 0;
+        for (int i = 0; i < hmac1.length; i++) {
+            res |= hmac1[i] ^ hmac2[i];
+        }
+        return res == 0;
+    }
+}
diff --git a/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/NamingEncoder.java b/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/NamingEncoder.java
new file mode 100644
index 0000000..1521be6
--- /dev/null
+++ b/nearby/service/java/com/android/server/nearby/common/bluetooth/fastpair/NamingEncoder.java
@@ -0,0 +1,129 @@
+/*
+ * Copyright 2021 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.nearby.common.bluetooth.fastpair;
+
+import static com.android.server.nearby.common.bluetooth.fastpair.AesCtrMultipleBlockEncryption.NONCE_SIZE;
+
+import static com.google.common.primitives.Bytes.concat;
+
+import static java.nio.charset.StandardCharsets.UTF_8;
+
+import android.annotation.TargetApi;
+import android.os.Build.VERSION_CODES;
+
+import com.google.common.base.Utf8;
+
+import java.security.GeneralSecurityException;
+import java.util.Arrays;
+
+/**
+ * Naming utilities for encoding naming packet, decoding naming packet and verifying both the data
+ * integrity and the authentication of a message by checking HMAC.
+ *
+ * <p>Naming packet is:
+ *
+ * <ol>
+ *   <li>Naming_Packet[0 - 7]: the first 8-byte of HMAC.
+ *   <li>Naming_Packet[8 - var]: the encrypted name (with 8-byte nonce appended to the front).
+ * </ol>
+ */
+@TargetApi(VERSION_CODES.M)
+public final class NamingEncoder {
+
+    static final int EXTRACT_HMAC_SIZE = 8;
+    static final int MAX_LENGTH_OF_NAME = 48;
+
+    private NamingEncoder() {
+    }
+
+    /**
+     * Encodes the name to naming packet by the given secret.
+     *
+     * @param secret AES-128 key for encryption.
+     * @param name the given name to be encoded.
+     * @return the encrypted data with the 8-byte extracted HMAC appended to the front.
+     * @throws GeneralSecurityException if the given key or name is invalid for encoding.
+     */
+    public static byte[] encodeNamingPacket(byte[] secret, String name)
+            throws GeneralSecurityException {
+        if (secret == null || secret.length != AesCtrMultipleBlockEncryption.KEY_LENGTH) {
+            throw new GeneralSecurityException(
+                    "Incorrect secret for encoding name packet, secret.length = "
+                            + (secret == null ? "NULL" : secret.length));
+        }
+
+        if ((name == null) || (name.length() == 0) || (Utf8.encodedLength(name)
+                > MAX_LENGTH_OF_NAME)) {
+            throw new GeneralSecurityException(
+                    "Invalid name for encoding name packet, Utf8.encodedLength(name) = "
+                            + (name == null ? "NULL" : Utf8.encodedLength(name)));
+        }
+
+        byte[] encryptedData = AesCtrMultipleBlockEncryption.encrypt(secret, name.getBytes(UTF_8));
+        byte[] extractedHmac =
+                Arrays.copyOf(HmacSha256.build(secret, encryptedData), EXTRACT_HMAC_SIZE);
+
+        return concat(extractedHmac, encryptedData);
+    }
+
+    /**
+     * Decodes the name from naming packet by the given secret.
+     *
+     * @param secret AES-128 key used in the encryption to decrypt data.
+     * @param namingPacket naming packet which is encoded by the given secret..
+     * @return the name decoded from the given packet.
+     * @throws GeneralSecurityException if the given key or naming packet is invalid for decoding.
+     */
+    public static String decodeNamingPacket(byte[] secret, byte[] namingPacket)
+            throws GeneralSecurityException {
+        if (secret == null || secret.length != AesCtrMultipleBlockEncryption.KEY_LENGTH) {
+            throw new GeneralSecurityException(
+                    "Incorrect secret for decoding name packet, secret.length = "
+                            + (secret == null ? "NULL" : secret.length));
+        }
+        if (namingPacket == null
+                || namingPacket.length <= EXTRACT_HMAC_SIZE
+                || namingPacket.length > (MAX_LENGTH_OF_NAME + EXTRACT_HMAC_SIZE + NONCE_SIZE)) {
+            throw new GeneralSecurityException(
+                    "Naming packet size is incorrect, namingPacket.length is "
+                            + (namingPacket == null ? "NULL" : namingPacket.length));
+        }
+
+        if (!verifyHmac(secret, namingPacket)) {
+            throw new GeneralSecurityException(
+                    "Verify HMAC failed, could be incorrect key or naming packet.");
+        }
+        byte[] encryptedData = Arrays
+                .copyOfRange(namingPacket, EXTRACT_HMAC_SIZE, namingPacket.length);
+        return new String(AesCtrMultipleBlockEncryption.decrypt(secret, encryptedData), UTF_8);
+    }
+
+    // Computes the HMAC of the given key and name, and compares the first 8-byte of the HMAC result
+    // with the one from name packet. Must call constant-time comparison to prevent a possible
+    // timing attack, e.g. time the same MAC with all different first byte for a given ciphertext,
+    // the right one will take longer as it will fail on the second byte's verification.
+    private static boolean verifyHmac(byte[] key, byte[] namingPacket)
+            throws GeneralSecurityException {
+        byte[] packetHmac = Arrays.copyOfRange(namingPacket, /* from= */ 0, EXTRACT_HMAC_SIZE);
+        byte[] encryptedData = Arrays
+                .copyOfRange(namingPacket, EXTRACT_HMAC_SIZE, namingPacket.length);
+        byte[] computedHmac = Arrays
+                .copyOf(HmacSha256.build(key, encryptedData), EXTRACT_HMAC_SIZE);
+
+        return HmacSha256.compareTwoHMACs(packetHmac, computedHmac);
+    }
+}
diff --git a/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/HmacSha256Test.java b/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/HmacSha256Test.java
new file mode 100644
index 0000000..9457e95
--- /dev/null
+++ b/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/HmacSha256Test.java
@@ -0,0 +1,147 @@
+/*
+ * Copyright (C) 2021 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.nearby.common.bluetooth.fastpair;
+
+import static com.android.server.nearby.common.bluetooth.fastpair.AesCtrMultipleBlockEncryption.KEY_LENGTH;
+import static com.android.server.nearby.common.bluetooth.fastpair.HmacSha256.HMAC_SHA256_BLOCK_SIZE;
+
+import static com.google.common.io.BaseEncoding.base16;
+import static com.google.common.primitives.Bytes.concat;
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.junit.Assert.assertThrows;
+
+import android.platform.test.annotations.Presubmit;
+
+import androidx.test.filters.SmallTest;
+import androidx.test.runner.AndroidJUnit4;
+
+import com.google.common.base.Preconditions;
+import com.google.common.hash.Hashing;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.security.GeneralSecurityException;
+import java.util.Arrays;
+import java.util.Random;
+
+/**
+ * Unit tests for {@link HmacSha256}.
+ */
+@Presubmit
+@SmallTest
+@RunWith(AndroidJUnit4.class)
+public class HmacSha256Test {
+
+    private static final int EXTRACT_HMAC_SIZE = 8;
+    private static final byte OUTER_PADDING_BYTE = 0x5c;
+    private static final byte INNER_PADDING_BYTE = 0x36;
+
+    @Test
+    public void compareResultWithOurImplementation_mustBeIdentical()
+            throws GeneralSecurityException {
+        Random random = new Random(0xFE2C);
+
+        for (int i = 0; i < 1000; i++) {
+            byte[] secret = AesCtrMultipleBlockEncryption.generateKey();
+            // Avoid too small data size that may cause false alarm.
+            int dataLength = random.nextInt(64);
+            byte[] data = new byte[dataLength];
+            random.nextBytes(data);
+
+            assertThat(HmacSha256.build(secret, data)).isEqualTo(doHmacSha256(secret, data));
+        }
+    }
+
+    @Test
+    public void inputIncorrectKeySizeToDecrypt_mustThrowException() {
+        byte[] secret = new byte[KEY_LENGTH - 1];
+        byte[] data = base16().decode("1234567890ABCDEF1234567890ABCDEF1234567890ABCD");
+
+        GeneralSecurityException exception =
+                assertThrows(GeneralSecurityException.class, () -> HmacSha256.build(secret, data));
+
+        assertThat(exception)
+                .hasMessageThat()
+                .contains("Incorrect key length, should be the AES-128 key.");
+    }
+
+    @Test
+    public void inputTwoIdenticalArrays_compareTwoHmacMustReturnTrue() {
+        Random random = new Random(0x1237);
+        byte[] array1 = new byte[EXTRACT_HMAC_SIZE];
+        random.nextBytes(array1);
+        byte[] array2 = Arrays.copyOf(array1, array1.length);
+
+        assertThat(HmacSha256.compareTwoHMACs(array1, array2)).isTrue();
+    }
+
+    @Test
+    public void inputTwoRandomArrays_compareTwoHmacMustReturnFalse() {
+        Random random = new Random(0xff);
+        byte[] array1 = new byte[EXTRACT_HMAC_SIZE];
+        random.nextBytes(array1);
+        byte[] array2 = new byte[EXTRACT_HMAC_SIZE];
+        random.nextBytes(array2);
+
+        assertThat(HmacSha256.compareTwoHMACs(array1, array2)).isFalse();
+    }
+
+    // HMAC-SHA256 may not be previously defined on Bluetooth platforms, so we explicitly create
+    // the code on test case. This will allow us to easily detect where partner implementation might
+    // have gone wrong or where our spec isn't clear enough.
+    static byte[] doHmacSha256(byte[] key, byte[] data) {
+
+        Preconditions.checkArgument(
+                key != null && key.length == KEY_LENGTH && data != null,
+                "Parameters can't be null.");
+
+        // Performs SHA256(concat((key ^ opad),SHA256(concat((key ^ ipad), data)))), where
+        // key is the given secret extended to 64 bytes by concat(secret, ZEROS).
+        // opad is 64 bytes outer padding, consisting of repeated bytes valued 0x5c.
+        // ipad is 64 bytes inner padding, consisting of repeated bytes valued 0x36.
+        byte[] keyIpad = new byte[HMAC_SHA256_BLOCK_SIZE];
+        byte[] keyOpad = new byte[HMAC_SHA256_BLOCK_SIZE];
+
+        for (int i = 0; i < KEY_LENGTH; i++) {
+            keyIpad[i] = (byte) (key[i] ^ INNER_PADDING_BYTE);
+            keyOpad[i] = (byte) (key[i] ^ OUTER_PADDING_BYTE);
+        }
+        Arrays.fill(keyIpad, KEY_LENGTH, HMAC_SHA256_BLOCK_SIZE, INNER_PADDING_BYTE);
+        Arrays.fill(keyOpad, KEY_LENGTH, HMAC_SHA256_BLOCK_SIZE, OUTER_PADDING_BYTE);
+
+        byte[] innerSha256Result = Hashing.sha256().hashBytes(concat(keyIpad, data)).asBytes();
+        return Hashing.sha256().hashBytes(concat(keyOpad, innerSha256Result)).asBytes();
+    }
+
+    // Adds this test example on spec. Also we can easily change the parameters(e.g. secret, data)
+    // to clarify test results with partners.
+    @Test
+    public void inputTestExampleToHmacSha256_getCorrectResult() {
+        byte[] secret = base16().decode("0123456789ABCDEF0123456789ABCDEF");
+        byte[] data =
+                base16().decode(
+                        "0001020304050607EE4A2483738052E44E9B2A145E5DDFAA44B9E5536AF438E1E5C6");
+
+        byte[] hmacResult = doHmacSha256(secret, data);
+
+        assertThat(hmacResult)
+                .isEqualTo(base16().decode(
+                        "55EC5E6055AF6E92618B7D8710D4413709AB5DA27CA26A66F52E5AD4E8209052"));
+    }
+}
diff --git a/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/NamingEncoderTest.java b/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/NamingEncoderTest.java
new file mode 100644
index 0000000..ba51408
--- /dev/null
+++ b/nearby/tests/src/com/android/server/nearby/common/bluetooth/fastpair/NamingEncoderTest.java
@@ -0,0 +1,141 @@
+/*
+ * Copyright (C) 2021 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.nearby.common.bluetooth.fastpair;
+
+import static com.android.server.nearby.common.bluetooth.fastpair.AesCtrMultipleBlockEncryption.KEY_LENGTH;
+import static com.android.server.nearby.common.bluetooth.fastpair.AesCtrMultipleBlockEncryption.NONCE_SIZE;
+import static com.android.server.nearby.common.bluetooth.fastpair.NamingEncoder.EXTRACT_HMAC_SIZE;
+import static com.android.server.nearby.common.bluetooth.fastpair.NamingEncoder.MAX_LENGTH_OF_NAME;
+
+import static com.google.common.io.BaseEncoding.base16;
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.junit.Assert.assertThrows;
+
+import android.platform.test.annotations.Presubmit;
+
+import androidx.test.filters.SmallTest;
+import androidx.test.runner.AndroidJUnit4;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.security.GeneralSecurityException;
+
+/**
+ * Unit tests for {@link NamingEncoder}.
+ */
+@Presubmit
+@SmallTest
+@RunWith(AndroidJUnit4.class)
+public class NamingEncoderTest {
+
+    @Test
+    public void decodeEncodedNamingPacket_mustGetSameName() throws GeneralSecurityException {
+        byte[] secret = AesCtrMultipleBlockEncryption.generateKey();
+        String name = "Someone's Google Headphone";
+
+        byte[] encodedNamingPacket = NamingEncoder.encodeNamingPacket(secret, name);
+
+        assertThat(NamingEncoder.decodeNamingPacket(secret, encodedNamingPacket)).isEqualTo(name);
+    }
+
+    @Test
+    public void inputIncorrectKeySizeToEncode_mustThrowException() {
+        byte[] secret = new byte[KEY_LENGTH - 1];
+        String data = "Someone's Google Headphone";
+
+        GeneralSecurityException exception =
+                assertThrows(
+                        GeneralSecurityException.class,
+                        () -> NamingEncoder.encodeNamingPacket(secret, data));
+
+        assertThat(exception).hasMessageThat()
+                .contains("Incorrect secret for encoding name packet");
+    }
+
+    @Test
+    public void inputIncorrectKeySizeToDecode_mustThrowException() {
+        byte[] secret = new byte[KEY_LENGTH - 1];
+        byte[] data = new byte[50];
+
+        GeneralSecurityException exception =
+                assertThrows(
+                        GeneralSecurityException.class,
+                        () -> NamingEncoder.decodeNamingPacket(secret, data));
+
+        assertThat(exception).hasMessageThat()
+                .contains("Incorrect secret for decoding name packet");
+    }
+
+    @Test
+    public void inputTooSmallPacketSize_mustThrowException() {
+        byte[] secret = new byte[KEY_LENGTH];
+        byte[] data = new byte[EXTRACT_HMAC_SIZE - 1];
+
+        GeneralSecurityException exception =
+                assertThrows(
+                        GeneralSecurityException.class,
+                        () -> NamingEncoder.decodeNamingPacket(secret, data));
+
+        assertThat(exception).hasMessageThat().contains("Naming packet size is incorrect");
+    }
+
+    @Test
+    public void inputTooLargePacketSize_mustThrowException() throws GeneralSecurityException {
+        byte[] secret = AesCtrMultipleBlockEncryption.generateKey();
+        byte[] namingPacket = new byte[MAX_LENGTH_OF_NAME + EXTRACT_HMAC_SIZE + NONCE_SIZE + 1];
+
+        GeneralSecurityException exception =
+                assertThrows(
+                        GeneralSecurityException.class,
+                        () -> NamingEncoder.decodeNamingPacket(secret, namingPacket));
+
+        assertThat(exception).hasMessageThat().contains("Naming packet size is incorrect");
+    }
+
+    @Test
+    public void inputIncorrectHmacToDecode_mustThrowException() throws GeneralSecurityException {
+        byte[] secret = AesCtrMultipleBlockEncryption.generateKey();
+        String name = "Someone's Google Headphone";
+
+        byte[] encodedNamingPacket = NamingEncoder.encodeNamingPacket(secret, name);
+        encodedNamingPacket[0] = (byte) ~encodedNamingPacket[0];
+
+        GeneralSecurityException exception =
+                assertThrows(
+                        GeneralSecurityException.class,
+                        () -> NamingEncoder.decodeNamingPacket(secret, encodedNamingPacket));
+
+        assertThat(exception)
+                .hasMessageThat()
+                .contains("Verify HMAC failed, could be incorrect key or naming packet.");
+    }
+
+    // Adds this test example on spec. Also we can easily change the parameters(e.g. secret, naming
+    // packet) to clarify test results with partners.
+    @Test
+    public void decodeTestNamingPacket_mustGetSameName() throws GeneralSecurityException {
+        byte[] secret = base16().decode("0123456789ABCDEF0123456789ABCDEF");
+        byte[] namingPacket = base16().decode(
+                "55EC5E6055AF6E920001020304050607EE4A2483738052E44E9B2A145E5DDFAA44B9E5536AF438"
+                        + "E1E5C6");
+
+        assertThat(NamingEncoder.decodeNamingPacket(secret, namingPacket))
+                .isEqualTo("Someone's Google Headphone");
+    }
+}