Dirt cheap steganography

This steg module is based on code, ideas and images from http://blog.wolfram.com/2010/07/08/doing-spy-stuff-with-mathematica/ .
It requires numpy & matplotlib but can be reworked to depend on pypng instead of matplotlib

Sample usage

$ python2.7 simple_decode.py --help

Usage:

Hide/Unhide info in images as described in this post:

http://blog.wolfram.com/2010/07/08/doing-spy-stuff-with-mathematica/

usage: simple_decode.py [options]

Options:

-h, --help show this help message and exit

-v DEBUG, --verbose=DEBUG

Debug. Higher integers increases verbosity

-e ENCODED_FILE, --encoded_file=ENCODED_FILE

Encoded PNG file to work with. Default is

steg_chicken_secret.png

-d DATA_FILE, --data_file=DATA_FILE

File with decoded data or with data to encode.

Example decode of data hidden in the wolfram blog images

$ python2.7 simple_decode.py -e steg_chicken_secret.png -d chicken.txt
$ cat chicken.txt ;echo

This is a secret message.



$ python2.7 simple_decode.py -e alice.png -d alice.txt

$ file alice.txt

alice.txt: UTF-8 Unicode English text, with very long lines, with no line terminators



$ python2.7 simple_decode.py -e finalImage.png -d data.jpg

$ file data.jpg

data.jpg: JPEG image data, JFIF standard 1.01, comment: "Created by Wolfram Mathematica "

recursion && tail recursion

A look at the difference between plain old recursion and tail recursion.

• Compile recursion.c
• Fire up GDB

$ gdb recursion
GNU gdb (GDB) 7.2-debian
.....
(gdb)

• Set up breakpoints at recursion termination points

(gdb)  break recursion.c:50
Breakpoint 1 at 0x4005b9: file /home/lmwangi/learning/algo/recursions/recursion.c, line 50.
(gdb)  break recursion.c:68
Breakpoint 2 at 0x400601: file /home/lmwangi/learning/algo/recursions/recursion.c, line 68.

• Run till the first breakpoint - Good old recursion. Notice that we have to step 4 times.

(gdb) run
Starting program: /home/lmwangi/learning/algo/recursions/recursion

Breakpoint 1, factorial (n=1) at /home/lmwangi/learning/algo/recursions/recursion.c:50
50                      return 1;
(gdb) bt
#0  factorial (n=1) at /home/lmwangi/learning/algo/recursions/recursion.c:50
#1  0x00000000004005cd in factorial (n=2) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#2  0x00000000004005cd in factorial (n=3) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#3  0x00000000004005cd in factorial (n=4) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#4  0x00000000004005cd in factorial (n=5) at /home/lmwangi/learning/algo/recursions/recursion.c:53
#5  0x0000000000400544 in main () at /home/lmwangi/learning/algo/recursions/recursion.c:30
(gdb) step
56      }
(gdb) step
56      }
(gdb) step
56      }
(gdb) step
56      }
(gdb) step
56      }
(gdb) step
main () at /home/lmwangi/learning/algo/recursions/recursion.c:32
32              printf("Factorial %d\n", result);

• Tail recursion. Notice that we step only once since the function has all the results from prior operations

(gdb) cont
Continuing.
Factorial 120

Breakpoint 2, tail_factorial (n=1, a=120) at /home/lmwangi/learning/algo/recursions/recursion.c:68
68                      return a;
(gdb) bt
#0  tail_factorial (n=1, a=120) at /home/lmwangi/learning/algo/recursions/recursion.c:68
#1  0x000000000040061c in tail_factorial (n=2, a=60) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#2  0x000000000040061c in tail_factorial (n=3, a=20) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#3  0x000000000040061c in tail_factorial (n=4, a=5) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#4  0x000000000040061c in tail_factorial (n=5, a=1) at /home/lmwangi/learning/algo/recursions/recursion.c:71
#5  0x000000000040056d in main () at /home/lmwangi/learning/algo/recursions/recursion.c:34
(gdb) step
73      }
(gdb) step
main () at /home/lmwangi/learning/algo/recursions/recursion.c:36
36              printf("Tail Factorial %d\n", result);
(gdb) 

