I Wanted Orange (The machine would not make a mistake.)

3Aug/16Off

Experiments in decryption – Overwatch puzzle

As part of it's "Summer Games" update, Overwatch put an easter-egg into their video, embedding some base64-encoded text into a scene. Overwatch Base64 hint

 

Unfortunately there may be errors since the font doesn't clearly distinguish between certain characters such as 1/l/I, but one interpretation comes out to binary data like:

>>> binascii.b2a_qp(binascii.a2b_base64("U2FsdGVkX1+vupppZksvRf5pq5g5XjFRlipRkwB0K1Y96Qsv2L m+31cmzaAILwytX/z66ZVWEQM/ccf1g+9m5Ubu1+sit+A9cenD xxqklaxbm4cMeh2oKhqlHhdaBKOi6XX2XDWpa6+P5o9MQw=="))
'Salted__=AF=BA=9AifK/E=FEi=AB=989^1Q=96*Q=93=00t+V=3D=E9=0B/=D8=B9=BE=DFW&=\n=CD=A0=08/=0C=AD_=FC=FA=E9=95V=11=03?q=C7=F5=83=EFf=E5F=EE=D7=EB"=B7=E0=3Dq=\n=E9=C3=C7=1A=A4=95=AC[=9B=87=0Cz=1D=A8*=1A=A5=1E=17Z=04=A3=A2=E9u=F6\\5=A9k=\n=AF=8F=E6=8FLC'

This seems to be from an OpenSSL command-line encryption utility, since it begins with the bytes for "Salted__". I'm really no crypto expert, but this is interesting. Maybe I can at least run a dictionary-attack against it?

The first thing to note about the puzzle is that it has an odd number of bytes, implying that that a "stream" cipher was used rather than a "block" cipher, or at least a block cipher being used in a streaming mode. Our chances of guessing the right one are somewhat slim anyway, so why not start with a simple stream-cipher, RC4? First we need to figure out how it's implemented in the OpenSSL command-line tools. Let's try a simple example using "x" (one byte) as our secret message, and "test" as our key:

$ hexdump temp.txt
0000000 0078
0000001

$ openssl RC4 -S FFFFFFFFFFFFFFFF -k "test" -p -in temp.txt -a
salt=FFFFFFFFFFFFFFFF
key=D7BA581CCB7DBAFD5BD1C7DF8BDDE4E3
U2FsdGVkX1///////////5Y=

 

By forcing the salt to a known 8-byte pattern (-S) and by telling OpenSSL to show us the key it created (-p) we know that somehow all those FF's and "test" combined to make D7BA581CCB7DBAFD5BD1C7DF8BDDE4E3. This is useful, because with a small amount of trial-and-error I can figure out how it is generated, leading to this Python script which gives the same key-output:

import binascii
from Crypto.Hash import MD5

password = "test"
salt = binascii.a2b_hex("FFFFFFFFFFFFFFFF")
key = MD5.new(password+salt).digest()
print binascii.b2a_hex(key) # Output: d7ba581ccb7dbafd5bd1c7df8bdde4e3

Now we're one step on the way to scripting up a compatible RC4 encoding routine, which ends up looking like:

import binascii
from Crypto.Hash import MD5
from Crypto.Cipher import ARC4

def encryptString(self, in_str, password):
    salt =  binascii.a2b_hex('FF' * 8)
    tempkey = MD5.new(password+salt).digest()
    print binascii.b2a_hex(tempkey)
    cipher = ARC4.new(tempkey)
    enc = cipher.encrypt(in_str)
    return 'Salted__' + salt + enc

Great! Now we can implement decoding, and after a little more tinkering, and we've got a little Python class which can encrypt/decrypt the same as the command-line tool:

import binascii
from Crypto.Hash import MD5
from Crypto.Cipher import ARC4
from Crypto import Random

class SimpleRc4:
    def __init__(self):        
        self.random = Random.new()       
        self.header = "Salted__"
        self.saltLen = 8

    def encryptString(self, in_str, password):        
        salt =  self.random.read(self.saltLen)
        tempkey = MD5.new(password+salt).digest()
        cipher = ARC4.new(tempkey)
        enc = cipher.encrypt(in_str)
        return self.header + salt + enc
    
    def decryptString(self, in_str, password):        
        salt = in_str[len(self.header) : len(self.header)+self.saltLen]
        body = in_str[len(self.header)+self.saltLen:]
        tempkey = MD5.new(password+salt).digest()        
        cipher = ARC4.new(tempkey)
        dec = cipher.decrypt(body)
        return dec

    def selftest(self):
        password = "selftest"
        a = "Content"                    
        b = self.encryptString(a,password)                                        
        c = self.decryptString(b,password)        
        assert(a == c)

So what's this kind of thing useful for? Quickly trying lots and lots of decodings. Here, let's build up a brute-forcing framework, and prove that we can crack a simple RC4-encoded message... (Github Gist)

#!/usr/bin/python
import sys
import itertools
import binascii
import StringIO

from Crypto.Hash import SHA, MD5
from Crypto.Cipher import AES, ARC4
from Crypto import Random
    

class Breaker:
    def __init__(self,e,puzzle):
        self.e = e
        self.puzzle = puzzle
        self.last = None
            
    def attempt(self, password):
        self.last = password
        result = self.e.decryptString(self.puzzle, password)                
        return result
    
    def comboAttack(self, sequence, tester):
        for pw in sequence:            
            result = b.attempt(pw)
            if tester(result):
                yield (pw, result)
                
    @staticmethod
    def CheckBoringAscii(result):
        for c in result:
            d = ord(c)
            if d > 127:
                return False
            elif d < 32:
                return False
            
        return True

    @staticmethod
    def GenPasswordList(passwordFile):        
        with open(passwordFile,'rb') as pwdict:
            for line in pwdict:            
                pw = line.strip()
                yield pw

    @staticmethod
    def GenBrute(charset, maxlength):        
        for i in range(1, maxlength + 1):            
            for c in itertools.product(charset,repeat=i):
                yield ''.join(c)       

class SimpleRc4:
    def __init__(self):        
        self.random = Random.new()       
        self.header = "Salted__"
        self.saltLen = 8

    def encryptString(self, in_str, password):        
        salt =  self.random.read(self.saltLen)
        tempkey = MD5.new(password+salt).digest()
        cipher = ARC4.new(tempkey)
        enc = cipher.encrypt(in_str)
        return self.header + salt + enc
    
    def decryptString(self, in_str, password):        
        salt = in_str[len(self.header) : len(self.header)+self.saltLen]
        body = in_str[len(self.header)+self.saltLen:]
        tempkey = MD5.new(password+salt).digest()        
        cipher = ARC4.new(tempkey)
        dec = cipher.decrypt(body)
        return dec

    def selftest(self):
        password = "selftest"
        a = "Content"                    
        b = self.encryptString(a,password)                                        
        c = self.decryptString(b,password)        
        assert(a == c)


if __name__ == "__main__":
   
    e = SimpleRc4()    
    e.selftest()
    sample = e.encryptString("brute decode challenge", "test")
    
    b = Breaker(e, sample)
    
    source = Breaker.GenBrute('abcdefghijklmnopqrstuvwxyz',4)
    tester = Breaker.CheckBoringAscii
    for pw,result in b.comboAttack(source, tester):
        print pw, result 
    #Output: test brute decode challenge

And... Yes! It manages to crack the sample.

I'll explore applying this framework to the actual Overwatch puzzle in a follow-up post. I'll need to put in some fuzzier logic to handle the fact that the source-data -- the ciphertext -- may be subtly corrupted by errors by humans who have to write it down from inside a video-frame.