Transcript A new key assignment scheme for enforcing complicated access

A new key assignment scheme
for enforcing complicated
access control policies in
hierarchy
Authors: Iuon-Chang Lin, Min-Shiang Hwang
and C. C. Chang
Source: Future Generation Computer Systems,
Vol.19, pp.457-462, 2003.
Adviser: Min-Shiang Hwang
Speaker: Chun-Ta Li
Date: 2004/11/18
1
Cryptanalysis of YCN key
assignment scheme in a hierarchy
Authors: Min-Shiang Hwang
Source: Information Processing Letters,
Vol.73, pp.97-101, 2000.
2
Modifying YCN Key
Assignment Scheme
against Hwang’s Attack
Authors: Jyh-Haw Yeh, Min-Shiang Hwang
and Wen-Chen Hu
Preprint submitted to Elsevier Science
5 November 2004
3
Introduction
• Access control policy – access control problem
in a hierarchy
Key1 Key2 Key3 Key4 Key5 Key6
C1
Key management
problem
Key2
C2
C3
Key3
C4
C5
C6
Key4
Key5
Key6
4
Introduction (cont.)
• Ak1 and Taylor [1983]
– Super-key (top-down)
• CA assigns to each user class {prime, secret key,
public parameter}
• Cjhigh derive the secret key of Cilow
Large public
parameter
Secret key and
Public parameter of Ci and Cj
Product of the primes of Ci
5
Introduction (cont.)
Large amount of
storage to store
public parameters
• Mackinnon et al. [1985] – canonical assignment
– Reduce the values of public parameters
• Harn and Lin [1990] – (bottom-up)
– Security: difficulty of factoring a large number
– Size of the storage space is much smaller
• Yeh et al. [1998] – YCN scheme
– transitive exceptions
– anti-symmetrical arrangements
Several user classes can collaborate to
derive the derivation and encryption keys
Hwang [2000]
YCN is
insecure
6
C1
Original YCN Scheme
C3
• CA
–
–
–
–
C4
C2
C5
Generates secret number K0
C6
Generates M (product of two large prime numbers)
Assign a prime number Pi to each user class Ci
Compute the product Xi for Ci
除鄰近節點外
順著箭頭所能到 X i
達的節點

P P
j 1,..., U i
ij
Ci Cm ,
j 1,..., U m
mj
將能順箭頭指到i節
點的Pij值做連乘
7
Original YCN Scheme (cont.)
• Compute the public information Tie and Tid for Ci
Tid 

j 1,..., Ui
Pij

Tie   X i / 
除鄰近
Cn

節點外
的祖先
節點
 Pm
Cm Ci
順箭頭所到達不 Pm = 7
了的節點質數值 Pn1 = Ø
C1
Pm = 2,7
P42= 31
C2

Pni 
Pm Pm = 2,3,7,11,13
Cm Ci P13,43,53 = 17,37,43 C
Pn4 = Ø
Pm = 2
C4

