PlaidCTF2014 Write Up: rsa(forensic450)

Sebenarnya kami tidak berhasil menyelesaikan challenge RSA ini tepat waktu, jadi kami tidak mendapatkan poin. Tapi karena kami sudah berhasil menyelesaikan challengenya, jadi kami tuliskan pembahasannya.

Inti dari solusinya adalah berdasarkan paper: "Reconstructing RSA Private Keys from Random Key Bits"

http://cseweb.ucsd.edu/~hovav/papers/hs09.html

Ada source code yang bisa didownload di situ, tapi sourcenya perlu dimodifikasi. Berikut ini adalah modifikasi yang saya lakukan:

	diff -ruN rsabits-orig/rsa.C rsabits/rsa.C
	--- rsabits-orig/rsa.C 2014-04-15 10:09:53.406244277 +0700
	+++ rsabits/rsa.C 2014-04-15 10:15:55.666047590 +0700
	@@ -40,6 +40,8 @@
	// C:
	#include <sys/types.h>
	+#include <stdio.h>
	+#include <string.h>
	#include <unistd.h>
	#include <stdlib.h>
	#include <fcntl.h>
	@@ -47,9 +49,12 @@
	#include <sys/time.h>
	// *shudder* STL:
	#include <iostream>
	+#include <sstream>
	#include <fstream>
	#include <iomanip>
	#include <queue>
	+#include <vector>
	+#include <string>
	// NTL:
	#include <NTL/ZZ.h>
	#include <NTL/LLL.h>
	@@ -148,6 +153,150 @@
	file >> priv.dq1;
	}
	+std::string hextab = "0123456789abcdef";
	+
	+int hexval(char c)
	+{
	+ return hextab.find(c);
	+}
	+
	+//we need strip 0 in case it is corrupted
	+void read_corrupted_value(vector<string> &lines, unsigned int &start, ZZ &val, ZZ &mask, bool stripzero)
	+{
	+ std::string hex;
	+
	+ while (start < lines.size()) {
	+ if (lines[start][0]!=' ') {
	+ break;
	+ }
	+ std::string line = lines[start].substr(4);
	+ //-1: ignore last ':'
	+ for (unsigned int i = 0; i < line.size()-1; i+=3) {
	+ std::string part = line.substr(i, 2);
	+ hex = part + hex;
	+ }
	+ start++;
	+ }
	+
	+ if (stripzero) {
	+ hex = hex.substr(0, hex.size()-2);
	+ } else {
	+ //if it ends with 00
	+ if (hex[hex.size()-1]=='0' && hex[hex.size()-2]=='0') {
	+ hex = hex.substr(0, hex.size()-2);
	+ }
	+ }
	+
	+ vector<unsigned char> bytes;
	+
	+ printf("hex = %s\n", hex.c_str());
	+ int current_bit = 0;
	+
	+ clear(mask);
	+
	+ for (unsigned int i =0; i < hex.size(); i+=2) {
	+ char c1 = hex[i];
	+ char c2 = hex[i+1];
	+ if (c1!=' ' && c2!=' ') {
	+ unsigned char v = hexval(c1) << 4 | hexval(c2);
	+ bytes.push_back(v);
	+ for (int j = 0; j < 8; j++) {
	+ SetBit(mask, current_bit + j);
	+ }
	+ } else if (c1==' ' && c2==' ') {
	+ bytes.push_back(0);
	+ } else if (c1==' ') { //eg: ' f'
	+ bytes.push_back(hexval(c2));
	+ //only first 4 bits known
	+ for (int j = 0; j < 4; j++) {
	+ SetBit(mask, current_bit + j);
	+ }
	+ } else { //c2 ==' ', eg: 'f '
	+ bytes.push_back(hexval(c1)<<4);
	+ //only last 4 bits known
	+ for (int j = 4; j < 8; j++) {
	+ SetBit(mask, current_bit + j);
	+ }
	+
	+ }
	+ current_bit += 8;
	+ }
	+
	+ ZZFromBytes(val, &bytes[0], bytes.size());
	+
	+// cout << val;
	+// printf("\n");
	+// cout << mask;
	+// printf("\n");
	+
	+}
	+
	+void
	+read_corrupted_file(char *filename,
	+ rsa_pub &pub,
	+ rsa_priv &priv,
	+ int &bits,
	+ rsa_mask &mask)
	+{
	+ ifstream file(filename);
	+ if (!file)
	+ {
	+ cerr << "Error: can't open input file " << filename << endl;
	+ exit(1);
	+ }
	+ vector<string> lines;
	+ ZZ dummymask;
	+
	+ while(!file.eof()) {
	+ std::string tmp;
	+ getline(file, tmp);
	+ lines.push_back(tmp);
	+ }
	+
	+ unsigned int start = 0;
	+ //too lazy to parse
	+ //Private-Key: (N bit)
	+ if (lines[start].find("1024")!=string::npos) {
	+ bits = 1024;
	+ cout << "1024 BITS\n";
	+ } else if (lines[start].find("2048")!=string::npos) {
	+ bits = 2048;
	+ cout << "2048 BITS\n";
	+ } else {
	+ cout << "UNKNOWN NUMBER OF BITS\n";
	+ exit(0);
	+ }
	+
	+ start += 2;//start from line 2, read modulus (modulus is NOT corrupted, if it is corrupted, please copy from public key)
	+
	+ cout << "Modulus \n";
	+ read_corrupted_value(lines, start, pub.N, dummymask, true);
	+ //todo: should parse this:
	+ pub.e = 65537;
	+ start++;
	+ cout << "Private exponent \n";
	+ start++;
	+ read_corrupted_value(lines, start, priv.d, mask.d, true);
	+ start++;
	+ cout << "p\n";
	+
	+ read_corrupted_value(lines, start, priv.p, mask.p, true);
	+ start++;
	+ cout << "q\n";
	+
	+ read_corrupted_value(lines, start, priv.q, mask.q, true);
	+ start++;
	+ cout << " dp1\n";
	+ read_corrupted_value(lines, start, priv.dp1, mask.dp1, false);
	+ start++;
	+ cout << " dq1\n";
	+ read_corrupted_value(lines, start, priv.dq1, mask.dq1, false);
	+
	+ //exit(0);
	+}
	+
	+
	+
	void
	make_rsa_key(rsa_pub &pub, rsa_priv &priv, long bits, ZZ& e)
	{
	@@ -544,6 +693,7 @@
	"\t-t\tgives timing information\n"
	"\t-w W\tsets panic width to W (default is -1, meaning no limit)\n"
	"\t-i FILE\treads RSA key from FILE\n"
	+ "\t-x FILE\tfix RSA key from FILE\n"
	"\t-h\tprint this message\n");
	}
	@@ -573,6 +723,49 @@
	SetSeed(ZZFromBytes(randbuf, RANDBYTES));
	}
	+
	+int write_solution(rsa_priv &priv, rsa_pub &pub)
	+{
	+ static int ctr = 0;
	+ stringstream ss;
	+ ss << "solution" << ctr << ".asn";
	+
	+
	+ ZZ coeff;
	+
	+ if (InvModStatus(coeff, priv.q, priv.p)!=0) {
	+ cout << " not a solution \n";
	+ return 0;
	+ }
	+
	+ priv.d = InvMod(pub.e, (priv.p-1)*(priv.q-1));
	+
	+ ofstream output(ss.str().c_str());
	+ if (output.is_open()) {
	+ output << "asn1=SEQUENCE:rsa_key\n\n";
	+ output << "[rsa_key]\nversion=INTEGER:0\n";
	+ output << "modulus=INTEGER:" << pub.N << "\n";
	+ output << "pubExp=INTEGER:" << pub.e << "\n";
	+ output << "privExp=INTEGER:" << priv.d << "\n";
	+ output << "p=INTEGER:" << priv.p << "\n";
	+ output << "q=INTEGER:" << priv.q << "\n";
	+ ZZ e1;
	+ ZZ e2;
	+
	+ rem(e1, priv.d, priv.p-1);
	+ rem(e2, priv.d, priv.q-1);
	+ output << "e1=INTEGER:" << e1 << "\n";
	+ output << "e2=INTEGER:" << e2 << "\n";
	+ ZZ coeff = InvMod(priv.q, priv.p);
	+ output << "coeff=INTEGER:" << coeff << "\n";
	+
	+ output.close();
	+ }
	+ ctr++;
	+ return 1;
	+}
	+
	+
	int
	main(int argc, char *argv[])
	{
	@@ -586,9 +779,11 @@
	E = 65537;
	char *filename = NULL;
	+ bool fix_file = false;
	int c;
	- while((c = getopt(argc, argv, "e:n:f:svtw:i:h")) != EOF)
	+
	+ while((c = getopt(argc, argv, "e:n:f:svtw:i:x:h")) != EOF)
	switch (c)
	{
	case 'e':
	@@ -615,6 +810,10 @@
	case 'i':
	filename = optarg;
	break;
	+ case 'x':
	+ fix_file = true;
	+ filename = optarg;
	+ break;
	case 'h':
	usage();
	exit(0);
	@@ -623,11 +822,16 @@
	if (do_seed)
	seed();
	- if (filename)
	- read_rsa_key(filename, pub, key, MODULUS_BITS);
	- else
	- make_rsa_key(pub, key, MODULUS_BITS, E);
	- degrade_rsa_key(mask, key, delta);
	+ if (!fix_file) {
	+ if (filename)
	+ read_rsa_key(filename, pub, key, MODULUS_BITS);
	+ else
	+ make_rsa_key(pub, key, MODULUS_BITS, E);
	+ degrade_rsa_key(mask, key, delta);
	+ } else {
	+ read_corrupted_file(filename, pub, key, MODULUS_BITS, mask);
	+ }
	+
	double start_time = 0.0, mid_time = 0.0, stop_time = 0.0;
	@@ -828,6 +1032,10 @@
	while (!Q_gh.empty())
	{
	item &soln = Q_gh.front();
	+ if (write_solution(soln.key, pub)) {
	+ found = 1;
	+ }
	+
	if (soln.key.p == key.p)
	{
	found = 1;
	@@ -839,6 +1047,11 @@
	while (!Q_hg.empty())
	{
	item &soln = Q_hg.front();
	+
	+ if (write_solution(soln.key, pub)) {
	+ found = 1;
	+ }
	+
	if (soln.key.p == key.p)
	{
	found = 1;

view raw rsa.diff hosted with ❤ by GitHub

Program aslinya akan menghasilkan RSA key (atau membaca dari  file), merusak key tersebut, lalu merekonstruksi kembali keynya. Bagian membaca dari file diganti agar membaca bit yang tersedia dan bit yang tidak tersedia dianggap corrupt.

Saya menambahkan opsi -x <corrupted_file>. File input harus diperbaiki dulu supaya nilai modulus benar. Ini bisa didapatkan dari public key:

openssl pkey -pubin -in public.pub -text -noout
Contoh file input berdasarkan soal:

	Private-Key: (1024 bit)
	modulus :
	00:db:fa:bd:b1:49:5d:32:76:e7:62:6b:84:79:6e:
	9f:c2:0f:a1:3c:17:44:f1:0c:8c:3f:3e:3c:2c:60:
	40:c2:e7:f3:13:df:a3:d1:fe:10:d1:ae:57:7c:fe:
	ab:74:52:aa:53:10:2e:ef:7b:e0:09:9c:02:25:60:
	e5:7a:5c:30:d5:09:40:64:2d:1b:09:7d:d2:10:9a:
	e0:2f:2d:cf:f8:19:8c:d5:a3:95:fc:ac:42:66:10:
	78:48:b9:dd:63:c3:87:d2:53:8e:50:41:53:43:04:
	20:33:ea:09:c0:84:15:5e:65:2b:0f:06:23:40:d5:
	d4:71:7a:40:2a:9d:80:6a:6b
	publicExponent : 65537 (0x10001)
	privateExponent :
	f: : : a: a:9 :e : : 1: 2: : :e : :1 :
	3 : 1: : : : a: :2 : : : : : : : :
	9 : a: : : : : : 5:c1: 0:b : 3: 2:0 :b0:
	:c : f: :f : :d2: : : d: :1 : :3 : :
	: : :0 : 3: : : 5:c : :3 :6 : :a4: :
	4 : : :8f: : : : : a: : c:5f: 7: 6: :
	1: : b: : 5: :84:0 :b : f: 3: : : 4: 6:
	: : 5:1 : :d : : f: : c: : : 5: : :
	:e :f4:b :4 :8e: :
	prime1 :
	00: :6 : 1:1 : :b :0 : 2:c : b:2 : : a:1 :
	c : : 0: :28:0 : :cd: : 8: : :20: c: :
	: 5: :9 : c:3 : : : a:b :c :3 : : : :
	f: : : f: 1: 1:b : : c:f : a: :a : : :
	a:38: :6 :
	prime2 :
	:e : :d :2 :6 : 7: :33: :46: : 4: : :
	:5 : : 4:6 : : 6: : e:d : : : 9: e:1 :
	: : : : :0 : : : :c : 5: : :a :0 :
	6 : : :8 :e9:f : f:7 :5 : e:1 : : : 1:9 :
	4:d :e9: 6:
	exponent1:
	9:d : 5: :c :67: : 9: : : : d: : : 3:
	f:6 : 0:c : :6 :ad: :2 :d :d : : :0 :7 :
	:5 : 6: : 5:1 :f : d: : 2: : : 2: 3: :
	9 : : : : :67: 3: :4 : 7:c0: 4:b :c :f :
	:3 :b : 1
	exponent2 :
	1 : 9:47:8 : : : : 3: : : :6 : : :0 :
	e :e :8 : : : : : 1:c :74: : :d : 9:3 :
	5 : e: : 2: :7 : 2:c : : : : :5 : : 8:
	: :c : : 1: :a : : 9: 5: : 3: : e:c :
	: : 6:
	coefficient:
	:a :d :84:f : : c:43: : : : 6: : : :
	: b: :c :9 : : : : : : 4:23:8b: :6 :
	2 : 2: : : 7:5b: : : :7 : : : : : :
	f1:7 :1 : :f : a: : 5: : : : 5: : c: 1:
	:48: b: 6:

view raw corrupted.pem hosted with ❤ by GitHub

Jalankan program:

./rsa -x corrupted.pem

Hasilnya: solution0.asn

Ubah ke format der:

openssl asn1parse -genconf solution0.asn -out newkey.der

Check bahwa keynya benar, dan tuliskan ke PEM:

openssl rsa -in newkey.der -inform der -text -check > key.pem

Decrypt pesan:

openssl rsautl -decrypt -in encrypted -out plaintext.txt -inkey key.pem

Hasilnya adalah:

crypt0>>>f0rensics3~