blog by willwam845

pbctf 2020 writeups

Perfect Blue CTF 2020

I participated in Perfect Blue CTF hosted by the wonderful team perfect blue with the Crusaders of Rust. We placed 11th, which I think is pretty good!

Here’s my writeups for the challenges that I solved.

GCombo - misc

One day I spied out my friend accessing some google form to enter his secret combination lock. 
Afterwards, I kept bothering him about it, and he finally decided to give the link to me. 
Maybe you can figure out his combo for me and get a tasty flag in return:

By: theKidOfArcrania

link

Survey?

This challenge presents us with a Google Forms site. This is typical for a survey challenge, and so we start by carrying out a KPBSA (known plaintext survey blood attack). We know the flag format is pbctf{text_here}, and so we search for this in the source.

Upon doing so, we see that the flag is pbctf{<digits you got along the way>_<password>}

pls gimme flag ;-;

Now, this was not the actual flag, and this is because we need to actually find these things in the Google Forms.

We see that the Google Form itself prompts us with a selection screen with a “combination lock”. This is where the actual challenge begins.

A quick guide to Google Forms

The whole reason why our KPBSA works is because Google Forms stores the data of the survey in the source of the html page, meaning that, if there are multiple sections to the form, you can see the oother sections before you complete the first.

Google Forms also has a functionality, which allows you to, based on a user’s response, give them a section of the survey. The challenge uses this in order to “check” our password.

But how does the form know what options lead where?

Well, if we look at the survey itself, we see that each number option has a number after it.

cool numbers

Notice how after the 5, the number is different from the rest? This means that the location is different to all the others, and we can therefore assume that “5” is the first character of our pin.

But now where do we go?

We need to find some way to figure out where this takes us, and what the number means. To do this, I’m going to do some local testing.

I created this very simple form, which only has one question. It redirects to the next section if you pick “no”, redirects back to the same section if you select “yes”, and redirects to the third section if you pick “maybe”.

do you like stego

We can now take a look at the public data created from this Google Form

