Reviewing Signal’s Cryptography, Part 5

Reviewing the Cryptography Used by Signal

Contents

  1. Introduction
  2. How Soatok Approaches Cryptography Audits
  3. Mapping Signal and Prioritizing Targets
  4. Message and Media Encryption
  5. Forward-Secure Ratcheting Protocols (you are here)
  6. Miscellaneous Cryptographic Features
  7. Signal’s New Key Transparency Feature
  8. Summary and Findings

Forward-Secure Ratcheting Protocols

In the previous section, we concluded that the symmetric-key encryption used by Signal is secure if the keys are well-managed.

The forward-secure ratcheting protocols will thus be the primary determining factor in our overall assessment of the security of the previous section.

Overview

  1. Ratcheting Protocols
  2. Diffie-Hellman
  3. ML-KEM-1024
  4. KDF Chaining
  5. Group Key Agreement

Ratcheting Protocols

Signal’s ratcheting protocol has evolved over time, and today, it has the following layers to it:

  1. X3DH: Extended Three-Way Diffie-Hellman, which I’ve previously implemented a variant of in TypeScript
  2. The Double Ratchet, which combines X3DH with a KDF ratcheting protocol that only uses symmetric-key cryptography.
  3. PQXDH: Post-Quantum Extended Diffie-Hellman, which combines ML-KEM-1024 (formerly known as Kyber) with the X3DH.

The implementation we’re most interested in is the Rust code in libsignal. The front-facing ratcheting code describing the protocol actually fits in a little under 200 lines.

Here’s the initialization code for “Alice” (the sender):

pub(crate) fn initialize_alice_session<R: Rng + CryptoRng>(
    parameters: &AliceSignalProtocolParameters,
    mut csprng: &mut R,
) -> Result<SessionState> {
    let local_identity = parameters.our_identity_key_pair().identity_key();

    let sending_ratchet_key = KeyPair::generate(&mut csprng);

    let mut secrets = Vec::with_capacity(32 * 5);

    secrets.extend_from_slice(&[0xFFu8; 32]); // "discontinuity bytes"

    let our_base_private_key = parameters.our_base_key_pair().private_key;

    secrets.extend_from_slice(
        &parameters
            .our_identity_key_pair()
            .private_key()
            .calculate_agreement(parameters.their_signed_pre_key())?,
    );

    secrets.extend_from_slice(
        &our_base_private_key.calculate_agreement(parameters.their_identity_key().public_key())?,
    );

    secrets.extend_from_slice(
        &our_base_private_key.calculate_agreement(parameters.their_signed_pre_key())?,
    );

    if let Some(their_one_time_prekey) = parameters.their_one_time_pre_key() {
        secrets
            .extend_from_slice(&our_base_private_key.calculate_agreement(their_one_time_prekey)?);
    }

    let kyber_ciphertext = parameters.their_kyber_pre_key().map(|kyber_public| {
        let (ss, ct) = kyber_public.encapsulate();
        secrets.extend_from_slice(ss.as_ref());
        ct
    });
    let has_kyber = parameters.their_kyber_pre_key().is_some();

    let (root_key, chain_key) = derive_keys(has_kyber, &secrets);

    let (sending_chain_root_key, sending_chain_chain_key) = root_key.create_chain(
        parameters.their_ratchet_key(),
        &sending_ratchet_key.private_key,
    )?;

    let mut session = SessionState::new(
        message_version(has_kyber),
        local_identity,
        parameters.their_identity_key(),
        &sending_chain_root_key,
        &parameters.our_base_key_pair().public_key,
    )
    .with_receiver_chain(parameters.their_ratchet_key(), &chain_key)
    .with_sender_chain(&sending_ratchet_key, &sending_chain_chain_key);

    if let Some(kyber_ciphertext) = kyber_ciphertext {
        session.set_kyber_ciphertext(kyber_ciphertext);
    }

    Ok(session)
}

Diffie-Hellman

The calculate_agreement calls on the private keys are an abstraction around a call to the diffie_hellman method on StaticSecret from x25519-dalek.

pub fn calculate_agreement(
	&self,
	their_public_key: &[u8; PUBLIC_KEY_LENGTH],
) -> [u8; AGREEMENT_LENGTH] {
	*self
		.secret
		.diffie_hellman(&PublicKey::from(*their_public_key))
		.as_bytes()
}

If you trace this through the other curve25519-dalek code (including operator overloading), you’ll eventually arrive at variable_base_mul.

pub fn variable_base_mul(point: &EdwardsPoint, scalar: &Scalar) -> EdwardsPoint {
    match get_selected_backend() {
        #[cfg(curve25519_dalek_backend = "simd")]
        BackendKind::Avx2 => vector::scalar_mul::variable_base::spec_avx2::mul(point, scalar),
        #[cfg(all(curve25519_dalek_backend = "unstable_avx512", nightly))]
        BackendKind::Avx512 => {
            vector::scalar_mul::variable_base::spec_avx512ifma_avx512vl::mul(point, scalar)
        }
        BackendKind::Serial => serial::scalar_mul::variable_base::mul(point, scalar),
    }
}

At this point, we could try to review all of curve25519-dalek for implementation flaws, but that would take a long time and make for an excruciatingly dull read. If anyone is interested in doing that, the relevant code for Signal is here.

ML-KEM-1024

Signal’s post-quantum cryptography (i.e., how kyber_ciphertext is derived in the ratcheting protocol code at the top of this page) is a simple wrapper for the pqcrypto-kyber crate (crates.io).

However, this crate was deleted in October 2024 in favor of the new pcrypto-mlkem crate (which conforms to the FIPS-203 specification).

There is an existing issue tracking the migration from pqcrypto-kyber to pqcrypto-mlkem.

If there is any vulnerability introduced by discrepancies between ML-KEM and the original Kyber submission package, then it won’t affect the security of any Signal messages until a quantum computer exists because the Kyber shared secret is mixed with the Diffie-Hellman shared secrets with a Key Derivation Function.

KDF Chaining

So, regardless of whether you’re using X3DH or PQXDH, the output is a shared secret. What does Signal do with this secret to ensure forward secrecy?

It turns out, this is really simple:

fn derive_keys_with_label(label: &[u8], secret_input: &[u8]) -> (RootKey, ChainKey) {
    let mut secrets = [0; 64];
    hkdf::Hkdf::<sha2::Sha256>::new(None, secret_input)
        .expand(label, &mut secrets)
        .expect("valid length");
    let (root_key_bytes, chain_key_bytes) = secrets.split_at(32);

    let root_key = RootKey::new(root_key_bytes.try_into().expect("correct length"));
    let chain_key = ChainKey::new(chain_key_bytes.try_into().expect("correct length"), 0);

    (root_key, chain_key)
}

Signal uses HDKF-HMAC-SHA256 to derive a 512-bit (64 byte) secret. Half of these bytes are the new root key (used as an IKM for deriving the cipher key, MAC key, and IV for message and media encryption), the other half is used as the next HKDF key for deriving future keys.

This is the essence of how the symmetric component of the double ratchet works. Since HKDF is a secure KDF, and they’re not even misusing the salt/info parameters (as evidenced by None being passed to Hkdf::new() for the salt parameter–which would have only degraded from KDF security to PRF security, which is still secure enough for this context), there’s no attack here.

Soatok Yay Sticker
Art: AJ

Group Key Agreement

Even if we’re sure that 1:1 group messaging is secure (assuming the answer to “can you trust the X25519 public key?” is “yes”), due to the ratcheting protocols, group messaging is kind of special.

It would be much simpler if Signal adopted something like RFC 9420 (Messaging Layer Security), but MLS doesn’t provide the metadata resistance that Signal prioritized.

The encryption key used for sending messages to a group is handled here on the decrypt path, and here on the encrypt path.

Let’s start with the encrypt path. 

