tag:blogger.com,1999:blog-74385492837340297202024-03-13T20:11:16.643+01:00siddhadev's blogUnknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-7438549283734029720.post-78039249099035695342012-11-24T18:10:00.000+01:002013-07-19T11:37:34.290+02:00Counting partitions with generating functions<h4>Problem</h4><blockquote class="tr_bq">Find how many ways are there to pay an amount \(n\) using coins of \(c_1, c_2,\cdots, c_k\).</blockquote><br />
To count the ways of summing \(n\), what we need is the coefficient of \(x^n\) in <br />
\[<br />
\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}}<br />
\]<br />
Now \(x^c-1=(x-\omega_{1})(x-\omega_{2})\cdots(x-\omega_{c})\) and we can represent the product above as<br />
\[<br />
\frac{(-1)^{k}}{Q(x)} = \frac{(-1)^{k}}{(x-a_1)^{m_1}(x-a_2)^{m_2}\cdots(x-a_l)^{m_l}}<br />
\]<br />
where \(m_i\) is the multiplicity of \(a_i\) in the denominator. Decomposing in partial fractions we get <br />
\[<br />
\sum_{i=1}^{m_1} \frac{A_1^{i}}{(x-a_1)^{i}} <br />
+ \cdots + <br />
\sum_{i=1}^{m_l} \frac{A_l^{i}}{(x-a_l)^{i}}<br />
\]<br />
<br />
And using <br />
\[<br />
\sum_{n=0}^{\infty} \binom{n+k}{k}t^n = \frac{1}{(1-t)^{k+1}}<br />
\]<br />
<br />
we end up with (up to a factor \((-1)^k\))<br />
\[<br />
\sum_{i=1}^{m_1}\binom{n+i-1}{i-1}\frac{(-1)^{i}A_1^{i}}{a_1^{n+i}} <br />
+ \cdots + <br />
\sum_{i=1}^{m_l}\binom{n+i-1}{i-1}\frac{(-1)^{i}A_l^{i}}{a_l^{n+i}}<br />
\]<br />
<br />
To calculate \(A_i^{m_i}\) we observe that<br />
\[<br />
\left. \frac{(x-a_i)^{m_i}}{Q(x)}\right|_{x=a_i} = A_i^{m_i}<br />
\]<br />
and to get the other \(A_i\)s we have<br />
\[<br />
\left.<br />
\frac{1}{j!}<br />
\frac{d^j}{dx^j}<br />
\left(<br />
\frac{(x-a_i)^{m_i}}{Q(x)}<br />
\right)<br />
\right|_{x=a_i} <br />
= A_i^{m_i-j}<br />
\]<br />
<br />
<hr><br />
For the partial fraction expansion we have followed the exposition <a href="http://www.stanford.edu/~boyd/ee102/rational.pdf">here</a>.<br />
<br />
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\)<br />
\[<br />
F(x) = \frac{P(x)}{Q(x)} = \frac{P(x)}{(x-a_1)^{k_1} \dots (x-a_l)^{k_l}}<br />
\]<br />
partial fraction expansion has than the form<br />
\[<br />
F(x) = \sum_{i=1}^{k_1} \frac{A_1^{i}}{(x-a_1)^{i}} + <br />
\sum_{i=1}^{k_2} \frac{A_2^{i}}{(x-a_2)^{i}} + <br />
\cdots +<br />
\sum_{i=1}^{k_l} \frac{A_l^{i}}{(x-a_l)^{i}} <br />
\]<br />
<br />
Then<br />
\[<br />
\left. F(x)(x-a_i)^{k_i}\right|_{x=a_i} = A_i^{k_i}<br />
\]<br />
and to get the other \(A_i\)s we have<br />
\[<br />
\left.<br />
\frac{1}{j!}<br />
\frac{d^j}{dx^j}<br />
\left(<br />
F(x)(x-a_i)^{k_i}<br />
\right)<br />
\right|_{x=a_i} <br />
= A_i^{k_i-j}<br />
\]Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7438549283734029720.post-42372623697012283312012-02-03T23:57:00.001+01:002012-11-24T19:14:28.698+01:00Relative INTERP in ELF and set-uidThe combination of a set-uid and a relative path in the INTERP section of an ELF binary is very dangerous. <br />
<br />
This seems to be general security issue/leak concerning how dynamic linking in linux/glibc works, so let me explain what it is: <br />
<br />
Consider building a dynamically linked binary and specifying a relative path in the ELF <code>INTERP</code> section (using the <code>--dynamic-linker</code> 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).<br />
<br />
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.<br />
<br />
To demonstrate this, take a look at the following C code (issue.c): <br />
<br />
<pre class="brush: 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());
}
</pre><br />
If you now execute the set-uid binary like this<br />
<br />
<pre class="brush: bash">./issue
</pre><br />
or even just do this<br />
<br />
<pre class="brush: bash">ldd issue
</pre><br />
instead of getting what you might expect, e.g.<br />
<br />
<pre class="brush: bash">(vulnarable) euid:0
</pre><br />
you get<br />
<br />
<pre class="brush: bash">(rootkit) euid:0
</pre><br />
The point is you could replace the <code>ld-linux-x86-64.so.6</code> binary with whatever you like, and it will get executed with root permissions.<br />
<br />
Similar issues seems to have been addressed by not resolving <code>$ORIGIN</code> in <code>RPATH</code> or ignoring <code>LD_LIBRARY_PATH</code> if the set-uid flag is set. <br />
<br />
So I wonder if the <code>INTERP</code> in ELF has to be ignored whenever the set-uid flag is set (i.e. by using the default dynamic linker - <code>/lib32/ld-linux.so.2</code> or <code>/lib64/ld-linux-x86-64.so.2</code>)?<br />
<br />
So what do you think, where should this be fixed or reported - in glibc or the kernel?<br />
<br />
The discussion at stackoverflow <a href="http://stackoverflow.com/questions/9019083/security-issue-with-set-uid-and-a-relative-path-for-interp-dynamic-linker-in-e">security issue with set-uid and a relative path for INTERP (dynamic linker) in ELF</a>.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-7438549283734029720.post-26197291748886814922009-07-02T09:57:00.004+02:002012-02-07T20:17:49.973+01:00Joshua Bloch: Here's a Mystic Code PoemThe <a href="http://java.sun.com/developer/technicalArticles/Interviews/devinsight_4/#1">Mystic Code Poem</a> from Joshua Bloch could be written down in an even more mystical and funny way: <br />
<blockquote><pre class="brush: c">int inverse(int __) {
int _=__;
_*= -~-~- (__*_);
_*= -~-~- (__*_);
_*= -~-~- (__*_);
_*= -~-~- (__*_);
return _;
}</pre></blockquote>Not quite obvious, but the code above will find the multiplicative inverse of its odd parameter, e.g. <code>N*inverse(N) = 1 mod 2^32</code>.Unknownnoreply@blogger.com0