Cryptography

Hack The Vote CTF 2016


Warp Speed 150

Our Trump advertising campaign is incredible, it’s skyrocketing! It’s astronomical! Wait stop!! SLOW DOWN!!!

File: warp_speed.5978d1405660e365872cf72dddc7515603f657f12526bd61e56feacf332cccad.jpg

warp_speed.5978d1405660e365872cf72dddc7515603f657f12526bd61e56feacf332cccad.jpg

As you could clearly see, they have sliced a single image into several slices and split it into two halves. The first part of the challenge is to slice the image into several slices from the left side of the image and right side of the image. We used a slicer script using python PIL: slicer.py. A slice has a height of 7 pixels. Thus we have got 36 slices from the left side and right side of the image.

Now it’s time to join one each from left and right one by one to make a single portrait image.  We wrote another script to join them and make a single image: merge_image.py

flag.jpg

Flag: flag{1337_ph0t0_5k1lls}

Electioneering (250 Points)

We confiscated this poster that was being handed out at polling places. It doesn’t appear to be supporting a candidate, but we’d like you to take a look just to be sure.

poster

Upon receiving the PNG image, I ran the binwalk image over the file. To my surprise, it had a zip file embedded in it which was password protected.

So our task was to find the password for the zip file to extract the flag.txt file.

Upon loading the image in the stegsolve tool, we were able to find some noise in the top left corner in the gray bits of the poster.png file and solved it as gray_bits.bmp

Screenshot_20161125_103214.png

While zooming into the image (using gimp), you could see that the height of the noise is 4 pixels.

screenshot_20161125_103747

And it prints: IrateAnagramCakeImage

This should be the password of the zip file.

Flag: flag{4nd_th3_w1nn3r_15…}

TOPKEK 50

A CNN reporter had only one question that she couldn’t get off her mind

Do we even know, who is this 4 CHAN???

So she set out to find who this 400lb hacker is. During her investigation, she came across this cryptic message on some politically incorrect forum online, can you figure out what it means?

kek

We considered KEK as 0 in binary and TOP as 1 in binary and ‘!’ is number of times zero or one is repeated. We wrote a script to read the flag from the kek script.

Flag: flag{T0o0o0o0o0P______1m_h4V1nG_FuN_r1gHt_n0W_4R3_y0u_h4v1ng_fun______K3K!!!}

 

Advertisements

Binary Vectors


As a part of my master’s degree case study, I had given few questions in modulo arithmetic to implement as a pre-requisite for implementing a research paper. A few concepts in the document contains Binary vectors, Boolean functions, Walsh transform, Fast Walsh Transform and ANF and I thought I should blog about the same.

u >> i = (ui, ui+1 , . . . , um−1, 0, . . . )
u&v = (u0 ∗ v0 , . . . , um−1 ∗ vm−1)

For example, to get the first bit (u0 ) of an integer u, we can write u&1. Similarly, (u >> i)&1 gives the i-th bit (ui) of u

Question1:

Write a function taking as inputs an integer u (viewed as a binary vector) and an integer i, which returns the i-th bit of u?

Solution:
This is how an unisigned integer is represented in a 32 bit machine’s memory:

Value of first bit:

%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000001010
%%%%%%%%%% %%%%%%%%%%

Unsigned int 10 is represented like ^^ in binary in a 32 bit machine/compiler. We are going to just do a logical and with ‘1’
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000001010 &
0000000000000000 0000000000000001
——————————————————
0000000000000000 0000000000000000

Value of ith bit:

Lets take 10, and this is how it is represented in binary

%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000001010
%%%%%%%%%% %%%%%%%%%%

And lets say i is 2. After the first right shift
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000000101
%%%%%%%%%% %%%%%%%%%%

After the second right shift
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000000000000010
%%%%%%%%%% %%%%%%%%%%

In-order to find the value of ith bit, a logical AND operation is done to the last binary.
0000000000000000 0000000000000010 &
0000000000000000 0000000000000001
——————————————————
0000000000000000 0000000000000000

Source Code:

/* Written by Giri
   A function taking as inputs an integer u (viewed as a binary vector)
   and an integer i, which returns the i-th bit of u */

#include "header.h"
/* Functions are defined in util.c */

