Saturday, 24 November 2012

Counting partitions with generating functions

Problem

Find how many ways are there to pay an amount $n$ using coins of $c_1, c_2,\cdots, c_k$.

To count the ways of summing $n$, what we need is the coefficient of $x^n$ in
$\prod_{i=1}^{k}(1+x^{c_i}+x^{2c_i}+x^{3c_i}+\cdots) = \prod_{i=1}^{k}\frac{1}{1-x^{c_i}}$
Now $x^c-1=(x-\omega_{1})(x-\omega_{2})\cdots(x-\omega_{c})$ and we can represent the product above as
$\frac{(-1)^{k}}{Q(x)} = \frac{(-1)^{k}}{(x-a_1)^{m_1}(x-a_2)^{m_2}\cdots(x-a_l)^{m_l}}$
where $m_i$ is the multiplicity of $a_i$ in the denominator. Decomposing in partial fractions we get
$\sum_{i=1}^{m_1} \frac{A_1^{i}}{(x-a_1)^{i}} + \cdots + \sum_{i=1}^{m_l} \frac{A_l^{i}}{(x-a_l)^{i}}$

And using
$\sum_{n=0}^{\infty} \binom{n+k}{k}t^n = \frac{1}{(1-t)^{k+1}}$

we end up with (up to a factor $(-1)^k$)
$\sum_{i=1}^{m_1}\binom{n+i-1}{i-1}\frac{(-1)^{i}A_1^{i}}{a_1^{n+i}} + \cdots + \sum_{i=1}^{m_l}\binom{n+i-1}{i-1}\frac{(-1)^{i}A_l^{i}}{a_l^{n+i}}$

To calculate $A_i^{m_i}$ we observe that
$\left. \frac{(x-a_i)^{m_i}}{Q(x)}\right|_{x=a_i} = A_i^{m_i}$
and to get the other $A_i$s we have
$\left. \frac{1}{j!} \frac{d^j}{dx^j} \left( \frac{(x-a_i)^{m_i}}{Q(x)} \right) \right|_{x=a_i} = A_i^{m_i-j}$

For the partial fraction expansion we have followed the exposition here.

Let $F(x)$ be a proper fraction, and let the denomitor $Q(x)$ have roots $a_1,\cdots,a_l$ with multiplicities $k_1,\cdots,k_l$
$F(x) = \frac{P(x)}{Q(x)} = \frac{P(x)}{(x-a_1)^{k_1} \dots (x-a_l)^{k_l}}$
partial fraction expansion has than the form
$F(x) = \sum_{i=1}^{k_1} \frac{A_1^{i}}{(x-a_1)^{i}} + \sum_{i=1}^{k_2} \frac{A_2^{i}}{(x-a_2)^{i}} + \cdots + \sum_{i=1}^{k_l} \frac{A_l^{i}}{(x-a_l)^{i}}$

Then
$\left. F(x)(x-a_i)^{k_i}\right|_{x=a_i} = A_i^{k_i}$
and to get the other $A_i$s we have
$\left. \frac{1}{j!} \frac{d^j}{dx^j} \left( F(x)(x-a_i)^{k_i} \right) \right|_{x=a_i} = A_i^{k_i-j}$

Friday, 3 February 2012

Relative INTERP in ELF and set-uid

The combination of a set-uid and a relative path in the INTERP section of an ELF binary is very dangerous.

This seems to be general security issue/leak concerning how dynamic linking in linux/glibc works, so let me explain what it is:

Consider building a dynamically linked binary and specifying a relative path in the ELF INTERP section (using the --dynamic-linker gcc option) so you could redistribute a custom glibc version with your dynamically linked commercial application (where you are not allowed to link statically against the LGPL glibc, but still need to make your binary work across different linux distribution having different glibc versions).

If you chown the binary to root, and put the set-uid flag on your binary, it effectively becomes a rootkit. As executing it from a different directory, allows you to replace the dynamic linker executable, that will be executed with root permission.

To demonstrate this, take a look at the following C code (issue.c):

// issue.c
//
// build like this:
//   gcc -DNAME=\"vulnarable\" -o issue -Wl,--dynamic-linker,$DLINKER issue.c // sudo chown root issue // sudo chmod u+s issue // now build the code to be executed with // root permissions (we use the same issue.c): // mkdir -p .lib64/ // gcc -DNAME=\"rootkit\" -o$DLINKER --static issue.c
//

#include <stdio.h>

int main(int argc, char* argv[])
{
printf("(%s) euid:%d\n", NAME, geteuid());
}


If you now execute the set-uid binary like this

./issue


or even just do this

ldd issue


instead of getting what you might expect, e.g.

(vulnarable) euid:0


you get

(rootkit) euid:0


The point is you could replace the ld-linux-x86-64.so.6 binary with whatever you like, and it will get executed with root permissions.

Similar issues seems to have been addressed by not resolving \$ORIGIN in RPATH or ignoring LD_LIBRARY_PATH if the set-uid flag is set.

So I wonder if the INTERP in ELF has to be ignored whenever the set-uid flag is set (i.e. by using the default dynamic linker - /lib32/ld-linux.so.2 or /lib64/ld-linux-x86-64.so.2)?

So what do you think, where should this be fixed or reported - in glibc or the kernel?

The discussion at stackoverflow security issue with set-uid and a relative path for INTERP (dynamic linker) in ELF.

Thursday, 2 July 2009

Joshua Bloch: Here's a Mystic Code Poem

The Mystic Code Poem from Joshua Bloch could be written down in an even more mystical and funny way:
int inverse(int __) {
int _=__;

_*= -~-~- (__*_);
_*= -~-~- (__*_);
_*= -~-~- (__*_);
_*= -~-~- (__*_);

return _;
}
Not quite obvious, but the code above will find the multiplicative inverse of its odd parameter, e.g. N*inverse(N) = 1 mod 2^32.