17 박민경KICS hwp

Transcription

1 논문 속성기반암호화방식을이용한다중서버패스워드인증키교환 박민경, 조은상 *, 권태경 * Multi Server Password Authenticated Key Exchange Using Attribute-Based Encryption Minkyung Park, Eunsang Cho *, Ted Taekyoung Kwon * 요 약 패스워드인증키교환프로토콜 (Password Authenticated Key Exchange: PAKE) 은서버와클라이언트가서로인증하고키를교환하는알고리즘이다. 패스워드를여러개의서버에나누어저장해서, 모든서버가손상되지않으면패스워드나키가유출되지않는알고리즘은다중서버 PAKE다. 속성기반암호화방식에서는암호화하는주체가원하는속성을모두만족하여야복호화가가능한특징이있다. 본논문에서는속성기반암호화방식의속성값을패스워드로보아, 공개키 / 개인키를별도로생성하지않고공개키기반암호화가가능한다중서버 PAKE 프로토콜을제안한다. 제안한프로토콜은서버당한번의메시지교환이필요하며사전 (dictionary) 공격에안전하다. 또한사전공격에대한위협모델을제시하고보안분석을통하여안전성을검증하였으며, 사용한암호알고리즘의수행시간측정을통해제안한프로토콜의실현가능성 (feasibility) 을검토한다. Key Words : Password Authenticated Key Exchange, Attribute-based Encryption, Dictionary Attack ABSTRACT Password authenticated key exchange (PAKE) is a protocol that a client stores its password to a server, authenticates itself using its password and shares a session key with the server. In multi-server PAKE, a client splits its password and stores them to several servers separately. Unless all the servers are compromised, client s password will not be disclosed in the multi-server setting. In attribute-based encryption (ABE), a sender encrypts a message M using a set of attributes and then a receiver decrypts it using the same set of attributes. In this paper, we introduce multi-server PAKE protocol that utilizes a set of attributes of ABE as a client s password. In the protocol, the client and servers do not need to create additional public/private key pairs because the password is used as a set of public keys. Also, the client and the servers exchange only one round-trip message per server. The protocol is secure against dictionary attacks. We prove our system is secure in a proposed threat model. Finally we show feasibility through evaluating the execution time of the protocol. 본논문은정부 ( 미래창조과학부 ) 의재원으로한국연구재단의지원을받아수행된연구결과물임을밝힙니다.(No.2013R1A2A2A ) First and Corresponding Author : Seoul National University Department of Computer Science and Engineering, mkpark@mmlab. snu.ac.kr, 학생회원 * Seoul National University Department of Computer Science and Engineering, escho@mmlab.snu.ac.kr, tkkwon@snu.ac.kr 논문번호 :KICS , Received June 1, 2015; Revised August 11, 2015; Accepted August 11,

