INTERNET-DRAFT Yixian Yang Expires: April 2006 Jian Li Huayi Rao Yongli Tang Beijing University of Posts and Telecom. October 2005 Multi-layer Intrusion Tolerance Based On Threshold(MIT) draft-yang-mit-00.txt Intellectual Property Rights (IPR) statement: By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Status of this Memo By submitting this Internet-Draft, I certify that any applicable patent or other IPR claims of which I am aware have been disclosed, and any of which I become aware will be disclosed, in accordance with RFC 3668. 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. Copyright Notice Copyright (C) The Internet Society (2005). All Rights Reserved. Abstract Multi-layer Intrusion Tolerance Based On Threshold(MITT) is proposed to solve the problems of maintaining acceptable service, despite existing intrusions. MITT integrates redundancy and variety architectures, and utilizes the threshold secret share schemes to implement the survivability of system and to protect confidential data from compromised service in the presence of intrusions. Yixian Yang, et al. Expires April, 2006 [Page 1] INTERNET-DRAFT MIT Based On Threshold October,2005 1 Introduction Intrusion tolerance is the application of fault-tolerance methods to security. It assumes that system vulnerabilities cannot be totally eliminated, and that external attackers or malicious insiders will identify and exploit these vulnerabilities and gain illicit access to the system. The objective of intrusion tolerance is to maintain acceptable, though possibly degraded, service despite intrusions in parts of the system. This paper adopt Multi-layer Intrusion Tolerance Based on Threshold security model, integrates redundancy and variety architectures, at the same time, we utilize the threshold secret share schemes to implement the survivability of system and to protect confidential data from compromised service in the presence of intrusions. Yixian Yang, et al. Expires April, 2006 [Page 2] INTERNET-DRAFT MIT Based On Threshold October,2005 2 related work Despite our best efforts, any sufficiently complex computer system has vulnerabilities. It is safe assume that such vulnerabilities can be exploited by attackers who will be able to penetrate the system. Intrusion tolerance attempts to maintain acceptable service despite such intrusions. The design presents our work on building Multi-layer intrusion tolerance systems namely: user + PS+ OS + DBMS + transaction- layer intrusion tolerance; integrates threshold secret share schemes and variety architectures. 2.1 RSA cryptosystem RSA cryptosystem is the most attractive and popular security technique for many applications, such as electronic commerce and secure internet access. It has to perform modular exponentiation with large exponent and modulus for security consideration. RSA algorithm is a typical public-key cryptosystem. It is a basic technique of many security protocols. It can be described briefly as follows: step 1 Choose two large strong primes, p and q. Let n = pq. step 2 Compute value of n: ¦Õ(n) = (p - 1)(q - 1). step 3 Find a random number e satisfying e of Z¦Õ(n) and gcd (e, ¦Õ(n)) = 1. step 4 Compute a number d such that d = e exp-1 mod ¦Õ(n). step 5 Encryption: Given a message m satisfying m exp e mod n, then the cipher text c = m exp e mod n. step 6 Decryption: m = c exp d mod n. RSA cryptosystem presents a threshold RSA primitive with heuristic security and gives a provably secure threshold RSA primitive in which each user has only one key share but the computation is done in a very complex algebraic structure. Applies combinatory to develop an elegant and simple threshold RSA primitive. Discusses how to add robustness to a threshold RSA primitive and integrates proactive into threshold RSA and presents a simple threshold RSA primitive. All of the above primitives could be used for both threshold decryption and threshold digital signature schemes. gives the first threshold DSS primitive. Yixian Yang, et al. Expires April, 2006 [Page 3] INTERNET-DRAFT MIT Based On Threshold October,2005 2.2 Threshold Cryptography Threshold cryptography is a society-oriented cryptography .In threshold cryptography, the message receiver/signer is not an ordinary individual, but an entity of an organization, such as a department, whose duties are collectively assumed by a group of users of this organization. These users share responsibilities of the entity to decrypt a message or sign a message, which is a desirable way to prevent power abuse. On the other hand, from the viewpoint of an outsider, this role is assumed by a single entity of the organization (the department in the above example). Therefore, the internal structure of the organization is kept secret from outsiders. In threshold cryptography each entity owns a public key and the corresponding private key is shared among a group of users. Any t, 1 ¡Ü b ¡Ü n, of these n users can co-decrypt or co-sign a message, without reconstructing the shared private key. On the other hand, any subset with size less than t, 1 ¡Ü t ¡Ü n, users can neither recover the private key nor co-sign/co-decrypt a message on behalf of the entity. So far several threshold RSA primitives and threshold DSA primitives have been presented in the research community. Presents a more efficient threshold DSS primitive. It also addresses the robustness issue of the threshold DSS primitive. Threshold cryptography has been implemented to achieve fault tolerance, role separation and protection against inside attackers . Potentially it can be employed by organizations such as government and companies. However, threshold cryptography is still not widely used in the real world in spite of its advantages. Yixian Yang, et al. Expires April, 2006 [Page 4] INTERNET-DRAFT MIT Based On Threshold October,2005 3 Architectures In order to making a intrusion tolerant system, which requires in general a multi - layer approach, since attacks could come from any of the following layers: (1) Hardware; (2) PS(Proxy Service); (3) AS (Applications Service); (4) DBMS(Data Base Management Systems); (5) Data Base. A multi-layer approach can be developed along two directions: (1) from scratch; (2) using ¡°off-the-shelf¡± components. Along the from-scratch direction, tamper-resistant processing environments, and trusted PS, trusted OS or trusted DBMS loaders have been applied to close the door on hardware attacks and OS bugs; certified programs and protective compiler extensions can be applied to close the door on many DBMS bugs; and signed checksums (and a small amount of tamper-resistant storage to keep the signing key) have been used to detect OS-level data corruption. 3.1 intrusion prevention level We use some software and hardware to defend the malicious behaviors such as PKI, PMI, firewall and so on. It's a prevent level which is used to prevent the malicious at first. But no assurance can be assumed once the system is compromised. Intrusion tolerance, on the other hand, focuses on providing minimal level of services even when some components have been partially compromised. The next four levels are intrusion tolerance levels, which can tolerate by different ways. 3.2 PS layer PS have an important effect in this architecture so that it is a main aim which intrusive by attackers. We set one PS as the master PS, the others as vice-PS. The master PS do with the request of the clients, then transport the valid request to the AS. If the master PS is intruded or spoils, one vice-PS becomes the master PS, the master PS become a vice-PS when it is repaired. Yixian Yang, et al. Expires April, 2006 [Page 5] INTERNET-DRAFT MIT Based On Threshold October,2005 In order to provide the better intrusion tolerances at this layer, we consider a certificate authorities private key .The system component by CA, proxy severs, administration severs and IDS. The system built on top of threshold cryptography, ensure the security of a CA through a series of defense-in-depth protections. The CA won¡¯t be compromised when a few system components are compromised or some system administrators betray. The private key of a CA is protected by distributed different PS of the key to different (signing) components and by ensuring that any component of the PS is unable to reconstruct the private key. The basic idea of the system is to distribute the certificate signing task from a single CA signing server to a set of PS( proxy servers) which is share servers. we begin by explaining how one shares a private RSA key among a number of Proxy servers. 3.2.1 n-out-of-n sharing Recall that an RSA private key consists of a modulus N and a secret exponent d. The modulus N is a product of two large primes, and d is a positive integer less than N. To decrypt a ciphertext C, one computes C exp d mod N. Similarly to sign a message digest M, one computes M exp d mod N. Hence, both operations require an exponentiation to the power d modulo N. Without the secret exponent d it is believed to be hard to either decrypt ciphertexts or generate signatures. Each PS can be stored on a separate server and yet the private key can be used without having to reconstruct the secret. The basic idea, due to Frankel, is to pick random numbers d1; d2; d3 in the range [-N,N] so that d1 + d2 + d3 = d. We then store share di on share server number i, for i = 1; 2; 3. Note that an attacker who breaks into any two of the three servers learns nothing about the private key d. All three servers must be compromised to obtain d. When a client wishes to apply the key to sign a message M, it sends M to all three servers. Each server applies its own share di to obtain Si = M exp di mod N, and sends the result Si back to the client. The client obtains S1; S2; S3 from the three servers. It multiplies them to obtain the signature S = S1*S2*S3 mod N. Since d = d1 + d2 + d3, we have that S = M exp d mod N as required. Note that the private key d was never reconstructed in order to be used. In addition, there is no communication between the share servers. The only interaction is between the client and each of the servers. Clearly this approach generalizes to distributing a private RSA key among k servers. Even if k-1 of the shares are exposed, an attacker learns nothing about the private key d. Since all k share servers must be involved in applying to key we call this sharing a k-out-of-k sharing. Yixian Yang, et al. Expires April, 2006 [Page 6] INTERNET-DRAFT MIT Based On Threshold October,2005 3.2.2 t-out-of-n sharing There are a number of problems with the approach described above. Most importantly, it is not fault-tolerant. If one of the share servers crashes the entire system collapses . If one of the share servers loses its share, the private key is lost forever. For this reason, we use a t-out-of-n sharing of the secret key; any t of the share servers can be used to apply the key. For instance, if we use a 3-out-of-4 sharing no harm is done if one of the share servers is taken. In addition, a break-in into any two servers reveals no information about the private key. Typically a t-out-of-n sharing is achieved using Shamir's classic secret sharing . Unfortunately, when using Shamir's secret sharing the keys must be reconstructed before they can be used. This is inappropriate for our purposes. Instead, we use a combinatorial construction to obtain a t-out-of-k sharing of d from several n-out- of - n sharing of d. We give two examples. d = d1 + d2 + d3 d = d4 + d5 + d6 3-out-of-4 sharing --------------------------------------------------- |Server 1 | Server 2 | Server 3 | Server 4| --------------------------------------------------- | d1 | d2 | d3 | d3 | --------------------------------------------------- | d4 | d4 | d5 | d6 | --------------------------------------------------- Figure 1: 3-0ut-of-4 sharing scheme of private key d d = d1 + d2 d = d3 + d4 2-out-of-4 sharing --------------------------------------------------- |Server 1 | Server 2 | Server 3 | Server 4| --------------------------------------------------- | d1 | d1 | d2 | d2 | --------------------------------------------------- | d3 | d4 | d3 | d4 | --------------------------------------------------- Figure 2: 2-0ut-of-4 sharing scheme of private key d Yixian Yang, et al. Expires April, 2006 [Page 7] INTERNET-DRAFT MIT Based On Threshold October,2005 In both examples all the di's are random integers in the range [-N,N] satisfying the stated equalities. Each server stores multiple di's as indicated by the column corresponding to that server. Observe that in the example on the left, any three servers can apply the key while any two servers learn nothing about d. The example on the right is more fault tolerant, but compromising two servers reveals the key. A compromise of a single server reveals nothing about the key. More generally, we implemented an algorithm that constructs tables as above for a t-out-of-k sharing for any t and k. When a client requests that the servers apply a private key, it species which coalition of t servers is used. Based on the coalition, each server locally decides which of its di's it will use and sends the resulting Si back to the client. The client multiplies the t responses and obtains the signature S. The client then uses the public key to check the validity of S as a signature. This is done to ensure that all Proxy servers responded properly. The function of the IDS is to detect and surveys the network , PS, CA and administration server. Administration server is used to administrate the private key of PS .In addition ,it can pause the PS or close the PS sometimes. 3.3 AS layer AS layer, which is component by a group of servers, each of which has a function of redundancy, supplies application service to the clients. All the servers which have the same function orbit on different operating systems, and the software of each system have more than one edition. Therefore, it can defend the attack which is aimed at one operating system availably. That is when one server is attacked, the other servers can continue be used. 3.4 DBMS layer At the DBMS layer, we adopt several data base management systems such as Oracle, DB2, SQL server, SYBASE and so on. Because one virus usually fit one OS or one DBMS, it can't avail all kinds of OS and DBMS ,we use a series of different DBMS in different operating systems so that when one DBMS can't be use, but the others can supply service. We put the secret data in different DBMS to make sure it's secure. 3.5 Data base intrusion tolerance layer This layer addresses the following problem: How can we tolerate the successful attacks (or intrusions) into a database system in such a way that the database system can continue delivering essential services in the face of attacks and damage? Yixian Yang, et al. Expires April, 2006 [Page 8] INTERNET-DRAFT MIT Based On Threshold October,2005 While traditional secure database systems rely on preventive controls, an intrusion tolerance data base system can detect intrusions, isolate attacks, contain, assess, and repair the damage caused by intrusions in a timely manner such that a self-stabilized level of database trustworthiness can be provided to applications. In order to keep the data secret, we adopt the secret sharing scheme. The data is divided into two classes. One is common data, which is copied and store, the other is secret data which is distributed among the store node and use a t-out of-n sharing to be sure the data is secret. Yixian Yang, et al. Expires April, 2006 [Page 9] INTERNET-DRAFT MIT Based On Threshold October,2005 4 Evaluation and Analysis 4.1 Security In this design, we use five-layers structure which integrates redundancy and variety architectures, which make the system more harder attacked. Different intrusion tolerance methods used in each layer make the defense more comprehensive. RSA cryptography and threshold cryptography used in intrusion tolerance, make the attackers can¡¯t damage the system as easy as before. 4.2 Validity This design adopt to a improved threshold scheme, which isn¡¯t deal with ring Z¦Õ(n), but we introduce a prime field Zr, which may avoid using ring Z¦Õ(n),because it can cause complex operation. Consequently, we improved validity of scheme. 4.3 Usability The private key is stored by sharing. Even n-t, di are lost or broken down, the system can continue to be operated. Yixian Yang, et al. Expires April, 2006 [Page 10] INTERNET-DRAFT MIT Based On Threshold October,2005 5 Conclusion In this design, several intrusion tolerance methods was adopt to avoid the defended leak because of using only one intrusion tolerance method. Multi-layers intrusion tolerance system which can tolerate kinds of attacks, which make it more harder attacked. Especially, at the second and fifth layers, we used secret sharing, which make the system more security. Yixian Yang, et al. Expires April, 2006 [Page 11] INTERNET-DRAFT MIT Based On Threshold October,2005 6. References [1] Feldman P.A Practical Scheme for Non-interactive Verifiable Secret Sharing. In: Proc.28th Annual Symp. on the Foundations of Computer Science 1109, Springer-Verlag, 1996:157-172 [2] Desmedt Y, Frankel Y, Proc. Crypto¡¯91, Lecture Notes in Computer Science 576, Springer - Verlag, 1992:457-469 [3] J van Leeuwen ed. Handbook of Theoretical Computer Science- Chapter12. Algorithms in Number Theory, Elsevier Science Publishers BV, 1990 [4] Ammann P, Jajodia S, McCollum C D, et al. Surviving Information Warfare Attacks on Database [A], Proceedings of the IEEE Symposium on Security and Privacy[C], New York: IEEE, 1997:164-174 [5] Liu P, Jajodia S. Multi2phase Damage Connement in Database Systems for Intrusion Tolerance[A]. Proc 14th IEEE Computer Security Foundations Workshop[C]. New York: IEEE, 2001: 191-205. [6] Ranger G R, Khosla P K, Bakkaloglu M, et al. Survivable Storage Systems[A] . In DARPA Information Survivability Conference and Exposition ¢ò[C]. New York: IEEE Computer Society, 2001:184-195. [7] Spafford E H, Zamboni D. Intrusion Detection Using Autonomous Agents[J]. Computer Networks, 2000, 34(4):547-570. [8] Frankel Y. A Practical Protocol for Large Group Oriented Networks [A]. Advances in Cryptology¡ªEUROCRYPTp89 [C]. Berlin : Springer - Verlag, 1989:56-61. [9] De Soete M ,Quisquater J J ,Vedder K. A Signature with Shared Verification Scheme. In : Proc. CRYPTO¡¯89 ,Lecture Notes in Computer Science 435 ,Springer - Verlag ,1990 :253¡«262 [10] Croft R A ,Harris S P. Public - key Cryptography and Re - usable Shared Secrets. In : Proc. Cryptography and Coding. Clarendon Press, 1989:189-201 [11] Desmedt Y, Frankel Y. Shared Generation of Authenticators and Signatures. In : Proc. CRYPTO¡¯91, Lecture Notes in Computer Science 576, Springer - Verlag, 1992:457-469 [12] Santis A D, Desmedt Y, Frankel Y, Yung M. How to Share a Function Securely. In :Proc. 26th ACM Symp. on Theory of Computing, IEEE, 1994:522-533 [13] Gennaro R ,Jarecki S , Krawczyk H ,Rabin T. Robust and Efficient Sharing of RSA Functions. In : Proc. CRYPTO¡¯96, Lecture Notes in Computer Science 1109, Springer - Verlag, 1996:157-172 Yixian Yang, et al. Expires April, 2006 [Page 12] INTERNET-DRAFT MIT Based On Threshold October,2005 [14] Shamir A. How to Share a Secret . Commun. ACM, Vol.22,1979:612- 613 [15] Blakley G R. Safeguarding Cryptographic Keys. In : Proc. Nat.Computer Conf. AFIPS Conf. Proc. Vol.48, 1979:313-317 [16] Feldman P. A Practical Scheme for Non - Interactive Verifiable Secret Sharing. In :Proc. 28th Annual Symp. on the Foundations of Computer Science. IEEE ,1987 :427-437 [17] T. P. Pedersen. Distributed Provers with Applications to Undeniable Signatures. In : Proc. EUROCRYPT¡¯91 ,Lecture Notes in Computer Science 547 ,Springer - Verlag ,1991 :221-242 [18] Gennaro ,Jarecki S ,Krawczyk H ,Rabin T. Robust Threshold dss Signatures. In :Proc. EUROCRYPT¡¯96 ,Lecture Notes in Computer Science 1070 ,Springer - Verlag ,1996 [19] Goldreich O ,Micali S ,Wigderson A. How to Play Any Mental Game. In :Proc. 19th Annual Symposiumon the Theory of Computing ,ACM ,1987 :218-229 Yixian Yang, et al. Expires March, 2006 [Page 13] INTERNET-DRAFT Alert Filtration and Fusion September,2005 7. Acknowledgement The authors gratefully acknowledge the contributions of Ming Cao, Xiuling Zhu, Xu Zhu, Xinliu Wang and Shuai Zeng. 8. Authors' Addresses Yixian Yang Information Security Center, Beijing University of posts and telecom.(BUPT), Beijing, China, 100876 Phone: 8610-62283366 Email: yxyang@bupt.edu.cn Full Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf- ipr@ietf.org. Yixian Yang, et al. Expires March, 2006 [Page 14]