Identifying Cryptographic Algorithms

Recognising XOR, Base64 and Custom Encodings dealt with transformations you can undo by looking hard enough. Real ciphers are different: without the key, the output is designed to be indistinguishable from random, and no amount of frequency analysis will help. But malware must carry or derive its key somewhere you can reach, and ciphers are among the easiest code to identify, because they are full of fixed constants.

Your job here is not cryptanalysis. It is to answer four questions quickly: which algorithm, in which mode, with which key and IV, and where do they come from? Those answers let someone write a decryptor, a config extractor or a network signature.

Encoding or encryption?

Before naming an algorithm, decide which class you are dealing with. The distinction is practical, not academic:

Two edge cases matter. RC4 is a real cipher but small enough to look like a decoder. And a repeating 16-byte XOR key is still encoding, however random it looks: if ciphertext XOR known plaintext repeats, it is XOR, not AES.

Tip: A ciphertext length that is always a multiple of 16 points to a 128-bit block cipher (AES), and a multiple of 8 to a 64-bit one (DES, 3DES, Blowfish, TEA). Identical 16-byte blocks inside one ciphertext suggest ECB mode, which leaks repeated plaintext blocks.

Recognising algorithms from constants

Most algorithms need fixed numbers: S-boxes, initial hash values, round constants or magic words, stored as tables in .rdata or as immediates in code. Search for both byte orders, since x86 stores 32-bit words little-endian (see endianness).

One matching constant is a lead, not a verdict: 0x67452301 alone could be MD5, SHA-1 or RIPEMD-160. Look for the full table or several constants in one function.

Structure: RC4, bignums and friends

RC4 has no constants, but it has an unmistakable shape. The key schedule (KSA) fills a 256-byte array with the values 0 to 255, then runs a second 256-iteration loop that swaps pairs of entries under the control of the key. The generator (PRGA) is a short loop that increments i, adds S[i] to j, swaps again and XORs the data with S[(S[i] + S[j]) & 0xFF]. Two 256-iteration loops back to back, one with a single byte store and one with two, plus heavy movzx use for the & 0xFF, is RC4 until proven otherwise.

RSA and elliptic-curve code has no S-boxes, just loops over arrays of 32- or 64-bit limbs using mul, adc and sbb, plus square-and-multiply or Montgomery reduction. Curve constants such as the P-256 prime or 121665 (Curve25519) name the curve. Malware rarely writes this by hand; it uses CryptoAPI, CNG or a linked library.

AES with AES-NI has no table either: look for aesenc, aesenclast and aeskeygenassist in SIMD registers.

Recognising algorithms from imports and libraries

The easiest case is malware that asks Windows to do the crypto: the call sequences are recognisable and the parameters name the algorithm.

If these APIs are resolved dynamically, the import table will not show them. Look for the DLL and function names as strings, or as hashes (see API hashing), and return to the lesson on Reading Capabilities from Imports for the general method.

Statically linked libraries are the other common case. OpenSSL, mbedTLS, Crypto++, libsodium, Go's crypto/* packages and Rust crates bring their own error and version strings (in Go, package paths survive stripping). Identify the library, rename its functions and do not reverse it; focus on the caller. FLIRT in IDA, Function ID in Ghidra and capa's library signatures automate this.

Tools

Run a constant scanner and capa together: a table match tells you what, and cross-references or capa's function address tell you where.

Warning: Constants can be hidden. Authors compute tables at runtime, store them XOR-encoded, or tweak a constant (a modified TEA delta, a non-standard S-box). A tool that finds "nothing" has only proved that the standard tables are not stored in plain form.

Finding the key and the IV

Once you know the function, the key is one of its arguments. Work backwards from the call site:

