Older blog entries for dangermaus (starting at number 65)

31 Dec 2012 (updated 31 Dec 2012 at 22:52 UTC) »
"You just keep pushing. You just keep pushing. I made every possible mistake that could be made. But I just kept pushing!" René Descartes 1596-1650

This is a report for the last months spent at the Open Source front and marked by several failures including the loss of the last server for the Global Processing Unit project. Hidden around the corner there was some success, too.

deltasql

deltasql was essentially improved in two ways: copy&paste support via browser was added using the ZeroClipboard library. It is not necessary anymore to manually select the SQL script before copying it. With another library called OpenFlashChart (by John Glazebrook), we added graphs and pie charts to show how the complexity of a deltasql server increases over time. The number of scripts and of synchronizations are shown in a line chart, the size of modules and projects in pie charts. The latter improvement was picked up by Linux Magazine and deltasql 1.5.0 did a short headline also in the printed edition of the magazine.

Global Processing Unit

The change which gave me most pleasure was adding variable daylength duration depending on the day of the year and latitude to the Simclimate frontend. The effect is given by the inclination of the Earth rotation axis in respect to the ecliptic plane (the plane which contains both Earth and Sun). Earth inclination is called declination, too. Declination gives the typical bell shape to the sunlight projected onto the 360x180 degree matrix of the world's surface. I documented for the first time Simclimate here.

I finally documented the Orbit Reconstrunction and Analysis extension as well. The discovery of the likely cause for the Pioneer Anomaly puts an end to the development of this extension. The cause of the tiny anomalous acceleration toward the Sun experienced by the Pioneer space probes is probably due to the radioactive heat of the power source reflected by the parabolic antenna dish of the space probe, and not due to new Physics. For the rest, the domain www.gpu-grid.net is down, GPU clients do not autoupdate nor connect automatically to each other anymore.

Adventures on hacker.org

Our soliders fought epic battles totalling 229 challenges solved. Solving some of them gave me a kind of Zen flash. Some ROT13 hints on my favourite challenges follow:

Sbe 'Nalobql Bhg Gurer', V erprvirq na vzcbegnag gjrrg sebz rsr. Qvwxfgen urycrq zr jvgu 'Pnyphyngbe'. Urephyrf vf qrsvavgryl abg gur evtug rzhyngbe sbe 'Znvasenzr' orpnhfr vg vf gbb qvssvphyg gb frg hc. N oyhrvfu tybj ba lbhe snpr jvyy yrnq gb gur fbyhgvba bs 'Cbxr Zr'. Fbyivat 'Vafpehgnoyr' erdhverq zr gb tb onpx gb gur svefg punyyratr bs gur frevrf gb ercrng gur onfvpf. Va 'Wrhk qh Fbeg' V vzcyrzragrq gur gurbergvpnyyl snfgrfg nytbevguz, nygubhtu vg ghearq bhg gb or pbzcyrgryl birexvyy. Sbe 'Pnir Znfgre', qba'g ehfu ohg nqwhfg lbhe fcrrq. Naq fghqlvat Znqber'f fvgr urycrq zr jvgu 'Dhvar'.

I also wrote a Bash tool named discochal to compare challenge solvers. You can compare any two players and see which challenges where solved only by one player. Sometimes, this information is useful to infer additional information on difficult challenges (if you study a bit strengths and weaknesses of other players). The tool can be checked out from the GPU git repository following the instructions on the forum.

One of the challenges brought me to study the maths behind stereograms. The article "Bewegte Autostereogramme" in c't Programmieren 3/2012 has an interesting explanation on how to create stereograms using the Kinect sensor!

Tapeworm

Tapeworm is the fourth puzzle on hacker.org I am attacking (Runaway Robot, Crossflip and OneOfus being the first three), and here I miserably bit the dust. My automatic solver uses simple Depth First Search using hashes to detect already known boards and computing weighted shortest paths as simple heuristics, and barely solves level 40 because this puzzle is crazy deep. My beloved Virus managed to manually solve levels up to level 104. I had at least one good idea: to debug the code I inject into a html level template of Tapeworm my current board as javascript variable, and then look at the result in a browser as it would be a level on hacker.org. This probably works with other puzzles as well, but i never tried it before.

Firewall Analysis

I kindly received a configuration file of a midsize company to analyze. I discovered some interesting things, especially looking at the routing table. Many invalid IP subranges are all rerouted to the same server. Maybe a Nagios server (or one of its sensors) which is able to detect local port scans? On the DMZ there is a suspect IP address (with a SMTP rerouting for email notification), which might be a honeypot? An external security company reserved 20 IPs, specifying them one by one and called it HyperVM. Probably, they are monitoring the network from outside with 20 virtual machines! Amazing :-)

The LISP way

