PicoCTF 2017 - Crypto Challenges

Datetime:2017-04-20 05:32:59         Topic: Encryption and Decryption          Share        Original >>
Here to See The Original Article!!!

So, here's my first set of Pico solutions. I've started with the crypto for now. For those of you who don't fancy reading through, here are some links to each one.

Keyz

This one's trivial. Run ssh-keygen , cat ~/.ssh/id_rsa.pub and copy the public key, then in the web shell, mkdir .ssh; echo "[public key]" > ~/.ssh/authorized_keys

Then, just ssh in and the flag's in the MOTD

Flag: who_needs_pwords_anyways

Substitute

A wizard (he seemed kinda odd...) handed me this. Can you figure out what it says?

This one is also pretty trivial. Looking at the message, and the name of the challenge, just guess that it's a simple substitution cipher. Take the ciphertext you're given, and paste it into quipqiup . A few moments later, you get the flag

Flag: IFONLYMODERNCRYPTOWASLIKETHIS

Hash101

This one consists of four separate levels.

Welcome to Hashes 101!

There are 4 Levels. Complete all and receive a prize!


-------- LEVEL 1: Text = just 1's and 0's --------
All text can be represented by numbers. To see how different letters translate to numbers, go to http://www.asciitable.com/

TO UNLOCK NEXT LEVEL, give me the ASCII representation of 0110100001100101011011000110110001101111

For this one, just convert the binary through to ASCII however you like. It turns out to be hello

The next level is just as easy:

------ LEVEL 2: Numbers can be base ANYTHING -----
Numbers can be represented many ways. A popular way to represent computer data is in base 16 or 'hex' since it lines up with bytes very well (2 hex characters = 8 binary bits). Other formats include base64, binary, and just regular base10 (decimal)! In a way, that ASCII chart represents a system where all text can be seen as "base128" (not including the Extended ASCII codes)

TO UNLOCK NEXT LEVEL, give me the text you just decoded, hello, as its hex equivalent, and then the decimal equivalent of that hex number ("foo" -> 666f6f -> 6713199)

hex>

Convert "hello" to hex, and you get 68656c6c6f

hex>68656c6c6f  
Good job! 68656c6c6f to ASCII -> hello is hello  
Now decimal  
dec>

Convert 0x68656c6c6f to decimal, and you get 448378203247

The next level introduces a simple modular hash function.

----------- LEVEL 3: Hashing Function ------------
A Hashing Function intakes any data of any size and irreversibly transforms it into a fixed-length number. For example, a simple Hashing Function could be to add up the sum of all the values of all the bytes in the data and get the remainder after dividing by 16 (modulus 16)

TO UNLOCK NEXT LEVEL, give me a string that will result in a 0 after being transformed with the mentioned example hashing function

>

In this case, the hash function on a single character c is simply c % 0x10 . Therefore, let's just use 0x50, or E

One more level....

--------------- LEVEL 4: Real Hash ---------------
A real Hashing Function is used for many things. This can include checking to ensure a file has not been changed (its hash value would change if any part of it is changed). An important use of hashes is for storing passwords because a Hashing Function cannot be reversed to find the initial data. Therefore if someone steals the hashes, they must try many different inputs to see if they can "crack" it to find what password yields the same hash. Normally, this is too much work (if the password is long enough). But many times, people's passwords are easy to guess... Brute forcing this hash yourself is not a good idea, but there is a strong possibility that, if the password is weak, this hash has been cracked by someone before. Try looking for websites that have stored already cracked hashes.

TO CLAIM YOUR PRIZE, give me the string password that will result in this MD5 hash (MD5, like most hashes, are represented as hex digits):  
d63d5efad4a59c06228d0596a89e2a34

Just look up the hash on any of the myriad hash lookup services . In this case, the hash is of 3mb0x . So, finally, we get our flag!

Correct! Completed level 4  
You completed all 4 levels! Here is your prize: c3ee093f26ba147ccc451fd13c91ffce

Flag: c3ee093f26ba147ccc451fd13c91ffce

ComputeAES

We get the following info:

Encrypted with AES in ECB mode. All values base64 encoded  
ciphertext = rW4q3swEuIOEy8RTIp/DCMdNPtdYopSRXKSLYnX9NQe8z+LMsZ6Mx/x8pwGwofdZ  
key = 6v3TyEgjUcQRnWuIhjdTBA==

