RSA 공격법

RSA 공격법에 대해 한번도 정리해놓은적이 없어서... CTF 문제로 RSA가 나올때마다 헤매게 되어서 한번 정리해두는게 좋을 것 같다는 생각이 들어서 이렇게 정리하게 되었다.

공격법에는 여러가지가 있는데, 일단 대충 정리하면 아래와 같다.

Sage : https://sagecell.sagemath.org/

http://sage.skku.edu/

http://matrix.skku.ac.kr/sage/

▶ 개인키 유출

p,q,ϕ(n),d 중 단 하나만이라도 노출된다면 나머지 키들을 취득할 수 있다.

이건 당연한 것이, 원래 n=pq에서 n을 구하고 나면 p,q는 파기되어야하나, 이 p,q를 구할 수 있다면 역으로 모두 다 구할 수 있게된다.

확장된 유클리드 호제법이나 유클리드 호제법을 사용하면 간단.

▶ 소인수분해

n을 소인수분해할 수 있다면 위의 개인키 유출과 같다.

아래는 소인수분해 DB로 DB에 이미 등록되있는 소인수분해값이라면 찾아서 알려준다.

FatorDB : http://factordb.com/    

ECM : https://www.alpertron.com.ar/ECM.HTM

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

줄여서 CCA라고 부른다. RSA가 갖는 "곱셈에 대한 준동형사상 (Homomorphism) 성질"을 이용한 공격이라고 한다.

RSA 같은 키로 생성된 서로 다른 암호문 두 개를 곱하면, 평문 두개의 곱을 암호화한 것과 그 결과가 같다.

Textbook RSA에서 많이 쓰이는 공격법이다. (Textbook RSA와 일반 RSA 차이)

Textbook RSA에서는 메세지의 서명과 그 확인에 많이 쓰이기 때문에, 이를 이용해서 내가 서명하지않은 메세지의 평문또한 복구가능하다.

말로만으로는 어려우므로 밑에 수식으로 다시 표현하겠다. (https://asecuritysite.com/encryption/c_c)

여기서 우리는 C를 알고 있고, 임의로 r^e를 만들어 C'를 만들고 C'에 대한 서명(d)을 할 수 있다. 

그렇다면 우리가 얻게 되는 값은 평문 M*r 이 되고, r은 우리가 만든 값이므로 M을 구할 수 있다.

▶ 순환 공격(Cyclic Attack)

평문이 나올 때까지, 암호문을 계속해서 암호화하는 공격이다. 이 공격은 결국 암호문을 해독하지만 소인수분해와 동일한 복잡도를 가진다.

RSA는 모듈러 연산을 사용하기 때문에 평문 집합과 암호문 집합이 동일하다.

예) mod 4를 사용하는 경우 평문 집합 {1, 2, 3} , 암호문 집합 {1, 2, 3}

암호문은 평문에 대해 1:1 대응이기 때문에 평문에 대한 암호문은 반드시 존재한다.

그러므로 계속 암호화하다보면 언젠가는 다시 평문이 나오게 되어있다.

하지만 n은 보통 굉장히 크므로... 현실적으로는 불가능하다.

▶ 잘못된 암호화 공격(Faulty Encryption)

공격자 Malory가 Alice와 Bob이 사용하는 통신 채널에 접속할 수 있다면 Malory는 전송되는 모든 것을 들을 수 있고 전송되는 것을 변경할 수도 있다.

Alice는 개인적으로 Bob에게 말하기를 원하지만 공개키를 알지 못한다. Alice는 Bob에게 메일을 보내 공개키를 요청한다.

