PaperlayerView exact revision on arXiv

Source-linked AI summary

Keeping Authorities "Honest or Bust" with Decentralized Witness Cosigning

Ewa Syta, Iulia Tamas, Dylan Visher, David Isaac Wolinsky, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ismail Khoffi, Bryan Ford

arXiv:1503.08768v4cs.CR

TL;DR

Critical network authorities are attractive attack targets and remain central points of failure even when cryptographically authenticated. The paper introduces CoSi, which has witnesses validate and cosign authoritative statements using scalable collective signatures, and demonstrates signing with 8,192 witnesses in slightly over 2 seconds.

  • Problem

    Critical network authorities remain central points of failure and attractive attack targets because compromise of their keys can enable impersonation and misuse.

  • Method

    CoSi uses witness cosigning, tree-based communication, and compact exception representations to let thousands of witnesses validate and collectively sign authoritative statements.

  • Results

    8,192 cosigning witnesses achieved average per-round collective signing latency of slightly over 2 seconds, with maximum latency under 3 seconds.

  • Takeaways & Limitations

    Witness cosigning provides proactive transparency by making compromised authority keys insufficient for individually signing statements clients accept without witness cosigning.

  • Takeaways & Limitations

    CoSi requires active communication on the signing path and a somewhat selective witness group to avoid Sybil attacks.

Abstract

from arXiv · show

The secret keys of critical network authorities - such as time, name, certificate, and software update services - represent high-value targets for hackers, criminals, and spy agencies wishing to use these keys secretly to compromise other hosts. To protect authorities and their clients proactively from undetected exploits and misuse, we introduce CoSi, a scalable witness cosigning protocol ensuring that every authoritative statement is validated and publicly logged by a diverse group of witnesses before any client will accept it. A statement S collectively signed by W witnesses assures clients that S has been seen, and not immediately found erroneous, by those W observers. Even if S is compromised in a fashion not readily detectable by the witnesses, CoSi still guarantees S's exposure to public scrutiny, forcing secrecy-minded attackers to risk that the compromise will soon be detected by one of the W witnesses. Because clients can verify collective signatures efficiently without communication, CoSi protects clients' privacy, and offers the first transparency mechanism effective against persistent man-in-the-middle attackers who control a victim's Internet access, the authority's secret key, and several witnesses' secret keys. CoSi builds on existing cryptographic multisignature methods, scaling them to support thousands of witnesses via signature aggregation over efficient communication trees. A working prototype demonstrates CoSi in the context of timestamping and logging authorities, enabling groups of over 8,000 distributed witnesses to cosign authoritative statements in under two seconds.

I. INTRODUCTION

Centralized authorities are attractive targets whose compromised keys can enable covert attacks, while existing transparency checks may be delayed, blocked, or privacy-invasive. CoSi introduces scalable witness cosigning so authoritative statements receive collective validation and public exposure before clients accept them.

  • Threat model: Compromised authority keys can enable attackers to impersonate services, issue false credentials, or deliver malicious software to targeted hosts.Authorities include time, certificate, directory, timestamp, and software update services.
  • Threat model: Existing logging and monitoring checks often occur retroactively, require communication, can be blocked by attackers controlling network access, and raise privacy concerns.These systems also introduce log servers as additional central points of failure.
  • CoSi approach: Witness cosigning requires authorities to send proposed statements to a diverse witness group, whose collective signatures provide clients cryptographic evidence without verification-time communication.Witnesses may sanity-check statements for consistency before cosigning, although they need not detect every malicious statement.
  • CoSi approach: An attacker targeting a client that requires W witness signatures must compromise the authority and W witnesses or submit the forged statement to honest witnesses, risking public detection.The latter option exposes the statement to scrutiny even when witnesses do not immediately identify the compromise.
  • Scalable design: CoSi adapts Schnorr multisignatures and communication trees to aggregate thousands of witness signatures into compact, efficiently verifiable collective signatures.The protocol addresses cosignature collection, witness availability, and client verification scalability.
  • Evaluation: 8,000 witnesses distributed with simulated 200ms round-trip delays cosigned statements in about 2 seconds per signing round.The prototype was also evaluated at larger scales and integrated with timestamping and certificate logging authorities.
  • Contributions: The paper contributes a proactive transparency approach, a collective signing protocol scalable to thousands of participants, and an experimental implementation integrated with authority services.The prototype demonstrates practicality in timestamping and certificate logging contexts.

