The Shikata Ga Nai Encoder

Shikata Ga Nai is the first encoder we’ll demystify in the Shellcode Signature series, where Booz Allen threat analysts explore technical issues and insights for security practitioners to reference as they protect their organizations against cyber threats. Shikata Ga Nai is one of the few encoders in the Metasploit Framework with an ‘excellent’ ranking on GitHub, and is often referenced in cybersecurity books and tutorials.[1] Before its payload can be successfully encoded, Shikata Ga Nai runs through a handful of steps, as described below.

Shikata Ga Nai’s Order of Operations

Step 1: Floating-Point Unit Instructions

Shikata Ga Nai’s floating-point unit (FPU) block contains a set of FPU instructions (Ruby Array) that, along with the FNSTENV step, allows the encoder to determine from where in memory it is executing. This GetEIP/GetPC step is a critical part of all shellcode. 

The encoder needs to know where its encoded payload starts. It can’t use absolute addresses because the shellcode will typically have no control over where it gets placed in memory. Instead, if the encoder can figure out where the shellcode is currently executing, it can address everything relative to that location. There are multiple ways of accomplishing this, but Shikata Ga Nai is hardcoded to use the FPU/FNSTENV method described below.

The following is the source that generates the FPU instructions:

 def fpu_instructions
    fpus = []

    0xe8.upto(0xee) { |x| fpus << "\xd9" + x.chr }
    0xc0.upto(0xcf) { |x| fpus << "\xd9" + x.chr }
    0xc0.upto(0xdf) { |x| fpus << "\xda" + x.chr }
    0xc0.upto(0xdf) { |x| fpus << "\xdb" + x.chr }
    0xc0.upto(0xc7) { |x| fpus << "\xdd" + x.chr }

    fpus << "\xd9\xd0"
    fpus << "\xd9\xe1"
    fpus << "\xd9\xf6"
    fpus << "\xd9\xf7"
    fpus << "\xd9\xe5"

    # This FPU instruction seems to fail consistently on Linux
    #fpus << "\xdb\xe1"

    fpus

  end

The result is an array of 100 potential instructions:

["\xD9\xE8", "\xD9\xE9", "\xD9\xEA", "\xD9\xEB", "\xD9\xEC", "\xD9\xED", "\xD9\xEE", "\xD9\xC0", "\xD9\xC1", "\xD9\xC2", "\xD9\xC3", "\xD9\xC4", "\xD9\xC5", "\xD9\xC6", "\xD9\xC7", "\xD9\xC8", "\xD9\xC9", "\xD9\xCA", "\xD9\xCB", "\xD9\xCC", "\xD9\xCD", "\xD9\xCE", "\xD9\xCF", "\xDA\xC0", "\xDA\xC1", "\xDA\xC2", "\xDA\xC3", "\xDA\xC4", "\xDA\xC5", "\xDA\xC6", "\xDA\xC7", "\xDA\xC8", "\xDA\xC9", "\xDA\xCA", "\xDA\xCB", "\xDA\xCC", "\xDA\xCD", "\xDA\xCE", "\xDA\xCF", "\xDA\xD0", "\xDA\xD1", "\xDA\xD2", "\xDA\xD3", "\xDA\xD4", "\xDA\xD5", "\xDA\xD6", "\xDA\xD7", "\xDA\xD8", "\xDA\xD9", "\xDA\xDA", "\xDA\xDB", "\xDA\xDC", "\xDA\xDD", "\xDA\xDE", "\xDA\xDF", "\xDB\xC0", "\xDB\xC1", "\xDB\xC2", "\xDB\xC3", "\xDB\xC4", "\xDB\xC5", "\xDB\xC6", "\xDB\xC7", "\xDB\xC8", "\xDB\xC9", "\xDB\xCA", "\xDB\xCB", "\xDB\xCC", "\xDB\xCD", "\xDB\xCE", "\xDB\xCF", "\xDB\xD0", "\xDB\xD1", "\xDB\xD2", "\xDB\xD3", "\xDB\xD4", "\xDB\xD5", "\xDB\xD6", "\xDB\xD7", "\xDB\xD8", "\xDB\xD9", "\xDB\xDA", "\xDB\xDB", "\xDB\xDC", "\xDB\xDD", "\xDB\xDE", "\xDB\xDF", "\xDD\xC0", "\xDD\xC1", "\xDD\xC2", "\xDD\xC3", "\xDD\xC4", "\xDD\xC5", "\xDD\xC6", "\xDD\xC7", "\xD9\xD0", "\xD9\xE1", "\xD9\xF6", "\xD9\xF7", "\xD9\xE5"]

