package app.attestation.server;

import app.attestation.server.attestation.AttestationApplicationId;
import app.attestation.server.attestation.AttestationApplicationId.AttestationPackageInfo;
import app.attestation.server.attestation.AuthorizationList;
import app.attestation.server.attestation.ParsedAttestationRecord;
import app.attestation.server.attestation.RootOfTrust;
import com.almworks.sqlite4java.SQLiteConnection;
import com.almworks.sqlite4java.SQLiteException;
import com.almworks.sqlite4java.SQLiteStatement;
import com.github.benmanes.caffeine.cache.Cache;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import com.google.common.io.BaseEncoding;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.nio.ByteBuffer;
import java.security.GeneralSecurityException;
import java.security.PublicKey;
import java.security.SecureRandom;
import java.security.Signature;
import java.security.cert.Certificate;
import java.security.cert.CertificateEncodingException;
import java.security.cert.CertificateException;
import java.security.cert.CertificateFactory;
import java.security.cert.X509Certificate;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.List;
import java.util.logging.Logger;
import java.util.zip.DataFormatException;
import java.util.zip.Deflater;
import java.util.zip.DeflaterOutputStream;
import java.util.zip.Inflater;

class AttestationProtocol {
    private static final Logger logger = Logger.getLogger(AttestationProtocol.class.getName());

    static final int RANDOM_TOKEN_LENGTH = 32;
    private static final String SIGNATURE_ALGORITHM = "SHA256WithECDSA";
    private static final HashFunction FINGERPRINT_HASH_FUNCTION = Hashing.sha256();
    private static final int FINGERPRINT_LENGTH = FINGERPRINT_HASH_FUNCTION.bits() / 8;

    // Challenge message:
    //
    // byte maxVersion = PROTOCOL_VERSION
    // byte[] challenge index (length: RANDOM_TOKEN_LENGTH)
    // byte[] challenge (length: RANDOM_TOKEN_LENGTH)
    //
    // The challenge index is randomly generated by Auditor and used for all future challenge
    // messages from that Auditor. It's used on the Auditee as an index to choose the correct
    // persistent key to satisfy the Auditor, rather than only supporting pairing with one. In
    // theory, the Auditor could authenticate to the Auditee, but this app already provides a
    // better way to do that by doing the same process in reverse for a supported device.
    //
    // The challenge is randomly generated by the Auditor and serves the security function of
    // enforcing that the results are fresh. It's returned inside the attestation certificate
    // which has a signature from the device's provisioned key (not usable by the OS) and the
    // outer signature from the hardware-backed key generated for the initial pairing.
    //
    // Attestation message:
    //
    // For backwards compatibility the Auditor device sends its maximum supported version, and
    // the Auditee uses the highest version it supports.
    //
    // Compression is done with raw DEFLATE (no zlib wrapper) with a preset dictionary generated from
    // sample certificates.
    //
    // signed message {
    // byte version = min(maxVersion, PROTOCOL_VERSION)
    // short compressedChainLength
    // byte[] compressedChain { [short encodedCertificateLength, byte[] encodedCertificate] }
    // byte[] fingerprint (length: FINGERPRINT_LENGTH)
    // int osEnforcedFlags
    // int autoRebootSeconds (-1 for unknown)
    // byte portSecurityMode (-1 for unknown)
    // byte userCount (-1 for unknown)
    // byte oemUnlockAllowed (-1 for unknown)
    // }
    // byte[] signature (rest of message)
    //
    // Protocol version changes:
    //
    // 6: autoRebootSeconds added
    // 6: portSecurityMode added
    // 6: userCount added
    // 6: oemUnlockAllowed added
    // 7: new DEFLATE dictionary with new ECDSA root included
    //
    // n/a
    //
    // For each audit, the Auditee generates a fresh hardware-backed key with key attestation
    // using the provided challenge. It reports back the certificate chain to be verified by the
    // Auditor. The public key certificate of the generated key is signed by a key provisioned on
    // the device (not usable by the OS) chaining up to an intermediate and the Google root. The
    // certificate contains the key attestation metadata including the important fields with the
    // lock state, verified boot state, the verified boot public key fingerprint and the OS
    // version / patch level:
    //
    // https://developer.android.com/training/articles/security-key-attestation.html#certificate_schema
    //
    // The Auditee keeps the first hardware-backed key generated for a challenge index and uses it
    // to sign all future attestations. The fingerprint of the persistent key is included in the
    // attestation message for the Auditor to find the corresponding pinning data. Other keys are
    // never actually used, only generated for fresh key attestation data.
    //
    // The OS can use the persistent generated hardware-backed key for signing but cannot obtain
    // the private key. The key isn't be usable if verified boot fails or the OS is downgraded and
    // the keys are protected against replay attacks via the Replay Protected Memory Block.
    // Devices launching with Android P or later can provide a StrongBox Keymaster to support
    // storing the keys in a dedicated hardware security module to substantially reduce the attack
    // surface for obtaining the keys. StrongBox is paired with the TEE and the TEE corroborates
    // the validity of the keys and attestation. The Pixel 3 and 3 XL are the first devices with a
    // StrongBox implementation via the Titan M security chip.
    //
    // https://android-developers.googleblog.com/2018/10/building-titan-better-security-through.html
    //
    // The attestation message also includes osEnforcedFlags with data obtained at the OS level,
    // which is vulnerable to tampering by an attacker with control over the OS. However, the OS
    // did get verified by verified boot so without a verified boot bypass they would need to keep
    // exploiting it after booting. The bootloader / TEE verified OS version / OS patch level are
    // a useful mitigation as they reveal that the OS isn't upgraded even if an attacker has root.
    //
    // The Auditor saves the initial certificate chain, using the initial certificate to verify
    // the outer signature and the rest of the chain for pinning the expected chain. It enforces
    // downgrade protection for the OS version/patch (bootloader/TEE enforced) and app version (OS
    // enforced) by keeping them updated.
    static final byte PROTOCOL_VERSION = 7;
    private static final byte PROTOCOL_VERSION_MINIMUM = 5;
    // can become longer in the future, but this is the minimum length
    private static final byte CHALLENGE_MESSAGE_LENGTH = 1 + RANDOM_TOKEN_LENGTH * 2;
    private static final int MAX_ENCODED_CHAIN_LENGTH = 5000;
    static final int MAX_MESSAGE_SIZE = 2953;