pub async fn create_sender_key_distribution_message<R: Rng + CryptoRng>(
    sender: &ProtocolAddress,
    distribution_id: Uuid,
    sender_key_store: &mut dyn SenderKeyStore,
    csprng: &mut R,
) -> Result<SenderKeyDistributionMessage> {
    let sender_key_record = sender_key_store
        .load_sender_key(sender, distribution_id)
        .await?;

    let sender_key_record = match sender_key_record {
        Some(record) => record,
        None => {
            // libsignal-protocol-java uses 31-bit integers for sender key chain IDs
            let chain_id = (csprng.gen::<u32>()) >> 1;
            log::info!(
                "Creating SenderKey for distribution {} with chain ID {}",
                distribution_id,
                chain_id
            );

            let iteration = 0;
            let sender_key: [u8; 32] = csprng.gen();
            let signing_key = KeyPair::generate(csprng);
            let mut record = SenderKeyRecord::new_empty();
            record.add_sender_key_state(
                SENDERKEY_MESSAGE_CURRENT_VERSION,
                chain_id,
                iteration,
                &sender_key,
                signing_key.public_key,
                Some(signing_key.private_key),
            );
            sender_key_store
                .store_sender_key(sender, distribution_id, &record)
                .await?;
            record
        }
    };

    let state = sender_key_record
        .sender_key_state()
        .map_err(|_| SignalProtocolError::InvalidSenderKeySession { distribution_id })?;
    let sender_chain_key = state
        .sender_chain_key()
        .ok_or(SignalProtocolError::InvalidSenderKeySession { distribution_id })?;
    let message_version = state
        .message_version()
        .try_into()
        .map_err(|_| SignalProtocolError::InvalidSenderKeySession { distribution_id })?;

    SenderKeyDistributionMessage::new(
        message_version,
        distribution_id,
        state.chain_id(),
        sender_chain_key.iteration(),
        sender_chain_key.seed().to_vec(),
        state
            .signing_key_public()
            .map_err(|_| SignalProtocolError::InvalidSenderKeySession { distribution_id })?,
    )
}

As you can see from the highlighted section, it generates a 31-bit random Chain ID, 256-bit random sender key, and an X25519 signing keypair (XEdDSA). The X25519 public key for the corresponding keypair is serialized and sent to the other participants.

On the decrypt path, these records are processed as you’d expect:

pub async fn process_sender_key_distribution_message(
    sender: &ProtocolAddress,
    skdm: &SenderKeyDistributionMessage,
    sender_key_store: &mut dyn SenderKeyStore,
) -> Result<()> {
    let distribution_id = skdm.distribution_id()?;
    log::info!(
        "{} Processing SenderKey distribution {} with chain ID {}",
        sender,
        distribution_id,
        skdm.chain_id()?
    );

    let mut sender_key_record = sender_key_store
        .load_sender_key(sender, distribution_id)
        .await?
        .unwrap_or_else(SenderKeyRecord::new_empty);

    sender_key_record.add_sender_key_state(
        skdm.message_version(),
        skdm.chain_id()?,
        skdm.iteration()?,
        skdm.chain_key()?,
        *skdm.signing_key()?,
        None,
    );
    sender_key_store
        .store_sender_key(sender, distribution_id, &sender_key_record)
        .await?;
    Ok(())
}

The SenderKeyDistributionMessage struct is deserialized from bytes like so:

mpl TryFrom<&[u8]> for SenderKeyDistributionMessage {
    type Error = SignalProtocolError;

    fn try_from(value: &[u8]) -> Result<Self> {
        // The message contains at least a X25519 key and a chain key
        if value.len() < 1 + 32 + 32 {
            return Err(SignalProtocolError::CiphertextMessageTooShort(value.len()));
        }

        let message_version = value[0] >> 4;

        if message_version < SENDERKEY_MESSAGE_CURRENT_VERSION {
            return Err(SignalProtocolError::LegacyCiphertextVersion(
                message_version,
            ));
        }
        if message_version > SENDERKEY_MESSAGE_CURRENT_VERSION {
            return Err(SignalProtocolError::UnrecognizedCiphertextVersion(
                message_version,
            ));
        }

        let proto_structure = proto::wire::SenderKeyDistributionMessage::decode(&value[1..])
            .map_err(|_| SignalProtocolError::InvalidProtobufEncoding)?;

        let distribution_id = proto_structure
            .distribution_uuid
            .and_then(|bytes| Uuid::from_slice(bytes.as_slice()).ok())
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let chain_id = proto_structure
            .chain_id
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let iteration = proto_structure
            .iteration
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let chain_key = proto_structure
            .chain_key
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let signing_key = proto_structure
            .signing_key
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;

        if chain_key.len() != 32 || signing_key.len() != 33 {
            return Err(SignalProtocolError::InvalidProtobufEncoding);
        }

        let signing_key = PublicKey::deserialize(&signing_key)?;

        Ok(SenderKeyDistributionMessage {
            message_version,
            distribution_id,
            chain_id,
            iteration,
            chain_key,
            signing_key,
            serialized: Box::from(value),
        })
    }
}

