, Evaluation of Certificate Verification Methods in Mobile Environment Katsuyuki UMEZAWA,, Mitsuhiro OIKAWA, Seiichi SUSAKI, Satoru TEZUKA, and Shigei

Size: px

Start display at page:

Download ", Evaluation of Certificate Verification Methods in Mobile Environment Katsuyuki UMEZAWA,, Mitsuhiro OIKAWA, Seiichi SUSAKI, Satoru TEZUKA, and Shigei"

あきおかつもと
5 years ago
Views:

1 , Evaluation of Certificate Verification Method in Mobile Environment Katuyuki UMEZAWA,, Mituhiro OIKAWA, Seiichi SUSAKI, Satoru TEZUKA, and Shigeichi HIRASAWA PKI PKI CRL OCSP CVS 3 3 CVS PKI CVS OCSP CRL 1. ID PKI Hitachi, Ltd., Sytem Development Laboratory, Hitachi Sytem Plaza Shinkawaaki, 890 Kahimada, Saiwai-ku, Kawaaki-hi, Japan Graduate School of Science & Engineering, Waeda Univerity, Okubo, Shinjuku-ku, Tokyo, Japan (GPKI) PKI 384 D Vol. J90 D No. 2 pp c 2007

2 CRL (Certificate Revocation Lit) OCSP (Online Certificate Statu Protocol) CVS (Certificate Validation Server) 1 2 [1] CRL OCSP CVS CRL OCSP CVS ITU-T X.509 (2000) [5] RFC3280 [6] 2. 1 CRL (Certificate Revocation Lit) [5], [6] OCSP (Online Certificate Statu Protocol) [7] CVS (Certificate Validation Server) [8], [9] CRL CRL CRL (Certification Authority CA) CRL CRL CRL CRL CRL CRL 1 SCVP [15] CVS [2] [4] 385

3 2007/2 Vol. J90 D No. 2 δ-crl 5 CRL CRL δ-crl bae-crl CRL CRL bae-crl δ-crl bae-crl CRL δ-crl bae-crl OCSP OCSP OCSP (Varidation Authority VA) (good) (revoked) (unknown) CVS CRL OCSP CVS CVS (GPKI) [8] [9] [14] (CA) (VA) CA VA CRL OCSP CVS CA VA [1] (δ-)crl 2 3 VA OCSP 2 VA VA CVS VA CA CRL 5 VA VA OCSP VA 6 1 Table 1 Claification of the certificate verification method. CRL OCSP CVS 1 (δ-)crl Fig. 1 (δ-)crl model. 5 CRL CRL CRL (CRT Certificate Revocation Tree) 6 VA

4 2 OCSP 1 Fig. 2 OCSP model 1. 3 OCSP 2 Fig. 3 OCSP model 2. 4 CVS 1 Fig. 4 CVS model 1. N k q r β α M 1 M 2 M 3 M 4 M 5 D n D ig D n D ig 5 CVS 2 Fig. 5 CVS model 2. 2 Table 2 Notation. [ ] VA [ ] CA [ ] 1 [ /day ] CA +1 [ ] VA [bit/] VA VA CA VA [] [] [] CRL [] [] OCSP [bit] OCSP [bit] CVS [bit] CVS [bit] 3. 2 CRL CRL CRL CRL CRL C x M x R x T x T x = C x + M x + R x (1) x C x M x R x C x 387