Unix Permission modes

This is a long post covering unix permission modes. A file's mode is stored in it's inode structure. Most of this post is inline in the following shell interaction snippet(plain text here). The quirky bits are:

1. Permissions are analysed in increasing generality i.e User, Group, Others. The first match is accepted whether positive or negative
2. Executing a setuid binary is equivalent to executing that binary as the user owning the binary
3. Executing a setgid binary is equivalent to executing the binary as the group owning that binary
4. Binaries require setting the x bit only while shell scripts require r & x bits to be set.
5. If you setgid a directory and create a file in that directory, the file's group will be set to the group of the directory (Group permissions become inherited regardless of whether you were in that group).
6. Sticky bits on a directory restrict deletion to the owner of the directory, the creator of a file and the superuser. That's how /tmp works! It's also known as the restricted deletion flag.

# Lets make a couple of tests
$ test_read () { $(cat  2>/dev/null test.file > /dev/null ); if [ $? -eq 0 ];then echo "Read : True "; else echo "Read : False"; fi; }
$ test_write () { $(echo 2>/dev/null -e '#!/bin/sh\necho hello' > test.file ); if [ $? -eq 0 ];then echo "Write: True "; else echo "Write: False"; fi; }
$ test_exec () { $( ./test.file 2>/dev/null 1>/dev/null); if [ $? -eq 0 ];then echo "Exec : True "; else echo "Exec : False"; fi; }

# Touch a test.file
$ ls -l test.file
-rwx------ 1 lmwangi lmwangi 21 Apr 14 16:31 test.file

# Test mode as user 
$ for mode in $(seq -w 0 100 700); do echo "Mode $mode"; touch test.file; chmod $mode test.file; test_read; test_write; test_exec;echo;  done
Mode 000
Read : False
Write: False
Exec : False

Mode 100
Read : False
Write: False
Exec : False

Mode 200
Read : False
Write: True 
Exec : False

Mode 300
Read : False
Write: True 
Exec : False

Mode 400
Read : True 
Write: False
Exec : False

Mode 500
Read : True 
Write: False
Exec : True 

Mode 600
Read : True 
Write: True 
Exec : False

Mode 700
Read : True 
Write: True 
Exec : True 


# File permissions like firewall acls stop at the first match. If I am the owner of the file, matching stops with the user bits. Groups/others are never consulted... So we chgrp of file to a group you are not in say root and test.
$ sudo chgrp root test.file 
$ ls -l
total 4
----rwx--- 1 lmwangi root 21 Apr 14 16:36 test.file

$ for mode in $(seq -w 0 010 070); do echo "Mode $mode"; touch test.file; chmod $mode test.file; test_read; test_write; test_exec;echo;  done
Mode 000
Read : False
Write: False
Exec : False

Mode 010
Read : False
Write: False
Exec : False

Mode 020
Read : False
Write: False
Exec : False

Mode 030
Read : False
Write: False
Exec : False

Mode 040
Read : False
Write: False
Exec : False

Mode 050
Read : False
Write: False
Exec : False

Mode 060
Read : False
Write: False
Exec : False

Mode 070
Read : False
Write: False
Exec : False

# It get's interesting if I am not the owner of the file but I am in a group that owns the file.
$ id
uid=1000(lmwangi) gid=1000(lmwangi) groups=1000(lmwangi),20(dialout),24(cdrom),25(floppy),29(audio),44(video),46(plugdev),112(netdev),114(fuse),119(libvirt),1003(packetcapture)
$ ls -l
total 4
----rwx--- 1 root lmwangi 21 Apr 14 16:42 test.file

