[암호 스터디 #3] 암호학적 보안

2째주에 2~3 장을 함께 공부해야해서 조금 빡세지만 ,, 해봤다!

3.1 불가능의 정의

암호학에서 불가능을 2가지의 개념을 가지고 정의한다.

1) 이론적인 불가능성에 대한 정보 보안성(informational security) : 보안을 정량화 하지 않는다. ( 실제 응용에서 쓸모가 없다. )

2) 실질적인 불가능성에 대한 계산 보안성(computational security) : 암호의 세기를 실질적으로 측정

3.1.1 이론적인 보안성: 정보 보안성

암호를 깨는 것이 가능한지 아닌지에 관한 것

ex) 백만년을 들어서 깰 수 있다면 ? 그 암호는 정보적으로 불안전한것.

3.1.2 실용적인 보안성: 계산 보안성

적당한(reasonable) 시간과 적당한 자원( 메모리, 하드웨어, 예산, 에너지 등)안에 깰 수 없으면 안전하다고 간주.

ex) 백만년을 들여서 깰 수 있다고 했을 때 백만년은 적당한 시간이 아니기 때문에 계산 보안성을 갖추고 있는 암호라고 할 수 있다.

- 계산 보안성을 표현

t : 공격자가 수행할 연산 횟수의 한계, 노력의 하계(lower bound; 보안을 깨는 데 필요한 최소한의 연산 횟수)

ε : 한 공격의 성공 확률의 한계 ( 엡실론 )

- (t,ε) 보안이란

: 공격자가 최대 t회의 연산을 수행할 수 있고 그 성공 확률이 ε을 넘지 않을 때의 암호

: 즉, 공격자가 적어도 t번을 연산을 했을 때 성공 확률이 ε라는 것이지 t번을 해서 깰 수 있다는 것이 아님.

3.2 보안성의 정량화

안전하다고 간주되는 어떤 암호가 주어졌을 때 우선 파악해야 할 것은 그 암호가 어느 정도의 공격 노력을 견딜 수 있는지이다. 이를 답하기 위해서 다음 절들을 공부해보쟈.

3.2.1 비트수를 척도로 한 보안성의 측정

- t 보안

: 계산 보안성의 맥락에서, 성공적으로 공략하는 데 적어도 t회 연산이 필요한 암호

: 성공 확률 ε이 1에 가깝다고 가정

- n비트 보안, n비트 안전

: 주어진 보안 개념을 침해하는 데 약 2^n회의 연산이 필요하다

--> 연산 횟수를 알 수 있다면 이진 로그를 취해서 그 암호의 보안 수준(security level)을 알 수 있다.

- 비트 보안성은 암호들의 보안 수준을 비교할 때는 유용, but 실제 비용에 대한 정보를 충분히 주지않는다.

3.2.2 전방위 공격 비용

실질적인 보안 수준을 추정할 때, 병렬성, 메모리, 계산 전 연산, 공격 대상 수 를 반드시 고려해야 한다.

- 병렬성

두 공격이 있을 때 한 공격은 순서 의존적(sequentially dependent) 연산을, 다른 한 공격은 순서 독립적(sequentially independent)이라고 하자. 당연히 병렬 즉 순서 독립적 공격이 더 빠르게 작업을 할 수 있다.

- 메모리

공격의 공간 소비와 관련해서 중요하게 고려할 사항은 1회의 공격 도중 필요한 메모리 참조(lookup) 횟수, 메모리 접근 속도(읽기, 쓰기 속도 다를 수 있음), 접근한 자료의 크기, 접근 패턴(연속된 메모리 주소 접근 또는 임의 메모리 주소 접근, 연속된 메모리 주소 접근이 더 빠름), 메모리 안의 자료 구조 등이다.

- 사전 계산

사전계산 : 공격 시 한 번만 수행한 후 계속 재사용할 수 있는 연산, 공격의 오프라인 단계(offline stage)라고 부르기도 한다.

실제 사례 ) 2G 이동통신 암호화에 대한 한 공격은 2개월의 시간을 들여서 2TB 분량의 참조표를 생성, 그것을 이용하여 2G 암호화를 깨고 비밀 세션 키를 얻는 데는 단 몇 초밖에 걸리지 않았다.

- 공격 대상 수

공격 대상이 많을 수록 공격면(attack surface)도 넓어진다.

ex) n비트 키를 공격 대상으로 삼는다 하면 2^n 만큼의 시도가 필요하겠지? 근데 그 중 M개의 키를 찾는다고 하면 또한 M개를 모두 찾는게 아닌 그중 하나만 찾아도 된다면 M/2^n 이겠지?

정리하자면 대상의 수가 증가하면 공격의 비용과 시간이 감소한다는 것이다.

3.2.3 보안 수준의 선택과 평가

현재 보안 수준을 선택할 때는 흔히 128비트 보안성과 256비트 보안성 중 하나를 선택하게 된다.

64비트나 80비트는 보안성이 충분하지 않기 때문이다.

3.3 보안의 달성

보안 수준을 선택한 후에는 암복호화 방안이 그 수준을 유지하게 하는 것이 중요하다.

암복호화 알고리즘의 보안성에 관한 확신을 가지는 방법에는 아래 두가지가 있다.

1) 수학적 증명에 의존하는 증명 가능 보안성(provable security)

2) 알고리즘을 깨려고 했지만 실패한 사례들을 증거로 삼는 발견법적 보안성(heuristic security)

3.3.1 증명 가능 보안성

: 주어진 암복호화 방안을 깨는 것이 다른 어떤 어려운 문제를 풀기보다 쉽지 않음을 증명한다.