3
C5 Pm = 2,7
P15 = 19
C6
Pm = 2,3,5,7,11
P16,26,46 = 23,29,41
8
Original YCN Scheme (cont.)
• Assign the derivation key Kid and encryption key Kie
for each Ci
Kid  ( K 0 )Tid mod M
Kie  ( K 0 )Tie mod M
kept secret by the user class Ci
• Ci can use its own derivation key Kid to derive the
encryption key Kje of Cj
C1
K je  ( Kid )
T je / Tid
mod M
C2 derives C3’s encryption key K3e
K3e=(K02*3*7*11*13*19*23*29*31*41) mod M C3
= (K02*7*29)2*3*7*11*13*19*23*29*31*41/2*7*29 mod M
C4
C2
C5
9
C6
The Weakness of the YCN Scheme
Theorem 1. Assume that there are only two top
classes (Ca and Cb) in the hierarchy. Ca and Cb can
collaborate to derive the derivation and encryption
keys of all of the classes in the YCN scheme.
• gcd(Tad, Tbd) = 1
• sTad + tTbd = 1
• Ca and Cb can collaborate to derive the secret K0
KsadKtbd = (K0)sTad(K0)tTbd mod M
= (K0)(sTad+tTbd) mod M
= K0
• gcd(T1d,T4d) = gcd(52003,94054) = 1
• (s, t) = (76107, -42080) such that sT1d + tT4d = 1
Ks1dKt4d = (K0)sT1d(K0)tT4d mod M
= (K0)((76107*52003)-(42080*94054)) mod M
= K0
C1
C4
C2
C3
C5
C6
T1d = 7,17,19,23
T4d = 2,31,37,41
10
The Weakness of the YCN Scheme (cont.)
C1
Theorem 2. If C1,C2,…, and Cn are n top classes in the
hierarchy, any two of these classes (e.g., C1 and C2)
can collaborate to derive the derivation and encryption
keys of all successors of these top classes.
•
•
C1 and C2  derivation and encryption keys of C6
– gcd(T1d, T2d) = 7
– s(T1d/7) + t(T2d/7) = 1
– C1 and C2 can collaborate to derive the secret (K0)7
((K1d)s(K2d)t)T6d/7 mod M
= ((K0)sT1d(K0)tT2d)T6d/7 mod M
T
(K0)7 == K(K0) 6d mod M
6d
C3
C4
C2
C5
C6
C5 and C6  derivation and encryption keys of C3
– gcd(T5d, T6d) = 2*7 = 14
– s(T5d/14) + t(T6d/14) = 1
– C1 and C2 can collaborate to derive the secret (K0)14
((K5d)s(K6d)t)T3d/14 mod M
= ((K0)sT5d(K0)tT6d)T3d/14 mod M
14= (K0)T3d mod M
(K0) = K
3d
11
The Modified YCN Scheme
C1
• CA
–
–
–
–
C2
C4
Generates secret number K0
C3
C5
Generates M (product of two large prime numbers)
Assign a prime number Pi to each user class Ci
C6
Compute the product Pi` for Ci
12
The Modified YCN Scheme (cont.)
• CA computes the public information Tid and Tie
Ti d  (  Pj Pj' )(  Pj )

( Ci ,C j )E
Ti e 
(
j Pj )(

Ci ( C j )
'
P
( Ci ,C j ) E j )(

'
P
Ci ( C j ) j ) if  Ct such that Ct ( Ci )
Tid
otherwise
C1
C2
Tie
2*3*5*7*11*13 *1 *17
C3
Tid

5* 11*19 *7 *13 *3
(1,3) (1,5) (1,4)(1,6) 1(2)
C4
d
T
2* 5* 7* 3
i
C5
(5,1)(5,3)(5,4)5(2)
C6
The Modified YCN Scheme (cont.)
•
d
d
T
i
CA assigns a derivation key Ki = (K0) mod
e
e
T
an encryption key Ki = (K0) i mod M
M and
• A class Ci can apply a key derivation function fil(x,y)
to derive another class Cl’s key (x and y could be either
the character d or e)
y/T x
x T y/T x
y
y
x
T
T
T
– fil(x,y) = (Ki ) l i = ((K0) i ) l i = (K0) l ) mod M = Kl
14
The Modified YCN Scheme (cont.)
• Theorem 1. Under the modified YCN key assignment
scheme, Tid|Tle if and only if the policy allows Ci to access
Cl, i.e., (Ci,Cl) E .
• Theorem 2. If the policy does not allow any class Cik  H
to access Cl, i.e.,(Cik , Cl )  E ,then both Tld and Tle are not
multiple of Y under the modified YCN scheme,
where Y  gcd{Tikd | Cik  H } .
• Theorem 3. If there is a transitive exception Ci
Cl with
an intermediate class Ck, i.e., Ci(Ck), then Tid
Tkd and
Tke
Tld under the modified YCN scheme.
15
A New Key Assignment Scheme
•
•
•
•
CA generates two large primes: p and q
CA calculates n = p*q, where n is public
CA chooses another parameter, g
CA chooses a set of distinct primes {e1,e2,…,em} for
all user classes {C1,C2,…,Cm}
gcd(Ø(n), ei) = 1
and 1 < ei < Ø(n)
• CA calculates {d1,d2,…,dm}
ei x di ≡ 1 mod Ø(n)
16
A New Key Assignment Scheme
(cont.)
• CA generates the derivation keys {DK1,DK2,…,DKm} and
the secret keys {SK1,SK2,…,SKm} for all user classes
{C1,C2,…,Cm}
C j Ci ( d j )

DK i  g
mod n
SK i  g di mod n
• Ci can derive the secret key of class Cj with the derivation
key DKi as follows:
(e )
SK j  DKi Ck Ci ,k  j k mod n
Ck  Ci ( d k )  Ck  Ci , k  j ( ek )

 (g
)
mod n
 g mod n
dj
17
A New Key Assignment Scheme
(cont.)
• Example
– CA calculates the derivation keys
•
•
•
•
C1: DK1 = gd2*d4 mod n SK1 = gd1 mod n
C2: DK2 = gd3*d4 mod n SK2 = gd2 mod n
C3: DK3 = null
SK3 = gd3 mod n
C4: DK4 = gd2 mod n
SK4 = gd4 mod n
– C1 derives the secret keys SK2 and Sk4
• SK2 = DK1e4 mod n
• SK4 = DK1e2 mod n
18
Thanks for your attention
19
Example
• transitive exceptions
– C1 can access C2 and C2 can access C3
– But C1 cannot access C3
• anti-symmetrical arrangements
– C2 can access C4 and C4 can access C2
– But C2 and C4 are two different user classes
20