Square CTF 2018 C2: flipping bits

Challenge02 - Flipping_Bits_02

Analysis

Inside the file ‘flipping_bits.jar’ we have only one file, flipping_bits.txt. This challenge provided two messages RSA encoded with different public exponents and the same modulus.

02

We have:

Cyphertext ct1: 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
Cyphertext ct2: 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065
Exponent e1: 13
Exponent e2: 15
Modulus (n): 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627

In RSA encryption, the modulus n should be the product of two large prime numbers p and q:

Large prime number p, Large prime number q
Modulus n = p * q

But when we were searching for those numbers, we find that n was itself a prime number. So what?

Solution

Using the same modulus with different exponents leaves RSA open to a “Common Modulus Attack” described in many places (like here).

As described in the link, this can be solved by performing the Extended Euclidean Algorithm (EEA) on the two exponents and using the result in a mathematical operation.

With the EEA we can compute the integers such that

x * e1 + y * e2 = 1    (Bézout’s identity)

The extended GCD can be found using wolfram alpha and solves as

ExtendedGCD[13,15] = [7, -6]

[We could also use xgcd from libnum library as libnum.xgcd(13, 15) ]

So x = 7 and y =  – (6).

And for Bézout’s Identity:

7*13 + (-6)*15 = 1

Because  y < 0 we’ll need to compute the inverse of (ct2 mod N) later.

Now:

Plaintext = ct1x  * ct2y mod N
Plaintext = ct17 mod N * ct2(-6) mod N

In Python, we can translate with the function pow(x, y, z), computed more efficiently than pow(x, y) % z.

It returns x to the power y; if z is present, return x to the power y, modulo z.

Using this with the python code below gives the solution. Note that to raise to a negative power the value needs to be inverted first (i.e. gmpy2.invert), else Python throws an error:

TypeError: pow() 2nd argument cannot be negative when 3rd argument specified

The function gmpy2.invert(x,m) returns y such that x * y == 1 modulo m, or 0 if no such y exists.

We wrote a Python script to solve this, and called flipping-bits-solve.py

import gmpy2
import binascii

ct1 = 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
ct2 = 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065
e1 = 13
e2 = 15
modulus = 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627

# ct1 == plaintext1 ** 13 % modulus
# ct2 == plaintext2 ** 15 % modulus

plaintext = pow(ct1,7,modulus) * pow(gmpy2.invert(ct2,modulus),6,modulus)
plaintext = plaintext % modulus
cyphertext2 = plaintext ** 15 % modulus

print 'plaintext1:'
print(plaintext)
print ''
print 'Hex plaintext1:'
print hex(plaintext)
print ''
print 'Plaintext 1:'
print(binascii.unhexlify('%x'%plaintext))
print ''
print 'Cyphertext 2:'
print cyphertext2
print ''
if (cyphertext2 == ct2):
    print "Plaintext1 and Plaintext2 are the same."
else:
    print "Plaintext1 and Plaintext2 are not the same."

And this is the result:

15

The flag we were searching for is:

flag-54d3db5c1efcd7afa579c37bcb560ae0

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.