[현대 암호학] 06-5. RSA 에 대한 공격 / 6. 선택 암호문 공격

5. RSA 에 대한 공격

 

암호문으로 부터 평문 구하기

 

해독자(공격자)가 가진 정보

 

암호 해독자가 알고 있는 것

• 암호문 : 도청해서 구한다.
• E와 N : 공개 키로서 공개 되어 있음

 

암호 해독자가 모르는 것

• 평문 : 지금부터 해독하려고 하는 내용
• D : 개인 키 중 적어도 D는 모름
• 키타 : 키 쌍을 만든 p, q, L을 모름

 

 

 

암호문으로 부터 평문 구하기

 

암호문 = (평문)^E mod N

 

• 위의 평문을 구하려면 이산 대수 문제를 풀어야 함
• 이산 대수 문제는 매우 곤란
• 현재까지 아직 이산 대수를 구하는 빠른 방법을 알지 못함

 

 

 

전사 공격

• D의 후보가 되는 수를 순서대로 모두 시도해서 복호화 해본다.
• D의 비트 수가 크면 클수록 어려워진다.
• 비트 수가 충분히 크면 전사공격으로 수 D를 찾아내는 것은 현실적으로는 불가능
• RSA에서는 p와 q의 비트 수로서 512 비트 이상을 사용
• N은 1024 비트 이상을 이용
• E나 D는 N과 같은 정도의 크기로 할 수 있으므로 D를 찾으려면 1024 비트 이상의 전사공격이 필요
• 현실적으로 불가능

 

 

 

E와 N으로 부터 D 구하기

 

E × D mod L = 1

 

• L은 LCM(p-1, q-1)이므로 E로부터 D를 계산할 때는 p와 q를 사용
• 암호해독자는 p와 q를 전혀 모름
• 해독자는 D를 구할 수 없음
• RSA의 안정성을 위해 소수 p와 q를 암호 해독자가 모르게 해야 함

 

 

 

N의 소인수 분해

• N = p × q라는 관계식을 공격자는 알고 있고, N은 공개되어 있다.
• N으로 부터 p와 q를 구할 수 없는 것일까?
• p와 q는 소수이기 때문에 N으로부터 p와 q를 구한다는 것은 자연수 N을 소인수분해하는 것

 

 

소인수 분해

• 큰 수를 고속으로 소인수 분해 할 수 있는 방법이 발견되면 RSA를 깰 수 있다.
• 그러나, 현재 큰 수의 소인수 분해를 고속으로 행하는 방법은 아직 발견되지 않았다.
• 소인수분해를 간단히 수행하는 방법이 존재하는지의 여부도 아직 모른다.

 

[참고] 양자 컴퓨터

 

• RSA 암호체계의 안정성은 큰 숫자를 소인수 분해하는 것이 어렵다는 것에 기반을 두고 있다. 그러므로 큰 수의 소인수 분해를 획기적으로 빠르게 할 수 있는 알고리즘이 발견되다면, 이 암호 체계는 가치가 떨어지게 된다.
• 1993년 피터 쇼어는 쇼어 알고리즘을 발표하여, 양자 컴퓨터를 이용하여 임의의 정수를 다항 시간 안에 소인수 분해 하는 방법을 발표하였다. 따라서, 양자 컴퓨터가 본격적으로 실용화되면 RSA 알고리즘은 무용지물이 될것이다. 그러나, 양자 컴퓨터가 이 정도 수준으로 실용화되려면 아직 여러 해가 더 필요할 것으로 보인다.

 

 

p와 q 추측하기

• 소인수분해를 하지 않아도 p와 q가 암호 해독자에게 알려질 가능성은 있다.
• p와 q는 의사난수 생성기도 생성하기 때문에 의사난수 생성기의 품질이 나쁘면 p와 q를 암호 해독자가 추측할 수 있다.
• 난수 생성기가 강력해서 암호 해독자가 추측할 수 없어야 한다.

 

 

기타 공격

• N을 소인수분해 해서 p와 q를 구할수 있으면 D를 구할 수 있다.
• "D를 구하는 것"이 "N을 소인수분해 하는 것"과 수학적 같은지 아닌지가 증명되어 있지 않다.
• N을 소인수분해 하지 않아도(p와 q를 몰라도) E와 N으로 부터 D를 구하는 방법이 있을 수 있다.

 

 

 

