# «Eike Kiltz∗ Anton Mityagin† Saurabh Panjwani‡ Barath Raghavan§ April 30, 2005 Abstract We present a new primitive—Append-only Signatures ...»

• HIBS.Setup(1k ): Run the AOS.Setup(1k ) algorithm to generate a pair (AOS.pk, Sig[ε]) and output it as the master public/private key pair for H IBS.

• HIBS.KeyDel(HIBS.pk, HIBS.SK[I[1..n]], In+1 ): Given the master public key, the secret key of hierarchical identity I[1..n], and a new identity In+1, the delegation algorithm interprets HIBS.SK[I[1..n]] as an A OS signature of I[1..n]. It appends to the signature a message

**In+1 and outputs the resulting signature as the secret key of I[1..n + 1]:**

** HIBS.SK[I[1..n + 1]] ← AOS.Append(HIBS.pk, HIBS.SK[I[1..n]], In ).**

• HIBS.Sign(HIBS.pk, HIBS.SK[In ], M ): Given a master public key, a secret key of the hierarchical identity I[1..n], and a message M, the sign algorithm for H IBS interprets HIBS.SK[I[1..n]] as an A OS signature of I[1..n]. It appends a symbol ∆ to HIBS.SK[I[1..n]] and then appends a message M to the resulting AOS signature to get the ﬁnal signature

**sig:**

sig ← AOS.Append(HIBS.pk, AOS.Append(HIBS.pk, HIBS.SK[I[1..n]], ∆), M ).

** Theorem 4.5 If the AOS scheme A OS = (AOS.**

Setup, AOS.Append, AOS.Vfy) is aos-uf-cma secure, then the HIBS scheme H IBS from Construction 4.4 is hibs-uf-cma secure.

As in Deﬁnition 2.1, adversary B gets input a public key AOS.pk for the A OS scheme. B runs the HIBS-UF-CMA experiment against H IBS as well as an instance of adversary A. B gives as input to A the master public key HIBS.pk = AOS.pk. Adversary B answers the oracle queries of

**adversary A using the oracle AOSSign(·) for A OS as follows:**

the description of the simulation.

It is easy to see that B perfectly simulates the two oracles Corrupt(·) and Sign(·, ·); that is, B’s responses on A’s queries are distributed exactly as in the true HIBS-UF-CMA experiment.

Note that if sig∗ is a valid signature of M ∗ with respect to the hierarchical identity I ∗ [1..n], then sig∗ is also a valid AOS signature on the message M ∗ [1..n + 2].

The fact that ∆ ∈ HIBS.IDSpace ensures that the message M ∗ [1..n + 2] was never queried by B to the oracle AOSSign(·) when simulating the oracle Corrupt(·). Furthermore, if A’s forgery is valid, no preﬁx of the hierarchical identity I ∗ [1..n] can be queried to the oracle Corrupt(·) by A and hence no preﬁx of M ∗ [1..n + 2] was queried to the oracle AOSSign(·) by B. Also, A is not allowed to call oracle Sign(·) for the tuple (I ∗ [1..n], M ∗ ). This ensures that no preﬁx of M ∗ [1..n + 2] was ever queried to oracle AOSSign(·) when simulating oracle Sign(·, ·). Thus, whenever A outputs a valid forgery, B wins AOS-UF-CMA game against A OS.

The above reduction uses the existence of a symbol ∆ such that ∆ ∈ AOS.MSpace but ∆ ∈ HIBS.IDSpace. For the case that HIBS.IDSpace = AOS.MSpace, there is an alternative way of constructing a HIBS from an AOS scheme. We sketch the construction for the interesting binary case—that is, for HIBS.IDSpace = AOS.MSpace = HIBS.MSpace = {0, 1}.

The HIBS secret key of the hierarchical identity I[1..n] is then deﬁned to be the AOS signature of (I1, 0, I2, 0,..., In, 0). The HIBS signature of M under the hierarchical identity I[1..n] is deﬁned as the AOS signature of (I1, 0,..., In, 0, M, 1). The security proof of the resulting HIBS scheme is a natural modiﬁcation of the proof of Theorem 4.5.

4.4 Discussion Given the equivalence between the AOS and HIBS schemes, one can easily transform all our constructions in Section 3 into provably secure HIBS schemes. Note that since the reductions are tight, an eﬃcient AOS implies an eﬃcient HIBS and vice-versa. The advantages of this indirect approach to designing HIBS are twofold. First, AOS is a much simpler primitive than HIBS; security proofs for AOS schemes are easier to carry out than those for HIBS. Second, some of the tricks used in eﬃcient AOS schemes (for example, the hash-tree based construction) could yield more eﬃcient HIBS constructions.