This code is exposed to both FFI and JNI. If we focus on the Android code, the wrapper is defined here:

impl TryFrom<&[u8]> for SenderKeyDistributionMessage {
    type Error = SignalProtocolError;

    fn try_from(value: &[u8]) -> Result<Self> {
        // The message contains at least a X25519 key and a chain key
        if value.len() < 1 + 32 + 32 {
            return Err(SignalProtocolError::CiphertextMessageTooShort(value.len()));
        }

        let message_version = value[0] >> 4;

        if message_version < SENDERKEY_MESSAGE_CURRENT_VERSION {
            return Err(SignalProtocolError::LegacyCiphertextVersion(
                message_version,
            ));
        }
        if message_version > SENDERKEY_MESSAGE_CURRENT_VERSION {
            return Err(SignalProtocolError::UnrecognizedCiphertextVersion(
                message_version,
            ));
        }

        let proto_structure = proto::wire::SenderKeyDistributionMessage::decode(&value[1..])
            .map_err(|_| SignalProtocolError::InvalidProtobufEncoding)?;

        let distribution_id = proto_structure
            .distribution_uuid
            .and_then(|bytes| Uuid::from_slice(bytes.as_slice()).ok())
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let chain_id = proto_structure
            .chain_id
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let iteration = proto_structure
            .iteration
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let chain_key = proto_structure
            .chain_key
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;
        let signing_key = proto_structure
            .signing_key
            .ok_or(SignalProtocolError::InvalidProtobufEncoding)?;

        if chain_key.len() != 32 || signing_key.len() != 33 {
            return Err(SignalProtocolError::InvalidProtobufEncoding);
        }

        let signing_key = PublicKey::deserialize(&signing_key)?;

        Ok(SenderKeyDistributionMessage {
            message_version,
            distribution_id,
            chain_id,
            iteration,
            chain_key,
            signing_key,
            serialized: Box::from(value),
        })
    }
}

If you want to trace the usages in the Android app:

When you put these details together, it’s pretty clear what’s happening.

  1. The group message is encrypted with AES-CBC.
  2. The ciphertext (step 1) is signed with XEdDSA.
  3. The envelope is encrypted in accordance with Sealed Sender. This envelope includes the signing public key, initial chain key, chain counter, etc. as well as the ciphertext and signature.

Upon receiving a message, Signal opens the Sealed Sender envelope, verifies the signature matches the public key for that sender, and then decrypts the group message ciphertext.

There’s a lot more interesting stuff at work here, so let’s focus on the advanced cryptography used for group messaging next.

We can’t stop here, this is zero-knowledge proof country.

Blep Tongue Sticker
CMYKat

Part 5 Recap

The double ratchet provides forward secrecy and key compromise impersonation (KCI) security by only using a symmetric key once. It achieves this by combining Elliptic Curve Diffie-Hellman handshakes with HKDF that splits root keys from chain keys, which are used to derive the keys used for each message and future root keys (respectively).

There is new code that combines a post-quantum KEM to provide post-quantum security for the Signal handshake, but it relies on old Rust implementation of Kyber, rather than the new ML-KEM standard in FIPS-203, which was deleted by pqcrypto. Until they resolve this, the long-term maintainability of their post-quantum cryptography is uncertain (though I do not know of any specific vulnerabilities in Kyber as implemented in pqcrypto).

The group messaging protocols are a little interesting, so next, we’re going to explore some of the zero-knowledge proof and advanced cryptography.

Next: Miscellaneous Cryptographic Features