diff --git a/service-t/src/com/android/server/NsdService.java b/service-t/src/com/android/server/NsdService.java
index 7c1ca30..0a8adf0 100644
--- a/service-t/src/com/android/server/NsdService.java
+++ b/service-t/src/com/android/server/NsdService.java
@@ -201,6 +201,7 @@
     private static final int NO_SENT_QUERY_COUNT = 0;
     private static final int DISCOVERY_QUERY_SENT_CALLBACK = 1000;
     private static final int MAX_SUBTYPE_COUNT = 100;
+    private static final int DNSSEC_PROTOCOL = 3;
     private static final SharedLog LOGGER = new SharedLog("serviceDiscovery");
 
     private final Context mContext;
@@ -1009,6 +1010,17 @@
                                 break;
                             }
 
+                            if (!checkPublicKey(serviceInfo.getPublicKey())) {
+                                Log.e(TAG,
+                                        "Invalid public key: "
+                                                + Arrays.toString(serviceInfo.getPublicKey()));
+                                clientInfo.onRegisterServiceFailedImmediately(
+                                        clientRequestId,
+                                        NsdManager.FAILURE_BAD_PARAMETERS,
+                                        false /* isLegacy */);
+                                break;
+                            }
+
                             Set<String> subtypes = new ArraySet<>(serviceInfo.getSubtypes());
                             if (typeSubtype != null && typeSubtype.second != null) {
                                 for (String subType : typeSubtype.second) {
@@ -1842,6 +1854,25 @@
         return Pattern.compile(HOSTNAME_REGEX).matcher(hostname).matches();
     }
 
+    /**
+     * Checks if the public key is valid.
+     *
+     * <p>For simplicity, it only checks if the protocol is DNSSEC and the RDATA is not fewer than 4
+     * bytes. See RFC 3445 Section 3.
+     *
+     * <p>Message format: flags (2 bytes), protocol (1 byte), algorithm (1 byte), public key.
+     */
+    private static boolean checkPublicKey(@Nullable byte[] publicKey) {
+        if (publicKey == null) {
+            return true;
+        }
+        if (publicKey.length < 4) {
+            return false;
+        }
+        int protocol = publicKey[2];
+        return protocol == DNSSEC_PROTOCOL;
+    }
+
     /** Returns {@code true} if {@code subtype} is a valid DNS-SD subtype label. */
     private static boolean checkSubtypeLabel(String subtype) {
         return Pattern.compile("^" + SUBTYPE_LABEL_REGEX + "$").matcher(subtype).matches();
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsKeyRecord.java b/service-t/src/com/android/server/connectivity/mdns/MdnsKeyRecord.java
new file mode 100644
index 0000000..ba8a56e
--- /dev/null
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsKeyRecord.java
@@ -0,0 +1,100 @@
+/*
+ * Copyright (C) 2024 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.connectivity.mdns;
+
+import static com.android.net.module.util.HexDump.toHexString;
+
+import android.annotation.NonNull;
+import android.annotation.Nullable;
+
+import androidx.annotation.VisibleForTesting;
+
+import java.io.IOException;
+import java.util.Arrays;
+
+/** An mDNS "KEY" record, which contains a public key for a name. See RFC 2535. */
+@VisibleForTesting(otherwise = VisibleForTesting.PACKAGE_PRIVATE)
+public class MdnsKeyRecord extends MdnsRecord {
+    @Nullable private byte[] rData;
+
+    public MdnsKeyRecord(@NonNull String[] name, @NonNull MdnsPacketReader reader)
+            throws IOException {
+        this(name, reader, false);
+    }
+
+    public MdnsKeyRecord(@NonNull String[] name, @NonNull MdnsPacketReader reader,
+            boolean isQuestion) throws IOException {
+        super(name, TYPE_KEY, reader, isQuestion);
+    }
+
+    public MdnsKeyRecord(@NonNull String[] name, boolean isUnicast) {
+        super(name, TYPE_KEY,
+                MdnsConstants.QCLASS_INTERNET | (isUnicast ? MdnsConstants.QCLASS_UNICAST : 0),
+                0L /* receiptTimeMillis */, false /* cacheFlush */, 0L /* ttlMillis */);
+    }
+
+    public MdnsKeyRecord(@NonNull String[] name, long receiptTimeMillis, boolean cacheFlush,
+            long ttlMillis, @Nullable byte[] rData) {
+        super(name, TYPE_KEY, MdnsConstants.QCLASS_INTERNET, receiptTimeMillis, cacheFlush,
+                ttlMillis);
+        if (rData != null) {
+            this.rData = Arrays.copyOf(rData, rData.length);
+        }
+    }
+    /** Returns the KEY RDATA in bytes **/
+    public byte[] getRData() {
+        if (rData == null) {
+            return null;
+        }
+        return Arrays.copyOf(rData, rData.length);
+    }
+
+    @Override
+    protected void readData(MdnsPacketReader reader) throws IOException {
+        rData = new byte[reader.getRemaining()];
+        reader.readBytes(rData);
+    }
+
+    @Override
+    protected void writeData(MdnsPacketWriter writer) throws IOException {
+        if (rData != null) {
+            writer.writeBytes(rData);
+        }
+    }
+
+    @Override
+    public String toString() {
+        return "KEY: " + toHexString(rData);
+    }
+
+    @Override
+    public int hashCode() {
+        return (super.hashCode() * 31) + Arrays.hashCode(rData);
+    }
+
+    @Override
+    public boolean equals(@Nullable Object other) {
+        if (this == other) {
+            return true;
+        }
+        if (!(other instanceof MdnsKeyRecord)) {
+            return false;
+        }
+
+        return super.equals(other) && Arrays.equals(rData, ((MdnsKeyRecord) other).rData);
+    }
+}
\ No newline at end of file
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsPacket.java b/service-t/src/com/android/server/connectivity/mdns/MdnsPacket.java
index 83ecabc..aef8211 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsPacket.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsPacket.java
@@ -196,6 +196,15 @@
                 }
             }
 