5 2007/2 Vol. J90 D No. 2 λ X P (X) =λ X e λ /X! [1] q [ /day ] CA k [ ] T [day] CA qt/k 1. A 1 2 CA λ = qt k 7 T T 1 p e X 1 p e T X 1 =1 e qt k (2) VA X X OCSP 1 N VA 1. A 2 2 OCSP 2 CVS 1 2 N/ VA 1. A 3 2 A 4 2 VA q = q N CVS 2 q 1 1. A 4 3 q Nv 1 VA 1. A 4 4 VA VA q = q N OCSP 1 CVS 2 k/ OCSP 2 CVS 1 k CA T VA CA qt/k N 1. A 2 3 A 4 5 N qt/k 1. A 3 3 VA T 1 OCSP 1 CVS 2 p T vx 1 OCSP 2 CVS 1 T p v X 1 p T vx 1 =1 qt e k N (3) p v T X 1 =1 e qt k NNv (4) 3. 4 CRL CRL δ-crl CA CRL CA VA CRL 8 CRL T C CRL CA 1 CRL 1 CRL C CRL (2) T = T C l CRL CA q C CRL = k pe T C X 1 lcrl T C q (5) l CRL CA 1 CRL 2. l CRL = N pl l n + l ig [bit] (6) k δ-crl bae-crl δ-crl C baecrl C delta C deltacrl = C baecrl + C delta (7) δ-crl bae-crl CRL CRL C baecrl (5) bae-crl T B C baecrl = k pe T B X 1 lcrl (8) T B q δ-crl C delta n δ-crl l delta (n) C delta = k pe T C X 1 TB TC 1 n=1 l delta (n) (9) T B q l delta (n) l delta (n)= N { ( ) pl n } 1 1 TC l n k L + l ig (10) 7 [1] 8 [1] CA CRL 388

6 3. CA VA CRL OCSP 1 CVS 2 k/ CA CRL OCSP 2 CVS 1 k CA CRL 1 CRL C x x (3) (4) T = T C l CRL CRL CA q β C OCSP1 = C CV S2 = k p T C vx 1 lcrl T C q β (11) C CV S1 = C OCSP2 = k pvt C X 1 l CRL (12) T C q β CRL r 1 CVS 1 CVS 2 VA 3 5 CRL δ-crl OCSP 1 r CRL δ-crl VA 1 5 M n (1 n 5) [] M 12 = M 1 + M 2 M 35 = M 3 + M 5 1 M x x 9 M CRL =(r 1)(M 12 + M 4) (13) M deltacrl = M CRL (14) M OCSP1 =(r 1)(M 12 + αm 4 + M 35) (15) M OCSP2 =(r 1)(M 12 + αm 4)+M 35 (16) M CV S1 =(r 1)α(M 12 + M 4)+M 35 (17) M CV S2 = M CV S1 (18) 3. 6 CRL δ-crl 0 10 CVS 1 2 r OCSP 1 2 CA r 1 OCSP 1 r 1 OCSP 2 CVS 1 2 OCSP 1 (r 1)(D n +D ig) OCSP 2 (r 1)D n + D ig CVS 1 2 rd n + D ig CVS 2 CA VA VA VA VA Nv 1 CVS 2 VA VA R CV S2 R CV S2 = Nv 1 (r 1) (Dn + Dig) β (19) VA VA VA OCSP 1 1 R x x 11 R CRL = R deltacrl = 0 (20) (r 1)(Dn + Dig) R OCSP1 = (21) (r 1)Dn + Dig R OCSP2 = (22) R CV S1 = rd n + D ig (23) { rd n + D ig R CV S2 = 9 r 1 CA 10 CRL

7 2007/2 Vol. J90 D No. 2 + Nv 1 } (r 1)(Dn + Dig) β (24) M 2 M VA (δ-)crl OCSP 1 2 CVS 1 12 (a) (1) T x x T x = C x + M x + R x (2) (23) 3 1 T x x T CRL = M (25) T deltacrl = M (26) T OCSP1 = β (0.712α+4)M (27) T OCSP2 = β (0.712α+3)M (28) T CV S1 = β (2.712α+1)M (29) k, 384k, 6 =28.8k [bit/] Fig. 6 The average of the verification time in the each ytem when the tranaction peed i =28.8k [bit/]. 7 = 384k [bit/] Fig. 7 The average of the verification time in the each ytem when the tranaction peed i = 384k [bit/]. 2.4M [bit/] α = β = 100 CA VA 100 (25) (29) Y CRL 12 CVS 2 390

