Category Archives: Français

Rapport de TER : Inégalités informationnelles et groupes finis

Mon rapport de TER (Travail d’étude et de recherche) est disponible ici (en français uniquement pour le moment). J’y étudie un résultat de Chan et Yeung qui fait apparaître un lien entre les inégalités de grandeurs informationnelles (au sens de la théorie de Shannon) et la théorie des groupes finis. Le principal attrait de ce résultat est qu’il permet potentiellement d’utiliser les nombreux résultats de la théorie des groupes pour prouver de nouvelles inégalités de grandeurs informationnelles.

L’algo Rho de Pollard

(Pollard, 1975) On rappelle qu’on cherche à factoriser un entier \(n\), qui est le produit de deux nombres premiers distincts \(p\) et \(q\) (i.e., on cherche à retrouver un des deux facteurs \(p\), l’autre facteur se calculant ensuite simplement). Cet algorithme n’est pas une attaque sur RSA à proprement parler, car il ne fonctionne que si le nombre à factoriser n’a que de petits facteurs, ce qui n’est pas le cas pour RSA.

Idée

L’idée de l’algorithme Rho et que si on parvient à trouver deux entiers distincts \(x\) et \(x’\) inférieurs à \(n\) et tels que \(x \equiv x’\ [p]\), alors \(x-x’\) est multiple de \(p\). Comme \(n\) est également multiple de \(p\), le PGCD de \(x-x’\) et \(n\) sera multiple de \(p\), ce qui signifie qu’il sera égal à \(p\) ou \(n\). Ainsi, on teste successivement des paires \((x,x’)\) d’entiers de \([0,n-1]\) jusqu’à trouver une paire telle que le PGCD de \(x-x’\) et \(n\) est supérieur à \(1\) mais inférieur à \(n\). Cette méthode s’implémente facilement :

Continue reading

Niveau 5 : Buffer overflow, part 2

Le niveau 3 n’était pas très réaliste : le code qui lançait un shell était déjà dans le programme, ainsi que le code pour l’appeler, et il ne restait plus qu’à modifier une adresse. Le niveau 5 l’est un peu plus :

level5@io:/tmp/bach$ cat /levels/level05.c 
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {

	char buf[128];

	if(argc < 2) return 1;

	strcpy(buf, argv[1]);

	printf("%s\n", buf);	

	return 0;
}

Continue reading

Niveau 4 : The system() has failed

Le niveau 4 est de prime abord encore plus énigmatique que le niveau 2 :

level4@io:/tmp/bach$ cat /levels/level04.c 
#include <stdlib.h>

int main() {
	
	system("id");

	return 0;
}

Quand on l’exécute, ça donne :

level4@io:/tmp/bach$ /levels/level04
uid=1004(level4) gid=1004(level4) euid=1005(level5) groups=1005(level5),1004(level4),1029(nosu)

ce qui a au moins l’utilité de nous rappeler que le programme tourne setuid. La solution est assez évidente pour qui connaît un peu les systèmes UNIX :

Continue reading

Niveau 3 : Buffer overflow, part 1

Enfin, on devient des 7r00 h4><0rZ qui exploitent des buffer overflows. :D Encore une fois, on a le code source :

level3@io:~$ cat /levels/level03.c 
//bla, based on work by beach

#include <stdio.h>
#include <string.h>

void good()
{
        puts("Win.");
        execl("/bin/sh", "sh", NULL);
}
void bad()
{
        printf("I'm so sorry, you're at %p and you want to be at %p\n", bad, good);
}

int main(int argc, char **argv, char **envp)
{
        void (*functionpointer)(void) = bad;
        char buffer[50];

        if(argc != 2 || strlen(argv[1]) < 4)
                return 0;

        memcpy(buffer, argv[1], strlen(argv[1]));
        memset(buffer, 0, strlen(argv[1]) - 4);

        printf("This is exciting we're going to %p\n", functionpointer);
        functionpointer();

        return 0;
}

Donc il faut trouver un moyen d’appeler la fonction good()

Continue reading

Niveau 2 alt : NaNaNaNaNaNaN, Baaaaatman !

La version alternative du niveau 2 est un piège redoutable :

level2@io:~$ cat /levels/level02_alt.c 
/* submitted by noname */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>


#define answer 3.141593

void main(int argc, char **argv) {

	float a = (argc - 2)?: strtod(argv[1], 0);

        printf("You provided the number %f which is too ", a);


        if(a < answer)
                 puts("low");
        else if(a > answer)
                puts("high");
        else
                execl("/bin/sh", "sh", "-p", NULL);
}

Il faut donc passer une valeur qui ne soit ni inférieure ni supérieure à 3,141593. Fastoche !

level2@io:~$ /levels/level02_alt 3.141593
You provided the number 3.141593 which is too low

:(

Continue reading

Niveau 2, ou les joies de l’arithmétique sur machine

Le niveau 2 est très différent du premier :

level2@io:~$ ls /levels/level02*
/levels/level02  /levels/level02.c  /levels/level02_alt  /levels/level02_alt.c

Non seulement il existe en deux versions, mais en plus on a accès au code source. Ça devrait être simple, alors… Commençons par le premier, le code source est d’une simplicité déconcertante :

level2@io:~$ cat /levels/level02.c 
//a little fun brought to you by bla

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <setjmp.h>

void catcher(int a)
{
        setresuid(geteuid(),geteuid(),geteuid());
	printf("WIN!\n");
        system("/bin/sh");
        exit(0);
}

int main(int argc, char **argv)
{
	puts("source code is available in level02.c\n");

        if (argc != 3 || !atoi(argv[2]))
                return 1;
        signal(SIGFPE, catcher);
        return abs(atoi(argv[1])) / atoi(argv[2]);
}

On dirait qu’il suffit de se débrouiller pour appeler la fonction catcher()

Continue reading

Un peu de hack…

Pour ne pas (trop) perdre la main à force de ne faire que des maths, j’ai commencé récemment à jouer sur smashthestack.org, plus précisément sur io. Je vais poster ici ce que je trouve ; évidemment les pros trouveront ça trivial (au moins pour les premiers niveaux, qui n’utilisent que des techniques de base), mais les autres apprendront peut-être quelques petites choses… Pour les intéressés, ça se passe par là :

ssh level1@io.netgarage.org

Le mot de passe est level1. Le niveau 1 est un bête programme qui prend un mot de passe en paramètre :

level1@io:~$ /levels/level01 
You need to supply a password.
Usage: /levels/level01 [password]
level1@io:~$ /levels/level01 foo
Fail.

Le but est évidemment de trouver le mot de passe. La solution après le jump…

Continue reading