2 Ⅰ. 서론개체가스스로를인증하려고할때 ( 예를들어, 사람들이인터넷으로웹서버에로그인을하거나, 스마트폰에서무선랜에접속하려고할때, 허가된단말인지인증하는등 ) 사용되는것은주로패스워드이다. 패스워드기반인증키교환프로토콜 (Password Authenticated Key Exchange: PAKE) 은서버에저장되어있는패스워드를이용해서서버와클라이언트가서로를인증하고공유키를교환하는알고리즘이다. 패스워드는인증서나, 생체정보등다른인증방식에비해상대적으로기억하기쉽고, 사용하기도쉽다는장점때문에많이사용되고있다. 그러나이러한패스워드의장점이단점으로도작용할수있다. 보안에취약하고낮은엔트로피를가진패스워드는공격자가추측하기쉽고, 또한보안에취약한서버는공격자의공격에인증정보를노출시킬수도있다. 같은패스워드를여러사이트에서사용하기때문에한서버의패스워드가유출이되면다른사이트의패스워드도더이상안전하지않다 [1]. PAKE는서버의수에따라 2가지로분류할수있다. 첫번째방식은패스워드를저장하는서버가 1개존재하는단일서버방식이다. 해당서버의패스워드나개인키가탈취되면더이상안전하지않다는단점이있다. 이를극복한방식이두번째방식인다중서버 PAKE이다. 다중서버 PAKE는클라이언트의패스워드를여러개의서버 (N개) 에저장한다. N개의서버중 N-1개의서버가손상되어도클라이언트의패스워드일부만유출이되기때문에상대적으로안전하다. 또한보안이뛰어난제 3의서버를패스워드저장서버로이용하면다른서버에서패스워드가탈취되어도보안이뛰어난서버의개인키가탈취될확률이낮다. 서버자체의안정성이외에도 PAKE 프로토콜이안전해야한다. PAKE는사전공격 (dictionary attack) 에취약하기때문이다. 사전공격은추측공격의일종으로, 성공할가능성이있는패스워드들을추측해서 ( 사전을만들어서 ) 패스워드를알아내는방법이다. 사전공격은크게온라인사전공격과오프라인사전공격으로나뉜다 [2]. 이공격은프로토콜에따라서패스워드가쉽게노출될수도, 노출되지않을수도있기때문에 PAKE 프로토콜은이에안전해야한다. 패스워드를안전하게전달하기위해주로비대칭키기반암호화를한다. 비대칭키기반암호화방식은키쌍이필요하다. 서버와패스워드간에미리키쌍을 나누거나키쌍을생성해내는방법을나누는등의양쪽의합의가있어야한다. 또한다중서버를사용하는경우에는클라이언트와각서버가다른키쌍을공유해야한다. 본논문에서는패스워드를비대칭키로사용하는다중서버 PAKE를제안하여별도의키 ( 비대칭키 ) 를생성하지않도록한다. 이를가능하게하는것은속성기반암호화방식 (Attribute-based encryption: ABE) 이다. 속성기반암호화방식은 Goyal 등 [3] 에의해고안된암호화방식이다. 메시지를암호화하는주체는이를복호화는주체의속성을이용해암호화한다. 암호화에사용된속성을모두가지고있어야암호문을복호화할수있다. 제안하는프로토콜에서는패스워드를속성으로보았다. 패스워드를가진서버와클라이언트만복호화가가능하다. 속성 ( 패스워드 ) 을가지고공개키기반암호화를하기때문에별도의키쌍이필요하지않다. 암호화는속성과난수를이용해암호화마다새로운키쌍을만든다. ABE의자세한설명은 2장에서설명하겠다. 남은장은다음과같이구성되어있다. 2장에서는관련연구와 ABE에대한자세한방법을설명하고, 논문에서제안하는프로토콜의기본이되는모델에대해정의한다. 3장에서는제안하는 PAKE 프로토콜을자세하게설명한다. 4장에서는제안하는 PAKE 프로토콜의안전성을점검한다. 5장에서는성능을간단히보이고, 6장에서결론을맺는다. Ⅱ. Background & Definition 2.1 PAKE Algorithms Bellovin과 Merritt [4] 는 RSA나 El gamal를이용한사전공격에안전한 PAKE 알고리즘을발표하였다. 그이후로인증서를동시에사용하는 PKI 기반 PAKE [5], ID를동시에사용하는 ID기반 PAKE [6], Smart card를이용한방식등이발표되었다 [7]. 비교적최근에는생체정보를이용한방식등다양한인증정보와패스워드를함께사용하는프로토콜에대한연구가있다 [8,9]. 다중서버방식 PAKE도다양한프로토콜이고안되었다. 다중서버방식도세부적으로 2개의서버를사용한방식과 3개이상의서버를사용한방식으로나눌수있다. 2개의서버에패스워드를나눠저장하고두서버모두패스워드인증과정에참여하는 PAKE가발표되었다 [2,10]. 패스워드를 3개이상서버에저장하는방식으로는, N개의서버에패스워드를 1598