8 3 Table 3 Parameter for evaluation. 1 2 N [ ] 77,229, ,000 N [ ] 633,000 77,229,000 q [ /day] p [ /day] 0.1/ /365 L [day] CRL δ-crl T C [day] 1 1 CRL l n,[bit] CRL l ig [bit] CA k [ ] VA [ ] OCSP D n [bit] OCSP D ig [bit] CVS D n [bit] 6,464 6,464 CVS D ig [bit] bae-crl T B [ ] M 1 [] 0 0 M 2 [] M M M 3 [] 0 0 CRL M 4 [] 0.356M 0.356M M 5 [] M M M Table4 ThevalueofM that i the interection in Fig. 6, 7 and k 384k 2.4M T CRL M = M = M = T deltacrl M = M = M = T OCSP 1 M = M = M = T OCSP 2 M = M = M = =2.4M [bit/] Fig. 8 The average of the verification time in the each ytem when the tranaction peed i =2.4M [bit/]. Y CVS CVS (α =1.0) (β =1.0) OCSP 2 CVS 1 (28) (29) M T CV S1 >T OCSP2 CVS CVS (b) CVS T CV S1 M 4 391

9 2007/2 Vol. J90 D No k [bit/] M = T CV S1 T OCSP2 26.2m [] CVS (c) CVS VA α α 0.5 = 384k [bit/] =2.4M [bit/] OCSP 1 OCSP 2 CVS 1 9 CVS 1 9 CVS 1 α CVS 1 9 CVS CVS (CRL) CRL CVS 2 13 VA VA CVS 1 CVS 1 CVS 2 VA VA CA α =0.5 VA β =1.0 CA VA VA = 100M [bit/] CVS OCSP 1 2 CVS Fig. 9 Area where average verification time of CVS method become mall more than OCSP method 1 and = 100M [bit/] Fig. 10 The average of the verification time in the each ytem when the tranaction peed i = 100M [bit/] CA CRL VA CA CRL OCSP VA CRL 392

10 14 10 CVS 1 CVS 2 (CRL) CVS CRL OCSP CVS 3. CRL OCSP [2] CVS 1 CDMA 1x WIN BREW CPU Intel r Pentium r GHz 2GByte OS Window r XP operating ytem 5 (M CV S1) (R CV S1) (T CV S1) CRL C CV S1 =0 M 35 =0 675 [Byte] 569 [Byte] 5[Byte] 1249 [Byte] rd n + D ig = 9992 [bit] α =0.16/ CRL 7 CRL 4. M (17) (28 [m]) 2 (r =2) (M 35 =0) (α =0.16/10.03) M 12+M 4 = 1755 [m] (13) (14) CRL M CRL = M deltacrl = 1755 [m] (15) (16) 7 CRL M 4 =0.356M 2 M 1 =0 M OCSP1 = M OCSP2 = 1302 [m] (23) (879 [m]) 9992 [bit] = [bit/] 1 OCSP 704 [bit] (21) (22) R OCSP1 = R OCSP2 =62[m] 8 γ n (n = 1, 2, 3) 1 1 CRL 6 Table 6 The meaurement value of ignature generation time. [m] CRL Table 7 The ratio between time of verifying ignature and earching CRL. (M 2 M 5) 1 CRL (M 4) Table 5 The meaurement value of certificate validation time. [m] (M CV S1) 28 (R CV S1) (879) (T CV S1) 907 * 8 Table 8 Certificate verification time of each method. [m] T CRL T deltacrl γ 1 T OCSP 1 T OCSP γ 2 T CV S γ 3 14 OCSP

11 2007/2 Vol. J90 D No. 2 (5) (11) (12) CRL CA k VA T C q q 1 T p C T ex 1 p C vx 1 p T C vx 1 1 γ n γ 1 = l CRL/ γ 2 = γ 3 = l CRL/(β ) VA VA CA β >1 γ 1 >γ 2 = γ 3 15 γ 8143 [Byte] CRL CRL 106 [m] (6) 3 CRL 1230 [Byte] 106 [m] γ CVS CRL CRL CRL λ =(q N/Nv)/( ) M/M/S [m] 15 T = R CRL δ-crl CRL CRL 1 δ-crl CRL γ 1 11 Fig. 11 The average repone time. 5. VA (NICT) Window Microoft Corporation Intel Pentium Intel Corporation BREW BREW Qualcomm [1] PKI vol.45, no.12, pp

