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

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)가 가능함
• (작성중)