    private static final int OS_ENFORCED_FLAGS_NONE = 0;
    private static final int OS_ENFORCED_FLAGS_USER_PROFILE_SECURE = 1;
    private static final int OS_ENFORCED_FLAGS_ACCESSIBILITY = 1 << 1;
    private static final int OS_ENFORCED_FLAGS_DEVICE_ADMIN = 1 << 2;
    private static final int OS_ENFORCED_FLAGS_ADB_ENABLED = 1 << 3;
    private static final int OS_ENFORCED_FLAGS_ADD_USERS_WHEN_LOCKED = 1 << 4;
    private static final int OS_ENFORCED_FLAGS_ENROLLED_BIOMETRICS = 1 << 5;
    private static final int OS_ENFORCED_FLAGS_DENY_NEW_USB = 1 << 6; // obsolete since version 86
    private static final int OS_ENFORCED_FLAGS_DEVICE_ADMIN_NON_SYSTEM = 1 << 7;
    private static final int OS_ENFORCED_FLAGS_OEM_UNLOCK_ALLOWED = 1 << 8; // obsolete since version 89
    private static final int OS_ENFORCED_FLAGS_SYSTEM_USER = 1 << 9;
    private static final int OS_ENFORCED_FLAGS_ALL =
            OS_ENFORCED_FLAGS_USER_PROFILE_SECURE |
            OS_ENFORCED_FLAGS_ACCESSIBILITY |
            OS_ENFORCED_FLAGS_DEVICE_ADMIN |
            OS_ENFORCED_FLAGS_ADB_ENABLED |
            OS_ENFORCED_FLAGS_ADD_USERS_WHEN_LOCKED |
            OS_ENFORCED_FLAGS_ENROLLED_BIOMETRICS |
            OS_ENFORCED_FLAGS_DENY_NEW_USB |
            OS_ENFORCED_FLAGS_DEVICE_ADMIN_NON_SYSTEM |
            OS_ENFORCED_FLAGS_OEM_UNLOCK_ALLOWED |
            OS_ENFORCED_FLAGS_SYSTEM_USER;

    private static final String AUDITOR_APP_PACKAGE_NAME_RELEASE = "app.attestation.auditor";
    private static final String AUDITOR_APP_PACKAGE_NAME_PLAY = "app.attestation.auditor.play";
    private static final String AUDITOR_APP_PACKAGE_NAME_DEBUG = "app.attestation.auditor.debug";
    private static final String AUDITOR_APP_SIGNATURE_DIGEST_RELEASE =
            "990E04F0864B19F14F84E0E432F7A393F297AB105A22C1E1B10B442A4A62C42C";
    private static final String AUDITOR_APP_SIGNATURE_DIGEST_PLAY =
            "075335BD7B54C965222B5284D2A1FDEF1198AE45EC7B09A4934287A0E3A243C7";
    private static final String AUDITOR_APP_SIGNATURE_DIGEST_DEBUG =
            "17727D8B61D55A864936B1A7B4A2554A15151F32EBCF44CDAA6E6C3258231890";
    private static final byte AUDITOR_APP_VARIANT_RELEASE = 0;
    private static final byte AUDITOR_APP_VARIANT_PLAY = 1;
    private static final byte AUDITOR_APP_VARIANT_DEBUG = 2;

    private static final int AUDITOR_APP_MINIMUM_VERSION = 87;
    private static final int OS_VERSION_MINIMUM = 130000;
    private static final int OS_PATCH_LEVEL_MINIMUM = 202208;
    private static final int VENDOR_PATCH_LEVEL_MINIMUM = 20220805;
    private static final int BOOT_PATCH_LEVEL_MINIMUM = 20220805;

    private static final String DEVICE_PIXEL_4_GENERIC = "Google Pixel 4 / Pixel 4 XL";
    private static final String DEVICE_PIXEL_4 = "Google Pixel 4";
    private static final String DEVICE_PIXEL_4_XL = "Google Pixel 4 XL";
    private static final String DEVICE_PIXEL_4A = "Google Pixel 4a";
    private static final String DEVICE_PIXEL_4A_5G = "Google Pixel 4a (5G)";
    private static final String DEVICE_PIXEL_5 = "Google Pixel 5";
    private static final String DEVICE_PIXEL_5_GENERIC = "Google Pixel 4a (5G) / Pixel 5";
    private static final String DEVICE_PIXEL_5A = "Google Pixel 5a";
    private static final String DEVICE_PIXEL_6 = "Google Pixel 6";
    private static final String DEVICE_PIXEL_6_PRO = "Google Pixel 6 Pro";
    private static final String DEVICE_PIXEL_6A = "Google Pixel 6a";
    private static final String DEVICE_PIXEL_7 = "Google Pixel 7";
    private static final String DEVICE_PIXEL_7_PRO = "Google Pixel 7 Pro";
    private static final String DEVICE_PIXEL_7A = "Google Pixel 7a";
    private static final String DEVICE_PIXEL_TABLET = "Google Pixel Tablet";
    private static final String DEVICE_PIXEL_FOLD = "Google Pixel Fold";
    private static final String DEVICE_PIXEL_8 = "Google Pixel 8";
    private static final String DEVICE_PIXEL_8_PRO = "Google Pixel 8 Pro";
    private static final String DEVICE_PIXEL_8A = "Google Pixel 8a";
    private static final String DEVICE_PIXEL_9 = "Google Pixel 9";
    private static final String DEVICE_PIXEL_9_PRO = "Google Pixel 9 Pro";
    private static final String DEVICE_PIXEL_9_PRO_XL = "Google Pixel 9 Pro XL";
    private static final String DEVICE_PIXEL_9_PRO_FOLD = "Google Pixel 9 Pro Fold";
    private static final String DEVICE_PIXEL_9A = "Google Pixel 9a";
    private static final String DEVICE_PIXEL_10 = "Google Pixel 10";
    private static final String DEVICE_PIXEL_10_PRO = "Google Pixel 10 Pro";
    private static final String DEVICE_PIXEL_10_PRO_XL = "Google Pixel 10 Pro XL";
    private static final String DEVICE_PIXEL_10_PRO_FOLD = "Google Pixel 10 Pro Fold";

    private static final String OS_STOCK = "Stock";
    private static final String OS_GRAPHENE = "GrapheneOS";

    public record DeviceInfo(String name, int attestationVersion, int keymasterVersion,
            // API for detecting this was replaced in keymaster v3 but the new one isn't used yet
            boolean rollbackResistant,
            String osName) {

        boolean hasPogoPins() {
            return DEVICE_PIXEL_TABLET.equals(name);
        }
    }

    static final ImmutableMap<String, DeviceInfo> fingerprintsNonStock = ImmutableMap
            .<String, DeviceInfo>builder()
            // GrapheneOS
            .put("80EF268700EE42686F779A47B4A155FE1FFC2EEDF836B4803CAAB8FA61439746",
                    new DeviceInfo(DEVICE_PIXEL_4, 3, 4, false, OS_GRAPHENE))
            .put("3F15FDCB82847FED97427CE00563B8F9FF34627070DE5FDB17ACA7849AB98CC8",
                    new DeviceInfo(DEVICE_PIXEL_4_XL, 3, 4, false, OS_GRAPHENE))
            .put("9F2454A1657B1B5AD7F2336B39A2611F7A40B2E0DDFD0D6553A359605928DF29",
                    new DeviceInfo(DEVICE_PIXEL_4A, 3, 4, false, OS_GRAPHENE))
            .put("DCEC2D053D3EC4F1C9BE414AA07E4D7D7CBD12040AD2F8831C994A83A0536866",
                    new DeviceInfo(DEVICE_PIXEL_4A_5G, 3, 4, false, OS_GRAPHENE))
            .put("36A99EAB7907E4FB12A70E3C41C456BCBE46C13413FBFE2436ADEE2B2B61120F",
                    new DeviceInfo(DEVICE_PIXEL_5, 3, 4, false, OS_GRAPHENE))
            .put("0ABDDEDA03B6CE10548C95E0BEA196FAA539866F929BCDF7ECA84B4203952514",
                    new DeviceInfo(DEVICE_PIXEL_5A, 3, 4, false, OS_GRAPHENE))
            .put("F0A890375D1405E62EBFD87E8D3F475F948EF031BBF9DDD516D5F600A23677E8",
                    new DeviceInfo(DEVICE_PIXEL_6, 100, 100, false, OS_GRAPHENE))
            .put("439B76524D94C40652CE1BF0D8243773C634D2F99BA3160D8D02AA5E29FF925C",
                    new DeviceInfo(DEVICE_PIXEL_6_PRO, 100, 100, false, OS_GRAPHENE))
            .put("08C860350A9600692D10C8512F7B8E80707757468E8FBFEEA2A870C0A83D6031",
                    new DeviceInfo(DEVICE_PIXEL_6A, 100, 100, false, OS_GRAPHENE))
            .put("3EFE5392BE3AC38AFB894D13DE639E521675E62571A8A9B3EF9FC8C44FD17FA1",
                    new DeviceInfo(DEVICE_PIXEL_7, 200, 200, false, OS_GRAPHENE))
            .put("BC1C0DD95664604382BB888412026422742EB333071EA0B2D19036217D49182F",
                    new DeviceInfo(DEVICE_PIXEL_7_PRO, 200, 200, false, OS_GRAPHENE))
            .put("508D75DEA10C5CBC3E7632260FC0B59F6055A8A49DD84E693B6D8899EDBB01E4",
                    new DeviceInfo(DEVICE_PIXEL_7A, 200, 200, false, OS_GRAPHENE))
            .put("94DF136E6C6AA08DC26580AF46F36419B5F9BAF46039DB076F5295B91AAFF230",
                    new DeviceInfo(DEVICE_PIXEL_TABLET, 200, 200, false, OS_GRAPHENE))
            .put("EE0C9DFEF6F55A878538B0DBF7E78E3BC3F1A13C8C44839B095FE26DD5FE2842",
                    new DeviceInfo(DEVICE_PIXEL_FOLD, 200, 200, false, OS_GRAPHENE))
            .put("CD7479653AA88208F9F03034810EF9B7B0AF8A9D41E2000E458AC403A2ACB233",
                    new DeviceInfo(DEVICE_PIXEL_8, 300, 300, false, OS_GRAPHENE))
            .put("896DB2D09D84E1D6BB747002B8A114950B946E5825772A9D48BA7EB01D118C1C",
                    new DeviceInfo(DEVICE_PIXEL_8_PRO, 300, 300, false, OS_GRAPHENE))
            .put("096B8BD6D44527A24AC1564B308839F67E78202185CBFF9CFDCB10E63250BC5E",
                    new DeviceInfo(DEVICE_PIXEL_8A, 300, 300, false, OS_GRAPHENE))
            .put("9E6A8F3E0D761A780179F93ACD5721BA1AB7C8C537C7761073C0A754B0E932DE",
                    new DeviceInfo(DEVICE_PIXEL_9, 300, 300, false, OS_GRAPHENE))
            .put("F729CAB861DA1B83FDFAB402FC9480758F2AE78EE0B61C1F2137DD1AB7076E86",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO, 300, 300, false, OS_GRAPHENE))
            .put("55D3C2323DB91BB91F20D38D015E85112D038F6B6B5738FE352C1A80DBA57023",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_XL, 300, 300, false, OS_GRAPHENE))
            .put("AF4D2C6E62BE0FEC54F0271B9776FF061DD8392D9F51CF6AB1551D346679E24C",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_FOLD, 300, 300, false, OS_GRAPHENE))
            .put("0508DE44EE00BFB49ECE32C418AF1896391ABDE0F05B64F41BC9A2DFB589445B",
                    new DeviceInfo(DEVICE_PIXEL_9A, 300, 300, false, OS_GRAPHENE))
            .put("3F7415EA26F5DF5B14EA6D153256071A7A1AF9CE7B0970B7311CC463C7EA02C7",
                    new DeviceInfo(DEVICE_PIXEL_10, 300, 300, false, OS_GRAPHENE))
            .put("4E8EE8F717754052198CA6D2D3AAA232E2461B4293C0D6F297E519CC778DE093",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO, 300, 300, false, OS_GRAPHENE))
            .put("141D7FC32AF7958A416F2661B37CF6F27BFB376FB5CE616AEAA27A82C7A04F74",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_XL, 300, 300, false, OS_GRAPHENE))
            .put("55A2D44103E56D5EC65496399C417987BA77730E6488FC60BA058D09FC3CAEE3",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_FOLD, 300, 300, false, OS_GRAPHENE))
            .build();
    static final ImmutableMap<String, DeviceInfo> fingerprintsStock = ImmutableMap
            .<String, DeviceInfo>builder()
            .put("AE6316B4753C61F5855B95B9B98484AF784F2E83648D0FCC8107FCA752CAEA34",
                    new DeviceInfo(DEVICE_PIXEL_4_GENERIC, 3, 4, false, OS_STOCK))
            .put("879CD3F18EA76E244D4D4AC3BCB9C337C13B4667190B19035AFE2536550050F1",
                    new DeviceInfo(DEVICE_PIXEL_4A, 3, 4, false, OS_STOCK))
            .put("88265D85BA9E1E2F6036A259D880D2741031ACA445840137395B6D541C0FC7FC",
                    new DeviceInfo(DEVICE_PIXEL_5_GENERIC, 3, 4, false, OS_STOCK))
            .put("1DD694CE00BF131AD61CEB576B7DCC41CF7F9B2C418F4C12B2B8F3E9A1EA911D",
                    new DeviceInfo(DEVICE_PIXEL_5A, 3, 4, false, OS_STOCK))
            .put("0F6E75C80183B5DEC074B0054D4271E99389EBE4B136B0819DE1F150BA0FF9D7",
                    new DeviceInfo(DEVICE_PIXEL_6, 100, 100, false, OS_STOCK))
            .put("42ED1BCA352FABD428F34E8FCEE62776F4CB2C66E06F82E5A59FF4495267BFC2",
                    new DeviceInfo(DEVICE_PIXEL_6_PRO, 100, 100, false, OS_STOCK))
            .put("9AC4174153D45E4545B0F49E22FE63273999B6AC1CB6949C3A9F03EC8807EEE9",
                    new DeviceInfo(DEVICE_PIXEL_6A, 100, 100, false, OS_STOCK))
            .put("8B2C4CD539F5075E8E7CF212ADB3DB0413FBD77D321199C73D5A473C51F2E10D",
                    new DeviceInfo(DEVICE_PIXEL_7, 200, 200, false, OS_STOCK))
            .put("26AC4C60BEB1E378357CAD0C3061347AF8DF6FBABBB0D8CEA2445855EE01E368",
                    new DeviceInfo(DEVICE_PIXEL_7_PRO, 200, 200, false, OS_STOCK))
            .put("003F1ADE9D476E612B00F2983E6AD7DCD15E6A80CC2DBB008DA7D6839ED73A8F",
                    new DeviceInfo(DEVICE_PIXEL_7A, 200, 200, false, OS_STOCK))
            .put("C72E569827EC2E19A1073D927E3B6A1C6C8322DA795D5CE44BF3B95031B37C0A",
                    new DeviceInfo(DEVICE_PIXEL_TABLET, 200, 200, false, OS_STOCK))
            .put("3BBD4712D8714812E762D3FB6D2D5724800C3342B1835CDBC1D3634AE59D646E",
                    new DeviceInfo(DEVICE_PIXEL_FOLD, 200, 200, false, OS_STOCK))
            .put("64DEF0828FF5D3EAC65C3F5CEF46C1D855FE0A5D8525E90FB94FC3DBA9988C87",
                    new DeviceInfo(DEVICE_PIXEL_8, 300, 300, false, OS_STOCK))
            .put("E5362DDF4676E8AA134DB520749BCB1F44FE6556F5E7BFAB130CB6343476FC15",
                    new DeviceInfo(DEVICE_PIXEL_8_PRO, 300, 300, false, OS_STOCK))
            .put("9DE25FB02BB5530D44149D148437C82E267E557322530AA6F03B0AC2E92931DA",
                    new DeviceInfo(DEVICE_PIXEL_8A, 300, 300, false, OS_STOCK))
            .put("ACB5A4DD184E2C44CFA6A53D2D5C5E8674C9498A59F8AE8019942AC1FCEB1E6C",
                    new DeviceInfo(DEVICE_PIXEL_9, 300, 300, false, OS_STOCK))
            .put("06035F636BDB7F299A94B51C7D5645A913551327FFC5452B00C5830476D3208E",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO, 300, 300, false, OS_STOCK))
            .put("D05975CFD778082E3D1623C91419F6D8634E579A786592118CCEA057537579B7",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_XL, 300, 300, false, OS_STOCK))
            .put("800E9093D29614F5BC3FC76A0E819BA0A5C0C94A7D6A17C53E7D017D346B7172",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_FOLD, 300, 300, false, OS_STOCK))
            .put("3327AF62D84AB897AF2523A16DCB5801E60C5D5B97F41CA1BD099C4784F7B743",
                    new DeviceInfo(DEVICE_PIXEL_9A, 300, 300, false, OS_STOCK))
            .put("757C626A2A91FE852536546048D7CA3F50DF6C745C026DB9FF89CC4703C59481",
                    new DeviceInfo(DEVICE_PIXEL_10, 300, 300, false, OS_STOCK))
            .put("244BAAF78D0FEE555A562FDD3F70EF61036492FBA7AD192B83BB8D427E380B17",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO, 300, 300, false, OS_STOCK))
            .put("CA5C81DA02B8DEBB054FC625135A7833698A9B32148E8A2EF619EBC62AB2E3D8",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_XL, 300, 300, false, OS_STOCK))
            .put("072D8E3269350849F3DE787AC7A319F264C34FA326A7E70917FD96AAEFD2FB0E",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_FOLD, 300, 300, false, OS_STOCK))
            .build();

    static final ImmutableMap<String, DeviceInfo> fingerprintsStrongBoxNonStock = ImmutableMap
            .<String, DeviceInfo>builder()
            // GrapheneOS
            .put("80EF268700EE42686F779A47B4A155FE1FFC2EEDF836B4803CAAB8FA61439746",
                    new DeviceInfo(DEVICE_PIXEL_4, 3, 4, false, OS_GRAPHENE))
            .put("3F15FDCB82847FED97427CE00563B8F9FF34627070DE5FDB17ACA7849AB98CC8",
                    new DeviceInfo(DEVICE_PIXEL_4_XL, 3, 4, false, OS_GRAPHENE))
            .put("9F2454A1657B1B5AD7F2336B39A2611F7A40B2E0DDFD0D6553A359605928DF29",
                    new DeviceInfo(DEVICE_PIXEL_4A, 3, 4, false, OS_GRAPHENE))
            .put("DCEC2D053D3EC4F1C9BE414AA07E4D7D7CBD12040AD2F8831C994A83A0536866",
                    new DeviceInfo(DEVICE_PIXEL_4A_5G, 4, 41, false, OS_GRAPHENE))
            .put("36A99EAB7907E4FB12A70E3C41C456BCBE46C13413FBFE2436ADEE2B2B61120F",
                    new DeviceInfo(DEVICE_PIXEL_5, 4, 41, false, OS_GRAPHENE))
            .put("0ABDDEDA03B6CE10548C95E0BEA196FAA539866F929BCDF7ECA84B4203952514",
                    new DeviceInfo(DEVICE_PIXEL_5A, 4, 41, false, OS_GRAPHENE))
            .put("F0A890375D1405E62EBFD87E8D3F475F948EF031BBF9DDD516D5F600A23677E8",
                    new DeviceInfo(DEVICE_PIXEL_6, 100, 100, false, OS_GRAPHENE))
            .put("439B76524D94C40652CE1BF0D8243773C634D2F99BA3160D8D02AA5E29FF925C",
                    new DeviceInfo(DEVICE_PIXEL_6_PRO, 100, 100, false, OS_GRAPHENE))
            .put("08C860350A9600692D10C8512F7B8E80707757468E8FBFEEA2A870C0A83D6031",
                    new DeviceInfo(DEVICE_PIXEL_6A, 100, 100, false, OS_GRAPHENE))
            .put("3EFE5392BE3AC38AFB894D13DE639E521675E62571A8A9B3EF9FC8C44FD17FA1",
                    new DeviceInfo(DEVICE_PIXEL_7, 100, 100, false, OS_GRAPHENE))
            .put("BC1C0DD95664604382BB888412026422742EB333071EA0B2D19036217D49182F",
                    new DeviceInfo(DEVICE_PIXEL_7_PRO, 100, 100, false, OS_GRAPHENE))
            .put("508D75DEA10C5CBC3E7632260FC0B59F6055A8A49DD84E693B6D8899EDBB01E4",
                    new DeviceInfo(DEVICE_PIXEL_7A, 100, 100, false, OS_GRAPHENE))
            .put("94DF136E6C6AA08DC26580AF46F36419B5F9BAF46039DB076F5295B91AAFF230",
                    new DeviceInfo(DEVICE_PIXEL_TABLET, 100, 100, false, OS_GRAPHENE))
            .put("EE0C9DFEF6F55A878538B0DBF7E78E3BC3F1A13C8C44839B095FE26DD5FE2842",
                    new DeviceInfo(DEVICE_PIXEL_FOLD, 100, 100, false, OS_GRAPHENE))
            .put("CD7479653AA88208F9F03034810EF9B7B0AF8A9D41E2000E458AC403A2ACB233",
                    new DeviceInfo(DEVICE_PIXEL_8, 300, 300, false, OS_GRAPHENE))
            .put("896DB2D09D84E1D6BB747002B8A114950B946E5825772A9D48BA7EB01D118C1C",
                    new DeviceInfo(DEVICE_PIXEL_8_PRO, 300, 300, false, OS_GRAPHENE))
            .put("096B8BD6D44527A24AC1564B308839F67E78202185CBFF9CFDCB10E63250BC5E",
                    new DeviceInfo(DEVICE_PIXEL_8A, 300, 300, false, OS_GRAPHENE))
            .put("9E6A8F3E0D761A780179F93ACD5721BA1AB7C8C537C7761073C0A754B0E932DE",
                    new DeviceInfo(DEVICE_PIXEL_9, 300, 300, false, OS_GRAPHENE))
            .put("F729CAB861DA1B83FDFAB402FC9480758F2AE78EE0B61C1F2137DD1AB7076E86",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO, 300, 300, false, OS_GRAPHENE))
            .put("55D3C2323DB91BB91F20D38D015E85112D038F6B6B5738FE352C1A80DBA57023",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_XL, 300, 300, false, OS_GRAPHENE))
            .put("AF4D2C6E62BE0FEC54F0271B9776FF061DD8392D9F51CF6AB1551D346679E24C",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_FOLD, 300, 300, false, OS_GRAPHENE))
            .put("0508DE44EE00BFB49ECE32C418AF1896391ABDE0F05B64F41BC9A2DFB589445B",
                    new DeviceInfo(DEVICE_PIXEL_9A, 300, 300, false, OS_GRAPHENE))
            .put("3F7415EA26F5DF5B14EA6D153256071A7A1AF9CE7B0970B7311CC463C7EA02C7",
                    new DeviceInfo(DEVICE_PIXEL_10, 300, 300, false, OS_GRAPHENE))
            .put("4E8EE8F717754052198CA6D2D3AAA232E2461B4293C0D6F297E519CC778DE093",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO, 300, 300, false, OS_GRAPHENE))
            .put("141D7FC32AF7958A416F2661B37CF6F27BFB376FB5CE616AEAA27A82C7A04F74",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_XL, 300, 300, false, OS_GRAPHENE))
            .put("55A2D44103E56D5EC65496399C417987BA77730E6488FC60BA058D09FC3CAEE3",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_FOLD, 300, 300, false, OS_GRAPHENE))
            .build();
    static final ImmutableMap<String, DeviceInfo> fingerprintsStrongBoxStock = ImmutableMap
            .<String, DeviceInfo>builder()
            .put("AE6316B4753C61F5855B95B9B98484AF784F2E83648D0FCC8107FCA752CAEA34",
                    new DeviceInfo(DEVICE_PIXEL_4_GENERIC, 3, 4, false, OS_STOCK))
            .put("879CD3F18EA76E244D4D4AC3BCB9C337C13B4667190B19035AFE2536550050F1",
                    new DeviceInfo(DEVICE_PIXEL_4A, 3, 4, false, OS_STOCK))
            .put("88265D85BA9E1E2F6036A259D880D2741031ACA445840137395B6D541C0FC7FC",
                    new DeviceInfo(DEVICE_PIXEL_5_GENERIC, 4, 41, false, OS_STOCK))
            .put("1DD694CE00BF131AD61CEB576B7DCC41CF7F9B2C418F4C12B2B8F3E9A1EA911D",
                    new DeviceInfo(DEVICE_PIXEL_5A, 4, 41, false, OS_STOCK))
            .put("0F6E75C80183B5DEC074B0054D4271E99389EBE4B136B0819DE1F150BA0FF9D7",
                    new DeviceInfo(DEVICE_PIXEL_6, 100, 100, false, OS_STOCK))
            .put("42ED1BCA352FABD428F34E8FCEE62776F4CB2C66E06F82E5A59FF4495267BFC2",
                    new DeviceInfo(DEVICE_PIXEL_6_PRO, 100, 100, false, OS_STOCK))
            .put("9AC4174153D45E4545B0F49E22FE63273999B6AC1CB6949C3A9F03EC8807EEE9",
                    new DeviceInfo(DEVICE_PIXEL_6A, 100, 100, false, OS_STOCK))
            .put("8B2C4CD539F5075E8E7CF212ADB3DB0413FBD77D321199C73D5A473C51F2E10D",
                    new DeviceInfo(DEVICE_PIXEL_7, 100, 100, false, OS_STOCK))
            .put("26AC4C60BEB1E378357CAD0C3061347AF8DF6FBABBB0D8CEA2445855EE01E368",
                    new DeviceInfo(DEVICE_PIXEL_7_PRO, 100, 100, false, OS_STOCK))
            .put("003F1ADE9D476E612B00F2983E6AD7DCD15E6A80CC2DBB008DA7D6839ED73A8F",
                    new DeviceInfo(DEVICE_PIXEL_7A, 100, 100, false, OS_STOCK))
            .put("C72E569827EC2E19A1073D927E3B6A1C6C8322DA795D5CE44BF3B95031B37C0A",
                    new DeviceInfo(DEVICE_PIXEL_TABLET, 100, 100, false, OS_STOCK))
            .put("3BBD4712D8714812E762D3FB6D2D5724800C3342B1835CDBC1D3634AE59D646E",
                    new DeviceInfo(DEVICE_PIXEL_FOLD, 100, 100, false, OS_STOCK))
            .put("64DEF0828FF5D3EAC65C3F5CEF46C1D855FE0A5D8525E90FB94FC3DBA9988C87",
                    new DeviceInfo(DEVICE_PIXEL_8, 300, 300, false, OS_STOCK))
            .put("E5362DDF4676E8AA134DB520749BCB1F44FE6556F5E7BFAB130CB6343476FC15",
                    new DeviceInfo(DEVICE_PIXEL_8_PRO, 300, 300, false, OS_STOCK))
            .put("9DE25FB02BB5530D44149D148437C82E267E557322530AA6F03B0AC2E92931DA",
                    new DeviceInfo(DEVICE_PIXEL_8A, 300, 300, false, OS_STOCK))
            .put("ACB5A4DD184E2C44CFA6A53D2D5C5E8674C9498A59F8AE8019942AC1FCEB1E6C",
                    new DeviceInfo(DEVICE_PIXEL_9, 300, 300, false, OS_STOCK))
            .put("06035F636BDB7F299A94B51C7D5645A913551327FFC5452B00C5830476D3208E",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO, 300, 300, false, OS_STOCK))
            .put("D05975CFD778082E3D1623C91419F6D8634E579A786592118CCEA057537579B7",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_XL, 300, 300, false, OS_STOCK))
            .put("800E9093D29614F5BC3FC76A0E819BA0A5C0C94A7D6A17C53E7D017D346B7172",
                    new DeviceInfo(DEVICE_PIXEL_9_PRO_FOLD, 300, 300, false, OS_STOCK))
            .put("3327AF62D84AB897AF2523A16DCB5801E60C5D5B97F41CA1BD099C4784F7B743",
                    new DeviceInfo(DEVICE_PIXEL_9A, 300, 300, false, OS_STOCK))
            .put("757C626A2A91FE852536546048D7CA3F50DF6C745C026DB9FF89CC4703C59481",
                    new DeviceInfo(DEVICE_PIXEL_10, 300, 300, false, OS_STOCK))
            .put("244BAAF78D0FEE555A562FDD3F70EF61036492FBA7AD192B83BB8D427E380B17",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO, 300, 300, false, OS_STOCK))
            .put("CA5C81DA02B8DEBB054FC625135A7833698A9B32148E8A2EF619EBC62AB2E3D8",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_XL, 300, 300, false, OS_STOCK))
            .put("072D8E3269350849F3DE787AC7A319F264C34FA326A7E70917FD96AAEFD2FB0E",
                    new DeviceInfo(DEVICE_PIXEL_10_PRO_FOLD, 300, 300, false, OS_STOCK))
            .build();

    private static final byte[] GOOGLE_ROOT_CERTIFICATE_0 = readResource("google_root_0.der");
    private static final byte[] GOOGLE_ROOT_CERTIFICATE_1 = readResource("google_root_1.der");
    private static final byte[] GOOGLE_ROOT_CERTIFICATE_2 = readResource("google_root_2.der");
    private static final byte[] GOOGLE_ROOT_CERTIFICATE_3 = readResource("google_root_3.der");
    private static final byte[] GOOGLE_ROOT_CERTIFICATE_4 = readResource("google_root_4.der");
    static final byte[] DEFLATE_DICTIONARY_2 = readResource("deflate_dictionary_2.bin");
    static final byte[] DEFLATE_DICTIONARY_4 = readResource("deflate_dictionary_4.bin");
    static final byte[] DEFLATE_DICTIONARY_5 = readResource("deflate_dictionary_5.bin");

    private static byte[] readResource(final String path) {
        try (final InputStream stream = AttestationProtocol.class.getResourceAsStream(path)) {
            return stream.readAllBytes();
        } catch (final IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static final ThreadLocal<SecureRandom> random =
            ThreadLocal.withInitial(() -> new SecureRandom());

    static byte[] generateRandomToken() {
        final byte[] challenge = new byte[RANDOM_TOKEN_LENGTH];
        random.get().nextBytes(challenge);
        return challenge;
    }

    private static byte[] getFingerprint(final Certificate certificate)
            throws CertificateEncodingException {
        return FINGERPRINT_HASH_FUNCTION.hashBytes(certificate.getEncoded()).asBytes();
    }

    private record Verified(String device, String verifiedBootKey, byte[] verifiedBootHash,
            String osName, int osVersion, int osPatchLevel, int vendorPatchLevel, int bootPatchLevel,
            int appVersion, int appVariant, int securityLevel, boolean attestKey) {

        boolean hasPogoPins() {
            return DEVICE_PIXEL_TABLET.equals(device);
        }
    }

    private static X509Certificate generateCertificate(final InputStream in)
            throws CertificateException {
        return (X509Certificate) CertificateFactory.getInstance("X.509").generateCertificate(in);
    }

    private static Verified verifyStateless(final Certificate[] certificates,
            final Cache<ByteBuffer, Boolean> pendingChallenges, final boolean hasPersistentKey,
            final byte[][] validRoots) throws GeneralSecurityException {

        verifyCertificateSignatures(certificates, hasPersistentKey);

        // check that the root certificate is a valid key attestation root
        final byte[] root = certificates[certificates.length - 1].getEncoded();
        if (!Arrays.stream(validRoots).anyMatch(v -> Arrays.equals(v, root))) {
