CTF writeup: 0CTF/TCTF 2020's babyring makes RC4 run in circles. Reduce the ring check to XOR equations and let SageMath choose RSA inputs that close the loop.
The first part is obviously proof of work, in which we have to find 4 bytes XXXX such that
sha256(XXXX + 16-char-val) = sha256_hash for provided 16-char-val postfix and sha256_hash
Which is easy to solve
using permutations may not always work (in case of repeated characters), earlier I used combinations_with_replacement which had some weird issues which I could not debug
```python
from hashlib import sha256
import string
from itertools import permutations as take
CHARSET_SHA = string.printable[:62].encode() #0-9a-zA-Z as in challenge
def pow_sha(postfix, hash_val):
for prefix in take(CHARSET_SHA, 4):
prefix_bytes = bytes(prefix)
shaa = sha256(prefix_bytes+postfix).hexdigest()
if shaa == SHA_256_HASH:
return prefix_bytes
Now comes the main part of the challenge, in which we have to provide 64 `xi` values a message `msg` and a value `v`
The `msg` is sha256 hashed and first 16 bytes are taken to form the `key` for `ARC4`
The value `v` is XORed with last 64 bits of `pow(x[i], e, Ns[i])` and then `ARC4` encrypted. The goal is to produce the final value equal to the input `v`.
Since `ARC4` is simply a stream cipher, and encryption is just XORing the plaintext with a keystream, our final value `cur` is essentially `v^ys[0]^...ys[63]^xors[0]^xors[1]...^xors[63]`, where `ys[0..63]` are the last 64 bits of the respective `y[0..63]` and `xors[0]^xors[1]...^xors[63]` part is essentially dependent on `key` and an invariant for a given `key`, lets call it `invariant(key)` (bye bye `ARC4`).
All we need to do is to find `x[0..63]` such that `ys[0]^ys[1]...^ys[63] == invariant(key)` and we will have `cur==v` for all `v` as a consequence.
```python
from Crypto.Cipher import ARC4
from hashlib import sha256
from struct import pack, unpack
def encrypt_64(v,key,y):
E = ARC4.new(key)
cur = v
for i in range(64):
pt = (cur^y[i])%(1<<64)
ct = unpack('Q',E.encrypt(pack('Q',pt)))[0]
cur = ct
return cur
def invariant(key):
key_val = sha256(key).digest()[:16]
return encrypt_64(0,key_val,[0 for i in range(64)])
print(invariant(b'aaa'))
# 911494890333775973
One could simply put x[i] as some value such that ys[i] == invariant and all other xs == 0 but only if one could solve ANY of the RSA by factoring 4096 bit Ns, which is obviously not feasible!
Not knowing much linear algebra, I found this stackexchange post and this showing all that needs to be done is to have a set of 64 64-bit vectors, and we can represent any 64 bit value using xor of a subset of the vectors. Taking the corresponding ys for xs = 2 for all i, and solving the subset for given invariant, we will only set x[i] = 2 in the i in subset else x[i]=0 (to have no effect).
#Ns not shown here
last_64=[pow(2,e,i)%(1<<64)foriinNs]invariant=911494890333775973#for msg = b'aaa'
I=GF(2**64)last_64_mat=[list(map(int,bin(i)[2:].zfill(64)))foriinlast_64]mat=matrix(I,last_64_mat)invariant_vec=list(map(int,bin(invariant)[2:].zfill(64)))invariant_vec=matrix(I,invariant_vec)op=mat.solve_left(invariant_vec)print(op[0])
Awesome! we have
(0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1) as our output vector, we just have to return xi as 2*op and we are done ;)
Python
1
2
3
4
5
6
7
8
9
10
11
xs=(0,1,0,1,0,1,0,0,0,1,1,0,0,0,1,1,0,1,0,1,0,0,1,1,0,0,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1,1,0,0,0,1,0,0,0,1,1,1,1,1,1,0,1,0,0,1)xs=[2*iforiinxs]REM.recv()REM.send(b'aaa')#message
foriinrange(64):REM.send(str(xs[i]).encode())#xi's
REM.recv()REM.send(b'0')#v any v would do the job ;)
REM.recv()#flag{babbbcbdbebfbgbhbibjbkblbmbnbobpbqbrbsbtbubvbwbxby}