Labels

Recent Posts

Wednesday, September 10, 2014

Real Programmers Use One-Way Hash Function


GNU nano is a text editor - a program often used to edit the source code of other programs. Emacs, Vim and ed are all progressively more "hard core" editors. cat is a Unix program that concatenates and outputs the contents of files. Things get steadily more ridiculous from here. Using a magnetised needle to flip bits on a hard drive requires nanometer precision and binary mastery, but in the early days of programming people did use needles sometimes to fix bugs on Punched cards. The use of a magnetized needle may also be a reference to the Apollo AGC guidance computer, whose instructions were physically written as patterns of wires looped around or through cylindrical magnets in order to record binary code.  -- http://www.explainxkcd.com/wiki/index.php/378:_Real_Programmers
For a real programmer, writing binary executable directly seems to be a bit too easy, even with magnetized needles. The real hard core way is using one-way hash functions, like sha2 or md5.

In the spirit of Great Python Challenge, which were used to promote PyCon APAC 2014, I posted a challenge on my Facebook, aksing if anyone can use one-way hash function to write program, for example:
cat 0.c| shasum -a 384 | xxd -p -r > a.out && chmod a+x a.out && ./a.out
sha384 was chosen because it is possible to fit an ELF binary into sha384 digest (see http://www.muppetlabs.com/~breadbox/software/tiny/teensy.html).

After I posted the challenge, I was trying to find a solution myself too. It turns out that it is possible to do so.
Follow below steps (Copy& Paste) to try the code:
mkdir test
cd test
wget https://raw.githubusercontent.com/tjwei/tjw_ipynb/master/0.c
sh 0.c
gcc 0.c && ./a.out
cat 0.c | shasum -a 384 | xxd -p -r > a.out && chmod a+x a.out
./a.out


The story

The first solution is https://github.com/tjwei/tjw_ipynb/blob/master/a.c
Sort of working, but I am not satisfied because I'd expect it can at least say "Hello World!".
My 2nd attpemt is https://raw.githubusercontent.com/tjwei/tjw_ipynb/aa733143a5a76f460122e93028f49693d53931e8/0.c
which is not bad, it does say "Hello World!", but still has some issues I don't like.
I realized that I have to search the solution harder. First thing I did was to reduce the length of the code to fit in 112 bytes, so that the whole code can be fit in one sha512 block. This can speed up the hashing by a factor of 5~7. In order to do that, all description, which was in the comment of the code,  were moved to a webpage and the url is shortened.
Then, I use OpenCL and a customized kernel to do the sha384 hashing. On my HD7970 ghz edition, it can do 160 mhash/s, without overclocking the card.
You can find the final result: https://github.com/tjwei/tjw_ipynb/blob/master/0.c
And working notebook at:
http://nbviewer.ipython.org/github/tjwei/tjw_ipynb/blob/master/RealMan2.ipynb

And

Since it is a challenge, I do receive some replies. An answer from Kuo-Tung is quite good too, see  http://paste.plurk.com/show/1982392/

No comments:

Post a Comment