II. BACKGROUND AND MOTIVATION

Critical network services depend on authorities whose compromise or equivocation can mislead clients, while existing defenses provide incomplete or delayed protection. Witness cosigning applies decentralized checking to services including certificates, logs, timestamps, DNS, and directory authorities.

  • Certificate Authorities: Certificate authorities create weakest-link security because any trusted CA can issue fraudulent certificates for any domain if compromised.Stolen CA master keys have been abused to impersonate websites and spy on users.
  • Certificate Authorities: Browser key pinning cannot cover the whole Web, while public-log checking may be limited by delayed checking and dependence on active communication.These limitations motivate adding proactive witness cosigning to certificate services.
  • Tamper-Evident Logging Authorities: Logging authorities are vulnerable to equivocation, allowing false histories or different views to be presented to different clients, including through stolen log-server keys.Such attacks can defeat Certificate Transparency by combining compromised CA and log-server keys.
  • Tamper-Evident Logging Authorities: With N > 3000 independent participants checking and cosigning each log entry, colluding groups of up to 1000 participants cannot successfully equivocate or rewrite history.The paper presents this as a proof-of-concept witness-cosigning extension for Certificate Transparency logs.
  • Time and Timestamp Authorities: Witness cosigning complements coarse-grained timestamping by helping clients detect timestamps that are hours, days, or years inaccurate.Its communication latency likely precludes fine-grained clock synchronization.
  • Directory Authorities: DNSSEC’s dependence on a centrally managed root zone remains a concern; witnessing root-zone signatures with willing TLD operators could enable rapid misuse discovery.The proposed witness group could include operators of more than 1,000 TLDs.
  • Directory Authorities: Tor clients mitigate a compromised directory authority by accepting relay lists only when signed by a majority of a small nine-server consensus group.A compromised authority could otherwise provide only attacker-controlled relays and de-anonymize clients.

E. Software Download and Update Authorities

Software update services are essential but can become attack vectors when signing credentials or vendor infrastructure are compromised. CoSi’s authority-and-witness architecture applies collective validation and logging to authoritative statements, while allowing witnesses to perform application-specific checks.

  • Motivation: Software update services help patch security vulnerabilities promptly but can themselves become attack vectors.Authenticated updates remain exposed when code-signing certificates are available on the black market or vendors leak secret keys.
  • Architecture: CoSi uses an authority and a witness cothority to participate in signing each authoritative statement.The authority initiates signing rounds and proposes statements; witnesses validate and cosign them.
  • Architecture: The authority publishes the witness group’s identities and public keys so verifiers know which participants may cosign statements.For a root CA, the browser’s root certificate can include the witnesses’ public keys alongside the CA’s key.
  • Threat Model: CoSi assumes the authority remains live and highly available, while a policy-defined threshold of witnesses may be offline or under denial-of-service attack.Clients may also impose more complex verification predicates than simple numeric thresholds.
  • Witness Validation: Witnesses can publish logs and perform quick syntactic, semantic, and application-specific checks before signing statements.Examples include checking timestamps, hash-chained log consistency, certificate policies, and revocation status.

D. Schnorr Signatures and Multisignatures

CoSi builds on Schnorr multisignatures, whose aggregate public keys and constant-size signatures allow many signers to produce a jointly verifiable signature. The paper addresses the gap that conventional multisignatures had mainly been practical only for small groups.

  • Schnorr Signatures: Schnorr signatures use a hard discrete-logarithm group, with public key X = G^x derived from secret key x.The paper uses standard elliptic curves in practice and multiplicative-group notation for consistency with prior literature.
  • Schnorr Signatures: Fiat-Shamir makes Schnorr’s challenge non-interactive by hashing the commitment and statement, after which the signer returns a response.The resulting challenge-response pair can be verified by recomputing the commitment from the response and public key.
  • Multisignatures: Schnorr multisignatures aggregate individual public keys and commitment shares, then combine response shares into one collective signature.Anyone can verify the constant-size signature against the statement and aggregate public key.
  • Multisignatures: Every individual public key must be validated with proof of secret-key knowledge to prevent related-key attacks against another participant.Without validation, a dishonest participant could construct a public key that appears to incorporate a victim’s signature share.
  • Scalability Gap: Multisignatures had generally been considered practical only for small groups, around N ≈ 10, motivating CoSi’s scaling work.The paper extends the approach toward thousands of participants while addressing availability challenges.

E. Tree-based Collective Signing

