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