Skip to content

Archives

  • March 2020

Categories

  • ctf
  • security

Copyright Jafar Akhondali 2021 | Theme by ThemeinProgress | Proudly powered by WordPress

  • English
  • فارسی
Jafar AkhondaliYet Another Programmer

SuSeC CTF 2020 – Inaction Writeup (ppc)

ctf . securityOn 2020-03-19 by Jafar
زمان مطالعه: 3 دقیقه

Below is the writeup for a programming challenge in SuSec CTF 2020.
The source code is given as follow:

import re, sys, os, signal, string, random
from hashlib import *
from secret import flag

p = 2**2281 - 1
s = 2**228
pad = 2228

def idle_square(x, toil, pad):
    for i in range(toil):
        x = pow(x ^ pad, 2, p)
    return x

def gen_chall(toil):
	x = random.randint(1, s)
	return [x, toil, pad]

def main():
	pr("-"*72)
	pr("|" + " hi all, in each level try to solve given challenge ".center(70) + "|")
	pr("-"*72)
	stage = 40
	for i in range(stage):
		x, toil, pad = gen_chall(stage)
		y = idle_square(x, toil, pad)
		pr('y =', y)
		pr('please send solution:')
		ans = sc()
		try:
			ans = int(ans)
		except:
			die('Sorry, the given answer is not integer! Bye!!')
		if ans == x:
			if i == 39:
				die('Congratz! You got the flag:', flag)
			else:
				pr('Great! Please solve the next level :P')
		else:
			die('Your answer is not correct, try again, Bye!')

Basically all the operation is happening in idle_square funcion. In 40 rounds, the chosen x (which we have to find its value) will first get XOR-ed by a constant (pad) and then is powered by 2 in the field of another constant(p).

This part of the problem is a typic in cryptographic called modular square root which is solvable using Shanks algorithm. However, since the power is 2 there should be two possible answers for each round unless the Shanks algorithm fails. So there would be at most 2**40 possible answers for this challenge. I’ve traced the code manually and found out in first step (which we have the initial value of x) the x is slightly smaller than other possible answers.

I’ve modified this Shanks implementation a little to work with large numbers and put the function in the back-track algorithm. Hopefully in many places, the Shanks algorithm fails (meaning there is not a valid step to go further) and this will dramatically reduce our calculations.

p = 2**2281 - 1
s = 2**228
pad = 2228

all = []
def solve(y, stage):
    if stage <= 0:
        all.append(y)
        return
    possible_current_stage_answers = prime_mod_sqrt(y, p)
    for possible_current_stage_answer in possible_current_stage_answers:
        x = (possible_current_stage_answer ^ pad) % p
        solve(x, stage - 1)

solve(y, 40)
x = min(all)

Now, all is left is to connect to server and repeat these steps. We have to repeat these steps 40 times and provide valid X to get flag. Whole code is attached for readabily:

from pwn import *


def legendre_symbol(a, p):
    """
    Legendre symbol
    Define if a is a quadratic residue modulo odd prime
    http://en.wikipedia.org/wiki/Legendre_symbol
    """
    ls = pow(a, (p - 1)//2, p)
    if ls == p - 1:
        return -1
    return ls

def prime_mod_sqrt(a, p):
    """
    Square root modulo prime number
    Solve the equation
        x^2 = a mod p
    and return list of x solution
    http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm
    """
    a %= p

    # Simple case
    if a == 0:
        return [0]
    if p == 2:
        return [a]

    # Check solution existence on odd prime
    if legendre_symbol(a, p) != 1:
        return []

    # Simple case
    if p % 4 == 3:
        x = pow(a, (p + 1)//4, p)
        return [x, p-x]

    # Factor p-1 on the form q * 2^s (with Q odd)
    q, s = p - 1, 0
    while q % 2 == 0:
        s += 1
        q //= 2

    # Select a z which is a quadratic non resudue modulo p
    z = 1
    while legendre_symbol(z, p) != -1:
        z += 1
    c = pow(z, q, p)

    # Search for a solution
    x = pow(a, (q + 1)//2, p)
    t = pow(a, q, p)
    m = s
    while t != 1:
        # Find the lowest i such that t^(2^i) = 1
        i, e = 0, 2
        for i in range(1, m):
            if pow(t, e, p) == 1:
                break
            e *= 2

        # Update next value to iterate
        b = pow(c, 2**(m - i - 1), p)
        x = (x * b) % p
        t = (t * b * b) % p
        c = (b * b) % p
        m = i

    return [x, p-x]

p = 2**2281 - 1
s = 2**228
pad = 2228

all = []
def solve(y, stage):
    global all
    if stage <= 0:
        all.append(y)
        return
    possible_current_stage_answers = prime_mod_sqrt(y, p)
    for possible_current_stage_answer in possible_current_stage_answers:
        x = (possible_current_stage_answer ^ pad) % p
        solve(x, stage - 1)


s = remote('66.172.27.57', 3114)

for i in range(1,41):
    y = int(s.recvline_contains('y = ')[4:])
    s.recvline_contains("please send solution:\n")
    print("[*] ------- Step {} ------- ".format(i))
    print("[*] Got new y: {}".format(y))
    solve(y, 40)
    x = min(all)
    all = []
    print("[*] Valid x : {}".format(x))
    s.sendline(str(x))

s.interactive()

And after a while, we get the flag:

Congratz! You got the flag: SUSEC{5m4Rt___p0W___cH4lL3n93}

1

مثل این مطلب:

SuSeC CTF 2020 - Little
SuSec CTF 2020 - Web 0

Write a Reply or Comment Cancel reply

Your email address will not be published.

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

It’s Me

سلام، من جعفرم و سعی میکنم توی حوزه برنامه نویسی و امنیت مطالبی رو بزارم که کمتر در موردشون صحبت شده. بعضی از پست هارو فقط با زبان انگلیسی منتشر کردم

  • twitter
  • twitter
  • linkedin
  • github
  • telegram
  • telegram
Preloaded shit
  • فارسیفارسی
  • EnglishEnglish

Categories

  • security (3)
    • ctf (2)