CoSi scales collective signing by distributing communication and computation over a leader-defined spanning tree. Its four-phase protocol aggregates Schnorr commitments and responses into a compact signature that third parties can verify normally.

  • Tree Construction: A spanning tree of depth O(log N) distributes CoSi’s communication and computation costs across participants.The tree optimizes performance and can be reconfigured without changing the protocol’s security properties.
  • Protocol Phases: CoSi’s four phases are announcement, commitment, challenge, and response, forming two communication round-trips through the spanning tree.Bottom-up aggregation collects commitments and responses, while the leader multicasts announcements and the challenge.
  • Protocol Phases: The statement can be announced early for parallel validation or introduced during the challenge phase for late binding.Keeping the first two phases independent of the statement could also support offline preparation, although that variation was not evaluated.
  • Verification: Each node can verify descendant response aggregates using the corresponding partial aggregate public key.A dishonest aggregate commitment cannot produce a correct response without the required discrete logarithm knowledge.
  • Verification: The final collective signature is (c, ˆr0), which third parties verify as a standard Schnorr signature.Verification recomputes the commitment and checks the hash-derived challenge.
  • Security: CoSi’s collective signature remains unforgeable because producing the response requires collective knowledge of every aggregated participant’s secret key.The hash function makes the challenge unpredictable relative to the collective commitment.

F. Accounting for Unavailable Witnesses

CoSi accommodates unavailable witnesses by documenting exceptions in collective signatures while preserving efficient verification. Its proactive validation model also faces delays, communication costs, and a selective-membership constraint.

  • Unavailable witnesses: CoSi lets the leader proceed with any number of missing witnesses and records which witnesses were absent in the collective signature.Verifiers learn both the number and identities of missing witnesses and can apply arbitrary acceptance predicates.
  • Unavailable witnesses: Witness failures can be handled by reporting unreachable participants, reconfiguring the tree, and restarting the signing round without them.The resulting signature includes the challenge, aggregate response, and missing-witness indication.
  • Signature representation: Less than 100 bytes is achievable when nearly all witnesses cosign, using the most compact representation of absent witnesses.CoSi selects among absent-witness lists, present-witness lists, and bitmaps; worst-case size is about 2K + W/8 bytes.
  • Validation: Witness validation can require substantial time and computation, such as rebuilding software, making delays acceptable for some applications but not others.The paper gives reproducible software builds as an example of potentially lengthy validation.
  • Validation: A maximum validation time can preserve signing progress, but allowing unfinished checks weakens transparency from proactive to partly retroactive.Parallel signatures can separately attest that witnesses saw a statement and validated it.
  • Tradeoffs: CoSi requires active, potentially global communication during signing, so it suits periodic or batched activities better than high-volume, low-latency signing.Its witness group also cannot be completely open because unrestricted joining enables Sybil attacks.

IV. DESIGN VARIATIONS AND TRADEOFFS

The paper explores variations that trade certificate size, witness organization, verification policy, and availability against complexity and security properties.

  • Verification predicates: CoSi can verify signatures with arbitrary witness-subset predicates, including weighted thresholds when some witnesses are more trusted than others.The authority may also count its own signature as mandatory while aggregating it with witness signatures.
  • Witness organization: Hierarchical witness groups can impose nested regional thresholds, potentially protecting against compromise or denial of service affecting some regions.The example divides a global witness body into geopolitical regions with separate internal thresholds.
  • Fallback policies: Context-specific verification policies can provide a fallback when massive witness failure or misbehavior prevents the normal threshold from being met.A manufacturer could instruct users to install a subsequent update manually and revise the witness group.
  • Certificate size: The basic design requires the authority certificate to contain every witness public key, which is acceptable when distributed within a larger package such as a browser root store.The paper identifies certificate size as a tradeoff of compact collective signatures.
  • Certificate size: A Merkle-tree commitment can replace the complete witness-key list in the certificate while allowing verifiers to authenticate listed present or missing witnesses.Each signature carries the shorter key list together with Merkle inclusion proofs.
  • Certificate size: With the alternate key-tree design, signatures can grow to O(N) or potentially O(N log N) as more witnesses go missing.When all witnesses are present, the signature is minimal; separate inclusion proofs can increase growth further.

C. Gracefully Tolerating Network Unreliability

CoSi addresses network and witness unreliability through tree rebuilding and adaptive aggregation, while recognizing that severe churn can still undermine progress.

  • Network unreliability: If communication links fail, CoSi allows the authority to rebuild its tree, but severe or frequent network churn may invalidate a tree before use.The limitation remains even when witness servers themselves are reliable.
  • Adaptive aggregation: A binomial swap forest lets witnesses dynamically choose communication partners during aggregation, adapting to intermittent link failures without restarting.This works provided the witnesses themselves remain available.
  • Witness failures: Multiple witnesses becoming unavailable during one round can force repeated restarts and prevent the leader from making progress.The paper motivates protocols that complete each round despite witness behavior.
  • Witness failures: During the Commit phase, witnesses can exclude unreachable children from aggregate commits and report them so the signing round continues immediately.This avoids restarting solely because some children are unresponsive.
  • Witness failures: If a witness disappears after committing, CoSi can preserve consistency by binding the challenge to a Merkle summary of all individual commits.The leader later supplies missing commits and inclusion proofs, allowing verifiers to adjust the aggregate commit.
  • Witness failures: Missing post-Commit witnesses are removed from verification using their committed values and Merkle inclusion proofs.This lets the remaining responses be checked against the adjusted aggregate commit.

E. Extreme Witness Churn and Asynchronous Networks

The paper examines alternatives for extreme churn and asynchronous networks, especially BLS-based aggregation, while identifying unresolved costs for overlapping aggregates.

  • Schnorr limitations: Schnorr-based CoSi requires two communication round-trips, which can fail when a distributed structure becomes unusable between rounds.This is particularly limiting in unstable or asynchronous settings.
  • BLS alternative: BLS signatures may enable single-round-trip collective signing and incremental aggregation for asynchronous protocols.The tradeoff is reliance on pairing-based elliptic curves.
  • Asynchronous aggregation: Overlapping BLS aggregates can double-count a participant, producing a signature with an incorrect repeated key contribution.The example combines AB and BC into a result containing 2x_B.
  • Asynchronous aggregation: Coefficient vectors can track duplicate contributions, but require O(N) communication per aggregation step and O(N) verification computation.Their elements are smaller than full elliptic-curve points, partly mitigating the overhead.
  • Prototype: The prototype implements tree-based collective signing and integrates CoSi with timestamping and Certificate Transparency logging.It uses Schnorr signatures on Ed25519 and includes exception handling for witness failures.
  • Prototype: The timestamp service initiates a signing round every 10 seconds to timestamp batches of documents or nonces.Batching avoids initiating a separate globally communicating round for every client request.

1) Timestamp Request Processing:

The timestamping service batches client requests into Merkle-tree records and uses CoSi to obtain witness-cosigned attestations. Its CT integration adds proactive witness auditing, but client protection depends on supporting inclusion-proof and STH-cosigning behavior.

  • Timestamp Request Processing: Clients submit document hashes, which the timestamp server batches into a Merkle tree and returns with an inclusion proof after a signing round.The server does not transmit the full tree; clients verify inclusion using the hash, timestamp record, certificate, and proof.
  • Timestamp Request Processing: Clients can submit random nonces to obtain fresh, witness-cosigned time attestations that help sanity-check NTP sources.CoSi’s coarse-grained checking complements rather than replaces fine-grained NTP synchronization.
  • Timestamp Request Processing: Witnesses can also serve clients, building local Merkle trees whose roots are aggregated into one global tree during the Commit phase.During the Challenge phase, witnesses receive proofs connecting local roots to the signed global record and complete client inclusion proofs after signing.
  • Certificate Logging: The CT extension attaches collective witness signatures to Signed Tree Heads, allowing witnesses to check log behavior before signing.Current clients may not directly benefit unless they support STH inclusion proofs and collective signatures; signing every timestamp record could be costly at high volume.

VI. EVALUATION

The evaluation tests CoSi’s practicality and scalability against individual-signature and JVSS baselines using large simulated witness groups. CoSi scales gracefully to thousands of witnesses, while competing approaches become impractical at much smaller sizes.

  • Experimental Setup: 33,825 witnesses were evaluated on DeterLab using up to 1,058 witness processes per physical machine.The experiments used a depth-3 tree with branching factor 32 and imposed 200ms round-trip latency between witnesses.
  • Scalability: 8,192 witnesses yielded average per-round CoSi signing latency slightly above 2 seconds before testbed oversubscription dominated performance.Figure 3 averages ten runs and shows minimum-to-maximum latency ranges.
  • Scalability: Naive and NTree approaches become impractical beyond around 256 witnesses because individual signatures increase computation, transmission, and verification costs.NTree additionally concentrates increasing computational load near the top of its communication tree.
  • Scalability: JVSS becomes impractical beyond about 32 witnesses because each participant performs O(N^2) dealing during setup and, for threshold Schnorr signing, every round.Replacing Schnorr with BLS can remove fresh per-round dealing but not the O(N^2) key-generation cost.
  • Computation Costs: CoSi’s most heavily loaded node maintains relatively flat computation cost as the witness group grows, unlike competing schemes whose costs explode beyond a few tens of witnesses.The measured computation time sums CPU time across parallel threads and can exceed wall-clock latency.