[null,["",[[2007564277,"is it",null,2,[[1668954036,[["yes",null,-1,null,0]
,["no",null,1475128018,null,0]
,["maybe",null,2106518918,null,0]
]
,0,null,null,null,null,null,0]
]
]
,[1475128018,"Flag","wow its a flag well done",8]
,[2106518918,"i hate you",null,8]
]
,null,null,null,[0,0]
,null,[1,""]
,"is stego bad",48,[null,null,null,null,0]
,null,null,null,null,[2]
]

Notice the numbers after the “no” option and “maybe” option, which should redirect us to sections 2 and 3, are the same as the numbers before the texts of those sections? Now we have a way to get where an option will lead!

Solving the challenge

Firstly, we know that the flag is the series of digits followed by some sort of password, so we start by trying to look for this password.

We, after briefly scrolling through the html, find this line.

That’s most likely our password! And notice how it also has a section number, meaning that we can trace where it came from.

shiny password ooo

751651474 > ?

Searching for this number in the code, we find that it takes us to this section if we enter a “0” as the last digit of our pin.

go back

Now the path is quite clear, we need to go back and retrieve all the digits by working backwards using the section numbers as our guide.

We do this to get:

751651474 > 1385363611 - digit 0
1385363611 > 1566374398 - digit 7
1566374398 > 46599266 - digit 3
46599266 > 1138684813 - digit 3
1138684813 > 1996292448 - digit 9
1996292448 > 1737460359 - digit 6
1737460359 > 147720654 - digit 2
147720654 > 1094087816 - digit 1
1094087816 > 1114266997 - digit 8
1114266997 > 938169490 - digit 5

Reversing the obtained digits gets us our actual pin: 5812693370

And we have our password from before, so we have all we need for our flag!

Flag: pbctf{5812693370_s3cuR3_p1n_id_2_3v3ry0ne}

Trivia

cool fact i was in fact inspiration for this challege

inspirative

so thats pretty nifty i think

Ainissesthai - Crypto

A team of codebreakers had to invent computers to break this cipher. Can you figure out what the flag is?

By: UnblvR

download

We get a single download, along with a server to connect to. Let’s have a look at the download, which is presumably the source code for the server.

#!/bin/env python3

from string import ascii_uppercase as UC
from random import SystemRandom
from enigma.machine import EnigmaMachine
from secretstuff import FLAG, PLUGBOARD_SETTINGS

assert FLAG.isupper() # Without pbcft{...}
random = SystemRandom()

for _ in range(50):
    ROTORS = [random.choice(("I","II","III","IV","V","VI","VII","VIII")) for _ in range(3)]
    REFLECTOR = random.choice(("B", "C", "B-Thin", "C-Thin"))
    RING_SETTINGS = [random.randrange(26) for _ in range(3)]

    machine = EnigmaMachine.from_key_sheet(
           rotors=ROTORS,
           reflector=REFLECTOR,
           ring_settings=RING_SETTINGS,
           plugboard_settings=PLUGBOARD_SETTINGS)

    machine.set_display(''.join(random.sample(UC, 3)))

    ciphertext = machine.process_text(FLAG)

    print(ciphertext)

Seems we are dealing with the classical Enigma cipher.

Upon further inspection of the code, we see that we also don’t have any way to interact with the server, we just get output.

The server seems to generate a random set of parameters for the rotors, reflector and ring settings, however it doesn’t change the plugboard settings, as those are read from a file.

The vulnerability here is that when you encrypt a single character with enigma, it is impossible to get the encrypted character be the same as the original plaintext character.

This means we can use an attack which I like to call the “no leeks” attack. Basically, if we check, for each position, which letter of the alphabet never appears, we know that that character was the original plaintext character.

Implementation below:

from string import ascii_uppercase

output = open("output.txt").read().strip().split("\n") # just 200 lines of output
plaintext = [""] * len(output[0])

for i in range(len(plaintext)):
  candidates = list(ascii_uppercase)
  for out in output:
    if out[i] in candidates:
      candidates.remove(out[i])
  assert len(candidates) == 1
  plaintext[i] = candidates[0]

print(f"Flag: pbctf{{{''.join(plaintext)}}}")

Flag: pbctf{FATALFLAWINENIGMA}

Strong Cipher - Rev/Crypto

Multiplication is better than addition.

By: rbtree

binary ciphertext

The Reversing

Now, I don’t really do rev, so I decided to leave this up to my teammates, and luckily, my teammate will135 did most of the reversing for me. The basic idea is that it takes in 3 arguments, which are 3 files, an input file, a key file and an output file.

The key is truncated to 16 bytes, and then acts like a XOR key; it is repeated to the length of the plaintext.

Then, byte by byte, the key and the plaintext byte are multiplied in the galois field of \(2^{8}\).

Galois field multiplication?

Galois field multiplication works slightly differently from normal multiplication, and I found a very nice site explaining it.

It also gives pseudocode for a multiplication function, which goes as follows:

  • Take in 2 parameters a, and b.
  • Set the product, p, to 0
  • repeat 8 times:
    • if b % 2 == 1
      • perform a logical or on p and a, and make p the result
    • check if a’s MSB is 1, and remember this for later
    • rotate a left by one bit
    • if a’s MSB was 1:
      • perform a logical or on a and the hex number 0x1b
    • shift b one place to the right.
  • p is now the product of a and b

This was quick and easy to implement in python, so I wrote a function to do it.

def multiply(a,b):
  p = 0
  for _ in range(8):
    if b % 2:
      p ^= a
    check = a & 0x80
    a <<= 1
    if check == 0x80:
      a ^= 0x1b
    b >>= 1
  return p % 256

Now, we need to figure out some way to decrypt our own messages, given a key and ciphertext. Basically, we find the inverse of our key, and then do multiplication by the inverse to get to the original character, similar to how modular division works.

def multiply(a,b):
  p = 0
  for _ in range(8):
    if b % 2:
      p ^= a
    check = a & 0x80
    a <<= 1
    if check == 0x80:
      a ^= 0x1b
    b >>= 1
  return p % 256

def div(a,b):
  for i in range(256):
    if multiply(b,i) == a:
      return i

def decrypt(ct, key):
  key = [div(1,x) for i,x in enumerate(key)]
  o = []
  ct = list(ct)
  key = list(key) * ((len(ct)//len(key))+2)
  for i, p in enumerate(ct):
    o.append(multiply(key[i%len(key)], p))
  return("".join([chr(x) for x in o]).encode('latin-1'))

Key recovery

Alright… so now we need the key… how are we going to do that?

Well, we can assume/guess that the plaintext will be somewhat text, with the flag buried in there somewhere.

Now, since the key is repeated, it acts like a multi-byte xor key, and since we know the maximum length of the key can only be 16, we can bruteforce this key length too.

Since we can guess most of the plaintext will be readable, we can, for each byte of the key, bruteforce all 256 possible bytes, and then see what byte results in the most readable plaintext, just in case all of it isn’t readable.

Implementation below:

ciphertext = open("ciphertext","rb").read()

def multiply(a,b):
  p = 0
  for _ in range(8):
    if b % 2:
      p ^= a
    check = a & 0x80
    a <<= 1
    if check == 0x80:
      a ^= 0x1b
    b >>= 1
  return p % 256

def div(a,b):
  for i in range(256):
    if multiply(b,i) == a:
      return i

def decrypt(ct, key):
  key = [div(1,x) for i,x in enumerate(key)]
  o = []
  ct = list(ct)
  key = list(key) * ((len(ct)//len(key))+2)
  for i, p in enumerate(ct):
    o.append(multiply(key[i%len(key)], p))
  return("".join([chr(x) for x in o]).encode('latin-1'))

for keylen in range(1,16):
  key = [""] * keylen
  ct = [ciphertext[i:i+keylen] for i in range(0, len(ciphertext), keylen)][:-1]
  for i in range(keylen):
    maxval = [0,0]
    for byte in range(256):
      c = 0
      for _ct in ct:
        char = multiply(_ct[i], byte)
        if char >= 32 and char <= 128:c += 1
      if c > maxval[0]:
        maxval[0] = c
        maxval[1] = byte
    key[i] = maxval[1]
  key = [div(1,x) for i,x in enumerate(key)]
  print(f"Key for length {keylen}:","".join([chr(x) for x in key]))
  pt = decrypt(ciphertext, key)
  if b'pbctf{' not in pt:
    print("Not correct key...")
  else:
    print("Found!", pt.decode())
    exit()

We then get a lovely Wikipedia article on finite field arithmetic, along with the flag!

Flag: pbctf{I_love_gf2p8mul!Heart_hEart_heArt_heaRt_hearT}

Thanks to qopruzjf and will135 for working on this with me :)