Use the Keys Pre-Distribution KDP-scheme for Mandatory Access Control Implementation
S. V. Belim S. Yu. Belim



Use the Keys Pre-Distribution KDP-scheme for Mandatory Access Control Implementation  






S.V. Belim, S.Yu. Belim 

Dostoevsky Omsk State University, Omsk, Russia
 






Abstract



The possibility of use the keys preliminary distribution KDP-scheme for mandatory access control
realization in the distributed systems with user's hierarchy is considered. The modified keys
preliminary distribution algorithm is suggested. It is developed a method for creation of subsets
family for solution this task.


Keywords: keys pre-distribution scheme, KDP-scheme, security model, mandatory access
control.




§ INTRODUCTION


Mandatory differentiation of access is more rigorous in comparison with a discretionary analog. 
The centralized security subsystem is necessary for its realization. At system there has 
to be a uniform center of a decision making comparing mandates of access. This problem is easily
solved in local systems. There are some difficulties for the distributed systems. 
Now this problem is solved on the basis of open keys certificates. Such decision cannot 
be considered satisfactory. Certificates use sluggish asymmetric cryptographic algorithms. 
The system based on certificates uses the center of confirmation.

Qualitatively other algorithm can be constructed on the basis of keys preliminary distribution
schemes. In this case the role of the central server comes down only to key materials 
distribution. Network's subscribers calculate keys of information exchange self-contained. 
The main problem consists that widely known keys preliminary distribution schemes <cit.>
provide information exchange for each user with everyone. Modification of such schemes 
is necessary for accounting of security policy of system. Modifications of the Blom's keys
preliminary distribution scheme, considering the forbidden channels it is suggested in work 
<cit.>. The organization of simplex channels for the same scheme is realized in article
<cit.>. The solution similar task on the basis of the KDP scheme is proposed in articles 
<cit.>.  These works are focused on realization of discretionary security policy. 
Mandatory security policy demands accounting of hierarchy, both subjects, and objects. 
The decision on the basis of hash functions is suggested in article <cit.>. However 
this approach does not allow realizing exchange between users taking into account hierarchy.

The purpose of this article is development of the keys preliminary distribution scheme allowing
realizing mandatory security policy in the distributed computing systems.



§ KEYS PRELIMINARY DISTRIBUTION SCHEME


Mandatory access control uses a security tags set which form an algebraic lattice. Security 
tags are both at users, and at informational objects. At request for access there is a comparison
of security tags. The decision is made on the basis of some logical condition.

Let's designate the set of users in the distributed system U. For users of system there is 
an order relation. We will be limited to the order relation described by the graph in the form 
of a tree. 	Dominance of the user u_i over the user u_j we will designate u_i>u_j. 
Also the situation when users are incomparable with each other is possible. Let's use then
designation u_i<>u_j. We will be limited to a case of mandatory access control in which only
informational streams from below up are resolved. This case corresponds to mandatory security
policy on ensuring confidentiality of information. In this case for two users u_i>u_j  
is resolved only informational stream from u_j to u_i. For two incomparable users 
informational streams in both parties are forbidden.

Let's set the task to formation the key scheme allowing communicating according to mandatory 
access control. For this purpose we will construct the keys preliminary distribution scheme
calculating pair keys only for the allowed channels.

For the solution this task we modify the KDP scheme of keys preliminary distribution. 
For system without access control in the KDP scheme key materials is formed in based of set
K={k_1,...,k_n}. Key materials beforehand are sent to all users via secure channels.  
For development of pair keys the system subsets S={S_1,...,S_m} of set {1,...,n} 
is used. m – number of users in system. The set S is open. For information exchange with 
the user u_j the user  u_i takes subsets S_i  S_j. Further he calculates the elements
entering in the product of sets S_ij=S_i∩ S_j. The pair key is calculated with use the
key materials K, and subsets S_ij:

    k_ij= ⊕ k_l   (l∈ S_ij).