A quick script using Python and Radare2 can disassemble the bytes returned from the fpu_instructions block. Script below:

#!/usr/bin/python3

import r2pipe

instructions = ["D9E8", "D9E9", "D9EA", "D9EB", "D9EC", "D9ED", "D9EE", "D9C0", "D9C1", "D9C2", "D9C3", "D9C4", "D9C5", "D9C6", "D9C7", "D9C8", "D9C9", "D9CA", "D9CB", "D9CC", "D9CD", "D9CE", "D9CF", "DAC0", "DAC1", "DAC2", "DAC3", "DAC4", "DAC5", "DAC6", "DAC7", "DAC8", "DAC9", "DACA", "DACB", "DACC", "DACD", "DACE", "DACF", "DAD0", "DAD1", "DAD2", "DAD3", "DAD4", "DAD5", "DAD6", "DAD7", "DAD8", "DAD9", "DADA", "DADB", "DADC", "DADD", "DADE", "DADF", "DBC0", "DBC1", "DBC2", "DBC3", "DBC4", "DBC5", "DBC6", "DBC7", "DBC8", "DBC9", "DBCA", "DBCB", "DBCC", "DBCD", "DBCE", "DBCF", "DBD0", "DBD1", "DBD2", "DBD3", "DBD4", "DBD5", "DBD6", "DBD7", "DBD8", "DBD9", "DBDA", "DBDB", "DBDC", "DBDD", "DBDE", "DBDF", "DDC0", "DDC1", "DDC2", "DDC3", "DDC4", "DDC5", "DDC6", "DDC7", "D9D0", "D9E1", "D9F6", "D9F7", "D9E5"]

r2 = r2pipe.open('malloc://1024')

r2.cmd('e asm.bits = 32')

ret = []

for code in instructions:

    ret.append(r2.cmd('pad %s'% code.strip('')))

print(ret)

The process described above results in the following set of FPU instructions:

['fld1', 'fldl2t', 'fldl2e', 'fldpi', 'fldlg2', 'fldln2', 'fldz', 'fld st(0)', 'fld st(1)', 'fld st(2)', 'fld st(3)', 'fld st(4)', 'fld st(5)', 'fld st(6)', 'fld st(7)', 'fxch st(0)', 'fxch st(1)', 'fxch st(2)', 'fxch st(3)', 'fxch st(4)', 'fxch st(5)', 'fxch st(6)', 'fxch st(7)', 'fcmovb st(0), st(0)', 'fcmovb st(0), st(1)', 'fcmovb st(0), st(2)', 'fcmovb st(0), st(3)', 'fcmovb st(0), st(4)', 'fcmovb st(0), st(5)', 'fcmovb st(0), st(6)', 'fcmovb st(0), st(7)', 'fcmove st(0), st(0)', 'fcmove st(0), st(1)', 'fcmove st(0), st(2)', 'fcmove st(0), st(3)', 'fcmove st(0), st(4)', 'fcmove st(0), st(5)', 'fcmove st(0), st(6)', 'fcmove st(0), st(7)', 'fcmovbe st(0), st(0)', 'fcmovbe st(0), st(1)', 'fcmovbe st(0), st(2)', 'fcmovbe st(0), st(3)', 'fcmovbe st(0), st(4)', 'fcmovbe st(0), st(5)', 'fcmovbe st(0), st(6)', 'fcmovbe st(0), st(7)', 'fcmovu st(0), st(0)', 'fcmovu st(0), st(1)', 'fcmovu st(0), st(2)', 'fcmovu st(0), st(3)', 'fcmovu st(0), st(4)', 'fcmovu st(0), st(5)', 'fcmovu st(0), st(6)', 'fcmovu st(0), st(7)', 'fcmovnb st(0), st(0)', 'fcmovnb st(0), st(1)', 'fcmovnb st(0), st(2)', 'fcmovnb st(0), st(3)', 'fcmovnb st(0), st(4)', 'fcmovnb st(0), st(5)', 'fcmovnb st(0), st(6)', 'fcmovnb st(0), st(7)', 'fcmovne st(0), st(0)', 'fcmovne st(0), st(1)', 'fcmovne st(0), st(2)', 'fcmovne st(0), st(3)', 'fcmovne st(0), st(4)', 'fcmovne st(0), st(5)', 'fcmovne st(0), st(6)', 'fcmovne st(0), st(7)', 'fcmovnbe st(0), st(0)', 'fcmovnbe st(0), st(1)', 'fcmovnbe st(0), st(2)', 'fcmovnbe st(0), st(3)', 'fcmovnbe st(0), st(4)', 'fcmovnbe st(0), st(5)', 'fcmovnbe st(0), st(6)', 'fcmovnbe st(0), st(7)', 'fcmovnu st(0), st(0)', 'fcmovnu st(0), st(1)', 'fcmovnu st(0), st(2)', 'fcmovnu st(0), st(3)', 'fcmovnu st(0), st(4)', 'fcmovnu st(0), st(5)', 'fcmovnu st(0), st(6)', 'fcmovnu st(0), st(7)', 'ffree st(0)', 'ffree st(1)', 'ffree st(2)', 'ffree st(3)', 'ffree st(4)', 'ffree st(5)', 'ffree st(6)', 'ffree st(7)', 'fnop', 'fabs', 'fdecstp', 'fincstp', 'fxam']