The challenge 'Cons Car' first, the book '7 languages in 7 weeks' later with Clojure, brought me to LISP and the LISP way of thinking. Although I am still looking for my own project to be developed in LISP, I experimented with the online book Practical Common LISP. I also read through the series on LISP by Douglas Hofstadter on old Scientific American issues. Looking at ways to replace the computational engine of the GPU project, I developed an interest in Computer Algebra Systems and looked at both Maxima and REDUCE which have a core in LISP. LISP was intentionally developed with the manipulation of algebraic equations in mind. One of the first conferences on LISP of its creator John McCarthy was about symbolic differentiation. The file sin.lisp of Maxima source package implements symbolic integration and references in the source code the original typewritten PhD Thesis of Joel Moses. LISP was the first language which introduced recursion and garbage collection, ideas later picked up by other programming languages.
The most powerful idea, which was never introduced in other languages, because if they would, they would look like LISP and simply become a LISP dialect, is that data and code are both expressed as lists and this gives to the language a particular plasticity. By using so called LISP macros (C/C++ macros express a different less powerful concept) it is very easy to extend the language; for example, try in any other language to implement a change that causes the programming language itself to be parsed in reverse order. In LISP, simply write

(defmacro backwards (expr) (reverse expr))

Now, you can sum two numbers with (+ 1 1) or more originally with (backwards (1 1 +))

And speaking of numbers: Common LISP natively supports big numbers, complex numbers (!) and conversion between numbers in an unrivalled way!
Another thing discovered by McCarthy is that in LISP, it is very easy to write an interpreter of LISP, no more than thirty lines are required to do it.

Other parallellization ideas

With LISP, I am looking to improve my understanding of (semi) functional languages. Stateless functions are easy to parallelize. One idea that popped up was running the Global Processing Unit on clients which would run MultiLisp and on top of them some Computer Algebra system. A Microsoft research paper, Gordon et al, Uniqueness and Reference Immutability for Safe Parallelism, points into another direction: variable qualifiers gives important hints to the compiler to compile code on parallel architectures. By the way, it is time to check the specifications of your graphics card: your dual core laptop might hide up to 100 CUDA cores which can run fragment shaders or vertex shaders in parallel! The magazine c't Programmieren 3/2012 has lot of source code to leverage this CUDA power!

Online book about Cryptography

The Codebreakers book features a comprehensive and interesting history of Cryptography, it just misses the developments at Bletchley Park because it was published before the documents were declassified. By the way, some more papers on Enigma by Alan Turing were declassified.

Broken Tire Story

When trying to reach the parent's house of Virus, the overloaded car hit a little stone. In the cockpit, I heard a loud bump and four minutes later we were at the house, greeted by the 'pffff' of the broken tire loosing air. I replaced the tire with a reserve one and then dedicated my attention to the sharp little stone down the street in the forest. Using shovel and pickaxe to remove the earth round it, I discovered that it was a big one, like the iceberg is just the tip of a huge block of ice. I thought I will never remove it, but being in holiday and not knowing how to use TNT, and where to buy it, I decided to give it a try. All of a sudden, I was able to move the stone a tiny bit, carefully leveraging with the pickaxe. Then another bit, I filled holes first with sand, then with stones of increasing size. About one hour later, I managed to remove the big stone and learned my daily lesson, namely that things which look impossible might turn manageable if worked out without pressure.

Wasp War and their Revenge

We found two yellowjacket nests hidden on the curtain of our balcony. Armed with a special spray (Gesal Protect), we decided to kill them all. I carefully read instructions on the spray can, but unfortunately missed to read the last sentence.
I dressed myself with jacket, scarf around my neck and gokart helmet to avoid wasp stings. It was a calm evening with no wind.
Then with an amazing jet coming from the spray at high pressure, I killed many wasps (counted the next day in daylight, they were 27). Doing the operation in the evening on the bare light coming from the apartment, I completely missed the tiny drops of insecticide which were in suspension at mid air. I breathed them, unaware that they were existing.
I felt like in Kafka's short story (the Metamorphosis) when I discovered with horror that the last sentence on the instructions was about avoiding to breath the insecticide (kind of obviuos, but you know... ehm)! Through the night, my lungs burned (the Prallethrin which stops air holes of the wasp?). The next day I almost had to stop working, I had dizziness and glows swirling in front of my eyes(the Cyphenothrin burning the yellowjacket brain?). Fortunately, the latter effect lasted only for twenty minutes, and the dizziness disappeared at midday and since then I am back human. The daily lesson thaught me this time that insecticides are really something to leave hands off, to be used with _extreme_ care, and I wonder how role they play in the scaring pollinator population decline.

Casino Adventure

I had the chance to visit a Casino: they gave us first a drink and then an introduction to the Russian Roulette and the Black Jack game. As premise let me mention that I never was lucky at games.
They gave us fifteen coins to test our understanding of Roulette rules. So, I put them all on Black, but the ball finished its trajectory to a Red cell. I lost all coins in one shot! The croupier and someone in our group laughed at me; oh man, someone who is so stupid, why not carefully playing complex combinations on corners! After three rounds with test coins on which I could not play because I already lost everything at the first, they gave us three real coins, each one worth five Swiss Francs.
Again, I put all three coins on colour (I think it was Red, honestly I do not remember) and won doubling them to six. I then put all them on Even and won again. I had now twelve coins and decided it was time to play Black Jack. Believe it or not, simply by playing Black Jack golden rule which was even written on the green table and saying 'Dealer must draw on 16 or less and stand on all 17s', I was able to increase my capital up to 27 coins. Fortunately, my group was now leaving for dinner and therefore I was forced to stop. I went to the bank to exchange the coins. They gave me 120 Swiss Francs but said, they can't turn the first three coins into cash because they are a gift from the Casino anyway. So, I have to play them or keep them as souvenir. I then looked myself around and found an old woman and gave the three coins to her. She looked wise to me and did not look them like a gift of destiny. So many people ruin their life and loose their wealth in Casino games because they do not understand that the randomness of the game is constrained by the rules with the ruler as ultimate winner (the Casino is the ruler).

