Older blog entries for dangermaus (starting at number 61)

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 :-)
of mice and men

we just solved the Cavern challenge on the hacker academy. our bash warrior fought and died several times deep down into the dungeon, but a final modification into his mind brought him in about 16 hours down to the diabolic beast at the bottom. our warrior slaught the beast in two moves :-) we did not think someone could create such a deep dungeon!
dungeon's challenges are our entry to the more complicated challenges that require games to be solved by automation.

digging deeper

our "challenges solved" counter scores 102, but now the next challenges require us to invest much more time. we solved the first 90 challenges in two weeks, and then it took one week to solve another ten. this week we solved only one or two... also, we need to dig deeper into our toolbox. in particular, we start performing statistical analysis on ciphertexts (like done on one of my previous jobs)... i also printed out the Python code of the HackVM to learn its inners. and we need to decompose cellular automata into its components to know the number of cells at the 10th billion generation...

a life worth living

the Conway's game of life challenges are interesting, too. and make me feel younger, as my first Life implementation in BASIC for C64 was around 1989, after reading some old articles in Scientific American. i still remember the flash experience i had; my life simulation was not behaving as expected: only when i introduced a copy of the lifeboard for the previous generation, things started working out :-). with my father, we did another implementation in Turbo Pascal for Windows 3.1 back in 1992. the third implementation i did was just some days ago in Freepascal to solve the 'life skills' challenge. but in all my implementations were on bounded universes.

with please, i then noticed the Golly project, a simulator for Cellular Automata including Life. Golly has an unbounded universe, still it is very fast when the lifeboard size is small and can adapt lifeboard size if cells grow out of the box. and it is amazing feeling, as there are plenty of patterns in Golly and even a complete Turing machine working on the Life universe. it is amazing because i remember reading in Scientific American about it and how it theoretically should be possible to construct it in Life, as some NAND patterns were already working when simulated on a big supercomputer. 20 years later, i can run a complete Turing machine on the Life universe on my old laptop :-D.

in Scientific American, i read also about Life in 3 dimensions, and i wonder if there were progress on this as well. but probably not, as we 3D beings we think best in 2D. or at least me...

thinking different

all this time spent on the hacker academy is producing some chemical changes in my mind: i start looking at the detail, giving importance to an end of line or looking at ranges were a function is presumed to work. errors get more important than all the rest! and evidence just becomes obvious background noise... too much evidence can become even a misleading trail.
numbers previously thought big get small like a quarter hour or like four billion keys XORed on a ciphertext. numbers never considered before (because greater than the universe's atom count) are solution to challenges...
writing use-once code and combining tools and operating systems... burning CPU time, network bandwidth and hard disks... in short, hacker.org is wonderful!
fall to the dark side

as Khan stopped feeding me with exercises, I fell into the dark side of the power, and my wife virus too. to date, we solved together 92 quests. Some highlights until now were: we disassembled Java to retrieve passphrases, compiled ADA, uncompressed strange files and brought the JVM to throw exceptions were nobody could think of it. we wrote crawlers to get answer to the One Minute Man oracle (two lines in bash cronjobbed) and wrote a Conway's game of life in Freepascal to compute the maximum number of cells for a particular cell pattern. we heard pictures and morse code, each time extracting the signal out of an amazing amount of noise. we digged into Pi until we found the patterns we wanted. virus solved, among others, the CipherQuest D exercise, which is a substitute cipher with errors and at least 15 meaningless characters. exercices vary in difficulty: we found messages in newspapers as the Simpsons did and we took the natural logarithm of the 150 000 000 000 Fibonacci number... but still, we face another 178 challenges
and we do not know if we are up to it... we feel like a newbie climber in front of the Everest...

deltasql 1.3.7

at least, the fall to the dark side produced something powerful in form of a new release of deltasql: it features salted MD5 hashed passwords with a password reset mechanism. Sure enough for most people around... but not for them.

I learned bookkeeping on Khan Academy with the two types of accounting: accrual basis and cash accounting. Assets, liabilities and equity words entered my head, currently busy with some Khan brain teasers.

And I managed to solve all currently published exercises on Khan Academy (129/129) :-) Kudos to my TI-89 which helped me out so many times! However, the unknown and legendary Black Hole badges aren't yet in my journeyer backpack... And to earn them, it is currently impossible because... the answer is ... hidden in Kahn's source code. Check badges/point_badges.py and exercise_completion_count_badges.py to unveil the secret...

Fabian Bellard's scientific web calculator is very powerful! I discovered it today while reading an advogato entry on him!

My academic career was a failure, but fortunately my khanacademic career is skyroketing :-). These days, I watched videos on Thermodynamics (in Chemistry section). I had a deep look at the Carnot Cycle, at adjabatic and isothermic processes and at the entropy definition, and the Maxwell's demon was lurking all the time.

I watched videos in history from French revolution, through Napoleon's rise and until his fall, and I felt sympathetic with people in the Haitian revolution and was scared by the dishonest debt they had to pay until 1947! In my previous history courses I had a more theoretical approach to the French revolution: we discussed in deep all Illuministic theories, but I completeley missed the stuff going on in Europe in 1789-1815. In the end, the Swiss constitution was enforced by Napoleon... I wonder how I could visit London and Paris without knowing what I do now... I practiced with exercises on the Academy site, too. To date, I watched 124 videos and solved 104 exercices. My goal is to earn at least one of the two unknown Black Hole badges!

Dangertube

As my one and one half year old daughter is learning by imitation, I decided to do the same! I equipped myself with an Aiptek 10000U (for about 130 Swiss francs) and bought Screenvideorecorder for another 40 bucks. I then created a tutorial video on how to compute the gamma factor of special relativity. English, audio and overall handling are experimental! (what else would you expect from dangermouse? ;-)

I also created 7 videos on how deltasql works and put an old introduction to the GPU project on Youtube.

Joomla

I am very happy on how Joomla manages the site of our local boy scout group. People keep sending me articles and in a matter of minutes I get them online.

Excel SUMIFS function

It adds the cells in a range (range: Two or more cells on a sheet. The cells in a range can be adjacent or nonadjacent.) that meet multiple criteria. For example, if you want to sum the numbers in the range A1:A20 only if the corresponding numbers in B1:B20 are greater than zero (0) and the corresponding numbers in C1:C20 are less than 10, you can use the following formula:


=SUMIFS(A1:A20, B1:B20, ">0", C1:C20, "<10")

I recently saw SUMIFS used as an extended VLOOKUP with more than one cell which needed to match.

52 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!