I participated corCTF with H0j3n last weekened, it was a nice CTF. Here are some of the writeups

Challenges

tadpole

tadpole

Attachments

Look at the python source code:

from Crypto.Util.number import bytes_to_long, isPrime
from secrets import randbelow

p = bytes_to_long(open("flag.txt", "rb").read())
assert isPrime(p)

a = randbelow(p)
b = randbelow(p)

def f(s):
    return (a * s + b) % p

print("a = ", a)
print("b = ", b)
print("f(31337) = ", f(31337))
print("f(f(31337)) = ", f(f(31337)))

As you can see, we are given \(a\), \(b\), \(f(31337)\) and \(f(f(31337))\)

And we need to find \(p\) which is the flag!

Modular arithmetic

If you familar with PRNG, you know this is using LCG https://en.wikipedia.org/wiki/Linear_congruential_generator

We need some math in order to find \(p\)

According to modular arithmetic, we know that \(f(s) \equiv as+b \mod p\), therefore \(f(s) = kp+as+b\)

So to find \(kp\), we just need to calculate \(f(s)-(as+b)\)

We got value of \(f(31337)\) and \(f(f(31337))\), we just need to calculate the \(kp\) of both value then calculate the GCD (Greatest Common Divisor) of both \(kp\), then we found \(p\) !!

\[k_1p=f(31337)-a(31337)+b\] \[k_2p=f(f(31337))-a(f(31337))+b\] \[p=gcd(k_1p,k_2p)\]

Calculate the flag using python script:

import gmpy2
from Crypto.Util.number import long_to_bytes
a =  7904681699700731398014734140051852539595806699214201704996640156917030632322659247608208994194840235514587046537148300460058962186080655943804500265088604049870276334033409850015651340974377752209566343260236095126079946537115705967909011471361527517536608234561184232228641232031445095605905800675590040729
b =  16276123569406561065481657801212560821090379741833362117064628294630146690975007397274564762071994252430611109538448562330994891595998956302505598671868738461167036849263008183930906881997588494441620076078667417828837239330797541019054284027314592321358909551790371565447129285494856611848340083448507929914
x1 =  52926479498929750044944450970022719277159248911867759992013481774911823190312079157541825423250020665153531167070545276398175787563829542933394906173782217836783565154742242903537987641141610732290449825336292689379131350316072955262065808081711030055841841406454441280215520187695501682433223390854051207100
x2 =  65547980822717919074991147621216627925232640728803041128894527143789172030203362875900831296779973655308791371486165705460914922484808659375299900737148358509883361622225046840011907835671004704947767016613458301891561318029714351016012481309583866288472491239769813776978841785764693181622804797533665463949

k1 = x1-(a*31337+b)
k2 = x2-(a*x1+b)

flag = gmpy2.gcd(k1,k2)
print(long_to_bytes(flag))
# b'corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs} <- this is flag adm'

Thats the flag! Simple math to calculate the flag

Flag

corctf{1n_m4th3m4t1c5,_th3_3ucl1d14n_4lg0r1thm_1s_4n_3ff1c13nt_m3th0d_f0r_c0mput1ng_th3_GCD_0f_tw0_1nt3g3rs}

luckyguess

Look at the python source code:

#!/usr/local/bin/python
from random import getrandbits

p = 2**521 - 1
a = getrandbits(521)
b = getrandbits(521)
print("a =", a)
print("b =", b)

try:
    x = int(input("enter your starting point: "))
    y = int(input("alright, what's your guess? "))
except:
    print("?")
    exit(-1)

r = getrandbits(20)
for _ in range(r):
    x = (x * a + b) % p

if x == y:
    print("wow, you are truly psychic! here, have a flag:", open("flag.txt").read())
else:
    print("sorry, you are not a true psychic... better luck next time")

Seems like another LCG again? Now we’re given \(a\), \(b\) and \(p\) and we can input the seed value \(x\) then guess correctly the final output to get the flag

Math again

\(r\) is 20bits long which is nearly impossible to guess, therefore it must have a value that \(x=f(x)\), so no matter what is \(r\) we can guess correctly the output

Searching for lcg bad seed found this slides stated the bad seed value is:

\[-(a-1)^{-1} \cdot b \mod p\]

We just need to solve the equation:

\[x=ax+b\] \[x-ax=b\] \[(1-a)x=b\] \[x=\frac{b}{1-a}\]

So if we input \(\frac{b}{1-a}\) as \(x\) we will get the same value! To calculate that we need to calculate the modular inverse of \(1-a\) then times \(b\) (Because of modular arithmetic)

My solution code using python:

from pwn import *
from Crypto.Util.number import *
p = remote("be.ax",31800)
p.recvuntil("a = ")
a = int(p.recvuntil('\n')[:-1])
p.recvuntil("b = ")
b = int(p.recvuntil('\n')[:-1])

P = 2**521 - 1
x = inverse(1-a,P) * b
print(f"x={x}")
print(f"y={(x * a + b) % P}")
p.interactive()
# x=8157802442862108603218032583174746602223107830105214400988760572848074964652282496633630863529974747007475186870875400736430339942641753414979724185385288945897013204349648892711500237449393089807499954866150814334827186976415763962970310451225314299120689307545333928967256604082498152596192970917628246788271253
# y=2878357714346482341059412386794527457065632409440137333123405194141516437425787096997746957221822320071627316690087461212467873121606718509524987871762938567
# [*] Switching to interactive mode
# enter your starting point: $ 8157802442862108603218032583174746602223107830105214400988760572848074964652282496633630863529974747007475186870875400736430339942641753414979724185385288945897013204349648892711500237449393089807499954866150814334827186976415763962970310451225314299120689307545333928967256604082498152596192970917628246788271253
# alright, what's your guess? $ 2878357714346482341059412386794527457065632409440137333123405194141516437425787096997746957221822320071627316690087461212467873121606718509524987871762938567
# wow, you are truly psychic! here, have a flag: corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}

Flag

corctf{r34l_psych1c5_d0nt_n33d_f1x3d_p01nt5_t0_tr1ck_th15_lcg!}

hidE

Look at the source code, seems like a RSA question:

#!/usr/local/bin/python
import random
import time
import math
import binascii
from Crypto.Util.number import *

p, q = getPrime(512), getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)

flag = open('./flag.txt').read().encode()

random.seed(int(time.time()))

def encrypt(msg):
    e = random.randint(1, n)
    while math.gcd(e, phi) != 1:
        e = random.randint(1, n)
    pt = bytes_to_long(msg)
    ct = pow(pt, e, n)
    return binascii.hexlify(long_to_bytes(ct)).decode()


def main():
    print('Secure Encryption Service')
    print('Your modulus is:', n)
    while True:
        print('Options')
        print('-------')
        print('(1) Encrypt flag')
        print('(2) Encrypt message')
        print('(3) Quit')
        x = input('Choose an option: ')
        if x not in '123':
            print('Unrecognized option.')
            exit()
        elif x == '1':
            print('Here is your encrypted flag:', encrypt(flag))
        elif x == '2':
            msg = input('Enter your message in hex: ')
            print('Here is your encrypted message:', encrypt(binascii.unhexlify(msg)))
        elif x == '3':
            print('Bye')
            exit()

if __name__ == '__main__':
    main()

As you can see, we can get encrypted flag and encrypted message but we only know \(n\)

How do we get the flag??

Find \(e\)

Look at the code carefully, you will see the random seed is using current time

random.seed(int(time.time()))

So we can easily guess the seed and \(e\) with random.randint()

Example python code:

# Generate 10 possible value of e
random.seed(start_time-i)
possible_e = []
for _ in range(10):
    possible_e.append(random.randint(1, n))

Find \(m\)

Now we got the \(e\) but how we get the flag?? We can use the Common Modulus Attack!

We can generate 2 different ciphertext that encrypt with the same modulus, so it is applicable to this attack!

My solution code in python:

import random
import time
import gmpy2
from pwn import *
from Crypto.Util.number import *
from itertools import combinations

p = remote("be.ax" ,31124)
# Record start time
start_time = int(time.time()) 

# Get modulus
p.recvuntil("is: ")
n = int(p.recvuntil('\n')[:-1])
p.sendlineafter(": ","1")

# Get two different ciphertext of flag
p.recvuntil("encrypted flag: ")
c1 = int(p.recvuntil('\n')[:-1],16)
p.sendlineafter(": ","1")

p.recvuntil("encrypted flag: ")
c2 = int(p.recvuntil('\n')[:-1],16)

# Code get from https://infosecwriteups.com/rsa-attacks-common-modulus-7bdb34f331a5
def attack(c1, c2, e1, e2, N):
    s1 = inverse(e1,e2)
    s2 = int((gmpy2.gcd(e1,e2) - e1 * s1) // e2)
    temp = inverse(c2, N)
    m1 = pow(c1,s1,N)
    m2 = pow(temp,-s2,N)
    return long_to_bytes((m1 * m2) % N)

# Server time will delay abit so brute force the time
for i in range(5):
    random.seed(start_time-i)
    possible_e = []
    # Generate 10 possible e
    for _ in range(10):
        possible_e.append(random.randint(1, n))

    # Generate the combination of 2 possible e
    comb = combinations(possible_e, 2)
    for e1,e2 in list(comb):
        if gmpy2.gcd(e1,e2):
            m = attack(c1, c2, e1, e2, n)
            # If flag format in message found the flag!
            if b"corctf" in m:
                print(m)
# b'corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}\n'

Flag

corctf{y34h_th4t_w4snt_v3ry_h1dd3n_tbh_l0l}