Advent of Code 2017

Merry Christmas!

Advent of code just finished up, and with it 25 small programming problems. Personally, I thought it was great and enjoyed every moment of it! There were some easy problems and a few difficult ones. The most difficult one for me was day 21, where a gird of “pixels” was to be broken up into 2×2 or 3×3 chunks, operations performed on those chunks to grow them, and the edited chunks reassembled for the next round. I ran into a lot of issues during this challenge, though the biggest one was that I was not keeping my arrays consistent, so elements were swapping places and not going where they should.

In the end, I finished all of it (not without a little help from the sub-reddit), and will certainly do it again! If you’re looking for some programming challenges, I recommend it for sure! If you want to see my solutions for all of the problems, they’re here.

Hope you have a great New Year!

~T

Posted by Tanner in Posts, Programming Projects

PyMENACE – Simple Machine Learning

While browsing YouTube, I came across the video “MENACE: the pile of matchboxes which can learn.” The video goes on to detail MENACE, or Machine Educable Noughts And Crosses Engine, in which there is a matchbox for every possible state of Tic-Tac-Toe. In each box, there are beads corresponding to the possible moves the “computer” can make. On the computer’s turn, the player finds the correct game state and draw a random bead. After the game ends, if the computer won, every move the computer made receives three more beads of the correct color. If the player won, the beads the computer played are simply removed from play. In this way, the computer eventually learns to play Tic-Tac-Toe by trial and error.

Now I found this concept fascinating and as such I wanted to give it a try! However, I’m pretty lazy and didn’t want to make 304 matchboxes nor did I have 200+ people to help it learn. So I programmed it! To start with, I wanted to get the knowledge “map” made. This means I had to generate every possible board state, well not all of them, just the ones where it is MENACE’s turn. After doing that, each board state is initialized with probabilities for each possible play position.

Now that I had the knowledge map, I put together the functionality for actually making a move. Both MENACE and the player make a move with the same function, the player just has to provide their move as an argument. Every move MENACE makes is stored in a list that is then referenced my the learning function. When a winner is detected, MENACE goes through every move it made and adjusts accordingly. (Win: +4, Tie: +3, Lose: -1)

After the basic functionality was there, I put together a simple QT GUI wrapper and hooked MENACE to it. Now, this isn’t the worlds best Tic-Tac-Toe game, but it does learn as you play. If you want to give it a try, you can check out the code on my GitHub, or you can try to make it yourself! Either way, I hope you enjoyed this cobbled together mess of a post.

~T

Posted by Tanner in Posts, Programming Projects

Pwn2Win CTF 2017 – Differential Privacy – Crypto

Is it possible to have privacy on these days? The Rebelious Fingers do not think so. Get the flag.

nc 200.136.213.143 9999

Right off the bat we know this has something to do with differential privacy (Such a surprise!) and we have a server so lets connect to it.

Hello, chose an option:
[1] Info
[2] Query the flag (in ASCII)
[3] Quit

Basic menu, lets see the options.

1
You can query the flag, but the characters are private (indistinguishable).
Differential privacy mechanism: Laplace
Sensitivity: ||125 – 45|| = 80
Epsilon: 6.5

2
[85, 89, 108, -16, 78, 67, 123, 61, 110, 96, 103, 85, 107, 116, 122, 130, 96, 83, 108, 136, 100, 94, 103, 90, 117, 102, 73, 118, 118, 112, 112, 105, 101, 110, 143, 103, 75]

Mhm, well not sure what to do with this yet. I don’t really know much about differential privacy, so let’s research. Differential privacy is used to encode data in such a way that you can’t discern any single persons input while keeping the actual statistical findings of the data intact. It does this by adding a Laplace random number set by some parameters to the value. Because the average of the Laplace function is 0, the average of the data set stays about the same.

At this point, I was at a loss. I would work on some other problems and come back to this one now and then. Then I noticed that the query values change on successive connections. Because the center of the Laplace function is 0, if you take the average of a lot of different encodings, it should be the original value! Python time!

from pwn import *
import ast

