<- CRYPTO

Lost Modulus Again

6 minutes to read

We are given a short Python code to encrypt the flag:

#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes, inverse
from os import urandom

class RSA:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.e = 3
        self.n = self.p * self.q
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
    def encrypt(self, data: bytes) -> bytes:
        pt = int(data.hex(), 16)
        ct = pow(pt, self.e, self.n)
        return long_to_bytes(ct)
    def decrypt(self, data: bytes) -> bytes:
        ct = int(data.hex(), 16)
        pt = pow(ct, self.d, self.n)
        return long_to_bytes(pt)

def main():
    flag = open('flag.txt', 'r').read().strip().encode()
    #padding makes everything secure :lemonthink:
    def pad(data: bytes) -> bytes:
        return data+urandom(16)
    crypto = RSA()
    print ('Flag1 :', crypto.encrypt(pad(flag)).hex())
    print ('Flag2 :', crypto.encrypt(pad(flag)).hex())
    print( 'msg1 :', crypto.encrypt(b"Lost modulus had a serious falw in it , we fixed it in this version, This should be secure").hex())
    print( 'msg2 :', crypto.encrypt(b"If you can't see the modulus you cannot break the rsa , even my primes are 1024 bits , right ?").hex())
if __name__ == '__main__':
    main()

And we are also given the output:

Flag1 : 685dba88de1ecf0b4ae5bc84b7ee87f63eb37f697ca9a5ab6af9359341a2fbbf53b9502477cabb1658fdf775a34a0712b04d0fd2679b47ec088e0ab3c0a9a866198077a496bb1de138cd165ca28722dee7c4cc81ac0a3a179095f11981e9c7bcd590576169ed877b5692f42a7d9845bdb7c0bffd4e97541b65321de83e4083c1c8cc93eec59933f42655d7c0ad170ed9a3ea418b582e09a2692fc1965d8372cac678f0dabe1b0cbda93ac9b484feb9d2e96f3ab7e2fc6430da1931281c1870c637866be7fcd69c1b067e001887bb17a57ccd77532ea9dfaa0be1390db5511771dc9e03593e344bf0647ddac395b1fe80a86ad4ea4606fdb8a82fdcf9c846114c
Flag2 : 356f7e82071f321361075ee85f9b42922662559ed64b253c64ff37b52fe8dcf3ab3163079bc9a12e951f84d2f7a911cbf1b1e8d7cd759a128f21a89b625b07ded33443a2888ca9a455198fd5b4a3fb307f34c704b7dcad88685263f4c3f4cf37f1099f2bd188de72533308c25fc18948dda220e3693b7f3edb689ee489c14e7624932ee8928370c9c1d59b06d1071a259d64c38735b1b586082099919713b669a79e43329f0c20508620982d95b774a57d009540c2ef2835887d229273223272f86fb0b1740937d3fc83d7556ffe634a16fb1faf6125878b06f5d537c21260014e2e67ae47636cbce899c463a3669954253aac3aa89a1c800d3251cf6a36badf
msg1 : 0241f53c0690e3faccc3753b6064aef27341b5bef3a10fcbb362251e1f5474a055a04e631af1bb4542351f6051438fc6dbf2011f79cbd85bc667d1097b57818d01d11aa09db0ef221ccf8d9eb16903423702b64a534d49153b49dc47fd5597a96f2a6480d296d36d08ba3438cc193bba6ee2c3ea81ab4dbb029a737c3f5597c8e4b8db8ab06605443eb35160828bc78b1d889814d8811e89efae3d741a481a7bd09483df8ee6d32b56a8d7eb20b275cf3ba5936838da2893f82cbc469f1497f785603e72df1ae1f619e08834588f2e64dd5f4cbbdbc7357dadcd89dbd9e18b0948f9b3f8f6b0df217bd7e8ae5c89a20878ffb127e3cf862baa78cc67ec1012af
msg2 : 7499a590fcb19dd0880b77a0dd57f66f6055976100b10053adadaeec18c382c5c3d095b4edd6ee2a5dfdc5790b18ff96e54f093fa62d4b518c1bbe65ad3588a81a1723ce72798ddd06d1eca7be9332a7b754f85582c4c5800d0c778ec320fa53806d122b4f4e436ead12bdf05031d4c181416184932517da985ff503759d128761bd96009c43bf11e45ba60f495235d29a863b7a64d9752868dd9896563fe2cc91df6f092f6d4d7d600b4fbf2b52579a0f2657223a1092c067584aad9997540b25921513f96f2da0c26ffb2ee7578540efc50bc8ab0feeeb24e0e96ebc1e6310dbed880ec5d9788a86bebe72c4b5d9b5c66716e6b84021591372c823c6d78c4e

Source code analysis

The above are 4 ciphertexts of an RSA-2048 encryption. We know that the exponent is , but we do not have the modulus :