So, we open up a python REPL:

>>> from Crypto.Cipher import AES
>>> from base64 import b64decode
>>> cipher = AES.AESCipher(b64decode("6v3TyEgjUcQRnWuIhjdTBA=="), AES.MODE_ECB)
>>> print cipher.decrypt(b64decode("rW4q3swEuIOEy8RTIp/DCMdNPtdYopSRXKSLYnX9NQe8z+LMsZ6Mx/x8pwGwofdZ"))
flag{do_not_let_machines_win_983e8a2d}_________

Oooh, look, a flag.

Flag: flag{do_not_let_machines_win_983e8a2d}

ComputeRSA

Also trivial.

RSA encryption/decryption is based on a formula that anyone can find and use, as long as they know the values to plug in. Given the encrypted number 150815, d = 1941, and N = 435979, what is the decrypted number?
>>> pow(150815, 1941, 435979)
133337L

Flag: 133337

SoRandom

We found sorandom.py running at shell2017.picoctf.com:33123. It seems to be outputting the flag but randomizing all the characters first. Is there anyway to get back the original flag?  
Update (text only) 16:16 EST 1 Apr Running python 2 (same version as on the server)

First of all, let's take a look at the server code:

#!/usr/bin/python -u
import random,string

flag = "FLAG:"+open("flag", "r").read()[:-1]  
encflag = ""  
random.seed("random")  
for c in flag:  
  if c.islower():
    #rotate number around alphabet a random amount
    encflag += chr((ord(c)-ord('a')+random.randrange(0,26))%26 + ord('a'))
  elif c.isupper():
    encflag += chr((ord(c)-ord('A')+random.randrange(0,26))%26 + ord('A'))
  elif c.isdigit():
    encflag += chr((ord(c)-ord('0')+random.randrange(0,10))%10 + ord('0'))
  else:
    encflag += c
print "Unguessably Randomized Flag: "+encflag

So, it's generating a fixed "rotated" alphabet, based on a PRNG with a known seed. We can generate the inverse of this shift by simply replacing + with - , then pull the scrambled flag from the server. This leads us to the following:

#!/usr/bin/python -u
import random,string

flag = "BNZQ:2m8807395d9os2156v70qu84sy1w2i6e"  
encflag = ""  
random.seed("random")  
for c in flag:  
  if c.islower():
    #rotate number around alphabet a random amount
    encflag += chr((ord(c)-ord('a')-random.randrange(0,26))%26 + ord('a'))
  elif c.isupper():
    encflag += chr((ord(c)-ord('A')-random.randrange(0,26))%26 + ord('A'))
  elif c.isdigit():
    encflag += chr((ord(c)-ord('0')-random.randrange(0,10))%10 + ord('0'))
  else:
    encflag += c
print "Unguessably Randomized Flag: "+encflag

Run it, and we get a flag.

Flag: FLAG:9b6098160b2ca5139c83fe29fd7c9e5d

LeakedHashes

Someone got hacked! Check out some service's password hashes that were leaked at hashdump.txt! Do you think they chose strong passwords? We should check... The service is running at shell2017.picoctf.com:3815!

Download the hash list that we're given, and run hashcat against it:

hashcat64 -a 0 -m 0 --username pico.txt rockyou.txt

Now show us the results, and see if we've cracked anything...

E:\Users\Ben\Documents\hashcat-3.20>hashcat64 -a 0 -m 0 --username pico.txt rockyou.txt --show  
roselyn:189dbb843e5420471ba9f10f03d8e9dc:m0n3y

So now we have creds roselyn:m0n3y . Use those to log into the service, and hit y . You'll get a bunch of ASCII art cats, and a flag somewhere amongst them.

Flag: 4f36a002cc953e6567a878758abc8cf9

Weird RSA

We recovered some data. It was labeled as RSA, but what in the world are "dq" and "dp"? Can you decrypt the ciphertext for us?

Okay, we're given some RSA parameters, including a "dp" and "dq". A little research reveals that those are used in a fast algorithm for RSA decryption based on the Chinese Remainder Theorem. These are our parameters:

c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885  
p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243  
q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629  
dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961  
dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

So, we find a nice guide on how to use them, go off, and do just that.

Flag: Theres_more_than_one_way_to_RSA

HashChain

