TWCTF 2017 - BabyDLP, BabyRSA, 3Rev

I had sometime at the weekend to play this CTF. One of my favorites CTF, good crypto challenges.

BabyDLP

# Python 3
from signal import alarm
from Crypto.Util.number import *

p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2

bits = size(p)

with open("flag", "r") as f:
    flag = f.readline().strip().encode("latin1")
    m = bytes_to_long(flag)

def run(fin, fout):
    alarm(1200)
    try:
        while True:
            line = fin.readline()[:4+bits//4]
            s = int(line, 16) # Note: input is HEX
            c = pow(g, m ^ s, p)
            fout.write(hex(c) + "\n")
            fout.flush()
    except:
        pass

if __name__ == "__main__":
    run(sys.stdin, sys.stdout)

Alright, so the idea is, giving you prime p 1024 bits, generator g, and ask you to query the flag with parameter as your choice s.

The idea is simple, however it makes this a good challenge because when I approach to the challenge, I approach two ways:

  • Go find a paper, or protocol which has been broken. (many CTFs often apply new techniques follow the industry)

  • Or just algebra Math.

When I saw the challenge, it had very few solves, therefore I ran for the first option.

After 2 hours, I hit myself against the wall. Stuck. Gradually, I saw the solution for the challenge increase dramatically, therefore I realize it would be simple Math.

Finally, with my pen and paper hand on, I wrote down the way I query:

Table 1. Notes
m s Explain

mi

1

mi = 0, g(m_xor_s) changed

m

TWCTF{

Xor with Prefix (1)

mi

0

mi = 0, g(m_xor_s) unchanged

(1) Fail

Ok, so basically I want to control my s parameter xor with m somehow the result won’t changed, as a result, I just have to invert the bit! (because 1_xor_1 = 0, should invert it)

Seem nice. Confuse? More example:

m s Explain

101011

100

g(101011_xor_100) = g(101111) * g100

101011

1

g(101011_xor_1) = g(101010) * g1

101011

10

g(101011_xor_10) = g(101001) * g10

That’s it.

Here is the code. .solve.py

from pwn import *
from Crypto.Util.number import long_to_bytes
from gmpy2 import powmod

p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2

# Connect
r = remote('ppc2.chal.ctf.westerns.tokyo', 28459)
# Total
result = 0
# Get g^m
r.sendline("0")

g_m = int(r.readline(), 16)

for n in range(p.bit_length()):
    # Guess bit, if g_m won't change, we guess correct bit
    # Remember to invert the guess bit
    r.sendline(hex(1 << n))

    server = int(r.readline(), 16)

    temp = g_m * powmod(g, 1 << n, p)
    if server != temp % p :
        # Right guess, invert the bit
        result += (1 << n)


    print n
    print result
    print repr(long_to_bytes(result))

Log

Lesson learned: Try to think simple first.

BabyRSA

This is the challenge I spent most of the time on, very interesting to me. I plan to write the 2nd part of "Recover RSA Private key from MSB of d" someday.

Take a look at the source code:

challenge.rb
p = rand(2**1024)
q = 19 * p + rand(2**512)

p = next_prime(p)
q = next_prime(q)

e = 65537
d = mod_inverse(e, (p - 1) * (q - 1))

n = (p.to_i * q.to_i)

Instantly, when I saw the script, I immediately realise that p and q are constructed. If someone construct primes, these are backdoor

Ok, so how can we find the flag? Clearly, for this challenge, I have to factor N. So I tried:

  • Go to server, tried factor with Yafu.

  • Run script ECM factor.

  • Run Fermat factor.

All failed. Signed.

So I back to math, I need to know something about the p, q, therefore I can factor N.

Let’s use pen and paper, again…​

p = x
q = 19*x + y
N = p*q = x(19*x + y) = 19*x^2 + x*y

Just don’t care about next_prime function, we can get approximate number and then bruteforce the get correct one.

I stuck at this for about 10 hours long. Things I did:

  • Read papers

  • Read papers

  • Back to use pen and paper.

  • Screaming.

  • U@!@)!@)(!)(@)

If you can’t do something, it means you don’t have enough information to do it.
— Some_random_man_or_me

I list all information I know:

  • p: 1024 bits

  • q: 1024 + 512 = 1024 bits where 512 LSB bits changed

  • N: 2052 bits

  • No leakage of p and q.

  • p and q related.

So I had an idea, try to get equation without y (512 bits garbage). To do that, I have to only count first 512 bits of q (well, to remove garbage), the same to p.

Simpler said, I’m going to ignore 512 LSB of q and p

So I have:

Nhigh = p1st_512 * q1st_512 = p1st_512 * (19*p1st_512) = 19*p1*p2 (2)

Where p1 and p2 different is small, so just call them pMSB. Nhigh is 1024 MSB of N.

Ok, let’s find pMSB:

Sage
sage: N = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423
sage: bin(N)[2:][:1024]
'1011111110010001010110000001111011010000111010010111000000100001011110000000000101111010101001100010111100010101011101101110000011111011110011111101101110100110111000010001011000010110010000000000111001110110000110111000100001001100011000110011101000101010001101010100000100011110110011011111010011110101001101010010110111001011011010100001110100010101011001110000000010000000100011000010111011110101100111011111010101100101111101101111000100011001011100110111000101010101010011010110111000111010100011101000100010011010110101001010110010101000100000001011000110010101100100100010101110100111001100101101110001100111111001001001101110101101101111001000100010001001111111100001001100011010010001011011101010010111110001111011111001101111001001001001010100011111001010110101101111111000001010000011001011011011000010010100011111111101100100110100111011110100011011000101001110110001111000101111010111010110100110110000100010000101010110101100010010010100011011001101000100101111110110101011001100011011110110011111110011111001'
sage: N_high = int(bin(N)[2:][:1024],2)
sage: sqrt(N_high/19)
sqrt(134523449446261047453386101401047318321523412047913361207717211757887188920911777081443098535920782738254112327644579637328349527026275421107459432131643183832896351516859288088254483755260307634082365896698236646613880650494822417414283911932804106494480262396118144678580100611190512590908012228499358743801/19)
sage: p_msb = int(sqrt(N_high/19))
2660861054208432925528283166243923571484720040440334967320912362923106576855061934140848053446044925080541859540860254430540104191371349361971373395463759L

Ok, so now we have p_msb, so does q_msb, because the different between them p_msb and q_msb is small. So we can consider they share MSB.

From MSB, I’m going to recover full p and q.

Normally, if q and p are balance primes, I will use this script, just plug and play.

However, the challenge created so well that you have to understand the math underlying, so yeah, script kiddie won’t help you much.

You can take a look at my previous post, we will use similar method to recover full p and q.

The thing is, I only have 512 MSB of pmsb. Don’t worry, Coopersmith can find the rest 512 bits of pmsb for you. It’s magic! :) For now, we will take advance of it.

