ShaFuck is not unbeatable

When I found ShaFuck, I really loved this idea and I thought it's indeed impossible to write code in this language.

However, I found a way to write code in ShaFuck and I could write a script which translates Brainfuck code into ShaFuck code.

http://shinh.skr.jp/obf/bf2sf.rb

Here is a few evidence:

• http://shinh.skr.jp/obf/hello.sf
• http://shinh.skr.jp/obf/cal.sf.gz

> ./shafuck hello.sf
Hello, world!
> ./shafuck cal.sf
2012 03
                   1
 2  3  4  5  6  7  8
 9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 

The idea was very simple. We cannot find a 1024 byte characters which will be translated into a fully meaningful 20 BF commands (1/32^20 if SHA1 is random), but we can find a code chunk which will become 3 bytes of BF sequence and 17 bytes of junks. As the existence of BF comments (i.e., any characters which aren't the eight BF commands) are allowed as long as they aren't executed, we need to skip the junks. Luckily, I could find a translation:

+ => +>[ (17B)  (18B) ]<
- => ->[ (17B)  (18B) ]<
> => >[  (18B)  (18B) ]>
< => <[  (18B)  (18B) ]<
. => .>[ (17B)  (18B) ]<
, => ,>[ (17B)  (18B) ]<
[ => >[  (18B)  (17B) ]<[
] => >[  (18B)  (17B) ]<]

With my translation, all BF commands will be translated into 2 ShaFuck code junks (i.e., 2048 bytes of code). The trick was that we will never modify the contents of odd address and they always have zero. We can use them to skip junks. Note that > and < moves the pointers twice.

I found code chunks which will be translated into the above sequences by

http://shinh.skr.jp/obf/sf_find_ops.cc

I used sha1.c and sha1.h in shafuck's reference implementation. It took about 3 minutes to find code chunks we need.

I used shafuck-0.2 for this entry. The feature versions may not have this vulnerability. I think the simplest "fix" for this issue is validating code after calculating SHA1 and before running code.