Sal is my Khan

Peter Collingbridge published a tool to see personal statistics on Khan Academy. Freaks will like the feature to see how many minutes are needed to get the next Listener badge. I bought the book of Sal "The One World Schoolhouse" and found some interesting ideas. The first was kind of obvious for people actively using the academy, and it is about filling holes in education with videos. Then, there is the idea of mixed ages classes where older children can teach younger, and younger can have their superheros. Finally, I did not know that Sal managed to get three MIT degrees in parallel, avoiding lessons and just learning with peers on a bet on whom could do more courses at once!

Two incredible landings

We were all astonished, looking at the landing of Mars Rover Curiosity with sky crane and at the jump of Felix Baumgartner from almost outer space. After Space Shuttle's retirement there is new hope for advancements in space technology! Instead of expensive Soyuz vessels to return from the International Space Station, we could simply step out and jump from there :-) An incredible jump for a man, a huge leap for mankind!

Happy New Year, and many apologies for my English :-)
18 Mar 2012 (updated 19 Mar 2012 at 14:30 UTC) »

This is the monthly report after the usual battles fought in cyberspace and beyond!

Third encounter with AIX

Mauri was playing with hanging puppets and Marti was already eating Spaghetti, but we were all waiting my father for supper on friday evening. The phone rang once, I called back but it was busy. It turned out that my father phoned, however he had to stop the phone call as someone from IBM support finally called him. He explained me that he had a strange black box in a corner of a huge hall full with wine boxes (each with 12 bottles of prestigious wine!) which refused to boot up. On the black box one could read IBM 520, and closer there was a label saying "Type 8203-E4A N/S G5-208 B4". The server went down on friday morning at 9:45 when an electrician doing maintenance work removed fuses to work safely. The whistling UPS run unheard for a while, and the black beast died right after UPS finished its juice.

The whole company could not work without this server through friday. (on which a DHCP server, a file server and a billing software run), so my father decided to keep trying and to skip supper. I could not resist when he mentioned the box was running AIX, so dangermouse mounted in his car and drove to the huge wine hall equipped with ananas pieces, biscuits and the two laptops virgibuntu and andromeda. Intermezzo for the fans: the Calibra car lost the front spoiler in a close encounter with the guard rail, which explains the broken blizzard sign, too.

But back to the problem: the local network was not lying neither on the usual 192.168.x.x IP range, nor on 10.x.x.x. It was between 172.16.x.x and 172.31.x.x which was unusual setting for us, and the confusion was great. On the LCD panel of the IBM 520 one could find out that it was started in modality A which was sort of diagnostic modality. The box did not have neither keyboard nor screen and was silent like the monolith of Space Odissey.
It had a strange HMS port, but we did not know what HMS was. Either the manual of 500 pages we found in Internet about HMS forgot to introduce what HMS was, or we were so tired that could not figure out.

The next day, when the kind technician of IBM came, we learned how to use HMS to revive the server, and learned about the smitty utility, and why one of the hard disk never lighted. For short time, I had the root password of the box, but when I tried to login to have a ride, the software owner already changed it. It is the third time I encounter an AIX, but never had the chance to login and discover its inners! In the end, our job reduced to get the printers back up and running, and to add a samba network name to the host file, which for some reason the resurrected blackbox did not want to resolve. When we left, I glanced one last time at the misterious IBM 520 box, and I felt like it was laughing.


Phantom Computer

I discovered that Virtualbox 4 has much better network support. I used this fact to setup a Fedora Linux 16 with the Sage libraries, a phantastic collection of mathematical software. Additionally, I found out that GPU libraries worked well under Linux, especially the Synapse support made by Lukas Gebauer. There is still some hope for the version II of GPU then! And from the outside, this Fedora thing should appear like a phantom computer on its network segment!

OneOfUs

There were two lessons I learned with this puzzle: the first one is "let others help you"! In fact, I could not even solve the first level of the puzzle, while Virgi made it up to level 27. She explained me the rules of the game (we could not see them as we were logged in), and also some of the heuristics she was using, and to which mathematical problem it reduced (this can be found in the forum as well). I had a bad time passing the first level after that, but finally managed to do it! contagious told me that he used an external library to solve the Crossflip challenge. As my brute force solver barely brought me to level 60 and I could not find a way to implement Posa search, I decided to go with external libraries to defeat OneOfUs. I tried out many, including one of an author who made the claim P=NP. He was so kind to provide the C++ implementation, which you can't say of most of so called scientific authors. Still, his library did up to level 460, but then started going very slow. I teamed up with userfriendly, sharing what we discovered on the problem. After our briefing, he then skyrocketed to level 1000.

