[2021 PBCTF] Steroid Stream

$\textsf{fake[LEN-LEN//3:LEN]} = 0$. Therefore $\textsf{key[LEN-LEN//3:LEN]}$ can be recovered(Index is ignored).

 

For $\textsf{fake[i]} \text{  for  } i < \textsf{LEN-LEN//3}$, those value is linear combination of $\textsf{key[i+1:LEN]}$. It is enough to check whether which remaining value is a linear combination of $\textsf{key[i+1:LEN]}$.

 

There might be a false positive, so I was planning to bruteforce last four or five recovered keybits but fortunately there was no false positive.

 

def keygen(ln):
    # Generate a linearly independent key
    arr = [ 1 << i for i in range(ln) ]

    for i in range(ln):
        for j in range(i):
            if random.getrandbits(1):
                arr[j] ^= arr[i]
    for i in range(ln):
        for j in range(i):
            if random.getrandbits(1):
                arr[ln - 1 - j] ^= arr[ln - 1 - i]

    return arr

def gen_keystream(key):
    ln = len(key)
    assert ln > 50
    
    # Generate some fake values based on the given key...
    fake = [0] * ln
    for i in range(ln - ln // 3):
        arr = list(range(i + 1, ln))
        random.shuffle(arr)
        for j in arr[:ln // 3]:
            fake[i] ^= key[j]

    # Generate the keystream
    res = []
    for i in range(ln):
        t = random.getrandbits(1)
        if t:
            res.append((t, [fake[i], key[i]]))
        else:
            res.append((t, [key[i], fake[i]]))

    # Shuffle!
    random.shuffle(res)

    keystream = [v[0] for v in res]
    public = [v[1] for v in res]
    return keystream, public

def xor(a, b):
    return [x ^ y for x, y in zip(a, b)]

def recover_keystream(key, public):
    st = set(key)
    keystream = []
    for v0, v1 in public:
        if v0 in st:
            keystream.append(0)
        elif v1 in st:
            keystream.append(1)
        else:
            assert False, "Failed to recover the keystream"
    return keystream

def bytes_to_bits(inp):
    res = []
    for v in inp:
        res.extend(list(map(int, format(v, '08b'))))
    return res

def bits_to_bytes(inp):
    res = []
    for i in range(0, len(inp), 8):
        res.append(int(''.join(map(str, inp[i:i+8])), 2))
    return bytes(res)

def rank_check(basis, t, LEN):
    for i in range(LEN-1,-1,-1):
        if t & (1<<i):
            if basis[i] == 0:
                return False
            t ^= basis[i]
    return t == 0

def add_basis(basis,t,LEN):
    for j in range(LEN-1, -1, -1):
        if t & (1 << j):
            if basis[j] == 0:
                basis[j] = t
                return None
            else:
                t ^= basis[j]

def solve():
    f = open('output.txt')
    enc = int(f.readline(), 16)
    pub = eval(f.readline()) # len 616
    LEN = len(pub)
    keystream = [0]*LEN
    vis = [0]*LEN
    basis = [0]*LEN


    ############# BASIS
    for i in range(LEN):
        if pub[i][0] == 0:
            vis[i] = True
            keystream[i] = 1
            add_basis(basis,pub[i][1],LEN)

        if pub[i][1] == 0:
            vis[i] = True
            keystream[i] = 0
            add_basis(basis,pub[i][0],LEN)
    
    for cur in range(LEN//3, LEN):        
        for i in range(LEN):
            if vis[i]: continue
            if rank_check(basis, pub[i][0], LEN):
                vis[i] = True
                add_basis(basis, pub[i][1], LEN)
                keystream[i] = 1
                print("now ", cur, "keystream", i, keystream[i])
                break
            
            if rank_check(basis, pub[i][1], LEN):
                vis[i] = True
                add_basis(basis, pub[i][0], LEN)
                print("now ", cur, "keystream", i, keystream[i])
                break
        else:
            print("!!!!!",i)
            return None
    print(keystream)
    z = 0
    for i in range(LEN):
        if keystream[i]: z ^= (1<<(LEN-1-i))

    print(long_to_bytes(z^enc))

solve()

'CTF > Crypto' 카테고리의 다른 글

[2021 PBCTF] Steroid Stream  (2) 2021.10.11
[2021 PBCTF] Alkaloid Stream  (2) 2021.10.11
[2019 X-MAS CTF] Santa Knows Crypto  (0) 2019.12.14
[2019 X-MAS CTF] Hashed Presents  (0) 2019.12.14
[2019 X-MAS CTF] DeFUNct Ransomware  (0) 2019.12.14
[HITCON CTF 2019 Quals] Very Simple Haskell  (0) 2019.10.14
[HITCON CTF 2019 Quals] Lost Modulus Again  (2) 2019.10.14
  Comments
  • 코테준비
    안녕하세요!!
    현직 개발자 신입입니다..
    요즘 개발을하면서 알고리즘에 부딪히기도 많이하고
    회사를 좀더 좋은곳으로 옮겨야겠다는 마음을 자꾸가지게 되더라구요 ㅠㅠ
    그래서 회사와 병행으로 코테를 준비하려고합니다..

    근데 저는 전공자인데 언어는 JAVA가 주력언어라 현재 개발직군이 spring쪽이라서
    그래서 보조언어로 코테를 풀때 파이썬을 선택하려는데 괜찮을까요?
    글을 읽어보니 C++이 장점이 많더라구요
    근데 제가 대학시절에 C++이 너무 재미가 없어서 공부도 안했긴했는데
    물론 파이썬은 조금 기억은나는데 이 상황에서는 C++을 새로잡는게 나을까요?

    엄청 높은 기업을 들어가려는것은 아닙니다..
    중견 강소 정도의 코테 준비를 목표로하고 있습니다.

    조언해주시면 감사하겠습니다!!
    • 확실히 C++이 PS보다 자바보다 좋은건 맞는데 그 이점과 현 상황에서 C++를 새로 익히는 비용을 잘 저울질해서 선택하시면 될 것 같습니다.

      개인적으로는 지금 댓글주신 상황이라면 자바 언어에 훨씬 친숙할테니 굳이 C++를 새로 익히기 보다는 자바로 진행해도 괜찮을 것 같습니다.
댓글 쓰기