Codehead's Corner
Random ramblings on hacking, coding, fighting with infrastructure and general tech
Internetwache CTF 2016 – Prime Time – Coding – 60 Points
Posted: 21 Feb 2016 at 23:02 by Codehead

Challenge:

It’s Prime Time! (code60)

Description: We all know that prime numbers are quite important in cryptography. Can you help me to find some?

Service: 188.166.133.53:11059

Solution:

Running netcat against the address gave the following output:

> nc 188.166.133.53 11059
Hi, you know that prime numbers are important, don't you? 
Help me calculating the next prime!
Level 1.: Find the next prime number after 5:

I know the answer to that!, Lets see how far we get doing this manually:

> nc 188.166.133.53 11059
Hi, you know that prime numbers are important, don't you? 
Help me calculating the next prime!
Level 1.: Find the next prime number after 5:
7
Yay, that's right!
Level 2.: Find the next prime number after 15:
17
Yay, that's right!
Level 3.: Find the next prime number after 19:
23
Yay, that's right!
Level 4.: Find the next prime number after 37:
39
Nope, that's just wrong. Try again later!

OK, this is going to need automation. I’ve seen this type of challenge before. Calculating the primes can get quite slow for large numbers, so let’s use a lookup table of pre-calculated primes.

Google quickly provided a text file of the first 10,000 primes.

This needed a quick bit of bash-fu to transform it into a one entry per line list:

cat 10000.txt | tr  [:blank:] '\n' | grep -v "^[[:space:]]*$" > primelist.txt

Next, a bit of python to talk to the server and pull primes from the list:

import sys
from telnetlib import Telnet

def main():

  tn = Telnet('188.166.133.53', 11059)

  for i in range(0,200):
    sys.stdout.write(tn.read_until("the next prime number after ",0.2))
    numstr = tn.read_eager()
    sys.stdout.write(numstr)

    numval = numstr.split(':')
    nxtpr = nextPrime(int(numval[0]))
    sys.stdout.write(nxtpr)
    tn.write(nxtpr)

  print tn.read_all()

  tn.close()


def nextPrime(tp):

  with open('primelist.txt') as f:
    for ln in f.readlines():
      if (int(ln) > tp):
        return ln;

if __name__ == "__main__":
    main()

The output is as follows:

> snip - way too much data before this bit <

Level 95.: Find the next prime number after 584:
587
Yay, that's right!
Level 96.: Find the next prime number after 425:
431
Yay, that's right!
Level 97.: Find the next prime number after 837:
839
Yay, that's right!
Level 98.: Find the next prime number after 44:
47
Yay, that's right!
Level 99.: Find the next prime number after 422:
431
Yay, that's right!
Level 100.: Find the next prime number after 902:
907
Yay, that's right!
IW{Pr1m3s_4r3_!mp0rt4nt}

100 primes! Way too many to type by hand. Interestingly, the request value was never higher than 1000, so on-the-fly calculation would have probably been fine.

Prime Time!

Categories: Hacking CTF

Site powered by Hugo.
Polymer theme by pdevty, tweaked by Codehead