1. Follow the arguments. In the Windows x64 ABI the first four arguments are in rcx, rdx, r8 and r9. A lea rcx, [rip+...] pointing into .rdata or .data, followed by a small constant length in rdx, is often the key and its size. For API calls, the key is the blob passed to CryptImportKey or the buffer passed to BCryptGenerateSymmetricKey.
2. Check for derivation. The stored value may be a password that is hashed first (CryptCreateHash + CryptDeriveKey, PBKDF2, or a custom routine). Report the stored secret and the derivation, because a decryptor needs both.
3. Find the IV and mode. Look for a 16-byte buffer passed alongside the key, a BCryptSetProperty call naming the chaining mode, or a CryptSetKeyParam with KP_IV or KP_MODE. An IV is often prepended to each ciphertext, so check whether the first 16 bytes of every message are consumed separately.
4. Go dynamic when static is hard. In a debugger, set a breakpoint on the decryption function, CryptImportKey or BCryptGenerateSymmetricKey and read the key from the arguments. In memory dumps, aeskeyfind searches for expanded AES key schedules.

Always confirm a recovered key by decrypting real data with an independent implementation (Python's cryptography package or CyberChef). Matching output is the only proof.

What to report

A crypto finding should let a colleague reproduce the decryption without opening the sample:

If the key is generated per victim and wrapped with an embedded RSA public key, as in much ransomware, say so: it decides what responders can recover.

Lab: find RC4 and CRC32 in a binary

You will compile a harmless program with a hand-written RC4 and a table-driven CRC32, then find both with a YARA constant scan, a Capstone idiom scanner and capa. You need mingw-w64 and a virtual environment with yara-python, capstone, pefile and, optionally, flare-capa.

1. Build the program. Save as cryptolab.c. The CRC32 table is precomputed, as zlib does it; the listing below truncates it after the first entries, so generate the full 256-entry table with a few lines of Python (the standard reflected algorithm with polynomial 0xEDB88320) and paste it in.

   // cryptolab.c - RC4 and a table-driven CRC32 over a demo string (benign lab program)
   #include <stdio.h>
   #include <string.h>
   #include <stdint.h>
   
   /* Precomputed like zlib's crc32.c: reflected polynomial 0xEDB88320 */
   static const uint32_t crc_table[256] = {
       0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
       /* ... 250 more entries ... */
   };
   
   static uint32_t crc32(const unsigned char *p, size_t n) {
       uint32_t c = 0xFFFFFFFFu;
       while (n--)
           c = crc_table[(c ^ *p++) & 0xFF] ^ (c >> 8);
       return c ^ 0xFFFFFFFFu;
   }
   
   static void rc4(const unsigned char *key, size_t klen, unsigned char *buf, size_t n) {
       unsigned char S[256];
       for (int i = 0; i < 256; i++)               /* KSA: identity permutation */
           S[i] = (unsigned char)i;
       for (int i = 0, j = 0; i < 256; i++) {      /* KSA: key-driven swaps */
           j = (j + S[i] + key[i % klen]) & 0xFF;
           unsigned char t = S[i]; S[i] = S[j]; S[j] = t;
       }
       for (size_t k = 0, i = 0, j = 0; k < n; k++) {  /* PRGA */
           i = (i + 1) & 0xFF;
           j = (j + S[i]) & 0xFF;
           unsigned char t = S[i]; S[i] = S[j]; S[j] = t;
           buf[k] ^= S[(S[i] + S[j]) & 0xFF];
       }
   }
   
   int main(void) {
       static const unsigned char key[] = "lab-rc4-key";
       unsigned char msg[] = "server=update.example.com;port=8080;id=lab";
       size_t n = strlen((char *)msg);
   
       printf("crc32(plain) = %08x\n", crc32(msg, n));
       rc4(key, sizeof(key) - 1, msg, n);
       printf("rc4 first bytes = %02x %02x %02x %02x\n", msg[0], msg[1], msg[2], msg[3]);
       rc4(key, sizeof(key) - 1, msg, n);
       printf("round trip: %s\n", msg);
       return 0;
   }

   x86_64-w64-mingw32-gcc -O1 -s -o cryptolab.exe cryptolab.c
   x86_64-w64-mingw32-gcc -O2 -s -o cryptolab_O2.exe cryptolab.c

   Built natively (clang -O2 cryptolab.c) and run, it prints:

   crc32(plain) = 65f3938f
   rc4 first bytes = 7b 88 57 44
   round trip: server=update.example.com;port=8080;id=lab

2. Scan for constants with YARA. Save a small rule set as crypto_consts.yar. Each rule is a fragment of a table from the constants section above:

   rule CRC32_table_reflected {
       strings:
           $t = { 00 00 00 00 96 30 07 77 2C 61 0E EE BA 51 09 99 }
       condition:
           $t
   }
   rule CRC32_poly_immediate {
       strings:
           $p = { 20 83 B8 ED }            // 0xEDB88320 as a little-endian dword
       condition:
           $p
   }
   rule SHA256_initial_values {
       strings:
           $h = { 67 E6 09 6A 85 AE 67 BB 72 F3 6E 3C 3A F5 4F A5 }
       condition:
           $h
   }
   rule AES_forward_sbox {
       strings:
           $s = { 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 }
       condition:
           $s
   }
   rule ChaCha_Salsa_sigma {
       strings:
           $s = "expand 32-byte k"
       condition:
           $s
   }
   rule TEA_delta {
       strings:
           $d1 = { B9 79 37 9E }           // 0x9E3779B9
           $d2 = { 47 86 C8 61 }           // 0x61C88647 (= -0x9E3779B9)
       condition:
           any of them
   }

   Then map each hit to a section and virtual address with scan_consts.py:

   # scan_consts.py - run the crypto-constant YARA rules and map hits to PE sections
   import sys, pefile, yara
   
   rules = yara.compile(filepath="crypto_consts.yar")
   for path in sys.argv[1:]:
       pe = pefile.PE(path)
       data = open(path, "rb").read()
       print(f"== {path}")
       for m in rules.match(data=data):
           for s in m.strings:
               for inst in s.instances:
                   sec = next((x.Name.rstrip(b"\0").decode() for x in pe.sections
                               if x.PointerToRawData <= inst.offset < x.PointerToRawData + x.SizeOfRawData), "?")
                   rva = pe.get_rva_from_offset(inst.offset)
                   print(f"  {m.rule:24} {s.identifier:4} offset=0x{inst.offset:05x} "
                         f"va=0x{pe.OPTIONAL_HEADER.ImageBase + rva:x} {sec}")

   python scan_consts.py cryptolab.exe cryptolab_O2.exe

   == cryptolab.exe
     CRC32_table_reflected    $t   offset=0x02460 va=0x140004060 .rdata
     CRC32_poly_immediate     $p   offset=0x02660 va=0x140004260 .rdata
   == cryptolab_O2.exe
     CRC32_table_reflected    $t   offset=0x02460 va=0x140004060 .rdata
     CRC32_poly_immediate     $p   offset=0x02660 va=0x140004260 .rdata

   The table is found at the same place in both builds. Note that the "polynomial" hit is not an immediate in code: it sits 0x200 bytes into the table, because entry 128 of the reflected CRC32 table equals the polynomial itself. Always check where a hit lands. No rule finds RC4, because RC4 has no constants.

3. Find RC4 by structure with Capstone. Save as find_rc4.py. It looks for short loops that end in a backward conditional jump, compare against 0xFF or 0x100, and write single bytes:

   # find_rc4.py - flag tight 256-iteration loops that write bytes (RC4 KSA shape)
   import sys, pefile
   from capstone import Cs, CS_ARCH_X86, CS_MODE_64
   from capstone.x86 import X86_OP_IMM, X86_OP_MEM
   
   pe = pefile.PE(sys.argv[1])
   text = next(s for s in pe.sections if s.Name.startswith(b".text"))
   base = pe.OPTIONAL_HEADER.ImageBase + text.VirtualAddress
   md = Cs(CS_ARCH_X86, CS_MODE_64)
   md.detail = True
   insns = list(md.disasm(text.get_data(), base))
   index = {i.address: n for n, i in enumerate(insns)}
   
   def byte_store(i):
       ops = i.operands
       return (i.mnemonic == "mov" and len(ops) == 2 and ops[0].type == X86_OP_MEM
               and ops[0].size == 1)
   
   loops = []
   for n, i in enumerate(insns):
       # a conditional jump backwards = the bottom of a loop
       if not i.mnemonic.startswith("j") or i.mnemonic == "jmp":
           continue
       tgt = i.operands[0].imm if i.operands[0].type == X86_OP_IMM else None
       if tgt is None or tgt >= i.address or tgt not in index:
           continue
       body = insns[index[tgt]:n + 1]
       if len(body) > 25:
           continue
       bound = [x for x in body if x.mnemonic == "cmp" and x.operands[-1].type == X86_OP_IMM
                and x.operands[-1].imm in (0xFF, 0x100)]
       stores = [x for x in body if byte_store(x)]
       if bound and stores:
           loops.append((tgt, i.address, len(body), len(stores)))
   
   for start, end, size, nst in loops:
       print(f"loop 0x{start:x}-0x{end:x}: {size:2} insns, 256 iterations, {nst} byte store(s)")
   # RC4 KSA: an init loop (1 store) followed closely by a swap loop (>= 2 stores)
   for a, b in zip(loops, loops[1:]):
       if a[3] == 1 and b[3] >= 2 and b[0] - a[1] < 0x40:
           print(f"RC4 KSA candidate: init 0x{a[0]:x}, swap 0x{b[0]:x}")
           for x in insns[index[a[0]]:index[a[1]] + 1]:
               print(f"  {x.address:x}: {x.mnemonic:6} {x.op_str}")

   python find_rc4.py cryptolab.exe

   loop 0x1400014e0-0x1400014ee:  5 insns, 256 iterations, 1 byte store(s)
   loop 0x140001500-0x140001539: 16 insns, 256 iterations, 2 byte store(s)
   RC4 KSA candidate: init 0x1400014e0, swap 0x140001500
     1400014e0: mov    byte ptr [rdx], al
     1400014e2: add    eax, 1
     1400014e5: add    rdx, 1
     1400014e9: cmp    eax, 0x100
     1400014ee: jne    0x1400014e0

   The five-instruction loop is S[i] = i, and the swap loop follows immediately. Now run the same script on cryptolab_O2.exe: it prints nothing. At -O2 GCC vectorises the identity loop into SSE instructions that fill sixteen bytes per iteration, so there is no cmp eax, 0x100 left to match. Keep that in mind whenever a hand-written heuristic comes back empty.

4. Run capa. Installed with pip install flare-capa, capa 9.4 needs its rules (the capa-rules repository) and the sigs directory from the capa repository at the same tag:

   capa -r capa-rules -s capa/sigs cryptolab.exe

   Trimmed to the relevant rows:

   │ CRYPTOGRAPHY         │ Encrypt Data::RC4 [C0027.009]                         │
   │                      │ Encryption Key::RC4 KSA [C0028.002]                   │
   │                      │ Generate Pseudo-random Sequence::RC4 PRGA [C0021.004] │
   │ DATA                 │ Checksum::CRC32 [C0032.001]                           │
   │                      │ Encode Data::XOR [C0026.002]                          │
   ...
   │ hash data with CRC32                    │ data-manipulation/checksum/crc32   │
   │ encode data using XOR (2 matches)       │ data-manipulation/encoding/xor     │
   │ encrypt data using RC4 KSA              │ data-manipulation/encryption/rc4   │
   │ encrypt data using RC4 PRGA             │ data-manipulation/encryption/rc4   │

   With -vv, capa shows why. The RC4 KSA rule matched function 0x1400014C0 on two tight loops bounded by 0x100 (at 0x1400014E9 and 0x140001532, the same loops your script found) plus the movzx pattern for "modulo 256". The CRC32 rule matched the first 32 bytes of the table. Run capa on cryptolab_O2.exe too: it still reports CRC32 and RC4 PRGA, but "RC4 KSA" disappears, for the same reason your script went quiet.

5. Find the key at the call site. capa gave you the RC4 function, 0x1400014c0. Look at how it is called:

   x86_64-w64-mingw32-objdump -d -M intel cryptolab.exe | grep -B6 "call   0x1400014c0"

   14000168b:	48 8d 3d be 29 00 00 	lea    rdi,[rip+0x29be]        # 0x140004050
   140001692:	49 89 d9             	mov    r9,rbx
   140001695:	49 89 f0             	mov    r8,rsi
   140001698:	ba 0b 00 00 00       	mov    edx,0xb
   14000169d:	48 89 f9             	mov    rcx,rdi
   1400016a0:	e8 1b fe ff ff       	call   0x1400014c0

   The first argument (rcx) is 0x140004050 and the second (rdx) is 11: an 11-byte key in .rdata. Dump it with x86_64-w64-mingw32-objdump -s -j .rdata cryptolab.exe and you will see lab-rc4-key at that address, directly before the CRC32 table.

6. Confirm with an independent implementation. Save as rc4_check.py:

   # rc4_check.py - confirm the identification: same key, same keystream as the binary
   import pefile, zlib
   
   def rc4(key: bytes, data: bytes) -> bytes:
       S = list(range(256)); j = 0
       for i in range(256):
           j = (j + S[i] + key[i % len(key)]) & 0xFF
           S[i], S[j] = S[j], S[i]
       out, i, j = bytearray(), 0, 0
       for b in data:
           i = (i + 1) & 0xFF; j = (j + S[i]) & 0xFF
           S[i], S[j] = S[j], S[i]
           out.append(b ^ S[(S[i] + S[j]) & 0xFF])
       return bytes(out)
   
   pe = pefile.PE("cryptolab.exe")
   key = pe.get_data(0x4050, 11)            # RVA of the lea rcx target, length from edx=0xb
   msg = b"server=update.example.com;port=8080;id=lab"
   print("key       :", key)
   print("rc4 first :", rc4(key, msg)[:4].hex(" "))
   print("crc32     :", f"{zlib.crc32(msg):08x}")

   key       : b'lab-rc4-key'
   rc4 first : 7b 88 57 44
   crc32     : 65f3938f

   Both values match what the program printed in step 1. You have now identified both algorithms, located the key, and verified the result: everything the report table asks for.

   For contrast, repeat step 5 on cryptolab_O2.exe. The two calls to 0x1400014c0 now pass only the buffer (lea rcx,[rsp+0x30]) and its length (mov edx,0x2a). GCC specialised the function for its single constant key: the key address 0x140004050 and a magic-number multiplication for i % 11 moved inside it. The key is still there, but you find it by reading the function body, not the call site.

Questions to answer: Why did the YARA scan find CRC32 but not RC4, and which approach found RC4 instead? Which capa rule disappeared at -O2, and what does that tell you about trusting a single tool? If the key at 0x140004050 had been XOR-encoded and decoded just before the call, which steps of this lab would still work and which would you replace with a debugger breakpoint? Write the "what to report" table for this binary.

Key takeaways

• Encryption depends on a real key and produces near-random output; encoding does not. Known plaintext that reveals a repeating key means you are still looking at an encoding.
• Constants identify most algorithms: AES S-boxes, MD5/SHA initial values, CRC32 tables, the ChaCha20 expand 32-byte k string and the TEA delta. Search both byte orders and check where each hit lands.
• RC4, RSA and AES-NI have no telltale tables; recognise them by structure. CryptoAPI and CNG name the algorithm in their parameters, and linked libraries should be identified rather than reversed.
• capa, FindCrypt, signsrch and YARA complement each other, and all can miss optimised or modified code. Confirm every identification by decrypting with an independent implementation.
• Report algorithm, mode, purpose, implementation, key location and key material, with the evidence that proves it.