ASIS 2014 quals # Crypto – Plough

Posté le by - 2 724 vues

URL: http://asis-ctf.ir/challenges/
Type: block of bits encoding
Solution: ASIS_c0d9dce6d68b484f7a37d5c80d576913
 

Description
Source code of encryptor and encrypted file is given
file

Archive contains 2 files:

$ tar xvfJ crypto_250_bf16a61aa8117be9c994f171023d37ff 
x f753c38c5baadab5a53052ad06e7d7a0
$ unzip f753c38c5baadab5a53052ad06e7d7a0 
  inflating: encrypted               
  inflating: plough.cpp

plough.cpp is the C++ source code of the algorithm used to encrypt the file:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
//----------------------------------
class class1
{
	private:
		FILE*file;
		unsigned char k;
		char chw;
	public:
		class1(char[20]);
		~class1();
		void w(char);
		void wn(int, char);
};
//---------
class1::class1(char FileName[20])
{
	if(!(file = fopen(FileName, "wb")))
	{
		cout << "\nError: cant crate file!";
		exit(1);
	}
	k = 128;
	chw = 0;
}
//---------
class1::~class1()
{
	if(k != 128)
	putc(chw, file);
	fclose(file);
}
//---------
void class1::w(char b)
{
	if(b > 1)
		b = 1;
	chw += b * k;
	if(!(k /= 2))
	{
		putc(chw, file);
		k = 128;
		chw = 0;
	}
}
//---------
void class1::wn(int n, char ch)
{
	int k = (n > 0);
	char temp;
	for(; n > 1; n--)
		k *= 2;
	for(; k; k /= 2)
	{
		temp = ch & k;
		w(temp);
	}
}
//----------------------------------------------------
class class2
{
	private:
		FILE*file;
		unsigned char k;
		char chR;
	public:
		class2(char[20]);
		~class2();
		int r();
		char rn(int);
		int end();
};
//---------
class2::class2(char FileName[20])
{
	if(!(file = fopen(FileName, "rb")))
	{
		cout << "\nError: cant read file!";
		exit(1);
	}
	chR = getc(file);
	k = 128;
}
//---------
class2::~class2()
{
	fclose(file);
}
//---------
int class2::r()
{
	int ret = k & chR;
	if(!(k /= 2))
	{
		chR = getc(file);
		k = 128;
	}
	if(ret)
		return 1;
	else
		return 0;
}
//---------
char class2::rn(int n)
{
	int ret = 0;
	int k = (n > 0);
	for(; n > 1; n--)
		k *= 2;
	for(; k; k /= 2)
		ret += r() * k;
	return (char) ret;
}
//---------
int class2::end()
{
	if(feof(file))
		return 1;
	else
		return 0;
}
//----------------------------------
char* zip(char *inFileName, char *outFileName);
//----------------------------------
int main(int argc,char*argv[])
{
	if(argc != 3)
		cout << "usage:\tplough inputFilePath outputFilePath";
	else
		cout << zip(argv[1], argv[2]);
	return 0;
}
//----------------------------------
char* zip(char *inFileName, char *outFileName)
{
	class2 IBFile(inFileName);
	class1 OBFile(outFileName);
	char shift = 0, counter = 0;
	char r;
	int ended = 0;
	do
	{
		r = IBFile.r();
		ended = IBFile.end();
		if(ended)
		{
			if(!shift)
			{
				if(!r)
					OBFile.wn(3, ++counter);
				else
				{
					OBFile.wn(3, counter);
					OBFile.wn(2, 1);
				}
			}
			else
			{
				if(r)
					OBFile.wn(2, ++counter);
				else
				{
					OBFile.wn(2, counter);
					OBFile.wn(3, 1);
				}
			}
		}
		else
		{
			if(!shift)
			{
				if(!r)
				{
					counter++;
					if(counter == 7)
					{
						OBFile.wn(3, 7);
						counter = 0;
						shift = 1;
					}
				}
				else
				{
					OBFile.wn(3, counter);
					shift = 1;
					counter = 1;
				}
			}
			else
			{
				if(r)
				{
					counter++;
					if(counter == 3)
					{
						OBFile.wn(2, 3);
						counter = 0;
						shift = 0;
					}
				}
				else
				{
					OBFile.wn(2, counter);
					shift = 0;
					counter = 1;
				}
			}
		}
	}while(!ended);
	return (char*)"End\n";
}

 

Algorithm analysis

We have two classes:

  • class1 is for dealing with output bits flow
    • constructor & destructor: handle opening & closing output file
    • w(char b): set (b=1) / unset (b=0) the current bit of current output byte
    • wn(int n, char ch): encode ch value using n bits
  • class2 is for dealing with input bits flow
    • constructor & destructor: handle opening & closing input file
    • r(): return value (0 or 1) of current bit of current input byte
    • rn(int n): return compound value of the n bits starting from current bit of current input byte (not used here)
    • end(): return end of input file status

And one encoding function zip(char *inFileName, char *outFileName):

  • r is the value of current bit of current input byte
  • shift is used to toggle writing of 3 bits and 2 bits
  • counter is the « distance » between a bit value and the next one

Reverse encoding scheme

As seen above there is 2 main writing processes:

  • 3 bits (shift=0): the 3 bits value specifies the « position » of the next bit '1' (or '0' if the 3 bits value is 0b111)
  • 2 bits (shift=1): it depends of the 2 bits value and the counter value. For an easier implementation, we can define all the decoding combinations through this matrix:
      counter = 0 counter = 1
    2 bits = 00 0  
    2 bits = 01 10 0
    2 bits = 10 110 10
    2 bits = 11 111 11

    If the result value ends with a '1' then counter = 0 else counter = 1

Python decoder

Python is not optimized for decoding such big files, but is easier to see how it works. In order to simplify it, we do not decode the end of file (not neccessary).

f = open('encrypted', 'rb')
iSTR = f.read()
iBSTR = ''.join(['{:08b}'.format(ord(c)) for c in iSTR])
f.close()
 
oBSTR = ''
shift, counter = 0, 0
while (iBSTR != ''):
  if (shift == 0):
    r, iBSTR = int(iBSTR[:3],2), iBSTR[3:]
    oBSTR += '0' * (r - counter)
    if (r < 7):
      oBSTR += '1'
      counter = 1
    else:
      counter = 0
    shift = 1
  else:
    r, iBSTR = int(iBSTR[:2],2), iBSTR[2:]
    oBSTR += [['0', '10', '110', '111'], ['', '0', '10', '11']][counter][r]
    if (oBSTR[-1] == '1'):
      counter = 0
    else:
      counter = 1
    shift = 0
 
oSTR = ''.join([chr(int(oBSTR[i:i+8],2)) for i in range(0, len(oBSTR), 8)])
f = open('plain', 'wb')
f.write(oSTR)
f.close()

 
Running on encrypted, we obtain the following decoded PNG image flag file:
plough_plain

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *