Efficient Gossip Protocols for Verifying the Consistency of Certificate Logs

I. INTRODUCTION

• A log can selectively show a fraudulent certificate to targeted victims, so clients need to exchange information to expose split-world attacks.The motivating example is a malicious government using a man-in-the-middle attack while preventing people from reporting it.Source: §I · p. 1
• Gossip must work through existing connections because traditional epidemic protocols generally require membership management or an overlay network.The paper describes peer selection as client-driven: gossip messages travel through standard HTTPS connections, with servers acting as intermediaries.Source: §I · p. 1
• The paper presents gossip protocols, evaluates them with a simulation framework, discusses deployment and implementation, analyzes attacks, and reports a prototype.Source: §I · p. 1

II. BACKGROUND

• Certificate Transparency uses an append-only chronological Merkle tree, with SCTs promising certificate inclusion and STHs identifying signed tree heads.Clients can request audit proofs for certificate inclusion and consistency proofs between tree sizes; the cited CT specification did not yet propose a gossip protocol.Source: §II · pp. 1–2

III. MODEL

• The model includes split-world logs, malicious clients or servers injecting chosen messages, and SCTs whose certificates are never added to the tree.Source: §III · p. 2

IV. DESIRED PROPERTIES

• The protocol should eventually detect inconsistent views, append-only violations, or certificates missing after one MMD, with high probability.Other desired properties include scalability, efficient storage and communication, incremental deployment without dedicated infrastructure, and privacy of visited websites.Source: §IV · p. 2

V. GENERAL FRAMEWORK

• Clients exchange gossip messages through HTTPS requests and responses, then update local state and obtain log proofs when needed.The client selects m1, the server selects m2, and both update after the response is selected; detected anomalies are reported to a monitor.Source: §V · p. 3
• On receiving an SCT, clients fetch the latest STH, a consistency proof against a previous STH when available, and an audit proof for the certificate.Repeating the process for every SCT gives clients a more recent log view, while saving already-processed SCTs reduces connections but can leave the view outdated.Source: §V · pp. 3–4

A. STH-Only Gossiping

• A larger STH preserves the inconsistency-detection value of a smaller one when their consistency has been proven, allowing the protocol to retain only the largest tree head.Source: A. STH-Only Gossiping · p. 4

B. STH-and-Consistency-Proof Gossiping

• Gossiping consistency proofs with STHs aims to reduce log connections while preserving the first protocol’s security properties.The paper also motivates the reduction as a way to make gossip participation harder to infer from client-to-log traffic.Source: B. STH-and-Consistency-Proof Gossiping · p. 4
• Each valid message contains two STHs and the consistency proof between their tree sizes.Source: B. STH-and-Consistency-Proof Gossiping · p. 4
• Pairing the proof with both STHs lets recipients validate the proof and attribute a resulting inconsistency to log misbehavior.An invalid proof sent without both STHs can leave clients unable to determine whether the server or log caused the problem.Source: B. STH-and-Consistency-Proof Gossiping · p. 4
• Clients store message data and audited SCTs, while servers keep valid messages in a map and track the largest STH encountered.Servers select a stored response by the tree size in the client’s message, or send a default message if none is available.Source: B. STH-and-Consistency-Proof Gossiping · p. 4
• When a received message supplies a larger STH, the server updates its largest-head state and may store the message, evicting the smallest-key entry at the configured storage limit.Source: B. STH-and-Consistency-Proof Gossiping · p. 4

• When anomalies are detected, clients and servers stop normal gossip and report and propagate special messages until the problem is fixed.Source: §VII · p. 5
• Warnings are generated for persistent log unresponsiveness, an STH older than one MMD, or an invalid log signature or proof.Source: §VII · p. 5
• Two or more valid, log-signed STHs with conflicting tree size, root hash, or timestamp form an inconsistency message; recipients can immediately distrust the log and propagate it.Source: §VII · p. 5
• Warning recipients independently contact the log to verify the reported problem before treating it as confirmed.Source: §VII · p. 5

• The simulation covers 112 countries, varies the fraction of clients gossiping (factor f), and sets the MMD to two hours with one new STH per MMD.Source: A. Simulation Framework · p. 5
• More than 104 million HTTP and 74 million HTTPS entries from a private 24-hour SWITCH trace inform hourly connection estimates, modeled with a negative binomial distribution.Source: A. Simulation Framework · pp. 5–6
• Website selection uses June 2014 Alexa top-100 domain data for each country and proportionally reduces connections to account for sites outside those lists.Source: A. Simulation Framework · p. 6
• Of 5,107 scanned top-domain servers, 287 (about 5.62%) met the combined HTTPS, certificate-validity, connection, and redirect condition.Source: A. Simulation Framework · p. 6
• Negative binomial event counts are used because variance greatly exceeds the mean, unlike the Poisson model's shared mean-and-variance parameter.Source: A. Simulation Framework · p. 6
• Unless stated otherwise, only scanned servers are assumed CT-enabled and gossiping; they generate about 33.5% of country page views on average, and certificates last 24 months.Source: A. Simulation Framework · p. 6

Simulation scope

• The results cover a 365-day simulation with a 0.1% gossip factor; the 10,000-message storage limit was never reached.The limit was set for the simulation, and the authors report that protocol storage needs remained below it.Source: B. Results · p. 6

STH distribution

• With SCTs saved, more than 78% of clients held an STH over a day old; without saving them, fewer than 26% of gossiping clients lacked one of the last 12 STHs.Figure 4 plots the client distribution by STH age at the end of an MMD.Source: B. Results · p. 7, Figure 4 · p. 7
• About 7.02 million STH queries per MMD were measured without saved SCTs, compared with about 10,000 when SCTs were saved.The latter figure applies to both gossip protocols.Source: B. Results · p. 7

Overhead

• 0.0058% overhead for proof gossip versus 8.58% for STH-only gossip, showing a substantial reduction in log connections.The measurements correspond to about 407.58 versus 602,263.2 log connections per MMD, respectively.Source: B. Results · p. 7

Storage

• Client-side gossip storage was a few kilobytes, while the largest server message map held 4,380 messages after 365 days.A 10,000-message limit would require less than 16 MB and hold more than two years of log data.Source: B. Results · p. 7

Scalability

• Both protocols improve recent-STH distribution with greater participation, while proof gossip has much lower overhead that rises slowly as more servers participate.Even a single gossiping domain, google.com, achieved performance close to that observed with many more servers.Source: B. Results · p. 7, Figure 5 · p. 8

IX. ANALYSIS AND DISCUSSION

• For a single victim, equal-size STHs with different roots expose the split; unequal sizes trigger an unproducible consistency proof and an alert requiring independent confirmation.Different roots provide strong evidence of misbehavior; an alert based on a missing or incorrect proof should be independently confirmed.Source: §IX · p. 8
• A population-wide split is detectable when a gossiping client reaches an unaffected gossiping server, including through travel, if participant numbers suffice.The text gives travel to another country as one way this connection might occur despite a country-wide firewall.Source: §IX · p. 8
• Browser auto-updates may speed client adoption, while manually updated servers may adopt the protocol more slowly.The authors consider slower server uptake acceptable if the protocol scales and its connection and storage costs remain low.Source: §IX · p. 8
• Batching consistency-proof requests and alert verification at regular intervals reduces log requests and duplicate fetches, but delays detection according to the interval.The paper proposes batching rather than requesting proofs immediately when needed.Source: §IX · p. 8
• Gossiping a fraudulent SCT can expose privacy-sensitive information, so users should consent to sharing it.Ordinary gossiped data is expected to be identical across users and not reveal visited domains.Source: §IX · p. 8

X. REALIZATION IN PRACTICE

• HTTP headers conceal whether a client is gossiping from eavesdroppers and allow longer messages, while TLS extensions support TLS services but expose unencrypted handshake messages.TLS handshake fields may add latency, especially in a multi-log setting; HTTP header size is usually configured between 4–16 KB.Source: §X · pp. 8–9
• The Protocol 2 implementation used the CT Python API, Django server middleware, and an HTTP client that exchanged gossip messages in headers and updated local storage.The server checks incoming gossip headers, updates storage, and embeds a selected message in its reply for the client to process.Source: §X · p. 9
• 162 ms average latency covered downloading an STH, consistency proof, or audit proof; verification averaged 68.87 ms for STH validity, 0.17 ms between STHs, and 0.28 ms for SCT audits.The most important computational overhead comes from log signature verification, which the authors say will not be noticed by users because the operations are non-blocking.Source: §X · p. 9

XI. CONCLUSION

• Gossiping both consistency proofs and STHs was the most promising approach for detecting inconsistencies with small overhead in evaluation using real traffic traces.The conclusion reports this as the paper’s evaluation result.Source: §XI · p. 9
• The proposals require no overlay network or dedicated infrastructure and can be incrementally deployed.The authors report that implementation can improve security with small deployment effort and without sacrificing performance or privacy.Source: §XI · p. 9
• The authors state that their concepts may be adapted to other public-log approaches beyond Certificate Transparency.Source: §XI · p. 9