We found a service hiding a flag! It seems to be using some kind of MD5 Hash Chain authentication to identify who is allowed to see the flag. Maybe there is a flaw you can exploit? hcexample.py has some example code on how to calculate iterations of the MD5 hash chain. Connect to it at shell2017.picoctf.com:50102!

So, this is a simple hash chain authentication scheme, where we authenticate by finding the hash in the chain prior to the "challenge" hash presented by the server. On connecting to the service, we are presented with the following options:

*******************************************
***            FlagKeeper 1.1           ***
*  now with HASHCHAIN AUTHENTICATION! XD  *
*******************************************

Would you like to register(r) or get flag(f)?

r/f?

Let's have a look at the registration...

r  
Hello new user! Your ID is now 9831 and your assigned hashchain seed is a62dd1eb9b15f8d11a8bf167591c2f17  
Please validate your new ID by sending the hash before this one in your hashchain (it will hash to the one I give you):  
7487f1eb2ff4cd1f60326ff74e1728a7

Hmmm, that hashchain seed looks a lot like an MD5 hash in and of itself. Could it simply be the hash of the user ID?

md5("9831") = a62dd1eb9b15f8d11a8bf167591c2f17

That's a yes. Now, let's look at the get flag option...

f  
This flag only for user 8886  
Please authenticate as user 8886  
58a116a80bcdb2ed23423a49f5bfaabd  
Next token?

So, we can use the provided hc_example.py with a seed of "8886" to generate a bunch of hashes and see when 58a116a80bcdb2ed23423a49f5bfaabd comes up.

...
40249f4dcc725e5baf3cd6f959243273  
58a116a80bcdb2ed23423a49f5bfaabd  
...

So, our next token is 40249f4dcc725e5baf3cd6f959243273 . Giving that to the service gives us our flag!

Flag: 96630f954dd403c7882666b5443e4678

Broadcast

You stumbled upon a group Message. Can you figure out what they were sending? The string sent is ASCII encoded as a hex number (submit the ASCII string as the flag)

We use Håstad's broadcast attack (Clue's in the name). This attack is applicable where multiple messages are encrypted with the same e and different n , and allows us to leak the message without knowledge of d . Using this algorithm will output the flag.

Flag: broadcast_with_small_e_is_killer_26528074390

SmallRSA

You intercepted a single message. However, it appears to be encrypted. Can you decrypt it?

First off, let's look at the information we have:

e = 165528674684553774754161107952508373110624366523537426971950721796143115780129435315899759675151336726943047090419484833345443949104434072639959175019000332954933802344468968633829926100061874628202284567388558408274913523076548466524630414081156553457145524778651651092522168245814433643807177041677885126141  
n = 380654536359671023755976891498668045392440824270475526144618987828344270045182740160077144588766610702530210398859909208327353118643014342338185873507801667054475298636689473117890228196755174002229463306397132008619636921625801645435089242900101841738546712222819150058222758938346094596787521134065656721069  
c = 60109758698128083867894286068285517856121577775873732971271767838094375540242140682860856525076716857853484762310661349595705965454241788627490154678487289327504291223547525832864143253412180183596307295520420578906308624860023542143928885210079178897416418810270090406582415840515326539954964020452551186119

That e value is unusually large, where you'd usually something like e = 65537 . This suggests that d is quite small - hence the name of the challenge, probably. In this case, we can use Wiener's Attack to efficiently find the decryption key, d .

Using the attack, then, easily gets us d and allows us to decrypt the flag.

Flag: flag{Are_any_RSA_vals_good_13441315963}

SmallSign

This service outputs a flag if you can forge an RSA signature!  
nc shell2017.picoctf.com 10650  
smallsign.py

So, some sort of a signature forging challenge. Let's look at the server code, for starters.

#!/usr/bin/python -u

from Crypto.PublicKey import RSA  
import random  
import signal

key = RSA.generate(2048)  
flag = open("./flag").read()

print "You have 60 seconds to forge a signature! Go!"  
# In 60 seconds, deliver a SIGALRM and terminate
signal.alarm(60)

print "N:", key.n  
print "e:", key.e

while True:  
    m = int(raw_input("Enter a number to sign (-1 to stop): "))
    if m == -1:
        break
    sig = key.sign(m, None)
    print "Signature:", str(sig[0])