host = "200.136.213.143"
port = 9999

#This is the ammount of values to keep after throwing out the largest and smallest values.
#[100,50,10,7,6,5,4,3,2,1,-10,-50,-100] will keep [7,6,5,4,3,2,1]
sample = 7


def get_list():
  #get a new data set from the server
  #turn it into a list
  conn = remote(host,port)
  conn.recvuntil("t\n")
  conn.send(b"2\n")
  data = ast.literal_eval(conn.recvline().decode().strip())
  conn.close()
  #print(data)
  return data

gotten = None

while True:
  d = get_list()

  if not gotten:
    #initialize the gotten array if it hasn't been
    gotten = [[] for j in d]

  for j,v in enumerate(d):
    #add each new value to the corresponding sub-array
    gotten[j].append(v)

  if len(gotten[0]) > sample + 1:
    #After we've gotten enough data
    r = max([1,int((len(gotten[0])-sample)/2)])
    for vals in gotten:
      #For each character, sort it's values and average the sample
      work = vals[:]
      work = sorted(work)[r:-r]
      print(chr(int(round(sum(work)/len(work)))), end="")
    print(" ", len(gotten[0]))

Running this code will print out an estimate of the correct string after each ‘download.’ After 20 updates, the output is something like this

FTK*>VzHY_m`qxqu\lpmtbqmpd]xdf\nqesd|

This makes almost no sense, so lets make a bigger data set.

After 400 updates, it’s looking a bit better

CSF-BR{H`am_jtut_filserjng`uie^npird}

General flag structure is there, and maybe the beginnings of some words.
Let’s keep going. 1622 updates later we get

CTF-BR{I_am_jtst_filtering_the_noise}

Only one incomplete word! Looks like it’s probably “just” let’s try that! It worked!

CTF-BR{I_am_just_filtering_the_noise}

~T

Posted by Tanner in CTF, Posts

Pwn2Win CTF 2017 – Top Secret – Electronics

Molly was able to take pictures of a strange digital circuit sketch, along with an also strange message. All of these things were inside an envelope in a safe, which was labeled “Top Secret”.

We believe it might contain Butcher Corp’s plans for the future, can you help us read the message?

Strange Circuit.jpg
Message.txt

To start off we are given a circuit diagram and an input file. Taking a look at the circuit, I recognized the JK Flip-Flop zero to seven counter in the upper right, with the current value being fed into a MUX. Following this, we see that the MUX is sending a positive value to one of eight transistors which in turn provide a ground to one row of diodes. Looking over the circuit, we can note that there are 9 (0-8) inputs, this matches the Message.txt file we got. Input 0 is used to clock the JK Flip-Flop circuit, while inputs 1-8 are fed to the grid of diodes.

At this point, I was a little stuck. I didn’t understand how to get anything useful from this. So I showed the diagram to an Electrical Engineering friend of mine. He suggested that the diode grid was actually a Light Emitting Diode grid. Immediately I realized that had to be it, it’s an LED matrix! So some quick python code to read in the file and…

Well that doesn’t look right… I think I see “CTF” in there, but… Well no, something went wrong. Back to the circuit! Then I realized, inputs 2,3,7, and 8 are inverted! They go through two transistors! Let’s invert those inputs in the code!

There it is! We got a flag!

Here’s the code I used to generate the correct flag.

from PIL import Image

#Black and white pixels
OFF = (0,0,0)
ON = (255,255,255)

#Read in the file and split it into "letters"
with open("Message.txt", 'r') as f:
    blocks = f.read().split("\n\n")

#Create an empty image with the right dimensions
img = Image.new("RGB", (len(blocks)*8,8))

for n,block in enumerate(blocks):
    #Set the x offset depending on the character
    dx = n*8
    
    #Split the block into lines only using positive clocked lines
    #We don't care about the zero lines
    chunked = []
    for line in block.split("\n"):
        if line[0] == "1":
            chunked.append(line.split(" ")[1:])

    print(chunked)
    
    #Draw the pixels
    for y,chunk in enumerate(chunked):
        for x,val in enumerate(chunk):
            #Should this one be inverted?
            if x in [1,2,6,7]:
                if val == "0":
                    pix = OFF
                else:
                    pix = ON
            else:
                if val == "1":
                    pix = OFF
                else:
                    pix = ON

            img.putpixel((x+dx,y), pix)

img.save("solved.png")

~T

Posted by Tanner in CTF, Posts

BSides STL – Find the Flag – Decoding

Find the flag hidden in this program!
Hint: Build Additional Pylons

This challenge starts with a file called flag.exe

After running it, I checked for any recently changed files, no dice.

Binwalk Output

Looking at the output and, wow! We got a QR code!


And scanning that gives us the flag!
FLAG(YOUFOUNDTHEICON-BSIDESSTL-2017)
~T

Running flag.exe

Alright, let’s throw it in Kali and do some analysis.

Aha! Binwalk says there’s a PNG in there! Lets extract it!

binwalk --dd=".*" flag.exe
Posted by Tanner in CTF, Posts

Tokyo Westerns – My Simple Cipher – Crypto

To start off, we are given a text file containing some encrypted data and the program that was used to encrypt the data. The encryption program is as follows:

import sys
import random

key = sys.argv[1]
flag = '**CENSORED**'

assert len(key) == 13
assert max([ord(char) for char in key]) < 128
assert max([ord(char) for char in flag]) < 128

message = flag + "|" + key

encrypted = chr(random.randint(0, 128))

for i in range(0, len(message)):
  encrypted += chr((ord(message[i]) + ord(key[i % len(key)]) + ord(encrypted[i])) % 128)

print(encrypted.encode('hex'))

Now we know how it was encrypted and how the plaintext is structured! Let’s take a look at the encrypted data.

enc = 7c 15 3a 47 4b 6a 2d 3f 7d 3f 73 28 70 3e 6c 2d 24 3a 08 3e 2e 77 3c 45 54 77 48 66 7c 15 11 33 3f 4f 74 5e

So what do we already know about this?

  • enc[0] is already decrypted
  • enc[1:7] is “TWCTF{” this is our flag format
  • enc[20:22] is “}|” this is the end of the flag and the separator between the flag and the key
  • enc[22:] is the encrypted key

So now we need to figure out how to reverse the encryption algorithm.

encrypted += chr((ord(message[i]) + ord(key[i % len(key)]) + ord(encrypted[i])) % 128)

Because we know the first part of the flag, we can use that to retrieve a partial key! That is done through the magic of math

\(E_{n+1} = \left ( P_{n} + K_{n \mod 13} + E_{n} \right ) \mod 128\)

Because of the nature of the input, we can make an educated guess about the values of the above equation pre-mod.

\(w = \left ( E_n + M_n \right )\mod 128\)
\(g = E_{n+1}\)
\(k_n = \left\{\begin{matrix}128-w+g & w>g\\ g-w & w \leq g\end{matrix}\right.\)

Or if you’d rather read a program,

encrypted = "7C153A474B6A2D3F7D3F7328703E6C2D243A083E2E773C45547748667C1511333F4F745E"

hexbytes = [encrypted[i:i+2] for i in range(0,len(encrypted),2)]

key = ""

message = "TWCTF{"

def getadd(work,goal):
    work = work%128
    if work > goal:
        out = 128-work+goal
    else:
        out = goal-work

    return(out)

i = len(message)-1

for i,byte in enumerate(hexbytes):
    work = int(byte,16) + ord(message[i])
    goal = int(hexbytes[i+1],16)

    print(chr(getadd(work,goal)), end="")

Running through this will give us the first 6 characters of the key, which happen to be “ENJ0YH” at this point, we made an educated guess that the whole key was “ENJ0YHACKING!” and ran a decryption program

encrypted = "7C153A474B6A2D3F7D3F7328703E6C2D243A083E2E773C45547748667C1511333F4F745E"

hexbytes = [encrypted[i:i+2] for i in range(0,len(encrypted),2)]

message = ""

key = "ENJ0YHACKING!"

key = [ord(c) for c in key]


def getadd(work,goal):
    work = work%128
    if work > goal:
        out = 128-work+goal
    else:
        out = goal-work

    return(out)

for i,byte in enumerate(hexbytes[:-1]):
    work = key[i%13] + int(hexbytes[i],16)
    goal = int(hexbytes[i+1],16)

    message += chr(getadd(work,goal))

print(message)

This didn’t work, not entirely at least. After removing the unprintable characters from the output, we’re left with “TWCTF{Q{wkg-is-fun/z@A\0YHOLIDOb”
It decrypted part of the key at the end! Looks like the key is actually “ENJ0YHOLIDAY!”

Re-running the above program with the new key gives us the output “TWCTF{Crypto-is-fun!}|ENJ0YHOLIDAY!” and our flag TWCTF{Crypto-is-fun!}

~T

Posted by Tanner in CTF, Posts

TAMUctf – lowered_expectations – Crypto

Snowden RSA encrypted the contained message, but he made a fatal flaw in choosing keys.
He underestimated your hacking skills. Can you figure out the message?

[File]

We’re given a file with the contents C, e, and N. These are quickly recognized as RSA encryption where, with P = Plaintext, \( C=P^{e} \left ( modN \right ) \).

Because the given exponent, e = 3, is small and the given modulus is many orders of magnitude above the cipher text, it can be assumes that during encryption, the value never rose above the value N. This means we can simply knock off the “mod N” part of the encryption, leaving us with \(C=P^{e}\). Solving for P, we get \( P=C^{1/e}\) -or- \( P=\sqrt[e]{C}\). This is also known as the “Low Public Exponent Attack.”

While writing a python program to decrypt the flag, I did run into an issue of precision. Vanilla python decimals are not precise enough to fully decrypt the flag. This is however, easily fixed by using the decimal module which allows setting the desired precision.

Finally, the code worked and upon running it we get our flag!
gigem{get_L0W__d8d93c7ec9e56348}

If you do have to choose a low public exponent due to some technological limitation, make sure you pad your messages to a “full” message length. This will ensure that the modulus takes effect. If you have no such limitation, still pad your messages, but also make the exponent \(e=2^{16}+1\). These measures will ensure your message is adequately encrypted.

Python Code

~T

Posted by Tanner in CTF, Posts

Sunshine CTF – Vanity – Crypto

You need to buy some things, and luckily the local merchant accepts Bitcoin! You found out he only checks that the first four characters of his address and the one you send the coins to. Can you make him think you are sending him the coins while they really go to yourself?

For this challenge, we are given a server to connect to which gives the “merchants” Bitcoin address and asks for our Bitcoin private key in hex. The goal of the challenge being to generate valid addresses that begin with the same four characters. This is fairly simple as the first character is always a “1” so we only need to find the first three characters. After a bit of research, a program called VanityGen was found. This program takes a string and generated Bitcoin addresses and their corresponding private keys! Getting the flag from this point is trivial, a few commands later and we get it!

sun{a1waY5_ch3k__th0se_bits}

~T

Posted by Tanner in CTF, Posts

One Time Pad – Homebrew CTF Challenge

A few weeks ago was AlexCTF, and in that competition there was a cryptography challenge called “Many Time Secrets” with the description: “This time Fady learned from his old mistake and decided to use onetime pad as his encryption technique, but he never knew why people call it one time pad!”

The challenge then went on to give a hex encoded message what has been xor encrypted with a key. The trick here is that the same key, in this case the flag for the challenge, was used to encrypt every line. So by guessing the some of the key, which we know starts with “ALEXCTF{” we can slowly decrypt some of the message. Then by guessing the next part of the message, we can reveal more of the key. As we guess more of the message, more of the key is known. Which allows for more of the other messages to be known, which allows fore more guessing! Following through with this gives us the whole key/flag “ALEXCTF{HERE_GOES_THE_KEY}”

When I initially started working on this challenge, I found out about an attack on a one time pad that has reused a key. The attack is the many time pad attack. The setup is similar, you have a message that has been encrypted with a key. Then you have another message encrypted with the same key. However, in this case, the key is not known, and could be gibberish for all you know. So how do we recover the message? Well there is a really cool property of the xor operation that you can take advantage of when you have multiple things encrypted with the same key.

Note: For those that do not know, ⊕ is the bitwise xor operator. This means to take the xor individually of each bit pair of the message.

Ex. 1010 ⊕ 0111 = 1101

Let’s say you have two messages, M1 and M2, and you have a key, K. For otp encryption you would simply do

M1 ⊕ K=Encrypted

You would then send the encrypted text to whoever, and given that they have the key, all they have to do is

Encrypted ⊕ K=M1

But, when you have

E1 = M1 ⊕ K and E2 = M2 ⊕ K

something really interesting happens. You can xor the two encrypted texts together and completely remove the key from the equation! In other words,

E1 ⊕ E2 = M1 ⊕ K ⊕ M2 ⊕ K = M1 ⊕ M2

We’ve completely removed the unknown key from the equation! Now if we guess part of one of the messages, we would get the corresponding part of the other message! So, for example, if you are competing in a CTF and you know the flags start with “flag{” you would be able to guess that the flag is one of the encrypted lines, then all you have to do is xor each line with the line that contains the flag and you can start guessing away to reveal the flag.

For the many time pad attack, the method of discovering the message is identical to the original challenge. However, to get to this point, additional steps are required. Now I’ll leaved you with an actual message to try out the Many time pad attack yourself! (This is a CTF challenge with one of the lines starting with “flag{“)

34 4b 2a 49 01 29 73 64 6c 66 7b 44 10 11 73 6a 4c 4d 6d 5f 61 74 25 01 4c 33 1f 78 51
1e 4a 6b 42 4e 3a 21 6c 29 7b 7a 0b 45 2a 36 2b 4c 08 79 43 69 7d 27 01 56 33 48 25 14
39 0e 23 5a 57 2a 21 65 6c 69 6d 0c 10 3f 21 6e 40 19 2a 44 60 73 2c 46 4b 7c 5e 69 5b
05 5a 6b 4f 49 2a 21 62 67 6d 3f 1c 59 35 36 2b 51 0c 6e 1c 28 69 2d 01 4c 34 5e 7f 14
19 5d 6b 4c 49 2e 75 2d 40 28 7e 05 10 2d 20 62 4f 0a 2a 5e 67 6d 6c 01 70 39 4d 6e 14
1e 41 3c 1b 48 3c 21 79 61 6d 3f 1b 55 3b 26 79 44 4d 67 55 7b 69 23 46 5d 72 1f 26 19
16 42 2a 5c 5a 7f 6f 3e 56 3f 2e 05 03 07 23 3f 45 32 67 03 3c 74 77 7e 08 32 5c 38 49

~T

Posted by Tanner in CTF, Posts

Befunge Interpereter

Alright so Befunge… What is it? So a super simple explanation is that Befunge is a two dimensional esoteric[1] programming language. Basically what this means is, Befunge is a “joke” programming language that was created for fun and amusement. Befunge, or more specifically Befunge-93, is programmed in an 80×25 grid of cells with each cell holding one instruction. That instruction could simply push a number to the stack or change the direction of the read head, or it could, using values in the stack, alter the actual code while it is executing!

 

That’s a list of all the available commands for the Befunge language. While it may not look simple, I can assure you it isn’t! That’s not really the point though. The point is to program something and have a challenge while doing it. (And hopefully some fun too) Well now that we’ve seen what the language is, we want to get to programming with it don’t we? Unfortunately I couldn’t find an interpreter that made a lot of sense to me. So I started to put together my own.

At first I had it reading text files, but by the end of it, I wanted it to read from excel files because I wanted an easier grid to work with. It’s pretty simple to run, just open a shell and run the file along with a program name. Or nothing to see the help.

Here it is!

Until next time,
T

[1] Esoteric : Intended for or likely to be understood by only a small number of people with a specialized knowledge or interest, or an enlightened inner circle.

Posted by Tanner in Posts, Programming Projects