i HTTP Basi

Size: px

Start display at page:

Download "i HTTP Basi"

みいかひがき
5 years ago
Views:

1 2006 Web page Access Control based on Broadcast Encryption Scheme 5ADRM034

2 i HTTP Basic [4] HTTP Digest [4] FORM SSL DAC Discretionary Access Control MAC Mandatory Access Control RBAC Role-Based Access Control RBAC [7] [9] Complete Subtree Method(CS )[2][3] ACL

3 ii ACL mixi Subset Difference Method SD [2][10] [11] SNS Six Degrees of Separation

4 Web SNS blog Web [1] Web ID HTTP Basic ID (ACL) ACL HTTP Basic ID Complete Subtree Method(CS )[2] CS (ID, P ass) n r log 2 n/r Java SNS Web CS SNS mixi Web 6 7

5 HTTP Basic [4] HTTP Basic HTTP Web ACL DES,MD5 ACL ACL ( ) n Web [401] (authentication realm) (Basic ) Base64 Authorization Web [401] Base64 SSL HTTP Digest [4] HTTP Digest Basic HTTP Digest realm nonce opaque

6 2.1. Web (Web ) (httpd) 1.URL 2.Request 4.ID/PW 3.Response (401 Authorization Required) 5.ID/PW 6.Authorization ID/PW 8.Content 7.Response (200 OK) 2.1: Basic qop auth URI auth-int 2 response algorithm nonce-count(nc) qop 1 cnonce [401] response (algorithm MD5 ) A1 = username : realm : password A2 = HT T P method : uri(qop auth ) A2 = HT T P method : uri : H(entity body)(qop auth int) response = H(H(A1) : nonce : nc : cnonce : qop : H(A2))(qop auth auth int) response = H(H(A1) : nonce : H(A2))(qop ) response Authorization re- 3

7 2.1. sponce [401] nc auth-int HTTP Basic SSL HTTP/ Unauthorized WWW-Authenticate: Digest realm= algorithm= MD5,MD5-sess algorithm qop="auth,auth-int", nonce="dcd98b7102dd2f0e8b11d0f600bfb0c093", opaque="5ccc069c403ebaf9f0171e9517f40e41" Authorization: Digest username=, realm= nonce="dcd98b7102dd2f0e8b11d0f600bfb0c093", uri="/dir/index.html", algorithm= MD5 qop=auth, nc= , Authorization algorithm cnonce="0a4f113b", response="6629fae49393a c4ef1", opaque="5ccc069c403ebaf9f0171e9517f40e41" 2.2: FORM FORM HTTP HTML (HTML) FORM HTML SSL SSL 4