challenge = random.randint(0, 2**32)  
print "Challenge:", challenge  
s = int(raw_input("Enter the signature of the challenge: "))  
if key.verify(challenge, (s, None)):  
    print "Congrats! Here is the flag:", flag
else:  
    print "Nope, that's wrong!"

So, we can get signatures for arbitrary numbers, and then submit a signature, given known (per attempt) values of n and e . In order to forge the signature, then, we rely on the fact that RSA encryption and decryption is multiplicative - that is:

decrypt(m1) * decrypt(m2) % N = decrypt(m1 * m2)

This leads us to the following process:

  • Sign a bunch of the first few primes - as many as the 60-second limit allows.
  • Factorise the challenge
  • Pray to RNGesus that the prime factors of the challenge only include those which we've signed. If that's not the case, then try again.
  • Compute the signature using the multiplicative property by multiplying the signatures of all the prime factors
  • Submit result
  • Get flag

I implemented this really rather inelegantly, but eh, it worked. This one, in particular, can take a long time to run - it relies on the RNG generating a challenge with small enough factors, and takes ~1min per run.

import socket  
def factor(n, startFrom=2):  
    """returns a list of prime factors of n,
    knowing min possible >= startFrom."""
    if n <= 1:  return [ ]
    d = startFrom
    factors = [ ]
    while n >= d*d:
      if n % d == 0:
        factors.append(d)
        n = n/d
      else:
        d += 1 + d % 2  # 2 -> 3, odd -> odd + 2
    factors.append(n)
    return factors

def listPrimes(n):  
    '''Return a list of all primes < n using the Sieve of Eratosthenes.'''
    if n <= 2:  return []
    sieve = [True]*n # indices 0 ... n-1, ignore 1 and even.  Entries at odd 
        #  indices greater than 2 will be changed to false when found not prime 
    primes = [2]
    i = 3
    while(i < n):
        if sieve[i]:  # First number not eliminated must be prime
            primes.append(i)      # next eliminate multiples of i:  
            for mult in range(i*i, n, i): # Note multiples with a smaller 
                sieve[mult] = False       #   factor are already eliminated
        i += 2  # skip even numbers
    return primes

primes = listPrimes(1050)  
def attempt():  
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('shell2017.picoctf.com', 10650))
    s.recv(1024)
    d = s.recv(1024).split('\n')
    n = int(d[1][3:])
    e = int(d[2][3:])
    sigs = {}
    for prime in primes:
        s.send(str(prime) + "\n")
        s.recv(1024)
        sigs[prime] = int(s.recv(1024).split('\n')[0])
    s.send("-1\n")
    s.recv(1024)
    challenge = int(s.recv(1024).split('\n')[0])
    f = factor(challenge)
    rt = 1
    for fact in f:
        if fact in sigs:
            rt = (rt * sigs[fact]) % n
        else:
            print "FAIL - No signature for %d" % fact
            return False
    s.send(str(rt) + "\n")
    print s.recv(1024)
    print s.recv(1024)
    print s.recv(1024)
    print s.recv(1024)
    return True
r = False  
while r == False:  
    r = attempt()

Eventually, this gives us the flag.

Flag: 6298123dbccaf021eed3c55c79a806a3

Encrypted Shell

This service gives a shell, but it's password protected! We were able intercept this encrypted traffic which may contain a successful password authentication. Can you get shell access and read the contents of flag.txt?  
The service is running at shell2017.picoctf.com:30754.

First off, let's start by looking at the server code so that we have an idea of what the hell we're dealing with here.

#!/usr/bin/python2 -u
from hashlib import sha256  
from Crypto import Random  
from Crypto.Random import random  
from Crypto.Cipher import AES  
from subprocess import check_output, STDOUT, CalledProcessError

BLOCK_SIZE = 16  
R = Random.new()

with open("parameters.txt") as f:  
    p = int(f.readline().strip())
    g = int(f.readline().strip())

password = open("password.txt").read()

def pad(m):  
    o = BLOCK_SIZE - len(m) % BLOCK_SIZE
    return m + o * chr(o)

def unpad(p):  
    return p[0:-ord(p[-1])]

def send_encrypted(KEY, m):  
    IV = R.read(BLOCK_SIZE)
    aes = AES.new(KEY, AES.MODE_CBC, IV)
    c = aes.encrypt(pad(m))
    print (IV + c).encode('hex')

