MagicalTux in Japan

Geekness brought me to Japan!

Archive for category Hacking

Xilinx Virtex 7 (VC707 board) first steps

May 8

Posted by MagicalTux in Geek Attitude, Hacking | No Comments

FPGA are an option I see the best for our future in terms of computing. Right now programming a FPGA is still a pain, but it’ll be easier with time, and enables developers access to a power they do not usually get to touch. I decided to give FPGA programming a try and acquired the Xilinx VC707 test board. That board has a lot of ports, making it perfect for a wide range of things.

The first step is, of course, to get the included software to run on Linux. Being a Linux Gentoo user (and this kind of software being usually targeted at outdated RedHat releases) I was ready for some trouble.

Strangely enough, the installer actually worked (mostly) and installed almost all the files in /opt/Xilinx. The drivers didn’t install (some not at all, some a bit) but the soft was mostly running fine. At first I was troubled because this seemed to require a thing called WinDriver. Someone made an opensource implementation of this, but in the end the VC707 does not use this at all, so I didn’t need to get it working.
What the VC707 is using is Digilent hardware, and the driver on Linux segfaults instantly when you try to use it. Searching on Google finally led me to someone with the same issue who had a really simple – and working – fix.

To run Xilinx ISE, you need first to setup the environment on Linux, and the fix for Digilent driver is part of the env, so I’ve put everything in the same file.

export LD_PRELOAD=/usr/local/lib64/digilent/adept/libdpcomm.so.2
source /opt/Xilinx/13.4/ISE_DS/settings64.sh >/dev/null

This makes ISE working just fine on Linux Gentoo. I had a lot of trouble getting Digilent’s lib working fine, and I’m considering writing a Gentoo ebuild for this, as it’ll make it much easier…

Anyway I was able to compile my first VHDL program (something as easy as GPIO_LED_0 <= GPIO_SW_N and GPIO_SW_S) and run it on the board, so now I’m ready for more complex stuff!

Tags: , , , ,

Facebook Hacker Cup 2011 Qualification Round: the PHP code

Jan 11

Posted by MagicalTux in Hacking, PHP | No Comments

I wrote about how I completed the 3 exercices of Facebook’s Hacker Cup 2011 qualification round in my previous posts (Double Squares, Peg Game and Studious Student) and now I’ll provide the code I wrote. Since the Facebook qualification round ended, I guess it’s safe to post, and will allow people who have kept their input and output to really confirm if they won or not (it seems some people receive mails saying they do, then saying they don’t… looks like the Hacker Cup was hacked together a bit too quickly).

As I said previously in the Double Squares post, the concept was not to make nice code or think for a long time, but complete the exercices as fast as possible to have a correct output before everyone else. Instead of optimizing the code and write nice long comments, I wrote code that would provide the correct output with the minimal amount of coding efforts (which was achieved by being brutal). Because of this the code is almost not commented. If you want to understand what you see, you’d better look at the appropriate posts.

The code is meant to be run from PHP command line, using the php interpretor, or using php’s cgi binary (with flag -q). It should work with PHP 5.1+ (I use PHP 5.3) and will produce the output for the .txt file with the same name.

Instead of reading the number of entries in the file (first line) I ignored it and will just read each file until I reach EOF, ignoring empty lines (like the final line). There might be some ugly hacks, but it wouldn’t be a Hacker Cup without some hacks.

The code, in a 23kB .zip file

Remember that this was written as fast as possible. The goal was not to make nice code, but to make code quickly. It will work and produce correct output given any valid input data.

I’ll be back next week!

Tags: , , ,

Facebook Hacker Cup 3/3: Studious Student

Jan 11

Posted by MagicalTux in Hacking | 8 Comments

After talking about Double Squares and Peg Game, here is the last of the serie: Studious Student.

At first it may look like the easiest problem, however there is a trap here. Reading the problem quickly may let you think “oh, I just do alphabetical order and stick the words together”, but no. If you think that you’re doomed. I say that because I saw an example code on internet (in Java) which does exactly that while claiming to provide the right answer for this Facebook puzzle.

Facebook helped you a lot by putting this special case in the examples provided in the page (if it was me, I wouldn’t give it out that easily). Let’s have a look at this example:

5 jibw ji jp bw jibw

If you just order this in alphabetical order, you get “bw ji jibw jibw jp”, but this is not the right answer. The right answer would be “bw jibw jibw ji jp”. That’s because alphabetical order will count a word which is equal to the beginning of the next word as having precedence. This rule is irrelevant here since all the words are concatenated into a single string.

At this third problem I was still feeling brutal, so I wrote another bruteforcing code. I noticed the maximum of word count was rather low (9 words) which makes bruteforcing a viable solution again. Going through all the possible permutations for a given set is easy (with some recursive function calls) and with only 9 elements to play with, the maximum number of values I would have to test was 362880. Of course it’ll take some time, but not that much (actually it took 30 seconds to run in PHP).

I just generate every single possible permutation, and I compare it with my “current lowest”. If the new one is lower I replace the “current lowest”, then continue to the next value. Simple. And provides the expected result.

~

As I said my only regret here is having Facebook include the trap in the example values given on the page. But still, it must have cleared a lot of the “I never read exercice texts” guys.

So, that’s all for now. I’ll be doing this again next week after the first round!

Tags: , , ,

Facebook Hacker Cup 2/3: Peg Game

Jan 11

Posted by MagicalTux in Hacking | 2 Comments

Continuing my previous post, let me explain the second game now: Peg Game.

The concept is simple: there is a board with pegs, and a ball falls from the top. Each time it hits a peg, it has 50% chances of going to the left, and 50% chances going to the right, except if one of the directions is not available (the peg is on the side of the board). Sometimes pegs are missing (the board is old) and in this case the ball has nothing to hit, and has 100% chances of falling (gravity helping). The first and last lines of pegs are guaranteed intact. Also the board size is variable (but the first and last lines will always be wide lines).
The goal is to find the entry point with the most chances of arriving to a given exit.

Since I’m still in my “let’s be brutal” mood, I’ll be using a brutal way of solving this problem. I’ll be tracking chances from each entry point (holes between pegs on the first line), processing line after line until I reach the end, then I’ll check probability at goal point for each entry point and take the best one.

By checking the examples provided by Facebook I noticed that if two entry point have the same highest probability of win, the left-most one is to be taken.

For example a 5×5 board looks likes this:

 | | | |
x x x x x
>x x x x<
x x x x x
>x x x x<
x x x x x
 | | | |

On this 5×5 board, we have 4 entry points, and 4 exit points, indexed starting at zero. Missing peg coordinates ignore empty space.

For this exercices too I decided to go with PHP, and have some fun bruteforcing every possible outcome for all the entry points, in order to then select the outcome most fitting for our need (best chances of reaching goal).

The first step is to create a in-memory representation of the board (including missing pegs). I decided to use two dimentional arrays, and use the value to know what I have in a given place: nothing (false), a peg (true) or the board limits (NULL). A 5×5 board will be represented as a 9×5 array (I take empty spaces into account).
I then initialize my “probability” array for the first line, in which the probability of my ball being in column 1 when dropped in column 1 is 100%, etc. (probability of ball being in column 0 is 0 anyway, I coded that to avoid doing a special case for those).

I then iterate each line of my peg board through a function that will generate the new ball position probability for each initial position based on the line being analyzed. By default previous probability is inherited. If I hit a false (nothing) then nothing happens. If I hit a true (peg) in middle of board, half of the value is added to left and right cells, and current cell is set to zero, and if the peg is on the side of the board, probability is moved in the opposite direction. I shouldn’t hit NULL with a non-zero probability, but I coded it anyway (moves probability one or two cells toward the middle based on the existance of a peg or not in the next cell).

This proved to run quite fast despite using PHP (~60 seconds to run on facebook’s input file, which is less than the alloted 6 minutes) and gave the right results, which is good.

Tags: , , ,

Facebook Hacker Cup 1/3: Double Squares

Jan 11

Posted by MagicalTux in Hacking | 6 Comments

The “2011 Facebook Hacker Cup” is currently happening, and the qualification stage has just finished as I write those lines.

Since I like solving fun problems I took part and solved all 3 problems and will  be progressing to next stage. The goal here is speed (code won’t be reviewed by Facebook staff, but you need to produce results fast) so I decided to trade CPU cycles for development time. It took less time to write the code, but the CPU usage will be a bit more intensive than what it could be if I took time to optimize the code and fine more elegant ways to produce the required output.

So, let me explain the first one, called “Double Squares”. The problem here is quite simple, and revolves around the following equation:

x² + y² = a

Only a is known. x and y are both integer values between 0 and 2147483647 (0x7fffffff, the maximal value for a signed integer). The goal is not to find x or y, but to determine how many values of x and y can yield to the equation being true. And reversing values for x and y do not count as an extra solution.

First, let’s make this equation a bit easier to handle, shall we? What if we write our equation this way:

y = sqrt(a – x²)

We could then cycle through the possible values of x, compute y each time and see if it is integer. The problem makes things even easier:

  • We know the minimal value of y is 0, which means the maximal value for x would be sqrt(a). Since the maximal value for a is 2147483647, this means x will never be over 46340.
  • To avoid duplicate values of x and y we can stop as soon as y goes below x. This also means that in the worst case, we’ll have to test half of all the possibilities (23170 iterations in worst case is viable)

Looks like bruteforce is a viable solution.

My implementation in PHP needed about 200ms with the values from Facebook’s input. I was a bit disappointed it ran this fast (can’t really call it bruteforce) but at least the result is good.

Tags: , , ,

KDDI in Japan: new routers?

Oct 3

Posted by MagicalTux in Hacking | 1 Comment

KDDI in Japan recently started to provide new routers to people who migrate. The main change when receiving the new router is the fact there is no longer a need for a PPPoE session, which means a larger bandwidth available on the line.

However the nice shiny router provided by KDDI has not enough CPU power to route that much traffic, so like anyone else why not use a small linux box (in this kase a Kurobox Pro) and have it do the routing stuff?

Easier said than done. Our friends at KDDI really want everyone to use their modems (a BL190HW) and have added a few ways to avoid people with normal routers to use their network.

The first thing anyone will notice is the fact the router will only talk to the device with the right MAC address. That’s a quite common protection, and changing the MAC address of a device is trivial. After doing this the network works fine for a few hours then… nothing.

I then connected the router they provided and had a look at the stuff that went through on the network… and I noticed something else.

Our friends at KDDI have decided to add an extra “layer” of security: the modem will login using EAP authentication over ethernet (protocol 0x888e) using the modem’s serial number as login and an unknown secret. Since I do not have access to the modem firmware, it’s difficult to know what the secret is, however I do not want internet to go down every X hours, so I wrote an “EAP relay” which receive EAP-over-ethernet frames on two interfaces and will relay them to the other interface. The program I wrote is ugly but works.

Now I’ll work to get a copy of the firmware (if the modem indeed checks for update, it should be trivial) and analyze it to see if I can either:

  • Find how the secret is stored and/or generated
  • Locate any security exploit that would allow root access on the box
  • Crack/locate the password for the box
  • Push a modified firmware update to the router that would allow access from outside

The router introduces itself as “NetBSD/ovismips” via telnet, however refuses root login over this kind of non-secure channel…

Tags: , , , , ,

SeedFuck… oui..? non !

Apr 29

Posted by MagicalTux in Geek Attitude, Hacking | 14 Comments

Ça fait longtemps que je n’ai pas écrit d’article en français, mais ces derniers jours je vois que beaucoup de français se disent “ça y est, avec SeedFuck, Hadopi est fini”. Je tiens a préciser que non! Ça m’énerve de voir tout un tas de sources s’extasier devant du vent en croyant savoir comment le P2P en torrent marche (pour la petite histoire, je suis l’auteur d’un client torrent que personne n’utilise, mais ça fait quand même de moi quelqu’un qui sait comment ça marche).

Je ne suis pas particulièrement un défenseur d’Hadopi, mais je ne compte pas rester les bras croisés pendant que de telles inepties circulent sur Internet. Nos amis nantais (Trident Media Guard) n’auront pas de difficulté a passer au travers de SeedFuck et déterminer aisément les vraies ips.

Si j’était moi même une société nantaise mandatée par l’état pour tracker les ips qui téléchargent et partagent un fichier torrent donné mon mode opératoire serait légèrement différent. Le processus serait simple:

  • Connexion au tracker comme étant un client avec 0% du fichier, le tracker envoie une série de peers auquel je peux me connecter. Le tracker va également publier ma propre IP pour permettre aux peers de se connecter à moi.
  • J’établis des connexions aux peers et j’attend d’en reçevoir
  • Pour chaque peer qui se connecte à moi, ou que je contacte:
    • Je lui demande une partie du fichier qu’elle a et que mes autres peers n’ont pas ou peu (prévu comme ça dans le standard bittorrent)
    • Une fois la partie reçue je compare son checksum à ce qui est indiqué dans le fichier torrent
    • Si ça match, je stock la partie reçue avec l’ip d’origine, et la date/heure. En effet j’ai sous les yeux un flagrant délit de distribution de données sous copyright par une ip “en personne”

Ce mode opératoire rend la détection du client d’analyse Hadopi difficile (se comporte comme un client torrent, et l’usage d’un client id + une ip dynamique changés chaque jour n’aidera pas a la détection) tout en donnant une preuve irréfutable qu’une IP donnée a participé à un acte de piratage.

Seedfuck se contente d’ajouter dans les IPs connues du tracker de nouvelles IPs aléatoires. Cela signifie pas que ces ips vont réellement distribuer le fichier en question. Tout ce que ça fera est de réduire le ratio de peers valides dans la base du tracker, et diminuer la qualité du téléchargement P2P.

Donc je dis bravo à celui qui a imaginé Seedfuck, y’avais pas mieux pour aider l’état !

FAQ

Y’a écrit dans le brevet de TMG qu’ils n’allaient pas faire comme ça.

On peut espérer pour eux qu’ils n’ont pas prévu de rester sur une méthode unique du début à la fin. Si je peux me permettre de le rappeler, le combat entre le bien et le mal est un combat sans fin où chaque côté a l’avantage un moment, et ne l’a plus le moment d’après (à vous de décider quel côté est le bien et lequel est le mal).

De toutes façons le fait d’avoir breveté une méthode (moisie) ne les empêche pas d’utiliser une autre méthode.

Vérifier un checksum pour un morceau de fichier ne permet pas d’être sur a 100% qu’il s’agit bien du même fichier

Oui non hé ho! On parle là d’une IP qui répond au protocole bittorrent, confirme être sur le torrent en question, et qui a fourni des données binaires pour lesquelles le SHA1 correspond exactement. Les chances d’avoir une collision en SHA1 sont extrêmement faibles, pour le moment aucune collision n’a été trouvée, et les chances de collision sont calculées à 1 sur 2^63, ça laisse du temps).

Même si on ne peut effectivement pas être sur a 100% de rien du tout, c’est du 99.99999% avec de toutes façons une IP qui répond au protocole BT (la méthode TMG est plutôt du genre 70%).

PS: Si vous m’en voulez de donner un mode opératoire qui permet de contourner seedfuck ou n’importe quelle autre méthode en générant un cas de flagrant délit (l’ip en question a fourni un bout de fichier qui correspond au checksum du torrent, et donc est valide), essayez plutôt de vous demander pourquoi vous n’y avez pas pensé vous même.

Tags: , ,

Invision Power Board and IPv6, a dirty hack

Feb 18

Posted by MagicalTux in Geek Attitude, Hacking | No Comments

Since IPS seems to lack the willingness to fix the IPv6 issue with their software, and given the amount of users willing to totally disable IP protection on their board to allow IPv6 users, I decided to provide with those people an alternative solution allowing to differenciate users.

This will create fake IPv4 for IPv6 users based on the 64 first bits of their IP. As most currently exising IPv6 providers are assigning /64 classes to their customers, banning the generated IPv4 effectively bans the whole IPv6.

Also I do generate a 32bits IPv4 from 64bits of IPv6 using XOR. While this means people using IPv6 might share the same generated IPv4 (quite unlikely), it is usually impossible for someone to obtain a different generated IPv4 without access to more than a /64 (I believe only system administrators have this kind of thing).

You might want to store in database generated IPv4 and their IPv6 counterparts to be able to recover a given IPv6 from a blocked IPv4.

This method also allows to block IPs in the same subnet from IPv4 subnets (I don’t know if IPB supports this feature) and recognize people from the same subnet as the start of their generated ip will be the same (however whois information for the given IP will not match the real user’s ip).

To have the generated IPv4, insert this in conf_global.php :

$encoded_ip = inet_pton($_SERVER['REMOTE_ADDR']);
if (strlen($encoded_ip) == 16) {
    $ipv4 = '';
    for($i = 0; $i < 8; $i += 2) $ipv4 .= chr(ord($encoded_ip[$i]) ^ ord($encoded_ip[$i+1]));
    $_SERVER['REMOTE_ADDR'] = inet_ntop($ipv4);
}

And remember to ask your IPB support to have real IPv6 ASAP.

Tags: , , , ,

Invision Power Board and FaceBook connect on Chrome

Feb 3

Posted by MagicalTux in Hacking | 1 Comment

Some people who manage Invision Boards have seen the new “FaceBook connect” feature as something interesting… However at first, I couldn’t see the “Connect with FaceBook” button.

Searching around a bit finally got this error from Chrome:

Unsafe JavaScript attempt to access frame with URL http://bbs.gg.st/index.php?app=core&module=global&section=login from frame with URL http://www.facebook.com/extern/login_status.php?api_key=10e950be918b8f0561e2073c53f2ab8e&extern=0&channel=http%3A%2F%2Fbbs.gg.st%2Finterface%2Ffacebook%2Fxd_receiver.php&locale=en_US. Domains, protocols and ports must match.

On Firefox (and probably other browsers), this works without problem. Just sharing that so other people do not get stuck with the same problem.

Tags: , , , , , ,

Doing the impossible with apache modules

Jan 15

Posted by MagicalTux in Geek Attitude, Hacking | No Comments

I’ve been fighting with apache during the past few days to try to accomplish something that has never been done until now.

Apache has some nice included modules, for example mod_vhost_alias. This module allows someone to configure vhosts by just creating directories however it has some limitations:

  • It will cause problems with some other modules like mod_rewrite
  • You can’t configure stuff (php options, etc) by host (only with .htaccess files, but you can’t alter all settings)
  • It can’t handle variable kinds of domains

I decided to do something better, even with the people on #apache-modules (freenode) saying it’s not possible. It was even no possible to do this cleanly, however looking in apache’s code allowed me to reach my goal without too many problems, but with some really dirty parts.

#define CORE_PRIVATE

To reach my goal I needed to use some functions from Apache2′s core. I just wanted to say that I am really sorry, and won’t do it again (maybe). The functions I used are not meant to be used the way I used them, however I had no choice has there is no publicly available function to change the document root, or to inject configuration directives in the current request.

Anyway don’t do this at home, kids!

ap_get_module_config(…, &core_module)

One of the keys to play with core config dynamically is to fetch it. This is the way to modify ap_document_root. I just return DECLINED after completing my dirty work to let apache think it still has to do its work. Yes this is dirty. But it works.

ap_walk_config()

Ever wanted to do bad things in a per-config context? Now you can. I won’t comment this too much, but I’ll just say that it saved me big time (this one is not part of CORE_PRIVATE, so you can use it freely I guess).

The final step was to make logging easier. I decided to throw all the logging info through a udg socket which is then collected by a daemon, stored locally, and transferred to the logging server at the same time.

Tags: , , ,