그러나 전송 중에 Malory는 Alice의 공개키를 볼 수 있고 Bob의 공개 지수에서 (e, n)을 (e', n)으로 변경한다.

Alice는 잘못된 키를 받고, 준비된 메시지를 암호화하여 Bob에게 보냅니다. (Malory도 가져옵니다). 물론 잘못된 키가 사용 되었기 때문에 Bob은 해독 할 수 없습니다. 그래서 그는 Alice에게 이를 알리고 Bob이 자신의 공개키를 다시 보내는 것으로 시작하여 다시 시도하기로 동의합니다. 

이번에 Malory는 방해하지 않는다. Alice가 메시지를 다시 보내고 이번에는 올바른 공개 키로 암호화합니다.

Malory에는 이제 두 개의 암호문이 있습니다. 하나는 오류 지수로 암호화되고 다른 하나는 올바른 암호문으로 암호화됩니다. 

이제 공격자 Malory는 모듈러 N과 공개지수 e를 모두 알고 있습니다. 따라서 Alice가 두 암호문 모두 정확히 암호화했다고 가정할 때

이제 우리는 Common Modulus Attack 을 사용할 수 있습니다.

http://www.members.tripod.com/irish_ronan/rsa/attacks.html

▶ 유사소수

간단히 말해 n이 유사소수이면 소인수분해하기 쉽다는 것이다. 링크로 대체

Fermat factorization 공격

페르마소수(Fermat number)를 사용하게 되면 소인수분해가 매우 쉬워져서, N을 소인수분해하는데 걸리는 시간이 매우 짧아

p,q를 알 수 있고, 개인키를 얻을 수 있다.

예) [MeepwnCTF 2018] Old School (Fermat's factorization attack)

예) https://ctftime.org/task/6295

https://xerxes-break.tistory.com/397?category=679888

위 롸업에서 PLUS팀이 part1에서 페르마소수 인수분해 사용

(p/q의 값이 1에 근사하면 주어진 RSA 암호화 방식은 Fermat factorization 공격에 취약)

=> https://xerxes-break.tistory.com/450

▶ p-1 공격, 이차 체

 링크로 대체

▶ 개인키 부분 취득

간단히 설명하면, 개인키의 일부분만 찾을 수 있어도 RSA를 털 수 있다는 뜻

이런 문제가 나온다면 공부하게 되겠지

▶ 부채널 공격

(1) 시간차 공격(Timing Attack)

(2) 전력차 공격(Power Analysis Attack) 

부채널 분석(Side-Channel Analysis) 또는 부채널 공격(Side-Channel Attack)이란 과거 암호 해독 기법과는 달리 암호 연산 수행 시 장비에서 발생되는 전력 또는 전자파와 같은 정보를 이용해 비밀키를 찾는 방법이다. 

일반적으로 시간공격 (TA, Timing Attack), 전자기누출공격 (EMA, ElectroMagnetic emission Attack) 그리고 전력분석 공격(PA, Power analysis Attack) 등으로 나눌 수 있으며, 수집한 전력 또는 전자파의 일반적인 특성 또는 통계적인 분석기법을 활용한다. 

특히, 전력분석 공격은 하드웨어에서 ‘0’, ‘1’을 처리하는 소비되는 전력이 서로 다르다는 점을 이용하여, 장비에서 암호 알고리즘이 실행되는 동안의 소비 전력을 분석해 비밀키에 대한 정보를 얻어 내는 방법이다. 

이는단순 전력 분석(SPA, Simple Power Analysis), 차분 전력 분석(DPA, Differential Power Analysis) 및 상관 전력분석(CPA, Correlation Power Analysis) 등으로 나뉜다.

예시) 2016 암호경진대회 6번

공격자 Malory가 Alice와 Bob이 사용하는 통신 채널에 접속할 수 있다면 Malory는 전송되는 모든 것을 들을 수 있고 전송되는 것을 변경할 수도 있다.

▶ 낮은 지수 공격(Low Exponent Attack)

공개키 e의 값이 매우 작을 때 사용하는 공격법 - 출처(https://en.wikipedia.org/wiki/Coppersmith%27s_attack)

컴퓨터 모듈러 연산의 속도를 위하여 e값으로 페르마 소수 F0, F2, F4를 사용하는 경우가 많다. 

e값이 작고 평문의 길이가 매우 짧을 경우, 보통 n의 값이 매우 크기 때문에 암호문 C가 모듈러 연산에 걸리지않거나 몇 번걸리지않는 경우가 있다. 

그래서 이 경우 C값을 그냥 e 거듭제곱근을 구해서 평문을 복호화해 낼 수가 있다.

예) [UIUCTF 2018] Hastad

ex) 공격법 python의 gmpy모듈을 이용

import gmpy를 하면 result, bool = gmpy.root( num, k)를 쓸수가 있는데; 

이게 num를 k제곱근한 값을 result에 저장하고 bool에 성공여부를 0과 1로 저장한다.

import gmpy2, gmpy2.root도 있다.

위 예시의 문제의 출제의도는 Hastad Attack이였으나, N값이 C값에 비해 매우 크고, e=3이였기 때문에 세제곱근을 구하는 것을 통해 평문을 그냥 복구할 수 있었다.

▶ 위너 공격(Wiener's attack)

앞서 이야기한 낮은 지수 공격과 비슷한 느낌의 공격으로 Wiener's attack이 있다. - https://en.wikipedia.org/wiki/Wiener%27s_attack

Let ${\displaystyle \ N=pq}$ with ${\displaystyle \ q<p<2q}$. Let ${\displaystyle d<{\frac {1}{3}}N^{\frac {1}{4}}}$.
Given ${\displaystyle \left\langle N,e\right\rangle }$ with ${\displaystyle ed\equiv 1\ (\mathrm {mod} \ \varphi (N))}$, the attacker can efficiently recover ${\displaystyle d}$.

간단하게 위와 같다. 즉, 개인키 d가 작다면 이를 쉽게 복구할 수 있다는 것이다.

예시로는 PlaidCTF 2015 RSA 문제나 검색해보면 꽤 많은 문제들이 나온다.

▶ Common Modulus Attack

공격자가 두 수신자의 동일한 메시지 m의 두 암호문 c1, c2 와 수신자의 공개키 e1, e2가 서로소임을 알고 있다.

▶ 하스타드 공격 (Hastad's Broadcast Attack)

Coppersmith 정리를 이용한 첫 번째 응용, Hastad가 제안했던 알고리즘을 개선한 내용

Bob은 평문 M을 암호화하여 P1,P2,…,Pk 라고 하는 여러명에게 동시에 전송한다.

각 P은 각기 RSA 공개키를 갖고있다. 그리고 평문M이 모든 Ni보다 작다고 하자. 

이런 상황에서 Oscar는 Bob이 모르게 이들의 통신을 도청할 수 있고, k개의 암호문을 가로 챌 수 있다. 

편의상, 모든 공개키 ei가 3이라고 하자. 이 경우, k≥3이면, Oscar는 암호문으로부터 평문 M을 복호화 할 수 있다. 

즉, Oscar가 세 개의 암호문 C1,C2,C3를 얻었다고 하자. 여기서, C1=M^3 modN1, C2=M^3 modN2, C3=M^3 modN3 이다. 

그리고, Oscar가 Ni를 소인수 분해하지 못하게 하기 위해, 서로 다른 i, j 에 대해 gcd(Ni,Nj)=1라고 가정할 수 있다. 

그러면, CRT을 이용해, C'=M^3 modN1N2N3을 만족하는 원소 C'를 구할 수 있다. 가정에서 M이 모든 Ni보다 작다고 했기 때문에 M^3 < N1N2N3이고 따라서 C'=M3 이 성립한다. 따라서, Oscar는 C'의 삼제곱근을 실수에서 연산하면, M을 얻을 수 있다. 일반적으로, 모든 공개키(public exponent) ei가 같다고 하고 "k≥ei" 이기만 하면 Oscar는 평문 M을 복호화할 수 있다. 이 공격법은 공개키 e가 작은 경우에 한한다. 

정리:

• e=3, {n1, n2, n3}에 대해 동일한 평문 M을 3개 전송하였을 때

• c1, c2, c3가 존재한다. (각각 (n1,e), (n2,e), (n3,e)로 암호화) 

• 중국인의 나머지정리(CRT)를 이용하여 c^t == x (mod n1n2n3)를 계산

• m^3 < n1n2n3 이기 때문에 c^t=m^3

예시)

[UIUCTF 2018] Hastad

2016 국가암호공모전 II-A 분야 1번문제

공격 python 코드

import gmpy2
gmpy2.get_context().precision = 4096
 
from binascii import unhexlify
from functools import reduce
from gmpy2 import root
import gmpy
 
# Hastad's Broadcast Attack
# https://id0-rsa.pub/problem/11/
 
# Resources
# https://en.wikipedia.org/wiki/Coppersmith%27s_Attack
# https://github.com/sigh/Python-Math/blob/master/ntheory.py
 
EXPONENT = 3
 
CIPHERTEXT_1 = "ciphertext.1"
CIPHERTEXT_2 = "ciphertext.2"
CIPHERTEXT_3 = "ciphertext.3"
 
MODULUS_1 = "modulus.1"
MODULUS_2 = "modulus.2"
MODULUS_3 = "modulus.3"
 
 
def chinese_remainder_theorem(items):
    # Determine N, the product of all n_i
    N = 1
    for a, n in items:
        N *= n
 
    # Find the solution (mod N)
    result = 0
    for a, n in items:
        m = N // n
        r, s, d = extended_gcd(n, m)
        if d != 1:
            raise "Input not pairwise co-prime"
        result += a * s * m
 
    # Make sure we return the canonical solution.
    return result % N
 
 
def extended_gcd(a, b):
    x, y = 0, 1
    lastx, lasty = 1, 0
 
    while b:
        a, (q, b) = b, divmod(a, b)
        x, lastx = lastx - q * x, x
        y, lasty = lasty - q * y, y
 
    return (lastx, lasty, a)
 
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1:
        return 1
    while a > 1:
        q = a // b
        a, b = b, a % b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0:
        x1 += b0
    return x1
 
 
def get_value(filename):
    with open(filename) as f:
        value = f.readline()
    return int(value, 16)
 
if __name__ == '__main__':
    C1 = get_value(CIPHERTEXT_1)
    C2 = get_value(CIPHERTEXT_2)
    C3 = get_value(CIPHERTEXT_3)
    ciphertexts = [C1, C2, C3]
 
    N1 = get_value(MODULUS_1)
    N2 = get_value(MODULUS_2)
    N3 = get_value(MODULUS_3)
    modulus = [N1, N2, N3]
    
    C_M = [(c,m) for c,m in zip(cipher, modulus)]
 
    C = chinese_remainder_theorem(C_M)
    M = int(root(C, 3))
 
    M = hex(M)[2:]
    print(unhexlify(M).decode('utf-8'))

원본 : https://github.com/aaossa/Computer-Security-Algorithms/blob/master/11%20-%20H%C3%A5stad's%20Broadcast%20Attack/hastads-broadcast-attack.py#L7

▶ LSB Oracle Attack

CTF에 의외로 자주나오는 유형. 평문을 encrypt한 lsb값을 출력하는 oracle이 있을때

이 방법을 이용해서 문제를 풀 수 있다.

ex) 

https://xerxes-break.tistory.com/448

https://xerxes-break.tistory.com/449

▶ Coppersmith’s attack

자세한 내용 - 원문 - https://en.wikipedia.org/wiki/Coppersmith%27s_attack

Franklin-Reiter related-message attack

Coppersmith’s short-pad attack

참고할만한 블로그 글 - https://www.cryptologie.net/article/222/implementation-of-coppersmith-attack-rsa-attack-using-lattice-reductions/

Stereotyped messages

For example if you know the most significant bits of the message. You can find the rest of the message with this method.

The usual RSA model is this one: you have a ciphertext c a modulus N and a public exponent e. Find m such that m^e = c mod N.

Now, this is the relaxed model we can solve: you have c = (m + x)^e, you know a part of the message, m, but you don't know x. For example the message is always something like "the password today is: [password]". Coppersmith says that if you are looking for N^1/e of the message it is then a small root and you should be able to find it pretty quickly.

간단히 말하면, e가 매우 작고 (e=3정도) 평문 메세지 M을 알고 있고, 그 M의 뒷부분이 아주 조금 변하는 정도라면 이 공격을 통해 M을 구할 수 있다는 공격이다. 

예시문제 : 

[MeePwnCTF 2018] bazik

▶ 오류 주입 공격(몽고메리알고리즘[Montgomery Ladder])

Montgomery Ladder 지수승 알고리즘을 이용하여 서명(S=m^d mod N)가 수행되는 동안 오류 주입 공격을 통해 오류가 여러개의 서명 값을 이용하여 비밀키 d를 복구하는 것.

Copper

https://asecuritysite.com/encryption/copper

https://medium.com/asecuritysite-when-bob-met-alice/so-what-was-the-problem-with-the-estonian-id-system-and-tpms-1ef02a9bde7f

[Back] With the ROCA (Return of the Coppersmith Attack) vulnerability an RSA private key can be recovered from the knowledge of the public key [article]. It has the CVE identifier of CVE-2017-15361. The vulnerability related to the Infineon RSA library on the Infineon Trusted Platform Module (TPM) firmware. It affected BitLocker with TPM 1.2 and YubiKey 4. In this case we calculate the prime number with Prime=k×M+(65537amodM)$Prime=k\times M+({65537}^a\mathrm{mod}M)$: