pwnEd2 Writeups: Crypto

CTF WriteupspwnEd2

28 Feb

AES_ECB_VS_CBC

I get my block cipher modes confused all the time, tell them apart for me and i will tell you a motmot secret :) (typo its 0 for CBC)

nc 34.105.193.206 12003

Author: Thrypuro

Connecting to the service, we can choose some plaintext and then guess if the ciphertext we receive is ECB or CBC.

└──╼ $nc 34.105.193.206 12003
Send your input and recognise which mode of AES encryption it is for a certain number of time and then get the flag
Enter your plaintext 
hello world
{'cipertext ': '8f6cff66360bbf23cb4c2d83fe7e4011'}
Input 1 for ECB and 0a for CBC 
1
Wrong, too bad, will have to reset your counter now
Enter your plaintext 
hello hello
{'cipertext ': 'cc66c673b9409f3039b2b7e31b37e4db'}
Input 1 for ECB and 0a for CBC 
0
1 consecutive guesses!

For anyone not familiar: ECB and CBC are two different block cipher modes for encrypting multiple blocks of plaintext. ECB stands for electronic code book, and is the most simple method: split the input into blocks, encrypt each separately, then concatenate the result. CBC stands for cipher block chaining, and will XOR the result of the previous ciphertext block with the current plaintext before encrypting it. The first block doesn't have a previous one, so we generate an (ideally) random number called the initialisation vector (IV) and send that as the 0th block of the ciphertext.

There's a couple of ways of tackling this. The one I chose uses the fact that encrypting multiple blocks is handled differently in the two modes: ECB will keep them separate, whereas CBC combines them. This means if ECB handles the same block twice, it'll give the same result; CBC will give a different value in the second block. I then made a script to send the same 32 0's message and compare the first and second blocks of the message:

# Ommitted: telnet setup, readline(), json_recv()
# readline prints each output after reading it
readline()
while True:
    readline()
    tn.write(b'0'*32 + b'\n')
    print('0'*32 )
    response = json_recv()
    readline()
    if response['cipertext '][0:32] == response['cipertext '][32:64]:
        tn.write(b'1\n')
        print('1' )
    else:
        tn.write(b'0\n')
        print('0' )
    readline()
readline()

Send your input and recognise which mode of AES encryption it is for a certain number of time and then get the flag
Enter your plaintext 
00000000000000000000000000000000
{'cipertext ': 'c46eeb5eae0553a6b091e9533dfdeca04125c4c2ecb1aee2f7005f39b5309257a359894ff70dbefa6c0c8c642bc5e354'}
Input 1 for ECB and 0a for CBC 
0
1 consecutive guesses!
...
33 consecutive guesses!
Good job, you know your AES modes, here's the FLAG as the reward :)) : b'pwnEd{d1ffer3nt_m0d3$_0f_A3$_111}'

First blood!

An alternative approach to this is to note that the same key is always used, so the encryption of a block will stay the same. If you're using ECB, you can then recognise this block, whereas CBC will have mixed in the IV and will give a random looking result.

Golden_Tickets

We are using md5 to hash our tickets to see the one and only ISAAC GOLDEN. You get to submit two golden tickets to meet him. Legitimate tickets have the prefix ISAAC_GOLDEN_STAN in them. But only the luckiest of them all gets to see him. Will you be the lucky one?

nc 34.89.31.172 12001

Author: Thrypuro

MD5 has been broken for a great many years, and one of the possible attacks is a prefix attack: two messages with chosen prefixes can lead to a clash much faster than bruteforcing random messages. We can get an implementation of this attack online and run it with ISAAC_GOLDEN_STAN (plus padding) as the prefix to generate some clashes. I used https://github.com/cr-marcstevens/hashclash during the CTF.

echo -n "ISAAC_GOLDEN_STAN89012345678901234567890123456789012345678901234" > prefix.txt
../scripts/poc_no.sh prefix.txt
[wait about 10 minutes to crack]

This outputs two files which we can convert to hex then provide to the service:

Enter your first ticket: (hex)49534141435f474f4c44454e5f5354414e38393031323334353637383930313233343536373839303132333435363738393031323334353637383930313233348b6170221ba45098764de7823456746ab86c504e2fe049b39ffa9004bed55da4695fd1a1f14f1b20933b70f532092c369283a40ade51788257ba08942231b09d340b3258885cc0d40db428b59ae644c3cb148b6ada3f56064d8180e15573cdbc9323125a302b0227d4b257f1494deba0362b0ae0d80b8542266dcf1bf309a787
Enter your second ticket: (hex)49534141435f474f4c44454e5f5354414e38393031323334353637383930313233343536373839303132333435363738393031323334353637383930313233348b6170221ba45098764ee7823456746ab86c504e2fe049b39ffa9004bed55da4695fd1a1f14f1b20933b70f532092c369283a40ade51788257ba08942231b09d340b3258885cc0d40db328b59ae644c3cb148b6ada3f56064d8180e15573cdbc9323125a302b0227d4b257f1494deba0362b0ae0d80b8542266dcf1bf309a787
{'msg': "Matching tickets?!?! You must be very lucky, this way. Here's a sourneir for being this lucky pwned{md5_c011isions_ar3_pr3tty_g0ld}"}

Do You Know ELGamal?

RSA is wayy too overrated, so i decided to be hip and look at other asymetric encryption, I might of messed up my implementation but you will never get my flag B)

nc 35.246.121.30 12000

Author : Thrypuro

ElGamal encryption is an interesting alternative to RSA. To begin, pick a cyclic group G order q* and a generator g. Publish all of these as part of the public key. Now, each client picks a private key x, and publishes h=g^x as their public key.

* The easiest way to do this is to pick a prime q.

To encrypt a message m with ElGamal, pick a random y value from G and compute the shared secret s=h^y. The ciphertext is now sent in two parts: c1 = g^y and c2 = m * s. This can be decrypted by deriving the shared secret from c1 as s = c1^x, computing its modular inverse in G, and then multiplying by c2 to recover m.

Now for the challenge. When we connect, we get sent a ciphertext and public key (just h though, interestingly G/q/g are not given...) and can send a message of our own. We then get that message encrypted and then get disconnected.

Ciphertext: (0x49853f7278cfe89014e2f06400c58b439912f6262eeba102fcfb529942615804b8282b681afc9647199c3320774da4c2c470ecb9a8f2aedbee4cc4d55c5286f8, 0x375c1cbb6fb574639d589f954d2b0c76fa0e28e802df5a3ff24c37d64f5fe1d2a987fa81b4f99bd47b381628b63ca56c78a965cf6b1d2059bc5624059744e80a)
Public key: 3850580994364007781151459946925717721780794377692984957493165603874839947821516077331845247562465344883241665408647855674650825629163979737470626889369336
Enter text to input: 1
Ciphertext: (0x49853f7278cfe89014e2f06400c58b439912f6262eeba102fcfb529942615804b8282b681afc9647199c3320774da4c2c470ecb9a8f2aedbee4cc4d55c5286f8, 0xa3423cf6f95ec9f47483d120e7e95b87e18d8bf9a95cd6cde5cc3da8b301c1127d4f3d28f0d2885093f144c3e28c4bb888e456b146ae2fe91fa56e200c54e470)

We can see that the first part of both ciphertexts is the same, which reveals that they are re-using the y value! This allows us to derive the shared secret from our own message by computing

c2 * m^-1

although if we set the message to 1 (as in the example above), then c2 already is the shared secret! Now we just decrypt the flag as normal... except we don't have the modulus. I don't know how to get from the information given, so I left this challenge for a while.

About halfway through the competition, there was an announcement:

Breaking news: Do you know ELGamal? source file added!

Challenge author sentenced to drinks.

As they should be, because this challenge isn't possible without the full public key!

We can now look at the source, which contains the class...

class Challenge():
    def __init__(self):
       self.q = 12600908927583695025915922760858062869504898731692176260536498123355811076649093419400976600871355970813118607850398283879552845362863097769033273386072687
        ...

and we don't care about the rest! Now that we have q, we can easily compute:

>>> from Crypto.Util.number import inverse, long_to_bytes
>>> d = inverse(s, q)
>>> long_to_bytes((c2 * d) % q)
b'pwned{kn0w_y0ur_e1g4m4l_plaintext}'

Scuffed_rsa

I've read a bit around how RSA encryption works this morning and decided to implement it myself! I encrypted a very important flag using my own algorithm but now I can't remember it. For some reason my decryption function doesn't work :( I really don't know where I went wrong... Can you still help me recover it?

Author: yellowtides