Any of these FPU instructions are adequate for pre-populating the FPUDataPointer (address of previous FPU instruction) in the FPU environment which is extracted in the next step.

Step 2: Using FNSTENV to obtain EIP

Copy the 28-byte FPU environment structure to a specific memory address––usually on the stack. The structure is detailed below:

ESP[0]: FPUControlWord;
ESP[4]: FPUStatusWord;
ESP[8]: FPUTagWord;
ESP[0x0c]: FPUDataPointer;
ESP[0x10]: FPUInstructionPointer;
ESP[0x14]: FPULastInstructionOpcode;

This structure is hard-coded by the encoder for it to be written to [ESP - 0x0C], which means that the field FPUDataPointer will be directly at ESP (top of the stack), so it can be popped off directly in the next step.

FPUDataPointer will contain the address of the last FPU instruction executed (the one from the previous step), which allows the encoder to know where it is currently executing, so it can find the encoded payload relative to that instruction.

Step 3: Clear Register

ECX is zeroed out to set up the counter used in the loop. The interesting thing about this code is that it’s hardcoded to ECX using one of four possible operations, as:

   clear_register = Rex::Poly::LogicalBlock.new('clear_register',
      "\x31\xc9",  # xor ecx,ecx
      "\x29\xc9",  # sub ecx,ecx
      "\x33\xc9",  # xor ecx,ecx
      "\x2b\xc9")  # sub ecx,ecx

The counter is then initialized, and the loop is built. A handful of permutations are added in for the decode to make signature generation slightly trickier. Simply put, when there are that many choices in a permutation, the number of logical OR operations in a signature start increasing in complexity and cause performance issues. This is shown below.

   loop_block.add_perm(
      Proc.new { |b| xor1.call(b) + add1.call(b) + sub4.call(b) },
      Proc.new { |b| xor1.call(b) + sub4.call(b) + add2.call(b) },
      Proc.new { |b| sub4.call(b) + xor2.call(b) + add2.call(b) },
      Proc.new { |b| xor1.call(b) + add1.call(b) + add4.call(b) },
      Proc.new { |b| xor1.call(b) + add4.call(b) + add2.call(b) },
      Proc.new { |b| add4.call(b) + xor2.call(b) + add2.call(b) })

The loop instruction, shown below, is also set up to use two hardcoded bytes of E2 F5. 

   loop_inst = Rex::Poly::LogicalBlock.new('loop_inst',
      "\xe2\xf5")

Anytime a handful of static bytes are used in an encoder, they offer the defender the ability to use them as an anchor to tighten up signatures.

Step 4: Generating Samples and Testing

There are two primary methods for generating signatures:

1. Read the source of the encoder and figure out exactly how it’s working. Another benefit to having the source is knowing if there are any static bytes that we can use as anchors in our signatures. Although this is the better of the two methods, it’s not always available as an option.
2. Exhaustively create payloads and then disassemble them to determine commonalities in the generated payloads.

Creating a simple driver to brute force all single bad-byte combinations of Shikata Ga Nai is trivial enough to create test samples. The following Python snippet will do this using MSFVenom:

#!/usr/bin/env python
import subprocess
for i in xrange(0,256,1):
    fname = 'shikata_ga_nai_windows_shell_reverse_tcp_bad_byte_%02X' % i
        proc = 'msfvenom -e x86/shikata_ga_nai -p windows/shell_reverse_tcp LHOST=127.0.0.1 LPORT=4444 -f raw -b \'\\x%02X\'> %s' % (i, fname) 
    subprocess.call(proc, shell=True)

