2006 Web page Access Control based on Broadcast Encryption Scheme 5ADRM034
i 1 1 1.1................................. 1 1.2.................................... 1 2 2 2.1...................................... 2 2.1.1 HTTP Basic [4]........................... 2 2.1.2 HTTP Digest [4].......................... 2 2.1.3 FORM................................ 4 2.1.4 SSL.......................... 4 2.2................................... 6 2.2.1 DAC Discretionary Access Control...... 6 2.2.2 MAC Mandatory Access Control....... 6 2.2.3 RBAC Role-Based Access Control. 6 2.3...................................... 7 2.3.1 RBAC [7].................................. 7 2.3.2 [9]........ 9 3 11 3.1 Complete Subtree Method(CS )[2][3]..................... 11 3.2........................................ 12 3.3.................................... 12 4 15 4.1...................................... 15 4.2....................................... 15 4.3 ACL..................................... 16 4.4................................... 18 4.5................................... 19
ii 5 20 5.1...................................... 20 5.2...................................... 20 5.2.1.................................. 20 5.2.2 ACL................................. 20 5.2.3.......................... 21 5.3 mixi.................. 24 5.4........................................ 27 5.5....................................... 28 6 29 6.1........................................ 29 6.2.................................... 29 7 30 7.1 Subset Difference Method SD [2][10]................... 30 7.2 [11]........................... 33 7.3 SNS Six Degrees of Separation.................... 36 37 39
1 1 1.1 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 1.2 7 1 Web CS 2 3 4 5 SNS mixi Web 6 7
2 2 2.1 2.1.1 HTTP Basic [4] HTTP Basic HTTP Web ACL DES,MD5 ACL ACL ( ) n Web [401] (authentication realm) (Basic ) Base64 Authorization Web [401] Base64 SSL 2.1 2.1.2 HTTP Digest [4] HTTP Digest Basic HTTP Digest realm nonce opaque
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
2.1. sponce [401] 2.2 http://www.cs.dm.u-tokai.ac.jp/dir/index.html nc auth-int HTTP Basic SSL HTTP/1.1 401 Unauthorized WWW-Authenticate: Digest realm= www.cs.dm.u-tokai.ac.jp", algorithm= MD5,MD5-sess algorithm qop="auth,auth-int", nonce="dcd98b7102dd2f0e8b11d0f600bfb0c093", opaque="5ccc069c403ebaf9f0171e9517f40e41" Authorization: Digest username=, realm= www.cs.dm.u-tokai.ac.jp", nonce="dcd98b7102dd2f0e8b11d0f600bfb0c093", uri="/dir/index.html", algorithm= MD5 qop=auth, nc=00000001, Authorization algorithm cnonce="0a4f113b", response="6629fae49393a05397450978507c4ef1", opaque="5ccc069c403ebaf9f0171e9517f40e41" 2.2: 2.1.3 FORM FORM HTTP HTML (HTML) FORM HTML 2.1.4 SSL SSL 4
T & 2.1. CA SSL CA 2 2.3 (Web ) HTTPS! " # $ 0"1(2 8:9:; =? 8:9:; =? C!ES?DG<I!J X 345 06 7 %&(' )+*-,. / 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
2.2. 2.2 2.2.1 DAC Discretionary Access Control DAC Owner Group Everyone Read Write Execute Linux UNIX 2.2.2 MAC Mandatory Access Control MAC DAC 2.2.3 RBAC Role-Based Access Control RBAC (permission) (OS read write ) ( ) (role hierarchy) (inheritance) UNIX OS OS 6
2.3. 2.3 2.3.1 RBAC [7] RBAC RBAC 7
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/3 4 4. 6 7/ 8 9 6.5 6.5 6 :/ 0<; Context! "# $% "& 2.4: 8
2.3. 2.3.2 [9] BLP(Bell and LaPadula) SLA(Security Level Assignment) BLP BLP SLA BLP 1 BLP BLP BLP SLA [8] SLA 2.5, Step 1. 2.5 Step 2. I, II, III,... I, II, III,... 9
2.3. Step 3. 1 Step 4. SLA 2.5: 10
11 3 3.1 Complete Subtree Method(CS )[2][3] CS Naor CS N R 1 1 2 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
3.2. 3.2 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
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
# 3.3. KM x,..., x 1 15 sk 1 L 1 ( ) ( (012 3456 ) sk = ( x, x, x x ) 1 8 4 2, u 1 1 x 8 Unauthorized L = S 1 ( x, x x ) 1 4 11, 7 u 2 x 2 u 3! " # ( ($ % &'( ) OK (HTTP (HTTP2 345 6 ) L = S 2 ( x ) 2 2, x 6 )* + ", ( (-. / HTTP + ", ) 3.2: 14
15 4 3 Keymake ACL ACLmake Browser 3 4.1 4.1 4.2 Keymake 1. (member.csv) ( ) 2. 2 T 3. T 4. keylist.csv 5. T (userkey.csv)
4.3. ACL 4.1: CPU Xeon 2.3GHz Pentium4 2.8GHz Memory 1GB 512MB Linux Redhat 9 Windows XP JDK 1.5.0 JDK 1.5.0 6. (indkey.csv) 4.3 ACL ACLmake 1. (userac.csv) 2 T 1 0 T null 2. CS ( ) 0 0 0 1 1 1 1 0 0 1 0 1 ( ) 0 null 0 1 null 0 1 ( ) 16
4.3. ACL 2 1 null 0 4.1 3. (keylist.csv) ( 4. DES ACL.htpasswd (.htpasswd ) 5..htpasswd Web.htaccess.htpasswd.htaccess n=13 0 0 0 0 1 0 0 0 1 0 0 null 1 1 0 0 1 0 0 1 1 1 0 0 1 null 4.1: 17
4.4. 4.4 Browser (indkey.csv) 1. 2. Web Web 401 Unauthorized [ID:Pass] Base64 3. Authorization Web 4. Web [200] [401] Web 4.2 4.3 4.2: 18
4.5. 4.3: 4.5 4.4 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 user3 1 4.4:.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
20 5 5.1 (SNS)mixi SNS SNS Six Degrees of Separation[12] 5.2 5.2.1 SSL 5.1 Step 3 URL 5.1 21 20 TCP n = 1, 000, 000 1000 2.1 2 5.2.2 ACL 5.2 5.3 x n = 1, 000, 000 r = 0.3n 5.2 CS CS
5.2. 25000 20000 Turnaround Time[ms] 15000 10000 5000 0 0 5 10 15 20 25 Number of rounds 5.1: ( ) 5.2 5.3 x 0.35ms 5.2.3 5.4 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
5.2. 140000 120000 100000 Processing Time[ms] 80000 60000 40000 20000 0 0 0.2 0.4 0.6 0.8 1 Fraction of Revocation r/n 5.2: ACL (n = 1, 000, 000) 140000 120000 100000 Processing Time[ms] 80000 60000 40000 20000 0 0 50000 100000 150000 200000 250000 300000 350000 400000 Number of Keys 5.3: ACL 22
5.2. 100000 Basic CS(upper bound) CS(proposed) 80000 Size of ACL 60000 40000 20000 0 0 20000 40000 60000 80000 100000 Number of Users n 5.4: 23
5.3. MIXI 5.3 mixi (SNS) mixi[6] mixi 3 M Web HTTP Basic F N N 2 mixi (2004 ) 5.1 5.1 F M 5.5 5.5 M 50 n = 1, 000, 000 M = 50 M 2 = 2500 F, N, N 2 HTTP Basic CS 5.2 5.1 F HTTP Basic CS N, N 2 n = 250, 000, n = 62, 500, n = 7, 812 5.3, 5.4, 5.5 F n = 1, 000, 000 N N 2 n = 250, 000, n = 62, 500 n = 1, 000, 000 n = 7, 812 17% 24
5.3. MIXI CS HTTP Basic 7 6 5 frequency 4 3 2 1 0 0 10 20 30 40 50 60 70 80 90 100 110 120 130 Number of MyMixi 5.5: 5.1: mixi F 1427 71.3% N 368 18.3% N 2 209 10.4% 2004 100% 25
5.3. MIXI 5.2: N 2 ( ) Basic CS 1 21 F 1,000,000 1 N 50 50 N 2 2550 2546 713265 275 5.3: (n = 250, 000) Basic CS 1 19 F 250,000 1 N 50 50 N 2 2550 2536 5.4: (n = 62, 500) Basic CS 1 17 F 62,500 1 N 50 50 N 2 2550 2509 5.5: (n = 7, 812) Basic CS 1 14 F 7,812 1 N 50 50 N 2 2550 2106 26
5.4. 5.4 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 10 12 x13 x 14 x 15 x 1 8 = h L x 1 1 ( h L ( h L ( 1 ))) 5.6: 27
5.5. 5.5 2.1 45% HTTP Basic 28
29 6 6.1 HTTP Basic CS Web mixi 2 Web 6.2 Web ACL mixi
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 ))))
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
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 11 7.1: 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
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,1100. 33
7.2. [11] K 0 0,0000 K 0 0, K 0 0,0010 0001 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,0111 3 K 1 3,1101 K 1 3,1110 7.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 1 1 0 0 7.4: 34
7.2. [11] LN 0 K 0 0,1000 LN 1 K 1 0,1100 LN 2 7.5: 35
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 7.1 6 90% 6-degree 7.1: degree (%) 0 1 1 0.0 1 336 337 0.2 2 14,059 14.396 9.7 3 68,489 82,885 56.1 4 50,510 133,395 90.3 5 11,925 145,320 98.4 6 1,987 147,307 99.7 7 316 147,623 100.0 8 53 147,676 100.0 9 4 147,680 100.0 36
37 [1] 18 http://www.soumu.go.jp/s-news/2006/060413 2.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. 41-62(2001) [3] C. Wong, M. Gouda and S. Lam Secure Group Communications Using Key Graphs Proc. of ACMSIGCOMM 98, pp. 68-79(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. 131-136(2003) [6] mixi http://mixi.jp/home.pl [7] RBAC Vol.47 No.6 pp.1932-1940(2006) [8] Vol.41 No.8 pp.2255-2263(2000) [9] Vol.47 No.6 pp.1918-1931(2006) [10] SD Vol.47 No.2 pp.426-433(2006) [11] - - 2002 (SCIS) pp. 721-726(2002)
[12] 6 -SNS Six Degrees of Separation- Vol.90 No.2 pp.148-150(2007) [13] GREE http://gree.jp 38
39 2 5