3 논문 / 속성기반암호화방식을이용한다중서버패스워드인증키교환 저장하여그중 K개의서버와모두인증을성공해야사용자인증이가능한 threshold PAKE [11] 가있다. 그러나위의다중서버 PAKE 프로토콜들은메시지교환이많이발생하거나, 제한된수의서버에만적용할수있다는한계가있다. 2.2 Attribute-based Encryption 속성기반암호화방식 (ABE) [3] 은신원기반암호화방식 (ID-based encryption: IBE) [12] 으로부터파생되었다. IBE는전자우편주소와같은고유한 ID를공개키로사용하는공개키암호시스템으로 Shamir에의해처음제안되었다. 그후에일반적인 IBE에서진화한 Fuzzy Identity-Based Encryption(FIBE) 이 Sahai 와 Waters [13] 에의해제안되었다. 이방식에서는 identity를여러가지속성의집합으로정의한다. 암호화할때사용된공개키의집합과복호화하려는개인키의집합의 distance metric의차이가어느 threshold 보다작으면복호화가가능하다. 이에서한층더진화한것이 ABE이다. ABE는접근제어를위해 Goyal 등 [3] 에의해고안되었다. 사용자의데이터는서버에암호화되어저장된다. 따라서서버가공격당해도암호화된데이터는복호화되기쉽지않기때문에기밀성이유지된다. 데이터를암호화해서저장하면, 데이터를소비하고자하는소비자는이를복호화하기위한키가필요하다. 소비자에따라데이터마다다른접근제어가필요한상황에서는다른키쌍을생성해야하고, 이러한키쌍을효율적으로생성 / 관리하는것은중요한일이다. 사용자속성에따른유연성있는접근제어를 ABE에서가능하게했다. 예를들어인사과, 정보과등부서에따라서데이터접근권한이달라질수있고, 사장이나부장등직책이나맡은역할에따라서도접근권한이달라질수있다. ABE에서는인사과이면서동시에부장이거나혹은사장에게만접근권한이있도록데이터를암호화할수도있고, 정보과이면서동시에부장에게만접근권한이있도록데이터를암호화할수도있다. 첫번째경우에는인사과키와부장키를동시에가진소비자혹은사장키를가진소비자만복호화가가능하고, 두번째경우에는정보과키와부장키를가진소비자만이복호화가가능하다. Goyal 등이고안한 ABE는쌍 (Pairing) 기반암호화방식이다. 소수위수 (prime order) 가 인 2개의순환군 (cycle group), 에대해 bilinear map 는다음과같은특별한성질을갖는다는점을이용한다. 1) (1) 2) (2) 3) 를효과적으로계산하는알고리즘이존재한다. 위의특징을이용하여, ABE 알고리즘을설명할수있다. ABE는 Setup, Encryption, Key Generation, Decryption 4단계로구성된다. 간단히각단계를설명하면다음과같다. Setup 기본 public parameter를초기화한다. 위의예에서, 정보부, 인사부와같은부서나직책같은속성을나타내는속성집합 를규정하고, 각 의원소에대한속성특징값 와 값을랜덤으로선택한다. public parameter는 이다. master key( 비밀값 ) 는 이다. Encryption (,, PK) 메시지 을속성 로암호화하기위해랜덤인수 를선택한다. 이때, 암호문 E는다음과같다. (3) Key generation 암호문을복호화하기위해, 풀어낼키를생성한다. 암호문 로부터받은 를이용해개인키를만든다. (4) Decryption(E, D) Key generation 과정에서생성한키를이용하여암호문 의 을복호화한다. (5) 2.3 Model & Definition 이절에서는보안모델에대해설명하고앞으로사용할용어에대해정의할것이다. 사용할모델은다른많은 PAKE 알고리즘 [2,10,11] 에서사용한모델을기반으로하였다. 제안하는 PAKE 프로토콜은클라이언트와 N개의 1599

4 서버, 2종류의사용자가참여한다. 확률적다항시간공격자 (Probabilistic Polynomial Time: PPT) 는 A로표기한다. 사용자 U는공격자 A를제외한클라이언트 C와서버 를총칭하고, U로표기한다. 사용자가프로토콜에서대화하는상대방을파트너라고한다. 서버는 N개가있다고가정하며 으로표현한다. N개의서버중적어도 1개는안전하다고가정한다. 하나의클라이언트의패스워드 는나눠져서 N개의서버에저장된다. 각서버에저장된패스워드는 { } 으로표현되고 의특징을만족한다. 초기패스워드의분배는공격자의간섭없이안전하게이루어진다고가정한다. 각사용자는프로토콜을다른사용자와여러번수행할수있다. 매번수행할때마다, 사용자의새로운인스턴스가프로토콜에참여하며, 사용자 U의인스턴스 i를 라고표기한다. - 는다양한변수 (variables) 를가지고있다. 파트너의아이디를나타는 pid, 세션아이디를나타내는 sid 그리고사용자 U가파트너와공유한세션키인 sk가있다. 파트너의아이디란 가프로토콜을통해통신하고있는사용자의아이디를뜻한다. 세션아이디는프로토콜의수행을구별해주는아이디이다. 세션키는프로토콜이종료된후파트너와맺게되는키를뜻하는데, 클라이언트 C에게는 ( ) 의전체또는일부를 뜻하고, 서버 에게는 를뜻한다. - acc, term는각각 가성공적으로프로토콜이다수행된후세션키가의도한세션키인지, 프로토콜이전부수행되었는지를나타내는변수이다. 따라서클라이언트와서버 ( ) 가각각같은세션키를공유한다는것을의미한다. 공격자 A는프로토콜에서사용되는모든환경을제어할수있다고가정한다. 공격자는오라클모델에접근하여, 프로토콜환경을제어한다. 여기서사용되는오라클모델의타입은다음과같이정의한다. - send(u, i, M): 사용자 U의인스턴스 i인 에게메시지 M을전송한다. 는상태를업데이트하고, 그에대한메시지를출력하는데, 이상태나메시지는 A가알수있다. - execute(c, i, { }): 클라이언트 C의인스턴스 i는서버 의인스턴스 ( ) 와전체프로토콜을수행한다. 수행시에오고가는메시지나상태를공격자A 는모두볼수있다. 또한개인키가유출된서버가있다면, 유출된서버의내부상태도 A에게주어진다. 이오라클은메시지를엿듣는공격을하는공격자를표현한다. - corrupt(u): 사용자 U의개인키가유출될상황을모델링한다. 이오라클은일부서버나클라이언트가해킹당한상황을나타낸다. - reveal(u, U', i): 현재세션키 을 A에게알린다. 이오라클은세션키가유출이된상황을나타낸다. - test(u, U', i): 이오라클은실제상황을나타내는모델이아니라, 보안성을검증하기위해사용한다. 가랜덤하게비트 b를생성한다. 만약 b=1이면 세션키 를 A에게알려준다. b=1이아니면, 랜덤한세션키를 A에게알려준다. 이오라클은프로토콜수행도중아무때나실행할수있고, 단한번만가능하다. U와 U' 의개인키가유출되지않았고, 공격자가 reveal(u, U', i) 과 reveal(u', U, j) 를질의하지않았을때세션키는신선하다 (fresh) 고한다. 앞서설명한정의를바탕으로, 보안성을정의할것 이다. 공격자 A가 =TRUE이고, 신선한 에 Test(U, U', i) 질의한아웃풋 b와공격자 A가선택한 b' 의비트가같으면, 즉 b=b' 인경우 공격자 A의공격은성공했다 고하자. 이러한상황을 Suc이라고표기한다. 공격자 A가프로토콜 P에서얻을수있는이 득을 라고표기하고 라고정의한다. Ⅲ. Proposed protocol 이번장에서는제안하는 PAKE 프로토콜에대해설명한다. 이번장에서언급하는암호화 / 복호화는 ABE를이용한암호화 / 복호화다. 프로토콜이시작되기이전에패스워드와 ABE의 public parameter를분배하는과정이필요하다. 클라이언트 C는패스워드 를생성한다. 의조건에맞게서버 1600

5 논문 / 속성기반암호화방식을이용한다중서버패스워드인증키교환 버에게인증한다. 클라이언트는 값과세션키생성을위한 Diffie-Hellman 값 ( ) 을암호화한다 ( 그림 1의 1~3번 ). ABE 암호화과정에서비밀값 를매번생성하기때문에다른서버의메시지나 을클라이언트이외에는알아낼수없고, 를일회용비밀번호처럼사용하여서버에게보내기때문에 가노출되지않는다. 서버가메시지를복호화하려면 값을알아야한다. 이값은 를이용해계산하므로, 값이노출되지않고 를얻을수있다 ( 그림 1의 5번 ). 클라이언트가생성한 의값과복호화로얻은메시지 의해시값이일치하게되 그림 1. 프로토콜의수행과정 Fig. 1. An execution of the protocol 에 를저장한다. 는안전한경로로분배한다고가정한다. 각각의서버에서는다음과같은초기과정을수행한다. 서버 는비밀 값 를생성한다. 이값을이용해 를생성하며, 이값은 public parameter로공개하는정보가된다. 클라이언트 C는 인서버 의공 개값 과 값을이용해메시지를암호화할수있고, 를알고있는 는복호화가가능하다. 각서버는 와랜덤한수 x를이용해메시지를암호화한다. 클라이언트는 를알고있으므로 를알수있다. 또한, 클라이언트가 x값을알고있다면 값을알수있다. 따라서 각서버가생성한암호문의 를이용해 를구할수있게된다. 이러한원리를이용해인증프로토콜이수행된다. 그림 1에프로토콜의수행과정을명시하였다. H는충돌할확률이무시할정도로작은해시함수를나타내고 R은랜덤한수를생성하는생성기를나타낸다. 은랜덤한수 s를생성함을의미한다. ABD는복호화과정인 Attribute-based Decryption을의미한다. 클라이언트는 ABE 암호화를통해자기자신을서 면정상적으로복호화가된것으로간주하고, 클라이언트인증이끝난다. 클라이언트인증이끝나면, 서버는자신을클라이언트에게인증한다. 클라이언트는메시지 에모든서버가공통으로사용할비밀값 x와세션키를만들 어내는데사용하는 값을임의로생성해서전송했다. 비밀값 x를이용해서버 는자신의패스워드 를가지고암호화를하여클라이언트에게전송한다 ( 그림 1의 7~13번 ). 클라이언트는서버로부터 를받게된다. 이렇게받은값을모두 곱하게되면 를얻게된다. 이를정확하게도출해내면클라이언트는서버가정확한패스워드를가지고있음을동시에인증할수있다. 양방향인증이성공하면클라이언트와각서버는서로공통 적인세션키 를갖게된다. Ⅳ. Security analysis 프로토콜이사전공격에안전하다는것을다음과같이정의한다. [2,10,11] Definition 1. 사전의크기를 Dic 이라고하자. ( 가생성될수있는공간이며 의크기와도같다.) 는공격자가온라인사전공격을시도한횟수이고, 는무시할정도로작은수이다. PPT 공격자 A가최대 번의온라인사전공격을한다고할때, 프로토콜 P에대해 (6) 1601

