암호모듈구현방침 김승주 skim@kisa.or.kr 1
발표순서 1. 암호모듈과암호알고리즘 2. NIST의 CMVP 3. 암호의안전성 2 一. COA / KPA / CPA/ CCA 二. Whole / Partial / Correlated Preimage 4. 암호칩의안전성 一. Timing / Fault / Power Attack
1. 암호모듈과암호알고리즘 응용시스템 (Application/System) 정보보호제품 (Security Product) 암호모듈 (Crypto Module) 3 암호알고리즘 (Crypto Algorithm)
1. 암호모듈과암호알고리즘 기밀성데이터무결성인증부인방지 암호화 (Encryption) 데이터무결성기술 메시지인증신분확인전자서명 스트림암호 블록암호 ( 대칭키 ) ( 예 ) SEED 공개키암호 해쉬함수 (Unkeyed) ( 예 ) HAS-160 해쉬함수 (keyed) 전자서명 ( 공개키 ) ( 예 ) KCDSA 전자서명 ( 대칭키 ) 난수생성기 공개키매개변수 특허및표준 암호키분배 Public-key Security Foundations 4 효율적구현 키관리
2. NIST 의 CMVP ( 개요 ) 5 1995 년 7 월미국 NIST 와캐나다주정부의 CSE(Communications Security Establishment) 가공동으로개발한암호모듈의안전성검증을위한프로그램 CMVP(Cryptographic Module Validation Program) 는시험평가후 Level 1~4 를부여하고, List of Validated FIPS 140-1(FIPS 140-2) modules' 에등재하여평가제품으로서효력을발휘할수있게함. 2002 년 1 월현재약 250 여개의암호모듈이검증을받음. 국제공통평가기준인 CC(Common Criteria) 의경우암호알고리즘및암호모듈에대한평가는수행하지않으며, 암호의경우관련표준을따를것을권고하고있으나, 현재암호모듈안전성평가관련표준은 FIPS 140-2 만이표준으로제정되어있는상태여서미국의 CMVP 를참조모델로하고있는실정임.
6 응용시스템 표준권고 Security Specifications Firewalls Smart Cards Operating PKI Systems Telecom DBMS Biometrics Web Browsers Healthcare Encryption Hashing Authentication Signature Key Mgt. DES SHA-1 DSA FIPS 171 3-DES SHA-256 DES-MAC RSA D-H ECDSA MQV Skipjack SHA-384 DSA2 RSA HMAC RSA2 AES SHA-512 ECDSA2 Wrapping 산업계표준차세대표준자체개발 검증된표준 IT SECURITY NIAP 검증되지않은표준 Protocols SSL TLS IPSEC S/MIME IKE EKE SPEKE 검증중인표준 CMVP FISP 140-2 Crypto Modules 암호기술개발표준화
2. NIST 의 CMVP ( 안전성요구사항 ) 1 2 3 7 구현적합성평가 : 구현적합성평가는구현된암호기술이표준에따라제대로구현되었는지를평가하며, 이는각표준에따라평가하는방법이다르다. 암호키운용및관리평가 : 암호키운용및관리에대한평가는암호기술의안전성에직접적인영향을미치는암호키의생성, 확립, 분배, 입 / 출력, 저장, 파기등에대한방법및과정을평가함으로써, 잘못된암호키운용및관리에따른암호키의유출가능성을평가하는것이다. 이는암호모듈의안전성평가중가장중요한부분이라고할수있다. 물리적보안평가 : 물리적보안평가는암호모듈의사용환경에대한평가로서암호모듈의운영환경, EMI/EMC(ElectroMagnetic Interference/ ElectroMagnetic Compatibility), 자기테스트등에대한평가를말한다. 이는암호모듈의운용환경에따라암호모듈을직접적혹은간접적으로물리적인공격을할수있기때문에이에대한평가를한다.
3. 암호의안전성 일방향함수 (One-Way Function) : A function f : {0,1}* -> {0,1}* is called one-way if there is an efficient algorithm that on input x outputs f(x), whereas any feasible algorithm that tries to find a preimage of f(x) under f may succeed only with negligible probability. - Any Feasible Algorithm : 하드웨어 : DTM / NDTM / PTM 소프트웨어 : COA / KPA / CPA / CCA 8 - Preimage : Whole / Partial / Correlated
3.1 COA/KPA/CPA + Whole Preimage 목표 : 일방향성 암호문으로부터평문을구할수없음. 공격자모델 : 공개키 암호문 수동적공격자 평문 9 일방향성의증명 : 상대적비도
3.1 COA/KPA/CPA + Whole Preimage 공개키암호알고리즘 공개키암호알고리즘 A A 가해독가능 귀착 모순 복잡도이론 ( 가정 ) 해결불가능한문제 B B 가해결가능 부분정보 (partial information) 문제 : 평문공간이작을경우불충분! 10
3.1 COA/KPA/CPA + Whole Preimage ( 예제 ) 1976 년 : 공개키암호방식개념제안 (Diffie, Hellman) 공개키암호방식개념을만족시키기위한수학적배경연구 1978 년 : 최초의공개키암호방식개발 (Rivest, Shamir, Adleman - RSA) 11
3.1 COA/KPA/CPA + Whole Preimage ( 예제 ) 공개키 (Public Key) 와개인키 (Private Key) 공개키 (Public Key) 개인키 (Private Key) 12
3.1 COA/KPA/CPA + Whole Preimage ( 예제 ) 공개키저장소 암호화 갑돌이공개키 갑순이공개키 복호화 + + + 갑돌이 갑순이 13
3.1 COA/KPA/CPA + Whole Preimage ( 예제 ) 공개키저장소 31 19 암호화 갑돌이공개키 갑순이공개키 복호화 + + K 19 75 19 + 1/19 75 19 (75 19 ) 1/19 = 75 = K 갑돌이 갑순이 14
3.1 COA/KPA/CPA + Whole Preimage ( 예제 ) 공개키저장소 (19,143) 암호화 갑돌이공개키 갑순이공개키 복호화 + + K (19,143) 49 갑돌이 75 19 mod 143 = 49 + 갑순이 (11,13) 49 EUCLID(11-1,13-1) mod 143 = 75 = K 15
3.1 COA/KPA/CPA + Whole Preimage ( 문제점 ) 평문이 0 또는 1 이라면? 공개키저장소 암호화 갑돌이공개키 갑순이공개키 복호화 + + + 갑돌이 갑순이 16
3.2 COA/KPA/CPA + Partial Preimage 목표 : 다항식안전성 ( 구별불가능성 ) 2 개의암호문을구별할수없음. 공격자모델 : 공개키암호문 0/1 평문공간 {M 0, M 1 } 수동적공격자 17 암호알고리즘 : must be probabilistic!
3.2 COA/KPA/CPA + Partial Preimage Indistinguishable! 즉, 암호문의정보는 Zero. 유출정보유출정보 암호문 공개키 및공개사전정보 공개키 및공개사전정보 수동적공격자 18 Semantic Security (= Polynomial Security) : Computational version of Shannon s perfect secrecy
3.2 COA/KPA/CPA + Partial Preimage ( 예제 ) Random 한패딩정보삽입! 공개키저장소 암호화 갑돌이공개키 갑순이공개키 복호화 + + + 갑돌이 갑순이 19
3.2 COA/KPA/CPA + Partial Preimage ( 예제 ) 공개키저장소 31 19 암호화 갑돌이공개키 갑순이공개키 복호화 + + K 19 (75 R) 19 + 1/19 (75 R) 19 (75 R 19 ) 1/19 = 75 R -> 75 = K 갑돌이 갑순이 20
3.2 COA/KPA/CPA + Partial Preimage ( 예제 ) 비밀키 : p, q 공개키 : n = pq, 이차비잉여 y m = m 1 m 2 m t 의암호화 : (c 1, c 2,..., c t ) 난수 x i 선택, If m i = 1 then c i = yx i 2 (mod n) else c i = x i 2 (mod n) (c 1, c 2,..., c t ) 의복호화 : 21 e i = (c i / n), If e i = 1 then m i = 0 else if e i = -1 then m i = 1
3.2 COA/KPA/CPA + Partial Preimage ( 문제점 ) 암호문을조작할수있다면? 공개키저장소 암호화 갑돌이공개키 갑순이공개키 복호화 + + + 갑돌이 갑순이 22
3.3 CCA + Correlated Preimage After queries to DO Before queries to DO C 0 PK DO 능동적공격자 C 1,, C n M 1,, M n Decryption Oracle M 0 23 RULE : C 0 = C 1,, C n
3.3 CCA + Correlated Preimage ( 예제 ) C = 75 19 가로채기 능동적공격자 2 3 19 *C = (3*75) 19 = 225 19 3 225 (225 19 ) 1/19 = 225 =? 24 1 난수 3 선택 4 225/3 = (3*75)/3 = 75 = K
3.3 CCA + Correlated Preimage ( 예제 ) 공개키저장소 31 19 갑돌이공개키 갑순이공개키 C C 1 C = 1000 19-10% 능동적공격자 25 2 C = C * (0.9) 19 = (1000 * 0.9) 19 = 900 19
3.3 CCA + Correlated Preimage ( 예제 ) RSA-OAEP:de facto standard format of the RSA encryption used in SSL(PKCS#1) and SET m 00 0 r G + + G(r) H(s) H (Example) RSA-OAEP ( ) 26 C = s t e mod n s C = f ( s t) f t ( ) : one-way permutation
History of Provably Secure Public-key Cryptosystems (Encryption) 1976 1978 1979 1982 1984 1990 1991 1994 1998 DH RSA Rabin GM NY (OW-CPA) (IND-CPA) (IND-CCAI) DDN BR EPOC CS (NM-CCA2) (Random oracle model) Concept of public-key cryptosystem Proposal of various tricks Provable security (Theory) Practical approach by random oracle model Practical scheme in the standard model 27 Cited from Dr. T.Okamoto s Presentation Material in KISA
3.3 CCA + Correlated Preimage ( 문제점 ) After queries to DO Before queries to DO C 0 PK DO Not Consider a Higher-Level Protocol Designer! 능동적공격자 C 1,, C n M 1,, M n Decryption Oracle M 0 28 RULE : C 0 = C 1,, C n
3.4 Strong CCA C 0 PK DO An indication that the chosen ciphertext is invalid. 능동적공격자 C 1,, C n M 1,, M n Error Sig DUMP MEM Decryption Oracle 29 M 0 Non-erased internal state of Decryption Oracle
3.4 Strong CCA [1998] Bleichenbacher s Attack on RSA PKCS #1 [2000] Memory Reset [2001] Adversarial Encoding [2001] Memory Dump [2001] Composition Method of Cryptographic Primitives Krawczyk recommended to use Encrypt-then-Authenticate method when building secure channels. 30 AtE (SSL) : a = MAC(x), C = DES(x,a), transmit C EtA (IPSec) : C = DES(x), a = MAC(C), transmit (C,a) E&A(SSH) : C = DES(x), a = MAC(x), transmit (C,a)
4. 암호칩의안전성 RSA Key generation Generate two distinct random primes p and q Compute n = pq and (n) = (p-1) (q-1) Select a random integer e, 1<e< (n), such that gcd(e, (n))=1 Compute d, 1<d< (n), such that ed=1 (mod (n)) Public key: (n, e); Private key: d Signature generation Signature for message M : S = M d mod n Verification 31 Compute M = S e mod n
4. 암호칩의안전성 RSA with CRT Key generation The same parameters Signature generation Generate s s Signature for M : p q S M M d d u q p p mod mod q s p p (, where d u (, where d q s q q p mod d mod( p 1)) d mod( q 1)) N, where u p 1mod p 0mod q and u q 0mod p 1mod q 32 Verification The same procedure
4. 암호칩의안전성 테스트환경 - CPU : Pentium III 555Mhz - 메모리 : 256MB - OS : x86 Solaris 8-100번반복수행후, 평균수행시간을산출 결과 - 시간측정단위 : msec DSA ECDSA 주 ) 고속 RSA RSA 공개키크기 1024 bits 160 bits 1024 bits 1024 bits 서명생성 12.8 8.4 17.1 50.6 서명검증 28.5 18.8 2.6 2.6 33 주 ) SECP160R1 곡선이용
4.1 Timing Attack 첫번째비트를제외한전체수행시간 Dis t ribut ion of t he exec ut ion t imes of t he ent ire t ra ns f orma t ion time Dis t ribut ion of t he exec ut ion t ime it era t ions exc ept t he f irs t one 여러개의평문에대해측정한시간분포를구한다. 측정한시간분포를 d 0 =0 일때와 d 0 =1 일경우를나누어각각의확률분포를나타낸다. 아래의그림에서는 d 0 =0 일경우의표준편차가크므로추측하는비밀키의특정비트 d 0 는 1 이된다. Countermeasure : 평문이나비밀키를마스킹하는방법이대표적이다. 34 시간분포와표준편차
4.2 Fault Attack (Register Fault Attack) Example) j = n-2 번째비트에오류가발생하였을경우 서명값은 레지스터오류를포함한 RL 멱승알고리듬 오류서명과평문 M을알고 w에대해를알고있는공격자는비밀키의최상위 2비트를알아낼수있다. 35
4.3 Power Attack (SPA) exp1(m e, N) ; LR method { R=M for(i=n-2 down to 0){ R=R 2 mod N if (ith bit of d is a 1) R=R M mod N } return R } LR binary exponentiation M S M S M SPA : 신호파형을직접관측하여비밀키를찾을수있다. S 36
4.4 Power Attack (DPA) SPA + 통계적인분석 Crypto-System K Crypto-System Algorithm Power supply Step 2. 데이터분석 A 가능한키영역에서키의일부를추측 B 분류함수 D를이용하여전력신호데이터를분류한다. S S 0 1 { S [ j] D(key,data) 0 or low hamming weight} { S [ j] D(key,data) 1or high hamming weight} i i C 양분한데이터를각각평균하여차분신호를 p 0 p 1 p t 1 C 0 C 1 C t 1 S [ j 0 ] S [ j 1 ] S [ j t 1 ] 구한다. 1 [ j] S ] D i[ j] Si[ j S0 S [ j] S S1 S [ j] i 1 0 i S 1 37 Step 1. 데이터수집 (P i, C i, S i [j]) 의쌍을수집 D 추측한키를검증한다. lim t lim t D D [ j] non - zero [ j] 0 if if guess is correct guess is incorrect
4.1 RSA 에대한 Side-Channel 공격요약 Timing Attack Fault Attack Power Attack 1 Target d d d 2 Method Time difference in exponentiation. dep. on d j. Fault at only single register bit in computation Power dissipation linear to Hamming wgt. 3 References Kocher(96) Boneh et al.(97) Bao(98) Messerges(99) Kocher(99), May et al.(01) (1)Blinding at d (1)Verification fnc. added (1)Blinding at d 4 Countermeasures (2)Dummy processing added dep. on d j (2)Double computations for checking (2)Blinding at message (3)Non-deterministic processor 5 Remarks Not applicable to RSA+CRT Practical to RSA+CRT Very practical attack but not to RSA+CRT 38
4.1 RSA 에대한 Side-Channel 공격요약 Timing Attack Fault Attack Power Attack 1 Target p or q p or q p or q 2 Method Use of extra reduction in Montgomery Multiplication (( s ) e m, n) p or q Not yet in literatures 3 References Schindler(00) Boneh et al.(97) Joye et al.(99) Kocher(98) 4 Countermeasures (1)Verification fnc. added (1)Blinding at m (2)Double computations for - checking 5 Remarks Not applicable to a Montgomery Multiplier Without the final subtraction Yen s & Shamir s countermeasures Need to search for a trap to find p or q 39
감사합니다. http://www.crypto.re.kr http://www.cryptographer.info 40