There are a LOT of ways to mess up RSA. Let's see what happened this time...

e = 65536

def gen_key():
    p = getPrime(1024)
    q = getPrime(1024)
    n = p # q 
    t = (p-1) * (q-1)
    d = inverse(e, t)
    return n, d

It looks like

a. The e value is 65536, which is very not prime - likely a typo of 65537, the standard value
b. n = p # q ... is just p, the multiplication with q is commented out.

This means that the actual totient will be n-1, and additionally e is not coprime with the totient. This means we won't be able to uniquely decode the message, although we could perhaps still get the intended message...

Part of the reason that RSA works is that ed = 1 (mod totient), since this means that c^d = m^(ed) = m * m^(k*totient) = m (mod n). Let's see what ed is in this case...

>>> e*d % (n-1)
2

It's only 2! That means that if we try to decrypt the message, we'll get the actual message squared. Let's get that first:

>>> d = inverse(e, n-1)
>>> pt = pow(c, d, n)

Now we can perform the modular square root on this value by using the Tonelli-Shanks algorithm... or by asking a website to compute it for us, such as http://www.numbertheory.org/php/tonelli.html

3665573765028059998085620691867112612508129674283466691306664839381228993092379356500870855037^2 = 13436431026861987210657990227191038754313252461764250184965804757779991465066807695823488481242627264412039387076444368594879673591075335818113900487591832971123965787846445769495468271369

>>> long_to_bytes(3665573765028059998085620691867112612508129674283466691306664839381228993092379356500870855037)
b'pwnEd{t0nell1_sh4nk5_x16_s4v3s_th3_d4y}'

huffin_puffin_trees

David Huffman and Zippy have decided that they want to send some secret messages. But, they don't want them to be too long. Since Daniel is a smart dude, he designed some algo or something that would both shorten the message and make it unreadable to the l33tless. I wonder if you can figure it out ... ?

Message: 1101010101011011111011101101110010111101001111010001110011101000100111010101010110111110111011001100100101111010011110100011100111010001001110101010101101111101110100101011011110000001101110110100010010111101101101110001001011100001101000101000000111110110101110

Please put the decoded text into the pwnEd{} wrapper before submitting.

Author: maddox

The challenge name and description are hinting at Huffman trees, which allow a message to be encoded with minimum entropy. They work by EXPLAIN

We're given a lyrics.txt file, which we can assume is used to generate the Huffman tree for this specific challenge. It is perhaps worth implementing Huffman trees at some point to ensure you properly understand them, however since this is a timed competition I copied the code given at https://www.programiz.com/dsa/huffman-coding#code

After editing this to contain the lyrics.txt as the string ( with newlines removed), we can run it to get the Huffman code:

Char | Huffman code 
----------------------
 ' '  |          01
 'a'  |        1100
 'h'  |        1011
 'o'  |        1001
 'e'  |        1000
 't'  |        0001
 'g'  |        0000
 'n'  |       11110
 's'  |       11101
 'i'  |       11011
 'I'  |       10101
 'u'  |       00111
 'w'  |       00101
 'd'  |       00100
 'm'  |      111110
 'l'  |      111001
 'y'  |      111000
 "'"  |      110100
 'c'  |      101001
 'b'  |      001101
 'r'  |     1111111
 'k'  |     1101010
 'p'  |     1010000
 'B'  |     0011000
 'f'  |    11111100
 '.'  |    11010111
 [Chars after this point are not used]

Huffman codes are prefix codes, which means we can decode by reading from the left until we have a full character. Once we match an entire character, we start decoding the next one. Using this, we can read off the code as follows (spaces added for clarity):

11010 101010 110111 110111 01 1011 10010 11110100 11110100 01 1100 11101 00010 01
11010 101010 110111 110111 01 1001100 10010 11110100 11110100 01 1100 11101 00010 01 
11010 101010 110111 110111 01 001010 110111 1000 00011 01 110110 1000 10010 1111011 01
1011 1000 10010 11100 0011 01 00010 1000 00011 11101 <10101110>
i'll huff and i'll puff and i'll (low your house down<?>

There's two characters here which don't seem right, but we can fix them pretty easily to get

pwnEd{i'll huff and i'll puff and i'll blow your house down.}

Another first blood :D

Unsolved: Meet me in the middle of the curve, A bit shorter than usual, Matrix_key_exchange, Miller_phi

Kieron Turk