for mode in $(seq -w 0 010 070); do echo "Mode $mode"; sudo chmod $mode test.file; test_read; test_write; test_exec;echo;  done
Mode 000
Read : False
Write: False
Exec : False

Mode 010
Read : False
Write: False
Exec : False

Mode 020
Read : False
Write: True 
Exec : False

Mode 030
Read : False
Write: True 
Exec : False

Mode 040
Read : True 
Write: False
Exec : False

Mode 050
Read : True 
Write: False
Exec : True 

Mode 060
Read : True 
Write: True 
Exec : False

Mode 070
Read : True 
Write: True 
Exec : True 

# The same principle applies. Others mode only applies if I am neither the file owner nor in a group that owns the file.
$ for mode in $(seq -w 0 001 007); do echo "Mode $mode"; sudo chmod $mode test.file; test_read; test_write; test_exec;echo;  done
Mode 000
Read : False
Write: False
Exec : False

Mode 001
Read : False
Write: False
Exec : False

Mode 002
Read : False
Write: True 
Exec : False

Mode 003
Read : False
Write: True 
Exec : False

Mode 004
Read : True 
Write: False
Exec : False

Mode 005
Read : True 
Write: False
Exec : True 

Mode 006
Read : True 
Write: True 
Exec : False

Mode 007
Read : True 
Write: True 
Exec : True 

# It gets better with executables :)
# Let's make a small template executable
$  echo -e '#include <stdio.h>\nint main(){printf("hello\\n"); return 0;}' > hello.c && gcc hello.c -o hello
$ ./hello 
hello
# Now watch mode 100 compare with the a shell script of mode 100. Do the same for 300, 500 & 700
Mode 000
Read : False
Write: False
Exec : False

Mode 100
Read : False
Write: False
Exec : True 
Mode 200
Read : False
Write: True 
Exec : False

Mode 300
Read : False
Write: True 
Exec : True 

Mode 400
Read : True 
Write: False
Exec : False

Mode 500
Read : True 
Write: False
Exec : True 

Mode 600
Read : True 
Write: True 
Exec : False

Mode 700
Read : True 
Write: True 
Exec : True 

# As can be seen. You must have r & x to exec a shell script while your require only x for a binary.
# Recap again
$ for mode in $(seq -w 0 100 700); do echo $mode; chmod $mode test.file; ls -l test.file |grep test.file; ./test.file; done
000
---------- 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
-bash: ./test.file: Permission denied
100
---x------ 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
hello
200
--w------- 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
-bash: ./test.file: Permission denied
300
--wx------ 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
hello
400
-r-------- 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
-bash: ./test.file: Permission denied
500
-r-x------ 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
hello
600
-rw------- 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
-bash: ./test.file: Permission denied
700
-rwx------ 1 lmwangi lmwangi 6695 Apr 14 17:06 test.file
hello


# Now let's look at the  setuid/setgid/sticky bits. 
1 = Sticky - if set not relevant in a binary in my system [Linux]
2 = SetGID - if set the progran runs with eGID set to the binary group
4 = SetUID - if set the program runs with euid set tot the binary owner.

# Let's make a program that shows us the uid, effective uid, gid and effective gid
$ echo -e '#include <stdio.h>\n#include <unistd.h>\nint main(){printf("hello\\nUID:%d\\nEUID:%d\\nGID:%d\\nEGID:%d\\n",getuid(),geteuid(),getgid(),getegid()); return 0;}' > hello.c && gcc hello.c -o hello                                                      

$ ./hello 
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

$ id
uid=1000(lmwangi) gid=1000(lmwangi) groups=1000(lmwangi),20(dialout),24(cdrom),25(floppy),29(audio),44(video),46(plugdev),112(netdev),114(fuse),119(libvirt),1003(packetcapture)