I kept stucked at level 460 knowing all what userfriendly knew. I worked through the night, but could not find the mistake in my solver implementation. I supposed an obscure error in the POST implementation of Synapse (the submitting part of the solver), but could not find any error after I created a test page to see what I submitted. Defeated, I went to sleep. I thought on all what I observed (including the fact that the "P=NP" solver in its slowlyness passed level 460) and then had the Zen flash, which each hacker.org puzzle hides. It turns out that my solver was in fact correct and it was solving the problem, just it was solving another problem which was not the one expected by hacker.org! I had a nasty mistake in the board generation for level over 242, but this mistake showed up only on bigger boards! The second lesson learnt is "if you think your code is right, it is. Look somewhere else!". For the record, the last level was solved in 20 seconds. The whole story can be seen here, when charting will work again.

Cheat Engine

Cheat Engine is an amazing Open Source tool which you can attach to any running process. Among other things, it identifies where integer variables are held in memory, so that you can modify them while you are playing. This helped me out a lot in a challenge I could not disassemble. I also tried "What in the World" without luck, but knowing what the sequences probably are. And failed on "Slim Image", too. On hacker.org, I often feel at the limit of what my mind can do and also what current software and hardware can do, which is a good introduction for the next section :-)

Geometric Visions

I read the Geometric Visions article of Michael Crawford, which is a great article not only about mental disease, but also about philosophy and about how people mind works in general.

I only had acoustic allucinations once, when i was living in a place close to a noisy rail station where i could not sleep. i never had problems with depressions or so, also because i can't focus on details, i do not care about details (which can be also a problem in life :-)

To tell the difference between voices and real life, i used Occam's rasor principle: if my reasoning started getting too complex, and one easier explanation (which might be hurting to myself) is easier, then i decided to believe the easier explanation and to fix my behaviour in positive ways. I found out that most of the time, complex reasoning was just an excuse to hide my misbehaviour. Occam's principle worked very well through my whole life.

Final notes

I found the OpenFlashChart library for PHP and I am now pepping up deltasql with charts. The hope is that such chart experiments will help the GPU project as well!

As final links the history of Commodore International and of its founder, and a note on the strange Kaprekar numbers.
That's all folks!

20 Feb 2012 (updated 3 May 2012 at 05:52 UTC) »
Per aspera ad astra Through difficulties towards the stars! This is all what was boiling into dangermouse software pot. It was also a time of reminiscences. First, a look on the journey in hackerland:

Enigma

The challenge is about decoding a ciphertext without knowing the rotors and their initial position. Fortunately, the plugboard position is known.

I saw the Enigma machine at the Imperial Museum of War in Lodon in 2007. It also remembered me when i was working for a security company. I had time to read Turing's treatise on Enigma and dreamed of having my own Enigma on the desk. This month, I read through this slide presentation. The presentation not only explains how Enigma works, it also gives an interesting historic background. It gives the correct light on the events before and after World War II. The difference between the commercial and army version of Enigma was the wiring of the keyboard... Why the Polish were the only who could crack Enigma... Allied where open mouthed when they heard someone could crack rotor machines.. The British collected Enigmas and gave it to colonies after WWII, without revealing they could decode them... And I wonder if the cycles used by Marian Rejewsky are part of the unpublished chapters 4 and 6 of the Turing's treatise. And what else is hidden in the two chapters!

I then used this reference implementation, and created my own Enigma implementation in Freepascal. While coding, I could hear the gears inside the machine moving, the smell of grease and the notches and pitches ticking inside the Polnish "bomba".

I did first the army version (5 rotors, 2 reflectors) and sorted out feasible solutions with the index of coincidence. I then exhagerated and implemented also the Naval version (8 rotors, beta and gamma wheels and adapted reflectors). Admiral Doenitz would be scared, if he would see it! Although I have to admit that this works only if the plugboard is known. So, Admiral, don't worry and sleep weel in your submarine hidden in the oceanic depth...

The source code is committed to the playgroud area of the GPU repository, as this might become one day a GPU plugin to compete against the Enigma@Home project.

Crossflip

Crossflip is a puzzle about light bulbs switching on and off. Goal is to get all light bulbs on the board to be glowing. I decided to avoid the approach with the previous puzzle 'Runaway Robot', namely to work through all levels of enlightment. So, in one evening I had the linear equations in GF(2) describing the problem. The first straightforward implementation with booleans worked until level 150, with the usual GET/POST problem at level 91. Another implementation with packed matrix brought me to level 300.

But once again, things worsened: the linked list approach was a miserable failure, as the memory management was taking definitely more time than expected. I tried several things to break the barrier of O(n^3), in particular I focused on iterative methods (which remembered me the time I was working for university). Steepest descent and Conjugate gradient did not work, due to the self orthogonality of the scalar product. I tried to workaround it by simply counting the numbers of bits... Then I tried Gauss-Seidel iteration as there is no scalar product in the iteration. Still, the algorithm did not converge to the solution. Maybe, I had a mistake in the implementation, or the matrix was not positive definite, or it simply does not work in GF(2), who knows?