D. Network Traffic

CoSi’s tree organization trades depth-related network delay against per-node computation and communication. Larger branching factors reduce measured latency, while oversubscription makes the experimental results conservative.

  • Network Traffic: CoSi’s root network traffic rises much more slowly with witness count than baseline schemes because signature aggregation reduces communication.JVSS places particularly high network burden due to O(N^2) communication complexity.
  • Spanning Tree Configuration: Lower branching factors increase tree depth and add about 200ms of root-to-leaf round-trip latency per added depth unit.They also reduce CPU time and child-coordination communication at each node.
  • Spanning Tree Configuration: For 2,048 witnesses with branching factor 16, tree depth 3 produces collective signing latency below 2 seconds.Computation dominates at depths of 3 or less, whereas network latency begins to dominate at depths of 5 or more.
  • Testbed Oversubscription: Higher oversubscription produces noticeably worse latency, with the effect increasing as witness count and per-machine load rise.The experiments spread witness processes across 8, 16, or 32 physical machines.
  • Testbed Oversubscription: Because oversubscription works against CoSi’s performance, the measured signing times can be treated as conservative bounds for less-loaded deployments.Dedicated or less-overloaded witness servers may perform significantly better.

G. Timestamping Application Scalability

The timestamping prototype distributes request handling across witness servers and demonstrates high aggregate throughput, while integrations with existing authorities appear practical but remain application- and deployment-dependent. The discussion also identifies extensions to certificates, randomness, and other authority systems.

  • Timestamping Application Scalability: 4,096 timestamp/witness servers handled about 320,000 timestamp requests per second in aggregate across the collective.Each of 16 physical machines handled about 20,000 requests per second, despite largely unoptimized and unparallelized server code.
  • Integration: Retrofitting CoSi into the CT log server required about 315 changed lines and less than one person-week in the reported two-process integration.The authors caution that production deployment would require more effort.
  • Scope: The paper’s primary focus is the basic CoSi protocol rather than resolving all issues in particular cothority applications.The authors therefore revisit application implications without claiming to address every application-specific concern.
  • Certificate Authorities: Certificate-cothority deployment would require additional technical, organizational, and political work, including backward compatibility and incremental deployment.The paper leaves detailed integration of witness cosigning into the CA system to future work.
  • Public Randomness Authorities: CoSi can provide a simple collective public-randomness service, but the current prototype cannot guarantee fully unbiased outputs.A malicious leader colluding with f signers can choose among up to 2f possible responses through exception sets.
  • Other Types of Authorities: The tree-based techniques may also apply to blockchain security and performance or to collective decryption for time-lock vaults, key escrows, and fair exchange.These applications are presented as opportunities rather than evaluated deployments.

VIII. RELATED WORK

Related systems address authority security through threshold signing, tamper-evident logs, blockchains, pinning, and distributed trust, but CoSi extends collective witnessing to large witness groups and proactive transparency.

  • Threshold and aggregate signatures provide cryptographic foundations for CoSi, while threshold signatures may hide which authorized signers participated.
  • Tamper-evident logging systems address history rewriting and equivocation through weaker consistency, trusted hardware, or trusted parties.
  • Blockchain-based directory services make deep history rewriting difficult, but clients lack an efficient decentralized way to verify timestamp inclusion without tracking the blockchain or trusting another party.
  • PKI mitigations include browser pinning and certificate logging, but hard-coded coverage is limited and monitoring may not prevent an attacker from creating an accepted fake certificate.
  • COCA and Secure Distributed DNS distribute trust across small groups, reaching at most four and seven servers respectively in reported experiments.
  • CoSi complements software-update transparency systems by greatly increasing the number of independent servers an attacker must compromise to keep a compromise secret.
Loading 1503.08768v4…