(c) Byoungcheon Lee, Joongbu Univ. 암호프로토콜 중부대학교 정보보호학과 이병천 교수 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 차례 은닉서명 키 분배 비밀 분산 인증 Schnorr의 개인식별 방식 Schnorr 서명 - 개인식별의 디지털 서명 전환 영지식 증명 (c) Byoungcheon Lee, Joongbu Univ.

은닉서명 (Blind Signature) 서명자가 서명문 확인 불가 은닉서명 응용 전자화폐에 이용 RSA 방식의 은닉서명 S  M X M : 서명문 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 은닉 서명 (계속) RSA 방식 은닉서명 제공자 A 공개 정보 n, e 서명자 B r R Zn 서명문 M K1  reM mod n  Md mod n n = p  q gcd (e,  (n)) = 1 e  d  1 mod  (n) K2  K1d mod n  rMd mod n K1 K2 mod n (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 은닉 서명 (계속) 은닉서명 구성 예 제공자 A 공개 정보 n= 55, e = 7 서명자 B r R Zn r = 6 K1  reM mod n  67  5  40 mod 55   15 mod 55 n = p  q = 11  5 = 55  (n) =  (55) = 40 gcd (e,  (55)) = 1 e  d  1 mod  (n) d = 23 K2  K1d mod n  4023  35 mod 55 K1 = 40  Md mod 55 K2 = 35 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 키 분배 (계속) Diffie-Hellman의 키 분배 (인증키 이용) y  gX mod p 가입자 A 공개 정보 p, g, yA, yB 가입자 B yA  gXA mod p KAB  yBXA mod p  gXBXA mod p yB  gXB mod p KAB  yAXB mod p  gXAXB mod p (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 키 분배 (계속) Diffie-Hellman의 키 분배 개선 (임시키 이용) 가입자 A 공개 정보 p, g 가입자 B rA  R Zp yA  grA mod p KAB  yBrA mod p  grB rA mod p rB  R Zp yB  grB mod p KAB  yArB mod p  grA rB mod p yA yB (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 키 분배 (계속) ElGamal의 키 분배 가입자 A 공개 정보 p, g, yA, yB 가입자 B yA  gXA mod p rA  R Zp T  grA mod p KAB  yBrA mod p  grA XB mod p yB  gXB mod p KAB  T XB mod p T (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 키 분배 (계속) MTI (Matsumoto, Takashima, Imai) 키 분배 가입자 A 공개 정보 p, g, yA, yB 가입자 B yA  g XA mod p rA  R Zp TA  g rA mod p KAB  TB XA yB rA mod p  (g rB)XA (g XB)rA mod p  g rB XA + rA XB mod p yB  g XB mod p rB  R Zp TB  g rB mod p KAB  TA XB yA rB mod p  (g rA)XB (g XA)rB mod p  g rA XB + rB XA mod p TA TB (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 비밀 분산 비밀분산의 필요성 비밀 정보의 분할 보관 키 복구 Shamir의 비밀분산 기법 Lagrange Interpolating Polynomial Scheme (t, n) 비밀 분산 n : share t 개 이상의 share가 모이면 정보 복원 가능 t – 1차 다항식 이용 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 비밀 분산 (계속) Lagrange Interpolating Polynomial Scheme 예 p = 17, K = 11일 때 a = 7, b = 8로 (3, 5) 구성 F(x) = ax2 + bx + K mod p K1 = F(1) = 712 + 8 1 + 11  9 mod 17 K2 = F(2) = 722 + 8 2 + 11  4 mod 17 K3 = F(3) = 732 + 8 3 + 11  13 mod 17 K4 = F(4) = 742 + 8 4 + 11  2 mod 17 K5 = F(5) = 752 + 8 5 + 11  5 mod 17 K1, K2, K3, K4, K5 : shadow (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 비밀 분산 (계속) Lagrange Interpolating Polynomial Scheme 예 (계속) K2, K3, K4가 모이면 K = 11 복원 가능 a 22 + b 2 + K  4 mod 17 a 32 + b 3 + K  13 mod 17 a 42 + b 4 + K  2 mod 17 K 계산 가능 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 비밀 분산 (계속) 비밀키 K의 복구 방법 예: 인 경우 : 모여진 비밀값들의 집합 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 검증 가능한 비밀분산 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 비밀 분산 (계속) RSA 암호화와 비밀 분산 n = p · q p, q : 소수  (n) = (p – 1) (q – 1) gcd (Ke,  (n)) = 1 Ke  Kd  1 mod  (n) (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 비밀 분산 (계속) RSA 암호화와 비밀 분산 암호화 C  M Ke mod n , M : 평문 Ke = Ke1 + Ke2 +  +Ken C  M Ke1  M Ke2    M Ken mod n (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 비밀 분산 (계속) RSA 암호화와 비밀 분산 복호화 M  CKd mod n Kd = Kd1 + Kd2 +  +Kdn M  C Kd1  C Kd2    C Kdn mod n (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 인터넷을 통한 동전던지기 게임 인터넷을 통한 동전 던지기 문제 상대방을 신뢰할 수 없음 (상대방 인증) 사용자 인증 상대방의 동전 던지기 결과를 확인할 수 없음 해결 불가능하게 보임 정보보호 기술을 사용하여 해결함 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 인터넷을 통한 동전던지기 게임 Bob Alice 전산망 1. Alice는 동전 던지기에 사용할 일방향 해쉬함수 선정 4. Alice는 x가 짝수(앞면)인지 홀수(뒷면)인지 추측하여 Bob에게 통보 6. Alice는 y=f(x) 계산하여 확인 f(x) 2. Bob은 랜덤한 수 x 를 선택하여 y=f(x) 계산 3. Bob은 y를 Alice에게 전송 5. Bob은 x를 Alice에게 y HEAD = x는 짝수 TAIL = x는 홀수 x (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 인증 (Authentication) Entity Authentication (개체인증) 한 개체가 분명한 증명을 제시함으로써 다른 개체가 그 신분을 확신하도록 하는 과정 Identification(신분확인, 개인식별), Entity Verification (개체확인)과 같은 의미로 사용 Message Authentication (메시지인증) 메시지가 인증된 개체에 의해 생성되었다는 것을 보장 Digital Signature(디지털 서명)이나 MAC(메시지 인증 코드)에 의해 제공 (c) Byoungcheon Lee, Joongbu Univ.

개체인증 (Entity Authentication) 신분확인의 목적은 통신 주체에 대한 신분보장 제공 신분확인을 위하여 신분위장 및 재전송 공격들의 위협으로부터 보호 신분위장 : 어떤 개체가 다른 개체인 것처럼 가장하는 것 재전송 공격 : 전달되는 메시지를 불법적인 실체가 수정 등을 통해 나중에 다시 재연하는 것 신분확인 서비스는 다른 정보 보호 서비스들과 상호 작용하여 제공 액세스 제어, 데이터 무결성, 데이터 기밀성, 부인 방지, 감사 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 개체인증 방법 Something known 일반적인 패스워드, PIN Challenge-Response 프로토콜에서 사용하는 비밀키 Something possessed 신용카드, IC카드 시간 기반의 패스워드를 생성하는 생성기 Something inherent 신체 및 생체적인 특성을 이용하는 Biometrics 서명, 지문, 음성, 망막패턴, 키보드 입력 특성 등 대부분 비암호학적 특성을 가짐 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. Password 방식 특정 사용자에 해당하는 비밀 정보를 알고 있다는 사실을 검증자에게 증명함으로써 인증 Time-invariant password 사용 (Weak Authentication) - 모든 세션에 고정된 password 사용 - 공격에 취약 단 점 보완 방법 망각 다양한 공격 가능 - Replay attack - Exhaustive password search - Password guessing & Dictionary attack Password rule 사용 Salting password 사용 Passphrase 사용 Graphical password (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. Password 방식 (계속) 도청자 A의 password는 xxx이구나. Password table   IDA h(passwordA)   IDA h(passwordA) IDA, password password h(password) = ? YES h Accept NO Alice Reject 인증 서버 (c) Byoungcheon Lee, Joongbu Univ.

Challenge-Response 인증 방법 한 개체 A가 관련된 비밀에 대한 지식을 보임으로써 이를 알고 있는 다른 개체 B에게 신분을 증명 Challenge는 개체 B에 의해 랜덤하고 안전하게 선택되는 난수 Response는 A 자신이 아는 비밀 정보를 이용하여 Challenge를 적용시켜 계산한 결과 B는 수신한 정보(Response)를 A의 신분확인에 사용 비밀키, 공개키 암호와 영지식 개념을 사용 (c) Byoungcheon Lee, Joongbu Univ.

Time-synchronous authentication server 시간에 따라 변하는 패스워드 사용 토큰은 알고리즘, 시간, 이용자의 키에 기초하여 6자리 패스워드를 생성한다 1 Log-in:5555123456 이용자는 4자리 숫자 PIN과 6자리 패스워드로 로그 인을 한다 2 123456 Time-synchronous authentication server 서버가 6자리 숫자를 비교하여 일치하는 경우 이용자를 인증해 준다 5 5555123456 이용자의 PIN은 서버가 꺼낼 비밀키를 알려준다 3 이용자 데이터베이스 123456 서버가 현재 시간과 비밀키로 알고리즘을 수행하여 6자리 숫자를 생성한다 4 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. S/Key 일회용 패스워드 시스템 1. login ID 2. N,seed 4. XN client Hash function f() pass-phrase S Initial Setup 3. compute fN(S) = XN Host compute f(s), f(f(S)),...., X1,X2,X3, ...,XN store XN+1 5. compute f(XN) = XN+1 6. compare 7. store (c) Byoungcheon Lee, Joongbu Univ.

Challenge-Response 방식의 인증 1 Challenge-response authentication server 이용자는 인증 서버에게 PIN을 전달한다 2 User PIN 서버는 난수를 생성하여 그것을 Challenge로 반환한다 3 서버는 PIN을 이용하여 비밀키를 꺼내어 난수를 DES로 암호화한다 Challenge 1952736 Response 4083621 4083621 4083621 4 키 데이터베이스 이용자는 DES와 비밀키를 이용하여 난수를 암호화 하고 그것을 서버에게 Response로 반환한다 DES 5 서버는 암호화된 두 수를 비교하여 일치하는 경우 이용자를 인증한다 DES (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 개인식별 Schnorr의 개인식별 방식 사용자 A 공개 정보 p, g, q, yA 검증자 B r  Zq w  gr mod p R  r + XA E mod q C(A) 확인 E  R{0, 1, 2, , 2t–1} gR yA –E  w mod p 확인 C(A), w E R (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 개인식별 (계속) Schnorr의 개인식별 방식 Schnorr의 개인식별 검증 과정 gR yA –E mod p gr gXAE g – XA E mod p  gr mod p  w mod p (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 개인식별 (계속) 개인식별의 디지털 서명 전환 서명자 A 공개 정보 p, g, q, yA 검증자 B K  R Zq w  gK mod p E = h(w, M) R  K + XAE mod q gR yA–E  w mod p w, R, M (c) Byoungcheon Lee, Joongbu Univ.

영지식 증명 (Zero-knowledge proof) 내가 알고 있는 어떤 중요한 정보에 대하여 그 내용에 관한 것은 일체 알려 주지 않으면서 내가 그 정보를 알고 있음을 상대방에게 증명해 보이는 방법 (c) Byoungcheon Lee, Joongbu Univ.

영지식 증명 (Zero-knowledge proof) A B D C 1. V stands at A. 2. P walks to C or D. 3. V walks to B. 4. V asks P to come L or R. 5. P follows the request. 6. Repeat 1 ~ 5, n times. (c) Byoungcheon Lee, Joongbu Univ.

Zero-Knowledge Interactive Protocol의 예 설계 방법 : cut and choose + challenge-response protocol (challenge와 commitment에 난수 값을 사용) 공개정보 n, x 증명자 A (p, q) 검증자 B ci 1 if wi is QR 0 if wi is QNR bi {0, 1} (random) wi  zi2(mod n) if bi = 1  x•zi2(mod n) if bi = 0 (1≤i≤k, k = log n) If ci= bi (for all 1≤i≤k) Then, accept 증명자는 합성수 n의 소인수분해 p,q 를 알고 있다는 것을 검증자에게 증명 wi ci ZKIP의 예제 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 이산대수값을 알고 있다는 것을 증명 증명자 A는 다음의 이산대수값 x를 알고 있다는 것을 x를 노출시키지 않고 증명하고자 함 증명자 A 검증자 B Commitment Challenge Response (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ^ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 1 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 사례 암호시스템 파라메터 p=23, g=7, q=22 키생성 x=13, y=20 증명자는 x=13을 노출시키지 않고 이것을 알고있다는 것을 증명하려고 함 증명자 A 검증자 B Commitment Challenge Response (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 사례 암호시스템 파라메터 p=23, g=6, q=11 키생성 x=14, Y=9 증명자는 x=13을 노출시키지 않고 이것을 알고있다는 것을 증명하려고 함 증명자 A 검증자 B Commitment Challenge Response (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 두개의 이산대수값이 같다는 것을 증명 증명자 A는 다음 두개의 이산대수값이 같다는 것을 x를 노출시키지 않고 증명하고자 함 증명자 A 검증자 B Commitment Challenge Response (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 사례 증명자는 x=5를 알고 있으며 다음을 증명하고자 함 증명자 A 검증자 B Commitment Challenge Response (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 암호의 복호화 증명 사용자의 키 공개키 암호화 메시지 m에 대한 암호문은 (U,V) 복호화 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. ElGamal 암호의 복호화 증명 사용자는 자신의 비밀키 x를 노출시키지 않고 암호문 (U,V)로부터 복호화를 하여 정당한 메시지 m을 얻었다는 것을 증명하고자 함 다음 두개의 이산대수값이 같다는 것을 증명 (c) Byoungcheon Lee, Joongbu Univ.

(c) Byoungcheon Lee, Joongbu Univ. 인터넷 보안 프로토콜 OSI 7 구조 TCP/IP 구조 e-commerce protocols Application Applications Applications S/MIME, PGP S-HTTP Presentation SSL, TLS (Socket layer) Session Transport Transport Transport IPSEC, VPN Network Internet Internet Data link Network H/W link encryption Network Physical Internet (c) Byoungcheon Lee, Joongbu Univ.

SSL (Secure Socket Layer) 배경 : 웹 서버와 브라우저간의 안전한 통신을 위해 넷스케이프사 개발 (1993) 특징 응용계층과 TCP 계층을 연결하는 Socket layer에 적용 응용계층의 FTP, TELNET, HTTP 등의 프로토콜의 안전성 보장 현황 및 전망 현재 대부분의 전자 쇼핑몰들이 SSL 프로토콜을 지원하는 웹 서버를 구축 단순성 및 비용절감 측면을 고려해 볼 때 당분간 지속적으로 발전 예상 ※ 1996년 SSL 3.0이 발표된 후, 1998년에는 SSL 3.0이 TLS (Transport Layer Security) 1.0으로 개선된 후 IETF의 표준으로 추진중임 (c) Byoungcheon Lee, Joongbu Univ.

인터넷 보안 프로토콜 - 예 : SSL (계속) SSL 프로토콜의 구성 HTTP Telnet FTP 키분배 상호인증 SSL Handshake Protocol HTTP Telnet FTP • • • 무결성 비밀성 SSL Record Protocol TCP IP (c) Byoungcheon Lee, Joongbu Univ.

인터넷 보안 프로토콜 - 예 : SSL (계속) SSL Record Protocol MAC 어플리케이션 데이터 E-Commerce with Secure Socket Layer 레코드 프로토콜 데이터 E- Commerce with Secure 압축 메시지 인증 압축된 데이터 MAC 메시지 인증 코드(MAC) 암호화 암호화 데이터 + 인증 압축된 데이터 MAC TCP 패킷 암호화 데이터 + 인증 TCP 헤더 (c) Byoungcheon Lee, Joongbu Univ.

SSL Handshake Protocol : 상호인증 및 키 분배 암호세팅, 랜덤 데이터, 기타정보 서버인증 (인증서 이용) Premaster Secret 생성(현단계까지 사 용된 정보 이용) 정보를 이용하여 Master Secret 생성 Master Secret 정보 를 이용하여 세션키 생성 서버의 SSL 버전번호, 암호세팅, 랜덤 데이터, 기타 정보, 서버 인증서 클라이언트 인증 (인증서 이용) Premaster Secret을 복호화한 후, 이것을 이용하여 Master Secret 생성 Master Secret 정보 를 이용하여 세션키 생성 Premaster Secret 정보를 서버의 공개키로 암호화하여 전송, 클라이언트 인증서 이후 생성된 세션키를 이용한 암호통신 수행을 알림, Finished 메시지 전송 이후 생성된 세션키를 이용한 암호통신 수행을 알림, Finished 메시지 전송 SSL Handshake 프로토콜 종료 클라이언트 서버 (c) Byoungcheon Lee, Joongbu Univ.