At the end, I realized I had a major bug into the algorithm, when the system was undetermined. The bug is also in the Linear Algebra book we used at university, and now that I noticed it, I remember my friend Sid who pointed me at it! I could solve the last level (90000 variables) in 8 minutes 20 seconds. Andromeda compiled the last version of the code, and it was executed on Virus's computer. I did not implement one last optimization in this version, and the reverse elimination step was not optimized. I assume, with some more tackling, I could bring it down to 3 minutes, on 64 bit hardware. All in all, I had 15 different approaches, with more than 100 revisions. The whole story can be seen here. Now, I wonder if some system of linear equations could describe Eternity. For that puzzle, I have only the brute force approach in place...

There was also some other progress on the site: solving the challenge protecting the last upper-left corner castle took four evenings of focused thinking. "Lazy spiral" fall straight after.

And "Poke me", although still unsolved, remembered me when I (aged 9) was sitting with my father in front of the C64, he explaining me what "IF","THEN" and "ELSE" meant in Italian. I hope my sons will be interested as well in such stuff... I have an OLPC laptop around, I will show them, when it's time!

Some other updates from "real" hacking life follow:

deltasql 1.4.3

1.4.3 ships with a new feature: users who opt in, will receive an email notification each time a new script is inserted in deltasql.

This feature should easy the introduction in deltasql, where the development is currently done via emails. Users who are confident with deltasql will use it straight away, other users who are not conviced by deltasql strength can opt-in the email notification feature.

The only requirement for all users is that they need to insert the new script into deltasql instead of sending an email to the other users. Admins who would like to user this feature in production should consider installing patch level three available from here in the files section for 1.4.3.

For me, it was the first time I implemented a system which can send emails automatically. dangermouse is a spammer! :-D

Image resizing bomb

This bash script uses ImageMagick and takes as parameter to which percent you want to scale images down. It is useful for me to resize pictures from cameras to be published on the web.


#!/bin/bash
mkdir resized