int main () {
	ulong u, i, choice;
	do {
		printf ("1. Check first bit\n");
		printf ("2. Check a random bit\n");
		printf ("3. Exit\n");

		printf ("Enter your choice: ");
		scanf  ("%lu", &choice);

		switch ( choice ) {
			case 1: printf ("Enter the integer: ");
					scanf ("%lu", &u);
					printf ("The first bit is %d\n", check_first_bit (u));
			break;

			case 2: printf ("Enter the integer: ");
					scanf ("%lu", &u);
					printf ("Enter the value of ith bit which you want to extract from the integer: ");
					scanf ("%lu", &i);
					printf ("The requested bit is : %d\n" , check_random_bit(u, i));
			break;

			case 3: 
					exit (0);
			break;

			default: printf ("00ps! Wrong choice!!\n");
			break;
		}
	} while ( ! ( choice  3 ) );
	return 0;
}

Question 2

Write a function returning the indice of the first non-zero bit of a binary vector.

Solution: We shift the binary vector until we get a 1 at the first bit of the same.

Source code:

/* Written by Giri
   A function returning the indice of the first non-zero 
   bit of a binary vector */

#include "header.h"
/* Status: Complete */
/* Function returns the indice of the first non-zero value
   in the given unsigned integer						*/
ulong find_indice ( ulong u) {
	if (u == 0UL)
		return ULONG_MAX;
	ulong indice = 0;
	while (!(u & 1UL)) {
		indice = indice + 1;
		u = u >> 1;
	}
	return indice;
}

int main () {
	ulong u;
	ulong choice;
	do {
		printf ("1. Check the position of first non-zero bit\n");
		printf ("2. Exit\n");

		printf ("Enter your choice: ");
		scanf  ("%lu", &choice);

		switch ( choice ) {
			case 1: printf ("Enter the integer: ");
					scanf ("%lu", &u);
					printf ("The indice of the first non-zero number is %lu \n", find_indice (u));
			break;

			case 2: 
					exit (0);
			break;

			default: printf ("00ps! Wrong choice!\n");
			break;
		}
	} while ( ! ( choice  2 ) );
	return 0;
}

Question3

A function that implements the Hamming weight of a binary vector

Solution:
Say the input is 1023:
%%%%%%%%%% %%%%%%%%%%
0000000000000000 0000011111111111
%%%%%%%%%% %%%%%%%%%%

1023 & ( 1023 – 1 )
0000000000000000 0000011111111111 &
0000000000000000 0000011111111110
————————————————–
0000000000000000 0000011111111110
count = 1

1022 & ( 1022 – 1 )
0000000000000000 0000011111111110 &
0000000000000000 0000011111111100
————————————————–
0000000000000000 0000011111111100
count = 2

1020 & ( 1020 – 1 )
0000000000000000 0000011111111100 &
0000000000000000 0000011111111011
————————————————–
0000000000000000 0000011111111000
count = 3

1015 & ( 1015 – 1)
0000000000000000 0000011111111000 &
0000000000000000 0000011111110111
————————————————–
0000000000000000 0000011111110000
count = 4
.
.
.

512 & ( 512 – 1 )
0000000000000000 0000010000000000 &
0000000000000000 0000001111111111
—————————————————–
0000000000000000 0000000000000000
count = 10

Source code:

/* Written by Giri
   A function that implements the Hamming  weight of a binary 
   vector 
   In this example, I have used a built in function called 
   int __builtin_popcount (unsigned int x), which will return 
   the number of non-zero values in the given unsigned int */

#include "header.h"

int main () {
	ulong u;
	int choice;
	do {
		printf ("1. Find the Hamming weight of a binary vector (using built in function): \n");
		printf ("2. Find the Hamming weight of a binary vector (using a custom function): \n");
		printf ("3. Exit\n");
		printf ("Enter your choice: ");
		scanf ("%d", &choice);
		switch ( choice ) {
			case 1: printf ("Enter the binary vector: ");
					scanf ("%lu", &u);
					printf ("The Number of 1s in your binary vector is : %d\n", __builtin_popcount(u));
			break;

			case 2: printf ("Enter the binary vector: ");
					scanf ("%lu", &u);
					if ( u == 0 )
						printf ("There isn't any non-zero values in your binary vector\n");
					else
						printf ("The Number of 1s in your binary vector is : %lu\n", hamming_weight(u));
			break;

			case 3: 
				exit(0);
			break;

			default:
			break;
		}
	} while ( ! ( choice  2 ) );
	return  0;