Relaxed model:

  • p = sqrt(N/19), don’t care about 512 LSB of it, it’s unreliable. We just need its 512 MSB. Check the equation (2), where I made it.

  • So q = 19*p +- delta + rand. Again, it’s not the real q, the rest 512 bits is garbage. Where delta added to make you understand **I assume delta will help us correct q`

  • But we don’t know rand value, so just assume it is 512 bits value. q = 19*p + 2512. You may wonder why, we don’t know rand, we don’t know delta, so let just assume it as a value 2512 and let Sage solve it.

Write it down:

N = p*(19*p + rand)

Modulo both sides to N

0 = p*(19*p + rand)       (mod N) (3)

p != 0, of course. So 19*p + rand must be 0

0 = 19*p + rand           (mod N)

In equation (3), we know half of p, so this is solvable.

solve.sage
N = 386931010476066075837968435835568572278162262133897268076172926477773222237770106161904290022544637634198443777989318861346776496147456733417801969323559935547762053140311065149570645042679207282163944764258457818336874606186063312212223286995796662956880884390624903779609227558663952294861600483773641805524656787990883017538007871813015279849974842810524387541576499325580716200722985825884806159228713614036698970897017484020439048399276917685918470357385648137307211493845078192550112457897553375871556074252744253633037568961352527728436056302534978263323170336240030950585991108197098692769976160890567250487423

_p = int(sqrt(N//19))
_q = 19*_p + 2^512
# Done setting it up
F.<x> = PolynomialRing(Zmod(N), implementation='NTL')
# Set x in ring modulo N
f = x - _q
# Find back +- delta + rand
temp = f.small_roots(X=2**512, beta=0.5)[0]

# Now we got +-delta + rand

if N % (_q + temp) == 0:
    q = _q + temp
elif N % (_q - temp) == 0:
    q = _q - temp

# Now we have recover 512 bits of real `q`


p = N / int(q)

print 'p =', p
print 'q =', q
assert p*int(q) == N
Log
p = 142705255772364982838516531715718191640815441800236739365553038697417755590297275781522823491205105009501621401991866858062431379476890096993289842661379657047660611410332884726411582639930579067910778903846240476718035804927284356419622551632474819703665434429043509042542224222926361726591058189025941965577
q = 2711399859674934673931814102598645641175493394204498047945507735250937356215648239848933646332896995180530806637845470303186196210060911842872507010566213492961135662215921968753949975482648800278196297048045096783128013026497367853790321266446269754792894427483593297724124126249179455165834403387544079388999

Okay, now we have p, q. The work is done here.

Thanks for the very good challenge and good crypto challenge brand for 3 years. I really love them.

Rev_Rev_Rev

This challenge is fairly simple. Each character is mapped one-to-one (hint: ltrace). So just creat a map and then conver the cipher back to plaintext.

I just use encryption phase only, no time to read that bunch of shit.

Here is radare2 script, hope you like it.

solve.py
import r2pipe
import string

def generate_profile(stdin, stdout):
	string = """!/usr/bin/radare2
program=./3rev
stdin="{}"
stdout={}
	""".format(stdin, stdout)
	with open('inout.rr2', 'w') as f:
		f.write(string)


mapped = {}
for i in range(0, len(string.printable), 31):
	_stdin = string.printable[i:i+31]
	generate_profile(_stdin, '')

	r2 = r2pipe.open('./3rev')
	r2.cmd('e dbg.profile=inout.rr2')
	r2.cmd('doo')
	r2.cmd('db 0x0804866c')
	r2.cmd('dc')
	flag = eval(r2.cmd('pcs 32@0x08048870'))
	#print repr(flag)
	_instate = eval(r2.cmd('pcs 32@ `dr eax`'))
	print _stdin, repr(_instate)
	for a,b in zip(_instate, _stdin[::-1]):
		mapped[a] = b

print mapped, len(mapped)

result = ''
for i in flag:
	result += mapped[i]

print repr(result[::-1])
log
$ python solve.py
= attach 6 6
Process with PID 32621 started...
File dbg:///home/cothan/Work/2017/twctf/3rev/3rev  reopened in read-write mode
= attach 32621 32621
Assuming filepath /home/cothan/Work/2017/twctf/3rev/3rev
Selecting and continuing: 32621
hit breakpoint at: 804866c
0123456789abcdefghijklmnopqrstu 'Q\xd11\xb1q\xf1\t\x89I\xc9)\xa9i\xe9\x19\x99Y\xd99\xb9yc\xe3\x13\x93S\xd33\xb3s\xf3\x00'
= attach 6 6
Process with PID 32623 started...
File dbg:///home/cothan/Work/2017/twctf/3rev/3rev  reopened in read-write mode
= attach 32623 32623
Assuming filepath /home/cothan/Work/2017/twctf/3rev/3rev
Selecting and continuing: 32623
hit breakpoint at: 804866c
vwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ '\xa5e\xe5\x15\x95U\xd55\xb5u\xf5\r\x8dM\xcd-\xadm\xed\x1d\x9d]\xdd=\xbd}\xa1a\xe1\x11\x91\x00'
= attach 6 6
Process with PID 32625 started...
File dbg:///home/cothan/Work/2017/twctf/3rev/3rev  reopened in read-write mode
= attach 32625 32625
Assuming filepath /home/cothan/Work/2017/twctf/3rev/3rev
Selecting and continuing: 32625
hit breakpoint at: 804866c
!"#$%&'()*+,-./:;<=>?@[\]^_`{|} 'A\xc1!\xf9\x05\x85E\xc5%\xfd\x03\x83C\xc3#\xa3\x0b\x8bK\xcb+\xabk\xeb\x1b\x9b[\xdb;\xbb{\x00'
= attach 6 6
Process with PID 32627 started...
File dbg:///home/cothan/Work/2017/twctf/3rev/3rev  reopened in read-write mode
= attach 32627 32627
Assuming filepath /home/cothan/Work/2017/twctf/3rev/3rev
Selecting and continuing: 32627
hit breakpoint at: 804866c
~


