Liveness Vulnerability in AggregateQC Creation due to Unverified Message Signatures

[sunwoo383838]

Hello,

I am currently using this project to implement a new HotStuff-family consensus algorithm based on my theoretical work. During the implementation, I came across a different potential vulnerability from my previous reports that could severely impact liveness, which I've detailed below.

Description

A critical liveness vulnerability has been identified in the CreateAggregateQC function. The current implementation is susceptible to a denial-of-service (DoS) attack orchestrated by a single Byzantine node, which can stall the consensus process by poisoning an AggregateQC with an invalid MsgSignature.

The Problem

The CreateAggregateQC function collects and combines MsgSignature fields from multiple TimeoutMsg payloads without individually verifying each signature's validity against its corresponding Quorum Certificate (QC) within the same message. It blindly trusts that each received MsgSignature is valid before aggregation.

Steps to Reproduce

1. A Byzantine replica sends a TimeoutMsg to the current leader.
2. This message contains a valid view signature but has an intentionally invalid MsgSignature.
3. The leader calls CreateAggregateQC, which trustingly includes the invalid partial signature in the aggregation process.
4. The leader proposes this new AggregateQC containing the poisoned aggregate signature to the network.
5. Honest replicas receive the AggregateQC and call VerifyAggregateQC.
6. The verification fails because the aggregate signature is invalid due to the inclusion of the single forged partial signature.
7. The consensus process stalls as no valid AggregateQC can be formed.

Impact

A single Byzantine node can prevent the formation of a valid AggregateQC for a given view by submitting a single TimeoutMsg with an invalid MsgSignature. This forces honest nodes to reject the proposed AggregateQC, effectively stalling consensus progress and potentially leading to a persistent liveness failure if the attacker continues this behavior in subsequent views.

Recommendation

To mitigate this vulnerability, it is crucial to verify each individual MsgSignature before it is included in the aggregate signature.

The CreateAggregateQC function should be modified to iterate through all incoming TimeoutMsgs and validate that the MsgSignature is a valid signature for the QC contained in that same message. Only signatures that pass this verification should be combined to create the final AggregateQC.

By implementing this change, the system can ensure that only valid partial signatures contribute to the AggregateQC, neutralizing the described attack vector.

[meling]

Isn't this the same issue you raised in #224? We agree that this issue should be fixed, and your proposed plan is fine.

[sunwoo383838]

Hello, issues #224 and #227 address fundamentally different attack vectors.

The previous issue (#224) was about the validity of the highQC itself—the QC with the highest view number within an AggregateQC. The attack involved a Byzantine node submitting an invalid QC with a deceptively high view number, causing the entire AggregateQC to be rejected when the VerifyQuorumCert(highQC) check fails.

However, the current issue (#227) is about the binding of the MsgSignature within an individual TimeoutMsg. A function like OnRemoteTimeout verifies the view signature (VoteSignature) of the TimeoutMsg, but it optimistically combines the message signatures (MsgSignature) without checking if each one is correctly bound to the QC contained in that message's syncinfo.

This allows a Byzantine node to send a valid MsgSignature that is signed over a completely different QC than the one present in the TimeoutMsg's syncinfo. While the Combine process itself might succeed, the resulting AggregateQC will fail when other nodes attempt to verify it using BatchVerify due to the mismatch between the signature and the data.

In summary, #224 is about the forgery of the highQC itself, whereas #227 is about the missing binding verification between the MsgSignature and syncinfo. They impact liveness through different code paths and logic.

I hope this explanation clarifies the distinction. If it's okay with you, shall I proceed with adding the MsgSignature binding verification logic and commit the fix?

[meling]

Could you create an artificially constructed test case that demonstrates the attacks? That is, the test should implement your steps to reproduce and thus should fail with the current implementation, and not with your to-be-implemented fixes.

There is no need to set up communication, you only need to create the (valid/invalid) messages and pass them to the appropriate functions, "simulating" that they were recieved from the network.

[sunwoo383838]

So you're asking me to write the test code for this case, correct? Absolutely. However, something urgent has come up that I need to take care of. Once that's resolved, I'll write and send it over as soon as I have some free time, including for #224 as well. :)

[meling]

Yes. You can implement that test case as part of the PR that eventually fixes the problem. This is best-practice software engineering, so that you can be confident that your fix actually fixes the problem, and that it doesn't reappear in some other refactoring of the code.

[leandernikolaus]

I summarize my understanding of this issue and #224:
The timeoutMsg contains up to 3 different signatures or cryptographic structures.

type TimeoutMsg struct {
	ID            ID              // The ID of the replica who sent the message.
	View          View            // The view that the replica wants to enter.
	ViewSignature QuorumSignature // A signature of the view
	MsgSignature  QuorumSignature // A signature of the view, QC.BlockHash, and the replica ID
	SyncInfo      SyncInfo        // The highest QC/TC known to the sender.
}

• The ViewSignature is a signature on which view is timed out.
• The SyncInfo contains the highQC the sender knows, i.e. a summary of signatures.
• The MsgSignature contains a signature that binds the QC contained in the SyncInfo to the current timeout.

The simple (3phase) hotstuff Variant uses only the ViewSignature and the QC. However, it does not forward the QC to a third party.
Fast hotstuff uses the MsgSignature and also forwards the QC to other parties.

I agree that the MsgSignature should be verified somewhere.
One question. Does FastHotstuff need the ViewSignature?
It seems to me that FastHotstuff should actually verify the MsgSignature instead of the ViewSignature.

[sunwoo383838]

That's a great summary, and you are exactly right.

The core of the issue is that the current implementation of onRemoteTimeout in synchronizer.go tries to handle both the 3-chain (classic HotStuff) and 2-chain (Fast-HotStuff, using AggQC) models with a single logic path, which has led to this problem.

The specific code in question is:

// from onRemoteTimeout in synchronizer.go
if err := s.auth.Verify(timeout.ViewSignature, timeout.View.ToBytes()); err != nil {
	s.logger.Infof("View timeout signature could not be verified: %v", err)
	return
}

As you correctly pointed out, this ViewSignature is only meaningful in the 3-chain model. The most straightforward solution is to conditionally verify the MsgSignature instead of the ViewSignature when the 2-chain model is active (i.e., when ShouldUseAggQC is true and a MsgSignature is present in the TimeoutMsg).

On a related note, the entire concept of a TimeoutCert (TC) also appears to be unnecessary for the 2-chain model. In my local build, I have already been experimenting with removing all TC related operations such as the highTC field and functions like CreateTimeoutCert when not using the 3-chain model, which simplifies the logic considerably.