$ for owner in lmwangi:lmwangi lmwangi:root root:lmwangi root:root; do echo ">>>> $owner <<<<"; for mode in 1777 2777 4777 6777; do echo "mode $mode"; cp hello test.file ; sudo chown $owner test.file; sudo chmod $mode test.file; ls -l test.file; ./test.file;echo; done;  done
>>>> lmwangi:lmwangi <<<<
mode 1777
-rwxrwxrwt 1 lmwangi lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 2777
-rwxrwsrwx 1 lmwangi lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 4777
-rwsrwxrwx 1 lmwangi lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 6777
-rwsrwsrwx 1 lmwangi lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

>>>> lmwangi:root <<<<
mode 1777
-rwxrwxrwt 1 lmwangi root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 2777
-rwxrwsrwx 1 lmwangi root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:0

mode 4777
-rwsrwxrwx 1 lmwangi root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 6777
-rwsrwsrwx 1 lmwangi root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:0

>>>> root:lmwangi <<<<
mode 1777
-rwxrwxrwt 1 root lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 2777
-rwxrwsrwx 1 root lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 4777
-rwsrwxrwx 1 root lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:0
GID:1000
EGID:1000

mode 6777
-rwsrwsrwx 1 root lmwangi 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:0
GID:1000
EGID:1000

>>>> root:root <<<<
mode 1777
-rwxrwxrwt 1 root root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:1000

mode 2777
-rwxrwsrwx 1 root root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:1000
GID:1000
EGID:0

mode 4777
-rwsrwxrwx 1 root root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:0
GID:1000
EGID:1000

mode 6777
-rwsrwsrwx 1 root root 7205 Apr 14 17:31 test.file
hello
UID:1000
EUID:0
GID:1000
EGID:0

# Sticky bit (RESTRICTED DELETION FLAG) on directories 

$ mkdir test; sudo chown root:root test; sudo chmod 1777 test; ls -l |grep test
drwxrwxrwt 2 root    root    4096 Apr 14 17:39 test
-rwsrwsrwx 1 root    root    7205 Apr 14 17:31 test.file

$ echo lmwangi > test/by_lmwangi
$ ls -l test/
total 4
-rw-r--r-- 1 lmwangi lmwangi 8 Apr 14 17:41 by_lmwangi

# No one can remove the file
$ sudo su guest -c "rm test/by_lmwangi"
rm: remove write-protected regular file `test/by_lmwangi'? y
rm: cannot remove `test/by_lmwangi': Operation not permitted

# Root can  override though or the owner of the dir
$ sudo rm test/by_lmwangi 

