Category Archives: English


(This is part of my series on program vulnerability exploitation.)

Our ultimate goal when exploiting a program is to make it run arbitrary code. In general, especially in proof-of-concept exploits, we will want to spawn a shell since then from a shell we can execute arbitrary commands (so we consider that if we can spawn a shell, we can do anything). If the program already contains some code which spawns a shell, we can just replace a return address to jump to it in exactly the same way as in the previous post. You could try to exploit this program as an exercise:

Continue reading

Exploiting basic vulnerabilities

By popular demand (sort of), I have started writing a series of posts on my Tumblr to explain and demonstrate how some basic vulnerabilities in computer programs can be exploited by an attacker to compromise the security of the system on which the program runs (typically, an attacker will be able to run arbitrary code with the privileges of the user running the vulnerable program). So I’m putting them here as well.

Continue reading

Pseudo-random sequences and finite fields

One way to symmetrically encrypt a message is to generate a sequence of bits of the same length as the message, and perform a bitwise exclusive-or between the message and the sequence. Then the recipent performs the same operation, and recovers the original message. (This is one way to construct a stream cipher.)

Clearly, the security level provided by such an encryption scheme depends entirely on the way in which the sequence was generated. If it is truly random, then we obtain a so-called one time-pad, which, as long as it is used only once, guarantees perfect secrecy. At the other extreme, if the sequence consists of only 0-bits, then the encryption process does nothing at all and an adversary can directly read the message.

Continue reading

Secret-sharing with polynomials

Suppose you have a secret you wish to transmit to $n$ people, but in such a way that all of those $n$ people must collaborate in order for the secret to be revealed. In other words, it must not be possible for even $n-1$ of those people to obtain the secret, even partially, if the $n$th person does not cooperate.

Continue reading

Polynomial factorisation over finite fields, part 0: Overview

Another cool problem in computational number theory is how to factor a polynomial with coefficients in a finite field. Recall that for a field $K$, the ring $K[X]$ of polynomials in one indeterminate with coefficients in $K$ is a unique factorisation domain (UFD), which means that every polynomial of $K[X]$ can be factored as a product of irreducible polynomials and that this factorisation is unique up to order and unit factors. We are interested in finding a complete factorisation of a polynomial when $K$ is a finite field. Like primality testing, this involves several algorithms which must be run successively, so in this first post I will give an overview of each one, and I will describe them in detail in later posts.

Continue reading

Primality testing, part 2: The Pocklington-Lehmer primality test

(Continues this post.)

So we have this integer $n$, and we would like to know whether it is prime or not. We have used the Rabin-Miller compositeness test on it a couple times and it has always turned negative, so the probability that $n$ is not prime is excruciatingly small. Still, we have not proved that $n$ is prime; in order to do that, we need a real primality test. Basically, we are looking for a converse to Fermat’s theorem. Such a converse was found by Pocklington and improved by Lehmer. Essentially, it is based on the fact that an integer $a$ of multiplicative order $n-1$ modulo $n$ (i.e., such that $a^{n-1} \equiv 1 \pmod n$ and $a^e \not \equiv 1 \pmod n$ for all positive $e < n-1$) exists if and only if $n$ is prime. More precisely:

Continue reading