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-w_{1})(x-w_{2})\cdots(x-w_{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}x^n = \frac{1}{(1-x)^{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}
\]

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: 
//   DLINKER=.lib64/ld-linux-x86-64.so.2
//   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.

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.