$ rm -rf test
$ mkdir test
$ chmod 1777 test
$ sudo su guest -c "echo hello > test/by_guest"
$ ls -l test
total 4
-rw-r--r-- 1 guest guest 6 Apr 14 17:38 by_guest
$ ls -l |grep test
drwxrwxrwt 2 lmwangi lmwangi 4096 Apr 14 17:38 test
-rwsrwsrwx 1 root    root    7205 Apr 14 17:31 test.file
$ cat test/by_guest 
hello
$ rm test/by_guest 
rm: remove write-protected regular file `test/by_guest'? y

$ ls -l test
total 0

# And we go out with a bang
# setuid on dir == no change on files                                                                  
$ rm -rf test && mkdir test; sudo chown root:root test; sudo chmod 4777 test; ls -l|grep test
$ cd test/
$ touch aha
$ ls -l
total 0
-rw-r--r-- 1 lmwangi lmwangi 0 Apr 14 17:46 aha
$ cd ..

# But setgid on dir == changes any file created in it to the group owning the dir
$ rm -rf test && mkdir test; sudo chown root:root test; sudo chmod 2777 test; ls -l|grep test
drwxrwsrwx 2 root    root    4096 Apr 14 17:47 test
-rwsrwsrwx 1 root    root    7205 Apr 14 17:31 test.file
$ cd test/
$ touch aha
$ ls -l
total 0
-rw-r--r-- 1 lmwangi root 0 Apr 14 17:47 aha
$ id
uid=1000(lmwangi) gid=1000(lmwangi) groups=1000(lmwangi),20(dialout),24(cdrom),25(floppy),29(audio),44(video),46(plugdev),112(netdev),114(fuse),119(libvirt),1003(packetcapture)

Unix is loads of fun :)

Mergesort performance

Updated Sorting performance graph. My Quicksort implementation has weird variations. I'll have to look at the algorithm to figure out what's going on. Mergesort and Quicksort are practically equivalent for these set sizes.

Sorting in awk

I became interested in playing around with simple sorting algorithms and learning awk at the same time. Here is a quick roundup of the first three.

$ bash make_stats.sh
Doing 10 rounds of bubble_sort.awk with a dataset of 100 ints
Average real time in seconds: 0.0151

Doing 10 rounds of quick_sort.awk with a dataset of 100 ints
Average real time in seconds: 0.0476

Doing 10 rounds of selection_sort.awk with a dataset of 100 ints
Average real time in seconds: 0.0048

Doing 10 rounds of bubble_sort.awk with a dataset of 500 ints
Average real time in seconds: 0.3663

Doing 10 rounds of quick_sort.awk with a dataset of 500 ints
Average real time in seconds: 0.2443

Doing 10 rounds of selection_sort.awk with a dataset of 500 ints
Average real time in seconds: 0.0795

Doing 10 rounds of bubble_sort.awk with a dataset of 2500 ints
Average real time in seconds: 9.7188

Doing 10 rounds of quick_sort.awk with a dataset of 2500 ints
Average real time in seconds: 0.335

Doing 10 rounds of selection_sort.awk with a dataset of 2500 ints
Average real time in seconds: 2.1556

Divide and conquer rules the roost especially with large datasets.

Selection sort is obviously much faster than bubblesort.

Probable reasons:

1. Selection sort works on progressively smaller arrays with each iteration
2. Comparisons in bubble sort are expensive compared to moving an element to the end of the array
3. My implementation of bubble sort sucks.. (I'll check it again :( )

The make_stats script is in the same repository. It would be nice to update it to graph these stats using gnuplot


Update: Graphing can now be done by graph_performance.sh. It generates a couple of stats files and the graph in tmp. It expects to find gnuplot in your path. Sort size can be changed by editing make_stats.sh directly.

Poweroff or poweron usb devices in Linux

Sometimes, I need my external drive to suspend/spin down when I am suspending my machine.

Use lsusb to replace the vendor/product ids.

In my case

$ lsusb

...

Bus 001 Device 008: ID 1058:0704 Western Digital Technologies, Inc. Passport External HDD

...

~/bin/poweroff-usbdisk.sh

#!/bin/sh
# Poweroff a device identified by the vendor/product id below.
# If you have two similar devices (e.g two western digital drives),
# the script will fail. The fix is easy: enumerate the devices
# and suspend them individually. 

vendorid=1058
productid=0704

# Look for western digital
USBDIR=$(dirname $(find  /sys/bus/usb/devices/usb[1-5]/ -iname "*vendor*"|xargs grep $vendorid|cut -f1 -d: ))

# Verify it's the hdd
grep $productid $USBDIR/idProduct

#Power off 
if [ $? -eq 0 ]; then
sudo umount /mnt/audio/ && echo suspend |sudo tee $USBDIR/power/level;
fi
~/bin/poweron-usbdisk.sh

#!/bin/sh

# Poweron a device identified by the vendor/product id below.

# Look for western digital
USBDIR=$(dirname $(find  /sys/bus/usb/devices/usb[1-5]/ -iname "*vendor*"|xargs grep $vendorid |cut -f1 -d: ))
vendorid=1058
productid=0704


# Verify it's the hdd
grep $productid $USBDIR/idProduct

#Power off 
if [ $? -eq 0 ]; then  echo on |sudo tee $USBDIR/power/level; fi