class RSA:
    def __init__(self):
        self.p = getPrime(1024)
        self.q = getPrime(1024)
        self.e = 3
        self.n = self.p * self.q
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
    def encrypt(self, data: bytes) -> bytes:
        pt = int(data.hex(), 16)
        ct = pow(pt, self.e, self.n)
        return long_to_bytes(ct)
    def decrypt(self, data: bytes) -> bytes:
        ct = int(data.hex(), 16)
        pt = pow(ct, self.d, self.n)
        return long_to_bytes(pt)

For the first 2 ciphertexts (say and ), the flag is first padded with a random string of 16 bytes and then encrypted with RSA. The last 2 ciphertexts (say and ) correspond to some known messages hard-coded on the source code (say and ).

def main():
    flag = open('flag.txt', 'r').read().strip().encode()
    #padding makes everything secure :lemonthink:
    def pad(data: bytes) -> bytes:
        return data+urandom(16)
    crypto = RSA()
    print ('Flag1 :', crypto.encrypt(pad(flag)).hex())
    print ('Flag2 :', crypto.encrypt(pad(flag)).hex())
    print( 'msg1 :', crypto.encrypt(b"Lost modulus had a serious falw in it , we fixed it in this version, This should be secure").hex())
    print( 'msg2 :', crypto.encrypt(b"If you can't see the modulus you cannot break the rsa , even my primes are 1024 bits , right ?").hex())

Solution

First of all, we need to get . Notice that using the known messages and , we get:

Therefore, and are both multiple of , so we can find using the Greatest Common Divisor (GCD):

Now, to find the flag, the key point is that the plaintexts, before encrypting, are very related. Actually, we can denote the ciphertexts like:

Where and are the random 16-byte strings. Also notice that since padding is byte concatenation, we can express it in numerical terms with a multiplication times .

Since the padding is short and , we can apply the Coppersmith’s attack (actually, variants called Franklin–Reiter related-message attack and Coppersmith’s short-pad attack). For this, we define two polynomials:

Let’s say . These polynomials satisfy that

So, the point is a common root of polynomials and . We are interested in finding , but we will need to find first. For this, let’s take the resultant of these polynomials in the variable (kind of eliminating this variable):

As a result, , so we know that is a root of . Notice that the polynomials , , are defined over , which is not a field and we can’t easily find and such that . This means that finding this root is hard.

However, this root (16 bytes) is small compared to (2048 bits, 256 bytes). So, we can use Coppersmith method to find .

Once we have , we can update our previous polynomials and to:

Therefore, we have that , so is a root of both and . As a result, we can apply Franklin-Reiter related-messages attack, which consists basically in computing the polynomial GCD of these polynomials, to find the shared factor , and obtain the flag.

Implementation

All these steps can be done in SageMath. First, let’s write the given output of the challenge and known information:

sage: c1 = 0x685dba88de1ecf0b4ae5bc84b7ee87f63eb37f697ca9a5ab6af9359341a2fbbf53b9502477cabb1658fdf775a34a0712b04d0fd2679b47ec088e0ab3c0a9a866198077a496bb1de138cd165ca28722dee7c4cc81ac0a3a179095f11981e9c7bcd590576169ed877b5692f42a7d9845bdb7c0bffd4e97541b65321de83e4083c1c8cc93eec59933f42655d7c0ad170ed9a3ea418b582e09a2692fc1965d8372cac678f0dabe1b0cbda93ac9b484feb9d2e96f3ab7e2fc6430da1931281c1870c637866be7fcd69c1b067e001887bb17a57ccd77532ea9dfaa0be1390db5511771dc9e03593e344bf0647ddac395b1fe80a86ad4ea4606fdb8a82fdcf9c846114c
sage: c2 = 0x356f7e82071f321361075ee85f9b42922662559ed64b253c64ff37b52fe8dcf3ab3163079bc9a12e951f84d2f7a911cbf1b1e8d7cd759a128f21a89b625b07ded33443a2888ca9a455198fd5b4a3fb307f34c704b7dcad88685263f4c3f4cf37f1099f2bd188de72533308c25fc18948dda220e3693b7f3edb689ee489c14e7624932ee8928370c9c1d59b06d1071a259d64c38735b1b586082099919713b669a79e43329f0c20508620982d95b774a57d009540c2ef2835887d229273223272f86fb0b1740937d3fc83d7556ffe634a16fb1faf6125878b06f5d537c21260014e2e67ae47636cbce899c463a3669954253aac3aa89a1c800d3251cf6a36badf
sage: c3 = 0x0241f53c0690e3faccc3753b6064aef27341b5bef3a10fcbb362251e1f5474a055a04e631af1bb4542351f6051438fc6dbf2011f79cbd85bc667d1097b57818d01d11aa09db0ef221ccf8d9eb16903423702b64a534d49153b49dc47fd5597a96f2a6480d296d36d08ba3438cc193bba6ee2c3ea81ab4dbb029a737c3f5597c8e4b8db8ab06605443eb35160828bc78b1d889814d8811e89efae3d741a481a7bd09483df8ee6d32b56a8d7eb20b275cf3ba5936838da2893f82cbc469f1497f785603e72df1ae1f619e08834588f2e64dd5f4cbbdbc7357dadcd89dbd9e18b0948f9b3f8f6b0df217bd7e8ae5c89a20878ffb127e3cf862baa78cc67ec1012af
sage: c4 = 0x7499a590fcb19dd0880b77a0dd57f66f6055976100b10053adadaeec18c382c5c3d095b4edd6ee2a5dfdc5790b18ff96e54f093fa62d4b518c1bbe65ad3588a81a1723ce72798ddd06d1eca7be9332a7b754f85582c4c5800d0c778ec320fa53806d122b4f4e436ead12bdf05031d4c181416184932517da985ff503759d128761bd96009c43bf11e45ba60f495235d29a863b7a64d9752868dd9896563fe2cc91df6f092f6d4d7d600b4fbf2b52579a0f2657223a1092c067584aad9997540b25921513f96f2da0c26ffb2ee7578540efc50bc8ab0feeeb24e0e96ebc1e6310dbed880ec5d9788a86bebe72c4b5d9b5c66716e6b84021591372c823c6d78c4e
sage: 
sage: e = 3
sage: 
sage: m3 = int(b"Lost modulus had a serious falw in it , we fixed it in this version, This should be secure".hex(), 16)
sage: m4 = int(b"If you can't see the modulus you cannot break the rsa , even my primes are 1024 bits , right ?".hex(), 16)

Now, let’s find using the GCD:

sage: n = gcd(m3 ** e - c3, m4 ** e - c4)
sage: n
17239653555729308464049438184920371089879081148402291800380594759517665804698359052648921465219887554469533537465122062104900480567488997794605293481770139146098702102563250193298500864238250949982552595159802814788612573898410252974926866757617491510437384709301937357695288829868010397984533999482461397333141208905813094732501385628605554793978927603376904138986551086256407424185029648833489655496424708493511895902919181646372064531235987733921846952446773365611469842532440322381367711369625814351911101284458643213930109512205598526068165522864217435748337932540742524768583448250580752519750464577065964352977

Once we have , we can define polynomials and as stated before and find their resultant:

sage: P.<x, y> = PolynomialRing(Zmod(n))
sage: 
sage: f = x ** e - c1
sage: g = (x + y) ** e - c2
sage: 
sage: h = g.sylvester_matrix(f).det().univariate_polynomial()

Although SageMath has a resultant method, it is sometimes easier to compute the determinant of the Sylvester matrix, which is essentially the same as the resultant in this context and doesn’t throw any type error.

After that, we apply Coppersmith method on to find the small root :

sage: R = h.monic().small_roots(X=256 ** 16, beta=16 / 256)[0]
sage: R
17239653555729308464049438184920371089879081148402291800380594759517665804698359052648921465219887554469533537465122062104900480567488997794605293481770139146098702102563250193298500864238250949982552595159802814788612573898410252974926866757617491510437384709301937357695288829868010397984533999482461397333141208905813094732501385628605554793978927603376904138986551086256407424185029648833489655496424708493511895902919181646372064531235987733921846952446773365611469842532440322381367711369625814351911101284458643213930109512205598526068165522864217435748337932540742524768288846483820791076371295960930657614594

Although the value got for doesn’t look small, it is in fact small, but in negative form (and obviously a root of ):

sage: -R % n
294601766759961443379168616135306738383
sage: h(R)
0

Once we have , we can define polynomials and and apply polynomial GCD to find the padded flag:

sage: P.<t> = PolynomialRing(Zmod(n))
sage: 
sage: F = t ** e - c1
sage: G = (t + R) ** e - c2
sage: 
sage: def polynomial_gcd(f, g):
....:     return polynomial_gcd(g, f % g) if g else f.monic()
....: 
sage: flag_p1 = -polynomial_gcd(F, G).coefficients()[0] % n

Flag

At this point, we just remove the padding and we are done:

sage: flag = int(flag_p1) // 256 ** 16
sage: print(bytes.fromhex(hex(flag)[2:]).decode())
HTB{Fr4nk1ln_r3t1t3r_sh0rt_p4d_4tt4ck!4nyw4ys_n3v3r_us3_sm0l_3xr_f0r_rs4!1s_th1s_Msg_g01ng_l4rg3r?_0h_y3s_cuz_1_h4v3_t0_Pr3v3nt_Cub3_r00t_4tt4ck}