2016 암호여름학교 NIMS 
한참 재밌게 듣다가 갑자기 놓침....

Provable Security of Public-Key Cryptography

Aaram Yun, School of ECE, UNIST

Summary

• '증명가능한 안전성', 즉 provable security는 80년대 중반에 Goldwasser와 Micali가 계산복잡도 이론에 근거해서 암호화 방식의 안전성을 엄밀하게 정의하고 이를 환원 증명을 통해 증명한 이후로 암호학적 설계에서 중요한 패러다임으로 자리 잡았고, 오늘날은 사실상 공개키 암호학의 거의 전 분야에서 요구되고 있다. 본 강의에서는 구체적인 예를 통해 증명가능한 안전성에 관해 설명하고자 한다. 특히, IND-CCA 안전성을 만족하는 최초의 효율적인 암호화 방식인 Cramer-Shoup의 안전성 증명을 자세히 살펴보도록 한다.

Provable Security?

A bit of History...

• 1976 : Diffie & Hellman, "New direction in cryptography"
• 1982 : Goldwasser & Micali, "Probabilistic encryption and how to play mental poker, keeping secret all partial information", STOC 1982
  • Turing award for 2012

Provable security

Goldwasser & Micali

Why proof?

• Else, how can we be sure nobody learned anyting from what they have eavesdropped?
• or, how do you know that nothing happened?

Unconditionally?

• Bad new: currently, we don't know how to design a cryptosystem with proven security
• Because, if P=NP, then you can break

P and NP

Class P

• A problem is in class P: if it can be solved efficiently(in polynomial time)
• EX : Eulerian path problem
• "Given a graph G, is there an Eulerian path in this graph?"
• Eulerian path itself is the witness

Class NP

• A problem is in class NP : if given an answer, checking it can be done efficiently
• EX : Hamiltonian path problem
• "Given a graph G, is there a Hamiltonian path in this graph?"
• Hamiltonian path itself is the witness
• 정답을 확인하는 것은 쉽지만 정답을 찾는 건 어렵다.
• Another Example : "Given a bitstring c and a public key pk, is this c an encryption of some message with respect to the public key pk?"
• That is, do we have c = Encpk(m) for some message m?
• what can be the witness?

P vs NP Problem

• We have P =< NP. Do we have NP = P? or is there some problem in NP which is outside of P?
• Most people believe P != NP, but very hard to prove
• If NP = P, you can solve any NP problems efficiently
• You can answer questions like "Do we have c Encpk(m) for some messages m?"
• Big Deal?

Unconditional security

• So, P = NP --> such cryptosystem will not be secure
• Then, provably secure cryptosystem -> prrof of P = NP
• This is far beyond cryptography

Reduction

Use reduction between problems

• Given algorithm A for solving problem a, design algorithm B for solving b, which uses A as a subroutine
• Later, solving a -> solving b
• On the other hand, infeasible to solve b -> infeasible to solve a

Reductions everywhere

Reduction became the core methodology in complexity theory

• In a sense, bypassing P vs NP problem
• classifying between problems

Reduction and P.S.

• X : difficult mathematical problem
• E : cryptosystem
• R : polytime reduction for solving X, using an
• E can be attacked efficiently -> X can be solved efficiently
• Contrapositive : X cannot be solved efficiently -> E cannot be attacked efficienty
• The trust in the hardness of X is transferred into the trust in the security of E

More History

• Middle 80s - Early 90s : ad-hoc crypto & provable security went in parallel
• Random Oracle Model : to design practical & somewhat provable schemes
• Bellare & Rogaway : "Random Oracles are Practicals", 1993
• 2000 - : trying to do things in the Standard model

Case study : Cramer-Shoup encryption

Notion of PKE

Provable security of PKE

• 3-step recipe for provable security
• Step 1 : you need to define what you are making
  • Step 1-1 : you need to describe its syntax, or, correctness
  • Step 1-2 : you need to describe its security properties
• Step 2 : describe a concrete scheme realizing above notion
• Step 3 : give a reduction proof

Public-key encryption

Consists of 3 Polynomial algorithms( Gen, Enc, Dec)

• (pk, sk) <- Gen(1^lambda) : given security para lambda, Gen outputs public key & security key pair (pk, sk)
• c <- Encpk(m) : given a public key pk and a plaintext m, Enc outputs corresopnding ciphertext c
• Decsk(c) outputs a message, or it may fail to decrypt

Syntax of PKE

