go-f3 is Vulnerable to Cached Justification Verification Bypass

@@ -60,11 +60,11 @@ func (d *Driver) RequirePrepareAtRound(round uint64, value *gpbft.ECChain, justi
 	d.require.NotNil(msg)
 	instance := d.host.getInstance(msg.Vote.Instance)
 	d.require.NotNil(instance)
-	d.require.Equal(gpbft.PREPARE_PHASE, msg.Vote.Phase)
-	d.require.Equal(round, msg.Vote.Round)
-	d.require.True(value.Eq(msg.Vote.Value))
-	d.require.Equal(instance.id, msg.Vote.Instance)
-	d.require.Equal(instance.supplementalData, msg.Vote.SupplementalData)
+	d.require.Equal(gpbft.PREPARE_PHASE, msg.Vote.Phase, "phase different: expected %s, got %s", gpbft.PREPARE_PHASE, msg.Vote.Phase)
+	d.require.Equal(round, msg.Vote.Round, "round different")
+	d.require.True(value.Eq(msg.Vote.Value), "value different")
+	d.require.Equal(instance.id, msg.Vote.Instance, "instance different")
+	d.require.Equal(instance.supplementalData, msg.Vote.SupplementalData, "supplemental data different")
 	d.requireEqualJustification(justification, msg.Justification)
 	d.require.Empty(msg.Ticket)
 
@@ -85,7 +85,7 @@ func (d *Driver) RequireCommit(round uint64, vote *gpbft.ECChain, justification
 	d.require.Equal(instance.supplementalData, msg.Vote.SupplementalData)
 	d.require.Equal(instance.id, msg.Vote.Instance)
 	d.require.True(vote.Eq(msg.Vote.Value))
-	d.requireEqualJustification(justification, justification)
+	d.requireEqualJustification(justification, msg.Justification)
 	d.require.Empty(msg.Ticket)
 
 	d.require.NoError(d.deliverMessage(msg))
@@ -107,13 +107,22 @@ func (d *Driver) RequireConverge(round uint64, vote *gpbft.ECChain, justificatio
 	d.require.NoError(d.deliverMessage(msg))
 }
 
+// Must panics if err is non-nil, otherwise returns v.
+func Must[V any](v V, err error) V {
+	if err != nil {
+		panic(err)
+	}
+	return v
+}
+
 func (d *Driver) requireEqualJustification(one *gpbft.Justification, other *gpbft.Justification) {
 	if one == nil || other == nil {
 		d.require.Equal(one, other)
 	} else {
-		d.require.Equal(one.Signature, other.Signature)
-		d.require.Equal(one.Signers, other.Signers)
+		d.require.Equal(Must(one.Signers.All(100000)), Must(other.Signers.All(100000)), "signers different")
+		d.require.EqualExportedValues(one.Vote, other.Vote)
 		d.require.True(one.Vote.Eq(&other.Vote))
+		d.require.Equal(one.Signature, other.Signature, "signature different")
 	}
 }
 

@@ -225,7 +225,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 			Vote:   instance.NewCommit(0, &gpbft.ECChain{}),
 		})
 
-		evidenceOfCommitForBottom := instance.NewJustification(0, gpbft.COMMIT_PHASE, &gpbft.ECChain{}, 0, 1)
+		evidenceOfCommitForBottom := instance.NewJustification(0, gpbft.COMMIT_PHASE, nil, 0, 1)
 
 		driver.RequireConverge(1, baseChain, evidenceOfCommitForBottom)
 		driver.RequireDeliverMessage(&gpbft.GMessage{
@@ -342,7 +342,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 		driver.RequireStartInstance(futureInstance.ID())
 		driver.RequireQuality()
 		driver.RequirePrepare(futureInstance.Proposal())
-		driver.RequireCommit(0, futureInstance.Proposal(), instance.NewJustification(0, gpbft.PREPARE_PHASE, futureInstance.Proposal(), 0, 1))
+		driver.RequireCommit(0, futureInstance.Proposal(), futureInstance.NewJustification(0, gpbft.PREPARE_PHASE, futureInstance.Proposal(), 0, 1))
 	})
 
 	t.Run("Rebroadcasts selected messages on timeout", func(t *testing.T) {
@@ -379,7 +379,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 		})
 
 		// Expect progress to COMMIT with strong evidence of PREPARE.
