[TWCTF 2019] Simple Logic

require 'securerandom'
require 'openssl'

ROUNDS = 765
BITS = 128
PAIRS = 6

def encrypt(msg, key)
    enc = msg
    mask = (1 << BITS) - 1
    ROUNDS.times do
        enc = (enc + key) & mask
        enc = enc ^ key
    end
    enc
end

def decrypt(msg, key)
    enc = msg
    mask = (1 << BITS) - 1
    ROUNDS.times do
        enc = enc ^ key
        enc = (enc - key) & mask
    end
    enc
end

fail unless BITS % 8 == 0

flag = SecureRandom.bytes(BITS / 8).unpack1('H*').to_i(16)
key = SecureRandom.bytes(BITS / 8).unpack1('H*').to_i(16)

STDERR.puts "The flag: TWCTF{%x}" % flag
STDERR.puts "Key=%x" % key
STDOUT.puts "Encrypted flag: %x" % encrypt(flag, key)
fail unless decrypt(encrypt(flag, key), key) == flag # Decryption Check

PAIRS.times do |i|
    plain = SecureRandom.bytes(BITS / 8).unpack1('H*').to_i(16)
    enc = encrypt(plain, key)
    STDOUT.puts "Pair %d: plain=%x enc=%x" % [-~i, plain, enc]
end

In XOR / Addition / Subtraction is the operation which MSB does not effect on LSB. So you can recover the key begin to LSB.

from Crypto.Util.number import *
import random
plain = [0x29abc13947b5373b86a1dc1d423807a, 0xeeb83b72d3336a80a853bf9c61d6f254, 0x7a0e5ffc7208f978b81475201fbeb3a0, 0xc464714f5cdce458f32608f8b5e2002e, 0xf944aaccf6779a65e8ba74795da3c41d, 0x552682756304d662fa18e624b09b2ac5]
enc   = [0xb36b6b62a7e685bd1158744662c5d04a, 0x614d86b5b6653cdc8f33368c41e99254, 0x292a7ff7f12b4e21db00e593246be5a0, 0x64f930da37d494c634fa22a609342ffe, 0xaa3825e62d053fb0eb8e7e2621dabfe7, 0xf2ffdf4beb933681844c70190ecf60bf]

ROUND = 765
BITS = 128
PAIRS = 6

def encrypt(msg, key, idx):
 mask = (1 << (idx+1)) - 1
 msg = msg & mask
 key = key & mask
 enc = msg
 for _ in range(ROUND):
   enc = (enc + key) & mask
   enc = enc ^ key
 return enc

# recover key
def solve1(idx, cur):
 if idx == 128: print("idx 128 ", cur)
 mask = (1 << (idx+1)) - 1
 # 0
 isPossible = True
 for i in range(PAIRS):
   if encrypt(plain[i], cur, idx) != (enc[i] & mask): isPossible = False
 if isPossible: solve1(idx+1,cur)

   #1
 isPossible = True
 for i in range(PAIRS):
   if encrypt(plain[i], cur | (1<<idx), idx) != (enc[i] & mask): isPossible = False
 if isPossible: solve1(idx+1,cur | (1<<idx))


def decrypt(msg, key):
 enc = msg
 mask = (1<<BITS)-1
 for _ in range(ROUND):
   enc = enc ^ key
   enc = (enc - key) & mask
 return enc

solve1(0, 0)
key1 = 62900030173734087782946667685685220617
key2 = 233041213634203319514633971401569326345
for i in range(PAIRS):
 print(encrypt(plain[i],key1,127)==enc[i])
for i in range(PAIRS):
 print(encrypt(plain[i],key2,127)==enc[i])

enc_flag = 0x43713622de24d04b9c05395bb753d437
print(decrypt(enc_flag, key1))
print('TWCTF{'+hex(decrypt(enc_flag, key2))[2:]+'}')
#flag = 231142985373074826777991337363961431661
#print(encrypt(flag, key1, 127) == enc_flag)
#a1 = 0x2347823948723874289
#a2 = 0x2873482738724786821

#enc = encrypt(a1,a2,127)

#print(a1 == decrypt(enc,a2))