Santhacklaus 2019: Christmas Locker

Published December 23, 2019 • 2 minutes read

Before we start! This post is authored by @pwnh4. I'm really proud to have him for this guest post as he started computer security only a few months ago with my 2019 Piscine but already performs very well in CTF. Go follow him!

Christmas Locker is a cryptography challenge of the Santhacklaus 2019 CTF.


We get two files:

➜  unzip
 extracting: secret.pdf.santa        

What's up?

We can easily understand that we need to decode the .pdf.santa file into its .pdf equivalent by reversing the encryption. Let's see what's in this script:

import sys

lfsr_size = 32
lfsr_feeback = 0X100400007

def binarraytoint(bitlist):
    out = 0
    for bit in bitlist:
        out = (out << 1) | bit
    return out

def hamming_weigth(x):
    c = 0
        c += x % 2
        x = x >> 1
    return c

class shift_encrypt():
    def __init__(self,state,lfsr_size,feedback):
        self.state = state
        self.lfsr_size = lfsr_size = feedback

    def get_key_stream(self,stream_size):
        stream = []
        for i in range(stream_size):
            newbit = hamming_weigth (self.state & % 2
            newbit = newbit << self.lfsr_size - 1
            self.state = (self.state >> 1) | newbit
        return stream

def encrypt_byte(stream, b):
    k = binarraytoint(stream)
    b = int.from_bytes(b,"big")
    c = b ^ k
    c = c.to_bytes(1, byteorder='big')
    return c 

if (len(sys.argv) != 3):
        print ("Usage: shift_encrypt <key> <file>")

state = int(sys.argv[1],16)

se = shift_encrypt(state,lfsr_size,lfsr_feeback)

    input = open(sys.argv[2],"rb")
    output = open(sys.argv[2]+".santa","wb")

    while True:
        cleartext =
        if cleartext:
            stream = se.get_key_stream(8)
            c = encrypt_byte(stream,cleartext)  


We can see that the encryption process uses an LFSR logic.

An LFSR (for Linear Feedback Shift Registers) can, in this implementation, be described as :

Here, each state is used to generate a byte, called stream (with the method get_key_stream) that will then be used to XOR a byte of the input file. This is how the PDF file was encrypted.

Sexy representation of the encryption process:

initial_state -> process -> update state -> process -> update state -> ...
                    |                          | 
                    |-> generated stream byte  |-> generated stream byte 
                           |                          |
                           |-> XOR with input         |-> XOR with input


We know that the encrypted file is a PDF. So we know that this file starts with the bytes %PDF. We can easily find the first generated stream by XORing the byte % with the first encrypted byte.

The issue here is that there are multiple initial states of the LFSR that can generate this initial stream.

So what we can do is try every possibilities of initial states which generate the correct stream for the first 4 bytes of the pdf. If an initial state can be valid during four cycles, we can assume that it will be valid for all the rest of the file.

def get_original_state(encrypted, checking=0, state=None):
  encrypted : encrypted files as bytes array
  checking  : current evaluated byte
  state     : initial state of the current cycle
  first_pdf_bytes = [0x25, 0x50, 0x44, 0x46]
  if checking == len(first_pdf_bytes):
      return True

  # get the stream used to XOR the CHECKINGth byte
  orig_intstream = first_pdf_bytes[checking] ^ encrypted[checking]
  orig_stream = []
  for i in range(8):
      orig_stream.append(orig_intstream & 1)
      orig_intstream = orig_intstream >> 1
  orig_stream = orig_stream[::-1]

  if not state:
      # we iterate over all possible first state values
      for x in range(0, 99999999):
          STATE = x
          stream = []
          for i in range(8):
              newbit = hamming_weigth(x & 0X100400007) % 2
              newbit = newbit << 32 - 1
              x = (x >> 1) | newbit
          if stream == orig_stream:
              # check recursively if the current initial state is valid for the next
              if get_original_state(encrypted, checking + 1, x):
                  print("[+] Original state was", STATE)
      x = state
      stream = []
      for i in range(8):
          newbit = hamming_weigth(x & 0X100400007) % 2
          newbit = newbit << 32 - 1
          x = (x >> 1) | newbit
      if stream == orig_stream:
          # if arrive here, the intermediate cycle is validated and try to validate next cycle
          return get_original_state(encrypted, checking + 1, x)
  return False

Which outputs:

[+] Original state was 5929497

We can now launch the script with this value and get the original PDF file, in which we can see :


← Back to the index