Internet DRAFT - draft-yang-mit
draft-yang-mit
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]