12 2833, [2] IT , Sept [3] 2005 pp , Oct [4] 28 pp , Nov [5] ITU-T Recommendation X.509 (2000) ISO/IEC :2001: Information Technology Open Sytem Interconnection The Directory: Public-key and Attribute Certificate Framework. [6] R. Houley, T. Polk, W. Ford, and D. Solo, RFC Internet X.509 Public Key Infratructure Certificate and Certificate Revocation Lit (CRL) Profile, IETF, April [7] M. Myer, R. Ankney, A. Malpani, S. Galperin, and C. Adam, RFC X.509 Internet Public Key Infratructure Online Certificate Statu Protocol OCSP, IRTF, June [8] H15/12/17 [9] D-I vol.j87-d-i, no.8, pp , Aug [10] X.509 vol.2005, no.33, pp.55 60, [11] S. Hane, T. Fujihiro, Y. Hahimoto, T. Kaji, K. Kondo, and S. Tezuka, Speeding up X.509 certificate path validation, 4th International Workhop for Applied PKI, IWAP2005, [12] PKI 2002, pp , [13] (GPKI) OFS , [14] vol.2005, no.70, pp , [15] T. Freman, R. Houley, A. Malpani, D. Cooper, and T. Polk, Simple Certificate Validation Protocol (SCVP), IETF, July [16] CRL A 1 A 4 CRL OCSP 2 CVS 1 CRL 2. l CRL p 16 CRL A 1 (δ-)crl CRL Fig. A 1 Derive the average of the acquirement time of CRL for (δ-)crl model. A 2 OCSP 1 CRL Fig. A 2 Derive the average of the acquirement time of CRL for OCSP model [1] 395

13 2007/2 Vol. J90 D No. 2 l n l ig (6) 3. l delta(n) bae-crl n δ-crl P n CA T C N pt C/k [ ] P nt C/L [ ] A 3 CVS 1 OCSP 2 CRL Fig. A 3 Derive the average of the acquirement time of CRL for CVS model 1 and OCSP model 2. A 4 CVS 2 CRL Fig. A 4 Derive the average of the acquirement time of CRL for CVS model 2. N table (N,L,p,k) CA 1 N p/k [ ] N table (N,L,p,k)/L [ ] N table (N,L,p,k) N table (N,L,p,k)= N pl (A 1) k CRL l CRL P n+1 = P n + N pt C k PnTC L (A 2) P 0 =0 P n 1 n T B/T C 1 P n = N { ( ) pl n } TC 1 (A 3) k L n δ-crl l delta (n) l n l ig (10) N 2 N [16] ,126 IP 1 N 2 N [16] / 26.0% 20.3% 14.6% 3 1 q [16] [ / ] [ / ] 1 3[ /day]

2 q 1 1 77,229,000 3[ ] 633,000 [ ] 77,229,000 3/633,000 p L T C l n l ig [1] [1] N N [1] 1 2 N N CA k 2 CA 1 VA 19 (B) (C) A:

75 [m] (A 4) C deltacrl = 277.03 [m] (A 5) C OCSP1 =7.37 10 6 [m] (A 6) C OCSP2 =7.37 10 5 [m] (A 7) C CV S1 =7.

14 2 q ,229,000 3[ ] 633,000 [ ] 77,229,000 3/633,000 p L T C l n l ig [1] [1] N N [1] 1 2 N N CA k 2 CA 1 VA 19 (B) (C) A: 1/7 B: 1/18 C: 1/ CRL 1:0.356 CRL l CRL (6) 3 l CRL = 9843 [bit] CRL 5. CRL (5) (7) (11) (12) 1 CRL C CRL = [m] (A 4) C deltacrl = [m] (A 5) C OCSP1 = [m] (A 6) C OCSP2 = [m] (A 7) C CV S1 = [m] (A 8) D n D ig [7] D n D ig [3] T B [1] M 1 M 1 0 M 3 0 M 2 M 5 M M 4 CRL M 6 CRL 3 1 (A) 19 (MVNO)

15 2007/2 Vol. J90 D No LAN UCLA IEEE Fellow 2001 ACM 398

untitled

untitled better RFID 1 /?? PKI PKI ) (GPKI) GtoB GPKI 3300- LGPKI GtoC -> Identrus B2B GPKI Identrus PKI 2 Internet-VPN PKI? HTTPS ( ) HTTPS 3 PKI??????? PDA/ /? RFIDPKI?? 4 Challenge