처음 배우는 암호학 ch3 암호학적 보안

암호학에서의 보안과 컴퓨터에서의 보안은 다르다. 

차이점은 암호학에서는 정량화(quantification)이 가능하다는 거다. 

소프트웨어는 안전하다. 그렇지 않다로 끝나지만 암호학은 암호를 깨는데 필요한 노력의 양을 수치로 계산 할 수 있다. 

목표는 푸는 것이 '불가능'한 문제를 엄밀하게 정의 하는 것이다. 

 

여기서 불가능의 정의란 다음과 같다.

정보 보안성 : 이론적 -> 보안 정밀화 X  (그냥 이론적으로 불가능, 영원히 못 깨는 거_

계산 보안성 : 실질적 -> 실제로 암호 세기 측정

 

계산 보안성은 조건(시간, 자원, 메모리 등) 안에 못 깨면 안전하다고 간주

 

즉 '적당한' 시간 안에 깨는 것은 현실적으로 불가능하다는 점에서 계산 보안성을 갖추고 있음

 

t : 공격 연산 횟수 한계 

\(\epsilon\) : 공격의 성공 확률 한계 

 

어떤 암복호화 방안(Cryptographic scheme)에 대해 공격자가 최대 t 회 연산 성공확률이 $\epsilon$ 을 넘지 않을 때 

이를 (t,\(\epsilon\)) - 보안이라고 부른다. 

t가 lower bound 이다. 

 

성공하는데 적어도 t 회 걸리면 -> t-보안

연산횟수 파악 가능 -> 연산 횟수에 이진로그(보안 수준 파악 가능)

ex) 100000회면 $log_2 (100000) 즉 20비트

키의 크기는 upper bound를 할 뿐 이다. 

 

비트 보안성은 보안 수준 비교에 유용하지만 비용에 대한 정보를 제공하지는 않는다. 

단지 n비트 안전암호를 깨는데 $$2^n$$ 회 연산이 필요함을 말해준다.  

 

---

 

전방위 공격 비용(실제 비용 고려할 때)

1. 병렬성

 ex) 각각 $$2^{56}$$ 회 연산 사용하는 두 공격

둘의 차이는 병렬화 가능 유무

첫 공격 = 순서 의존적 

둘 공격 = 순서 독립적

만약 $$2^{16}$$ 개의 프로세서를 이용한다할때 

$$2^{56}/2^{16} = 2^{40}$$연산

총연산은 같지만 $$2^{16}$$ 만큼 즉 65537배 빠르다. 

 

2. 메모리

3. 사전 계산 : 재사용 가능

4. 공격 대상 수 : 대상이 많아질 수록 시간이 감소 된다. $$2^7/M$$ =  키를 하나만 찾으면 된다.

---

 

보안 수준의 선택과 평가

흔히 128,256 비트 보안성 중 하나 선택

개념적으로 128비트 보안성 깨기 위해 $$2^{128}$$ 연산 수행해야한다. 

 

암복호화 알고리즘이 보안성에 관한 확산을 가지는 방법은 수학적 증명에 의존 

-> 증명 가능 보안성(provable security)

 

능력있는 많은 사람들이 실패한 사례들을 증거로 삼는거는 

-> 발견법적 보안성(heuristic security)

 

 

증명 가능 보안성

- 암복호화 깨는게 다른 어려운 문제보다 쉽지 않음을 증명

이런 증명을 reduction이라고 한다.

ex) 문제 X 을 푸는 어떤 방법으로 어떤 암호를 깨는 방법을 만들면 그 암호를 가르켜 문제 X로 reduction 가능한다고 한다. 

 

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

 

안전한 어떤 암호 -> 새 암호

 

이 새 암호는 그저 암호보다는 이전 꺼보다는 약하지 않다는 거다.  

장점 : 공격면이 줄어듦 -> 새로운 한 문제만 깨면 됨

즉 조합을 깨려면 새 치환을 깨야한다는 결론으로 이어짐

 

 

함정 

연구자들은 보안성 증명에 크게 의존

허나 완벽하지 않음

암호학에서의 증명은 '상대적 진리(Relative truth)' 이다. 

 

대부분의 대칭 암호에는 보안성 증명 존재하지 않음(AES도 )

적용할 수 없을 때 유일한 증거는 많은 사람들이 깰려고 했으나 실패 -> '발견법적 보안성'

 

---

 

키 생성

1. 무작위생성 : PRNG 사용, 필요하면 키 생성 알고리즘 사용 (가장 간단)

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

3. 키 합의 프로토콜 : 특정한 프로토콜에 따라 메시지들을 교환해서 고유 키 확립

 

대칭 키 생성

비밀 키, 생성 쉬움

키의 길이가 보안- 수준과 일치

암호학적 PRNG 사용해서 대칭키 생성 -> 의사 난수 비트 n 생성 -> 이를 하나의 키로 사용

 

ex) openssl rand 16 - hex

 

 

키의 보호

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

문제는 키 복호화 위해 2차키 필요

흔히 쓰는 건 보호된 키가 필요할 때 사용자가 입력한 패스워드로 2차키 생성

흔히 보안 셸(SSH) 프로토콜의 비밀 키가 이런 식

 

2. 비밀 키를 패스워드로부터 즉시 생성 : 비밀 키를 파일에 담을 필요가 없다. 

강도가 약한 패스워드는 보안이 좀 취약해져서 많이 쓰는 방식은 아니다. 

 

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

키를 보안 메모리에 저장하면 컴퓨터가 침해당해도 키는 안전하다. 

제일 안전하지만 비용이 가장 크고 잃어버릴 수도 있고 불편함이 크다. 

 

문제 발생 요인들

- 부정확한 보안 증명들

- 하위 호환성을 위한 짧은 키 : 공개키 기반 암복호화 방안에서는 보안 수준이 키의 크기와 일치 x