발음하기도 어려운 Daniel Bleichenbacher("(블)라이헨바허"라고 읽는듯함)가 2006년에 구현에서의 RSA signature forgery 취약점을 발견하였다. 이 문서는 다음 링크를 바탕으로 만들어졌다.
https://www.ietf.org/mail-archive/web/openpgp/current/msg00999.html
이 공격은 \(e = 3\)일 때만 유효하다.
00 01 FF FF FF ... FF 00 ASN.1 HASH
signature는 위 형태로 되어있다. 여기서 구현상의 오류로, HASH 뒤에 아무런 데이터도 없는지 체크하지 않는다. 즉 공격자는 HASH 뒤의 값을 적절히 조절해 위 signature값의 세제곱근을 찾아낸 뒤 fake signature를 만들어낼 수 있다.
이를 이해하기 위해 알아둬야 할 수학적 지식이 있다. 이진수의 \(p\)번째 bit부터 \(q\)번째 bit까지 모두 1일 때, 숫자는 다음과 같이 표현 가능하다. (단, 최하위비트는 0번째 비트이다.)
\[ 2^{p+1} - 2^{q} \]
예를 들어 0111 1110\(_{2}\)은 \( 2^{7} - 2^{1} \)다.
다시 위에서 한 얘기로 돌아가자. \(D\)를 우리가 원하는 메시지인 00 + ASN.1 + HASH로 두자. key가 3072bit일 때, \(D\)를 오른쪽에서 2072번째 bit에 배치하면, 1의 시작 bit는 3057번째 bit이고(0x0001ffffff~~), 끝나는 비트에 대한 제한은 없으므로(FF의 길이에 대한 제한이 없음) \(q\)번째 bit라 두면, signature의 수식이 다음과 같다.
\[ 2^{3057} - 2^{q} + D\times 2^{2072} + \mbox{garbage} \]
garbage는 HASH 뒤에 나타날 모든 값을 의미한다. 위에서 얘기했던대로 HASH 뒤에 나타나는 garbage에 대한 값을 확인하지 않기 때문에 garbage는 어떠한 값이든 상관없다. 이 때, D의 길이는 SHA-1 hash일 때 288bit이다. 따라서 \( N = 2^{288} - D \)로 잡으면 위 식은 다음과 같이 변한다.
\[ = 2^{3057} -2^{q} + (2^{288} - N)\times 2^{2072} + \mbox{garbage} \]
\[ = 2^{3057} -2^{q} + 2^{2360} - N\times 2^{2072} + \mbox{garbage} \]
이 된다. 이 값은 어떤 수의 세제곱이 되어야한다(\(e=3\)이기 때문). 즉, 어떤 수를 \(A-B\)로 두면 위 signature에 대한 식은 \( (A-B)^{3} \)꼴로 표현될 수 있다. 여기서 \(2^{2360}\)을 소거하기 위해 \(q=2360\)으로 잡는다.
\[ (A-B)^{3} = 2^{3057} - N\times 2^{2072} + \mbox{garbage} \]
\( (A-B)^{3} = A^{3} -3A^{2}B +3AB^{2} -B^{3}\)임을 이용하여 \(A = 2^{3057/3} = 2^{1019}\)로 정의하면
\[ (A-B)^{3} = 2^{3057} -3\times 2^{2038}B +3AB^{2} -B^{3} = 2^{3057} - N\times 2^{2072} + \mbox{garbage} \]
여기서 \( 3AB^{2} -B^{3} = \mbox{garbage} \)로 없애버리고 식을 정리하면
\[ -3\times 2^{2038}B = -N\times 2^{2072} \]
\[ B=\frac{N\times 2^{34}}{3}\]
가 나온다. 따라서 \(A=2^{2019}, B=\frac{N\times 2^{34}}{3}\)로 잡으면, \( (A-B)^{3} \)는 signature 형태가 나오게 된다!
Daniel Bleichenbacher는 이렇게 매우 쉽게(?) 연필과 종이만으로(pencil and paper) forgery attack이 가능하다고 했다.
이를 통해 picoCTF 2014의 Revenge of the Bleichenbacher라는 문제를 풀어보자.
CommandServer라는 jar파일이 주어진다.
CommandServer.jar
이 프로그램은 서버를 돌려 명령어를 받고 이 명령어에 대한 signature를 받아서 verifySignature()를 통해 signature가 유효한지 판단한다. paramString1은 명령어이고, paramString2는 signature이다.
public boolean verifySignature(String paramString1, String paramString2) {
String str1 = sha1(paramString1);
BigInteger localBigInteger1 = new BigInteger(paramString2, 16);
BigInteger localBigInteger2 = localBigInteger1.modPow(new BigInteger("3"), N);
String str2 = localBigInteger2.toString(16);
while (str2.length() < 768) {
str2 = "0" + str2;
}
if ((str2.indexOf("0001ffffffffff") == 0) && (str2.length() == 768) &&
(str2.contains(str1))) {
for (int i = str2.indexOf("f"); i < str2.indexOf(str1) - 2; i++) {
if (str2.charAt(i) != 'f') return false;
}
return (str2.charAt(str2.indexOf(str1) - 2) == '0') && (str2.charAt(str2.indexOf(str1) - 1) == '0');
}
return false;
}
이 함수에서는 다음과 같은 동작을 한다.
이를 통해 picoCTF 2014의 Revenge of the Bleichenbacher라는 문제를 풀어보자.
1. paramString2를 세제곱해서 N(key)로 나머지를 구한다(str2).
2. str2가 0001ffffffffff로 시작하는지, 길이가 768글자인지, str1의 hash를 포함하는지 확인한다.
3. HASH의 앞앞글자까지 f인지 확인한다.
4. HASH의 앞글자와 앞앞글자가 0인지 확인한다.
예를 들어, 명령어 open의 signature의 형태는 다음과 같아야 한다.
00 01 FF FF FF ... FF 00 5fc7e38bffe00ca46add89145464a2eaf759d5c2
FF가 끝나고 00이 나와야 하며, 그 뒤로 open의 SHA-1 hash가 이어져야한다. 따라서 우리가 원하는 \(D\)는 \(D=\mbox{0x005fc7e38bffe00ca46add89145464a2eaf759d5c2}\)이고, 이는 168bit이므로 \(N=2^{168}-D=373597607363060102729912695217882050654491120118334\)가 나온다. 이를 비롯해 \(A-B\)를 구하는 과정은 다음과 같다.
import hashlib
A = 2**1019
D = '00' + hashlib.sha1('open').hexdigest()
N = 2**(len(D)*4) - int(D, 16)
B = N*2**34/3
sig = hex(A-B).lstrip('0x').rstrip('L')
print sig
결과
7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeab2a5fda0fffd566308e7cb6c5c5db83e3f477c7ad55555556
이 값을 verifySignature() 함수에 넣어보자. 이를 위해 새로운 Main.java파일을 만든다.
import java.security.MessageDigest;
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
private static final BigInteger N = new BigInteger("c5ddc7decb1beede4ebb96742e4279eb120b9c8b44472c0d0bb39da95a10cf72b630dbea181eeda65772779de8b6af53f2b0c5c3eccae2ef7a349b66637345f1cc0dec4d63550206688751e49da001b2f901cf39ebb1758bae0a89a3a4f8342fa26283f802ce6df144113a2abe075497d373435f80aa96bdf1ea500f58eea6bffb28add63c9d337dacf3bbf81996c7b6b9ac532007010acedb0714a547486c78ca162a0a85c643ce774b2805bd294435d262fb390adce055b971396c0363bb5f7aa409f5c223fa9c211945cb6be7a8df23a3357257a11bfe4bd983799d975e9ba337e928c33a7cd9638c5f4553b2a263233442677f848e948ccc4470a5a5bc16682b3a24188398389a079096d28588f03d01b7bfa6cce9a829e2f5c1b1cc785e891ffa89d63607f48473126f99aca203e0c2e77f21a35b6d6c8816c0650715144ff148d9c60f81bfacbfc5ef879a07bb6cd8e12476803006cc7ae25e8faafa4ee52dac698d7927092d10c4fb748dea6b3dd62a3588cf315f54216689877f3f0d", 16);
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("cmd: ");
String s1=sc.nextLine();
System.out.print("signature: ");
String s2=sc.nextLine();
System.out.println("Result: "+verifySignature(s1, s2));
}
public static String sha1(String paramString) {
try {
MessageDigest localMessageDigest = MessageDigest.getInstance("SHA-1");
byte[] arrayOfByte = localMessageDigest.digest(paramString.getBytes("UTF-8"));
StringBuffer localStringBuffer = new StringBuffer();
for (int i = 0; i < arrayOfByte.length; i++) {
String str = Integer.toHexString(0xFF & arrayOfByte[i]);
if (str.length() == 1) localStringBuffer.append('0');
localStringBuffer.append(str);
}
return localStringBuffer.toString();
}
catch (Exception e) { return null; }
}
public static boolean verifySignature(String paramString1, String paramString2)
{
String str1 = sha1(paramString1);
BigInteger localBigInteger1 = new BigInteger(paramString2, 16);
BigInteger localBigInteger2 = localBigInteger1.modPow(new BigInteger("3"), N);
String str2 = localBigInteger2.toString(16);
while (str2.length() < 768) {
str2 = "0" + str2;
}
System.out.println("str2: "+str2);
if (str2.indexOf("0001ffffffffff") != 0){
System.out.println("1:"+str2.indexOf("0001ffffffffff"));
return false;
}
else if(str2.length() != 768) {
System.out.println("2");
return false;
}
else if(!str2.contains(str1)) {
System.out.println("3");
return false;
}
for (int i = str2.indexOf("f"); i < str2.indexOf(str1) - 2; i++) {
if (str2.charAt(i) != 'f') {
System.out.println("4");
return false;
}
}
return (str2.charAt(str2.indexOf(str1) - 2) == '0') && (str2.charAt(str2.indexOf(str1) - 1) == '0');
}
}
CommandServer.jar에서 코드를 복사-붙여넣기 했었는데 컴파일 에러가 떠서 exception handle하는 부분을 수정했다.
이를 돌려서 cmd값과 signature값을 input으로 줬더니 true가 나온다.
이렇게 RSA signature forgery를 수행할 수 있다.
[+]
cryptography에 대한 지식이 거의 없어서 이해하는데 꽤나 오래걸렸네요.
설명이 부자연스럽거나 개념이 이상한 부분이 있다면 지적해주면 감사하겠습니다~!