The certiﬁcate-based AOS scheme (Section 3.1) thus naturally transforms a public-key signature scheme into a HIBS scheme. The certiﬁcate-based approach to constructing HIBS schemes was mentioned in [GS02] although this fact appears not to be widely known [CHYC04] and we were not able to ﬁnd any further studies of certiﬁcate-based HIBS in the literature. To the best of our knowledge, we are the ﬁrst to prove security for this scheme. In contrast to identitybased encryption (which is believed to be hard to implement without use of bilinear maps) such HIBS schemes do not utilize pairings, thereby yielding eﬃcient implementations. Moreover, the security proofs are done without using the Random Oracle model.

5 Applications In this section, we describe two practical scenarios in which append-only signatures are directly applicable.

5.1 Wide-area Routing Protocol Security An important application of AOS is in the construction of secure routing protocols for the Internet. The Border Gateway Protocol (BGP), which is the primary routing protocol used today in the Internet, has some well-known security weaknesses which require cryptographic solutions. While there have been many proposals for securing BGP in the past [KLS00, HPS04, SRS+ 04, WKvO05], each must develop its own cryptographic constructions due to the lack of any primitive designed speciﬁcally for this application. In the discussion below, we brieﬂy describe Internet routing and explain how our primitive is useful for ensuring one of the most important security requirements in BGP, namely path authenticity. Indeed, providing a suﬃcient cryptographic primitive for this problem led us to design AOS.

We begin with BGP, the Internet’s primary routing protocol, which is tasked with advertising paths from one network to all other networks. Each network, named by an Autonomous System (AS) number, uses BGP to advertise the sets of IP addresses it is responsible for to its neighbor ASes. Each AS, upon receiving such advertisements, appends itself to the list of ASes on the forwarding path and repropagates the advertisement if it adheres to some local policies. When an AS receives two path advertisements for the same IP address space, it must make a decision as to which it wishes to use for its purposes and also to propagate to neighbors. Finally, once the set of routes have converged, these routes are used for packet forwarding; for each packet, the router looks up the destination IP address and forwards it to the neighbor AS as given by the BGP path advertisement.

Unfortunately, this path advertisement process also allows for any intermediate AS to hijack the process by changing advertisements arbitrarily. For example, if an AS truncates the AS path in an advertisement, then its neighbors will receive an advertisement shorter than the true path (typically causing them to prefer it). In the worst case, an AS can use this attack to convince its neighbors to forward all their traﬃc to it, which it could then modify or drop at will. (There are several other classes of attacks against BGP, but path modiﬁcation and truncation are the most signiﬁcant.) Append-only Signatures can easily be applied to solve this problem as follows. Suppose that an AS R0 wishes to announce routes for some IP preﬁx using the above path advertisement process. It ﬁrst generates an AOS public-private key pair, distributes the public key AOS.pk throughout the network (this can be done with the help of a trusted authority that certiﬁes public keys of ASes as in [KLS00, HPS04, WKvO05]) and to every neighboring AS Ri1, sends the usual BGP information relating to the single-node path (R0 ) along with the AOS signature AOS.Append(AOS.pk, Sig[ε], Ri1 ). In order to continue the advertisement process, Ri1 sends to each of its own neighbors Ri2 a BGP announcement containing the path (R0, Ri1 ) and the AOS signature AOS.Append(AOS.pk, Sig[Ri1 ], Ri2 ). In other words, R0 appends the label of its neighbor Ri1 into the AOS signature chain and Ri1 further appends the label of Ri2 into it3. The This may seem a bit unintuitive because each AS appends the “succeeding” AS’s identity, rather than its own, into the AOS signature. However, this is important to ensure security of the protocol; otherwise, a malicious AS can make a path arbitrarily long by appending random ASes into the path before it ﬁnally appends itself.

The only mischief it can perform in the above protocol is to create an arbitrary loop starting and ending at itself;

this can be easily detected by any downstream AS.

advertisement process continues in this manner until all ASes in the network receive information about a path to R0. Each recipient can verify the validity of the announced path by verifying the corresponding AOS signature using the public key AOS.pk. If the AOS scheme is secure according to our deﬁnition (defn. 2.1), then all that a malicious AS can do is append the label of one of its neighbors into the AOS signature chain (since each neighbor Ri can check that the AS it receives an advertisement from was the last to be appended before Ri 4 ).

