DEV Community

Richard Fan
Richard Fan

Posted on • Updated on • Originally published at richardfan1126.Medium


Cyber Apocalypse CTF 2022 Writeup - Down the Rabinhole

The challenge

from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from Crypto.Util.Padding import pad
import os


def getPrimes(coefficient):
    while True:
        a = getPrime(512)
        p = 3 * coefficient * a + 2
        if isPrime(p):
    while True:
        b = getPrime(512)
        q = 3 * coefficient * b + 2
        if isPrime(q):
    return p, q

def encrypt(message, coefficient):
    p, q = getPrimes(coefficient)
    n = p * q

    padded_message = bytes_to_long(pad(message, 64))
    message = bytes_to_long(message)

    c1 = (message * (message + coefficient)) % n
    c2 = (padded_message * (padded_message + coefficient)) % n
    return (n, c1, c2)

def main():
    coefficient = getPrime(128)
    out = ""

    message = FLAG[0:len(FLAG)//2]
    n1, c1, c2 = encrypt(message, coefficient)
    out += f"{n1}\n{c1}\n{c2}\n"

    message = FLAG[len(FLAG)//2:]
    n2, c3, c4 = encrypt(message, coefficient)
    out += f"{n2}\n{c3}\n{c4}"

    with open("out.txt", "w") as f:

if __name__ == '__main__':

Enter fullscreen mode Exit fullscreen mode

The python script performs encryption on the flag then store in a text file:

Enter fullscreen mode Exit fullscreen mode

Similar challenge

This challenge is similar to Two Rabin in Asian Cyber Security Challenge. There is a writeup from amyriad here


Franklin–Reiter related-message attack

The flag is split into 2 parts and each part is encrypted with and without padding. So the cipertext pairs (c1, c2) and (c3, c4) differs by the padding bytes.

We can apply Franklin–Reiter related-message attack on each cipertext pair by applying amyriad's code

Guessing the missing parts

Unlike the Two Rabin challenge, the flag length and the value of coefficient (or B in Two Rabin challenge) are unknown to us.

Length of the flag

From the challenge code, we can see:

  • The flag is split into half and padded to 64-byte long, so the padding of both should be the same

  • The same coefficient is used for addition in 2 sets of encryption.

  • The length of modulus used in 2 sets of encryption is larger than the message being encrypted

    n is (512 + 128) * 2 = 1280-bit long and the message being encrypted is 512 * 2 = 1024-bit long

    So we can simply ignore the modulus

Based on these 3 findings, we can assume c2 and c4 will have the the same Least Significant Bytes (LSB). And the length of that LSBs is the same as the plaintext padding.

To better understand why, we can think of multiplication in decimal system

12345 * 23456 = 0289564320

34345 * 45456 = 1561186320

When we multiply numbers with the same least significant digits (345 and 456), the result will have the same length of same least significant digits (320) no matter what the other part is.

By comparing the bytestring of c2 and c4, we can see they have 39 same LSBs

c2 = b"\x14o\x81!\x1cg\x9e{)\xde\xa9\xfa\xb7\x99\x89\x8b\x17\xcf}\x008\x10m\xccx.H\x07\xd4D\x8f@\xc0\xbfJrN\x0e\xe3P\xeb\xe4h\xd6\xa2\xc6\xb1\x1fGR\xa6U\x90\xe6m\x83\xb2\xe3\xe6|\xf6\xe1\xa2\x85\x18+\x05\x1e\xfc3\x98\xa3\xe7`\xfa\x01\x03z\xc9:h%\xdd\xed\xc0\xb6\xa7\x94\xe9\xb1\xba\xc3\xcc\xd5\xde\xe7\xf0\xfa\x03\x0c\x15\x1e'09BKT]foxcE\xf0(\xc3 \xac\x9eiS\xe6H\xb5\x17\x9f\x12"
c4 = b"*\x95\xa6\x9a7\x90\xe3$\xe4c{O$j5D\xfcF\x837\xdf\xa4\xa2\x98\xf2\x99\xa7\xe6\x94FB\x97\x90\xf8\xdd\xd4\xcb]k(k\xa2\xdb\x83\xa3\xe4\x9a\xc2NSVN{\x18IS\x10\x88\x11g\xf2k\xb7\x95\xe0C\xdcf7\x15\x88B\xe9\x88Q\x84\x95\x86\x0e\x98E\xad7lu\xf6\xa7u\xd6\xb1\xba\xc3\xcc\xd5\xde\xe7\xf0\xfa\x03\x0c\x15\x1e'09BKT]foxcE\xf0(\xc3 \xac\x9eiS\xe6H\xb5\x17\x9f\x12"
lsb = b"\xb1\xba\xc3\xcc\xd5\xde\xe7\xf0\xfa\x03\x0c\x15\x1e'09BKT]foxcE\xf0(\xc3 \xac\x9eiS\xe6H\xb5\x17\x9f\x12"
Enter fullscreen mode Exit fullscreen mode

Because of how PKCS#7 performs padding, we also know the last 39 bytes of the padded plaintext is 39 of \x27 (Hex code of decimal number 39:

Enter fullscreen mode Exit fullscreen mode

The value of coefficient

We now knows part of the plaintext and its corresponding part of the ciphertext, we can guess the value of coefficient.

The relationship between them is:

ciphertext = padded_msg * (padded_msg + coefficient) % n
Enter fullscreen mode Exit fullscreen mode

Because we only know part of the padded_msg, we cannot simply get the coefficient by performing division on ciphertext.

But we also don't brute-force a 128-bit long number one-by-one.

Instead, we can brute-force the coefficient byte-by-byte.

For example, when we want to know 2467 * x = 3584551, we don't need to brute-force the number from 1 to 99999.

We can first brute-force the last digit: 2467 * 3 = 7401, which has the same last digit with the result. And we can assume the last digit of x is 3

Then 2467 * 53 = 130751 , which has the same last 2 digit with the result. And we can assume the last 2 digit of x is 53

Using the same method, we can instantly brute-force the coefficient by the following script:

ct = b'\x9c\xa5\xae\xb7\xc0\xc9\xd2\xdb\xe4\xed\xf7\x00\t\x12\x1b$-6?HQZcX%\xdaa\xbb\x107\x86\x8d\x89\r\x95\xc59_P'

pt = b'\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27\x27'
pt = bytes_to_long(pt)

coefficient = b''
for j in range(16):
    known_part = bytes_to_long(coefficient)
    for k in range(256):
        tmp = long_to_bytes(pt*(pt+k*(256 ** j)+known_part))
        if tmp[-j+1:] == ct[-j+1:]:
            coefficient = long_to_bytes(k) + coefficient

Enter fullscreen mode Exit fullscreen mode

The coefficient is 263063435253385937926984981365320113271

Putting all parts together

Based on the length of flag and the value of coefficient, we can alter amyriad's code as follow:

n = 56438641309774959123579452414864548345708278641778632906871133633348990457713200426806112132039095059800662176837023585166134224681069774331148738554157081531312104961252755406614635488382297434171375724135403083446853715913787796744272218693049072693460001363598351151832646947233969595478647666992523249343972394051106514947235445828889363124242280013397047951812688863313932909903047
e = 2
B = 263063435253385937926984981365320113271
c1= 429546912004731012886527767254149694574730322956287028161761007271362927652041138366004560890773167255588200792979452452
c2= 29903904396126887576044949247400308530425862142675118500848365445245957090320752747039056821346410855821626622960719507094119542088455732058232895757115241568569663893434035594991241152575495936972994239671806350060725033375704703416762794475486000391074743029264587481673930383986479738961452214727157980946
delta = (B + n) >> 1
c1 = (c1 + delta^2) % n
c2 = (c2 + delta^2) % n
# Source:
def gcd(a, b):
     while b:
         a, b = b, a % b
     return a.monic()
def franklinreiter(C1, C2, e, N, a, b):
     P.<X> = PolynomialRing(Zmod(N))
     g1 = (a*X + b)^e - C1
     g2 = X^e - C2
     result = -gcd(g1, g2).coefficients()[0]
     return result
def int_to_bytes(x: int) -> bytes:
     return x.to_bytes((x.bit_length() + 7) // 8, 'big')
bg = 0x272727272727272727272727272727272727272727272727272727272727272727272727272727
soln = franklinreiter(c2, c1, e, n, 1 << 312, bg + delta - (delta << 312)) - delta
Enter fullscreen mode Exit fullscreen mode

Parameters I have changed:

  • The value of B is same as the coefficient we found
  • n, c1, c2 is the value from the text file
  • Change bg to our plaintext padding
  • Change the bit shift value to 312 (39 bytes)

After running the franklinreiter with (n1, c1, c2) and (n2, c3, c4) respectively, we can get the flag:

Enter fullscreen mode Exit fullscreen mode

Top comments (0)