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

4Aug/16Off

Uncertain Base64 – Overwatch Puzzle

As I mentioned in yesterday's post, there's an Overwatch graphic of some base64 text with an unclear font... But what's the point of writing something to solve a puzzle when you aren't sure you have the right question?
Overwatch Base64 Issues
So I made this little function which takes a base64-string and generates visually-similar versions:

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

def B64Variants(val, confusions = None):
    if confusions is None:
        confusions = ["Il1","O0"] # Use defaults
    val = val.translate(None, " \n\t") # Remove whitespace
    sections = []        
    for char in val:
        confused = False
        for group in confusions:
            if char in group:
                confused = True                
                sections.append(list(group))
                
        if not confused:   
            if (len(sections) > 0) and isinstance(sections[-1],str):
                sections[-1] = sections[-1] + char
            else:
                sections.append(char)       
    # Tidy up so we have a consistent list-of-lists
    for i,v in enumerate(sections):
        if isinstance(v,str):
            sections[i] = [v]                
    for varBits in apply(itertools.product, sections):
        yield "".join(varBits)

if __name__ == "__main__":
    sample = binascii.b2a_base64("Hello, World!")
    print "given", sample
    for var in B64Variants(sample):
        print "maybe", var    

Example output:

given SGVsbG8sIFdvcmxkIQ==

maybe SGVsbG8sIFdvcmxkIQ==
maybe SGVsbG8sIFdvcmxklQ==
maybe SGVsbG8sIFdvcmxk1Q==
maybe SGVsbG8slFdvcmxkIQ==
maybe SGVsbG8slFdvcmxklQ==
maybe SGVsbG8slFdvcmxk1Q==
maybe SGVsbG8s1FdvcmxkIQ==
maybe SGVsbG8s1FdvcmxklQ==
maybe SGVsbG8s1Fdvcmxk1Q==

I think the next step is to try hooking this up to code which tries to decode the cipher-stream byte by byte, skipping to a new password (or a new Base64 source-string) when the decoded byte goes outside conventional ASCII. (I'm gambling that it'll contain an ASCII message, if it doesn't then it's hard to know if you've successfully cracked it.)

Finally, what happens if we apply this to one of the transcriptions people have made from the Overwatch Summer Games video?

U2FsdGVkXI+vupppZksvRf5pq5g5XjFRIipRkwBOKIY96Qsv2Lm+3IcmzaAILwytX/z66ZVWEQMccfIg+9m5UbuI+sit+A9cenDxxqkIaxbm4cMeh2oKhqIHhdaBKOi6XX2XDWpa6+P5o9MQw==
U2FsdGVkXI+vupppZksvRf5pq5g5XjFRIipRkwBOKIY96Qsv2Lm+3IcmzaAILwytX/z66ZVWEQMccfIg+9m5UbuI+sit+A9cenDxxqkIaxbm4cMeh2oKhqIHhdaBK0i6XX2XDWpa6+P5o9MQw==
U2FsdGVkXI+vupppZksvRf5pq5g5XjFRIipRkwBOKIY96Qsv2Lm+3IcmzaAILwytX/z66ZVWEQMccfIg+9m5UbuI+sit+A9cenDxxqkIaxbm4cMeh2oKhqlHhdaBKOi6XX2XDWpa6+P5o9MQw==
U2FsdGVkXI+vupppZksvRf5pq5g5XjFRIipRkwBOKIY96Qsv2Lm+3IcmzaAILwytX/z66ZVWEQMccfIg+9m5UbuI+sit+A9cenDxxqkIaxbm4cMeh2oKhqlHhdaBK0i6XX2XDWpa6+P5o9MQw==
U2FsdGVkXI+vupppZksvRf5pq5g5XjFRIipRkwBOKIY96Qsv2Lm+3IcmzaAILwytX/z66ZVWEQMccfIg+9m5UbuI+sit+A9cenDxxqkIaxbm4cMeh2oKhq1HhdaBKOi6XX2XDWpa6+P5o9MQw==
..snip..

78,732 variations in total. Uh oh. I'm happy with the output, but whatever I use to go through these, it needs to be able to memoize or somehow reuse whatever progress it can from variant-to-variant, rather than starting over with each new string.

P.S.

A more-realistic number would be 6,561, since we know that the first 1 is good because it's part of the OpenSSL header, and because the letter O is visibly wider than zero.

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.