ASIS Finals CTF 2017- Gracias Writeup

 

Points: 287    Solves: 9    Category: Crypto

Description: Some people think that combination of cryptographic systems will definitely improve the security. That’s your turn to prove them wrong.

This challenge is a bit simpler than it looks like. It is a multi-prime RSA challenge where we are given an encryption script, which has two functions, one that generates public and private keys and another that encrypts using the public key generated from the first function.

The function that generates public and private keys:

def make_pubpri(nbit):
    p, q, r = [ getPrime(nbit) for _ in xrange(3)]
    n = p * q * r
    phi = (p-1)*(q-1)*(r-1)
    l = min([p, q, r])
    d = getPrime(1)
    e = inverse(d, phi)
    a = gensafeprime.generate(2*nbit)
    while True:
        g = getRandomRange(2, a)
        if pow(g, 2, a) != 1 and pow(g, a/2, a) != 1:
            break
    return (n, e, a, g), (n, d, a, g)

There are three-512 bit primes- p, q, r being generated in this RSA Encryption instead of two. The decryption exponent d, is generated as a 256-bit prime. The function is returning n, e, a, g as the public key.

The following is the encryption function:

def encrypt(m, pub):
    n, e, a, g = pub
    k = getRandomRange(2, a)
    K = pow(g, k, a)
    c1, c2 = pow(k, e, n), (m * K) % a
    return c1, c2

Unlike the conventional RSA encryption, here the message is not encrypted using RSA; instead of that, k is encrypted using the public key exponent e, the ciphertext of which is c1. There is another ciphertext variable returned in the function along with c1 that is:

c2 = (m * K) % a

K = pow(g, k, a)

So, the flow of attack on this challenge is as follows:

1. Decrypt the ciphertext c1 to get k.
2. Use this k to generate K as given in the code and then simply multiply c2 with multiplicative inverse of K over modulus a, to get the message m.

Here are the values of public key variables given:

n = 1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L

e = 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L

The first thought that comes to my mind to solve step-1 in the flow of attack is Wiener’s Attack. By just looking at n and e values, we can suspect it to be vulnerable to Wiener’s Attack (Number of digits in each is almost the same, consider it a guess). I verified the criteria for it to be vulnerable to Wiener’s Attack (i.e. d<(1/3)*(N^1/4)  or   e>N^3/2) and found that e, i.e. the public key exponent, is a few bits smaller than N^3/2, which made me conclude that d, i.e. the private key exponent, must be a few bits greater than (1/3)*(N^1/4). So, the values fail to fall under the conventional criteria of Wiener’s Attack, by a few bits. But I wrote this script implementing Wiener’s Attack in python-sage to check if it really works.

Note that k is encrypted instead of message m, thus I used a temporary message m=12345, encrypted it using the same public key exponent e and modulus n, and finally tried Wiener’s Attack on this; thus the script:

from sage.all import continued_fraction, Integer
def wiener(e, n):
	m = 12345
	c = pow(m, e, n)

	list1 = continued_fraction(Integer(e)/Integer(n))
	conv = list1.convergents()
	for i in conv:
		d = int(i.denominator())
		m1 = pow(c, d, n)
		if m1 == m:
			return d
pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
n, e, a, g = pubkey
print wiener(e, n)

As expected, the function did not return anything. I could not find any other vulnerability in the code except the Wiener’s Attack and the close values of e and n suggested that there must be some kind of a Wiener’s Attack vulnerability, although not the conventional one. I found another variant of Wiener’s Attack upon searching more about it. There is a paper by Andrej Dujella on a variant of Wiener’s Attack and it works well when the size of d is just a few bits greater than N^1/4.

You can check the paper here: A Variant of Wiener’s Attack on RSA

Here is a conclusion of the paper which is significant in our attack:

1. Along with d being the denominator of the convergent of the continued fraction of (e/n), the decryption exponent can also be written in the form:
   1. a.    d = r*q_m+1 + s*q_m

Here q_m+1 and q_m are the (m+1)th and mth denominators of the convergents of the continued fraction of (e/n) respectively.

I assigned q0 = 1 and q1 as the first denominator of the convergent of continued fraction of (e/n). Here is the exploit for Step-1 where I implemented the Wiener’s Attack using the conclusion from the paper I described above:

def wiener(e, n):
	m = 12345
	c = pow(m, e, n)
	q0 = 1

	list1 = continued_fraction(Integer(e)/Integer(n))
	conv = list1.convergents()
	for i in conv:
		k = i.numerator()
		q1 = i.denominator()

		for r in range(20):
			for s in range(20):
				d = r*q1 + s*q0
				m1 = pow(c, d, n)
				if m1 == m:
					return d
		q0 = q1

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

n, e, a, g = pubkey
c1, c2 = c

d = wiener(e, n)
print d

This finally gave me the decryption exponent:

d = 100556095937036905102538523179832446199526507742826168666218687736467897968451

Now that the significant part of the challenge to get the decryption exponent is done, we can get k, then K and then finally the message m. This is Step-2 and the final step in the exploit:

from Crypto.Util.number import *

k = pow(c1, d, n)
K = pow(g, k, a)
print long_to_bytes(c2 * inverse(K, a) % a)

Which gives us the flag:
ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}

Here is the final exploit script:

from sage.all import continued_fraction, Integer
from Crypto.Util.number import *

def wiener(e, n):
	m = 12345
	c = pow(m, e, n)
	q0 = 1

	list1 = continued_fraction(Integer(e)/Integer(n))
	conv = list1.convergents()
	for i in conv:
		k = i.numerator()
		q1 = i.denominator()

		for r in range(20):
			for s in range(20):
				d = r*q1 + s*q0
				m1 = pow(c, d, n)
				if m1 == m:
					return d
		q0 = q1

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

n, e, a, g = pubkey
c1, c2 = c

print "e: ", e
print "n: ", n

d = wiener(e, n)

print "d: ", d

k = pow(c1, d, n)
K = pow(g, k, a)
m = long_to_bytes(c2 * inverse(K, a) % a)
print m