• iMessage with PQ3: The new state of the art in quantum-securemessaging at scale

    From Jolly Roger@jollyroger@pobox.com to misc.phone.mobile.iphone,comp.mobile.ipad,comp.sys.mac.apps on Wed Feb 21 21:07:41 2024
    From Newsgroup: comp.sys.mac.apps

    After watching the resident Apple-hating trolls get their panties
    twisted about iMessage security in a recent thread here, I just noticed
    Apple's announcement that iMessage is now encrypted with post-quantum cryptographic algorithms born from the NIST competition a while back:

    iMessage with PQ3: The new state of the art in quantum-secure messaging
    at scale

    <https://security.apple.com/blog/imessage-pq3/>

    ---
    Posted by Apple Security Engineering and Architecture (SEAR)

    Today we are announcing the most significant cryptographic security
    upgrade in iMessage history with the introduction of PQ3, a
    groundbreaking post-quantum cryptographic protocol that advances the
    state of the art of end-to-end secure messaging. With
    compromise-resilient encryption and extensive defenses against even
    highly sophisticated quantum attacks, PQ3 is the first messaging
    protocol to reach what we call Level 3 security — providing protocol protections that surpass those in all other widely deployed messaging
    apps. To our knowledge, PQ3 has the strongest security properties of any at-scale messaging protocol in the world.

    Messaging apps are placed on a spectrum starting with classical
    cryptography and progressing towards quantum security. Most apps fall
    into Level 0, with no end-to-end encryption by default and no quantum
    security, or Level 1, with end-to-end encryption by default, but with no quantum security. Signal’s PQXDH protocol introduces post-quantum
    security in the initial key establishment at Level 2 and iMessage with
    PQ3 attains Level 3, where post-quantum cryptography is used to secure
    both the initial key establishment and the ongoing message exchange.

    <https://security.apple.com/assets/image/generated/xlarge_quantum_security_messaging_apps_DarkMode.png>

    When iMessage launched in 2011, it was the first widely available
    messaging app to provide end-to-end encryption by default, and we have significantly upgraded its cryptography over the years. We most recently strengthened the iMessage cryptographic protocol in 2019 by switching
    from RSA to Elliptic Curve cryptography (ECC), and by protecting
    encryption keys on device with the Secure Enclave, making them
    significantly harder to extract from a device even for the most
    sophisticated adversaries. That protocol update went even further with
    an additional layer of defense: a periodic rekey mechanism to provide cryptographic self-healing even in the extremely unlikely case that a
    key ever became compromised. Each of these advances were formally
    verified by symbolic evaluation, a best practice that provides strong assurances of the security of cryptographic protocols.

    Historically, messaging platforms have used classical public key
    cryptography, such as RSA, Elliptic Curve signatures, and Diffie-Hellman
    key exchange, to establish secure end-to-end encrypted connections
    between devices. All these algorithms are based on difficult
    mathematical problems that have long been considered too computationally intensive for computers to solve, even when accounting for Moore’s law. However, the rise of quantum computing threatens to change the equation.
    A sufficiently powerful quantum computer could solve these classical mathematical problems in fundamentally different ways, and therefore —
    in theory — do so fast enough to threaten the security of end-to-end encrypted communications.

    Although quantum computers with this capability don’t exist yet,
    extremely well-resourced attackers can already prepare for their
    possible arrival by taking advantage of the steep decrease in modern
    data storage costs. The premise is simple: such attackers can collect
    large amounts of today’s encrypted data and file it all away for future reference. Even though they can’t decrypt any of this data today, they
    can retain it until they acquire a quantum computer that can decrypt it
    in the future, an attack scenario known as Harvest Now, Decrypt Later.

    To mitigate risks from future quantum computers, the cryptographic
    community has been working on post-quantum cryptography (PQC): new
    public key algorithms that provide the building blocks for
    quantum-secure protocols but don’t require a quantum computer to run —
    that is, protocols that can run on the classical, non-quantum computers
    we’re all using today, but that will remain secure from known threats
    posed by future quantum computers.

    To reason through how various messaging applications mitigate attacks,
    it’s helpful to place them along a spectrum of security properties.
    There’s no standard comparison to employ for this purpose, so we lay out
    our own simple, coarse-grained progression of messaging security levels
    in the image at the top of this post: we start on the left with
    classical cryptography and progress towards quantum security, which
    addresses current and future threats from quantum computers. Most
    existing messaging apps fall either into Level 0 — no end-to-end
    encryption by default and no quantum security — or Level 1 — with end-to-end encryption by default, but with no quantum security. A few
    months ago, Signal added support for the PQXDH protocol, becoming the
    first large-scale messaging app to introduce post-quantum security in
    the initial key establishment. This is a welcome and critical step that,
    by our scale, elevated Signal from Level 1 to Level 2 security.

    At Level 2, the application of post-quantum cryptography is limited to
    the initial key establishment, providing quantum security only if the conversation key material is never compromised. But today’s
    sophisticated adversaries already have incentives to compromise
    encryption keys, because doing so gives them the ability to decrypt
    messages protected by those keys for as long as the keys don’t change.
    To best protect end-to-end encrypted messaging, the post-quantum keys
    need to change on an ongoing basis to place an upper bound on how much
    of a conversation can be exposed by any single, point-in-time key
    compromise — both now and with future quantum computers. Therefore, we believe messaging protocols should go even further and attain Level 3
    security, where post-quantum cryptography is used to secure both the
    initial key establishment and the ongoing message exchange, with the
    ability to rapidly and automatically restore the cryptographic security
    of a conversation even if a given key becomes compromised.

    iMessage now meets this goal with a new cryptographic protocol that we
    call PQ3, offering the strongest protection against quantum attacks and becoming the only widely available messaging service to reach Level 3
    security. Support for PQ3 will start to roll out with the public
    releases of iOS 17.4, iPadOS 17.4, macOS 14.4, and watchOS 10.4, and is
    already in the corresponding developer preview and beta releases.
    iMessage conversations between devices that support PQ3 are
    automatically ramping up to the post-quantum encryption protocol. As we
    gain operational experience with PQ3 at the massive global scale of
    iMessage, it will fully replace the existing protocol within all
    supported conversations this year.

    Designing PQ3

    More than simply replacing an existing algorithm with a new one, we
    rebuilt the iMessage cryptographic protocol from the ground up to
    advance the state of the art in end-to-end encryption, and to deliver on
    the following requirements:

    - Introduce post-quantum cryptography from the start of a conversation, so
    that all communication is protected from current and future adversaries.

    - Mitigate the impact of key compromises by limiting how many past and
    future messages can be decrypted with a single compromised key.

    - Use a hybrid design to combine new post-quantum algorithms with current
    Elliptic Curve algorithms, ensuring that PQ3 can can never be less safe
    than the existing classical protocol.

    - Amortize message size to avoid excessive additional overhead from the
    added security.

    - Use formal verification methods to provide strong security assurances
    for the new protocol.

    PQ3 introduces a new post-quantum encryption key in the set of public
    keys each device generates locally and transmits to Apple servers as
    part of iMessage registration. For this application, we chose to use
    Kyber post-quantum public keys, an algorithm that received close
    scrutiny from the global cryptography community, and was selected by
    NIST as the Module Lattice-based Key Encapsulation Mechanism standard,
    or ML-KEM. This enables sender devices to obtain a receiver’s public
    keys and generate post-quantum encryption keys for the very first
    message, even if the receiver is offline. We refer to this as initial
    key establishment.

    We then include — within conversations — a periodic post-quantum
    rekeying mechanism that has the ability to self-heal from key compromise
    and protect future messages. In PQ3, the new keys sent along with the conversation are used to create fresh message encryption keys that can’t
    be computed from past ones, thereby bringing the conversation back to a
    secure state even if previous keys were extracted or compromised by an adversary. PQ3 is the first large scale cryptographic messaging protocol
    to introduce this novel post-quantum rekeying property.

    PQ3 employs a hybrid design that combines Elliptic Curve cryptography
    with post-quantum encryption both during the initial key establishment
    and during rekeying. Thus, the new cryptography is purely additive, and defeating PQ3 security requires defeating both the existing, classical
    ECC cryptography and the new post-quantum primitives. It also means the protocol benefits from all the experience we accumulated from deploying
    the ECC protocol and its implementations.

    Rekeying in PQ3 involves transmitting fresh public key material in-band
    with the encrypted messages that devices are exchanging. A new public
    key based on Elliptic Curve Diffie-Hellman (ECDH) is transmitted inline
    with every response. The post-quantum key used by PQ3 has a
    significantly larger wire size than the existing protocol, so to meet
    our message size requirement we designed the quantum-secure rekeying to
    happen periodically rather than with every message. To determine whether
    a new post-quantum key is transmitted, PQ3 uses a rekeying condition
    that aims to balance the average size of messages on the wire, preserve
    the user experience in limited connectivity scenarios, and keep the
    global volume of messages within the capacity of our server
    infrastructure. Should the need arise, future software updates can
    increase the rekeying frequency in a way that’s backward-compatible with
    all devices that support PQ3.

    With PQ3, iMessage continues to rely on classical cryptographic
    algorithms to authenticate the sender and verify the Contact Key
    Verification account key, because these mechanisms can’t be attacked retroactively with future quantum computers. To attempt to insert
    themselves in the middle of an iMessage conversation, an adversary would require a quantum computer capable of breaking one of the authentication
    keys before or at the time the communication takes place. In other
    words, these attacks cannot be performed in a Harvest Now, Decrypt Later scenario — they require the existence of a quantum computer capable of performing the attacks contemporaneously with the communication being
    attacked. We believe any such capability is still many years away, but
    as the threat of quantum computers evolves, we will continue to assess
    the need for post-quantum authentication to thwart such attacks.

    A formally proven protocol

    Our final requirement for iMessage PQ3 is formal verification — a mathematical proof of the intended security properties of the protocol.
    PQ3 received extensive review from Apple’s own multi-disciplinary teams
    in Security Engineering and Architecture (SEAR) as well as from some of
    the world’s foremost experts in cryptography. This includes a team led
    by Professor David Basin, head of the Information Security Group at ETH
    Zürich and one of the inventors of Tamarin — a leading security protocol verification tool that was also used to evaluate PQ3 — as well as
    Professor Douglas Stebila from the University of Waterloo, who has
    performed extensive research on post-quantum security for internet
    protocols. Each took a different but complementary approach, using
    different mathematical models to demonstrate that as long as the
    underlying cryptographic algorithms remain secure, so does PQ3. Finally,
    a leading third-party security consultancy supplemented our internal implementation review with an independent assessment of the PQ3 source
    code, which found no security issues.

    In the first mathematical analysis, Security analysis of the iMessage
    PQ3 protocol, Professor Douglas Stebila focused on so-called game-based
    proofs. This technique, also known as reduction, defines a series of “games“ or logical statements to show that the protocol is at least as strong as the algorithms that underpin it. Stebila’s analysis shows that
    PQ3 provides confidentiality even in the presence of some key
    compromises against both classical and quantum adversaries, in both the
    initial key establishment and the ongoing rekeying phase of the
    protocol. The analysis decomposes the many layers of key derivations
    down to the message keys and proves that, for an attacker, they are indistinguishable from random noise. Through an extensive demonstration
    that considers different attack paths for classical and quantum
    attackers in the proofs, Stebila shows that the keys used for PQ3 are
    secure as long as either the Elliptic Curve Diffie-Hellman problem
    remains hard or the Kyber post-quantum KEM remains secure.

    "The iMessage PQ3 protocol is a well-designed cryptographic protocol for
    secure messaging that uses state-of-the-art techniques for end-to-end
    encrypted communication. In my analysis using the reductionist security methodology, I confirmed that the PQ3 protocol provides post-quantum confidentiality, which can give users confidence in the privacy of their communication even in the face of potential improvements in quantum
    computing technology." — Professor Douglas Stebila

    In the second evaluation, A Formal Analysis of the iMessage PQ3
    Messaging Protocol, Prof. David Basin, Felix Linker, and Dr. Ralf Sasse
    at ETH Zürich use a method called symbolic evaluation. As highlighted in
    the paper’s abstract, this analysis includes a detailed formal model of
    the iMessage PQ3 protocol, a precise specification of its fine-grained
    security properties, and machine-checked proofs using the
    state-of-the-art symbolic Tamarin prover. The evaluation yielded a
    fine-grained analysis of the secrecy properties of PQ3, proving that “in
    the absence of the sender or recipient being compromised, all keys and
    messages transmitted are secret” and that “compromises can be tolerated
    in a well-defined sense where the effect of the compromise on the
    secrecy of data is limited in time and effect,” which confirms that PQ3
    meets our goals.

    "We provide a mathematical model of PQ3 as well as prove its secrecy and authenticity properties using a verification tool for machine-checked
    security proofs. We prove the properties even when the protocol operates
    in the presence of very strong adversaries who can corrupt parties or
    possess quantum computers and therefore defeat classical cryptography.
    PQ3 goes beyond Signal with regards to post-quantum defenses. In PQ3, a post-quantum secure algorithm is part of the ratcheting and used
    repeatedly, rather than only once in the initialization as in Signal.
    Our verification provides a very high degree of assurance that the
    protocol as designed functions securely, even in the post-quantum
    world." — Professor David Basin

    Diving into the details

    Because we know PQ3 will be of intense interest to security researchers
    and engineers as well as the cryptographic community, this blog post is
    really two posts in one. Up to now, we laid out our design goals,
    outlined how PQ3 meets them, and explained how we verified our
    confidence in the protocol with independent assessments. If you’d like
    to understand more detail about the cryptographic underpinnings, the
    remainder of the post is a deeper dive into how we constructed the PQ3 protocol.

    Post-quantum key establishment

    iMessage allows a user to register multiple devices on the same account.
    Each device generates its own set of encryption keys, and the private
    keys are never exported to any external system. The associated public
    keys are registered with Apple’s Identity Directory Service (IDS) to
    enable users to message each other using a simple identifier: email
    address or phone number. When a user sends a message from one of their
    devices, all of their other devices and all of the recipient’s devices receive the message. The messages are exchanged through pair-wise
    sessions established between the sending device and each receiving
    device. The same message is encrypted successively to each receiving
    device, with keys uniquely derived for each session. For the rest of
    this description, we will focus on a single device-to-device session.

    Because the receiving device might not be online when the conversation
    is established, the first message in a session is encrypted using the
    public encryption keys registered with the IDS server.

    Each device with PQ3 registers two public encryption keys and replaces
    them regularly with fresh ones:

    1. A post-quantum Kyber-1024 key encapsulation public key

    2. A classical P-256 Elliptic Curve key agreement public key

    These encryption keys are signed with ECDSA using a P-256 authentication
    key generated by the device’s Secure Enclave, along with a timestamp
    used to limit their validity. The device authentication public key is
    itself signed by the Contact Key Verification account key, along with
    some attributes such as the supported cryptographic protocol version.
    This process allows the sender to verify that the recipient device’s
    public encryption keys were uploaded by the intended recipient, and it
    guards against downgrade attacks.

    When Alice’s device instantiates a new session with Bob’s device, her device queries the IDS server for the key bundle associated with Bob’s device. The subset of the key bundle that contains the device’s authentication key and versioning information is validated using Contact
    Key Verification. The device then validates the signature covering the encryption keys and timestamps, which attests that the keys are valid
    and have not expired.

    Alice’s device can then use the two public encryption keys to share two symmetric keys with Bob. The first symmetric key is computed through an
    ECDH key exchange that combines an ephemeral encryption key from Alice
    with Bob’s registered P-256 public key. The second symmetric key is
    obtained from a Kyber key encapsulation with Bob’s post-quantum public
    key.

    To combine these two symmetric keys, we first extract their entropy by
    invoking HKDF-SHA384-Extract twice — once for each of the keys. The
    resulting 48-byte secret is further combined with a domain separation
    string and session information — which includes the user’s identifiers,
    the public keys used in the key exchange, and the encapsulated secret —
    by invoking HKDF-SHA384-Extract again to derive the session’s initial
    keying state. This combination ensures that the initial session state
    cannot be derived without knowing both of the shared secrets, meaning an attacker would need to break both algorithms to recover the resulting
    secret, thus satisfying our hybrid security requirement.

    Post-quantum rekeying

    Ongoing rekeying of the cryptographic session is designed such that keys
    used to encrypt past and future messages cannot be recomputed even by a powerful hypothetical attacker who is able to extract the cryptographic
    state of the device at a given point in time. The protocol generates a
    new unique key for each message, which periodically includes new entropy
    that is not deterministically derived from the current state of the conversation, effectively providing self-healing properties to the
    protocol. Our rekeying approach is modeled after ratcheting, a technique
    that consists of deriving a new session key from other keys and ensuring
    the cryptographic state always moves forward in one direction. PQ3
    combines three ratchets to achieve post-quantum encryption.

    The first ratchet, called the symmetric ratchet, protects older messages
    in a conversation to achieve forward secrecy. For every message, we
    derive a per-message encryption key from the current session key. The
    current session key itself is then further derived into a new session
    key, ratcheting the state forward. Each message key is deleted as soon
    as a corresponding message is decrypted, which prevents older harvested ciphertexts from being decrypted by an adversary who is able to
    compromise the device at a later time, and provides protection against
    replayed messages. This process uses 256-bit keys and intermediate
    values, and HKDF-SHA384 as a derivation function, which provides
    protection against both classical and quantum computers.

    The second ratchet, called the ECDH ratchet, protects future messages by updating the session with fresh entropy from an Elliptic Curve key
    agreement, ensuring that an adversary loses the ability to decrypt new
    messages even if they had compromised past session keys — a property
    called post-compromise security. The ECDH-based ratchet has a
    symmetrical flow: the private key of the outgoing ratchet public key
    from the sender is used with the last public key received from the
    recipient to establish a new shared secret between sender and receiver,
    which is then mixed into the session’s key material. The new PQ3
    protocol for iMessage uses NIST P-256 Elliptic Curve keys to perform
    this ratchet, which imposes only a small 32-byte overhead on each
    message.

    Because the second ratchet uses classical cryptography, PQ3 also adds a conditionally executed Kyber KEM-based ratchet. This third ratchet
    complements the ECDH-based ratchet to provide post-compromise security
    against Harvest Now, Decrypt Later quantum attacks as well.

    The use of a post-quantum ratchet can cause significant network overhead compared to an ECDH-based ratchet at the same security level. The
    post-quantum KEM requires sending both a public key and an encapsulated
    secret instead of a single outgoing public key. In addition, the
    underlying mathematical structure for quantum security requires
    significantly larger parameter sizes for public keys and encapsulated
    keys compared to Elliptic Curves.

    To limit the size overhead incurred by frequent rekeying while
    preserving a high level of security, the post-quantum KEM is
    instantiated with Kyber-768. Unlike the IDS-registered public keys used
    for the initial key establishment, ratcheting public keys are used only
    once to encapsulate a shared secret to the receiver, significantly
    limiting the impact of the compromise of a single key. However, while
    a 32-byte ECDH-based ratchet overhead is acceptable on every message,
    the post-quantum KEM ratchet increases the message size by more than 2 kilobytes. To avoid visible delays in message delivery when device
    connectivity is limited, this ratchet needs to be amortized over
    multiple messages.

    We therefore implemented an adaptive post-quantum rekeying criterion
    that takes into account the number of outgoing messages, the time
    elapsed since last rekeying, and current connectivity conditions. At
    launch, this means the post-quantum ratchet is performed approximately
    every 50 messages, but the criterion is bounded such that rekeying is
    always guaranteed to occur at least once every 7 days. And as we
    mentioned earlier, as the threat of quantum computers and infrastructure capacity evolves over time, future software updates can increase the
    rekeying frequency while preserving full backward compatibility.

    Completing the public key ratchets, whether based on ECDH or Kyber,
    requires sending and receiving a message. Although users may not
    immediately reply to a message, iMessage includes encrypted delivery
    receipts that allow devices to rapidly complete the ratchet even without
    a reply from the recipient, as long as the device is online. This
    technique avoids delays in the rekeying process and helps support strong post-compromise recovery.

    Similar to the initial session key establishment, the secrets
    established through the three ratchets are all combined with an evolving session key using HKDF-SHA384 through sequential calls to the Extract
    function. At the end of this process, we obtain a final message key,
    which can now be used to encrypt the payload.

    Padding and encryption

    To avoid leaking information about the message size, PQ3 adds padding to
    the message before encryption. This padding is implemented with the
    Padmé heuristic, which specifically limits the information leakage of ciphertexts with maximum length M to a practical optimum of O(log log M)
    bits. This is comparable to padding to a power of two but results in a
    lower overhead of at most 12 percent and even lower for larger payloads.
    This approach strikes an excellent balance between privacy and
    efficiency, and preserves the user experience in limited device
    connectivity scenarios.

    The padded payload is encrypted with AES-CTR using a 256-bit encryption
    key and initialization vector, both derived from the message key. While
    public key algorithms require fundamental changes to achieve quantum
    security, symmetric cryptography algorithms like the AES block cipher
    only require doubling the key size to maintain their level of security
    against quantum computers.

    Authentication

    Each message is individually signed with ECDSA using the elliptic curve
    P-256 device authentication key protected by the Secure Enclave. The
    receiving device verifies the mapping between the sender’s identifier
    (email address or phone number) and the public key used for signature verification. If both users have enabled Contact Key Verification and
    verified each other’s account key, the device verifies that the device authentication keys are present in the Key Transparency log and that the corresponding account key matches the account key stored in the user’s
    iCloud Keychain.

    The device’s authentication key is generated by the Secure Enclave and
    never exposed to the rest of the device, which helps prevent extraction
    of the private key even if the Application Processor is completely
    compromised. If an attacker were to compromise the Application
    Processor, they might be able to use the Secure Enclave to sign
    arbitrary messages. But after the device recovers from the compromise
    through a reboot or a software update, they would no longer be able to impersonate the user. This approach offers stronger guarantees than
    other messaging protocols where the authentication key is sometimes
    shared between devices or where the authentication takes place only at
    the beginning of the session.

    The message signature covers a wide range of fields, including the
    unique identifiers of the users and their push notification tokens, the encrypted payload, authenticated data, a ratchet-derived message key
    indicator that binds the signature to a unique location in the ratchet,
    and any public key information used in the protocol. The inclusion of
    these fields in the signature guarantees that the message can only be
    used in the context intended by the sender, and all the fields are
    exhaustively documented in the research papers from Stebila, Basin, and collaborators.

    Conclusion

    End-to-end encrypted messaging has seen a tremendous amount of
    innovation in recent years, including significant advances in
    post-quantum cryptography from Signal’s PQXDH protocol and in key transparency from WhatsApp’s Auditable Key Directory. Building on its pioneering legacy as the first widely available messaging app to provide end-to-end encryption by default, iMessage has continued to deliver
    advanced protections that surpass existing systems. iMessage Contact Key Verification is the most sophisticated key transparency system for
    messaging deployed at scale, and is the current global state of the art
    for automatic key verification. And the new PQ3 cryptographic protocol
    for iMessage combines post-quantum initial key establishment with
    three ongoing ratchets for self-healing against key compromise,
    defining the global state of the art for protecting messages against
    Harvest Now, Decrypt Later attacks and future quantum computers.
    ---

    Squirm, trollbois... 🤣
    --
    E-mail sent to this address may be devoured by my ravenous SPAM filter.
    I often ignore posts from Google. Use a real news client instead.

    JR
    --- Synchronet 3.20a-Linux NewsLink 1.114