8 T & 2.1. CA SSL CA (Web ) HTTPS! " # $ 0"1(2 8:9:; =? 8:9:; =? C!ES?DG<I!J X %&(' )+*-,. / 8:9<;>=?-@BA 8:9<; =?DC!EF?HG:I!J K!L M Y 8:9:; =? C!EF?DG:I!J X N OQP R 8:9<; =? C!ES?HG:I!J Y 2.3: SSL 5

9 DAC Discretionary Access Control DAC Owner Group Everyone Read Write Execute Linux UNIX MAC Mandatory Access Control MAC DAC RBAC Role-Based Access Control RBAC (permission) (OS read write ) ( ) (role hierarchy) (inheritance) UNIX OS OS 6

10 RBAC [7] RBAC RBAC 7

11 2.3. ( ) 2.4 Step 1. Step 2. Step 3. Step 4. Step 5. Step 6. Step 7. 2.ID,Pass,'(*),+ 3. -,. 1.ID,Pass,'(*),+,-.*/ 0,1 5. 2/ / :/ 0<; Context! "# $% "& 2.4: 8

12 [9] BLP(Bell and LaPadula) SLA(Security Level Assignment) BLP BLP SLA BLP 1 BLP BLP BLP SLA [8] SLA 2.5, Step Step 2. I, II, III,... I, II, III,... 9

13 2.3. Step 3. 1 Step 4. SLA 2.5: 10

14 Complete Subtree Method(CS )[2][3] CS Naor CS N R T n 2 d n = 2 d 1 2n 1 x j u i u i 1 + log 2 n 2 T N \ R 2 T

15 HTTP Basic CS Web KM S 1, S 2,... u 1,..., u n KM CS x j HTTP Basic ID (ID j, x j ) S CS ACL u i sk i Web 3.3 (ID, P ass) x 1,..., x 2n 1 u i sk i u i S j U = {u 1,..., u n } j U j U sk i ACL Step 1. KM CS 2 T x i KM u i sk i ={ (i 1, x i1 ), (i 2, x i2 ),..., (i m, x im )} i 1,..., i m m = log n ID Step 2. S 2 T L j ={ (j 1, x j1 ), (j 2, x j2 ),..., (j k, x jk )} j 1,..., j k CS k ID L ACL L KM KM L 2 T x j S ACL KM S ACL S ACL Step 3. u i Web sk i (i, x i ) sk i HTTP Basic S S ACL m sk i L j = φ 12

16 3.3. Web (, ) sk i 2 T sk i [Step2] 2 sk i [Step2] 2 [Step1] sk i [Step1] 3.1 n = 8 Sj U 1 = (u 1, u 2, u 4, u 7, u 8 ) 3.2 sk i u 1 u 1 sk 1 = {(i 1, x 1 ),..., (i 8, x 8 )} = {(1, x 1 ), (2, x 2 ), (4, x 4 ), (8, x 8 )} S j 3 (i, x) L 1 = {(4, x 4 ), (11, x 11 ), (7, x 7 )} u 3, u 5, u 6 x 1 x 4 x 2 x 3 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 3.1: Web 2 T 13

17 # 3.3. KM x,..., x 1 15 sk 1 L 1 ( ) ( ( ) sk = ( x, x, x x ) , u 1 1 x 8 Unauthorized L = S 1 ( x, x x ) , 7 u 2 x 2 u 3! " # ( ($ % &'( ) OK (HTTP (HTTP ) L = S 2 ( x ) 2 2, x 6 )* + ", ( (-. / HTTP + ", ) 3.2: 14

18 Keymake ACL ACLmake Browser Keymake 1. (member.csv) ( ) 2. 2 T 3. T 4. keylist.csv 5. T (userkey.csv)

19 4.3. ACL 4.1: CPU Xeon 2.3GHz Pentium4 2.8GHz Memory 1GB 512MB Linux Redhat 9 Windows XP JDK JDK (indkey.csv) 4.3 ACL ACLmake 1. (userac.csv) 2 T 1 0 T null 2. CS ( ) ( ) 0 null 0 1 null 0 1 ( ) 16

20 4.3. ACL 2 1 null (keylist.csv) ( 4. DES ACL.htpasswd (.htpasswd ) 5..htpasswd Web.htaccess.htpasswd.htaccess n= null null 4.1: 17

21 Browser (indkey.csv) Web Web 401 Unauthorized [ID:Pass] Base64 3. Authorization Web 4. Web [200] [401] Web : 18

22 : ACL 4.5 member.csv user1 tokai.ac.jp user2 cs.dm.jp user3 sr.uoy keylist.csv! ID Pass 1 id1 ruoy/rof 2 id2 ylerecnis " indkey.csv ID Pass id1036 nkik.read id518 uoy/knaht id205.ecnadiug userac.csv 0 or 1 user1 0 user2 1 user :.htaccess AuthType Basic AuthUserFile.htpasswd AuthGroupFile /dev/null AuthName "Enter password" Require valid-user.htpasswd Pass id1:fam.sqza7wf8i id2:eu0.zctjcht7e id3:nhwr5idhmlqje id4:3uy/85a7pxdvy id5:jjfmzyvatvan6 4.5: ACL 19

23 (SNS)mixi SNS SNS Six Degrees of Separation[12] SSL 5.1 Step 3 URL TCP n = 1, 000, ACL x n = 1, 000, 000 r = 0.3n 5.2 CS CS

24 Turnaround Time[ms] Number of rounds 5.1: ( ) x 0.35ms n x ACL 5.2 r = 0.3n HTTP Basic CS CS n r r log 2 n r [2] Web L.htpasswd 5.4 HTTP Basic CS HTTP Basic 27% 45% 21

25 Processing Time[ms] Fraction of Revocation r/n 5.2: ACL (n = 1, 000, 000) Processing Time[ms] Number of Keys 5.3: ACL 22

26 Basic CS(upper bound) CS(proposed) Size of ACL Number of Users n 5.4: 23

27 5.3. MIXI 5.3 mixi (SNS) mixi[6] mixi 3 M Web HTTP Basic F N N 2 mixi (2004 ) F M M 50 n = 1, 000, 000 M = 50 M 2 = 2500 F, N, N 2 HTTP Basic CS F HTTP Basic CS N, N 2 n = 250, 000, n = 62, 500, n = 7, , 5.4, 5.5 F n = 1, 000, 000 N N 2 n = 250, 000, n = 62, 500 n = 1, 000, 000 n = 7, % 24

28 5.3. MIXI CS HTTP Basic frequency Number of MyMixi 5.5: 5.1: mixi F % N % N % % 25

29 5.3. MIXI 5.2: N 2 ( ) Basic CS 1 21 F 1,000,000 1 N N : (n = 250, 000) Basic CS 1 19 F 250,000 1 N N : (n = 62, 500) Basic CS 1 17 F 62,500 1 N N : (n = 7, 812) Basic CS 1 14 F 7,812 1 N N

30 HTTP Basic n log n + 1 KM n 2n 1 [5] h L, h R T x i x 1 ( ) x 1 x 2 h 1 L (x 1) x 1 x 3 h 1 R (x 1) x 5.6 x 1 x h L, h R x x log n h, L h R x 1 x x 1 2 = h L x 1 4 = h L x ( 1 ) 1 ( h L ( 1 )) x 1 3 = h R x ( 1 ) x x 5 x 6 7 x x 9 x 11 x x13 x 14 x 15 x 1 8 = h L x 1 1 ( h L ( h L ( 1 ))) 5.6: 27

31 % HTTP Basic 28

32 HTTP Basic CS Web mixi 2 Web 6.2 Web ACL mixi

33 30 7 SNS Six Degrees of Separation 7.1 Subset Difference Method SD [2][10] SD SD 7.1 Label1 SD P i,j D i,j i j 3 G L G R G M v i v j Label i,j = G L (G R (G L (Label))) Label i,j D i,j = G M (Label i,j ) G 7.1 u 1 G Label 1 Label 1,3 = G R (Label 1 ) Label 1,5 = G L (G L (Label 1 )) Label 1,9 = G R (G R (G L (Label 1 ))) Label 1,17 = G R (G L (G R (G L (Label 1 ))))

34 7.1. SUBSET DIFFERENCE METHOD SD [2][10] Label 2 Label 2,5 = G L (Label 2 ) Label 2,9 = G R (G R (Label 2 )) Label 2,17 = G R (G L (G R (Label 2 ))) Label 4 Label 8 Label 4,9 = G R (Label 4 ) Label 4,17 = G R (G L (Label 4 )) Label 8,17 = G R (Label 8 ) D 1,3 Label 1,3 G D 1,3 = G M (Label 1,3 ) CS n k=1 r k2 ( k 1) SD SD Step 1. 2 T v i1, v i2 v v v i1, v i2 v v l v i1 v r v i2 v l, v r Step 2. v l v i1 S l,i1 v v i2 S,i2 Step 3. T 31

35 7.1. SUBSET DIFFERENCE METHOD SD [2][10] 4 Label 1 Label v i1 v i 2 Label 3 2 Label Label 5 Label 6 Label 7 Label 8 10 v j1 v Label Label 12 Label 14 v j2 Label 16 Label 32 u 1 u 5 u 6 u : SD 1 2 v v = v l v i1 v r P r,i2 v v 2 l v i1 r v i2 v i 7.2: 32

36 7.2. [11] 7.2 [11] Layer Number : LN Relative Node Number : RNN Node Revocation Pattern : NRP 7.3 NRP NRP= 1111 NRP= 0000 NRP 7.4 LN2/RNN3 LN1/RNN3 0 NRP LN1/RNN3 LN2/RNN3 0 NRP NRP 7.5 LN2/RNN0 LN2/RNN1 LN2/RNN0 LN2/RNN1 LN0/RNN0 LN1/RNN0 LN0/RNN0 NRP= 1000 K 0 0,1000 LN1/RNN0 NRP= 1100 K 1 0,

37 7.2. [11] K 0 0,0000 K 0 0, K 0 0, K 0 0,1000 K 0 0,1001 K 0 0,1010 K LN RNN, NRP LN 0 K 0 0,0100 K 0 0,1100 K 0 0,0101 K 0 0,1101 K 0 0,0110 K 0 0,1110 K 0 0,0111 RNN 0 K 1 3,0001 K 1 3,0010 K 1 3,0011 K 1 3,0100 K 1 3,0101 K 0 0,0011 K 0 0,1011 LN 1 RNN K 1 3,0110 K 1 3,1000 K 1 3,1001 K 1 3,1010 K 1 3,1011 K 1 3,1100 K 1 3, K 1 3,1101 K 1 3, : K 0 0,0000 K 0 0,0001 K 0 0,0010 K 0 0,0011 K 0 0,1000 K 0 0,1001 K 0 0,1010 K 0 0,1011 LN 0 K 0 0,0100 K 0 0,0101 K 0 0,0110 K 0 0,0111 K 0 0,1100 K 0 0,1101 K 0 0,1110 K 1 3,0001 K 1 3,0010 K 1 3,0011 K 1 3,0100 K 1 3,0101 LN 1 K 1 3,0110 K 1 3,1000 K 1 3,1001 K 1 3,1010 K 1 3,1011 K 1 3,1100 K 1 3,0111 K 1 3,1101 K 1 3,1110 LN 2 K 0 0, XXX 0 K 1 3, XXX 0 K X : 34

38 7.2. [11] LN 0 K 0 0,1000 LN 1 K 1 0,1100 LN 2 7.5: 35

39 7.3. SNS SIX DEGREES OF SEPARATION 7.3 SNS Six Degrees of Separation Six Degrees of Separation 6 Stanley Milgram SNS [12] SNS GREE[13] 147,680 1,059,684 degree 4.83 degree GREE % 6-degree 7.1: degree (%) , ,489 82, , , , , , , , , ,

40 37 [1] html/ [2] D. Naor, M. Naor and J. Lotspiech Revocation and Tracing Schemes for Stateless Receivers in Advances in Cryptology Crypto2001, Springer, LNCS 2139, pp (2001) [3] C. Wong, M. Gouda and S. Lam Secure Group Communications Using Key Graphs Proc. of ACMSIGCOMM 98, pp (1998) [4]. Franks, P. Hallam-Baker, J. Hostetler, S. Lawrence, P. Leach, A. Luotonen, L. Stewart HTTP Authentication: Basic and Digest Access Authentication RFC 2617, June 1999 [5], 2003 (SCIS) pp (2003) [6] mixi [7] RBAC Vol.47 No.6 pp (2006) [8] Vol.41 No.8 pp (2000) [9] Vol.47 No.6 pp (2006) [10] SD Vol.47 No.2 pp (2006) [11] (SCIS) pp (2002)

41 [12] 6 -SNS Six Degrees of Separation- Vol.90 No.2 pp (2007) [13] GREE 38

42 39 2 5

3.1 3.2 3.3 3.4 3.4.1Complete Subtree Method(CS ) 3.4.1RSA-CS 3.5 4.1 4.2 4.3 4.4 4.5 2

3.1 3.2 3.3 3.4 3.4.1Complete Subtree Method(CS ) 3.4.1RSA-CS 3.5 4.1 4.2 4.3 4.4 4.5 2 [1] 3 1 4 log n Layer Number : LN 0,1,2 Relative Node Number : RNN 0,1,2 Node Revocation Pattern : NRP 5 LN0 K0000