모바일 환경을 위해 수정된 TPM이 장착된 디바이스의 원격 익명 입증 프로토콜

신승목*, 이기열**, 김광조*

*정보통신공학과, KAIST

**부경대학교 대학원 컴퓨터공학과

Modified Anonymous Attestation Protocol of the TPM-installed device for the Mobile Environment

Sung-Mok Shin*, Ki-Yeal Lee**, Kwangjo Kim*

*Department of Information and Communications Engineering, KAIST

**Department of Computer Engineering, Graduate School,

Pukyong National University

요 약

미래의 신뢰 컴퓨팅 기술을 제공하기 위해 TCG에서는 TPM이라는 보안 장치를 제안하고, 이를 활용하기 위해 DAA라는 원격 익명 입증 프로토콜을 제안하고 있다. DAA는 Chaum과 Heyst에 의해 제안된 그룹 서명과 Camenisch와 Lysyanskaya에 의해 제안된 서명, 그리고 영지식 증명을 기반으로 하는 새로운 개념의 원격 익명 입증 프로토콜이다. 그러나 DAA는 많은 계산량을 요구하기 때문에 PC 기반의 장치 외에는 사용하기 어렵다는 단점이 있다. 또한 불법 TPM 검색에 이용되는 베이스 네임 생성 방법이 랜덤 값을 생성하는 방식이기 때문에 불법 TPM이 적법한 TPM으로 위장할 수 있는 문제점이 있다.

이러한 문제들을 해결하기 위해 본 논문에서는 모바일 환경에 적합한 원격 익명 입증 프로토콜을 제안한다. 제안방식은 현재 DAA가 가지고 있는 계산량에 대한 문제 해결을 위해서   Camenisch와 Stadler에 의해 제안된 서명 기법의 장점을 활용한다. 제안방식은 다음과 같은 장점을 가지고 있다 : 첫째, 현재의 DAA에 비해 3.6배가량 적은 계산량을 요구한다. 둘째, 불법 TPM에 의한 위장공격을 방지한다. 본 논문은 제안방식을 Java 기반으로 구현한 후 PC와 PDA에 각각 설치한 후 입증에 걸리는 시간을 측정하여 제안방식이 모바일 환경에서 적합하게 사용될 수 있다는 것을 증명한다.

서론

최근 네트워크와 컴퓨팅 기술의 발전으로 인터넷 사용량이 급격히 증가하고 이로 인해 웹상에서 디바이스의 합법성에 대한 입증기법의 필요성이 증가하고 있다. 그러나 이러한 서비스들은 웹상에서 안전한 디바이스 합법성 입증을 수행하기 위해 사용자의 개인 정보를 필요로 하고, 더 높은 보안 강도를 위해 더 많은 사용자의 개인 정보를 필요로 하게 된다. 이는 사용자의 신원, 즉 개인 정보가 웹상에 유포될 수 있는 가능성을 높이고, 인터넷 서비스를 이용하는 사용자들에게 불안감을 높이는 원인이 된다.

이를 해결하기 위해 Intel, IBM, Sun, 삼성전자와 같은 대형 IT 기업들은 TCG(Trusted Computing Group) [1,2,3]를 결성하여 이종 컴퓨팅 플랫폼에서 컴퓨팅 보안을 강화시키기 위해 표준을 제정해왔다. 특히 TCG는 TPM(Trusted Platform Module) [5]이라는 디바이스를 제안하여 PC, 임베디드 플랫폼, 모바일 환경에 대한 보안 기능을 강화하고자 노력하고 있다.

TCG는 공개키 암호화 방식에 기반을 두어 디바이스가 불법으로 사용되는지 아닌지를 입증(Attestation)하기 위해서 Privacy CA(Certificate Authority)라는 방식을 제안하였다. 하지만 공개키 기반 암호화방식과 같이 Privacy CA 역시 CA에  중요 기능이 집중되어 연산량이 커지고 CA가 공격당할 경우 전체 사용자의 보안이 위협받는 다는  단점을 지니고 있다. 또한 TPM은 Privacy CA를 통해서 합법성을 입증할 때 프라이버시 보호를 위해서 AIK(Attestation Identity Key)를 매번 만들어야 한다는 단점을 가지고 있다. 그림 1은 Privacy CA의 입증 방식을 나타낸다.

[그림 1] Privacy CA 방식의 원격 익명 입증 프로토콜

이에 TCG는 버전 1.2 [5]를 제안하면서 DAA(Direct Anonymous Attestation) [6]라는 원격 익명 입증 프로토콜을 제안하였다. Erikbell, Camenisch와 Chen에 의해 제안된 DAA는 그룹서명과 영지식 증명(Zero Knowledge Proof)에 기반을 두고 있으며, 이를 활용하여 TPM이 장착된 디바이스를 소유한 사용자의 익명성을 보장하면서 디바이스의 합법성을 입증할 수 있다.

하지만 DAA는 영지식증명과 여러 가지 서명 방식에 기반을 두고 있어 많은 계산량을 요구한다는 문제가 있다. 따라서 연산 능력이 충분한 PC 이외의 모바일 기기 등에서는 사용하기 어렵다. 또한 불법 TPM(Rogue TPM) 검색에 이용되는 베이스 네임 생성 방법이 랜덤 값을 생성하는 방식이기 때문에 불법 TPM이 적법한 TPM으로 위장할 수 있는 문제점이 있다.

본 논문에서는 연산량을 낮추고 불법 TPM의 위장 문제를 개선한 수정된 원격 익명 입증 프로토콜을 제시한다. 제안방식은 현재 DAA가 가지고 있는 계산량에 대한 문제 해결을 위해서 Camenisch와 Stadler(CS 서명) [11]에 의해 제안된 서명 기법의 장점을 활용한다. 제안방식은 다음과 같은 장점을 가지고 있다 : 첫째, 현재의 DAA에 비해 3.6배가량 적은 계산량을 요구한다. 둘째, 불법 TPM에 의한 위장공격을 방지한다. 본 논문에서는 제안방식을 Java 기반으로 구현한 후 PC와 PDA에 각각 설치한 후 입증에 걸리는 시간을 측정하여 제안방식이 모바일 환경에서 적합하게 사용될 수 있다는 것을 증명한다.

본 논문의 구성은 다음과 같다. 2장에서는 TCG와 DAA에 관해 소개하고 DAA의 문제점을 분석한다. 3장에서는 수정된 원격 익명 입증 프로토콜을 제시한다. 4장에서는 제안방식의 계산복잡도와 안전성을 평가한다. 끝으로 5장에서는 결론을 내린다.

관련연구

2.1 TCG

TCG는 이종 컴퓨팅 플랫폼에서 컴퓨팅 보안을 강화시키고자 하는 목적으로 설립된 비영리 산업 표준화 기관이다. Intel, IBM, Sun등의  중심 기업들이 대표로 구성되어 정책을 결정하면서 여러 개의 워킹 그룹과 기술 위원회를 두고 있다. TCG는 컴퓨터 플랫폼 내부로의 "Root of Trust"를 결합하기 위한 목적을 가지고 있다. TCG는 소프트웨어 적인 솔루션만으로는 하드웨어 컴퓨팅 플랫폼에 대한 보안 기능을 더 이상 보장할 수 없다고 생각하여 신뢰 컴퓨팅 플랫폼을 기반으로 하는 하드웨어와 운영체제의 성능 향상을 위해서 규격을 개발하고 있다. 그림 2는 TCG의 보안 구조를 도식화한 것이다.

[그림 2] TCG Overview [1]

2.2 DAA

DAA는 그룹 서명[7]과 영지식 증명에 기반을 둔 원격 익명 입증 프로토콜이다. TPM이 장착된 디바이스를 소유한 사용자는 본 프로토콜을 사용하여 자신의 익명성을 보장받으며 웹으로 제공되는 서비스를 사용할 수 있다. DAA는 다음과 같은 특징을 가지고 있다.

- 직접 증명(Direct Proof) :　TTP(Trusted Third Party)를 따로 두지 않고도 영지식 증명을 이용하여 TPM과 검증자의 통신상에서 TPM의 합법성 입증이 가능하다.

- 익명성 지원(Anonymity) : 어떠한 서명에 대해서 서명자의 신원이 밝혀지지 않는다.

- 서명 개봉능력 삭제 : 그룹서명에 기반을 두지만  기존의 그룹서명과는 달리 서명을 개봉(Open)할 수 있는 능력은 없다.

- 불법 TPM 식별 가능 : 적법한 과정을 통해 키를 발급받지 못한 TPM이 웹서비스를 사용하지 못하도록 할 수 있다.

- NP 문제에 기반 : Strong RSA 가정 [8] 및 Decisional Diffie-Hellman 가정 [9]에 기반하므로 랜덤 오라클 모델에서 안전하다.

2.2.1  DAA의 구성

DAA는 TPM이 장착된 디바이스들끼리 미리 약속된 프로토콜을 통해 정보를 주고받음으로써 사용자의 익명성을 지키면서 합법성 입증을 할 수 있게 해준다. DAA에 참여하는 주체들은 다음과 같다.

- TPM / 호스트 : 키, 패스워드, 그리고 디지털 인증서를 저장하는 하드웨어모듈이다.

- 발행자(Issuer) : 인증서를 발급해주는 역할을 하는 주체이다. TPM과의 통신 프로토콜을 통하여 현 TPM의 무결성이 보장되면 플랫폼에 인증서를 교부해주는 역할을 한다.

- 검증자(Verifier) : TPM / 호스트는 발급받은 인증서를 사용하여 서명을 생성하고 그 서명을 검증자에게 유효성을 검증받는다.

DAA는 그룹 서명을 기반으로 한 서명 방식을 제안하고 있다. 그룹 서명의 절차는 시작(Setup), 준비(Join), 서명(Sign), 검증(Verify), 서명 개봉(Open)으로 나눌 수 있다. 하지만 DAA는 사용자의 익명성을 제공하기 위해 그룹 서명의 서명 개봉 부분을 제외시켰다. 다음 표 1은 프로토콜에서 사용되는 표기법을 기술한다.

[표 1] 표기법

표기	의미
{0, 1}[eqn: {} ^{}][eqn: {} ^{l}]	길이 [eqn: l]의 이진스트링의 모든 집합
[eqn: g']	이차 잉여 모듈러 n그룹의 [eqn: QR _{n}]에 대한 랜덤 생성자
[eqn: g,`h,`S,`Z,`R _{0} ,`R _{1}]	선택되는 6개의 랜덤 정수
[eqn: ( GAMMA ,` rho ,` gamma )]	보안 파라미터를 만족하는 소수
[eqn: (n,`g prime ,`g,`h,`S,`Z,`][eqn: R _{0} ,`R _{1} ,` GAMMA ,` rho ,` gamma )]	발행자의 공개키
[eqn: f,`v _{1}]	TPM의 비밀정보
[eqn: f _{0} ,`f _{1}]	각각 [eqn: f]값의 LSB(Least Significat Bit), MSB(Most Significant Bit)
SPK	지식 서명(Signature Proof of Knowledge)
[eqn: U,`N _{I}]	TPM의 비밀정보와 발행자로부터 받은 공개키를 사용하여 생성된 증명 값
[eqn: zeta]	TPM의 베이스네임을 사용하여 생성되는 challenge 값
(A, e, v'')	발행자와 호스트 간에 합의된 세션 키
w, r	호스트에서 선택된 랜덤 값
[eqn: hat{T _{1}} , hat{T _{2}} ,` hat{T _{3}}]	호스트에서 선택된 랜덤 정수 w, r을 사용하여 계산된 값
[eqn: c']	[eqn: hat{T _{1}} , hat{T _{2}} ,` hat{T _{3}} ,` hat{N _{v}}] 값을 사용하여 검증자로부터 생성되는 서명 비교를 위한 값

다음은 DAA에서 이용하는 그룹 서명의 절차에 대한 설명이다.

- 시작 : Fiat-Shamir[10] 방식을 사용하여 발행자의 공개키와 비밀 키를 작성한다.

[그림 3] 시작과정

- 준비 : TPM은 DAA 발행자에게 [eqn: N _{1} ^{f}] 형태의 가명(pseudonym)을 전달하여 자신이 비밀 정보 [eqn: f]를 가지고 있다고 증명하고, 발행자를 통해 [eqn: v'']의 값을 받아서 인증서를 발급받는다.

[그림 4] 준비과정

- 서명 : TPM은 발급받은 인증서(credential)를 이용하여 메시지 m을 서명한다.

[그림 5] 서명과정

- 검증 : DAA 검증자에 의해 서명과정에서 생성한 서명의 유효성을 검증 받는다.

[그림 6] 검증과정

- 서명 개봉 : 프라이버시 보호를 위해서 그룹 서명 방식과 달리 DAA는 서명 개봉 연산을 제공하지 않는다.

2.3 DAA의 취약점

DAA는 영지식 증명을 이용하기 때문에 다른 그룹 서명 기법보다 많은 연산을 요구한다. 또한 베이스 네임(Base name)의 결정 방식을 2가지로 두어 베이스 네임에 따른 불법 TPM의 위장 문제를 발생 시킬 수 있다. 마지막으로 TPM을 검증하는 검증자가 발행자의 결탁에 따른 프라이버시 문제점을 생각할 수 있다. 본 논문에서는 이러한 문제점에 대해서 살펴보고 문제점을 해결하는 방안을 제시할 것이다.

(1) 많은 계산량에 대한 문제점

DAA는 영지식 증명을 이용하기 때문에 많은 계산량을 요구한다[12]. 4장에서의 PC 기반의 DAA 모듈을 PDA에 포팅하여 실행시켰을 경우 서명과정에 걸리는 시간이 1시간가량 소비되었다. 따라서 PC 또는 모바일 환경에서 DAA를 효율적으로 사용하기 위해서는 계산량을 줄인 수정된 원격 익명 입증 프로토콜이 필요하다.

(2) 베이스 네임 결정에 대한 문제점

DAA를 제안한 저자들은 불법 TPM 검색에 이용되는 베이스 네임의 생성 방법을 두 가지로 제시하였고, 이 방법 중 개발자에 맞는 방법을 사용하도록 제안하고 있다. 베이스 네임 생성 방법은 종류는 다음과 같다.

- 발행자와 검증자에서 베이스 네임 생성 : TPM에서 계산하는 [eqn: zeta]의 기초가 되는 베이스네임의 값을 발행자와 검증자가 생성한 이름을 사용하여 계산하는 방법이다.

- TPM이 생성한 값을 베이스네임으로 이용 : TPM에서 랜덤으로 생성한 값을 베이스네임으로 사용하는 방법이다.

성능 향상을 위해 수정된 원격 익명 입증 프로토콜

현재의 DAA는 모바일이 가지는 환경적 제약을 고려하지 않은 채 연구되어 모바일 환경에 바로 사용하기 어려울 것으로 예상된다. 따라서 본 논문에서는 모바일 환경에 사용할 수 있도록 수정된 원격 익명 입증 프로토콜을 제시한다. 이 프로토콜에서 필요한 보안 파라미터는 다음과 같다. 보안 파라미터는 Camenisch와 Lysyanskaya(CL 서명) [13]의 서명 기법 중 단일 메시지 서명 기법에 이용된 파라미터 크기를 적용하였다.

- [eqn: l _{n} (1024)] : RSA 계수 n의 길이

- [eqn: l _{x} (160)] : TPM이 가지는 EK(Endorsement key)의 비밀 키의 부분 정보 길이

- [eqn: l _{H} (160)] : 해시 함수(SHA-1) 결과의 길이

- [eqn: l _{c} (162)] : 준비과정에서 필요한 영지식 증명 랜덤 소수 c의 크기

- [eqn: l _{r} (1264),`l _{w} (1185)] : 서명 증명을 위해 사용되는 랜덤 소수의 크기

- [eqn: l _{v} (1185)] : 준비과정을 통해서 얻어진 비밀 정보 v의 크기

3.1 발행자의 시작 프로토콜

발행자의 공개키와 비밀키를 만드는 과정을 기술한다. 발행자의 공개키는 준비, 서명 프로토콜의 인자로 사용되며 비밀 키는 발행자에 의해 보호된다. 기존 프로토콜에서는 6개의 랜덤 정수를 선택하여 공개키에 포함시켰지만 제안방식에서는 2개의 랜덤 정수만을 생성하여 공개키로 사용한다.

프로토콜 1. 수정된 시작 프로토콜
(1) 발행자는 [eqn: p=2p'+1]과 [eqn: q=2q'+1]을 만족하는 RSA 계수 [eqn: n]=[eqn: pq]을 선택한다. 여기에서 [eqn: p,`q,`p',`q']는 소수이다. (2) 발행자는 또한 [eqn: QR _{n}]의 랜덤 생성자 [eqn: g prime]를 선택한다. (3) 랜덤 정수 [eqn: x _{g} ,x _{s} IN [1,`p',`q']]을 만족하는 [eqn: g], [eqn: S] 값을 계산한다. g[eqn: =g prime ^{x _{g}} mod`n`````S=]g[eqn: {} ^{x _{s}} mod``n] (4) 생성된 [eqn: g]가 <[eqn: g']>에 [eqn: S]가 <[eqn: g]>에 포함되는지 판단한다. (5) 발행자가 자신의 공개키([eqn: n], [eqn: g'], [eqn: g], [eqn: S])를 공개키로 공개하고, [eqn: p']*[eqn: q']를 비밀 키로 저장한다.

3.2 준비 프로토콜

준비 프로토콜은 TPM을 가지고 있는 디바이스(호스트)의 사용자가 자신의 TPM을 통하여 디바이스의 합법성을 입증 받고자 할 때 사용되는 인증서를 얻기 위한과정이다. 본 논문에서는 CL 서명과  CS 서명을 활용하여 기존의 준비 프로토콜을 수정하였다. 기존 프로토콜에서는 랜덤 값을 사용하여 베이스 네임을 생성하여 불법 TPM의 위장 공격이 가능하였지만 제안방식에서는 [eqn: result]라는 값을 생성하여 값을 비교함으로써 위장공격을 방지할 수 있다. 그리고 [eqn: SPK]값의 생성 방식을 수정하였다.

프로토콜 2. 수정된 준비 프로토콜
(1) TPM은 영지식 증명에 사용될 [eqn: Z _{n} ^{*}]에 속하는 랜덤 정수 w를 선택한다. (2) TPM은 아래의 식을 이용하여 ([eqn: x], [eqn: U,`B], [eqn: N _{I}])를 계산한다. [eqn: x]는 자신이 소유한 EK(Endorsement key) 비밀 키의 부분 정보를 나타낸다. TPM은 랜덤 수 [eqn: r]을 택하여 [eqn: B]의 값을 계산한다. 계산이 완료되면 TPM은 [eqn: U,`B], [eqn: N _{I}] 를 발행자에게 전송한다. [eqn: x=LSB _{l _{x}} (EK _{sk} )] [eqn: U=g ^{x} (mod``n),`B=g ^{r} (mod``n)] [eqn: zeta _{I} =H(g||U||0)(mod``n),`N _{I} = zeta _{I} ^{x} (mod``n)] (3) 발행자는 rogue list(불법 TPM에 대한 정보가 들어있는 리스트)를 이용하여 [eqn: U,`B], [eqn: N _{I}]를 전송한 TPM이 불법적인지 아닌지를 판단하고 불법적이면 요구를 무시한다. (4) 발행자는 다음과 같은 서명 지식 증명(Signature Proof of Knowledge : SPK)을 수행한다. SPK의 수행과정은 아래와 같다. {[eqn: SPK(x):U=±g ^{x} (mod``n) LAND N _{I} = zeta _{I} ^{x} (mod``n)]} - 발행자는 랜덤 값 [eqn: c]를 선택하여 호스트에게 전송한다. - 호스트는 TPM에게 [eqn: c]를 전송하고, TPM은 s=r+cx를 선택한다. TPM은 [eqn: result=H(a ^{s} ||c)]을 계산하고 호스트를 통해 s, [eqn: result]를 전송한다. - 발행자는 [eqn: BU ^{s}] 를 계산하고, [eqn: result=H(BU ^{s} ||c)]인지를 검사한다. 결과가 일치하면 인증서를 요구하는 TPM은 합법적이므로 U를 이용하여 TPM의 인증서의 정보 v를 생성한다. (5) 발행자는 다음 식을 이용하여 TPM이 인증서 정보 v를 생성한 후 호스트에 전송한다. [eqn: v == (U+1) ^{1/e} (mod``n)] (6) 호스트를 통해 [eqn: v]의 정보를 받은 TPM은 ([eqn: x], [eqn: v])를 인증서로 생성하여 저장한다.

3.3 서명 프로토콜

서명과정은 TPM/host를 소유한 사용자가 어떠한 메시지를 서명하기를 원할 때 준비과정에서 얻은 인증서 정보 ([eqn: x,`v])와 발행자의 공개키를 이용하여 전자서명을 생성하는 과정이다. 본 논문에서는 기존의 DAA를 제안한 저자의 방식을 따르고 있다. 하지만 변경된 준비과정으로 인해 서명과정에서 계산량을 줄일 수 있었다. 서명과정은 다음과 같다.

프로토콜 3. 수정된 서명 프로토콜
(1) TPM은 자신의 [eqn: U]값을 이용하여 [eqn: zeta]를 생성한다. [eqn: zeta _{V} =H(g||U||1)(mod``n)] (2) TPM은 랜덤 정수 w, r을 선택하여 다음을 계산한다. 또한 TPM은 (1)에서 생성한 [eqn: zeta]를 이용하여 [eqn: N _{V}]를 계산한다. [eqn: T _{1} :=rg ^{x} S ^{v} mod``n````T _{2} :=g ^{w} mod``n] [eqn: N _{v} := zeta ^{x} mod``n] (3) TPM은 x, r, w 값을 숨기면서 x, r, w값을 가지고 있다는 것을 증명하기 위해서 [eqn: r _{x} ,`r _{r} ,`r _{w}]의 임의값을 선택한 후, [eqn: tilde{T _{1}} ,` tilde{T _{2}}]를 계산한다. 계산이 완료되면 결과를 이용하여 [eqn: c _{h}]를 계산한다. [eqn: tilde{T _{1}} :=T _{1} ^{r _{r}} g ^{r _{x}} mod``n`````` tilde{T _{2}} :=g ^{r _{w}} mod``n`````Z:=T _{1} ^{r} g ^{x} mod``n] [eqn: c _{h} :=H(T _{1} ||T _{2} || zeta _{v} || tilde{T _{1}} || tilde{T _{2}} ||m)] (4) TPM은 검증자의 검증에 사용될 비밀 정수 [eqn: s _{x} ,`s _{r} ,`s _{w}]를 계산한 후, 다음과 같은 전자서명 [eqn: sigma]을 생성한다. [eqn: s _{x} =r _{x} +c _{h} x````````s _{r} =r _{r} +c _{h} r````````s _{w} =r _{w} +c _{h} w# sigma =(c _{h} ,`U,`T _{1} ,`T _{2} ,`N _{v} ,`Z,`s _{x} ,`s _{w} ,`s _{r} )]

3.4 검증 프로토콜

검증과정은 서명과정에서 생성된 전자서명의 요소들을 이용하여 검증자는 전자서명의 유효성을 판단한다. 상대방의 비밀정보를 모르는 검증자는 영지식 증명을 통해서 상대방의 전자서명을 검증할 수 있다.

프로토콜 4. 수정된 검증 프로토콜
(1) 검증자는 [eqn: Z,` hat{T _{1}} ,` hat{T _{2}}]를 계산하여 [eqn: c _{h} ']값을 계산한 후, [eqn: c _{h} ']와 [eqn: c _{h}]의 값을 비교하여 같은지 판단한다. [eqn: hat{T _{1}} :=Z ^{-c _{h}} T _{1} ^{S _{r}} g ^{S _{x}} mod``n````` hat{T _{2}} :=T _{2} ^{-c _{h}} g ^{S _{w}} mod``n# c _{h} ':=H(T _{1} ||T _{2} || zeta _{v} || hat{T _{1}} || hat{T _{2}} ||m)] (2) [eqn: c _{h} ']와 [eqn: c _{h}]의 값이 같으면 다음의 공식을 이용하여 [eqn: zeta _{V} ,N _{I}]를 구한 후, rogue list에 존재하는 지를 파악한다. 만약 rogue list에 [eqn: N _{I}]가 존재한다면 검증과정을 철회하고, 존재하지 않는다면 TPM 인증서가 유효하다고 답을 한다. [eqn: zeta _{V} =H(g||U||1)(mod``n),`N _{V} = zeta _{V} ^{x} (mod``n)]

구현 및 평가

본 절에서는 구현을 통하여 현재의 DAA가 가지는 연산량에 대한 측정과 제안방식의 안정성 및 효율성에 대해 알아본다.

4.1 제안방식의 구현 및 평가

구현된 DAA 1.0은 PC 환경에 최적화되어 있다. 구현 환경은 다음과 같다.

- Language : JDK 1.5.2

- OS : Window 2003/XP, Windows CE

- 기타 API : JCE/JCA API

PC 환경에서 DAA를 수행함으로써, 기존의 프로토콜의 성능을 평가한다. 키의 크기가 2048인 경우, 100번씩의 수행을 통해서 수행 성능을 비교하였다. 다음 표 1은 프로토콜별 수행시간을 나타낸다. 표 2의 결과에 따르면, DAA는 대부분의 수행시간이 시작과정에서 소모됨을 알 수 있다. 시작과정은 그룹 서명에 필요한 공개키 생성 및 검증 부분에서 계산양이 많이 요구되며, 이로 인해 긴 시간이 필요하다.

[표 2] 프로토콜별 수행 시간

(2048비트, 단위 : msec)

	시작	준비	서명	검증
최소소요시간	478,844	2,469	2,390	2,234
최대소요시간	522,188	3,062	3,031	2,688
평균소요시간	489,257	2,542	2,409	2,319

표 3은 실제 사용하게 될 키 및 파라미터의 생성에는 영향을 미치지 않는 검증과정을 포함했을 경우와 제거했을 경우에 대한 시작과정의 수행시간을 2048bit와 512bit의 키 크기를 기준으로 측정한 것이다. 컴퓨터 연산을 통해서 만들어진 각각의 보안 파라미터들을 검증하지 않고, PC 연산의 능력을 사용하여 DAA를 수행하면 시작 수행 시간이 급격히 줄어들므로 PC 환경에서는 현재의 DAA를 이용할 수 있다.

[표 3] 검증과정 여부에 따른 시작과정의 수행 시간(단위:msec)

	검증과정 포함		검증과정 미포함
	2048bit	512bit	2048bit	512bit
최소소요시간	478,844	10,656	4,4047	987
최대소요시간	522,188	52,141	53,359	32,875
평균소요시간	489,257	19,376	14,207	9,307

그림 7, 8은 검증과정 여부에 따른 시작과정의 수행 시간을 그래프로 표현한 것이다. 실제 키 와 파라미터의 생성 및 계산과정보다 생성된 키와 파라미터의 유효성을 검증하는 과정에서 가장 많은 시간이 소모됨을 알 수 있다.

[그림 7] 2048bit에 대한 검증과정

포함 시작과정 수행시간

[그림 8] 검증과정 포함여부에 따른

시작과정 수행시간

기존의 DAA의 시작과정을 HP iPaq Hx2790 포켓 PC와 IBM J9을 이용하여 수행한 결과는 표4와 같이 나왔다. 표 4는 PC 기반에서 512bit의 검증과정이 미 포함된 시작과정의 시간과 PDA 기반에서 512bit의 검증과정이 미 포함된 시작과정의 수행 시간을 나타내는 결과이다.

[표 4] PC 및 모바일 환경의 시작

과정 수행 시간(단위:msec)

	PC 환경	PDA 환경
	512bit	512bit
최소소요시간	987	913,487
최대소요시간	32,875	4,141,472
평균소요시간	9,307	1,882,388

표 4에서 알 수 있듯이 기존의 PC환경에 맞게 구현된 DAA는 모바일 기기(PDA) 성능의 제약으로 인해 N 계수의 크기가 512이고, 생성된 키에 대한 검증과정을 뺏음에도 불구하고 PC환경과 200배가 넘는 수행 시간을 볼 수 있다. 따라서 기존의 영지식 증명을 기반으로 하는 DAA는 PDA 및 모바일 환경에서는 사용이 불가능한 것으로 판단된다. 하지만 계산량을 많이 요구하는 시작과정을 수행하는 발행자를 PC기반으로 만든 후, 준비, 서명, 검증과정만 모바일 환경에서 수행하게 구현한다면 모바일 환경에서도 충분히 원격 익명 입증 프로토콜을 사용할 수 있을 것으로 판단된다. 그러나 실질적으로 모바일 환경에 원격 익명 입증 프로토콜을 적용하기 위해서는 시작과정에서 요구하는 계산량을 감소시키기 위한 경량화 및 새로운 프로토콜 제안이 필요하다는 것을 확인 할 수 있다.

4.2 제안방식의 계산복잡도 분석

제안방식의 계산 복잡도는 모듈러 제곱과 곱셈의 연산에 의해서 좌우된다. 계산 복잡도 산출을 위해 [14]에 제시된 계산 복잡도 연산 방식을 이용한다.

[표 5] 기존 프로토콜과 제안방식의 연산량 비교

(준비과정 - 160곱셈의 횟수 : n번, 80곱셈의 횟수 : m번, 40곱셈의 횟수 : p번, 12곱셈의 횟수 : q번)

(서명과정 - 160곱셈의 횟수 : a번, 80곱셈의 횟수 : b번, 40곱셈의 횟수 : c번, 12곱셈의 횟수 : d번)

	기존 DAA		제안방식
	제곱 횟수	곱셉 횟수	제곱 횟수	곱셈 횟수
준비과정	(160*n)+(80*m)+(40*p)+(12*q)	((160*n)+(80*m)+(40*p)+(12*q))/2	(160*(n-12))+(80*(m-6))+(40*p)+(12*q)	((160*(n-12))+(80*(m-6))+(40*p)+(12*q))/2
서명과정	(160*a)+(80*b)+(40*c)+(12*d)	((160*a)+(80*b)+(40*c)+(12*d))/2	(160*(a-12))+(80*(b-10))+(40*(c-4))+(12*d)	((160*(a-12))+(80*(b-10))+(40*(c-4))+(12*d))/2
합계	(160*(n+a))+(80*(m+b))+(40*(p-c))+(12*(q-d))	((160*(n+a))+(80*(m+b))+(40*(p-c))+(12*(q-d)))/2	(160*(n+a-24))+(80*(m+b-16))+(40*(p+c-4))+(12*(q+d))	((160*(n+a-24))+(80*(m+b-16))+(40*(p+c-4))+(12*(q+d)))/2

DAA에서 TPM과 호스트의 지수승 연산을 요구하는 프로토콜 과정은 시작과 서명 프로토콜과정이다. 따라서 TPM/호스트에 대한 DAA의 계산 복잡도를 구하기 위해서는 시작과 서명과정에 대한 계산 복잡도를 구하면 된다. 일반적인 지수승 연산 기법을 사용하여 기존의 DAA와 제안방식의 연산량을 비교하면 표 5와 같다. 계산의 단순화를 위해서 일반적인 지수승 연산 기법에 기반을 둔 계산 복잡도를 산출한다. 일반적인 지수승 연산 기법은 다음과 같다.

- 특정 지수연산에 대해서 [eqn: M _{1}]을 지수의 이진비트 길이라고 두고, [eqn: M _{2}]를 이진수로 표현한 값들 중 1의 개수라고 두자. 예를 들어 이진수가 (111101)[eqn: {} _{2}]일 때 [eqn: M _{1}]은 6이고 [eqn: M _{2}]는 5가 된다.

- 우리는 [eqn: M _{1} ,`M _{2}]를 이용하여 [eqn: M _{1}]을 제곱 연산의 횟수로, [eqn: M _{2}]를 곱셈 연산의 횟수로 계산할 수 있다. 예를 들어, [eqn: y=g ^{x} mod`n]과 [eqn: x IN]{[eqn: 0,`1 ^{}]}[eqn: {} ^{160}]이 주어졌다고 가정하면 x를 이진수로 변경하고 나서 예상되는 1의 개수는 80(=160/2)이다. 따라서 총 제곱 연산의 횟수는 160이고, 곱셈 수는 80이 된다.

표 5의 결과에 따라서 제안방식은 기존의 DAA보다 3.6배가량 빠르다는 것을 알 수 있다. 이 결과는 PC보다 덜 복잡한 기기에서도 원격 익명 입증 프로토콜을 사용할 수 있는 기반을 마련해 줄 것이다.

4.3 제안방식의 안전성 분석

제안방식의 안정성을 분석하기 위해서는 DAA의 기반이 되는 그룹서명의 요구사항을 만족하는 지를 살펴봐야 할 것이다. 제안방식이 그룹서명의 요구사항을 충족하면서 Strong RSA 가정을 만족한다면 제안방식은 랜덤 오라클 모델에서 안전하다. 제안방식은 다음과 같이 그룹서명의 요구사항을 만족한다.

- 건전성(Soundness)와 완전성(Completeness) : 공격자 E는 불법 TPM을 이용하여 생성한 인증서를 만들고자 발행자에게 Join 프로토콜을 요청하면, 발행자의 불법 TPM 검색을 이용하여 불법 TPM인지를 판단하고 요청을 거부한다. 검증자도 마찬가지로 불법 TPM 검색을 이용하여 공격자 E의 요청을 거부한다.

- 위조불가(Unforgeable) : TPM이 가지고 있는 EK의 비밀키를 기반으로 TPM의 인증서 및 서명이 생성을 생성한다. EK는 TPM의 생산단계에서 내장된 비밀키이므로, 공격자 E는 절대 EK를 알아낼 수 없다. 따라서 공격자 E가 EK의 비밀키를 알지 못하면, TPM의 인증서 및 서명을 생성할 수 없다. 인증서 생성은 Strong RSA 가정 및 Decisional Diffie-Hellman 가정을 기반으로 하고 있기 때문에 공격자가 EK를 알지 못하는 한 인증서를 생성할 수 없고 이로 인해 위조가 불가능하다.

결론

본 논문에서는 신뢰 컴퓨팅 기술 개발을 위해  TCG에서 제안한 원격 익명 입증 프로토콜인 DAA에 대해 분석한다. 또한 본 논문에서는 현재 DAA가 가지고 있는 높은 연산량 문제와 불법 TPM 검색 문제를 해결한 수정된 원격 익명 입증 프로토콜을 제안하였다.

본 논문의 제안방식은 현재의 DAA보다 3.6배가량 빠르게 합법성 입증을 수행하여 모바일 환경에서 DAA 적용을 가능하게 해줄 수 있을 것이다. 또한 기존 프로토콜이 가지고 있던 불법 TPM 검색에 대한 문제점을 해결하여 보안 기능을 한층 강화 하였다.

본 논문의 제안방식을 PC 기반으로 구현하여 PDA 환경에서와 성능을 비교함으로써 제안방식이 기존 DA보다 3.6배가량 빠르다는 것을 보인다. 이 결과를 통해 낮은 리소스를 가진 모바일 디바이스에서도 원격 익명 입증 프로토콜이 사용가능하다는 것을 보인다.

[참고문헌]

[1] TCG, "Mobile Trusted Module Specification Overview Document," 2006, http://citeseer.ist.psu.edu/ge06method.html

[2] TCG, "TCG Specification Architecture Overview Specification Revision 1.3," Specification, 2007.

[3] TCG, "Mobile Trusted Module Specification Overview Document," Specification, 2006.

[4] TCG, "TCG Sofrware Stack (TSS) Specification Version 1.2 Level 1," Specification, 2006.

[5] TCG, "TPM Main Part 1-3 Specification Version 1.2," Specification, 2007.

[6] E. Brickell, J. Camenisch and L. Chen, "Direct Anonymous Attestation," In Proceedings of 11th ACM Conference on Computer and Communications Security, ACS Press pp. 132-145, 2004.

[7] David Chaum and Eugene van Heyst, "Group Signature, Advances in Cryptography," Euro-CRYPT 91 pp. 257-265, 1991.

[8] Ronald L. Rivest, "RSA Problem," Encyclopedia of Cryptography and Security pp. 501-538, 2003.

[9] Dan Boneh, "The Decision Diffie–Hellman Problem," In Proceedings of the Third Algorithmic Number Theory Symposium, Lecture Notes in Computer Science, Vol. 1423, Springer-Verlag, pp. 48-63, 1998.

[10] Fiat and Adi Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems," Advances in Cryptology: Proceedings of Crypto 86 pp. 186-194, 1987.

[11] J. Camenisch and M. Stadler, "Efficient Group Signature Schemes for Large group," Advances in Cryptology - CRYPTO '97 pp. 410-424, LNCS 1294, 1997.

[12] He ge, "A Method to Implement Direct Anonymous Attestation," 2006, http://citeseer.ist.psu.edu/ge06method.html

[13] J. Camenisch and A. Lysyanskaya, "A signature scheme with efficient protocols," Security in Communication Networks, Third International conference, SCN 2002, LNCS 2576, 2003 pp. 268-289.

[14] A. J. Menezes, P. C. Oorschot and S. A. Vanstone. Handbook of Applied Cryptography, CRC press, Inc, 1997.