'\xfb\x81\x00\x00\x00\x07\x00\x00\x00\x02\x00\x00\x00\x80+]\xf7;\x88\x04\x08\x01\x00\x00\x00d\xad\x8b\xffl\xad\x8b'
{'\x00': '~', '\x83': '>', '\x8b': '.', '\x93': '6', '\x9b': '&', '\xa3': ':', '\xab': '*', '\xb3': '2', '\xbb': '"', '\xc3': '<', '\xcb': ',', '\xd3': '4', '\xdb': '$', '\xe3': '8', '\xeb': '(', '\xf3': '0', '\xfb': '\x0c', '\x03': '?', '\x07': ' ', '\x0b': '/', '\x13': '7', '\x1b': "'", '#': ';', '+': '+', '3': '3', ';': '#', 'C': '=', 'K': '-', 'S': '5', '[': '%', 'c': '9', 'k': ')', 's': '1', '{': '!', '\x81': '\x0b', '\x85': '^', '\x89': 'n', '\x8d': 'N', '\x91': 'v', '\x95': 'V', '\x99': 'f', '\x9d': 'F', '\xa1': 'z', '\xa5': 'Z', '\xa9': 'j', '\xad': 'J', '\xb1': 'r', '\xb5': 'R', '\xb9': 'b', '\xbd': 'B', '\xc1': '|', '\xc5': '\\', '\xc9': 'l', '\xcd': 'L', '\xd1': 't', '\xd5': 'T', '\xd9': 'd', '\xdd': 'D', '\xe1': 'x', '\xe5': 'X', '\xe9': 'h', '\xed': 'H', '\xf1': 'p', '\xf5': 'P', '\xf9': '`', '\xfd': '@', '\x05': '_', '\t': 'o', '\r': 'O', '\x11': 'w', '\x15': 'W', '\x19': 'g', '\x1d': 'G', '!': '{', '%': '[', ')': 'k', '-': 'K', '1': 's', '5': 'S', '9': 'c', '=': 'C', 'A': '}', 'E': ']', 'I': 'm', 'M': 'M', 'Q': 'u', 'U': 'U', 'Y': 'e', ']': 'E', 'a': 'y', 'e': 'Y', 'i': 'i', 'm': 'I', 'q': 'q', 'u': 'Q', 'y': 'a', '}': 'A'} 97
'~TWCTF{qpzisyDnbmboz76oglxpzYdk}'

And then it’s done.

Conclusion

So far, I enjoy CTF. So good, I’m in America. Now I can fully concentrate on my passion.

And that’s a good thing.