동형암호

암호의 분류

  • 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 의 평문은?
  • DEx2x2, but Ex2Ex2
  • 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 가 익숙하지만 대수적은 불편 저 두 개를 결합한 이론은 이제 막 연구 시작

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!=410262641026로 충분히 큼
  • 출력되는 암호문에 평문 정보가 노출됨

안전한 암호화의 조건

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

난수발생기 구조

난수 생성 이론

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


+ Recent posts