Bit Flip2(Cryptography)

task.py

from Cryptodome.Util.number import bytes_to_long, long_to_bytes
from Cryptodome.Cipher import AES
import hashlib
import os
import base64
from gmpy2 import is_prime
FLAG = open("flag").read()
FLAG += (16 - (len(FLAG) % 16))*" "
class Rng:
  def __init__(self, seed):
    self.seed = seed
    self.generated = b""
    self.num = 0
  def more_bytes(self):
    self.generated += hashlib.sha256(self.seed).digest()
    self.seed = long_to_bytes(bytes_to_long(self.seed) + 1, 32)
    self.num += 256
  def getbits(self, num=64):
    while (self.num < num):
      self.more_bytes()
    x = bytes_to_long(self.generated)
    self.num -= num
    self.generated = b""
    if self.num > 0:
      self.generated = long_to_bytes(x >> num, self.num // 8)
    return x & ((1 << num) - 1)
class DiffieHellman:
  def gen_prime(self):
    prime = self.rng.getbits(512)
    iter = 0
    while not is_prime(prime):
      iter += 1
      prime = self.rng.getbits(512)
    print("Generated after", iter, "iterations")
    return prime
  def __init__(self, seed, prime=None):
    self.rng = Rng(seed)
    if prime is None:
      prime = self.gen_prime()
    self.prime = prime
    self.my_secret = self.rng.getbits()
    self.my_number = pow(5, self.my_secret, prime)
    self.shared = 1337
  def set_other(self, x):
    self.shared ^= pow(x, self.my_secret, self.prime)
def pad32(x):
  return (b"\x00"*32+x)[-32:]
def xor32(a, b):
  return bytes(x^y for x, y in zip(pad32(a), pad32(b)))
def bit_flip(x):
  print("bit-flip str:")
  flip_str = base64.b64decode(input().strip())
  return xor32(flip_str, x)
alice_seed = os.urandom(16)
while 1:
  alice = DiffieHellman(bit_flip(alice_seed))
  bob = DiffieHellman(os.urandom(16), alice.prime)
  alice.set_other(bob.my_number)
  print("bob number", bob.my_number)
  bob.set_other(alice.my_number)
  iv = os.urandom(16)
  print(base64.b64encode(iv).decode())
  cipher = AES.new(long_to_bytes(alice.shared, 16)[:16], AES.MODE_CBC, IV=iv)
  enc_flag = cipher.encrypt(FLAG)
  print(base64.b64encode(enc_flag).decode())

 

풀이

1) Bit Flip2는 Bit Flip1과 동일한 task.py파일을 사용하지만, bob_number를 제공해주지 않는다.

2) Bit Flip1처럼 계산하려면 bob.secret이 필요하고, 이것을 얻기 위해 Bob의 16바이트를 추측해야 한다. 대신 alice_seed는 Bit Flip1과 동일하다.

3) bob.secret을 쉽게 얻기 위해서 alice_seed, alice.prime, alice.secret을 우리가 제어할 수 있어야한다.

4) 코드에 의하면 bob과 alice의 공유 가치는 pow(5, bob.secret*alice.secret, alice.prime)이다. 만약, 여기서 alice.prime을 0으로 설정한다면 alice_seed를 SHA(alice_seed) + SHA(alice_seed+1)가 소수가 되고 SHA(alice_seed + 2)의 상위 64비트가 0인 것으로 조작해야 한다.

5) 상위 64비트가 0이고 SHA256할 수 있는 값은 블록체인이 있다. 블록체인의 블록은 선행 0이 많이 있어서 어렵게 해야 하기 때문에 블록체인의 수십만 개의 해시가 모두 상위 64비트가 0인 것을 충족시킨다. 따라서 모든 블록체인의 비트 코인 해시를 가져와서 SHA(hash - 2) + SHA(hash - 1) 값이 소수인지 확인해야 한다. 

6) 해당되는 것을 찾으면 Bit Flip1에서처럼 alice_seed을 hash - 2로 뒤집는다. 상위 64비트가 0인 것으로 조작한 것을 통해 pow(5, bob.secret*alice.secret, alice.prime) = 1이라는 것을 알게 되었다.

7) 그러므로 task.py를 통해 공유 키는 1337^1 = 1336이라는 것을 구할 수 있으므로 최종적으로 AES키가 1336이라는 것을 구할 수 있다.
위에 있는 조건들을 사용해서 flag을 구하면 DrgnS{B1tc0in_p0w3r_crypt0_brut3}이 나온다.