Once this completes running, we’ll have a nice sample set of 236 payloads. Some iterations will fail since the bytes are necessary for the payload generation. For this exercise, we're going to generate many different iterations of our payload encoded with Shikata Ga Nai and then do some testing. 

Step 5: Yara Signature

The following Yara signature will trigger on the variants mentioned in this post. In addition to typical raw bytes, we’ve also placed an ASCII version of the hexlified opcodes that will trigger on payloads typically found in RTF or script files where the payload is represented in hex pairs.

rule shikata_ga_nai_encoder
{
  meta:
        author = "Nick Hoffman / Jeremy Humble"
        description = "shikata ga nai shellcode encoder"
  strings:    
        /*
    Steps:
          fpu
          fstenv
          pop (getcpu)
          clear_register
          add counter
      Decode loop
        */
$op_decoder = {  (
    d9 (e8|e9|ea|eb|ec|ed|ee|c?|d0|e1|f6|f7|e5) |
    (da|db) (c?|d?) |
    dd (c0|c1|c2|c3|c4|c5|c6|c7)
 ) [0-8]                                                                   //
FPU instruction
 d9 74 24 f4 [0-8]                   // fnstenv
 (58|59|5a|5b|5c|5d|5e|5f) [0-8]     // pop
 (31|29|33|2b) c9 [0-8]              // clear register
 (b1|69 b9 | b9) [0-8]               // add counter
 (83 | 31 | 03) [1-8]                // xor/add/sub loop
 (83 | 31 | 03) [1-8]                // xor/add/sub loop
 (83 | 31 | 03)                      // xor/add/sub loop
}
        $ascii_decoder =
/(d9(e8|e9|ea|eb|ec|ed|ee|c?|d0|e1|f6|f7|e5)|(da|db)(c?|d?)|dd(c0|c1|c2|c3|c4|c5|c6|c7)).{0,16}d97424f4.{0,16}(58|59|5a|5b|5c|5d|5e|5f).{0,16}(31|29|33|2b)c9.{0,16}(b1|69b9|b9).{0,16}(83|31|03).{2,16}(83|31|03).{2,16}(83|31|03)/ nocase
  condition:
        any of them
}

Results

When using Yara to run this signature against our sample set of payloads encoded with Shikata Ga Nai, we trigger on all samples and have no hits against our benign repository. We correctly identify all 236 generated samples.

~# yara -r shikata_ga_nai.yar shikata_ga_nai_payloads | wc -l
236

Conclusions and Suggestions to Improve the Encoder

The authors created many different permutations and options for various steps, which make it difficult to write reliable signatures that could accurately trigger without introducing false positives. This becomes an easier task with tools like Yara that support robust regular expressions and provide fast scanning of files.

According to its GitHub history, Shikata Ga Nai hasn’t been re-written in a long time. If an author is looking to make this a more robust encoder, we offer the following suggestions, which were compiled after reviewing the source and building multiple signatures: 

1. Incorporate more junk code instructions in between blocks.
   • This will greatly reduce the effectiveness of static signatures and force the hand of the blue team into pursuing emulation.
   • The primary downside of this is potentially changing register states or increasing the size of the payload to a non-desirable outcome.
     
2. Support more options for GetEIP. Shikata Ga Nai is currently using the combination of two FPU instructions paired with a POP. 
   • By using another array and permuting the options, it can remove the ability to look for the hardcoded four bytes ("\xd9\x74\x24\xf4") of the FNSTENV instruction. 
3. Use other registers as counters and provide more permutations of the loop operation. 
   • Currently, the loop is done through a hard-coded E2 F5, and ECX is hardcoded as the counting register. 
   • Support other registers as indexes and have the loop decrement the value held within the register. This approach adds bytes to the payload but allows for more permutations, which are more difficult to write signatures against.

Impressive work is currently being done within the Metasploit Framework to evade A/V engines, by leveraging encryption and breaking the payload into stages. We look forward to these improvements and the new unique sets of challenges of defending against them. [2]

Check back for our next article in the Shellcode Signatures Series for additional technical insights intended for security practitioners.

External References and Examples:

[1] https://github.com/rapid7/metasploit-framework/blob/master/modules/encoders/x86/shikata_ga_nai.rb
[2] https://blog.rapid7.com/2018/05/03/hiding-metasploit-shellcode-to-evade-windows-defender/

We offer these recommendations for informational use only and do not make any warranties or other promises they will be effective in managing cyber threats.