+            case MdnsRecord.TYPE_KEY: {
+                try {
+                    return new MdnsKeyRecord(name, reader, isQuestion);
+                } catch (IOException e) {
+                    throw new ParseException(MdnsResponseErrorCode.ERROR_READING_KEY_RDATA,
+                            "Failed to read KEY record from mDNS response.", e);
+                }
+            }
+
             case MdnsRecord.TYPE_NSEC: {
                 try {
                     return new MdnsNsecRecord(name, reader, isQuestion);
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsRecord.java b/service-t/src/com/android/server/connectivity/mdns/MdnsRecord.java
index 1f9f42b..b865319 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsRecord.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsRecord.java
@@ -41,6 +41,7 @@
     public static final int TYPE_PTR = 0x000C;
     public static final int TYPE_SRV = 0x0021;
     public static final int TYPE_TXT = 0x0010;
+    public static final int TYPE_KEY = 0x0019;
     public static final int TYPE_NSEC = 0x002f;
     public static final int TYPE_ANY = 0x00ff;
 
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java b/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java
index eb85110..39e8bcc 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java
@@ -184,6 +184,10 @@
         public final RecordInfo<MdnsServiceRecord> srvRecord;
         @Nullable
         public final RecordInfo<MdnsTextRecord> txtRecord;
+        @Nullable
+        public final RecordInfo<MdnsKeyRecord> serviceKeyRecord;
+        @Nullable
+        public final RecordInfo<MdnsKeyRecord> hostKeyRecord;
         @NonNull
         public final List<RecordInfo<MdnsInetAddressRecord>> addressRecords;
         @NonNull
@@ -245,7 +249,6 @@
                 nameRecordsTtlMillis = DEFAULT_NAME_RECORDS_TTL_MILLIS;
             }
 
-            final boolean hasService = !TextUtils.isEmpty(serviceInfo.getServiceType());
             final boolean hasCustomHost = !TextUtils.isEmpty(serviceInfo.getHostname());
             final String[] hostname =
                     hasCustomHost
@@ -253,9 +256,11 @@
                             : deviceHostname;
             final ArrayList<RecordInfo<?>> allRecords = new ArrayList<>(5);
 
-            if (hasService) {
-                final String[] serviceType = splitServiceType(serviceInfo);
-                final String[] serviceName = splitFullyQualifiedName(serviceInfo, serviceType);
+            final boolean hasService = !TextUtils.isEmpty(serviceInfo.getServiceType());
+            final String[] serviceType = hasService ? splitServiceType(serviceInfo) : null;
+            final String[] serviceName =
+                    hasService ? splitFullyQualifiedName(serviceInfo, serviceType) : null;
+            if (hasService && hasSrvRecord(serviceInfo)) {
                 // Service PTR records
                 ptrRecords = new ArrayList<>(serviceInfo.getSubtypes().size() + 1);
                 ptrRecords.add(new RecordInfo<>(
@@ -336,6 +341,36 @@
                 addressRecords = Collections.emptyList();
             }
 
+            final boolean hasKey = hasKeyRecord(serviceInfo);
+            if (hasKey && hasService) {
+                this.serviceKeyRecord = new RecordInfo<>(
+                        serviceInfo,
+                        new MdnsKeyRecord(
+                                serviceName,
+                                0L /*receiptTimeMillis */,
+                                true /* cacheFlush */,
+                                nameRecordsTtlMillis,
+                                serviceInfo.getPublicKey()),
+                        false /* sharedName */);
+                allRecords.add(this.serviceKeyRecord);
+            } else {
+                this.serviceKeyRecord = null;
+            }
+            if (hasKey && hasCustomHost) {
+                this.hostKeyRecord = new RecordInfo<>(
+                        serviceInfo,
+                        new MdnsKeyRecord(
+                                hostname,
+                                0L /*receiptTimeMillis */,
+                                true /* cacheFlush */,
+                                nameRecordsTtlMillis,
+                                serviceInfo.getPublicKey()),
+                        false /* sharedName */);
+                allRecords.add(this.hostKeyRecord);
+            } else {
+                this.hostKeyRecord = null;
+            }
+
             this.allRecords = Collections.unmodifiableList(allRecords);
             this.repliedServiceCount = repliedServiceCount;
             this.sentPacketCount = sentPacketCount;
@@ -486,6 +521,22 @@
                             ? inetAddressRecord.getInet6Address()
                             : inetAddressRecord.getInet4Address()));
         }
+
+        List<MdnsKeyRecord> keyRecords = new ArrayList<>();
+        if (registration.serviceKeyRecord != null) {
+            keyRecords.add(registration.serviceKeyRecord.record);
+        }
+        if (registration.hostKeyRecord != null) {
+            keyRecords.add(registration.hostKeyRecord.record);
+        }
+        for (MdnsKeyRecord keyRecord : keyRecords) {
+            probingRecords.add(new MdnsKeyRecord(
+                            keyRecord.getName(),
+                            0L /* receiptTimeMillis */,
+                            false /* cacheFlush */,
+                            keyRecord.getTtl(),
+                            keyRecord.getRData()));
+        }
         return new MdnsProber.ProbingInfo(serviceId, probingRecords);
     }
 
