AlpacaHack Round6 Writeup

Cryptoは普段全くやらない and 解けないが挑戦した。
コンテストに解くことができた1問だけ。

XorshiftStream

ランダムな64bitの初期状態とFLAGと同じ長さのランダムbyte列の鍵を使って暗号化。
鍵+(鍵 XOR FLAG)のbyte列を内部状態と8bytesごとにXORしている。

• 問題ファイル

  import os
  import secrets
  from Crypto.Util.strxor import strxor
  
  class XorshiftStream:
      def __init__(self, key: int):
          self.state = key % 2**64
  
      def _next(self):
          self.state = (self.state ^ (self.state << 13)) % 2**64
          self.state = (self.state ^ (self.state >> 7)) % 2**64
          self.state = (self.state ^ (self.state << 17)) % 2**64
          return self.state
  
      def encrypt(self, data: bytes):
          ct = b""
          for i in range(0, len(data), 8):
              pt_block = data[i : i + 8]
              ct += (int.from_bytes(pt_block, "little") ^ self._next()).to_bytes(
                  8, "little"
              )[: len(pt_block)]
          return ct
  
  FLAG = os.environ.get("FLAG", "fakeflag").encode()
  
  xss = XorshiftStream(secrets.randbelow(2**64))
  key = secrets.token_bytes(len(FLAG))
  
  c = xss.encrypt(key.hex().encode() + strxor(key, FLAG))
  print(c.hex())

暗号化の際、鍵はhex().encode()されているので最終的な出力はFLAGの3倍の長さのbyte列であり、
前半2/3はhexエンコードした鍵の暗号文、後半1/3は鍵とflagをXORしたものの暗号文になっている。

鍵をhexエンコードした場合、平文は’0’~‘9’と’a’~‘f’の値にしかなり得ないので、
それを条件に64bitの初期状態を求めるz3ソルバを書いてみたら、初期状態が復元できたのでそれを元に鍵とFLAGも復元できる。

• ソルバ

  from z3 import *
  import struct 
  from Crypto.Util.strxor import strxor
  
  def update_state(n):
          n = (n ^ (n << 13)) % 2**64
          n = (n ^ (n >> 7)) % 2**64
          n = (n ^ (n << 17)) % 2**64
          return n
  
  enc = "142d35c86db4e4bb82ca5965ca1d6bd55c0ffeb35c8a5825f00819821cd775c4c091391f5eb5671b251f5722f1b47e539122f7e5eadc00eee8a6a631928a0c14c57c7e05b6575067c336090f85618c8e181eeddbb3c6e177ad0f9b16d23c777b313e62b877148f06014e8bf3bc156bf88eedd123ba513dfd6fcb32446e41a5b719412939f5b98ffd54c2b5e44f4f7a927ecaff337cddf19fa4e38cbe01162a1b54bb43b0678adf2801d893655a74c656779f9a807c3125b5a30f4800a8"
  len_key = (len(enc)//3)*2
  enc_key = enc[:len_key]
  enc_xored_flag = enc[len_key:]
  
  # calc init_state by z3
  a = BitVec('a',64)
  b = []
  for i in range(0,len(enc_key)//(8*2)):
          n = struct.unpack('<Q',bytes.fromhex(enc_key[i*(8*2):(i+1)*8*2]))[0]
          b.append(BitVecVal(n,64))
  
  s = Solver()
  for r in range(len(b)):
          t = a
          for _ in range(r+1):
                  t = (t ^ (t << 13))
                  t = (t ^ LShR(t,7))
                  t = (t ^ (t << 17))
          c = t^b[r]
          for i in range(8):
                  byte_i = Extract(8*(i+1)-1,8*i,c)
                  s.add(Or(And(byte_i >=0x30, byte_i <= 0x39),And(byte_i >= 0x61, byte_i <= 0x66)))
  
  init_state = 0
  if s.check() == sat:
          init_state = s.model()[a].as_long()
          print("[+] init_state: "+hex(init_state))
  else:
          print("no")
          exit(1)
  
  # decrypt
  state = init_state
  plain = b''
  len_plain = len(enc)//2
  for i in range(0,len(enc),8*2):
          state = update_state(state)
          t = bytes.fromhex(enc[i:i+8*2])
          if len(t) < 8:
                  t += b'\x00'*(8-len(t))
          block = struct.unpack('<Q',t)[0]
          plain += struct.pack('<Q',(block^state))
  
  plain = plain[:len_plain]
  key   = plain[:len_key//2]
  xored = plain[len_key//2:]
  key_raw = bytes.fromhex(key.decode())
  print(strxor(key_raw,xored))

感想

最近AlpacaHackやDreamHackなどの個人戦CTFプラットフォームをちまちまやっているが、
流石にCrypto出来なさすぎてCryptoHackも始めた。
easyくらいの問題は解けるように頑張る。