[Original Writeup](https://github.com/schrislambert/personal_writeups/tree/master/bamboofox2019/oilcircuitbreaker)
# Oil Circuit Breaker
I figured I'd start doing CTF challenge writeups in 2020, so last night intothis morning I checked out BambooFoxCTF since someone on my team mentioned it a day back,looking for something I could solve and writeup.  Luckily, there was a symmetric cryptochallenge that seemed interesting, so I spent about 6-7 hours doing it.  Symmetric cryptois pretty rare, so this challenge being an interesting symmetric crypto was a nice surprise.It ended with 5 solves (not including me since I solved it after the competition ended),making it the second highest point value on the competition after a pwn chal.
## Beginning
The challenge presents you with two files, `ocb.py` and `server.py`: `ocb.py` implementsthe symmetric mode-of-operation we're going to be breaking, and `server.py` sets the rulesfor how we break it.  `server.py` is pretty straight forward: one connection = one key, 2 encryptions (must usedifference nonces), 1 decryption, and then we have to create a ciphertext/nonce/tag triothat authenticated decrypts to `giveme flag.txt`.  The obstacle is that we are not allowedto encrypt anything that contains `giveme flag.txt`.
`ocb.py` is much more interesting, it implements a (very useful) Block class whichcontains a fair amount of utility with working with blocks that will be passed to/fromblock ciphers, as well as an OCB class which implements [OCB](https://web.cs.ucdavis.edu/~rogaway/ocb/ocb-back.htm) over AES-128 (albiet with someissues---I'm not sure what differences there are because I'm too lazy to check, but the testvectors didn't work).  The important part is as follows
```pythonclass OCB:    def __init__(self, key):        self.aes = AES.new(key, AES.MODE_ECB)    def e(self, x):        y = Block(self.aes.encrypt(x.data))        return y    def d(self, y):        x = Block(self.aes.decrypt(y.data))        return x    @bytes_block_bytes    def encrypt(self, N, M):        L = self.e(N)
        C = Block()        S = Block.zero()        for i in range(M.blocksize()):            L = L.double()            if i == M.blocksize() - 1:                pad = self.e(Block.len(M[i].size()) ^ L)                C |= pad.msb(M[i].size()) ^ M[i]                S ^= pad ^ (C[i] | Block.zero(BLOCKSIZE - M[i].size()))            else:                C |= self.e(M[i] ^ L) ^ L                S ^= M[i]
        L = L.double() ^ L        T = self.e(S ^ L)
        return C, T
    @bytes_block_bytes    def decrypt(self, N, C, T):        L = self.e(N)
        M = Block()        S = Block.zero()        for i in range(C.blocksize()):            L = L.double()            if i == C.blocksize() - 1:                pad = self.e(Block.len(C[i].size()) ^ L)                M |= pad.msb(C[i].size()) ^ C[i]                S ^= pad ^ (C[i] | Block.zero(BLOCKSIZE - C[i].size()))            else:                M |= self.d(C[i] ^ L) ^ L                S ^= M[i]
        L = L.double() ^ L        if T == self.e(S ^ L):            return True, M        else:            return False, None```
`L.double()` is a method that is equivalent to multiplying by `x` over a 128-bitboolean polynomial mod ring.  That's not important other than it's reversible, andI implemented the inverse in the Block class, which I'll paste here
```pythonBLOCKSIZE = 16
class Block:    def __init__(self, data = b''):        self.data = data
    @classmethod    def fromhex(cls, hx):        return cls(unhexlify(hx))
    @classmethod    def random(cls, size):        return cls(urandom(size))
    @classmethod    def len(cls, n):        return cls(int(n * 8).to_bytes(BLOCKSIZE, 'big'))
    @classmethod    def zero(cls, size = BLOCKSIZE):        return cls(int(0).to_bytes(size, 'big'))
    def double(self):        assert(len(self.data) == BLOCKSIZE)        x = int.from_bytes(self.data, 'big')        n = BLOCKSIZE * 8        mask = (1 << n) - 1        if x & (1 << (n - 1)):            x = ((x << 1) & mask) ^ 0b10000111        else:            x = (x << 1) & mask        return Block(x.to_bytes(BLOCKSIZE, 'big'))
    # mine    def half(self):        assert(len(self.data) == BLOCKSIZE)        x = int.from_bytes(self.data, 'big')        n = BLOCKSIZE * 8        mask = (1 << n) - 1        if x & 1:            x = ((x ^ 0b10000111) >> 1) | (1 << (n - 1))        else:            x = x >> 1        return Block(x.to_bytes(BLOCKSIZE, 'big'))
    def hex(self):        return self.data.hex()
    def size(self):        return len(self.data)
    def blocksize(self):        return len(self.data) // BLOCKSIZE + (len(self.data) % BLOCKSIZE > 0)
    def msb(self, n):        return Block(self.data[:n])
    # mine    def lsb(self, n):        return Block(self.data[-n:])    def __or__(self, other):        return Block(self.data + other.data)
    def __xor__(self, other):        assert(len(self.data) == len(other.data))        return Block(bytes([x ^ y for x, y in zip(self.data, other.data)]))
    def __eq__(self, other):        return self.data == other.data```
## Solving
The important qualities to note are that the last block of the plaintextis only xored with the ciphertext (the pad is determined by an encryption ofthe length of the last block and the L parameter --- in turn determined by thenonce and the amount of blocks).  The tag is just an encryption of the Lparameter xor the xor of all the plaintexts.  Therefore, in order to get the15-length target plaintext, we must have the cipher and the tag which are```pythongoal = Block(b"giveme flag.txt")# cipher = e(Block.len(15) ^ L_2).msb(15) ^ goal# tag = e(goal | e(Block.len(15) ^ L_2).lsb(1))# My notation for L is that L_1 = e(Nonce), L_n.double() = L_(n+1), and# L_(n+1).half() = L_n```
So after a lot of thinking about this, I became fairly set on one idea:1. Use the first encryption to get the pad and setup for figuring out L2. Use the decryption (same nonce) to find L3. Use the second encryption (different known nonce) to get the tag.
For the first encryption, we know that we want the first block to be`Block.len(15)` so we can figure out the pad once we know L.  Everythingelse we're going to ignore for the time being since the decryption controlswhat we want to encrypt here.
The decryption is much more tricky.  In order to get information from the decryption,we need to know the tag in advance, so we have to construct something that makesthe tag something we know from encryption.
Things we need in the decrypted plaintext to make decryption work:1. Block.len(15) so we know the pad2. Block.len(15) again so they xor out to make the tag easier3. Some L parameter so we know L.4. Something to make the tag work.
The first two of these are straightforward, we just make the the first two blocksof the plaintext we encrypt `Block.len(15)` and then also make those the firsttwo blocks of the decryption.
For the next, we're going to be more creative.  Let's use 4 blocks since that'sthe amount of things we need and I also know it works in hindsight.  Then, wehave the tag in the decryption is equal to `e(L_5 ^ L_6 ^ S)` where S is the xorof all the plaintext blocks.  Since `M[0] = M[1] = Block.len(15)` from before,this gives us `tag = e(L_5 ^ L_6 ^ M[2] ^ M[3]`.  Remember, we want one of the Mblocks to be some L value, so wouldn't it be nice if we could get it to beeither `L_5` or `L_6` so stuff would cancel out?
Let's try to get `L_5`.  How would we do this?  Well, the last block of the encryptionis weird, so let's look at that.  We have `M[3] = C[3] ^ e(Block.len(C[3]) ^ L_5)`.  Asa side note, there's no point in making `M[3]` less than the full block size sinceit just loses us control/information (and we want `M[3] = L_5`, remember), so withthat we get `M[3] = L_5 = C[3] ^ e(Block.len(16) ^ L_5)`.  Wait.  So`C[3] = L_5 ^ e(Block.len(16) ^ L_5)` helps us a ton.  This value is the exact patternwe get from encryption of a normal block of value `Block.len(16)`, specifically the4th block.  Since this needs to be a normal block, say we have 5 blocks in the payloadwe're encrypting, with the 4th block being `Block.len(16)`.  This is doable.
Cool, so now we have `M[3] = L_5` and we're basically done.
| Block | Thing to Encrypt | Encrypts to                    | Thing to Decrypt | Decrypts to                                                      | XOR of Decrypteds    ||-------|------------------|--------------------------------|------------------|------------------------------------------------------------------|----------------------|| 0     | Block.len(15)    | C[0]                           | C[0]             | Block.len(15)                                                    | Block.len(15)        || 1     | Block.len(15)    | C[1]                           | C[1]             | Block.len(15)                                                    | Block.zero()         || 2     | Block.len(16)    | C[2]                           | C[2]             | Block.len(16)                                                    | Block.len(16)        || 3     | Block.len(16)    | C[3]                           | C[3]             |  e(Block.len(16) ^ L\_5) ^ e(Block.len(16) ^ L\_5) ^ L\_5 = L_\5 | Block.len(16) ^ L\_5 || 4     | Block.zero()     | C[4] = e(Block.len(16) ^ L\_6) |                  |                                                                  |                      || TAG   |                  | Garbage                        | C[4]             | e(Block.len(16) ^ L\_6)                                          |                      |
Just get `L_1 = L_5.half().half().half().half()`.
With our final encryption, we just reconstruct the pad as `C[0] ^ L_1.double()`, which we willxor with the goal to get our ciphertext for the win.  We just need to get`e((goal | pad.lsb(1)) ^ L_2 ^ L_3)`.  Get a new nonce/L by knowing that`e(Block.len(16) ^ L_6) = cipher[4]`.  So our `newnonce = Block.len(16) ^ L_5.double()` and`nL = cipher[4]`.  Finally, we get the encryption we want by sending`(goal | pad.lsb(1)) ^ L_2 ^ L_3 ^ nL_2` as the first block of the payload sothe first block of the cipher will be `e((goal | pad.lsb(1)) ^ L_2 ^ L_3 ^ nL_2 ^ nL_2) ^ nL_2`which we then xor with `nL.double()` to get the tag we want.
Just send the original nonce, the ciphertext and the tag we just made to the execute functionon the server for the flag.  Finally.
`BAMBOOFOX{IThOUgHtitWAspRoVaBles3cuRE}`
The attached source files with a lot of the comments I used to track what I wasdoing as I figured this out are in this directory as well.