그러한 보안성 증명(security proof)이 있다면 해당 난해 문제가 여전히 어렵다 -> 암호도 어렵다 -> 안전

이런 증명을 환원(reduction)이라고 한다.

1) 수학 문제를 기준으로 한 증명

ex) 소인수분해 문제(factoring problem) - RSA

두 소수의 곱 (n = pq)임이 알려진 어떤 수가 주어졌을 때 그 두 소수를 구하는 것이다. n이 작을 때는 쉽게 풀리지만 n의 비트수가 3000 이상이면 현실적으로 불가능하다고 간주한다.

- RSA

평문을 암호화 할 때 : 평문 P를 커다란 수로 취급해서 C = P^e mod n 을 계산한다. ( e,n :공개 키 )

암호문을 복호화 할 때 : P = C^d mod n ( d :비밀 키 )

-> n을 소인수분해할 수 있으면 RSA 깰 수 있음(공개 키에서 비밀 키를 복원), 비밀 키를 얻으면 n을 소인수분해할 수 있음.

2) 다른 암호학 문제를 기준으로 한 증명

: 대칭 암호에 대한 보안성 증명할 때 쓰임

ex) 완벽한 해시 알고리즘이 있다고 가정을 하고 우리가 만든 암복호화 방안이 해시 기반이라면 해시 알고리즘 보다 약하지 않음을 증명할 수 있다.

장점 : 암복호화 방안을 다 살펴볼 필요가 없이 핵심 알고리즘만 살펴보면 된다. ( 공격 벡터가 줄어 들어 살펴봐야할 곳도 줄어든다. )

3) 함정들

- 수학에서 증명은 '절대적 진리'를 입증하는 것이지만, 암호학에서 증명은 그냥 '상대적 진리'를 보여주는 것일 뿐이다.

- 어떤 암호의 비밀키를 복원하는 것이 소인수분해를 푸는 것만큼 어렵다고 증명했을 때, 공격자가 키 없이 평문을 복원할 수 있다면 키를 복원하는 것이 얼마나 어려운지는 문제가 되지 않는다.

- 종종 어려운 수학 문제가 생각보다 쉽게 풀린다는 점이 밝혀지기도 한다.

- 알고리즘의 보안성 증명이 옳다고 해도, 알고리즘 구현이 약할 수 있다.

3.3.2 발견법적 보안성

- 증명 가능 보안성은 암복호화 방안에 관한 확신을 얻는 데 아주 좋은 수단이지만, 모든 종류의 알고리즘에 적용할 수 있는 것은 아니다. 사실 대부분의 대칭 암호에는 보안성 증명이 존재하지 않는다.

- 증명 가능 보안성 접근 방식을 적용할 수 없는 경우, 어떠한 암호가 안전하다고 믿는 유일한 근거는 수많은 능력있는 사람들이 그것을 깨려고 했지만 실패했다는 점밖에 없다. -> 발견법적 보안성

ex) 암호를 만들어 놓고 세계적으로 유명한 암호해독가 103982명을 불러서 깨보십쇼 했는데 못깨면? 암호가 안전하다고 믿는 것이다.

3.4 키 생성

뭔가를 암호화하려면 키들을 생성해야 한다. 암호학적 보안에서는 비밀 키가 관건이다.

암복호화를 위한 키는 3가지 방식 중 하나로 만들어 내야 한다.

1) 무작위 생성 : PRNG 사용하고, 필요하다면 키 생성 알고리즘 사용 ( 아래 설명들은 무작위생성을 기준으로 함 )

2) 패스워드 기반 생성 : 사용자가 제공한 패스워드를 하나의 키로 변환하는 키 유도 함수( Key derivation function, KDF ) 사용

3) 키 합의 프로토콜 : 둘 이상의 통신 당사자들이 특정한 프로토콜에 따라 메시지들을 교환해서 하나의 공유 키를 확립한다.

3.4.1 대칭 키 생성

대칭 키 : 두 당사자가 공유하는 비밀 키, 생성하기가 가장 쉬움

: 흔히 키의 길이 == 보안 수준

: 암호학적 PRNG를 이용해서 n 비트 생성해서 그거를 쓰면 됨.

3.4.2 비대칭 키 생성

비대칭 키는 대칭 키 보다 생성하기 어렵다!!

비대칭 키를 생성하기 위해서는 의사난수 비트들을 종잣값으로 사용해서 키 생성 알고리즘(key-generation algorithm)을 실행해야 한다.

- 키 생성 알고리즘

: RSA를 위한 키 생성 알고리즘은 난수 두 개를 생성해서 n=pq 를 산출 하고 난수이면서 소수인 p,q를 얻기 위해서 소수판별 알고리즘도 필요함.

3.4.3 키의 보호

1) 키 포장(key wrapping) : 보호할 키를 2차 키로 암호화한다.

단점 : 원래의 보호된 키를 복호화하려면 2차 키가 필요하다.

ex) 보안 셸(SSH) 프로토콜의 비밀 키 보호

2) 비밀 키를 패스워드로부터 즉석에서 생성

장점 : 비밀 키를 따로 파일에 담아 둘 필요가 없다.

단점 : 강도가 약한 패스워드에 좀 더 취약하다.

3) 키를 하드웨어 토큰( 스마트카드나 USB 장치 )에 저장

장점 : 가장 안전한 키 저장 방법

단점 : 비용이 가장 크다

  : 항상 하드웨어 토큰을 가지고 있어야해서 불편함도 가장 크다

  : 하드웨어 토큰을 분실할 위험도 있다.