6 라면 P는사전공격에안전하다. Definition 1에서 가충분히작고, Dic이충분히 크다면 는무시할정도로작다. 따라서온라인사전공격에안전하다고볼수있다. 2장에서설명한모델을바탕으로, 제안하는프로토콜의 Definition 1 에따라사전공격에안전함을검증할것이다. 프로토콜을수행하는환경을시뮬레이터 S라고하자. 서버는최대 N-1개의서버 ( ) 에 corrupt( ) 를질의하였다고가정한다. 제안한프로토콜을 P0라고하고, 시뮬레이터에서 P0의몇가지변 화상황에대해공격자의이익 를측정한다. 이를바탕으로최종으로제안하는프로토콜이안전함을보인다. 프로토콜 P1: 시뮬레이터는 P0에서두가지상황을제외하고똑같이동작한다. (1) 메시지 (, ) 는오라클로부터중복생성될수있다. 중복생성되면프토로콜을중단한다. (2) 해시함수 H에서충돌이발생하면, 프로토콜을중단한다. 첫번째상황은무시할수있을정도의확률로발생한다. 두번째상황은전제조건에서해시함수에서는충돌이무시할정도로작은확률로일어난다고가정한다. 따라서 은무시할정도로작다. 프로토콜 P2: 시뮬레이터는 P1과한가지상황을제외하고똑같이동작한다. 공격자가 execute(c, i, { }) 를질의할때, corrupt( ) 가질의되지않은 이생성하는평문 는임의의수가된다. 메시지 는매번임의로클라이언트로부터생성되고, 서버별로다른값을갖게된다. 따라서프로토콜 P1과 P2의차이점은공격자 A가 ABE를키없이복호화할수있느냐에관련된문제이다. ABE에서평문 를추측할수없으므로따라서 는무시할정도로작다. 프로토콜 P3: 시뮬레이터는 P1과한가지상황을제외하고똑같이동작한다. 공격자가 execute(c, i, { }) 를질의할때, corrupt( ) 가질의된적이없는서버 에서생성하는 는임의의수가된다. 세션키는 Diffie-Hellman 알고리즘에의해생성된다. 따라서, 프로토콜 P2와의차이점은 Diffie-Hellman 문제를풀수있는지에관련된문제이다. 이는어렵다 (hard) 고알려져있으므로, 는무시할정도로작다. 프로토콜 P4: 시뮬레이터가 send(, j, ) 와 send(c,i, ) 가질의되었을때의응답을다음과같이바꾼다. 가공격자에의해생성된경우 ( 오라클에의해생성되지않은경우 ), send(, j, ) 쿼리는 =TRUE일때만, 가유효하다. 도마찬가지로공격자에의해생성된경우, send(c, i, ) 는 =TRUE일때만 가유효하다. ( 혹은 ) 가공격자에의해생성되 었고, ( 혹은 ) 가 TRUE라면, = ( = ) 라고하자. P4에서는공격자의성공 (Suc) 을다르게정의할것이다. 만약공격자 A가 send를신 선한서버인스턴스 에게질의했을때, = 이거나, 공격자 A가 send(,j, ) 를신선한클 라이언트인스턴스 에게질의했을때, = 이면 adversary는성공했다고간주한다. 위에서나열한상황이아닌경우의 Suc의정의는 P3와같다. 따라서 가된다. 프로토콜 P5: 시뮬레이터는두가지상황을제외하고똑같이동작한다. 공격자가 send(, j, ) 를질의할때, corrupt( ) 가질의된적이없는서버 에서생성하는평문 는임의의수가된다. 또한 에서발생하는 send(c, i, ) 의평문 또한임의의수가된다. 메시지 는매번임의로클라이언트로부터생성되고, 서버별로다른값을갖게된다. 또한 도 를연산한결과물이기때문에매프로토콜수행시마다달라진다. P2와마찬가지로 ABE를복호화할수있는가능성에관한문제로, 는무시할정도로작다. 프로토콜 P5에서, 와 는 와독립적이다. 따라서오프라인사전공격은성공하지못한다. 매번다른 s와 x를생성할뿐아니라서버 N 개에나누어져있기때문에 가그대로사용되는경우도없다. 온라인공격을하는공격자 A는프로토 1602

