diff --git a/keystore/Android.bp b/keystore/Android.bp
index 37bc6a8..9bf6cf3 100644
--- a/keystore/Android.bp
+++ b/keystore/Android.bp
@@ -229,16 +229,25 @@
     defaults: ["keystore_defaults"],
 
     srcs: [
+        ":IKeyAttestationApplicationIdProvider.aidl",
         "auth_token_table.cpp",
+        "keystore_attestation_id.cpp",
+        "KeyAttestationApplicationId.cpp",
+        "KeyAttestationPackageInfo.cpp",
+        "Signature.cpp",
     ],
     cflags: [ "-O0", ],
     static_libs: ["libgtest_main"],
     shared_libs: [
         "android.hardware.keymaster@4.0",
+        "libbinder",
+        "libcrypto",
         "libhidlbase",
         "libhwbinder",
         "libkeymaster4support",
         "libutils",
+        "libkeystore_aidl",
+        "libkeystore_parcelables",
     ],
     export_shared_lib_headers: [
         "android.hardware.keymaster@4.0",
@@ -247,6 +256,9 @@
         "libkeymaster4support",
     ],
 
+    aidl: {
+        include_dirs: ["frameworks/base/core/java/"],
+    },
     export_include_dirs: ["include"],
 }
 
diff --git a/keystore/KeyAttestationApplicationId.cpp b/keystore/KeyAttestationApplicationId.cpp
index 4bc939d..c62571f 100644
--- a/keystore/KeyAttestationApplicationId.cpp
+++ b/keystore/KeyAttestationApplicationId.cpp
@@ -31,6 +31,9 @@
     packageInfos_->push_back(std::move(package));
 }
 
+KeyAttestationApplicationId::KeyAttestationApplicationId(PackageInfoVector packages)
+    : packageInfos_(std::make_shared<PackageInfoVector>(std::move(packages))) {}
+
 status_t KeyAttestationApplicationId::writeToParcel(Parcel* parcel) const {
     return parcel->writeParcelableVector(packageInfos_);
 }
diff --git a/keystore/Signature.cpp b/keystore/Signature.cpp
index 1566df9..284f358 100644
--- a/keystore/Signature.cpp
+++ b/keystore/Signature.cpp
@@ -31,6 +31,8 @@
     return parcel->readByteVector(&sig_data_);
 }
 
+Signature::Signature(std::vector<uint8_t> signature_data) : sig_data_(std::move(signature_data)) {}
+
 }  // namespace pm
 }  // namespace content
 }  // namespace android
diff --git a/keystore/include/keystore/KeyAttestationApplicationId.h b/keystore/include/keystore/KeyAttestationApplicationId.h
index c612929..dc914c1 100644
--- a/keystore/include/keystore/KeyAttestationApplicationId.h
+++ b/keystore/include/keystore/KeyAttestationApplicationId.h
@@ -30,8 +30,11 @@
   public:
     typedef SharedNullableIterator<const KeyAttestationPackageInfo, std::vector>
         ConstKeyAttestationPackageInfoIterator;
+    typedef std::vector<std::unique_ptr<KeyAttestationPackageInfo>> PackageInfoVector;
     KeyAttestationApplicationId();
+    // Following c'tors are for initializing instances containing test data.
     KeyAttestationApplicationId(std::unique_ptr<KeyAttestationPackageInfo> package);
+    KeyAttestationApplicationId(PackageInfoVector packages);
 
     status_t writeToParcel(Parcel*) const override;
     status_t readFromParcel(const Parcel* parcel) override;
