voked by globally updating the group public key and locally updating each unrevoked party’s secret signing key. In this scheme, the verifiers need not maintain a list of individual revocations, but public-key updates must be applied universally to ensure all subsequent signatures can be verified.

Middlebox modification. Middleboxes, like network address translators (NATs), create a conundrum. In our architecture, senders sign all nonvolatile contents of outgoing packets, including source address. Thus, any packets traversing a NAT will no longer verify, as their contents have been changed. While some might consider this a shortcoming, it is a requirement of true attribution; signers can attest only to contents they transmitted. The only other option in our framework is to deem the source address volatile and exclude it from the packet signature. To do so would imply the source address has no significance beyond being a routing locater, though, unfortunately, this is not the case in today’s Internet, where end hosts use source addresses to demultiplex incoming connections, as well as to associate flows, with the appropriate IPsec associations.

This tension has been observed many times in the past, yielding two architecturally pure alternatives: future Internet architectures can either remove end host dependence on IP source addresses or make the presence of middleboxes explicit. For the time being, deployments requiring NAT-like functionality must make a trade-off between deployability and completeness, choosing between removing source addresses from the signature—thereby limiting the scope of the attribution— and encapsulating the original, signed packets in an IP-in-IP tunnel, exposing the middlebox to the receiver.

Related questions concern virtualization technologies. In a virtualized environment, the underlying machine must sign packets. Though technically feasible, we do not expand on specific approaches here.

Pairing-Based Cryptography (PBC) Library15 for group-signature operations that in turn uses the GNU Multiple Precision arithmetic library (GMP). To explore group signatures in the context of real network packets, we implemented Clue as a module in the Click Modular Router. 13 As PBC and GMP are designed as user-mode libraries, Clue employs Click as a user-mode process rather than as a Linux or BSD kernel module. While this architecture incurs some performance penalty on its own, the cryptographic operations dominate the user-mode transitions in practice, and the user-mode penalty does not interfere with fundamental system-design issues.

Figure 1 outlines the packet trailer used by the current prototype. The Clue module is mostly a straightforward packet-transformation element. When signing, the module performs the following four tasks:

˲ ˲Collects nonvolatile elements of an IP packet;

˲ ˲ Adds an 8B local NTP-derived timestamp to implement replay detection;

˲ ˲ Feeds the resulting data as input to the group-signature library to generate a signature; and

˲ ˲ Appends the signature (and additional optimization information) to the original packet, adjusting the IP length field accordingly.

Tasks like recalculating checksums are left to other, standard Click elements in the pipeline performing these functions. Similarly, when verifying, the module performs the following five tasks:

˲ ˲Validates a packet’s freshness from its timestamp;

˲ ˲ Collects the nonvolatile elements
of an IP packet;

figure 1. Clue packet-trailer format; shaded fields are explained in the section on optimizations.

16B

h (for windowed verification)

length
Timestamp

Clue

We developed the Clue prototype to explore the systems issues related to implementing a real-world group-signature scheme. Clue uses Stanford’s