The same operations are carried out by the user u_j when obtaining the message from u_i.

The scheme described above allows carrying out exchange of messages for each user with everyone 
in both directions. We modify the scheme, having entered into it asymmetry of keys 
k_ij≠ k_ji. For this purpose also we use the key materials K and a set S.  
For calculation the key of encrypting for the channel from u_j to u_i we use the difference 
of two sets:

    S_ij={[ S_i∖ S_j, if  S_i∩ S_j=∅;       S_i∩ S_j, overwise ].
           k_ij=⊕_l∈ S_ij k_l.


Such approach leads to automatic implementation the requirement of  keys asymmetry. 
For reading messages the user u_i  (i=1,...,m) will use keys k_ij (j=1,...,m), 
and for sending messages – keys k_ji (j=1,...,m). The suggested scheme is based on 
the symmetric encrypting that accelerates processes of encrypting and decrypting.

We realize the ban on channels of information exchange. For this purpose we will demand that 
the corresponding pair keys were zero k_ji=0, that is  S_ij=∅. From here we 
receive requirements to a set of subsets S. The most widespread approach to creation the set 
of S is uses of the Sperner's families <cit.>. The Sperner's family <cit.> is called 
the family of subsets D={D_1,...,D_n} such that, if D_i∩ D_j⊆ D_t, that either
t=i, or t=j. In the unmodified KDP scheme on the basis of elements D_i the Shperner's 
family are formed S_ij. We use similar approach for the solution the problem. Let's create 
the Shperner's family with the quantity of elements equal to number of users 
D={D_1,...,D_m}. We will form a set S, moving on a tree of users hierarchy leaves 
to a root. Let's allocate "leave's" users u_1,..., u_l, where l – quantity of leave's tops 
on the tree. Let's equate, the elements of a set S corresponding to them, to Sperner's family
elements S_i=D_i (i=1,...,l). Let's rise from leaves to a tree root. If the top of u_i has
the closest descendants u_i1,..., u_ik, then to this user there corresponds the set:

    S_i=S_i1∪ S_i2∪ ... S_ik∪ D_i.

This algorithm of formation the set S leads to realization of the required condition the
mandatory access control: if u_i>u_j, then S_i⊃ S_j, and 
S_i∖ S_j≠∅, but S_j∖ S_i=∅. Thus, users can create a pair
key only for the allowed communication channels. Also the requirement for incomparable users 
is fulfilled: if u_i<>u_j, then S_j∖ S_i=∅  and S_i∖ S_j=∅.



§ EXAMPLE OF KEYS PRELIMINARY DISTRIBUTION SCHEME


Let's consider implementation the suggested scheme on a simple example. In system seven users are authorized. The hierarchy of users is shown in the figure 1.



Let's define the key materials set with 15 one byte elements:

    k_1= 00100100, k_2= 10101010, k_3= 01010101, k_4= 11011011,	
          k_5= 11101110,  k_6= 00010001, k_7= 10010010,	k_8= 10110110,	
          k_9= 00011000,  	k_10= 11101110,  k_11= 10111001,  k_12= 11100111,
          k_13= 00101101, k_14= 11010010, k_15= 01111111.

We will set the Sperner's family as follows:

    D_1={1,2}, D_2={3,4}, D_3={5}, D_4={6,7,8},


    D_5=9,10, D_6={11,12,13},  D_7={14,15}.

For sheet tops the sets S are defined as

    S_4=D_4={6,7,8},  S_5=D_5={9,10},  S_6=D_6={11,12,13},  S_7=D_7={14,15}.

For other users

    S_2=S_4∪ S_5 ∪ D_2={3,4,6,7,8,9,10}, S_3=S_6∪ S_7∪ D_3={5,11,12,13,14,15},
          S_1=S_2∪ S_3∪ D_1={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.

Process of formation sets S is presented in the figure 2.



For calculation of pair keys we will define set differences

    Δ S_12=S_1∖ S_2={1,2,5,11,12,13,14,15},
          Δ S_13 = S_1∖ S_3={1,2,3,4,6,7,8,9,10},
          Δ S_14 = S_1∖ S_4={1,2,3,4,9,10,11,12,13,14,15},
          Δ S_15 = S_1∖ S_5={1,2,3,4,5,6,7,8,11,12,13,14,15},
          Δ S_16 = S_1∖ S_6={1,2,3,4,5,6,7,8,9,10,14,15},
          Δ S_17 = S_1∖ S_7={1,2,3,4,5,6,7,8,9,10,11,12,13},
          Δ S_21 = S_2∖ S_1=∅, 
    Δ S_23 = S_2∖ S_3=∅,
          Δ S_24 = S_2∖ S_4={3,4,9,10},
          Δ S_25 = S_2∖ S_5={3,4,6,7,8},
          Δ S_26 = S_2∖ S_6=∅, 	 
    Δ S_27 = S_2∖ S_7=∅, 	
          Δ S_31 = S_3∖ S_1=∅, Δ S_32 = S_3∖ S_2=∅, 	 
    Δ S_34 = S_3∖ S_4=∅, 	
    Δ S_35 = S_3∖ S_5=∅,
          Δ S_36 = S_3∖ S_6={5,14,15},
          Δ S_37 = S_3∖ S_7={5,11,12,13},
          Δ S_41 = S_4∖ S_1=∅, Δ S_42 = S4∖ S2=∅, 	 
    Δ S_43 = S_4∖ S_3=∅, 	
    Δ S_45 = S_4∖ S_5=∅,
          Δ S_46 = S_4∖ S_6=∅, Δ S_47 = S_4∖ S_7=∅,
          Δ S_51 = S_5∖ S_1=∅,  Δ S_52 = S_5∖ S_2=∅,  Δ S_53 = S_5∖ S_3=∅,  Δ S_54 = S_5∖ S_4=∅,
          Δ S_56 = S_5∖ S_6=∅,  Δ S_57 = S_5∖ S_7=∅,
          Δ S_61 = S_6∖ S_1=∅,  Δ S_62 = S_6∖ S_2=∅, Δ S_63 = S_6∖ S_3=∅,  Δ S_64 = S_6∖ S_4=∅,
          Δ S_65 = S_6∖ S_5=∅,  Δ S_67 = S_6∖ S_7=∅,
          Δ S_71 = S_7∖ S_1=∅,  Δ S_72 = S_7∖ S_2=∅,  Δ S_73 = S_7∖ S_3=∅,  Δ S_74 = S_7∖ S_4=∅,
          Δ S_75 = S_7∖ S_5=∅, Δ S_76 = S7∖ S6=∅.

Pair keys will be defined by equalities:

    k_12= k_1⊕ k_2⊕ k_5⊕ k_11⊕ k_12⊕ k_13⊕ k_14⊕ k_15=10111110,
          k_13= k_1⊕ k_2⊕ k_3⊕ k_4⊕ k_6⊕ k_7⊕ k_8⊕ k_9⊕ k_10=11000011,
          k_14= k_1⊕ k_2⊕ k_3⊕ k_4⊕ k_9⊕ k_10⊕ k_11⊕ k_12⊕ k_13⊕ k_14⊕ k_15=00101000,
          k_15= k_1⊕ k_2⊕ k_3⊕ k_4⊕ k_5⊕ k_6⊕ k_7⊕ k_8⊕ k_11⊕ k_12⊕ k_13⊕ k_14⊕ k_15=00000101,
          k_16= k_1⊕ k_2⊕ k_3⊕ k_4⊕ k_5⊕ k_6⊕ k_7⊕ k_8⊕ k_9⊕ k_10⊕ k_14⊕ k_15=10000000,
          k_17= k_1⊕ k_2⊕ k_3⊕ k_4⊕ k_5⊕ k_6⊕ k_7⊕ k_8⊕ k_9⊕ k_10⊕ k_11⊕ k_12⊕ k_13=01011110,
          k_21=0,  	k_23=0,
          k_24= k_3⊕ k_4⊕ k_9⊕ k_10=01111000,
          k_25= k_3⊕ k_4⊕ k_6⊕ k_7⊕ k_8=10111011,
          k_26=0,  	k_27=0,
          k_31=0,  	k_32=0,  	k_34=0,  	k_35=0,
          k_36= k_5⊕ k_14⊕ k_15=01100011,
          k_37= k_5⊕ k_11⊕ k_12⊕ k_13=10011111,
          k_41=0,  	k_42=0,  	k_43=0,  	k_45=0,  	k_46=0,  	k_47=0,
          k_51=0, k_52=0,  k_53=0,  	k_54=0,  	k_56=0,  	k_57=0,
          k_61=0,  	k_62=0,  k_63=0,  	k_64=0,  	k_65=0,  	k_67=0,
          k_71=0,  	k_72=0,  	k_73=0,  	k_74=0,  	k_75=0,  	k_76=0.

The constructed keys preliminary distribution scheme satisfies the hierarchy of subjects shown in
the figure 1. Only information channels are resolved "from below-up". Incomparable users also
cannot communicate.

The suggested scheme can be used also in systems with the hierarchy of users other than a tree. Let's review an example in the figure 3.



By the same principle elements of the set S are calculated (the Figure 4.)




The keys contradicting mandatory security policy are equal to zero.



§ CONCLUSION


The scheme suggested in this article allows realizing keys preliminary distribution 
of a symmetric enciphering for the distributed systems with user's hierarchy. As well as 
in case of the KDP scheme the Sperner's families are used. However KDP scheme allows forming
bidirectional channels of information exchange whereas the suggested scheme is focused 
on simplex channels. The suggested modification of the keys preliminary distribution scheme 
does not increase the size of key materials. It is an indispensable condition for using this
approach to creation the protected systems.

00

b1
Blom R. An optimal class of symmetric key generation systems. Proc. of the EUROCRYPT 84  pp 335-338. (1985)
b2
Mitchell C.J. and Piper C  Key storage in Secure Networks Discrete and Applied Math. 21 pp 215-228. (1988)
b3
Belim S.V., Belim S.Yu. and Polyakov S.Yu. The Implementation of Discretionary Access Separation
Using a Modified Blom's Scheme of Key Distribution. Information Security Problems. Computer 
Systems, 3, pp. 72–76. (2015)
b4
Belim S.V. and Belim S.Yu. The Modification of Blom's Key Predistribution Scheme, Taking into
Account Simplex Channels. Information Security Problems. Computer Systems, 3, pp. 82–86. (2017)
b5
Belim S.V. and Belim S.Yu. KDP Scheme of Preliminary Key Distribution in Discretionary Security
Policy.  Automatic Control and Computer Sciences, 50, 8, pp.777–786. (2016)
b6
Belim S.V. and Belim S.Yu. The VPN Implementation on Base of the KDP-Scheme. CEUR Workshop
Proceedings 1732. URL: http://ceur-ws.org/Vol-1732/paper3.pdf. (2016)
b7
Belim S.V. and Bogachenko N.F. Distribution of Cryptographic Keys in Systems with a Hierarchy of
Objects.  Automatic Control and Computer Sciences, 50, 8,  pp.773–776. (2016)
b8
Dyer M., Fenner T., Frieze A. and Thomason A. On key storage in secure networks. 
J. Cryptology, 8, pp. 189–200. (1995)
b9
O'Keefe C.M. Applications  finite geometries in information security. Australas. J. Combin.  
7, pp. 195–212. (1993)
b10
Young M. The Technical Writer's Handbook. Mill Valley, CA: University Science, 1989.