diff --git a/keystore/include/keystore/Signature.h b/keystore/include/keystore/Signature.h
index 3c996bb..31ecdef 100644
--- a/keystore/include/keystore/Signature.h
+++ b/keystore/include/keystore/Signature.h
@@ -25,6 +25,10 @@
 
 class Signature : public Parcelable {
   public:
+    Signature() = default;
+    // Intended for initializing instances containing test data.
+    Signature(std::vector<uint8_t> signature_data);
+
     status_t writeToParcel(Parcel*) const override;
     status_t readFromParcel(const Parcel* parcel) override;
 
diff --git a/keystore/key_store_service.cpp b/keystore/key_store_service.cpp
index 035558f..072bade 100644
--- a/keystore/key_store_service.cpp
+++ b/keystore/key_store_service.cpp
@@ -107,7 +107,7 @@
     return {ResponseCode::NO_ERROR, true};
 }
 
-constexpr size_t KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE = 1024;
+using ::android::security::KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE;
 
 KeyStoreServiceReturnCode updateParamsForAttestation(uid_t callingUid, AuthorizationSet* params) {
     KeyStoreServiceReturnCode responseCode;
@@ -125,11 +125,14 @@
     std::vector<uint8_t>& asn1_attestation_id = asn1_attestation_id_result;
 
     /*
-     * The attestation application ID cannot be longer than
-     * KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE, so we truncate if too long.
+     * The attestation application ID must not be longer than
+     * KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE, error out if gather_attestation_application_id
+     * returned such an invalid vector.
      */
     if (asn1_attestation_id.size() > KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE) {
-        asn1_attestation_id.resize(KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE);
+        ALOGE("BUG: Gathered Attestation Application ID is too big (%d)",
+              static_cast<int32_t>(asn1_attestation_id.size()));
+        return ErrorCode::CANNOT_ATTEST_IDS;
     }
 
     params->push_back(TAG_ATTESTATION_APPLICATION_ID, asn1_attestation_id);
diff --git a/keystore/keystore_attestation_id.cpp b/keystore/keystore_attestation_id.cpp
index 3d34ac5..491efb7 100644
--- a/keystore/keystore_attestation_id.cpp
+++ b/keystore/keystore_attestation_id.cpp
@@ -47,6 +47,7 @@
 namespace {
 
 constexpr const char* kAttestationSystemPackageName = "AndroidSystem";
+constexpr const char* kUnknownPackageName = "UnknownPackage";
 
 std::vector<uint8_t> signature2SHA256(const content::pm::Signature& sig) {
     std::vector<uint8_t> digest_buffer(SHA256_DIGEST_LENGTH);
@@ -82,6 +83,10 @@
     ASN1_INTEGER* version;
 } KM_ATTESTATION_PACKAGE_INFO;
 
+// Estimated size:
+// 4 bytes for the package name + package_name length
+// 11 bytes for the version (2 bytes header and up to 9 bytes of data).
+constexpr size_t AAID_PKG_INFO_OVERHEAD = 15;
 ASN1_SEQUENCE(KM_ATTESTATION_PACKAGE_INFO) = {
     ASN1_SIMPLE(KM_ATTESTATION_PACKAGE_INFO, package_name, ASN1_OCTET_STRING),
     ASN1_SIMPLE(KM_ATTESTATION_PACKAGE_INFO, version, ASN1_INTEGER),
@@ -90,11 +95,21 @@
 
 DECLARE_STACK_OF(KM_ATTESTATION_PACKAGE_INFO);
 
+// Estimated size:
+// See estimate above for the stack of package infos.
+// 34 (32 + 2) bytes for each signature digest.
+constexpr size_t AAID_SIGNATURE_SIZE = 34;
 typedef struct km_attestation_application_id {
     STACK_OF(KM_ATTESTATION_PACKAGE_INFO) * package_infos;
     STACK_OF(ASN1_OCTET_STRING) * signature_digests;
 } KM_ATTESTATION_APPLICATION_ID;
 
+// Estimated overhead:
+// 4 for the header of the octet string containing the fully-encoded data.
+// 4 for the sequence header.
+// 4 for the header of the package info set.
+// 4 for the header of the signature set.
+constexpr size_t AAID_GENERAL_OVERHEAD = 16;
 ASN1_SEQUENCE(KM_ATTESTATION_APPLICATION_ID) = {
     ASN1_SET_OF(KM_ATTESTATION_APPLICATION_ID, package_infos, KM_ATTESTATION_PACKAGE_INFO),
     ASN1_SET_OF(KM_ATTESTATION_APPLICATION_ID, signature_digests, ASN1_OCTET_STRING),
@@ -165,10 +180,23 @@
     return retval;
 }
 
+/* The following function are not used. They are mentioned here to silence
+ * warnings about them not being used.
+ */
+void unused_functions_silencer() __attribute__((unused));
+void unused_functions_silencer() {
+    i2d_KM_ATTESTATION_PACKAGE_INFO(nullptr, nullptr);
+    d2i_KM_ATTESTATION_APPLICATION_ID(nullptr, nullptr, 0);
+    d2i_KM_ATTESTATION_PACKAGE_INFO(nullptr, nullptr, 0);
+}
+
+}  // namespace
+
 StatusOr<std::vector<uint8_t>>
 build_attestation_application_id(const KeyAttestationApplicationId& key_attestation_id) {
     auto attestation_id =
         std::unique_ptr<KM_ATTESTATION_APPLICATION_ID>(KM_ATTESTATION_APPLICATION_ID_new());
+    size_t estimated_encoded_size = AAID_GENERAL_OVERHEAD;
 
     auto attestation_pinfo_stack = reinterpret_cast<_STACK*>(attestation_id->package_infos);
 
@@ -187,6 +215,10 @@
             ALOGE("Building DER attestation package info failed %d", rc);
             return rc;
         }
+        estimated_encoded_size += AAID_PKG_INFO_OVERHEAD + package_name.size();
+        if (estimated_encoded_size > KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE) {
+            break;
+        }
         if (!sk_push(attestation_pinfo_stack, attestation_package_info.get())) {
             return NO_MEMORY;
         }
@@ -207,6 +239,10 @@
 
     auto signature_digest_stack = reinterpret_cast<_STACK*>(attestation_id->signature_digests);
     for (auto si : signature_digests) {
+        estimated_encoded_size += AAID_SIGNATURE_SIZE;
+        if (estimated_encoded_size > KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE) {
+            break;
+        }
         auto asn1_item = std::unique_ptr<ASN1_OCTET_STRING>(ASN1_OCTET_STRING_new());
         if (!asn1_item) return NO_MEMORY;
         if (!ASN1_OCTET_STRING_set(asn1_item.get(), si.data(), si.size())) {
@@ -229,18 +265,6 @@
     return result;
 }
 
-/* The following function are not used. They are mentioned here to silence
- * warnings about them not being used.
- */
-void unused_functions_silencer() __attribute__((unused));
-void unused_functions_silencer() {
-    i2d_KM_ATTESTATION_PACKAGE_INFO(nullptr, nullptr);
-    d2i_KM_ATTESTATION_APPLICATION_ID(nullptr, nullptr, 0);
-    d2i_KM_ATTESTATION_PACKAGE_INFO(nullptr, nullptr, 0);
-}
-
-}  // namespace
-
 StatusOr<std::vector<uint8_t>> gather_attestation_application_id(uid_t uid) {
     KeyAttestationApplicationId key_attestation_id;
 
@@ -254,10 +278,15 @@
         /* Get the attestation application ID from package manager */
         auto& pm = KeyAttestationApplicationIdProvider::get();
         auto status = pm.getKeyAttestationApplicationId(uid, &key_attestation_id);
+        // Package Manager call has failed, perform attestation but indicate that the
+        // caller is unknown.
         if (!status.isOk()) {
-            ALOGE("package manager request for key attestation ID failed with: %s %d",
+            ALOGW("package manager request for key attestation ID failed with: %s %d",
                   status.exceptionMessage().string(), status.exceptionCode());
-            return FAILED_TRANSACTION;
+            auto pinfo = std::make_unique<KeyAttestationPackageInfo>(
+                String16(kUnknownPackageName), 1 /* version code */,
+                std::make_shared<KeyAttestationPackageInfo::SignaturesVector>());
+            key_attestation_id = KeyAttestationApplicationId(std::move(pinfo));
         }
     }
 
diff --git a/keystore/keystore_attestation_id.h b/keystore/keystore_attestation_id.h
index 8d20550..f45d5be 100644
--- a/keystore/keystore_attestation_id.h
+++ b/keystore/keystore_attestation_id.h
@@ -23,6 +23,14 @@
 namespace android {
 namespace security {
 
+constexpr size_t KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE = 1024;
+
+namespace keymaster {
+
+class KeyAttestationApplicationId;
+
+}  // namespace keymaster
+
 template <typename T> class StatusOr {
   public:
     StatusOr(const status_t error) : _status(error), _value() {}
@@ -57,6 +65,14 @@
  */
 StatusOr<std::vector<uint8_t>> gather_attestation_application_id(uid_t uid);
 
+/**
+ * Generates a DER-encoded vector containing information from KeyAttestationApplicationId.
+ * The size of the returned vector will not exceed KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE.
+ */
+
+StatusOr<std::vector<uint8_t>> build_attestation_application_id(
+    const ::android::security::keymaster::KeyAttestationApplicationId& key_attestation_id);
+
 }  // namespace security
 }  // namespace android
 #endif  // KEYSTORE_KEYSTORE_ATTESTATION_ID_H_
diff --git a/keystore/tests/Android.bp b/keystore/tests/Android.bp
index 73459c1..103fa0e 100644
--- a/keystore/tests/Android.bp
+++ b/keystore/tests/Android.bp
@@ -8,6 +8,7 @@
         "-O0",
     ],
     srcs: [
+        "aaid_truncation_test.cpp",
         "auth_token_table_test.cpp",
         "auth_token_formatting_test.cpp",
         "confirmationui_rate_limiting_test.cpp",
@@ -17,13 +18,20 @@
     static_libs: [
         "android.hardware.confirmationui@1.0",
         "libbase",
+        "libcrypto",
+        "libcutils",
         "libgtest_main",
         "libhidlbase",
         "libkeymaster4support",
         "libkeystore_test",
         "liblog",
+        "libutils",
+        "libvndksupport",
     ],
-    shared_libs: ["libkeymaster_messages"],
+    shared_libs: [
+        "libbinder",
+        "libkeymaster_messages",
+    ],
    sanitize: {
      cfi: false,
    }
diff --git a/keystore/tests/aaid_truncation_test.cpp b/keystore/tests/aaid_truncation_test.cpp
new file mode 100644
index 0000000..e5d5e9f
--- /dev/null
+++ b/keystore/tests/aaid_truncation_test.cpp
@@ -0,0 +1,148 @@
+/*
+ * Copyright (C) 2018 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.
+ */
+
+#include <gtest/gtest.h>
+
+#include <string>
+#include <utils/String16.h>
+
+#include "../keystore_attestation_id.h"
+#include <keymaster/logger.h>
+
+#include <keystore/KeyAttestationApplicationId.h>
+#include <keystore/KeyAttestationPackageInfo.h>
+#include <keystore/Signature.h>
+
+using ::android::String16;
+using ::android::security::KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE;
+using ::android::security::keymaster::KeyAttestationApplicationId;
+using ::android::security::keymaster::KeyAttestationPackageInfo;
+using std::vector;
+
+namespace keystore {
+
+namespace test {
+
+namespace {
+
+constexpr const char* kDummyPackageName = "DummyPackage";
+
+constexpr const char* kLongPackageName =
+    "a.long.package.name"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
+
+constexpr const char* kReasonablePackageName =
+    "a.reasonable.length.package.name"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
+    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
+
+constexpr const size_t kTooManyPackages = 4;
+
+// Signatures should be 32 bytes
+constexpr const uint8_t kDummySignature[32] = {
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f};
+constexpr const size_t kTooManySignatures = 35;
+
+}  // namespace
+
+using ::android::content::pm::Signature;
+using ::android::security::build_attestation_application_id;
+
+std::unique_ptr<KeyAttestationPackageInfo>
+make_package_info_with_signatures(const char* package_name,
+                                  KeyAttestationPackageInfo::SignaturesVector signatures) {
+    return std::make_unique<KeyAttestationPackageInfo>(
+        String16(package_name), 1 /* version code */,
+        std::make_shared<KeyAttestationPackageInfo::SignaturesVector>(std::move(signatures)));
+}
+
+std::unique_ptr<KeyAttestationPackageInfo> make_package_info(const char* package_name) {
+    return make_package_info_with_signatures(package_name,
+                                             KeyAttestationPackageInfo::SignaturesVector());
+}
+
+TEST(AaidTruncationTest, shortPackageInfoTest) {
+    KeyAttestationApplicationId app_id(make_package_info(kDummyPackageName));
+
+    auto result = build_attestation_application_id(app_id);
+    ASSERT_TRUE(result.isOk());
+    std::vector<uint8_t>& encoded_app_id = result;
+    ASSERT_LT(encoded_app_id.size(), KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE);
+}
+
+TEST(AaidTruncationTest, tooLongPackageNameTest) {
+    KeyAttestationApplicationId app_id(make_package_info(kLongPackageName));
+
+    auto result = build_attestation_application_id(app_id);
+    ASSERT_TRUE(result.isOk());
+    std::vector<uint8_t>& encoded_app_id = result;
+    ASSERT_LT(encoded_app_id.size(), KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE);
+}
+
+TEST(AaidTruncationTest, tooManySignaturesTest) {
+    std::vector<uint8_t> dummy_sig_data(kDummySignature, kDummySignature + 32);
+    KeyAttestationPackageInfo::SignaturesVector signatures;
+    // Add 35 signatures which will surely exceed the 1K limit.
+    for (size_t i = 0; i < kTooManySignatures; ++i) {
+        signatures.push_back(std::make_unique<Signature>(dummy_sig_data));
+    }
+
+    KeyAttestationApplicationId app_id(
+        make_package_info_with_signatures(kDummyPackageName, std::move(signatures)));
+
+    auto result = build_attestation_application_id(app_id);
+    ASSERT_TRUE(result.isOk());
+    std::vector<uint8_t>& encoded_app_id = result;
+    ASSERT_LT(encoded_app_id.size(), KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE);
+}
+
+TEST(AaidTruncationTest, combinedPackagesAndSignaturesTest) {
+    std::vector<uint8_t> dummy_sig_data(kDummySignature, kDummySignature + 32);
+    KeyAttestationApplicationId::PackageInfoVector packages;
+
+    for (size_t i = 0; i < kTooManyPackages; ++i) {
+        KeyAttestationPackageInfo::SignaturesVector signatures;
+        // Add a few signatures for each package
+        for (int j = 0; j < 3; ++j) {
+            signatures.push_back(std::make_unique<Signature>(dummy_sig_data));
+        }
+        packages.push_back(
+            make_package_info_with_signatures(kReasonablePackageName, std::move(signatures)));
+    }
+
+    KeyAttestationApplicationId app_id(std::move(packages));
+    auto result = build_attestation_application_id(app_id);
+    ASSERT_TRUE(result.isOk());
+    std::vector<uint8_t>& encoded_app_id = result;
+    ASSERT_LT(encoded_app_id.size(), KEY_ATTESTATION_APPLICATION_ID_MAX_SIZE);
+}
+
+}  // namespace test
+}  // namespace keystore