• The algorithm should satisfy the following:
• for any lambda, if key pair (pk, sk) is generated by (pk, sk) <- Gen(1^lambda), then for any plaintext

IND-CCA encryption

• Cramer-Shoup "First practical IND-CCA public key encryption scheme in the standard model"

Semantic Security

Intuitive security we want for an encryption

• "Even if you happen to know c, it won't help you at all in learning anything more about the plaintext m"
• c doesn't leak even one bit of information about m
• This is called semantic security
• Satisfying definition, but hard to use

Indistinguishability

• I'll give you a ciphertext c. This is either encryption of m0, or m1. Guess which is the case
• By default, you can win this game with probability 1/2$12$

Similar to semantic security, or, a special case of semantic security

• You already know that the plaintext is m0, or, m1

Semantic security VS IND

• Clearly, if your encryption scheme satisfies semantic security, then it also satifies IND
• Importantly, the other direction is also true
• 그래서 보편적으로 IND를 암호화 다룰 때 더 많이 씀

IND game

• A : polytime adverary
• IND GAME
• (pk, sk) <- Gen(1^lambda)
• (m0', m1', state) <- A('find', pk)
• b <- {0, 1}; c' <- Encpk(mb')
• b' <- A('guess', c', state) (not allowed to query c')
• A wins IND game if b = b'

Chosen ciphertext attack

Chosen plaintext attack

• The attacker's ability to create a ciphertext for any plaintext chosen by the attacker
• Obvious in PKE

Chosen ciphertext attack

• The attacker's ability to obtain decryption of any ciphertext chosen by the attacker
• IND-CCA : even against such powerful attacker, any ciphertext which is untouched by the attacker is still IND-secure

IND-CCA Justification?

Security assumption

Diffie-Hellman

• G : a group of prime order p
• g (- G : uniform random
• Assume discrete logarithm is hard on G : given g^a
• If you know g, g^a, and b (- Zp, then easy to compute gab=(ga)b$g^{ab}{g}^a{}^b$

Decisioin Diffie-Hellman

DDH Problem

DDH assumption : alternatively

DDH game

• b <- {0, 1}
• If b = 0, sample (g1, g2, u1, u2) <- D
• Else, sample (g1, g2, u1, u2) <- R
• b' <- A(g1, g2, u1, u2)
• b = b'

Collision-resistant hashing

• one more ingredient : hash function
• A hash function H maps elements in a large domain to a small, fixed size codomain
• Naturally, there should be lots of collisions : a pair (x, y) where H(x) = H(y) but x!=y$xy$
• H is collision-resistent, if it is computationally hard to actually find a collision
• 계산 자원에 제약이 주어지는 상황에서는 찾아내는 것이 불가능

Key generation

• Choose G with prime order p according to security parameter
• Choose g1,g2<−G$g_1{g}_{2}G$ : uniform random
• Choose x1,x2,y1,y2,z<−Zp$x1x_2{y}_1{y}_{2}z{Z}_p$: uniform random
• c=g1x1g2x2,d=g1y1g2y2,h=g1z$c{g_1}^{x_1}{g_2}^{x_2}d{g_1}^{y_1}{g_2}^{y_2}h{g_1}^z$

Encryption & Decryption

• (사정상 생략)

IND-CPA security of Cramer-Shoup

IND-CAP security

• Cramer-Shoup is IND-CPA, if DDH assumption holds

IND-CPA reduction proof

Basic idea

• B is DDH solver, so it receives a tuple t=(g1,g2,u1,u2)$t{g}_1{g}_2{u}_1{u}_2$
• B wants to find out if this tuple is a DDH tuple(from D), or a random tuple (from R)
• B simulates the IND-CPA game environment of A

How to determine t using A?

• B's simulation should at
• B will use this tuple t to create challenge ciphertext c∗$c^{}$ for A
• c∗=(u1,u2,u1zmb,u1x1+y1au2x1+y1a)where,a=H(u1,u2,u1z)$c^{}{u}_1{u}_2{u_1}^z{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}whereaH{u}_1{u}_2{u_1}^z$
• If t is from D, then c∗$c^{}$ is the same as correctly created
• On the other hand, if t is from R, then c∗$c^{}$ is a fake encryption for mb∗${m_b}^{}$
• c∗=(u1,u2,u1zmb,u1x1+y1au2x1+y1a)$c^{}{u}_1{u}_2{u_1}^z{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}$
• claim : from A' is point of view, u1z${u_1}^z$ is uniform random
• If so, u1zmb${u_1}^z{m}_b$ is also uniform random : it can be anything in G equally likely : no matter what b is
• In that case, A can win the fake IND-CPA game with prob. 1/2
• c∗=(u1=g1r,u2=g2r′,v=u1x1+y1au2x1+y1a)$c^{}{u}_1{g_1}^r{u}_2{g_2}^{r^{}}v{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}$
• (이하 생략. PPT 참조 바람.)

Bypassing the problem

• B will simulate IND-CPA game, but generating a fake pk
• Choose x1,x2,y1,y2,z1,z2<−Zp$x_1{x}_2{y}_1{y}_2{z}_1{z}_2{Z}_p$ : uniform random

• compute c=g1x1g2x2,d=g1y1g2y2$c{g_1}^{x_1}{g_2}^{x_2}d{g_1}^{y_1}{g_2}^{y_2}$

• Claim : this modification is completely invisible to A

Reassessing the situation

• B will use tuple t to create challenge ciphertext c∗$c^{}$ for A
• c∗=(u1,u2,u1z1u2z2mb,u1x1+y1au2x1+y1a)where,a=H(u1,u2,u1z1u2z2)$c^{}{u}_1{u}_2{u_1}^{z_1}{u_2}^{z_2}{m}_b{u_1}^{x_1{y}_{1}a}{u_2}^{x_1{y}_{1}a}whereaH{u}_1{u}_2{u_1}^{z_1}{u_2}^{z_2}$

Uniform randomness

Going to IND-CCA

""솔직히 너무 어려워서 잘 이해를 못하고 받아 적기만...."" 

Post-Quantum Public-key Cryptography

IT requires Public-key Cryptography

• 전자상거래의 증가

Factorization Progress

Inter Factorization Problem (IFP)

• Given a composite n = pq, find p and q
• 소인수 분해의 이산대수 문제
• 분석 기술이 나날이 발전중

DLP Progress in F_p^n

Discrete Logarithm Problem

• Given g^x in

ECDLP Progress

Elliptic Curve DLP

• Given xP in E(F_q), compute x.

The quantum computer threat

Shor Algorithm 1997

• Polynomial-Time algorithm for Prime Factorization and Descrete Logarithm on quantum computer
• RSA and ElGamal insecure

Quantum computer realistic?

• NSA seeks to build quantum computer that could crack most types of encryption
• Researchers use silicon to push quantum computing toward reality

만약 양자컴퓨터를 만들어도 발표하지 않고 사용할 가능성이 높기 때문에 위험

Target Environment

Post-quantum cryptography for small devices

• identity and adapt the most suitable PQ candidates to the requirements of constrained devices and to produce efficient and physically secure implementations *

PQ-Crypto for internet

• internet severs are subject to tremendous performance pressures
• goal is to intergrate high-security PQ-crypto into internet

PQ-Crypto for Cloud

NSA Suite B Cryptography

NSA announced that it is moving towards quantum-resistant algorithm

• Suite B is a family of cryptography......

Public key Cryptography

Quantum Cryptography

• Quantum key distribution(QKD)
• QKD is still vulnerable to a man-in-the-middle attack
• so far lacks the functionality of digital signatures
• 모든 키분배는 중간자 공격에 안전하지 않다.
• 양자 암호로는 인증까지는 할 수 없다. 그래서 공개키 암호와 함께 사용

Post-Quantum Problems

• Solving non-linear equation systems over finite fields
• Bounded distance decoding over finite fields
• Short and close lattice vectors
• Breaking cryptography hash functions
• Quantum key exchange
• 찝찝한 부분은 양자 컴퓨터에 안전하다고 증명되어 있지는 않다.
• 다만, 알려져있는 양자 알고리즘에 적용할 수 없는 알고리즘을 사용한 암호

Quantum Algorithms

Grover algorithm brings faster simultaneous search in data

• some security loss in symmetric crypto
• some security loss in hash functions

Polynomial-time quantum algorithm for

• factoring .....
• 생략

Quantum algorithms for Lattice-based crypto

SOLILOQUY, a lattice-based primitive designed at CESG in2016

• the security of SOLILOQUY is based on two well known hard problems
• closed vector problem
• principal ideal problem

Multivariate Quadratic-based PQ-Crypto

Retrospective of MQ-PKC

• Claude E. Shannon

• Breaking a good cipher should requires as much work as solving a system of simultaneous equation in a large number of unknowns of a complex type

• After the NESSIE consortium proposed SFLASH to be standardized. -> 2010 년도에 깨짐

MQ-Encryption

Multivariate public key cryptosystems

• Cryptosystems, whose public keys are a set of multivariate

• the public key is given as :

  • G(X1, ... , Xn) = (G1(X1, ... , Xn), ... , Gm(X1, ... , Xn))

• We use the finite field k = GF[2]/(x^2 + x+ 1) with 2^2 elements

• (more)

Soving Polynomial System (SPS) Problem

• given a system P = P1, ... , Pm of m nonlinear polynomial equations
• ....

Destructive Aspect of MQ-Problem

• 안좋은 면 : MQ를 이용해서 암호화 알고리즘을 설계하는 데 다른 암호 알고리즘을 깰 수도 있다.
• AES 같은 걸 깰 수 있음
• 관계식에서 아는 것과 모르는 것을 구분해 낼 수 있으면 그게 다변수 방적식

Attacks on AES

• 2^8에서 시도를 하면 3986개의 변수를 갖는 시스템을 풀면 AES 깰 수 있다.
• 카탄과 같은 경량 암호들도 다변수 시스템으로 나타낼 수 있기 때문에 공격 가능

Constructive Aspect of SPSP

ASA(Affine-Substitution-Affine) Structure

• trapdoor S have been hidden in secret affine layer
• AES-128 10 rounds with 19 layers

SASAS Structure

ASASA Structure

• truly random polynomial
• large public key size => 연산이 계속 늘어나면 degree가 점점 늘어남

MQ-PKCs

MQ-PKCs can be divided into the following two types

• MI-Scheme

동형암호

암호의 분류

• 1세대 암호 : 패스워드 (인증기술)
• 2세대 암호 : 대칭키 암호 (데이터 암호화)
• 3세대 암호 : 공개키 암호
• 4세대 암호 : 동형 암호

미래 컴퓨팅 환경

우리가 원하는 완벽한 하인

• 내가 하려는 일을 빠르게 대신 수행
• 비밀을 알지 못한다.

사례1 : 개인 클라우드

• 스토리지 클라우드 (드랍박스, 구글 드라이브, NAS 등)
• 계산 클라우드 : DNA 계산, 헬스케어, 개인성향분석을 통한 추천

사례2 : 다수 사용자 통계분석

• 개인정보기반 마케팅 (구글, 페이스북, 네이버 등)
• 정부 데이터

4세대 암호

4세대 암호 : 암호화된 데이터를 복호화 없이 연산하는 암호

• 탐색가능암호, DB암호 등
• computing on encrypted data, secure multiparty computation

동형암호(Fully Homomorphic encryption) : 2009 Gentry

• MIT가 선정한 2011년 10대 미래 유망 기술

개인정보기반 광고 시장

• facebook, twitter 등의 성장
• 구글 : gmail 등 구글의 개인정보를 통합관리
• 합법적인가? 안전한가?

Privacy Homomorphic

10 Emerging Technologies(MIT Technical Review 2011)

• Gentry's system

동형암호 설계 방법

Find an isomorphism between 주인 and 하인

• 주인쪽 연산을 하인도 동일하게 수행
• Enc : P -> C

• f    f'
  

• Enc : P -> C

문제 : 기지평문공격 (known text attack)

• y = E(x)인 (x, y)를 알면 y2$y^2$ 의 평문은?
• DE(x2)=x2$DE{x}^2{x}^2$, but E(x2)!=E(x)2$E{x}^2{Ex}^2$
• Noisy Isomorphism (C가 P보다 월등히 크다)

Pros and Cons

장점

• 컴퓨터에서 데이터의 모든 연산은 and, or, not의 논리 게이트로 연산
• 암호화된 상태로 and, or, not 연산이 가능하면 컴퓨터로 하는 모든 연산이 가능
• 해커의 데이터 유출 원천 봉쇄

단점

• 암호문 확장 : 10-100 K배 -> 0.1-1배 (대칭키 방식)
• 암복호화 속도 : 수십ms (AES : 1us, RAS : 1ms) -> 이제는 해결됨. 빨라짐
• 암호문 연산 : 곱셈 수백ms
• 응용연산 종류에 따른 속도의 차이가 큼 -> 개별적 최적화

법과 항등식

a-b가 n의 배수 <-> a = b (mod n)

• 예 : 5 = 2 (mod 3)

a=b(mod n) 이고, c=d(mod n) 이면

• a+c = b+d (mod n)
• a-c = b-d (mod n)
• ac = bd (mod n)

문제 : 1234*(56-78) 을 32로 나눈 나머지는?

• (1233+1)((54+2)-(78) ....

완전동형암호

RAD PH

• 비밀키 : 큰 두 개의 소수 p, q
• 공개키 : n = pq
• 암호화 : E(m) = (m mod p, m mod q)
• 복호화 : 중국인의 나머지 정리
• E(m1) + E(m2) = (m1 mod p, m1 mod q) + (m2 mod p, m2 mod q)

•         = (m1 + m2 mod p, m1+m2 mod q) = E(m1 + m2)
  

• 안전한가? Enc : P->C

재부팅 Bootstrapping

• 입력 : 노후화된 암호문, 암호화된 비밀키
• 출력 : 신규 암호문
• 과정 : 곱을 반복하여 노이즈가 커진 암호문을 노이즈가 작은 암호문으로 변경

동형암호

DGVH

• 비밀키 : a large prime p
• 연산키 :

Hard Problem and Security

AGCD Problem

• given several noisy multiples of p, find p.
• e.g, find p given x0 = pq0 + r0, x1 = pq1 + r1 with ri << p

how to solve?

• brute force for noise r or secret p
• Use continue fraction
• use lattice : orthogonal lattice attack and LLL

AGCD is provably hard?

SVP is NP-complete, but only in the worst case

(Ajtai96) SIS is as secure as the uSVP(worst c.)

• find a small integer solution of a system of integer equations

(Regev04) LWE is as secure as GapSVP

• m eqns with n variables over Zp is easy to solve
• what if the answers have noise? -> NP complete
• self-reducible (worst case = average case)

(C.-Stehle 15) AGCD is as secure as LWE

동형암호의 응용

예제1 : 생체인증

생체인증 시장 및 문제점

• 신한은행, 손바닥 정맥 인증 도입, 은행권 생체 본인 인증 본격화
• 생체인증 시장 규모 성장중
• 끊이지 않는 개인정보 유출 사고
• 생체정보는 유출 시 대체 불가능

생체인증 기술 개발

• 생체 정보를 보호하는 동형암호기반 생체인증 기술
• 인증시간 < 0.1초?
• 결과가 맞다 틀리다의 암호문이 나옴. 그래서 풀어주는 절차 필요
• 사용자의 위변조 방지를 위해 MAC 기술 적용

예제 2 : DNA 분석

DNA 분석/정밀의료와 암호화

• 개인의 유전정보를 이용한 정밀의료 새로운 보건의료 패러다임
• 미국 : 정밀의료 이니셔티브(PMI : Precise Medical Initiative) 2016 예산 2억 1500만 달러
• 문제는 유전정보의 보호 기술

DNA 맞춤의학

공공 유전자 변이 DB들로부터 DNA 바이오마커 수집

TCGA 유방암 데이터를 이용하여 유방암 특이적 질병패널 최종선정

• 유방암 질병패널에 기반한 질병감수성 예측모델 추측

DNA Privacy

스트레인저 비전 (조각가, 2012 뉴욕)

• DNA 분석 (공공장소에서 주운 머리카락)
• 얼굴 만드는 소프트웨어 이용
• 3d 프린터

DNA : 궁극의 프라이버시

• 개인의 DNA 정보 수집/악용

예제3 : 암호화된 헬스케어

• 건강진단 <--> 생체정보 (심박/활동량)

개인정보 헬스케어

• 예시 : 서인남성이 심장마비 걸릴 확률에서 변수로 쓰이는 헬스 정보는 나이(a), 키(ht), 몸무게(wt), 수축기 혈압 (sys), 이완기 혈압 (dia), 콜레스테롤 수치(chol) 이다. P(x) = e^x / (e^x-1)
• 실수동형암호의 필요성. 동치 계산을 해야 한다. -> 복소수 동형암호화

Smart Car

Cyber Physical System(CPS)

• 스마트홈에서 센서들이 인터넷에 연결되고 이 정보들과 사용자 명령이 합쳐서 일종의 컨트롤러에 전달되면 이것들이 계산되어 집행됨
• 계산 속도의 문제로 암호화 하지 않은 상태로 사용 중
• 정보조작, 원격조종, 위치정보 공개 등 많은 보안위협 산재
• Floating point HE(실수동형암호)를 통해 새로운 스마트카 제어 모델 설계

What is the next?

동형암호 vs 함수암호

• 현재 추세는 동형암호보다는 함수암호에 더 비중
• 그러나 조금 시각을 달리보면 동형 암호도
• 동형암호 : Enc(M1), ... , Enc(Mn) -> Enc(f(M1, M2, ..., Mn)) 모든 f
• 함수암호 : Enc(M1), ... , Enc(Mn) -> f(M1, M2, ... , Mn) 특정한 f

함수 암호의 응용

• 생체인식 : ENC_k(M1), ENC_k(M2) -> M1 = M2 인지 판별
• 프로그램 난독화 (Obfuscation) : 안전성 증명 -> 존재하는지 아닌지 불확실
• 암호화된 데이터에서 필요 정보 추출 (데이터마다 암호화시 지정)

양자컴퓨터 시대에도 안전!

(PQ) 양자 컴퓨터

양자컴퓨터

pros

• 인수분해와 이산로그를 다항식 시간에 계산
• 검색도 O(sqrt n) 시간에 해결 (groover algorithm)

cons

• NP-hard 문제는 다항식 시간에 계산 안됨
• 다룰 수 있는 q bit를 늘리는 것이 매우 어려움 (현재 수십)

일반적인 예상

• 수십년 이후에나 개발 가능할 듯

Post-Quantum Crypto

NSA Suite B Cryptography (2015 8 19)

• Qunatum Resistant Algorithm 으로 이동 계획 발표
• Suite B에 있는 타원곡선 암호 사용 자제 권고

Post-Quantum Crypto (based on NP-Hard Problem)

• 격자 : SVP and CVP in Integral Lattices of high dim
• 다변수 다항식 : solve multivariate Quandratic eqns
• 코드 : Decode of General Linear Codes
• 해쉬기반

NIST 공모

• 양자 암호에 안전한 공개키 암호 알고리즘
• 전자 서명
• 키 교환 프로토콜
• 다수의 알고리즘을 채택할 것으로 기대
• 공개적으로 투명한 평가를 중시할 예정

cs 쪽에서는 lattice 가 익숙하지만 대수적은 불편 저 두 개를 결합한 이론은 이제 막 연구 시작

https://youtu.be/BylWT5gsgfM

2016 암호여름학교 시간에 서울대학교 천정희(?) 교수님께서 좋은 영상을 소개해 주셨다.

암호화를 쉽게 잘 설명해 놓은 영상

2016 암호여름학교 - 난수발생기 강의

차례

• 난수발생기 개요
• 난수발생기 구조
• 표준 난수 발생기
• 난수 발생기의 안전성 분석
• 안전성 평가 기법과 안전한 활용

난수발생기 개요

난수발생기란?

난수발생기(RBG : Random Bit Generator) 기능

• 암호시스템에 필요한 난수 제공
• 이상적으로는 동전 던지기의 결과를 기대
• 암호시스템과 암호 모듈의 운용에 필수적인 요소

요구되는 성질

• 예측 불가능성
• ()
• () 
  

난수발생기와 보안 시스템

난수발생기의 용도

• 비밀키 암호에 사용되는 암호키 생성
• 공개키 암호의 파라미터 생성
• 기타 : nonce, salt 등

현대 암호의 안전성

• 보안시스템의 암호기능에서 난수 발생기의 사용은 필수
• 암호의 안전성 확보는 완벽한 난수 발생기 사용을 전제로 가능

난수발생기의 용도(1) 암호키

암호키의 생성

• 블록 암호의 암호키
• RSA 공개키 암호의 소수 생성

난수발생기의 용도(2) Salt

사용자 인증(로그인)용 패스워드의 저장

• 패스워드는 암호화된 형태로 시스템에 저장되어야 함
• 암호화 방식
  • 해쉬함수를 이용하는 방법
  • 비밀키 암호로 암호화하는 방법

난수발생기의 용도(3) Bit Commitment

원거리의 Alice와 Bob이 동전던지기 게임을 할 수 있을까?

• Alice : 난수 R1, R2 생성
• Alice : 동전을 던진 결과 a
• Alice : 해쉬값 H(R1,R2,a)와 R2를 Bob에게 전달
• Bob은 Alice의 동전 던진 결과를 b로 예측하여 공개
• Alice는 a를 공개하고, 증거자료로 R1, R2를 전송
• 해쉬값을 계산하여 결과를 검증

난수발생기 관련 용어들

의사난수 발생기(PRNG, DRNG)

• PRNG : Pseudo Random Number Generator
• 일정한 알고리즘에 따라 초기값(seed)로 부터 난수를 생성
• 알고리즘과 초기값이 모든 출력을 결정

진난수 발생기(TRNG)

• TRNG : True Random Number Generator
• 물리적 잡음을 기반으로 난수를 생성하는 장치

기타용어

• DRNG : Determenistic RNG
• DRBG : Deterministic Random Bit Gengerator

난수발생기 종류

TRNG, PRNG의 기본구조를 기반으로 다양한 조합이 가능

• 디지털화(Conversion to binary), 난수생성 알고리즘(Determenistic Algorithm)

난수발생기의 구현

하드웨어 난수발생기

• 하드웨어 장치에서 발생되는 잡음원을 이용한 난수 생성
• 잡음원의 편향된 성질을 보정하는 과정이 필요
• 잡음원(엔트로피 소스) : 열잡음원, 링오실레이터, 빔스플릿터 등

소프트웨어 난수발생기

• 외부의 잡음원 공급을 전제로 결정론적 알고리즘을 사용
• 잡음원 : OS 잡음(마우스 포인터 위치, 프로세스 id 등), 사용자 입력 등

난수발생기의 중요성

난수발생기의 중요성

• 암호시스템의 안전성은 이상적인 난수발생기를 사용해야 보장할 수 있음
• 암호학적 안전성 증명 모델도 완벽한 난수발생기의 사용을 전제로 함
• 난수발생기의 취약성은 보안 매개변수의 안전성을 약화시킴

암호의 안전성과 난수(1)

Caesar Cipher

• 평문(P), 암호문 (C), 암호키(K)의 관계
• \(C = Ek(M) = M+k mod 26)
• 암호키의 종류(26가지)가 너무 적어 안전하지 않음

단순치환 암호

• 암호키(=치환표) : A~Z를 무작위로 섞는 방법
• 암호키의 종류는 26!=4∗10262641026로 충분히 큼
• 출력되는 암호문에 평문 정보가 노출됨

안전한 암호화의 조건

• 암호문읜 난수와 구별할 수 없어야 한다. (평문을 추측할 수 있는 정보를 제공하지 않아야 한다.)
• 암호키는 공격자가 예측할 수 없어야 한다. (키 공간이 충분히 크고, 랜덤하게 선택되어, 공격자가 사용된 키를 맞출 확률이 낮아야 한다.)

난수발생기 구조

난수 생성 이론

Deterministic Extractor

• 결정론적 알고리즘 만으로는 엔트로피 소스로부터 좋은 난수를 얻을 수 없다.
• Extractor 알고리즘을 고정할 때, 주어진 입력 엔트로피가 우수하지만 출력이 균등분포에 근접하지 않는 예가 항상 존재한다.

Seeded Extractor

• Seed의 선택에 따라 extractor가 달라지도록 설계하면 균등분포에 근접한 출력을 얻는다.
• 단, seed의 선택을 잘 해야 한다.
• Ext(X;S) ~= (Uniform, S)

OS 난수발생기 구조

3단계 구조 : 엔트로피 수집, 시드 생성, 난수생성 알고리즘

• 엔트로피 수집 : 잡음원으로부터 엔트로피 수집, 시스템 의존적
• 시드 생성 : 시드(PRNG의 입력) 생성
• 의사난수 생성 알고리즘 : 표준화된 암호 알고리즘

LRNG 구조

• 커널 모드에서 수집된 엔트로피를 pool로 관리하여 출력
• Blocking Model(/dev/random)와 non-Blocking Model(/dev/urandom) 모드
• 디바이스로 마운트되어 작동
• 하드웨어 등의 환경에 따라 달라질 수 있다.

WRNG 구조 (윈도우 난수 발생기)

• 유저모드의 인스턴스로 생성되어 동작 (여러 WRNG 공존)
• 엔트로피 관리가 없어 Blocking Model은 제공하지 않음

표준 난수발생기

ISO/IEC 표준 모델

• ISO/IEC 18031 표준문서에 정의된 난수 발생기

미국의 NIST 모델

• SP800-90A 의 난수발생기 모델 : DRBG

독일의 BSI 모델

• AIS.31

한국 KCMVP의 난수발생기

암호모듈 검증제도의 알고리즘

• Hash_DRBG : sha224/256/384/512
• HMAC_DRBG : HMAC(sha224/~~)
• CTR_DRBG : ARIA128/192/256, LEA128/192/256

난수 발생기의 안전성 분석

난수발생기의 안전성

Backtracking resistence

Prediction resistence

• 공격자가 현재의 상태정보를 알 수 있을 때
• 이전 정보를 보호하는 것 (업데이트 알고리즘을 잘 만들기)
• 향후 출력을 보호하는 것 (다음 단계로 넘어갈 때 엔트로피 소스 넣기)

엔트로피 수집의 취약성

엔트로피 수집 단계의 취약성

• 충분한 엔트로피를 수집하지 못하면 난수의 출력이 예측 가능함
• 대부분의 취약성은 엔트로피 수집단계에서 발생함
• 시스템에서 활용 가능한 잡음원이 충분히 확보되어야 함

비트코인 지갑의 취약성

• 시스템 난수발생기의 취약성으로 전자지갑 탈취
• 비트코잉ㄴ 공개키 암호의 안전성에 치명적 손상 유발

모바일 환경에서의 엔트로피

• 키보드, 마우스 등의 가용 잡음원 부족
• 충분한 엔트로피의 소스를 확보해야 함

엔트로피 수집 - Windows

윈도우 환경에서의 엔트로피 소스

• GetCurrentProcessID()
• GetCurrentThreadID()
• GetLocalTime()
• GetDiskFreeSpace()
• GetComputerName()
• GetUserName()
• .....이 외에도 많이있지만 쓸만한 게 별로 없다

리눅스 환경에서의 엔트로피 소스(LPRNG가 사용하는 엔트로피 종류)

• ~~~

시드 생성 단계의 취약성

엔트로피 축적/시드 생성 단계에서의 취약성

• ios 난수 발생기 취약점
• 안드로이드 난수발생기 취약점

난수생성의 알고리즘의 취약성

의사난수생성 알고리즘의 취약성

• 알고리즘의 취약성 우려제기
• 미국의 NIST의 난수발생 알고리즘 표준
  • 백도어 심어 놓음 -> 스노든의 폭로
• 2014 ISO 회의에서 표준 철회

Dual_EC_DRBG란?

• 타원곡선 이산대수 문제 기반 의사난수발생기
• 미국 ANSI 표준, ISO
• NIST가 권장 파라미터를 제공

암호 전문가가 Dual_EC_DRBG의 취약성 지적

• P = eQ
• rP : Seed, rQ : Output
• 그런데 NSA가 e를 알고 있다는 의혹 제기
• e를 알고 있다면 새로운 난수를 계속 알 수 있음
• 하지만 의혹을 증명할 수는 없다.

안전성 평가 기법과 안전한 활용

난수발생기의 안전성 평가

안전성 평가의 중요성

• 난수 발생기의 취약성은 암호시스템 전체로 전파
• 특히 예측 가능한 출력이 발생하면 치명적

평가의 어려움

• 현실적으로 이상적인 난수에 도달할 수 없음
• 충분히 이상적인 난수에 근접함을 입증해야 함
• 개발자, 시험기관, 검증기관 모두에게 어려운 문제

난수발생기 평가 기준

난수발생기 평가 방법

• 수집되는 엔트로피의 건전성 평가
• 출력난수의 통계적 랜덤성 평가

난수발생기 평가 기준

• ISO/IEC 19790/24759

통계적 난수성 검정의 한계

• 통계적 난수성 검정은 편리한 도구이나 암호학적 안전성을 보장하지는 않는다.

엔트로피 개요

엔트로피 개념

• 데이터가 가진 실제 정보량을 정량적으로 측정한 값
• 엔트로피가 높다는 건 확률은 낮다고 얘기할 수 있음
• random variable의 확률분포가 엔트로피를 결정

엔트로피 종류

• 샤논(shannon) 엔트로피 : 가지고 있는 정보량의 기대값
• 민(Min) 엔트로피 : 확률 멕시멈의 정보량

요약

보안시스템의 안전성과 난수발생기

• 현대암호의 안전성은 난수발생기에 의존함
• 암호키와 보안매개변수 생성에 사용되는 난수발생기의 안전성이 확보되어야 함

난수발생기 평가의 어려움

• 암호 알고리즘의 경우 테스트 벡터의 확인으로 안전성을 확인하는 KAT(Known Answer Test)가 가능함
• (작성중)