@@ -1101,18 +1152,15 @@
                 Collections.emptyList() /* additionalRecords */);
     }
 
-    /** Check if the record is in any service registration */
-    private boolean hasInetAddressRecord(@NonNull MdnsInetAddressRecord record) {
-        for (int i = 0; i < mServices.size(); i++) {
-            final ServiceRegistration registration = mServices.valueAt(i);
-            if (registration.exiting) continue;
-
-            for (RecordInfo<MdnsInetAddressRecord> localRecord : registration.addressRecords) {
-                if (Objects.equals(localRecord.record, record)) {
-                    return true;
-                }
+    /** Check if the record is in a registration */
+    private static boolean hasInetAddressRecord(
+            @NonNull ServiceRegistration registration, @NonNull MdnsInetAddressRecord record) {
+        for (RecordInfo<MdnsInetAddressRecord> localRecord : registration.addressRecords) {
+            if (Objects.equals(localRecord.record, record)) {
+                return true;
             }
         }
+
         return false;
     }
 
@@ -1155,36 +1203,33 @@
         return conflicting;
     }
 
-
     private static boolean conflictForService(
             @NonNull MdnsRecord record, @NonNull ServiceRegistration registration) {
-        if (registration.srvRecord == null) {
+        String[] fullServiceName;
+        if (registration.srvRecord != null) {
+            fullServiceName = registration.srvRecord.record.getName();
+        } else if (registration.serviceKeyRecord != null) {
+            fullServiceName = registration.serviceKeyRecord.record.getName();
+        } else {
             return false;
         }
 
-        final RecordInfo<MdnsServiceRecord> srvRecord = registration.srvRecord;
-        if (!MdnsUtils.equalsDnsLabelIgnoreDnsCase(record.getName(), srvRecord.record.getName())) {
+        if (!MdnsUtils.equalsDnsLabelIgnoreDnsCase(record.getName(), fullServiceName)) {
             return false;
         }
 
         // As per RFC6762 9., it's fine if the "conflict" is an identical record with same
         // data.
-        if (record instanceof MdnsServiceRecord) {
-            final MdnsServiceRecord local = srvRecord.record;
-            final MdnsServiceRecord other = (MdnsServiceRecord) record;
-            // Note "equals" does not consider TTL or receipt time, as intended here
-            if (Objects.equals(local, other)) {
-                return false;
-            }
+        if (record instanceof MdnsServiceRecord && equals(record, registration.srvRecord)) {
+            return false;
+        }
+        if (record instanceof MdnsTextRecord && equals(record, registration.txtRecord)) {
+            return false;
+        }
+        if (record instanceof MdnsKeyRecord && equals(record, registration.serviceKeyRecord)) {
+            return false;
         }
 
-        if (record instanceof MdnsTextRecord) {
-            final MdnsTextRecord local = registration.txtRecord.record;
-            final MdnsTextRecord other = (MdnsTextRecord) record;
-            if (Objects.equals(local, other)) {
-                return false;
-            }
-        }
         return true;
     }
 
@@ -1196,6 +1241,11 @@
             return false;
         }
 
+        // It cannot be a hostname conflict because not record is registered with the hostname.
+        if (registration.addressRecords.isEmpty() && registration.hostKeyRecord == null) {
+            return false;
+        }
+
         // The record's name cannot be registered by NsdManager so it's not a conflict.
         if (record.getName().length != 2 || !record.getName()[1].equals(LOCAL_TLD)) {
             return false;
@@ -1207,13 +1257,26 @@
             return false;
         }
 
-        // If this registration has any address record and there's no identical record in the
-        // repository, it's a conflict. There will be no conflict if no registration has addresses
-        // for that hostname.
-        if (record instanceof MdnsInetAddressRecord) {
-            if (!registration.addressRecords.isEmpty()) {
-                return !hasInetAddressRecord((MdnsInetAddressRecord) record);
-            }
+        // As per RFC6762 9., it's fine if the "conflict" is an identical record with same
+        // data.
+        if (record instanceof MdnsInetAddressRecord
+                && hasInetAddressRecord(registration, (MdnsInetAddressRecord) record)) {
+            return false;
+        }
+        if (record instanceof MdnsKeyRecord && equals(record, registration.hostKeyRecord)) {
+            return false;
+        }
+
+        // Per RFC 6762 8.1, when a record is being probed, any answer containing a record with that
+        // name, of any type, MUST be considered a conflicting response.
+        if (registration.isProbing) {
+            return true;
+        }
+        if (record instanceof MdnsInetAddressRecord && !registration.addressRecords.isEmpty()) {
+            return true;
+        }
+        if (record instanceof MdnsKeyRecord && registration.hostKeyRecord != null) {
+            return true;
         }
 
         return false;
@@ -1402,4 +1465,21 @@
 
         return type;
     }
+
+    /** Returns whether there will be an SRV record when registering the {@code info}. */
+    private static boolean hasSrvRecord(@NonNull NsdServiceInfo info) {
+        return info.getPort() > 0;
+    }
+
+    /** Returns whether there will be KEY record(s) when registering the {@code info}. */
+    private static boolean hasKeyRecord(@NonNull NsdServiceInfo info) {
+        return info.getPublicKey() != null;
+    }
+
+    private static boolean equals(@NonNull MdnsRecord record, @Nullable RecordInfo<?> recordInfo) {
+        if (recordInfo == null) {
+            return false;
+        }
+        return Objects.equals(record, recordInfo.record);
+    }
 }
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsResponseErrorCode.java b/service-t/src/com/android/server/connectivity/mdns/MdnsResponseErrorCode.java
index 73a7e3a..f509da2 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsResponseErrorCode.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsResponseErrorCode.java
@@ -37,4 +37,5 @@
     public static final int ERROR_END_OF_FILE = 12;
     public static final int ERROR_READING_NSEC_RDATA = 13;
     public static final int ERROR_READING_ANY_RDATA = 14;
+    public static final int ERROR_READING_KEY_RDATA = 15;
 }
\ No newline at end of file
diff --git a/tests/cts/net/src/android/net/cts/NsdManagerTest.kt b/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
index 6c6f6a3..28685cc 100644
--- a/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
+++ b/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
@@ -1463,10 +1463,8 @@
         handlerThread.waitForIdle(TIMEOUT_MS)
 
         tryTest {
-            repeat(3) {
-                assertNotNull(packetReader.pollForAdvertisement(serviceName, serviceType),
-                        "Expect 3 announcements sent after initial probing")
-            }
+            assertNotNull(packetReader.pollForAdvertisement(serviceName, serviceType),
+                "No announcements sent after initial probing")
 
             assertEquals(si.serviceName, registeredService.serviceName)
             assertEquals(si.hostname, registeredService.hostname)
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
index f7e0b0e..d735dc6 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
@@ -21,11 +21,13 @@
 import android.net.nsd.NsdServiceInfo
 import android.os.Build
 import android.os.HandlerThread
+import com.android.net.module.util.HexDump.hexStringToByteArray
 import com.android.server.connectivity.mdns.MdnsAnnouncer.AnnouncementInfo
 import com.android.server.connectivity.mdns.MdnsInterfaceAdvertiser.CONFLICT_HOST
 import com.android.server.connectivity.mdns.MdnsInterfaceAdvertiser.CONFLICT_SERVICE
 import com.android.server.connectivity.mdns.MdnsRecord.TYPE_A
 import com.android.server.connectivity.mdns.MdnsRecord.TYPE_AAAA
+import com.android.server.connectivity.mdns.MdnsRecord.TYPE_KEY
 import com.android.server.connectivity.mdns.MdnsRecord.TYPE_PTR
 import com.android.server.connectivity.mdns.MdnsRecord.TYPE_SRV
 import com.android.server.connectivity.mdns.MdnsRecord.TYPE_TXT
@@ -120,6 +122,20 @@
     port = TEST_PORT
 }
 
+private val TEST_PUBLIC_KEY = hexStringToByteArray(
+        "0201030dc141d0637960b98cbc12cfca"
+                + "221d2879dac26ee5b460e9007c992e19"
+                + "02d897c391b03764d448f7d0c772fdb0"
+                + "3b1d9d6d52ff8886769e8e2362513565"
+                + "270962d3")
+
+private val TEST_PUBLIC_KEY_2 = hexStringToByteArray(
+        "0201030dc141d0637960b98cbc12cfca"
+                + "221d2879dac26ee5b460e9007c992e19"
+                + "02d897c391b03764d448f7d0c772fdb0"
+                + "3b1d9d6d52ff8886769e8e2362513565"
+                + "270962d4")
+
 @RunWith(DevSdkIgnoreRunner::class)
 @DevSdkIgnoreRule.IgnoreUpTo(Build.VERSION_CODES.S_V2)
 class MdnsRecordRepositoryTest {
@@ -581,6 +597,7 @@
             TYPE_PTR -> return MdnsPointerRecord(name, false /* isUnicast */)
             TYPE_SRV -> return MdnsServiceRecord(name, false /* isUnicast */)
             TYPE_TXT -> return MdnsTextRecord(name, false /* isUnicast */)
+            TYPE_KEY -> return MdnsKeyRecord(name, false /* isUnicast */)
             TYPE_A, TYPE_AAAA -> return MdnsInetAddressRecord(name, type, false /* isUnicast */)
             else -> fail("Unexpected question type: $type")
         }
@@ -908,6 +925,159 @@
     }
 
     @Test
+    fun testGetReply_keyQuestionForServiceName_returnsKeyRecord() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            serviceType = "_testservice._tcp"
+            serviceName = "MyTestService1"
+            port = TEST_PORT
+            publicKey = TEST_PUBLIC_KEY
+        })
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_2, NsdServiceInfo().apply {
+            serviceType = "_testservice._tcp"
+            serviceName = "MyTestService2"
+            port = 0 // No SRV RR
+            publicKey = TEST_PUBLIC_KEY
+        })
+        val src = InetSocketAddress(parseNumericAddress("fe80::123"), 5353)
+        val serviceName1 = arrayOf("MyTestService1", "_testservice", "_tcp", "local")
+        val serviceName2 = arrayOf("MyTestService2", "_testservice", "_tcp", "local")
+
+        val query1 = makeQuery(TYPE_KEY to serviceName1)
+        val reply1 = repository.getReply(query1, src)
+
+        assertNotNull(reply1)
+        assertEquals(listOf(MdnsKeyRecord(serviceName1,
+                0, false, LONG_TTL, TEST_PUBLIC_KEY)),
+                reply1.answers)
+        assertEquals(listOf(),
+                reply1.additionalAnswers)
+
+        val query2 = makeQuery(TYPE_KEY to serviceName2)
+        val reply2 = repository.getReply(query2, src)
+
+        assertNotNull(reply2)
+        assertEquals(listOf(MdnsKeyRecord(serviceName2,
+                0, false, LONG_TTL, TEST_PUBLIC_KEY)),
+                reply2.answers)
+        assertEquals(listOf(MdnsNsecRecord(serviceName2,
+                0L, true, SHORT_TTL,
+                serviceName2 /* nextDomain */,
+                intArrayOf(TYPE_KEY))),
+                reply2.additionalAnswers)
+    }
+
+    @Test
+    fun testGetReply_keyQuestionForHostname_returnsKeyRecord() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            hostname = "MyHost1"
+            hostAddresses = listOf(
+                    parseNumericAddress("2001:db8::1"),
+                    parseNumericAddress("2001:db8::2"))
+            publicKey = TEST_PUBLIC_KEY
+        })
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_2, NsdServiceInfo().apply {
+            hostname = "MyHost2"
+            hostAddresses = listOf() // No address records
+            publicKey = TEST_PUBLIC_KEY
+        })
+        val src = InetSocketAddress(parseNumericAddress("fe80::123"), 5353)
+        val hostname1 = arrayOf("MyHost1", "local")
+        val hostname2 = arrayOf("MyHost2", "local")
+
+        val query1 = makeQuery(TYPE_KEY to hostname1)
+        val reply1 = repository.getReply(query1, src)
+
+        assertNotNull(reply1)
+        assertEquals(listOf(MdnsKeyRecord(hostname1,
+                0, false, LONG_TTL, TEST_PUBLIC_KEY)),
+                reply1.answers)
+        assertEquals(listOf(),
+                reply1.additionalAnswers)
+
+        val query2 = makeQuery(TYPE_KEY to hostname2)
+        val reply2 = repository.getReply(query2, src)
+
+        assertNotNull(reply2)
+        assertEquals(listOf(MdnsKeyRecord(hostname2,
+                0, false, LONG_TTL, TEST_PUBLIC_KEY)),
+                reply2.answers)
+        assertEquals(listOf(MdnsNsecRecord(hostname2, 0L, true, SHORT_TTL,
+                hostname2 /* nextDomain */,
+                intArrayOf(TYPE_KEY))),
+                reply2.additionalAnswers)
+    }
+
+    @Test
+    fun testGetReply_keyRecordForHostRemoved_noAnswertoKeyQuestion() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            hostname = "MyHost1"
+            hostAddresses = listOf(
+                    parseNumericAddress("2001:db8::1"),
+                    parseNumericAddress("2001:db8::2"))
+            publicKey = TEST_PUBLIC_KEY
+        })
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_2, NsdServiceInfo().apply {
+            hostname = "MyHost2"
+            hostAddresses = listOf() // No address records
+            publicKey = TEST_PUBLIC_KEY
+        })
+        repository.removeService(TEST_SERVICE_ID_1)
+        repository.removeService(TEST_SERVICE_ID_2)
+        val src = InetSocketAddress(parseNumericAddress("fe80::123"), 5353)
+        val hostname1 = arrayOf("MyHost1", "local")
+        val hostname2 = arrayOf("MyHost2", "local")
+
+        val query1 = makeQuery(TYPE_KEY to hostname1)
+        val reply1 = repository.getReply(query1, src)
+
+        assertNull(reply1)
+
+        val query2 = makeQuery(TYPE_KEY to hostname2)
+        val reply2 = repository.getReply(query2, src)
+
+        assertNull(reply2)
+    }
+
+    @Test
+    fun testGetReply_keyRecordForServiceRemoved_noAnswertoKeyQuestion() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            serviceType = "_testservice._tcp"
+            serviceName = "MyTestService1"
+            port = TEST_PORT
+            publicKey = TEST_PUBLIC_KEY
+        })
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_2, NsdServiceInfo().apply {
+            serviceType = "_testservice._tcp"
+            serviceName = "MyTestService2"
+            port = 0 // No SRV RR
+            publicKey = TEST_PUBLIC_KEY
+        })
+        repository.removeService(TEST_SERVICE_ID_1)
+        repository.removeService(TEST_SERVICE_ID_2)
+        val src = InetSocketAddress(parseNumericAddress("fe80::123"), 5353)
+        val serviceName1 = arrayOf("MyTestService1", "_testservice", "_tcp", "local")
+        val serviceName2 = arrayOf("MyTestService2", "_testservice", "_tcp", "local")
+
+        val query1 = makeQuery(TYPE_KEY to serviceName1)
+        val reply1 = repository.getReply(query1, src)
+
+        assertNull(reply1)
+
+        val query2 = makeQuery(TYPE_KEY to serviceName2)
+        val reply2 = repository.getReply(query2, src)
+
+        assertNull(reply2)
+    }
+
+    @Test
     fun testGetReply_customHostRemoved_noAnswerToAAAAQuestion() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
         repository.initWithService(
@@ -1221,8 +1391,8 @@
     @Test
     fun testGetConflictingServices_customHostsReplyHasFewerAddressesThanUs_noConflict() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
-        repository.addService(TEST_CUSTOM_HOST_ID_1, TEST_CUSTOM_HOST_1, null /* ttl */)
-        repository.addService(TEST_CUSTOM_HOST_ID_2, TEST_CUSTOM_HOST_2, null /* ttl */)
+        repository.addServiceAndFinishProbing(TEST_CUSTOM_HOST_ID_1, TEST_CUSTOM_HOST_1)
+        repository.addServiceAndFinishProbing(TEST_CUSTOM_HOST_ID_2, TEST_CUSTOM_HOST_2)
 
         val packet = MdnsPacket(
                 0, /* flags */
@@ -1240,10 +1410,30 @@
     }
 
     @Test
-    fun testGetConflictingServices_customHostsReplyHasIdenticalHosts_noConflict() {
+    fun testGetConflictingServices_customHostsReplyHasSameNameRecord_conflictDuringProbing() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
         repository.addService(TEST_CUSTOM_HOST_ID_1, TEST_CUSTOM_HOST_1, null /* ttl */)
-        repository.addService(TEST_CUSTOM_HOST_ID_2, TEST_CUSTOM_HOST_2, null /* ttl */)
+        repository.addServiceAndFinishProbing(TEST_CUSTOM_HOST_ID_2, TEST_CUSTOM_HOST_2)
+
+        val packet = MdnsPacket(
+            0, /* flags */
+            emptyList(), /* questions */
+            listOf(MdnsKeyRecord(arrayOf("TestHost", "local"),
+                    0L /* receiptTimeMillis */, true /* cacheFlush */,
+                    0L /* ttlMillis */, TEST_PUBLIC_KEY),
+            ) /* answers */,
+            emptyList() /* authorityRecords */,
+            emptyList() /* additionalRecords */)
+
+        assertEquals(mapOf(TEST_CUSTOM_HOST_ID_1 to CONFLICT_HOST),
+            repository.getConflictingServices(packet))
+    }
+
+    @Test
+    fun testGetConflictingServices_customHostsReplyHasIdenticalHosts_noConflict() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+        repository.addServiceAndFinishProbing(TEST_CUSTOM_HOST_ID_1, TEST_CUSTOM_HOST_1)
+        repository.addServiceAndFinishProbing(TEST_CUSTOM_HOST_ID_2, TEST_CUSTOM_HOST_2)
 
         val packet = MdnsPacket(
                 0, /* flags */
@@ -1267,8 +1457,8 @@
     @Test
     fun testGetConflictingServices_customHostsCaseInsensitiveReplyHasIdenticalHosts_noConflict() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
-        repository.addService(TEST_CUSTOM_HOST_ID_1, TEST_CUSTOM_HOST_1, null /* ttl */)
-        repository.addService(TEST_CUSTOM_HOST_ID_2, TEST_CUSTOM_HOST_2, null /* ttl */)
+        repository.addServiceAndFinishProbing(TEST_CUSTOM_HOST_ID_1, TEST_CUSTOM_HOST_1)
+        repository.addServiceAndFinishProbing(TEST_CUSTOM_HOST_ID_2, TEST_CUSTOM_HOST_2)
 
         val packet = MdnsPacket(
                 0, /* flags */
@@ -1289,6 +1479,152 @@
     }
 
     @Test
+    fun testGetConflictingServices_identicalKeyRecordsForService_noConflict() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addService(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            serviceType = "_testservice._tcp"
+            serviceName = "MyTestService"
+            port = TEST_PORT
+            publicKey = TEST_PUBLIC_KEY
+        }, null /* ttl */)
+
+        val otherTtlMillis = 1234L
+        val packet = MdnsPacket(
+                0 /* flags */,
+                emptyList() /* questions */,
+                listOf(
+                        MdnsKeyRecord(
+                                arrayOf("MyTestService", "_testservice", "_tcp", "local"),
+                                0L /* receiptTimeMillis */, true /* cacheFlush */,
+                                otherTtlMillis,
+                                TEST_PUBLIC_KEY)
+                ) /* answers */,
+                emptyList() /* authorityRecords */,
+                emptyList() /* additionalRecords */)
+
+        assertEquals(emptyMap(),
+                repository.getConflictingServices(packet))
+    }
+
+    @Test
+    fun testGetConflictingServices_differentKeyRecordsForService_conflict() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addService(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            serviceType = "_testservice._tcp"
+            serviceName = "MyTestService"
+            port = TEST_PORT
+            publicKey = TEST_PUBLIC_KEY
+        }, null /* null */)
+
+        val otherTtlMillis = 1234L
+        val packet = MdnsPacket(
+                0 /* flags */,
+                emptyList() /* questions */,
+                listOf(
+                        MdnsKeyRecord(
+                                arrayOf("MyTestService", "_testservice", "_tcp", "local"),
+                                0L /* receiptTimeMillis */, true /* cacheFlush */,
+                                otherTtlMillis,
+                                TEST_PUBLIC_KEY_2)
+                ) /* answers */,
+                emptyList() /* authorityRecords */,
+                emptyList() /* additionalRecords */)
+
+        assertEquals(mapOf(TEST_SERVICE_ID_1 to CONFLICT_SERVICE),
+                repository.getConflictingServices(packet))
+    }
+
+    @Test
+    fun testGetConflictingServices_identicalKeyRecordsForHost_noConflict() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addServiceAndFinishProbing(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            hostname = "MyHost"
+            hostAddresses = listOf(
+                parseNumericAddress("2001:db8::1"),
+                parseNumericAddress("2001:db8::2")
+            )
+            publicKey = TEST_PUBLIC_KEY
+        })
+
+        val otherTtlMillis = 1234L
+        val packet = MdnsPacket(
+                0 /* flags */,
+                emptyList() /* questions */,
+                listOf(
+                        MdnsKeyRecord(
+                                arrayOf("MyHost", "local"),
+                                0L /* receiptTimeMillis */, true /* cacheFlush */,
+                                otherTtlMillis,
+                                TEST_PUBLIC_KEY)
+                ) /* answers */,
+                emptyList() /* authorityRecords */,
+                emptyList() /* additionalRecords */)
+
+        assertEquals(emptyMap(),
+                repository.getConflictingServices(packet))
+    }
+
+    @Test
+    fun testGetConflictingServices_keyForCustomHostReplySameRecordName_conflictDuringProbing() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addService(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            hostname = "MyHost"
+            publicKey = TEST_PUBLIC_KEY
+        }, null /* ttl */)
+
+        val otherTtlMillis = 1234L
+        val packet = MdnsPacket(
+            0 /* flags */,
+            emptyList() /* questions */,
+            listOf(MdnsInetAddressRecord(arrayOf("MyHost", "local"),
+                    0L /* receiptTimeMillis */,
+                    true /* cacheFlush */,
+                    otherTtlMillis,
+                    parseNumericAddress("192.168.2.111"))
+            ) /* answers */,
+            emptyList() /* authorityRecords */,
+            emptyList() /* additionalRecords */
+        )
+
+        assertEquals(mapOf(TEST_SERVICE_ID_1 to CONFLICT_HOST),
+            repository.getConflictingServices(packet))
+    }
+
+    @Test
+    fun testGetConflictingServices_differentKeyRecordsForHost_conflict() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
+
+        repository.addService(TEST_SERVICE_ID_1, NsdServiceInfo().apply {
+            hostname = "MyHost"
+            hostAddresses = listOf(
+                    parseNumericAddress("2001:db8::1"),
+                    parseNumericAddress("2001:db8::2"))
+            publicKey = TEST_PUBLIC_KEY
+        }, null /* ttl */)
+
+        val otherTtlMillis = 1234L
+        val packet = MdnsPacket(
+                0 /* flags */,
+                emptyList() /* questions */,
+                listOf(
+                        MdnsKeyRecord(
+                                arrayOf("MyHost", "local"),
+                                0L /* receiptTimeMillis */, true /* cacheFlush */,
+                                otherTtlMillis,
+                                TEST_PUBLIC_KEY_2)
+                ) /* answers */,
+                emptyList() /* authorityRecords */,
+                emptyList() /* additionalRecords */)
+
+        assertEquals(mapOf(TEST_SERVICE_ID_1 to CONFLICT_HOST),
+                repository.getConflictingServices(packet))
+    }
+
+    @Test
     fun testGetConflictingServices_IdenticalService() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME, makeFlags())
         repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1, null /* ttl */)
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java
index 55c2846..63548c1 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java
@@ -16,11 +16,13 @@
 
 package com.android.server.connectivity.mdns;
 
