HeroCTF v6: State

Could you decrypt the flag without the key ? Probably not.

Could you decrypt it with the stack ? Maaaaaaaybe …

No the key isn’t in the stack, what did you expect ?

Author : Alol

We are given a binary and its output: an encrypted flag a dump of the stack after encryption

Looking at the binary in Ghidra, we see a basic RC4 implementation:

undefined8 main(void)
{
  // ...
  int urand_fd;
  int flag_fd;
  byte *key_buf;
  byte *flag_buf;
  // ...
  int i;
  byte rc4_S [256];

  key_buf = (byte *)malloc(0x10);
  flag_buf = (byte *)malloc(0x1e);
  urand_fd = open("/dev/urandom",0);
  if (-1 < urand_fd) {
    sVar2 = read(urand_fd,key_buf,0x10);
    if (sVar2 == 0x10) {
      flag_fd = open("flag.txt",0);
      if (-1 < flag_fd) {
        sVar2 = read(flag_fd,flag_buf,0x1e);
        if (sVar2 == 0x1e) {
          close(urand_fd);
          close(flag_fd);
          rc4_genS(rc4_S,key_buf,0x10);
          rc4_enc(rc4_S,flag_buf,0x1e);
          for (i = 0; i < 0x1e; i = i + 1) {
            printf("%02hhx",(ulong)flag_buf[i]);
          }
          putchar(L'\n');
          write_stack_to_file();
          free(key_buf);
          free(flag_buf);
          // ...
        }
      }
    }
  }
  // ...
}

void rc4_genS(byte *S,byte *buf,int len)
{
  int i;
  int j;
  
  j = 0;
  for (i = 0; i < 0x100; i = i + 1) {
    S[i] = (byte)i;
  }
  for (i = 0; i < 0x100; i = i + 1) {
    j = (int)((uint)S[i] + j + (uint)buf[i % len]) % 0x100;
    swap(S + i,S + j);
  }
  return;
}

void rc4_enc(byte *S,byte *buf,int len)
{
  int i;
  int j;
  int idx;
  
  i = 0;
  j = 0;
  for (idx = 0; idx < len; idx = idx + 1) {
    i = (i + 1) % 0x100;
    j = (int)((uint)S[i] + j) % 0x100;
    swap(S + i,S + j);
    buf[idx] = buf[idx] ^ S[(byte)(S[j] + S[i])];
  }
  return;
}

As the challenge description says, the key isn’t on the stack (that and the flag go in malloc‘d buffers), but we do see in the variables something practically equally useful: internal state, specifically the S array.

Our task is quite simple: we just have to execute the algorithm in reverse to decipher the flag.

We start by finding S through the stack. Because it’s a permutation, we’re looking for 256 consecutive bytes such that each value is used once:

with open("output.txt", "r") as f:
	enc = bytes.fromhex(f.read())

with open("stack.bin", "rb") as f:
	stack = f.read()

counts = [0]*256
for i in range(0x100): counts[stack[i]] += 1
for i in range(0x100,len(stack)-0xff):
	counts[stack[i-0x100]] -= 1
	counts[stack[i]] += 1
	if all(c == 1 for c in counts):
		S = list(stack[i-0xff:i+1])
		print("S @", i-0xff, ":", S)

For your convenience during this next part, here’s the RC4 “pseudo-random generation algorithm” from wikipedia (to read in reverse):

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    t := (S[i] + S[j]) mod 256
    K := S[t]
    output K
endwhile

That final “output K” line is, in practice, ciphertext[idx] = plaintext[idx] xor K (Note that I’m not using i here: i is only internal RC4 state, not the index into the buffer we’re encrypting). Since we know the plaintext is a Hero{flag}, we can obtain the last K, and then do an index search to find t:

flag = [0x7d]

k = flag[0] ^ enc[-1]
t = S.index(k)

Since i is incremented once per iteration, we know that during the final iteration, it’s the length of the message (in our case 30). We can then use another index search to solve for j:

i = 0x1e
j = S.index((t - S[i]) % 256)

Then, running the rest of the cipher in reverse becomes easy. We already have the values of i and j at the end of the iteration, from which we can compute t then K and xor to decrypt. Do the swap, then simply subtract instead of adding to obtain the previous (next for us) values of i and j:

S[i], S[j] = S[j], S[i]
j = (j - S[i]) % 256

for i in range(0x1e-1,0,-1): # N.B. excludes i=0
	t = (S[i] + S[j]) % 256
	flag.append(S[t] ^ enc[i-1])

	S[i], S[j] = S[j], S[i]
	j = (j - S[i]) % 256

print(bytes(reversed(flag)))

And that’s our flag: Hero{AESKeyFinder_but_for_RC4}