INTERNET-DRAFT P. Rohatgi draft-irtf-smug-hybrid-src-auth-00.txt IBM Expires Dec 25 1999 June 25 1999 A Hybrid Signature Scheme for Multicast Source Authentication Status of this Memo This document is an Internet-Draft and is NOT offered in accordance with Section 10 of RFC2026, and the author does not provide the IETF with any rights other than to publish as an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Rohatgi [Page 1] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 ABSTRACT This draft describes a compact and fast hybrid signature scheme that can be used to solve the problem of packet source authentication for multicast. The scheme can be viewed as an improvement to off-line/on-line signature schemes, in that the signature size overhead is much smaller although still significant. This scheme offers several advantages over other schemes for multicast source authentication. Firstly, the scheme provides the same security guarantees as regular public key signatures, but the signature computation is an order of magnitude faster. Secondly, this scheme permits each individual packet to be signed independently and efficiently, thus avoiding sender side latency found in schemes which need to spread a signature computation over several outgoing packets in order to achieve efficiency. This makes the scheme suitable in highly interactive settings where latency is an issue. This feature also make the scheme useful in settings where several different signatures need to be computed for by a single server machine for several different, low rate flows. Thirdly, this is an off-line/on-line scheme where most of the computational load is in the off-line stage, thus the scheme is ideally suited to situations where the signer machine has very irregular load. Finally, the scheme produces fixed sized authentication information (or signatures) so that applications know a-priori the authentication overhead. Rohatgi [Page 2] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 TABLE OF CONTENTS Status of This Document ...................................1 ABSTRACT ..................................................2 TABLE OF CONTENTS..........................................3 1 INTRODUCTION.............................................4 1.1 PRIOR/RELATED WORK.....................................4 1.2 INTRODUCTION TO THE HYBRID SOLUTION....................7 2 SIZE REDUCTION TECHNIQUES................................9 2.1 TCRs AND COMMITMENTS...................................9 2.2 OPTIMIZING ANCILLARY INFORMATION......................10 2.3 OPTIMIZING CERTIFICATE SIZE...........................11 3 CONSTRUCTION OF SCHEME FROM CRYPTOGRAPHIC PRIMITIVES....11 3.1 THE PRIMITIVES........................................11 3.2 KEY GENERATION........................................13 3.3 SIGNATURE GENERATION..................................14 3.4 SIGNATURE VERIFICATION................................15 4 PERFORMANCE AND OVERHEAD ANALYSIS.......................16 4.1 SPACE OVERHEAD........................................16 4.2 TIME OVERHEAD.........................................16 4.2.1 KEY GENERATION......................................17 4.2.2 SIGNATURE GENERATION................................17 4.2.3 SIGNATURE VERIFICATION..............................17 REFERENCES................................................18 AUTHOR'S ADDRESSES........................................18 Rohatgi [Page 3] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 1. INTRODUCTION Packet Source Authentication, i.e., authenticating the sender of a received packet, is a fundamental security issue in any networking protocol. In the case of Unicast, this problem has been solved (e.g., in IPSEC) by the use of message authentication codes (MACs). However, the MAC approach is inadequate in a multicast setting, since MACs can be generated by anyone having access to the secret key. In multicast, all authorized receivers would need to know this key in order to verify the integrity of the message packets and thus any receiver can masquerade as any sender in order to attack other receivers. This problem does not arise in unicast where there is only one receiver. The best approach that can solve this problem from a security perspective would be for the sender to digitally sign each packet. Any recipient can then authenticate the packet. The main problem with this approach is performance. Public key signatures using acceptable algorithms and key-lengths are very compute-intensive to generate or to verify or both. As an example, even a high end workstation such as a 200 MHz PowerPC 604e based RS/6000 can generate only 40 or so 1024 bit RSA signatures per second. Clearly, some multicast applications could require a packet rate exceeding 50 packets/s and most applications which require less throughput, nevertheless cannot afford to devote a large fraction of CPU cycles doing signatures. Also, if a server is serving multicast data to several multicast groups, the number of public-key signatures that it can perform per second per group will be severely limited. Thus this solution is not practically feasible. 1.1 PRIOR/RELATED WORK One possible solution to this problem would be to relax the security requirements for authentication. If a certain amount of risk is acceptable, then one could use less-studied signature algorithms. This approach could provide fast yet secure authentication provided the underlying cryptographic assumptions are valid. However, if these assumptions turn out to be invalid, these schemes may be completely open to compromise. Another efficient approach to multicast packet authentication when the security requirement is relaxed was proposed in Canetti et al [3] where the concept of "asymmetric MACs" was introduced. The basic idea in this approach is that the sender knows several secret keys and these keys are shared with the recipients in such a manner so as to maintain several properties of the subsets of keys held by the recipients. For example, one such property could be that no collection of W receivers should know all the keys known by any other receiver. The server can authenticate a message by computing Rohatgi [Page 4] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 MACs using all its secret keys and appending all these MACs to the message (another variant uses more MACs with each MAC being only 1-bit long). This collection of MACs is known as an asymmetric MAC. Each recipient can verify the parts of the asymmetric MAC for which it knows the secret keys and if all these MACs verify then the receiver accepts the message as genuine. Note that a receiver, by itself cannot forge an asymmetric MAC since it does not know all the keys of a sender or even all the keys known to some other recipient. From the property of the subsets described above, even W receivers cannot collude to forge an asymmetric MAC to fool some other recipient. However once there are more than W colluders the security of the scheme could break down and once there are sufficient colluders to know all the sender keys then the scheme breaks down completely. It is easy to see that the number of MAC's computed by the sender has to be a linear function of the number of colluders that the scheme is supposed to be resilient against. Therefore, even though this scheme is useful in many scenarios, e.g., when groups are small and problems of collusion can be controlled, it does not work well in scenarios where the multicast group is very large and large collusions are likely to occur or difficult to detect. The advantage with this approach however is that it can employ well-studied and cryptographically secure MACing schemes and remain secure till the limit on the number of colluders is reached. If reliability of transmission was not an issue, there is another approach known as stream signing by Gennaro et al [5] that could be used to sign the multicast packets efficiently and provide the security guarantees associated with digital signatures. In this approach only one regular signature is transmitted at the beginning of a stream and each packet either contains a cryptographic hash of the next packet in the stream or a 1-time public key using which the next packet, which is signed by the corresponding 1-time private key, can be verified. However, this approach, as specified cannot tolerate a lost packet, since the information needed to authenticate future packets will be lost. While this may not be an issue in reliable internet protocols (such as those based on TCP/IP), it is a major issue for many multicast applications such as those involving audio/video delivery and multicast applications which use UDP over IP-Multicast which is inherently unreliable. In particular, the lack of any standard for reliable multicast over IP means that, for the time being, UDP over IP-Multicast remains the only non-proprietary method available for using multicast over the Internet. Another problem with [5] is that if the stream being sent is not known to the sender in advance then the sender needs to embed 1-time keys and signatures into the packet stream. These keys and signatures are fairly large and can result in a substantial space overhead within each packet. While some of the overhead can be reduced if the sender is allowed to delay outgoing packets, delay is not a viable option for peer-to-peer interactive multicast applications such as distributed simulations/gaming. Rohatgi [Page 5] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 In Wong et al [8], a different approach was proposed for packet authentication when a sender is allowed to delay and group together several consecutive packets. Essentially, this approach forms an authentication tree as in Merkle's scheme [9] from packets collected during a time-interval and signs the root of the authentication tree. Then each packet is augmented by the signature on the root and ancillary information which includes hashes on the logarithmically many nodes on the authentication tree. This allows packet can be individually verified. This approach is quite effective in client-server scenarios where the server is dedicated to serving a small number of multicast flows, each with reasonably smooth flow rates and strictly enforced bounds on processor loading. This approach too suffers from several practical drawbacks when these conditions do not hold. Firstly, as discussed earlier, delaying and grouping of sender's packets is not possible for interactive peer-to-peer interactive multicast applications. Secondly, there is the problem of serving multiple multicast flows. This is best illustrated by the following example. Suppose a server only has enough cycles to perform 10 public key operations per second. Using scheme in [8], such a server could potentially serve a single smooth flow of hundreds of authenticated packets per second with only a minor delay of a fraction of a second. However, if the same server was required to send only 50 different flows, each with a packet rate of only 1 packet/second (such as serving multiple hand held devices) for a total of 50 packets/second throughput, this will not be possible unless the same signing key and authentication tree data structure is shared across different flows or an unacceptable delay of 5 seconds is imposed on each flow. Sharing the signing key and authentication tree data structure across several different unrelated flows would result in a complex software architecture at the sender end, put unreasonable restrictions on the choice of authentication mechanisms across different flows and expose privacy issues with regard to information being shared across different flows. The third practical problem with the scheme is the fact that the size of the authentication information added on to each message is not fixed but depends of the short-term packet rate which in many applications is likely highly irregular. During high traffic periods, the authentication information will also be larger and this can cause additional undesirable side-effects such as increased packet loss due to fragmentation, precisely at times when the traffic volume is large. The fourth problem with the scheme it provides no mechanism to smooth out bursty processor loads. In any real system there will be periods when the processor has enough free time to calculate several signatures/second and there will be times when the processor barely has time to calculate 1-2. With the tree approach, there is no way to leverage the idle time of the CPU to help during the time when it is highly loaded and performance will seriously degrade when the CPU gets loaded. Rohatgi [Page 6] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 1.2 INTRODUCTION TO THE HYBRID SOLUTION We now introduce our approach which could be a possible solution to the problem of packet authentication for multicast in many scenarios and in particular does not suffer from the drawbacks described earlier. Our approach provides the security guarantees required for authentication, yet is efficient in both size and speed and also works in the fully unreliable setting (with additional small but significant overhead). To do so, our approach mimics the public key signature per packet approach which would have been the ideal solution if the speed of well-known public key signature algorithms was not an issue. To mitigate the problem of speed, we start by generalizing the off-line/on-line signature scheme of Even et al [4]. The sender uses regular public key signatures to sign a certificate for the public key of an efficient k-time signature scheme. This certificate is either sent multiple times separately or added on to each data packet or to a large fraction of the data packets. Each packet itself is signed using some i'th use of the k-time signature scheme. The use of k-time signatures which are at least an order of magnitude faster than regular signatures effectively amortizes the cost of the expensive regular signature over k packets. By choosing an appropriate value of k, one can bring up the speed of this hybrid signature scheme to be the same order of magnitude as the the speed of the k-time signature scheme. In practice, speeds of 500-1000 signatures/second are easily achievable for workstation class machines. It is also easy to see that this basic approach solves the problems associated with unreliability, multiple flows, bursty traffic, and irregular processor loading and therefore is a good starting point towards the development of a signature scheme for this problem. Unreliability can be fully addressed by sending the k-time public key certificate in each packet or more practically addressed by sending k-time key certificates multiple times within a flow, to minimize the impact of a few lost packets. The off-line nature of the expensive signature operation when combined with very high throughput of the on-line k-time signature scheme, yields a fairly clean way to handle multiple flows, bursty traffic and bursty processor load : For each flow, buffers of k-time keys and certificates can be precomputed and filled up during periods of low CPU usage and slow traffic to tide over periods of high CPU usage and high traffic. Rohatgi [Page 7] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 However this hybrid approach has a major drawback in that the size of k-time/1-time public keys and/or signatures tend to be impractically large. For example the hybrid approach outlined in the above paragraph when used in conjunction with a reasonably fast and secure k-time signature scheme, could easily result in the size overhead of the order of a kilobyte per packet. This draft describes a combination of techniques to substantially reduce the size overhead associated with the hybrid approach to make it much more practical without compromising on its security. In adopting these techniques, speed of the underlying schemes is also increased but since size is the main focus here, wherever possible we trade the speed improvements for additional size reduction. We address the issue of size in three ways. We first focus on the size overheads in the 1-time/k-time schemes and show how an approach based on commitments and the use of Target Collision Resistant hash functions can reduce the overhead. Next we use a known but rarely used technique to reduce the size of ancillary authentication information that needs to be carried along with the signature, to identify and authenticate the i'th use of a k-time key in cases where the k-time key is created from k independent 1-time keys. Next we describe how the size of a certificate itself can be reduced using known techniques. These three techniques allow us to create reasonably secure hybrid signature schemes which have a per-packet overhead of less than 300 bytes per packet and yet are capable of computing 500-1000 signatures/second on workstation class machines. The rest of the draft is organized as follows. In section 2 we outline the ideas behind our size reduction techniques. In section 3 we provide a concrete construction of the hybrid scheme based on well understood cryptographic primitives. This construction also illustrates the advantages of the size reduction techniques in practice. In section 4 we analyze the performance of one version of our concrete construction if one uses functions derived from the SHA-1 compress function as the basic cryptographic primitives. Rohatgi [Page 8] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 2. SIZE REDUCTION TECHNIQUES 2.1 TCRs and COMMITMENTS Most 1-time or k-time signature schemes have a signature size (and speed) which is proportional to the number of bits in the quantity being signed. Typically, this quantity is taken to be a collision resistant hash of the message being signed. In Bellare et al [1], it was argued that for the purposes of a signature, a weaker condition on the hash function called "Target Collision Resistance" or TCR would suffice (such functions were earlier known as Universal One-Way Hash Functions [7]). In this scenario, instead of requiring a single collision resistant hash function, a family of keyed hash functions with weaker properties could be used. The key specifies a hash function from the family. The signer of a message (the message may even be chosen by an adversary), chooses a hash function at random from the family (by picking a random key) and then computes the hash value and signs both the hash value and the key. The property of the family of hash functions, i.e., Target Collision Resistance, is that even when an adversary chooses a message m_1, when the signer picks a hash function at random, with overwhelming probability (based on the random choice of key) it is computationally difficult for the adversary to come up with another message m_2 such that m_1 and m_2 collide on the hash function chosen by the signer. Thus, target collision resistant hash function families may be much easier to design and have smaller output than collision resistant hash function since many attacks on collision resistant hash functions such as birthday attacks are not applicable. With this weaker notion of Target Collision Resistance, one can reduce the size of the hash of the message that need to be signed without affecting the security of the scheme. However in our application, this is not sufficient to reduce the size of the data which needs to be signed using the 1-time (or k-time) signature scheme since the random key used to choose a specific TCR hash function from the family needs to be signed as well. Ideally, we would have liked the sender to apply the 1-time signature only to the output of the TCR hash function and not on the key. But from the definition of TCR functions, for security reasons, the signer must choose this key after the message has been fixed and this key needs to be authenticated as well. To solve this problem we adopt the following approach: Suppose that in the regular signature on the k-time public key, we include commitments to the keys used to select the TCR hash function in each of the k uses of the k-time signature key. Then for each message, we could sign only its TCR hash value with the one of the k-time signatures and also reveal at the same time the TCR key for that use which was already committed to. With this approach we retain the security of the TCR construction and reduce the size of the message that needs to be singed directly by the k-time scheme by almost a factor of 2 and increase the speed of the underlying k-time scheme by a similar factor. Another well known fact about 1-time or k-time Rohatgi [Page 9] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 signatures is that usually there is a tradeoff between the time it takes for key generation/signature/verification and the size of the keys and the signatures. We can trade in the factor of 2 improvement in speed we obtained by using commitments to realize additional size savings. With this tradeoff, one can, in practice, reduce the space overhead of k-time signature schemes overall by a factor of 3 to make them compact yet fast and secure. 2.2 OPTIMIZING ANCILLARY INFORMATION The next optimization we make is to the ancillary information that needs to be carried along within a k-time signature which identifies the signature as an i'th use, in situations where the k-time scheme is essentially composed of k independent one-time schemes. Typically a k-time public key is created from k one-time public keys by means of a collision resistant hash tree construction over the k public keys, with the root of the hash tree being the k-time public key. When the i'th 1-time key is used to sign a message, then apart from the 1-time signature, the i'th signature must include the i'th public key and hashes of the sibling nodes on the path from the i'th public key to the root of the hash tree. In our construction, we replace the collision resistant hash tree with a TCR hash tree as described in Bellare et al [2]. This has several advantages. Firstly, the use of a TCR function implies that the sizes of all interior nodes in the tree get reduced by half and a single TCR key is used for each level in the tree. Since these level keys will be signed in the certificate for the k-time public key, they need not be sent with each signature. Thus the size overhead for the path gets reduced by a factor of 2. Also, due to reduced sizes of the intermediate nodes, a TCR tree works better with certificate signature schemes which permit message recovery from the signature, since more top level nodes can be accomodated within the embedded signed message. However, the use of a TCR hash tree over Public keys which contain commitments transforms these commitments to weaker primitives which we term "TCR-commitments". These are no longer commitments in the true sense. We coin the term "TCR-commitment" to denote a type of commitment in which it is possible for a committer to later on alter the value committed value but has no incentive to do so. However, the receiver gets no information from the commitment and also cannot create a different consistent opening of the commitment once the committer has opened the commitment. However as far as the properties of unforgeability and non-repudiation are concerned, weakening of commitments to TCR keys within individual 1-time public keys to TCR-commitments in the TCR hash tree calculation does not affect the security and non-repudiation properties of underlying signature scheme. Rohatgi [Page 10] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 2.3 OPTIMIZING CERTIFICATE SIZE. The next optimization is to use padding schemes described in Bellare et al [1], to embed the k-time public key inside the regular signature within the certificate itself for many popular regular public key signature schemes, thus saving on the overhead of transmitting both the k-time public key and its certificate. As mentioned earlier, this when used in conjunction with a TCR hash tree results in additional optimization since more top level TCR tree nodes can be embedded within the signature than top level collision resistant hash tree nodes. 3. CONSTRUCTION OF SCHEME FROM CRYPTOGRAPHIC PRIMITIVES. We now describe our scheme which creates a n^{2}-time key pairs with embedded TCR-commitments to be used in a hybrid scheme involving some other regular signature scheme such as RSA. Currently, a level of security of the order of 2^{80} is considered adequate and our scheme is meant to have a comparable level of security. By adjusting the primitives described below, the scheme can be generalized to give higher levels of security. 3.1 THE PRIMITIVES Our scheme is based on the following primitives, each offering around 80 bits of security. 1. Let H be a collision resistant hash function producing a 160-bit output. 2. Let C be a commitment scheme for 80 bit strings. C provides a C-create function for creating a commitment, a C-decommit function to create a de-commitment string and a C-open function for the receiver to open the commitment from the commitment and de-commitment strings. Although, at the theoretical, abstract and provable level we will use C in our scheme, at the practical construction level we will create our own commitment scheme by requiring more properties from H as described below: Further assume that 2.1 H is at least a weak extractor, i.e., when H is given a high entropy input (with entropy of say least a 100 bytes), its 160-bit output is close to random. This property is fully expected to be met or even exceeded (in terms of entropy required from input) by a function such as SHA-1, given its use for pseudorandom number generation. Rohatgi [Page 11] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 2.2 H is a collision resistant hash function formed by applying the MD method to a collision resistant H-Compress(k,D) function based on fixing some IV for k, where k is a key of size at least 80 bits and D is a fixed sized data block of size more than than 160 bits. 2.3 H-Compress behaves like a family of keyed pseudorandom functions with respect the key k. This property together with the collision resistant property of H-Compress is needed to use H as part of a commitment scheme. In practice, one would realize such a function by defining H-Compress as SHA-1-Compress (and H as SHA-1) and already there are real-world applications, such as the protocol to blind credit card numbers in SET by Krawczyk [6] which depend precisely on these two properties of SHA-1-Compress. With such a function, if we define PadH(x) to be some fixed bijective padding of input string x upto a multiple of the block size of the compression function then H'(r,T) = H(PadH(r)|T) for a large, almost random r of size at least 100 bytes, is a commitment to any string T of size less than the data block size of H-Compress, as well as a collision resistant function on r and T. The de-commit string is just r,T. 3. Let G(K, x) denote a family of keyed one-way functions with an 80 bit key K and 80 bit input x producing a 80 bit output. 4. Let T1(K,x) denote a target collision resistant keyed hash function family taking 80 bit key K and 80n bit input x, producing 80 bit output. 5. Let T2(K,x) denote a target collision resistant keyed hash function family taking an 80 bit key K and 160 bit input x producing a 80 bit output. Rohatgi [Page 12] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 3.2 KEY GENERATION The n^{2}-time public key is essentially derived from n^{2} independent random 1-time public keys hashed down using TCR hash functions in a tree construction (see \[1]). First pick three 80-bit keys g_1, g_2, g_3 uniformly at random. These keys will be used throughout the construction of this n^{2} use public key. Throughout the construction, g(x) = G(g_1, x) will be used as an 80 bit to 80 bit one-way function. For each i, corresponding to the i'th key of the n^{2}-time signature scheme do the following: Pick T_{i}, an 80 bit key uniformly at random. T_{i} will be used for selecting a TCR function when the i'th key is used to sign a message (the k-time public key will include a "commitment" to this key) Pick 23 random 80 bit values, r_{i,1},...,r_{i,23}. From these compute f_{i,1},...,f_{i,23} as follows: For each j in {1,...,22} f_{i,j} = g^{15}(r_{i,j}) and f_{i,23} = g(r_{i,23}). The basic idea behind this construction (which is similar to a construction given in [4]) is that since g is a one-way function any adversary who knows f_{i,j} but not r_{i,j} cannot compute r_{i,j} or even g^{k}(r_{i,j}) for any k < 15 and 1 <= j <= 22. The i'th public key includes in it a "commitment" for the TCR function key to be used for signing the i'th message. Without the commitment, the public key would just be f_{i,1},... ,f_{i,23} or a collision resistant hash of these quantities, i.e., H(f_{i,1} | ... | f_{i,23}). To include a commitment, in a theoretical setting the public key can be defined as follows: Compute T^{c}_{i} = C-create(T_i). Compute PK_i = H(f_{i,1} | .... | f_{i,23}| T^{c}_i) where "|" denotes concatenation. Rohatgi [Page 13] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 Instead, in practice however, we will use PK_i = H'(f_{i,1} | .... | f_{i,23}, T_i) as both a commitment to T_i and a collision resistant hash. The public key for the n^{2}-time signature scheme is then PK = PK_1 | PK_2 | ... | PK_{n^{2}} For the sake of space efficiency (as we mentioned earlier), we do not sign a collision resistant hash of PK. Instead we sign a tree-based TCR hash of PK (as described in [1]). This works as follows: At the leaves are the n^{2} public keys PK_1,...,PK_{n^2} each of which is 160 bits long. At the next higher level in the tree are n^{2} nodes, L_1,...,L_{n^2}, one for each public key. The value of node L_i is just T2(g_2, PK_i), i.e., the TCR hash of PK_i, using the family T2 under key g_2. At the next higher level in the tree are n nodes M_1,...,M_n. Each node M_i has n children, L_{n(i-1)+1},...,L_{ni} and its value is computed as M_i = T1(g_3, L_{n(i-1)+1} | ... | L_{ni}) These n nodes M_1,...,M_n together with g_1, g_2, g_3, constitute the public key for the n^{2}-time signature scheme. Each M_i has an 80 bit value, therefore the n^{2}-time signature scheme has a public key of size 80n + 240 bits. 3.3 SIGNATURE GENERATION To sign a message m with the i'th key of the n^{2}-time signature scheme, the signer does the following: 1. Compute h = T2(T_i, H(m)). This is an 80 bit TCR hash of m, under the assumption that H is collision resistant. 2. Let h_1,...,h_{80} denote the bits of h. Group these bits into 20 groups of 4 consecutive bits (aka nibbles). The value of each is a number from 0 to 15. Let n_1,...,n_{20} denote these numbers. 3. For 1 <= j <= 20, let Y_j = g^{15-n_j}(r_{i,j}). 4. Let N = n_1 + n_2 + ... + n_20. N is a number between 0 and 300 and therefore fits in 9 bits. Let n_{21} denote the value of the least significant 4 bits of N, n_{22} denote the value of the next 4 significant bits and n_{23} denote the value of the most significant 9'th bit. 5. Let Y_{21} = g^{n_{21}}(r_{i,21}). 6. Let Y_{22} = g^{n_{22}}(r_{i,22}). 7. Let Y_{23} = g^{n_{23}}(r_{i,23}). Rohatgi [Page 14] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 The signature then consists of T_i, Y_1,...,Y_{23} together with the values of the n-1 other L nodes which corresponding to the children of M_{(i+n-1)/n}, excluding L_i, i.e., the siblings of L_i. Let Sib(L_i) denote these nodes. Therefore the signature consists of T_i, Y_1,...,Y_{23},Sib(L_i). In the theoretical setting, the signature would include T^{c}_i and T^{d}_{i} = C-decommit(T_i, T^{c}_i) instead of T_i. 3.4 SIGNATURE VERIFICATION To verify a signature S_i = (T_i,Y_1,...,Y_{23},Sib(L_i)) (or S_i = (T^{c}_i, T^{d}_i,Y_1,...,Y_{23},Sib(L_i)) in the theoretical setting) on a message m do the following. 1. In the theoretical setting first use C-open(T^{c}_i, T^{d}_i) to obtain T_i. In the practical setting this step is omitted since T_i is provided. Compute h = T2(T_i, H(m)). This is an 80 bit TCR hash of m. 2. Let h_1...,h_{80} denote the bits of h. Group these bits into 20 groups of 4 consecutive bits. Each group is a number from 0 to 15. Let n_1,...,n_{20} denote these numbers. For 1 <= j <= 20, let f_j = g^{n_j}(Y_i). 3. Let N = n_1 + n_2 + ... n_20. N is a number between 0 and 300 and therefore fits in 9 bits. Let n_{21} denote the value of the least significant 4 bits of N, n_{22} denote the value of the next 4 significant bits and n_{23} denote the value of the most significant 9'th bit. 4. Let f_{21} = g^{15 - n_{21}}(Y_{21}). 5. Let f_{22} = g^{15 - n_{22}}(Y_{22}). 6. Let f_{23} = g^{1 - n_{23}}(Y_{23}). In the theoretical setting compute PK'_i = H(f_{i,1} | .... | f_{i,23} | T^{c}_i), in the practical setting compute PK'_i as PK'_i = H'(f_{1} | .... | f_{23}, T_i). PK'_i is supposed to be the same as PK_i in the key generation phase. Compute L'_i = T2(g_2, PK'_i). L'_i is supposed to be the same as L_i in the key generation phase. To verify this, since all the siblings of L_i are provided as part of the signature, verify that M_{(i+n-1)/n} = T1(g_3, ) where is just the concatenation of the L_i's in the proper order. Rohatgi [Page 15] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 4. PERFORMANCE AND OVERHEAD ANALYSIS Analyzing the performance of the above scheme requires fixing of the primitives being used and the parameters. One needs specific functions for H, G(K, x), T1(K,x) and T2(K,x). H can be taken to be SHA-1. In practice, G, T1 and T2 can all be derived from SHA-1 Compress and in our analysis we will assume that each application of G, T1 and T2 is comparable to an application of SHA-1-Compress. 4.1 SPACE OVERHEAD For typical values of n, (say 6), the size of the 36-time public key which is 80*6 + 240 = 720 bits, is small enough so that it may be embedded inside a signature block itself for popular signature algorithms like RSA and Rabin (e.g., see [1]) which is typically expected to be at 1024 bit block size. Thus the public key and the regular signature on it will occupy 128 bytes in this case. These 128 bytes can either be broadcast frequently or attached to each packet. The actual signature on a message m corresponding to the i'th use of the 36-time public key will have the following overhead: 1. 10 bytes : Disclosure of T_i. 2. 230 bytes : One time signature on h = T2(T_i, m). 3. 50 bytes : Values of the 5 other L nodes corresponding to the other children of M_{(i+5)/6}, i.e., siblings of L_i. This gives a total of 290 bytes. Further optimization of 10 fewer bytes may be obtained in exchange for only a marginal reduction in security if the scheme is modified so that f_{i,23} also serves the dual purpose of T_i. For n = 5, this is reduced to 280 bytes which can be further reduced to 270 bytes by the technique described above. 4.2 TIME OVERHEAD Clearly, the sender does one regular private key operation for the n^{2}-time key and the receiver does one signature verification for the n^{2}-time key. This time varies over the signature algorithm and can be amortized over the n^{2} uses. We now focus on the overhead just for the n^{2} use key. Rohatgi [Page 16] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 4.2.1 KEY GENERATION For efficiency it may be better for the signer to store all intermediate results in the key generation process. For n^{2} uses of the signature, the total amount of overhead is: 1. 240n^{2} + 30 random byte generation. In practice this is likely to be through a pseudorandom process. 2. 22 * 15 n^{2} + n^{2} = 331n^{2} applications of g. 3. n^{2} applications of H on 240 bytes. 4. n^{2} applications of T2. 5. n applications of T1. To get a sense of how many operations these are if we assume for example that an application of T2, T1, g is comparable to a SHA-1 compress, one application of H on 240 bytes of data is comparable to 5 SHA-1 compress and one SHA-1 compress produces 20 random bytes, this time overhead is comparable to 349n^{2} + n + 2 SHA-1 compresses, or on an average 349 SHA-1 compresses per key. On high end workstations, 1000 1-time keys can be produced per second. 4.2.2 SIGNATURE GENERATION If tables are kept at the time of key generation, then the cost of the signature is essentially computing the TCR hash of the message and around 25 table lookups. This will be exceedingly fast in practice. 4.2.3 SIGNATURE VERIFICATION Signature verification is very similar to key generation. However, on an average only 8 applications of g would be needed instead of 15 for each of the nibbles in the TCR hash of the message and no random numbers need to be generated. Thus total number of operations are 1. 8*22 + 1 = 177 applications of g. 2. 1 application of H on 240 bytes. 3. 1 application of T2. 4. 1 application of T1. Carrying the SHA-1 analogy, this translates to roughly 184 applications of SHA-1 Compress. Rohatgi [Page 17] INTERNET DRAFT draft-irtf-smug-hybrid-src-auth-00.txt June 1999 REFERENCES [1] M. Bellare, P. Rogaway. "The exact security of digital signatures: How to sign with RSA and Rabin". Advances in Cryptology - EUROCRYPT '96, Lecture Notes in Computer Science 1070, Springer-Verlag, 1996. [2] M. Bellare, P. Rogaway. "Collision-Resistant Hashing: Towards Making UOWHFs Practical". Advances in Cryptology - CRYPTO '97, Lecture Notes in Computer Science 1294, Springer-Verlag, 1997. [3] R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, B.Pinkas. "Multicast Security: A Taxonomy and Some Efficient Constructions". IEEE INFOCOM '99. [4] S. Even, O. Goldreich, S. Micali. "On-Line/Off-Line Digital Signatures". Journal of Cryptology, 9(1):35--67, 1996. [5] R. Gennaro, P. Rohatgi. "How to sign digital streams". Advances in Cryptology - CRYPTO '97, Lecture Notes in Computer Science 1294, Springer-Verlag, 1997, pp 180--197. [6] H. Krawczyk. "Blinding of credit card numbers in the SET protocol". Financial Cryptography '99. [7] M. Naor, M. Yung. "Universal one-way hash functions and their cryptographic applications". Proceedings of the 21st Annual Symposium on Theory of Computing, 1989. [8] C. Wong, S. Lam. "Digital Signatures for Flows and Multicasts". Proceedings IEEE ICNP '98, Austin TX, Oct 1998. [9] R. Merkle. "A Certified Digital Signature". Advances in Cryptology - CRYPTO '89, 1989. AUTHOR'S ADDRESS Pankaj Rohatgi IBM Thomas J. Watson Research Center P.O. Box 704 Yorktown Heights, NY 10598 Email: rohatgi@watson.ibm.com Rohatgi [Page 18] Expires 25 December 1999