-		evidenceOfPrepare := instance.NewJustification(0, gpbft.PREPARE_PHASE, instance.Proposal(), 0, 1)
+		evidenceOfPrepare := instance.NewJustification(0, gpbft.PREPARE_PHASE, baseChain, 0, 1)
 		driver.RequireCommit(0, baseChain, evidenceOfPrepare)
 
 		// Expect no messages until the rebroadcast timeout has expired.
@@ -463,6 +463,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 
 		futureRoundProposal := instance.Proposal().Extend(tipSet4.Key)
 		evidenceOfPrepareAtRound76 := instance.NewJustification(76, gpbft.PREPARE_PHASE, futureRoundProposal, 0, 1)
+		evidenceOfPrepareAtRound77 := instance.NewJustification(77, gpbft.PREPARE_PHASE, futureRoundProposal, 0, 1)
 
 		// Send Prepare messages to facilitate weak quorum of prepare at future round.
 		driver.RequireDeliverMessage(&gpbft.GMessage{
@@ -480,7 +481,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 		// Expect skip to round.
 		driver.RequireConverge(77, futureRoundProposal, evidenceOfPrepareAtRound76)
 		driver.RequirePrepareAtRound(77, futureRoundProposal, evidenceOfPrepareAtRound76)
-		driver.RequireCommit(77, futureRoundProposal, evidenceOfPrepareAtRound76)
+		driver.RequireCommit(77, futureRoundProposal, evidenceOfPrepareAtRound77)
 		// Expect no messages until the rebroadcast timeout has expired.
 		driver.RequireNoBroadcast()
 		// Trigger rebroadcast alarm.
@@ -492,7 +493,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 		//
 		// See: https://github.com/filecoin-project/go-f3/issues/595
 		driver.RequireQuality()
-		driver.RequireCommit(77, futureRoundProposal, evidenceOfPrepareAtRound76)
+		driver.RequireCommit(77, futureRoundProposal, evidenceOfPrepareAtRound77)
 		driver.RequirePrepareAtRound(77, futureRoundProposal, evidenceOfPrepareAtRound76)
 		driver.RequireConverge(77, futureRoundProposal, evidenceOfPrepareAtRound76)
 		driver.RequireNoBroadcast()
@@ -501,7 +502,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 		driver.RequireDeliverMessage(&gpbft.GMessage{
 			Sender:        1,
 			Vote:          instance.NewCommit(77, futureRoundProposal),
-			Justification: evidenceOfPrepareAtRound76,
+			Justification: evidenceOfPrepareAtRound77,
 		})
 
 		// Expect DECIDE with strong evidence of COMMIT.
@@ -651,7 +652,7 @@ func TestGPBFT_WithEvenPowerDistribution(t *testing.T) {
 				Vote:   instance.NewPrepare(0, instance.Proposal().BaseChain()),
 			})
 			// Assert COMMIT phase for base decision.
-			driver.RequireCommit(0, instance.Proposal().BaseChain(), instance.NewJustification(0, gpbft.PREPARE_PHASE, instance.Proposal(), 0, 1))
+			driver.RequireCommit(0, instance.Proposal().BaseChain(), instance.NewJustification(0, gpbft.PREPARE_PHASE, instance.Proposal().BaseChain(), 0, 1))
 		}
 		t.Run("Justification of CONVERGE to bottom from next round completes phase", func(t *testing.T) {
 			instance, driver := newInstanceAndDriver(t)
@@ -783,7 +784,7 @@ func TestGPBFT_WithExactOneThirdToTwoThirdPowerDistribution(t *testing.T) {
 				Vote:   instance.NewPrepare(0, baseChain),
 			},
 		)
-		driver.RequireCommit(0, baseChain, instance.NewJustification(0, gpbft.PREPARE_PHASE, baseChain, 1, 0))
+		driver.RequireCommit(0, baseChain, instance.NewJustification(0, gpbft.PREPARE_PHASE, baseChain, 1))
 
 		// Trigger timeout of COMMIT phase to force a scheduled re-broadcast.
 		driver.RequireDeliverAlarm()

@@ -992,7 +992,7 @@ func TestParticipant_ValidateMessage(t *testing.T) {
 			wantErr: "has justification from wrong round",
 		},
 		{
-			name: "justification with invalid value is error",
+			name: "justification with different value is error",
 			msg: func(subject *participantTestSubject) *gpbft.GMessage {
 				subject.mockValidSignature(somePowerEntry.PubKey, signature)
 				return &gpbft.GMessage{
@@ -1007,13 +1007,14 @@ func TestParticipant_ValidateMessage(t *testing.T) {
 					Justification: &gpbft.Justification{
 						Vote: gpbft.Payload{
 							Instance:         initialInstanceNumber,
+							Phase:            gpbft.PREPARE_PHASE,
 							Value:            &gpbft.ECChain{TipSets: []*gpbft.TipSet{subject.canonicalChain.Base(), {PowerTable: subject.supplementalData.PowerTable}}},
 							SupplementalData: *subject.supplementalData,
 						},
 					},
 				}
 			},
-			wantErr: "invalid justification vote value chain",
+			wantErr: "has invalid justification vote value chain",
 		},
 	}
 	for _, test := range tests {

@@ -338,39 +338,24 @@ func (v *cachingValidator) validateJustification(ctx context.Context, valueKey *
 	partial := valueKey != nil
 	cacheNamespace := validationNamespaces.justification(partial)
 
-	// It doesn't matter whether the justification is partial or not. Because, namespace
-	// separates the two.
-	cacheKey, err := v.getCacheKey(msg.Justification)
-	var alreadyValidated bool
-	if err != nil {
-		log.Warnw("failed to get cache key for justification", "partial", partial, "err", err)
-		// If we can't compute the cache key, we can't cache the justification. But we
-		// can still validate it.
-		cacheKey = nil
-	} else {
-		// Only cache the justification if:
-		//  * marshalling it was successful, and
-		//  * it is not yet present in the cache.
-		if alreadyValidated, err = v.isAlreadyValidated(msg.Vote.Instance, cacheNamespace, cacheKey); err != nil {
-			log.Warnw("failed to check if justification is already cached", "partial", partial, "err", err)
-		} else if alreadyValidated {
-			metrics.validationCache.Add(ctx, 1, metric.WithAttributes(attrCacheHit, attrCacheKindJustification, attrPartial(partial)))
-			return nil
-		} else {
-			metrics.validationCache.Add(ctx, 1, metric.WithAttributes(attrCacheMiss, attrCacheKindJustification, attrPartial(partial)))
-		}
-	}
-
 	// Check that the justification is for the same instance.
 	if msg.Vote.Instance != msg.Justification.Vote.Instance {
 		return fmt.Errorf("message with instanceID %v has evidence from instanceID: %v", msg.Vote.Instance, msg.Justification.Vote.Instance)
 	}
 	if !msg.Vote.SupplementalData.Eq(&msg.Justification.Vote.SupplementalData) {
 		return fmt.Errorf("message and justification have inconsistent supplemental data: %v != %v", msg.Vote.SupplementalData, msg.Justification.Vote.SupplementalData)
 	}
+
 	// Check that justification vote value is a valid chain.
 	if err := msg.Justification.Vote.Value.Validate(); err != nil {
-		return fmt.Errorf("invalid justification vote value chain: %w", err)
+		return fmt.Errorf("has invalid justification vote value chain: %w", err)
+	}
+
+	zeroKey := (&ECChain{}).Key()
+	msgKey := valueKey
+	if !partial {
+		key := msg.Vote.Value.Key()
+		msgKey = &key
 	}
 
 	// Check every remaining field of the justification, according to the phase requirements.
@@ -379,27 +364,27 @@ func (v *cachingValidator) validateJustification(ctx context.Context, valueKey *
 	// Anything else is disallowed.
 	expectations := map[Phase]map[Phase]struct {
 		Round uint64
-		Value *ECChain
+		Key   *ECChainKey
 	}{
 		// CONVERGE is justified by a strong quorum of COMMIT for bottom,
 		// or a strong quorum of PREPARE for the same value, from the previous round.
 		CONVERGE_PHASE: {
-			COMMIT_PHASE:  {msg.Vote.Round - 1, &ECChain{}},
-			PREPARE_PHASE: {msg.Vote.Round - 1, msg.Vote.Value},
+			COMMIT_PHASE:  {msg.Vote.Round - 1, &zeroKey},
+			PREPARE_PHASE: {msg.Vote.Round - 1, msgKey},
 		},
 		// PREPARE is justified by the same rules as CONVERGE (in rounds > 0).
 		PREPARE_PHASE: {
-			COMMIT_PHASE:  {msg.Vote.Round - 1, &ECChain{}},
-			PREPARE_PHASE: {msg.Vote.Round - 1, msg.Vote.Value},
+			COMMIT_PHASE:  {msg.Vote.Round - 1, &zeroKey},
+			PREPARE_PHASE: {msg.Vote.Round - 1, msgKey},
 		},
 		// COMMIT is justified by a strong quorum of PREPARE from the same round with the same value.
 		COMMIT_PHASE: {
-			PREPARE_PHASE: {msg.Vote.Round, msg.Vote.Value},
+			PREPARE_PHASE: {msg.Vote.Round, msgKey},
 		},
 		// DECIDE is justified by a strong quorum of COMMIT with the same value.
 		// The DECIDE message doesn't specify a round.
 		DECIDE_PHASE: {
-			COMMIT_PHASE: {math.MaxUint64, msg.Vote.Value},
+			COMMIT_PHASE: {math.MaxUint64, msgKey},
 		},
 	}
 
@@ -410,25 +395,15 @@ func (v *cachingValidator) validateJustification(ctx context.Context, valueKey *
 				return fmt.Errorf("message %v has justification from wrong round %d", msg, msg.Justification.Vote.Round)
 			}
 
-			// There are 4 possible cases:
-			// 1. The justification is from a complete message with a non-zero value
-			// 2. The justification is from a complete message with a zero value
-			// 3. The justification is from a partial message with non-zero value key
-			// 4. The justification is from a partial message with zero value key
-			//
-			// In cases 1 and 2, the justification vote value must match the expected value
-			// exactly.
-			//
-			// Whereas in cases 3 and 4, the justification vote can't directly be checked and
-			// instead we rely on asserting the value via signature verification. Because the
-			// signing payload uses the value key only.
-			if partial {
-				expectedVoteValueKey = *valueKey
-			} else {
-				if !msg.Justification.Vote.Value.Eq(expected.Value) {
+			// The key can be either the value key or the zero key.
+			// Depending on which type of justification we are dealing with,
+			// if message is not partial, then check the justification Value is same as the expected Value
+			expectedVoteValueKey = *expected.Key
+			if !partial {
+				justificationVoteValueKey := msg.Justification.Vote.Value.Key()
+				if !bytes.Equal(justificationVoteValueKey[:], expected.Key[:]) {
 					return fmt.Errorf("message %v has justification for a different value: %v", msg, msg.Justification.Vote.Value)
 				}
-				expectedVoteValueKey = expected.Value.Key()
 			}
 		} else {
 			return fmt.Errorf("message %v has justification with unexpected phase: %v", msg, msg.Justification.Vote.Phase)
@@ -437,18 +412,30 @@ func (v *cachingValidator) validateJustification(ctx context.Context, valueKey *
 		return fmt.Errorf("message %v has unexpected phase for justification", msg)
 	}
 
-	// Check justification power and signature.
-	justificationPower, signers, err := msg.Justification.GetSigners(comt.PowerTable)
+	cacheKey, err := v.getCacheKey(msg.Justification, expectedVoteValueKey[:])
+	var alreadyValidated bool
 	if err != nil {
-		return fmt.Errorf("failed to get justification signers: %w", err)
-	}
-	if !IsStrongQuorum(justificationPower, comt.PowerTable.ScaledTotal) {
-		return fmt.Errorf("message %v has justification with insufficient power: %v :%w", msg, justificationPower, ErrValidationInvalid)
+		log.Warnw("failed to get cache key for justification", "partial", partial, "err", err)
+		// If we can't compute the cache key, we can't cache the justification. But we
+		// can still validate it.
+		cacheKey = nil
+	} else {
+		// Only cache the justification if:
+		//  * marshalling it was successful, and
+		//  * it is not yet present in the cache.
+		if alreadyValidated, err = v.isAlreadyValidated(msg.Vote.Instance, cacheNamespace, cacheKey); err != nil {
+			log.Warnw("failed to check if justification is already cached", "partial", partial, "err", err)
+		} else if alreadyValidated {
+			metrics.validationCache.Add(ctx, 1, metric.WithAttributes(attrCacheHit, attrCacheKindJustification, attrPartial(partial)))
+			return nil
+		} else {
+			metrics.validationCache.Add(ctx, 1, metric.WithAttributes(attrCacheMiss, attrCacheKindJustification, attrPartial(partial)))
+		}
 	}
 
-	payload := msg.Justification.Vote.MarshalForSigningWithValueKey(v.networkName, expectedVoteValueKey)
-	if err := comt.AggregateVerifier.VerifyAggregate(signers, payload, msg.Justification.Signature); err != nil {
-		return fmt.Errorf("verification of the aggregate failed: %+v: %w", msg.Justification, err)
+	err = v.validateJustificationSignature(comt, msg.Justification, expectedVoteValueKey)
+	if err != nil {
+		return fmt.Errorf("internal justification validation failed: %w", err)
 	}
 
 	if len(cacheKey) > 0 {
@@ -461,6 +448,27 @@ func (v *cachingValidator) validateJustification(ctx context.Context, valueKey *
 	return nil
 }
 
+func (v *cachingValidator) validateJustificationSignature(comt *Committee, justif *Justification, expectedVoteValueKey ECChainKey) error {
+	// It doesn't matter whether the justification is partial or not. Because, namespace
+	// separates the two.
+
+	// Check justification power and signature.
+	justificationPower, signers, err := justif.GetSigners(comt.PowerTable)
+	if err != nil {
+		return fmt.Errorf("failed to get justification signers: %w", err)
+	}
+	if !IsStrongQuorum(justificationPower, comt.PowerTable.ScaledTotal) {
+		return fmt.Errorf("has justification with insufficient power: %v :%w", justificationPower, ErrValidationInvalid)
+	}
+
+	payload := justif.Vote.MarshalForSigningWithValueKey(v.networkName, expectedVoteValueKey)
+	if err := comt.AggregateVerifier.VerifyAggregate(signers, payload, justif.Signature); err != nil {
+		return fmt.Errorf("verification of the aggregate failed: %+v: %w", justif, err)
+	}
+
+	return nil
+}
+
 func (v *cachingValidator) isAlreadyValidated(group uint64, namespace validatorNamespace, cacheKey []byte) (bool, error) {
 	alreadyValidated, err := v.cache.Contains(group, namespace, cacheKey)
 	if err != nil {
@@ -469,10 +477,13 @@ func (v *cachingValidator) isAlreadyValidated(group uint64, namespace validatorN
 	return alreadyValidated, nil
 }
 
-func (v *cachingValidator) getCacheKey(msg cbor.Marshaler) ([]byte, error) {
+func (v *cachingValidator) getCacheKey(msg cbor.Marshaler, additionalFields ...[]byte) ([]byte, error) {
 	var buf bytes.Buffer
 	if err := msg.MarshalCBOR(&buf); err != nil {
 		return nil, fmt.Errorf("failed to get cache key: %w", err)
 	}
+	for _, field := range additionalFields {
+		_, _ = buf.Write(field)
+	}
 	return buf.Bytes(), nil
 }

@@ -13,8 +13,6 @@ import (
 func TestHashTree(t *testing.T) {
 	for i := 1; i < 256; i++ {
 		t.Run(fmt.Sprintf("Length/%d", i), func(t *testing.T) {
-			t.Parallel()
-
 			test := make([][]byte, i)
 			for j := range test {
 				test[j] = []byte{byte(j)}