def read_encrypted(KEY):  
    data = raw_input("").decode('hex')
    IV, data = data[:BLOCK_SIZE], data[BLOCK_SIZE:]
    aes = AES.new(KEY, AES.MODE_CBC, IV)
    m = unpad(aes.decrypt(data))
    return m

def serve_commands(KEY):  
    while True:
        cmd = read_encrypted(KEY)
        try:
            output = check_output(cmd, shell=True, stderr=STDOUT)
        except CalledProcessError as e:
            output = str(e) + "\n"
        send_encrypted(KEY, output)

print """Welcome to the  
______ _   _   _____ _          _ _  
|  _  \ | | | /  ___| |        | | |
| | | | |_| | \ `--.| |__   ___| | |
| | | |  _  |  `--. \ '_ \ / _ \ | |
| |/ /| | | | /\__/ / | | |  __/ | |
|___/ \_| |_/ \____/|_| |_|\___|_|_|
"""

print "Parameters:"  
print "p = {}".format(p)  
print "g = {}".format(g)

a = random.randint(1, 2**46)  
A = pow(g, a, p)  
print "A = {}".format(A)

B = int(raw_input("Please supply B: "))  
K = pow(B, a, p)

KEY = sha256(str(K)).digest()

pw = read_encrypted(KEY)  
if pw == password:  
    serve_commands(KEY)
else:  
    send_encrypted("Invalid password!\n")

So, basically, it performs a Diffie-Hellman Key Exchange and then authenticates via a password. Therefore, presumably, we need to follow a plan of attack something like:

  • Break the Diffie-Hellman exchange in the traffic capture to get the shared key
  • Decrypt the password
  • Connect to the server, exchange keys and authenticate with the password
  • cat flag.txt
  • Read our result out.

In order to do the first part, we'll need to calculate the discrete logarithm of one of the public values A or B modulo P. Fortunately, there appear to be some weak choices of parameter...

a = random.randint(1, 2**46)

This known, small bound on the value of a allows us to use the Baby-Step Giant-Step algorithm to compute the discrete logarithm of A fairly quickly and recover a . Let's look at the code.

import gmpy  
from gmpy import mpz

# Inputs to the algorithm
p=mpz([p from pcap])  
g=mpz([g from pcap])  
h=mpz([A from pcap])

hTable = {}

def main():  
    i = mpz(0)
    j = mpz(0)
    gI = gmpy.invert(g,p)
    B = pow(2,23)
    gC = pow(g,B,p)
    while i <= B:
        hTable[(h * pow(gI, i, p)) % p]=i
        i = i + 1
    print "Hash table created!"
    while j <= B:
        rhs = pow(gC, j, p)
        if rhs in hTable:
            i=hTable[rhs]
            break
        j = j + 1
    print "Result: ",i,j,j*B+i

if __name__ == "__main__":  
    main()

After a few minutes, this spits out our discrete logarithm. We now know that a = 18999223985004

With this knowledge, it's trivial to find our private key, and then our password:

from hashlib import sha256  
from Crypto import Random  
from Crypto.Random import random  
from Crypto.Cipher import AES  
g = 41899070570517490692126143234857256603477072005476801644745865627893958675820606802876173648371028044404957307185876963051595214534530501331532626624926034521316281025445575243636197258111995884364277423716373007329751928366973332463469104730271236078593527144954324116802080620822212777139186990364810367977  
a = 18999223985004  
gb = 52212067689594112109323640929301351606467118203383150327599211883168430054342124696361946771882317563613814253170561126339826644357001686458446188458014200762135544004281320619787980315833659890517041361133454035724795056335268420608527814057585862519036050687522158793940953574062642063690400491833858296879  
p = 174807157365465092731323561678522236549173502913317875393564963123330281052524687450754910240009920154525635325209526987433833785499384204819179549544106498491589834195860008906875039418684191252537604123129659746721614402346449135195832955793815709136053198207712511838753919608894095907732099313139446299843  
K = pow(gb, a, p)  
R = Random.new()  
key=sha256(str(K)).digest()  
BLOCK_SIZE = 16

def unpad(p):  
    return p[0:-ord(p[-1])]


def read_encrypted(KEY, data):  
    data = data.decode('hex')
    IV, data = data[:BLOCK_SIZE], data[BLOCK_SIZE:]
    aes = AES.new(KEY, AES.MODE_CBC, IV)
    m = unpad(aes.decrypt(data))
    return m

passwd = read_encrypted(key, "1a30a68af458370dfdcbbe6fb7112bf20488eea7f1203ffbb6510879ed71e79186bb45643e269e638b36d2102e130f3cc6c520a58f2ed892693f967b1be7783b")  
print passwd

Let this run through, and we get the password: ThisIsMySecurePasswordPleaseGiveMeAShell

Finally, we need to get through those last couple of stages to get our flag. Let's write a simple client up.

import socket  
from hashlib import sha256  
from Crypto import Random  
from Crypto.Random import random  
from Crypto.Cipher import AES  
from subprocess import check_output, STDOUT, CalledProcessError

BLOCK_SIZE = 16  
R = Random.new()  
s = socket.socket()  
def pad(m):  
    o = BLOCK_SIZE - len(m) % BLOCK_SIZE
    return m + o * chr(o)
def unpad(p):  
    return p[0:-ord(p[-1])]
def send_encrypted(KEY, m):  
    IV = R.read(BLOCK_SIZE)
    aes = AES.new(KEY, AES.MODE_CBC, IV)
    c = aes.encrypt(pad(m))
    out = (IV + c).encode('hex')
    s.send(out + "\n")

def read_encrypted(KEY, data):  
    data = data.decode('hex')
    IV, data = data[:BLOCK_SIZE], data[BLOCK_SIZE:]
    aes = AES.new(KEY, AES.MODE_CBC, IV)
    m = unpad(aes.decrypt(data))
    return m
def read_until(msg):  
    r = s.recv(1)
    while msg not in r:
        r += s.recv(1)
    return r
def readline():  
    return read_until("\n")[:-1]

s.connect(("shell2017.picoctf.com", 30754))  
for _ in xrange(9):  
    readline()
p = int(readline().split(" ")[2])  
g = int(readline().split(" ")[2])  
A= int(readline().split(" ")[2])  
s.recv(64)  
b = 2  
B = pow(g, b, p)  
s.send(str(B) + "\n")  
KEY = sha256(str(pow(A, b, p))).digest()  
send_encrypted(KEY, "ThisIsMySecurePasswordPleaseGiveMeAShell\n")  
send_encrypted(KEY, "cat flag.txt\n")  
print "FLAG: " + read_encrypted(KEY, readline())

Run this, and we get our flag back.

Flag: 908bf62fb191fd53a6a91e21774b8e7a

ECC2

More elliptic curve cryptography fun for everyone!  
handout.txt  
(Yes, the flag will just be the number n.)

Okay, an ECC challenge. I don't know much about ECC...

Elliptic Curve: y^2 = x^3 + A*x + B mod M  
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089  
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785  
B = *You can figure this out with the point below :)*

P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)  
n = *SECRET*  
n*P = (84451374362414055424313800316751686580646332049899422670338102989180879521718, 43738739399518925611438079326671646924823599185742673040934524615350311254357)

n < 400000000000000000000000000000

Find n.

Ah, that makes things a little clearer. Firstly, let's find B. It's but a simple python script away, as per usual.

M = 93556643250795678718734474880013829509320385402690660619699653921022012489089  
A = 66001598144012865876674115570268990806314506711104521036747533612798434904785  
P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)

lhs = (P[1] ** 2) % M  
rhs = (P[0] ** 3) + (P[0] * A) % M  
print "B = %d" % ((lhs - rhs) % M)

B = 25255205054024371783896605039267101837972419055969636393425590261926131199030

Okay, so now we have all of our curve parameters, we still need to find the value of n. In order to do this, we'll need to discover a little bit more information about our curve. One important property of the curve is the order of the generator point P. If it's smooth, we can reduce the problem into much smaller and more easily manageable ECDLPs and use the Chinese Remainder Theorem to combine these into our final value of n . This process is the Pohlig-Hellman Algorithm.

In order to test that, we'll use SageMath, which will be the tool of choice from here on. The code is stil quite brief:

q = 93556643250795678718734474880013829509320385402690660619699653921022012489089  
F = GF(q)  
E = EllipticCurve(F, [66001598144012865876674115570268990806314506711104521036747533612798434904785,25255205054024371783896605039267101837972419055969636393425590261926131199030])  
P = E(56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)  
Q = E(84451374362414055424313800316751686580646332049899422670338102989180879521718, 43738739399518925611438079326671646924823599185742673040934524615350311254357)  
print factor(P.order())