7 논문 / 속성기반암호화방식을이용한다중서버패스워드인증키교환 콜 P5에서 3가지경우에성공 (Suc) 할수있다. (1) 공격자가유효한 를생성하여 send(, j, ) 를신선한서버 에게질의하는경우이다. ( 즉, = ) 이경우를 Suc1이라고표기한다. (2) 공격자가유효한 를생성하여 send(c, i, ) 를신선한 C 에게질의하는경우이다.( 즉, = ) 이경우를 Suc2라고표기한다 (3) (1) 의경우도아니고, (2) 의경우도아닐때, Ci나 에게 Test를질의해서 이되는경우이다. 과 를측정하기위해, 공격자 A가 corrupt( ) 하였다고가정하고, ( ) 4가지경우로나눈다. 아래 4가지경우에 corrupt가질의되지않은서버를 라하자. Case 1. 공격자 A는 <C, Server k,, > 를바꾼다. 하지만 ABE는선택된암호문공격 (Chosen Ciphertext Attack: CCA) 에안전하다. 따라서 은무시할정도로작다. Case 2. 공격자 A는 '<C, Server k,, > 를새로생성한다. 공격자가생각하는암호 를이용해, 를암호화하고,, 를생성한다. 이경우에 은 /Dic+이다. Case 3. 공격자 A는 <C, Server k,, > 를바꾼다. 이경우도 Case1 과마찬가지로 은무시할정도로작다. Case 4. 공격자 A는 '<C, Server k,, > 를새로생성한다. 공격자가생각하는암호 를이용해 를암호화하고,, 를생성한다. 이경우에 는 /Dic+다. 위의 4가지를고려해보았을때, = /Dic+ 가된다. (7) Ⅴ. 실험이번장에서는제안한프로토콜에서사용하는 ABE의수행시간과그프로토콜의수행시간을측정한결과를분석하였다. JPBC library 1) 를이용하여 Java로알고리즘을구현하였다. 실험을수행한환경은다음과같다. Intel i CPU, 8GB RAM PC 1대에서측정하였다. 같은보안레벨에서측정하기위해 ABE는 160bit, RSA는 1024bit의키길이를이용하였다 [14]. 먼저 ABE와 RSA의암호화, 복호화속도를 1000 회측정한평균을 Table 1에나타내었다. 암호화, 복호화에사용한메시지길이는동일하게 20byte로하였다. Table 1에서볼수있듯이, ABE가 RSA에비해암호화에는약 150배, 복호화에는약 7배가느리다. ABE는 bilinear pairing연산을사용하기때문에다른공개키기반암호화방식인 RSA나 ElGamal에비해속도가느리다. 하지만, pairing 연산이나 ABE의성능을향상시키려는연구가지속적으로있고 [15, 16], 이에따라 ABE 알고리즘의성능향상을기대할수있다. 두번째로측정한것은제안한프로토콜의평균수행시간이다. 제안한알고리즘은서버의개수가증가해도, 증가하는서버의개수와 1번의메시지교환만하기때문에성능의차이가크지않다. 이를보이기위해, 서버의수를 1개부터 10개까지변화시키면서프로토콜수행시간을 5번씩측정하여평균을구하였다. 측정결과를그림 2에서나타내었다. 서버와클라이언트에서수행하는수행속도는선형적인양상을보인다. 서버를여러개사용하는다른프로토콜의경우 [11] 서버의수 N에따라메시지교환이 배일어나게된다. 이에비해서버의개수가많은상황이라면더나은성능을기대할수있다. 또한서버와클라이언트가같은머신이아닌개별머신에서수행한결과를측정한다면, 성능향상이예상된다. 또한, 프로토콜에서서버와클라이언트당 ABE 알고리즘을 2번씩수행하는데, 그림 2의결과에따르면대부분의프로토콜수행시간이암호화, 복호화에소요된다고예상할 가되고, 표 1. ABE, RSA 수행시간평균 Table 1. The average time for running RSA and ABE 가된다. 따라서사전공격에안전하다. (8) Encryption Decryption ABE 35,076 us 7,126 us RSA 203 us 1,035 us 1) JPBC library ( 1603

8 그림 2. 서버의수에따른프로토콜수행시간 Fig. 2. Comparison of the protocol execution time 수있다. 따라서 ABE의알고리즘성능이향상되면, 제안하는프로토콜의성능이크게개선될것으로보인다. Ⅵ. 결론 본논문에서는속성기반암호화방식을이용하여클라이언트의패스워드로부터각서버의개인키를생성하여사용할수있는다중서버 PAKE 프로토콜을제안하였다. 기존 PAKE 프로토콜은공개키기반암호화방식을사용하기위해공개키, 개인키쌍을패스워드와별도로생성및관리해야하고, 다수의메시지교환이필요한부담이있다. 더욱이기존다중서버 PAKE 프로토콜은메시지교환이기존 PAKE 프로토콜보다더많이필요하다. 제안하는프로토콜은이러한기존프로토콜의단점을완화하여별도의공개키, 개인키쌍의관리부담을해소하고, 서버당 1회의메시지교환으로인증과키교환이가능하다. 또한서버의개수에상관없이적용가능하며, 서버의개수가 N 개라고할때 N-1개의서버가손상되어도사전공격에안전함을보였다. References [1] J.-C. Park, A scheme for secure storage and retrieval of (ID, password) pairs using smart cards as secure and portable storages, J. KICS, vol. 39B, no. 06, pp , Jun [2] X. Yi, et al., ID-Based two-server passwordauthenticated key exchange, Springer: Computer Security -ESORICS 2014, vol. 8713, pp , Sept [3] V. Goyal, et al., Attribute-based encryption for fine-grained access control of encrypted data, in Proc. 13th ACM Conf. Comput. Commun. Security(CCS '06), pp , VA, USA, Oct [4] S. M. Bellovin and M. Merritt, Encrypted key exchange: Password-based protocol secure against dictionary attack, IEEE Symp. Research in Security and Privacy, pp , Oakland, CA, May [5] S. Halevi and H. Krawczyk, Public-key cryptography and password protocols, ACM Trans. Inf. Syst. Security, vol. 2, no. 3, pp , [6] X. Yi, et al., Identity-based passwordauthenticated key exchange for client/server model, SECRYPT 2012, pp , Rome, Italy, Jul [7] J. Xu, et al., An improved smart card based password authentication scheme with provable security, Computer Standards & Interfaces, vol. 31, no. 4, pp , Jun [8] B. Cho and J. Park, Technology review on multimodal biometric authentication, J. KICS, vol. 40, no. 1, Jan [9] J. Park, et al., QR-code based mutual authentication system for web service, J. KICS, vol. 39B, no. 4, pp , Apr [10] J. Katz, et al., Two-server password-only authenticated key exchange, ACNS, vol of LNCS, pp. 1-16, NY, USA, Jun [11] P. MacKenzie, et al., Threshold passwordauthenticated key exchange, Crypto 2002, pp , Califoria, USA, Aug [12] A. Shamir, Identity based cryptosystems and signature schemes in advances in cryptology, CRYPTO 84, vol. 196 of LNCS, pp , [13] A. Sahai, et al., Fuzzy identity based encryption in advances in cryptology, Eurocrypt, vol of LNCS, pp , [14] E. Barker, et al., NIST Special Publication Part3 Rev. 1: Recommendation for Key 1604

9 논문 / 속성기반암호화방식을이용한다중서버패스워드인증키교환 Management - Part1: General (Revision3), (20 12), Retrived May 31, 2015, from bs.nist.gov/nistpubs/specialpublications/nist.s P Pt3r1.pdf [15] S. Kwon, Efficient tate pairing computation for elliptic curves over binary fields, ACISP, vol of LNCS, pp , Barisbane, Australia, Jul [16] K. Javeed, et al., Efficient montgomery multiplier for pairing and elliptic curve based cryptography, 9th Int. Commun. Syst., Netw. & Digital Signal Process. (CSNDSP), pp , Manchester, Jul 박민경 (Minkyung Park) 2014년 2월 : 한국항공대학교컴퓨터공학학사 2014년 3월 ~ 현재 : 서울대학교컴퓨터공학석박사통합과정 < 관심분야 > 인터넷보안, 인증, 프라이버시 조은상 (Eunsang Cho) 2008년 2월 : 서울대학교컴퓨터공학학사 2008년 3월 ~ 현재 : 서울대학교컴퓨터공학석박사통합과정 < 관심분야 > 네트워크구조, 네트워크보안권태경 (Ted Taekyoung Kwon) 1993년 : 서울대학교컴퓨터공학학사 1995년 : 서울대학교컴퓨터공학석사 2000년 : 서울대학교컴퓨터공학박사 2004년 ~ 현재 : 서울대학교컴퓨터공학부교수 < 관심분야 > 미래인터넷, IoT, Web/SNS Analysis, 인터넷보안, 무선네트워크 1605