Identity Based Cryptosystem 김진

암호 시스템 E D Key Key Kenc Kdec Cryptanalyst Adversary M K Insecure Channel Plaintext M Ciphertext C Plaintext M Key Kenc Key Kdec C = EK(M) DK(C) = M

비밀키 암호 vs 공개키 암호 비밀키 암호 공개키 암호 그런데 왜? 공개키 암호를 생각하게 되었나? Kenc = Kdec 연산 속도가 빠르다. 공개키 암호 Kenc ≠ Kdec (Kenc: 공개키, Kdec: 비밀키) 연산 속도가 느리다. 그런데 왜? 공개키 암호를 생각하게 되었나?

비밀키 암호의 문제점 키 분배 문제 공개키 암호는? n명 사용자 간에 필요한 비밀키의 개수: nC2 = n(n-1)/2 사용자가 늘어남에 따라 비밀키의 개수가 매우 많아진다. 이들은 안전하게 공유하는 것은 매우 어려운 일임 공개키 암호는? n명 사용자 간에 필요한 키의 개수: 2n 개 각 사용자가 간직해야하는 키는 오직 자신의 비밀키 뿐임

공개키 암호는 괜찮은가 그렇다면, 공개키 암호는 모든 문제를 해결해주는가? A의 공개키가 KA 라는 것을 누가 보장하나? CA (Certificate Authority) 인증서는? 사용자가 공개키를 바꾸고 싶으면? 키를 바꾸면? 어휴…

해법의 등장 1984년 Shamir가 ID기반 암호를 제안 사용자의 신원정보 (사용자를 확인할 수 있는 정보)를 공개키로 사용하자! 비밀키는 비밀키 관리 기관에서 만들어주자! 그런데, 구현이… 2001년 Boneh와 Franklin이 타원곡선 상의 겹선형함수를 이용하여, ID 기반 암호알고리즘을 제안함 17년 묵는 문제의 해결!

그림 설명 Key Server (KGC) master secret public params key request + authenticate bob@b.com alice@a.com bob@b.com public params

Fully off-line - no connection to server required 그림 설명 Key Server Fully off-line - no connection to server required bob@b.com charlie@c.com bob@b.com public params

그림 설명 Master Secret s = Key Server 1872361923616378 1872361923616378 Key Server Request for Private Key for Identity bob@b.com

궁금증! 타원곡선? 겹선형 함수? 덧셈을 연산으로 갖는 집합 덧셈은 기하학적으로 정의됨 타원곡선 상에서 암호를 설계하면, 그 연산의 어려움 때문에, 원소의 크기가 작아도 됨 (메모리효율성) 깊이 알기는 어려워… 겹선형 함수? e:AⅹB→C 인 함수로, e(aP,bQ) = e(P,Q)ab 를 만족하는 함수 실례 : Weil pairing, Tate pairing 등

Boneh-Franklin IBE Use the elliptic curve group we already defined Choose arbitrary P∈E/Fp of order q Pick random s∈Zq* and set Ppub = sP Choose hash functions H: Fp2 →{0,1}n G: {0,1}*→Fp Message space M = {0,1}n, ciphertext space is C = E/Fp×{0,1}n System parameters are <p, n, P, Ppub, G, H>. Master-key is s.

Boneh-Franklin IBE Extract (get private key from ID) Use MapToPoint to map ID to a point QID Private key corresponding to ID is dID = sQID Encrypt (encrypt M with ID) Choose random r ∈ Zq C = <rP, M⊕H(gIDr)> where gID = ê(QID,Ppub) ∈ Fp2

Boneh-Franklin IBE Decrypt (decrypt C = <U,V>) If U is not a point of order q, reject the ciphertext Otherwise, M = V ⊕ H(ê(dID, U)) Why M can be recovered? ê(dID, U) = ê(sQID, rP) = ê(QID, P)sr = ê(QID, Ppub)r = gIDr V ⊕ H(ê(dID, U)) = M⊕H(gIDr)⊕ H(gIDr) = M

ID 기반 암호는 만능? KGC는 모든 것을 알고 있다! 키복구 문제로의 귀결! 해법은 없는가? 빅브라더의 탄생! 키복구 문제로의 귀결! 해법은 없는가? Certificateless Public Key Cryptosystem KGC의 역할은?

Provable Security 김진

왜? 암호의 라이프 싸이클을 생각해보자. 라이프 싸이클을 생각했을 때, 무엇이 문제인가?

현대 암호의 설계 Substitution과 Permutation을 적절히 섞어서 설계하거나, 계산적으로 어려운 문제를 기반으로 설계 오늘의 이야기는 여기!

증명 방식 증명의 대상 명제 하지만, 이 방식의 증명은 쉽지 않다. 따라서 대우 명제를 통해서 증명한다. 기반 문제가 어렵다면, 알고리즘은 공격하기가 어렵다. 하지만, 이 방식의 증명은 쉽지 않다. 따라서 대우 명제를 통해서 증명한다.

우리의 암호시스템이 공격 가능하다면, 기반 문제를 푸는 알고리즘이 존재한다. 결국, 우리의 증명은 … 우리의 암호시스템이 공격 가능하다면, 기반 문제를 푸는 알고리즘이 존재한다.

어려운 문제? 어려운 문제 Computationally hard problem Hard to solve the problem in polynomial time Hard to find a polynomial time algorithm which solves the problem 다항식 시간 알고리즘 (PPT, Polynomial Time Algorithm) 알고리즘이 답을 출력하는데 소요되는 계산 복잡도가 다항식 상한에 들어있는 알고리즘

계산 복잡도는 … 주어진 입력에 대해 알고리즘이 출력을 내는 데에 소요되는 시간 또는 계산 단계를 점근적으로(asymptotically) 표시한 값으로 생각해도 무방

암호에서의 복잡도 암호에서의 입력값은? Knerkhoff 정리를 보았다시피, 키의 길이를 기반으로 생각하면 되겠다. 암호에서의 입력을 보통 안전성 파라메터 (security parameter)라고 부른다. 많은 논문에서 안전성 파라메터를 1k라고 한다. 뭘까? k비트

안전하다? 도대체 안전하다는 기준은 뭘까? 키가 노출되지 않으면, 안전한가? 아니다! 그렇다면 대체 …

안전성 모델 그래서 안전성 모델이 나왔다. 안전성 모델은 다음의 두 가지를 엮어서 말한다. 공격 목표 (security goal) 공격자의 능력 (adversarial model)

공격 목표의 종류 암호 알고리즘의 대표적 공격 목표는 다음의 두가지 구별불가능성 indistinguishability (IND) 비유연성 non-malleability (NM)

공격자 능력의 종류 선택 평문 공격 선택 암호문 공격 능동적 선택 암호문 공격 Chosen Plaintext Attack (CPA) 선택 암호문 공격 Chosen Ciphertext Attack (CCA1) 능동적 선택 암호문 공격 Adaptively Chosen Ciphertext Attack (CCA2, ACCA)

표현과 살짝 결론 안전성 모델은 앞의 두 개의 결합으로 표시한다. 가장 강한 안전성 모델은 무엇인가? 선택 암호문 공격에 대하여 구별불가능성을 제공한다면? IND-CCA 가장 강한 안전성 모델은 무엇인가? IND-CCA2와 NM-CCA2 이다. 이 둘의 정도가 같음이 증명되었다. (1996년, Bellare 등)

IND와 NM IND NM 두 개의 메시지 중 어떤 메시지에 대한 암호문인지 판단하는 것 특정 메시지에 대한 암호문을 안다고 하여, 어떤 다른 메시지의 암호문에 대한 정보를 얻을 수 없음

물론 공격 목표가 되는 암호문에 대한 평문을 질의할 수는 없다! CPA, CCA1, CCA2 CPA 공격자는 자신이 선택한 평문에 대한 암호문을 언제라도 받을 수 있는 능력을 가짐 CCA1 CPA 능력 뿐 아니라, 공격자는 선택함 암호문에 대한 평문의 정보까지 받을 수 있음 CCA2 CCA1의 능력을 포함하고, 공격자는 언제라도 자신이 선택한 평문의 정보를 받을 수 있음 물론 공격 목표가 되는 암호문에 대한 평문을 질의할 수는 없다!

오라클 주어진 질문에 대해서 항상 옳은 답만을 말해주는 가상 기계 암호화 오라클 encryption oracle 복호화 오라클 decryption oracle 서명 오라클 sign oracle 랜덤 오라클 random oracle

랜덤 오라클 이상적인 해쉬 함수 주어진 입력에 대해서 일정한 길이의 메시지를 랜덤하게 출력함 실재하지는 않음 주어진 입력에 대해서 일정한 길이의 메시지를 랜덤하게 출력함 동일한 입력에 대해서는 동일한 출력을 내보냄

공격 성공 IND에서 공격 성공이란 것은 정확히 무엇을 의미하나? 어떤 메시지의 암호문인지 맞추면 됨 메시지가 두 개 이므로 누구라도 0.5의 확률로 답을 출력할 수 있음 공격자가 정답을 출력할 어드밴티지가 무시할 수 없을 정도의 양일 때, 공격 성공이라고 말함

무시하다? 무시할 수 있는 negligible 무시할 수 없는 overwhelming 결과값이 어떤 다항식의 역수보다 작은 정도이면 무시할 수 없는 overwhelming 결과값이 특정 다항식의 역수보다는 큰 경우이면

성공 확률 주어진 입력에 대해서 올바른 출력을 낼 확률 표현은 보통 이렇게 …

어드밴티지 결국 성공확률과 비슷한데, 어드밴티지의 경우는 그 값이 0일 때, 전혀 어드밴티지가 없다고 볼 수 있으며, 그 값은 항상 0보다 큰 값임 IND에서의 어드밴티지는 …