+import static com.android.server.connectivity.mdns.MdnsConstants.QCLASS_INTERNET;
 import static com.android.testutils.DevSdkIgnoreRuleKt.SC_V2;
 
 import static org.junit.Assert.assertArrayEquals;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotEquals;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertThrows;
@@ -424,4 +426,92 @@
         assertEquals(new TextEntry("xyz", HexDump.hexStringToByteArray("FFEFDFCF")),
                 entries.get(2));
     }
+
+    @Test
+    public void testKeyRecord() throws IOException {
+        final byte[] dataIn =
+                HexDump.hexStringToByteArray(
+                        "09746573742d686f7374056c6f63616c"
+                                + "00001980010000000a00440201030dc1"
+                                + "41d0637960b98cbc12cfca221d2879da"
+                                + "c26ee5b460e9007c992e1902d897c391"
+                                + "b03764d448f7d0c772fdb03b1d9d6d52"
+                                + "ff8886769e8e2362513565270962d3");
+        final byte[] rData =
+                HexDump.hexStringToByteArray(
+                        "0201030dc141d0637960b98cbc12cfca"
+                                + "221d2879dac26ee5b460e9007c992e19"
+                                + "02d897c391b03764d448f7d0c772fdb0"
+                                + "3b1d9d6d52ff8886769e8e2362513565"
+                                + "270962d3");
+        assertNotNull(dataIn);
+        String dataInText = HexDump.dumpHexString(dataIn, 0, dataIn.length);
+
+        // Decode
+        DatagramPacket packet = new DatagramPacket(dataIn, dataIn.length);
+        MdnsPacketReader reader = new MdnsPacketReader(packet);
+
+        String[] name = reader.readLabels();
+        assertNotNull(name);
+        assertEquals(2, name.length);
+        String fqdn = MdnsRecord.labelsToString(name);
+        assertEquals("test-host.local", fqdn);
+
+        int type = reader.readUInt16();
+        assertEquals(MdnsRecord.TYPE_KEY, type);
+
+        MdnsKeyRecord keyRecord;
+
+        // MdnsKeyRecord(String[] name, MdnsPacketReader reader)
+        reader = new MdnsPacketReader(packet);
+        reader.readLabels(); // Skip labels
+        reader.readUInt16(); // Skip type
+        keyRecord = new MdnsKeyRecord(name, reader);
+        assertEquals(MdnsRecord.TYPE_KEY, keyRecord.getType());
+        assertTrue(keyRecord.getTtl() > 0); // Not a question so the TTL is greater than 0
+        assertTrue(keyRecord.getCacheFlush());
+        assertArrayEquals(new String[] {"test-host", "local"}, keyRecord.getName());
+        assertArrayEquals(rData, keyRecord.getRData());
+        assertNotEquals(rData, keyRecord.getRData()); // Uses a copy of the original RDATA
+        assertEquals(dataInText, toHex(keyRecord));
+
+        // MdnsKeyRecord(String[] name, MdnsPacketReader reader, boolean isQuestion)
+        reader = new MdnsPacketReader(packet);
+        reader.readLabels(); // Skip labels
+        reader.readUInt16(); // Skip type
+        keyRecord = new MdnsKeyRecord(name, reader, false /* isQuestion */);
+        assertEquals(MdnsRecord.TYPE_KEY, keyRecord.getType());
+        assertTrue(keyRecord.getTtl() > 0); // Not a question, so the TTL is greater than 0
+        assertTrue(keyRecord.getCacheFlush());
+        assertArrayEquals(new String[] {"test-host", "local"}, keyRecord.getName());
+        assertArrayEquals(rData, keyRecord.getRData());
+        assertNotEquals(rData, keyRecord.getRData()); // Uses a copy of the original RDATA
+
+        // MdnsKeyRecord(String[] name, boolean isUnicast)
+        keyRecord = new MdnsKeyRecord(name, false /* isUnicast */);
+        assertEquals(MdnsRecord.TYPE_KEY, keyRecord.getType());
+        assertEquals(0, keyRecord.getTtl());
+        assertEquals(QCLASS_INTERNET, keyRecord.getRecordClass());
+        assertFalse(keyRecord.getCacheFlush());
+        assertArrayEquals(new String[] {"test-host", "local"}, keyRecord.getName());
+        assertArrayEquals(null, keyRecord.getRData());
+
+        // MdnsKeyRecord(String[] name, long receiptTimeMillis, boolean cacheFlush, long ttlMillis,
+        // byte[] rData)
+        keyRecord =
+                new MdnsKeyRecord(
+                        name,
+                        10 /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        20_000 /* ttlMillis */,
+                        rData);
+        assertEquals(MdnsRecord.TYPE_KEY, keyRecord.getType());
+        assertEquals(10, keyRecord.getReceiptTime());
+        assertTrue(keyRecord.getCacheFlush());
+        assertEquals(20_000, keyRecord.getTtl());
+        assertEquals(QCLASS_INTERNET, keyRecord.getRecordClass());
+        assertArrayEquals(new String[] {"test-host", "local"}, keyRecord.getName());
+        assertArrayEquals(rData, keyRecord.getRData());
+        assertNotEquals(rData, keyRecord.getRData()); // Uses a copy of the original RDATA
+    }
 }