VSS

This was a crypto challenge at N1CTF 2020, solved by 38 teams.

We are given a script, vss.py and an image, share2.png.

Analysis of the problem

The script implements a (2,2) Visual Secret Sharing Scheme. The shared image is a QRcode encoding the flag.

One can notice that share2.png is a 888x888 image, meaning that the original image is 444x444 (each original pixels is encoded in 4 new pixels in each share) By generating another 444x444 QRcode , we can notice that there is a quite a lot of white space on each side of the QRcode.

A random 444x444 Qrcode

The implementation of the scheme uses Python's random module, which is not a Cryptographically Secure PRNG. This module uses the MT19937 PRNG under the hood, which is known to be cloneable with at least 32 * 624 bits of output (the size of its internal state).

Python's getrandbits

Lets take a look at how getrandbits works. In the script, the color of the share's pixels depends on the flipped_coins variable, which is initialised as follows :

flipped_coins = [int(bit) for bit in bin(random.getrandbits(m*n))[2:].zfill(m*n)]

We know that MT19937 is using 32 bits values in its internal state. When getranbits is called with a value greater than 32, say 64 for example, it will get two dwords from its states, and prepend the second one to the MSBs of the first one. One can verify this using the following scripts:

import random

state = random.getstate()

a = random.getrandbits(32)
b = random.getrandbits(32)

random.setstate(state) # reset the module
c = random.getrandbits(64)

print("MSB: ", c == (b << 32) | a)

which yields

MSB: True

That means that if we want to recover the whole flipped_coins array, we will need to know its lasts 32 * 624 bits , and not its 32*624 firsts, as one would expect (yes i struggled on this :P).

We can count how many pixels of known color (white) we have at the bottom, before the qrcode starts.

from PIL import Image
import qrcode

content = "here is whats a great long long fake flag"

qr = qrcode.QRCode(
        version=1,
        error_correction=qrcode.constants.ERROR_CORRECT_L,
        box_size=12,
        border=4,
    )
qr.add_data(content)
qr.make(fit=True)

img = qr.make_image(fill_color="black", back_color="white")
img.save('myqr.png')

img = Image.open("myqr.png")
pixs = img.load()

m,n = img.size

assert(n == m == 444)

for i in range(m - 1, 0, -1): # Counting at the bottom of the image
    for j in range(n):
        if pixs[j,i] == 0:
            first_black_offset = i * n + j

            known_white = m*n - first_black_offset
            print("Number of bits known: {}".format(known_white))
            exit()

This yields Number of bits known: 21708, which is greater than 32*624 = 19968.

Its enough for us to be able to clone and predict the output of the random's module for the rest of the image.

Putting it all together

I didn't bother to reimplement the cloning stuff, I've used the MT19937-Predictor library to do so. If you are not familliar with MT19937 cloning, i recommend you to check this cryptopals challenge (or search for the technique on the net , its well known and there are plenty of articles on the subject).

Here is the implementation of the above attack :

from PIL import Image
import qrcode  # https://github.com/lincolnloop/python-qrcode
import random

from mt19937predictor import MT19937Predictor

img = Image.open("share2.png")
pixs = img.load()

bits = ""
m,n = img.size

# Retrieve the whole bit string
for i in range(m//2):
    for j in range(n//2):
        p1 = pixs[2*j, 2*i]

        # we assume that the pixels are all white (which is true for the lasts lines at the bottom)
        # so p1 is color0, which is set to 0 if flipped_coins[idx] is True.
        if p1 == 0:
            bits += "1"
        else:
            bits += "0"

predictor = MT19937Predictor()

# Feed the last 32*624 bits to the predictor, which is now able to clone the generator
predictor.setrandbits(int(bits[-32*624:], 2), 32*624)

# Recreate the upper part of flipped coins, ie the m*n values minus the 32*624 we already know
upper = [int(bit) for bit in bin(predictor.getrandbits((m//2) * (n//2) - 32 * 624))[2:].zfill((m//2)*(n//2) - 32*624)]

# Combine the two
flipped_coins =  upper + [int(bit) for bit in bits[-32*624:]]

out = Image.new("L", (m//2, n//2))
for i in range(m//2):
    for j in range(n//2):

        p1 = pixs[2*j, 2*i]
        idx = i * n//2 + j
        if (flipped_coins[idx] == 1 and p1 == 0) or (flipped_coins[idx] == 0 and p1 == 255):
            col = 255
        else:
            col = 0

        out.putpixel((j,i), col)

out.save("flag.png")

Executing it, we get the following QRcode:

which decodes to n1ctf{bf3724e3-c26b-4a63-9b4f-b33024b1db63}