중간자 공격(Man-In-The-Middle Attack, MITM Attack)

• RSA를 해독하는게 아니다.
• 기밀성을 침해하는 공격
• 공격자 맬로리가 송신자와 수신자 사이에서 송신자에 대해서는 수신자 처럼, 수신자에 대해서는 송신자처럼 행세하는 공격

 

중간자 공격 절차

멜로리에 의한  MITM  공격

 

① 앨리스는 밥의 공개 키 요청 ② 맬로리는 앨리스의 요청을 도청 ③ 밥은 자신의 공개 키(KB(pub))를 앨리스에게 전송 ④ 맬로리는 밥의 메일이 도달하지 못하도록 하고, 밥의 공개 키를 보존 ⑤ 맬로리는 자산의 공개 키(KM(pub))를 밥의 공개키라고 속여서 앨리스에게 전송 ⑥ 앨리스는 자신의 메시지(P)를 밥의 공개 키(실은 맬로리의 공개 키)로 암호화(C=E(KM(pub), P)) ⑦ 앨리스는 암호화한 메시지(C)를 밥에게 전송 ⑧ 맬리로는 앨리스의 암호 메일을 갈취해서 자신의 개인키(KM(pri))로 복호화(P=D(KM(pri), C) 하고 평문(P)을 확보 ⑨ 맬로리는 앨리스 행세를 하며, 위조 메일(P')을 만들고, 위의 단계 ④에서 보존해 둔 밥의 공개 키(KB(pub))를 써서 위조 메일을 암호화(C=E(KB(pub), P')하여 밥에게 전송 ⑩ 밥은 받은 암호 메일(C')을 자신의 개인 키로 복호화하고 메일(P')을 읽게 된다.

 

 

 

 

---

6. 선택 암호문 공격

 

암호 공격 모델

• 암호문 단독 공격(Ciphertext-Only Attack)
• 알려진 평문 공격(Known-Plaintext Attack)
• 선택 평문 공격(Chosen-Plaintext Attack)
• 선택 암호문 공격(Chosen-Ciphertext Attack)

 

복호 오라클(Decryption Oracle)

• 임의의 데이터를 송신하면 그것을 암호문으로 간주하고 회신 해주는 서비스

 

선택 암호문 공격(Chosen Ciphertext Attack)

• 복호 오라클 공격을 공격자가 이용할 수 있다고 가정한 공격
• 공격 대상인 암호문은 제외

 

복호 오라클 서비스의 의미

• 넌센스처럼 보이지만
• 실제 네트워크에서 오류메시지 반환을 악용하는 공격
• 위조 암호문을 여러 차례 전송하여 반환된 오류 메시지나 타이밍 정보를 활용해 평문을 추측
• RSA의 경우 선택암호문 공격으로 약간의 정보 취득 가능

 

 

RSA-OAEP(Optimal Asymmetric Encryption Padding)

 

RSA-OAEP 배경

 

RSA 암호의 안전성: N의 소인수분해 어려움

• 2048비트 이상 이용 권고

 

공격 예

• 설문조사와 같은 평문의 종류가 적은 경우
• 공격자가 자신이 암호화한 값과 해당 대상 암호문의 단순비교로 해독 가능
• 공격에 대한 해결책 암호화마다 평문, 랜덤값, 이와 더불어 평문에 대해서도 매번 다른 암호문이 생성되는 확률적 알고리즘을 이용하는 방법 사용: RSA-OAEP

 

RSA-OAEP(Optimal Asymmetric Encryption Padding)

 

• RSA를 개량해서 선택암호문공격으로부터 안전하게 만든것
• 암호문에 인증 과정을 추가한 방법
• 평문 해시 값과 정해진 개수의 0 등으로 만들어진 인증정보를 평문 앞에 추가한 뒤, 그 후에 RSA로 암호화 한다.
• 복호화시 RSA로 복호화한 후 선두에 올바른 인증 정보가 나타나지 않으면 오류로 판정(사용 예: SSH)

 

 

복호화시 올바른 인증 정보가 나타나지 않으면 오류로 판정

RSA-OAEP

 

• RSA가 트랩도어 치환(해시)이라면, H와 G가 완변한 해시함수일 때 RSA-OAEP는 선택 암호문 공격(CCA)에 안전
• H와 G에는 SHA-256를 사용