2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569 * 106831998530025000830453 * 1975901744727669147699767

Now, this does look quite interestingly smooth, so maybe Pohlig-Hellman is a good algorithm to use. However, those last two factors, in particular, look very large compared to the rest, so they'll probably add a vast amount to the computation time required. As this is a CTF, they're not going to make it take that much compute time, so we simply hand-wave and ignore those two factors. This leads us to the following code:

def pohlig_hellman(curve, G, H):  
    N = curve.order()
    factors = factor(N)[:-2]
    x = 0
    y = 1
    for i in range(len(factors)):
        ni = factors[i][0]**(factors[i][1])
        y *= ni
        tmp = N//ni
        G_prime = tmp * G
        H_prime = tmp * H
        x_prime = G_prime.discrete_log(H_prime)
        (gcd, x0, x1) = xgcd(ni, tmp)
        x += x_prime*x1*tmp
    return x % y

q = 93556643250795678718734474880013829509320385402690660619699653921022012489089  
F = GF(q)  
E = EllipticCurve(F, [66001598144012865876674115570268990806314506711104521036747533612798434904785,25255205054024371783896605039267101837972419055969636393425590261926131199030])  
P = E(56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926)  
Q = E(84451374362414055424313800316751686580646332049899422670338102989180879521718, 43738739399518925611438079326671646924823599185742673040934524615350311254357)  
print factor(P.order())  
s = pohlig_hellman(E, P, Q)

print "Is this correct? " + repr(P * s == Q)  
print s

2^2 * 3 * 5 * 7 * 137 * 593 * 24337 * 25589 * 3637793 * 5733569 * 106831998530025000830453 * 1975901744727669147699767  
Is this correct? True  
300455670009368164962892984010

The value of n , our flag, is that last number, and it is verified by the script.

Flag: 300455670009368164962892984010

Weirder RSA

Another message encrypted with RSA. It looks like some parameters are missing. Can you still decrypt it? Message

Missing parameters. How interesting. Let's see what we've got...

e = 65537  
n = 352758655756163603130656475864162239004344663459120398951306959672239055329877644796995008368282924624780849432051543118959312685532106237568240835778731486989439626252834661294225426875963944816709371554839452465119058016363040631618359944564550348310851045841670935254841385590882490443247265126417117450357  
dp = 13530055667815347122266109008252377134325151556131892235929064596659462917644020624855537451062167377041847601387880412738836767351591511886432133011921729  
c = 23428056833770750219439218340180501853506449797628734848807388355447212714387039203998085387476974936419607861041793755542930286287098871510394661091846780839592290953853536571372997807697657464569729651718518301857979495046280018444198435962234642736892075369840282923945267377104440625478468507147243879631

Okay, so it's CRT-RSA without dq or qinv . That means we can't decrypt straight off. Fortunately, a little google finds us a paper with a key recovery method that lets us factorise n and thus find the decryption key. Let's throw something together...

from fractions import gcd

def egcd(a, b):  
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):  
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

e = 65537  
n = 352758655756163603130656475864162239004344663459120398951306959672239055329877644796995008368282924624780849432051543118959312685532106237568240835778731486989439626252834661294225426875963944816709371554839452465119058016363040631618359944564550348310851045841670935254841385590882490443247265126417117450357  
dp = 13530055667815347122266109008252377134325151556131892235929064596659462917644020624855537451062167377041847601387880412738836767351591511886432133011921729  
c = 23428056833770750219439218340180501853506449797628734848807388355447212714387039203998085387476974936419607861041793755542930286287098871510394661091846780839592290953853536571372997807697657464569729651718518301857979495046280018444198435962234642736892075369840282923945267377104440625478468507147243879631

m1 = 3  
c1 = pow(m1, e, n)  
mp = pow(c1, dp, n)  
p = gcd(m1 - mp, n)  
q = n / p  
d = modinv(e, (p-1) * (q - 1))  
m = pow(c, d, n)  
print hex(m)[2:-1].decode("hex")

The code implements the method described in the paper. Run it, get flag, ???, profit.

Flag: flag{wow_leaking_dp_breaks_rsa?_47413771836}








New