In practice, the number of path advertisements received by any AS to a given source AS R0 is extremely small: as observed in real routing data [HPS04], the odds that an AS receives more than 15 path advertisements coming from the same source are about 1 in a 1000. This allows the use of eﬃcient m-time signature schemes (as in Section 3.5), with m equal to 15, in order to implement the AOS scheme in the above protocol and obtain a reasonable level of security.

5.2 Secure Delegation of Resources Fu et al. describe the SHARP system for distributed resource management, in which users wish to share their resources with each other in a fully decentralized system [FCC+ 03]. Central to this system is the notion of a claim—users are issued claims on resources which they present upon resource use. These claims are signed such that they can be veriﬁed to be valid by third parties. Furthermore, users can delegate their claims to others, restricting them in the process.

In this setting, the resource owner wishes to place some restrictions on how her resources are delegated. Their setting allows for a direct application of AOS. Quite simply, each resource provider, when initially issuing a resource claim, appends to an AOS the amount of resources to be given. Upon delegation, subsequent parties simply append to the signature what fraction of the existing claim is to be delegated. Upon claiming resources, the holder of the sub-delegated claim cannot use more than the fraction of the original resources indicated by the AOS signature.

6 Final Remarks and Open Problems

6.1 Finalization of AOS signature An interesting feature of append-only signature schemes which might be needed by some applications is the ability to “ﬁnalize” the signature, that is, to modify the signature of a message in the way which prohibits any further appending. The general solution to this problem is to use a special symbol Θ (from the message space) to denote the end of the message. When one wants to ﬁnalize the signature of some message, he should append Θ to the signature. Messages that contain symbol Θ in the middle of the message (not as the last symbol) are therefore considered to be invalid.

6.2 Restricted AOS In AOS, anyone can append and verify signatures. In certain scenarios, however, one may want to restrict the ability to append messages to a limited group of users. Still, anyone should be able to verify the signatures. We call this extension of AOS Restricted Append-Only Signatures (RAOS).

The security of this solution relies on the assumption that AS-to-AS links are authenticated in some standard manner, for example using Message Authentication Codes (MACs) or existing infrastructure like IPSec, as done in [HPS04, WKvO05]. Also, the AOS-based approach is not resilient to collusions between multiple malicious ASes, as is the case with all proposals for securing BGP that we are aware of.

Let U be a group of users allowed to perform the append operation. We assume that all members of the group U are given some key K of an (symmetric) encryption scheme EN C = (ENC, DEC).

We modify a given AOS scheme to get a RAOS scheme as follows: Deﬁne the RAOS signature of a message M [1..n] = (M1,..., Mn ) as the tuple

** Sig′ = (ENCK (Sig(M [1..n])), Sig(M1,..., Mn, Θ)),**

where Θ is the ﬁnalization symbol from the last paragraph. In order to append the message Mn+1 to a given RAOS signature on M [1..n], a member of the group U decrypts the ﬁrst part of the RAOS signature with her key K to obtain Sig(M [1..n]). She then appends Mn+1 using the original AOS.Append algorithm. Finally, she outputs the new RAOS signature tuple by encrypting Sig(M [1..n+1]) and appending Θ to Sig(M [1..n+1]). Note that without knowledge of the key K, the AOS signature Sig(M [1..n]) remains secret and hence appending cannot be performed. Public veriﬁcation is done by verifying if the second part of the RAOS signature is a valid AOS signature on the message (M1,..., Mn, Θ).

6.3 Shorter AOS signatures Given that wide-area routing protocols propagate a large number of messages, compact signatures are desirable. Thus we raise an open problem of whether it is possible to build an AOS scheme with constant signature length (in both message length and maximal message length).

This problem is equivalent to building a HIBS scheme where secret keys of the users have constant length (in the depth of the given user in the hierarchy and in the maximal depth of the hierarchy).

So far the best we can get is the construction from Section 3.3 which provides an AOS √ scheme that can sign messages of length up to n symbols with signatures of length O( n). This construction translates to a HIBS scheme with n-level deep hierarchy, where the secret key of √ each user has length O( n).

Acknowledgments We would like to thank Mihir Bellare (for suggesting an improvement to the proof of Theorem 3.1) and Daniele Micciancio (for some useful insight about the deﬁnition of AOS). Thanks also to the anonymous reviewers for pointing out errors and suggesting improvements.

References [AR00] Michel Abdalla and Leonid Reyzin. A new forward-secure digital signature scheme.