FILES=./*
for f in $FILES
do
if [ $f != "./resize.sh" ]
then
echo "Resizing $f file down to $1 per cent..."
# take action on each file. $f store current file name
convert $f -resize $1% "./resized/$f"
fi
done




12 Jan 2012 (updated 12 Jan 2012 at 14:51 UTC) »

These are the latest from my hackerland journey. I feared that either me or the challenge site would go down, and in fact hacker.org is now temporarily unavailable since three days. Maybe it is under a Denial of Services attack of some user who is angry because he can't solve some challenge... Who knows?

Close to the last castle

With 190 challenges solved, I am close to the last castle on the upper left corner of the map. The challenges around it are very hard, none of them is solved, and after there will be a super-hard challenge anyway to protect this castle.

Being a dangermouse it was reasonably easy to solve some quests of the serie "Really Small Mouse". I brought the mouse down to 21 instructions, but there are some hackers who can do it in 20 and less! Cool challenges encountered on the road were 'No full ACK in SEPT' which refreshed modular algebra a bit, 'Maelstrom' to train image recognition, 'HVM cipher' and 'Really Simple Access' to revive my reminescences of cryptanalysis. While solving "Shattered and Shuffled" and "Shredded and Scrambled", I felt cold down my neck, it was the breath of the dark side who strucked me.

I suffered deceiving in "Such Much" and only an answer on the forum brought me back on track. I almost brought down hacker.org by submitting huge numbers calculated with Python! I attacked with brute force 'Soviet Intercept' and I almost locked me out of this challenge; now I have to wait one hour between submitting of answers for this particular challenge, though now I prepared a sort of key which should allow the identification of the spies.

For the cryptographic challenges involving unkown codes, I developed a tool to perform the kappa-test, and another one to perform the chi-test on vigeneres which have substitutions in columns instead of simple caesar ciphers. I wrote them according to this article. I found a good tool to perform first image analysis on Steganographic challenges here made by Caesum, the author of the Challenger's handbook. To perform coprime factorization I definitely recommend MSieve. Other discoveries were Binary Coded Decimals (BCD) and Setun, a Russian computer which was working with ternary balanced circuits :-)

deltasql 1.4.2 and beyond

1.4.2 was a tactical release, to get hands on code which I did not touch since three months and also to advertise deltasql through the Mantra of Open Source Release often, release early. The development of 1.4.3 is struggled by technical accidents (the server I am using to test went down, because the friend of mine who kindly hosts deltasql forgot to pay the bill). Additionally, I face now trouble pushing my code with git to sourceforge. But 1.4.3 will be fresh wind with several minor bugfixes, user preferences and the ability to inform users of new scripts via sendmail.

Finally, to remember myself on how to

Set default operating system in Grub

1. edit DEFAULT variable in /etc/default/grub
2. run sudo grub-update

19 Dec 2011 (updated 19 Dec 2011 at 15:59 UTC) »

There are many challenge sites on the net, and one to unify them all.

I decided to focus on hacker.org as there are many high quality challenges involving programming, cryptography and maths, and a bit less of ugly exploits and similar. The site organizes challenges on a map. Harder challenges are on mountains, easier ones on grass. Each time a challenge is solved, it opens the road to new challenges. Castles protect challenges that are on crossroads. Winning against a fortified castle opens new possibilities and new areas to be discovered.

From easy to hard or the other way round

Sometimes i get stuck solving a harder challenge. At first time, it looks like i am wasting my time, but the point is that if by chance i manage to solve it, several other challenges suddenly get much easier.

This was the case with the Labyrinth challenge, which forced me to develop new techniques for the HVM. In the end, I invested more than one month of time on it. Once Labyrinth was solved, I could solve the similar Deluge and the sequel "Flash Flood warmup" in one day. Other challenges like "King Mouse", "Brokenest Keys" and "Mus Minutoides" finally found a solution through new ugly techniques (mainly calls with no returns and what i call the statistical approach, to spoil them a bit).

To sharpen my weapons further, I put Caesum's Challengers handbook in my journeyer's backpack. And here I found a good explanation of the chi and kappa test, so that I added the index of coincidence to the magic spells I am aware of.

It was a great satisfaction to besiege the castle protected by 'Spiral bits'! The path following algorithm did his job well, but the decoding part was a complete nightmare, so that i turned the Lazarus GUI into a complete editor for inserting, deleting and flipping bits. I also had an integrated lens on board and a tool to compare the decoding on slightly different paths (which did not work very well though). And a good bit of luck was also part of solving it!

I then succesfully attacked 'No full ACK in HEX' and 'No full ACK in DEC', learning Knuth arrow notation, the tower of powers, and in particular learning Python's ability of computing with large numbers, which is unrivalled. Maple couldn't do what Python did. Now I know why some numeric people I worked with were so happy with Python :-)

And still, there is work to do. My armies failed several times against 'Blizzard' and 'Descartes'. The 'Captcha' prototype needs further refinement as well...

(current ranking on hacker.org is 188 with 180 challenges solved/on Khan 200 challenges solved and Copernicus badge reached, next goal is one million points)

2 Dec 2011 (updated 2 Dec 2011 at 10:02 UTC) »

Mauri is born! Marti now has a brother and we are all very happy to welcome him in our family :-) Might the source be with you, Luke.

In the following, some updates on our lone hackerland journey:

Runaway Robot

Probably some smart people go straight to the correct solution. For me, I walked through all stages of enlightment. I first developed a maze parser in Frepascal, then got a brute force solver in place which could solve up to about maze level 120. The solver started taking long times for each new level (up to 6 hours). I am a bit out of gear right now as we moved house, lost connection to civilization for some time, and still have to reactivate the server room, which will move from pavement to cellar. I remembered that spartacusII server got burned in a similar challenge and decided to upgrade the algorithm as soon as possible. With dynamic programming I restricted a bit the solution space. A first attempt with combinations failed, I tried to debug the way I create combinations, but could not find the mistake. I rewrote the algorithm and got a working solver for levels up to 153. Then again, the solver was taking too much time. Finally, I got a sort of Zen flash and found a way to retrieve the solution, as it would be just popping out from the maze. The new solver could solve any maze in less than a second, and easily moved up to level 513. When it solved level 514 (a level noone has solved), and was waiting the one minute delay to avoid server pounding before the solution is submitted, I got very proud. Too much proud, as the server answered: "Your solution sucked, maximum level for this puzzle is 513". This site is amazing, it does not forget to teach you to be modest :-) The whole story can be seen in this graph as well.

I then decided to attack another puzzle, Mortal Coil. Adapting the parser and getting a brute force solver in place was easy, as Runaway prepared the path. But now I am stuck at level 68. I found papers on the Hamiltionian path problem, which is NP-complete and now need to think on how to divide and conquer it.

Other challenges

On the Hack Virtual Machine, I worked out the meaning of the two commands ^ and v and such knowledge lead to some progress: by analyzing the solution of Execution Style, I finally cracked Hello Small World! Also revision 34 of my Labyrinth program could solve the three mazes, though it required several submissions. In fact, the limit of 40'000 cycles is very tight. The version which solved the challenge could solve the reference maze I was using only in about 53'000 cycles. The Labyrinth program is based on a wall following algorithm published in Nievergelt's book about Algorithms and datatypes.

I found in the depths of Internet an almost complete map of the challenges and it is clear now that to achieve some breakthrough, I need to work out Spiral Bits. The encoding is a bit hard, but by printing out the spiral on a piece of A3 paper, it is possible to work it out with some patience. The pathfinder solver I developed follows the spiral but keeps staying on the side, so I have to think a way to balance it a bit. To debug the breadcrumbs left by the program, I use this magnifying glass.

On Khan Academy, I am close to the Copernicus Badge, but the Atlas Black Hole badge moved again out of range from 250 to 500 challenges...

Some other news

Unrelated to the previous topic, a deltasql patch to branch from existing tags for 1.4.1 is published here.

And do not forget to check the Wikileaks Spy Files!

Let me finally point at a news on the Voyager probes measuring Lyman-alpha radiation (here). Amazing piece of irons, the Voyager space probes!

Win a trip in space!

I once saw a documentary about Burt Rutan's Spaceship One. I was impressed by the engineering skills of Rutan's team and by their audacity: how they tried different rockets for their spaceship (the first one blew up), the ingenious method developed for reentry in atmosphere... How during the flight to win the SpaceX price the main 3D instrument gave up and the pilot simply lead the spaceship in direction where it was more dark :-)

If you are lucky, there is now the possibility to win a suborbital flight with Space Adventures, a company which offers space trips based on the technology developed by Rutan.

If you are a database administrator living in UK, US, Canada or Germany, try Redgate contest DBA in space. You might win a trip to space! I am doing it although I am Swiss and can't win anything just for fun :-)

I noticed the contest, because Redgate is developing database control version tools similar to deltasql.

Monitor a tor node in Wikileaks style

One of the good sources feeding Wikileaks is the tor network. What happens is that lot of intelligence agencies pull sensitive stolen documents via tor, so that they can hide their tracks while stealing documents. Wikileaks volunteers might run tor exit nodes and monitor for unencrypted traffic going through it.

For example, in Gentoo (unfortunately, this time I did not write down all steps, so it is only a sketch):


emerge -av tcpdump # to monitor traffic
emerge -av openntpd # to synchronize the clock with ntpd
emerge -av tor # tor itself
torgencert # generates a certificate for your tor node
ntptime # to adjust your clock


Configure /etc/tor/torrc so that it is sound, plus add the following lines so that the tor node becomes an exit node.
The following lines make your tor node an useful node which will cause you little trouble as all exiting traffic is encrypted a part of irc.


ExitPolicy accept *:22 # ssh
ExitPolicy accept *:465 # smtps (SMTP over SSL)
ExitPolicy accept *:993 # imaps (IMAP over SSL)
ExitPolicy accept *:994 # ircs (IRC over SSL)
ExitPolicy accept *:995 # pop3s (POP3 over SSL)

ExitPolicy accept *:6660-6697 # allow irc ports, very widely
ExitPolicy reject *:* # no other exits allowed


The next two policies make your tor node useful to monitor it for stolen documents. It is best however, not to run it for too long time as you might get complaints, as unfortunately tor is not only used by charitative NGOs...

ExitPolicy accept *:22 # ssh
ExitPolicy accept *:465 # smtps (SMTP over SSL)


The final policy is

ExitPolicy reject *:* # no other exits allowed


Now try to tear up tor and listen for packets:

/etc/init.d/tor start
tcpdump -A | grep -i "WHATYOUAREINTERESTEDIN" > captured .txt


If tor does not start check /var/log/tor/tor.log for hints.

Besides this topic, I found an interesting article on how the Great Chinese Firewall works. But I think that DNS poisoning is only one of the many techniques used.

Cool hacker challenges

On hacker.org I was able to cut the head of the arithmetic snake. And I am proud on how I solved the "Cons Car" challenge with a Freepascal prototype always at the swapping limit of my old andromeda laptop. As side effect, I finally got insights into the LISP language. I am breaking my head on the late didactic crypto challenges and on "Anybody Out There": I tried to model it with two parameters of an oscillating circuit (L and C) and had a look at the hydrogen line, but it did not work out. (rank 210/solved 170)

Not much progress on Khan Academy (videos 187/2619 - solved 194/211)
23 Sep 2011 (updated 23 Sep 2011 at 08:49 UTC) »
"Force has no place where there is need of skill." - Herodotus

Kahn's wisdom

Khan Academy published new exercices and this revived my interest in the platform: I solved some more exercices and watched through several videos. While watching "How Earth's tilt causes Seasons" I realised a conceptual mistake in simclimate (released with GPU): I consider the angle for sunlight but not day duration of sunlight... I also watched the series on Milancovitch Precession and Obliquity, Orbit Excentricity wobbling and Perihelion precession. I had the Python introduction, courses about Human Evolution and Earth Formation, and I then decided to start a complete refresh of Linear Algebra, as the course attended at university was taken 13 years ago. And even at work, from time to time, linear algebra is lurking. (Current status: exercices: 176/188, videos: 187/2259)

Journey in Hackerland

The quests are getting definitively more difficult to solve. This month I could solve only eight challenges. Revision 54 of my Brainfuck interpreter written in Superhack language finally conquered the fortified castle. For "Spiral bits" my prototypes aren't good enough yet, so that one complete area of Hackerland remains off range. "Execution Style" and several didactic cipher challenges were solved. Also the Lawsonomy secret is unveiled. But speaking of didactic cipher challenges: brute force works only up to 4 billion keys, which can be tested in roughly a quarter hour of computations assuming printable ASCII characters. If the key space is bigger, this quote is definitely not valid: "If force does not work, you are not using enough force". For "Branches" I painfully worked out a solution, but the number I get is not accepted as solution, meaning that probably I cut off too much code or that I oversimplified the recursion. Who knows. For "Snake Arithmetic", I understood how the nominator is composed, but I still could not telescope the denominator part of the Python equation. For "Anybody Out There" I bought the book "Fourier Transform for pedestrians", but I am still waiting for it as it is out of print and the new edition should come this month. For this alien challenge, I also asked help to an old keen friend of mine who studied physics.

Through my journey, I discovered plenty of tools worth of mention: IntelliJ IDEA, Netbeans and ImageMagick. My favourite pseudorandom generator ISAAC has a companion in form of the RadioGatun hash function.
(Current status: rank 212, quests 165/277)


deltasql 1.4.1

deltasql 1.4.1 is a maintenance release. I discovered a stability problem in deltaclient (for which a dedicated patch of 1.4.0 was done), and tried to minimize the impact of undefined index errors when using strict error_reporting in php.ini. Some unused columns were dropped and the synchronization INSERT statement was simplified. This release really qualifies for the maintenance tag.

My next goal is to try to develop a plugin for the Squirrel SQL client, which is phantastic client which is able to connect to multiple database types (as it is based among other drivers on JDBC ones, a technology I am familiar with). Squirrel SQL is useful at work as well, as there I do not have administrator rights, and I am therefore prevented to install the full Oracle driver.

Linux Magazines

I am a fan of Linux Magazine. I read many articles there, including one presenting System Dynamics tools used in simulations and one about the Hercules Mainframe emulator. And all the cloud computing stuff is more than a hype. Virtualbox is definitely running on my computers. Plenty of images for Virtualbox are here.

Cables

I downloaded Wikileaks cables from Cryptome. For the moment, I decided to split them with split -b 4096k cables.csv cableparts and to search through them with fgrep -i tanzania cableparts* > tanzania.txt. Probably not the best approach, though.
deltasql with new Freepascal/Lazarus client

I am quite proud of the new deltasql release 1.4.0, as it features a client completely written in Freepascal/Lazarus. It contains some of the libraries written for the GPU II platform, and some more stuff I will use to write an applaunch plugin for GPU II. I will test this plugin together with the anagramas plugin, developed as technical fallback from code written for hacker.org.

Echolink on Android

I tested the Echolink app on the Android phone of virus (HTC Legend). I connected to node HB3YGE-L two kilometers from my house. When I spoke the QSO handshake sequence,
it came out of the Yaesu FT60 with a delay of approximately two seconds. It worked also the other way round, speaking into the Yaesu FT60 echoed on the Android phone. I then connected to a node in New Zealand and heard ham radios talking, unfortunately I could not understand their English.

There is something which I miss on the Echolink app: I'd like to have the node number information along with the node name, so that I can connect to the nodes with the Yaesu FT60 by using the Echolink DTMF commands. I list them here as a reminder, the text is from the previous link.


Info Request: By pressing "*" will ask the Node to play an ID message.
Connect: Enter the Node ID number of the station you want to connect to.
Random Node: By pressing "00" the system will connect you to any available Node.
Random Link: By pressing "01" the system will connect you to any available Link or Repeater.
Disconnect: Press "#" to disconnect.


Virtual Academies

Life is definitely worth living :-), in the sense that the same named challenge on Hacker.org finally got solved, after destroying our best equipment. "Countdown Calc", "Patience" and "Blackbox" were interesting as they spaced on the decompiling domain. "Number Theory" and "Primal Pi" brushed up my aging C++ knowledge. "Filtration Residue", "Blood, Toil, Tear and Sweat" and "Dejà vu" taught us a lot. "Right Key Left", "My Chemical Romance", "Hereditary" and "Yoga Message" were pure fun. New tools discovered are Boomerang Decompiler, Hercules Emulator, Scilab and the NTL library. The challenge on which I hope to learn most is "Anybody Out There", although my mathematical skills are quite poor when it comes to signal analysis.

Problem is now that there are two castles, one protected by "Superbrainfuck", the other protected by "Spiral Bits". We have prototypes to solve the two challenges, but they still do not work :-(. And no way to execute "Execution Style", nor "One Function". Is this the end of our journey on hackerland?

For the record, our current ranking on Hacker.org is 239 with 157 challenges solved. Also Khan Academy published some more exercises (137/149)... Virtual Academies are the best escape path for Alice in Dilbertland!
The hacker explores the intersection of art and science in an insatiable quest to understand and shape the world around him.
We guide you on this journey.
From www.hacker.org

Yesterday evening we achieved the 128 Challenges solved mark :-) Best challenges in this journey from the last Blog entry were 'Maeda Path', 'Tic Tac Blah', 'Secure Room', 'Broken keys', 'Immortal' and 'Train Wreck'.

The challenge which keeps resisting us is 'A life worth living'. The spartacusii server burnt while computing the Game of Life for this challenge. Or maybe it died due too a lightning tempest which occurred two days ago. Or it did too much BOINC computations. Also the router is playing strange: I get a red light on the Internet... It was a second hand computer anyway. Basically, to solve more quests, we are risking the best of our gears. Now, I will need to reenable the pico server which I did not operate to spare current (and money). I also have another old server ready for operations.

We are now ranked 516 on the hacker.org site and almost in the top 500. This evening, me and virus will go out for dinner to party this incredible achievement in our life :-)

56 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!