In Plain Sight

Description

problem description

Solution

The link send us to a page with a link to a zip file named 822926066.zip containing password protected flag file. As the description alludes the password is probably long and hard so tools like John will not help us solving this challenge.

The link to the zip is in a github project looking around we find under releases another file In_Plain_Sight.jar. Using java decompiler on that file we get the following code:

import java.util.Random;
import java.util.function.Supplier;
import net.lingala.zip4j.exception.ZipException;

public class Main {
  public static void main(String[] args) throws ZipException {
    int leftLimit = 48;
    int rightLimit = 122;
    int targetStringLength = 100;
    Random random = new Random();
    String generatedName = Integer.toString(random.nextInt());
    String generatedPassword = ((StringBuilder)random.ints(leftLimit, rightLimit + 1).filter(i -> ((i <= 57 || i >= 65) && (i <= 90 || i >= 97))).limit(targetStringLength).<StringBuilder>collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)).toString();
    System.out.println("Flag was packed to zip: " + generatedName + ".zip");
    System.out.println("Password is: " + generatedPassword);
    Zipper zipper = new Zipper(generatedPassword, generatedName);
    zipper.pack("flag.txt");
  }
}

It is not a coincidence that Java also have SecureRandom class. Looking at the source of java.util.Random we see the following code snippets:

public
class Random implements java.io.Serializable {
//...
    private static final long multiplier = 0x5DEECE66DL;
    private static final long addend = 0xBL;
    private static final long mask = (1L << 48) - 1;
//...
    protected int next(int bits) {
        long oldseed, nextseed;
        AtomicLong seed = this.seed;
        do {
            oldseed = seed.get();
            nextseed = (oldseed * multiplier + addend) & mask;
        } while (!seed.compareAndSet(oldseed, nextseed));
        return (int)(nextseed >>> (48 - bits));
    }
//...
    final int internalNextInt(int origin, int bound) {
        if (origin < bound) {
            int n = bound - origin;
            if (n > 0) {
                return nextInt(n) + origin;
            }
            else {  // range not representable as int
                int r;
                do {
                    r = nextInt();
                } while (r < origin || r >= bound);
                return r;
            }
        }
        else {
            return nextInt();
        }
    }
//...
    public int nextInt() {
        return next(32);
    }
//...
    public int nextInt(int bound) {
        if (bound <= 0)
            throw new IllegalArgumentException(BadBound);

        int r = next(31);
        int m = bound - 1;
        if ((bound & m) == 0)  // i.e., bound is a power of 2
            r = (int)((bound * (long)r) >> 31);
        else {
            for (int u = r;
                 u - (r = u % bound) + m < 0;
                 u = next(31))
                ;
        }
        return r;
    }
//...
    public IntStream ints(int randomNumberOrigin, int randomNumberBound) {
        if (randomNumberOrigin >= randomNumberBound)
            throw new IllegalArgumentException(BadRange);
        return StreamSupport.intStream
                (new RandomIntsSpliterator
                         (this, 0L, Long.MAX_VALUE, randomNumberOrigin, randomNumberBound),
                 false);
    }
//...
   static final class RandomIntsSpliterator implements Spliterator.OfInt {
        final Random rng;
        long index;
        final long fence;
        final int origin;
        final int bound;
        RandomIntsSpliterator(Random rng, long index, long fence,
                              int origin, int bound) {
            this.rng = rng; this.index = index; this.fence = fence;
            this.origin = origin; this.bound = bound;
        }
//..
        public boolean tryAdvance(IntConsumer consumer) {
            if (consumer == null) throw new NullPointerException();
            long i = index, f = fence;
            if (i < f) {
                consumer.accept(rng.internalNextInt(origin, bound));
                index = i + 1;
                return true;
            }
            return false;
        }
//..
   }

First note that in next method the returned Integer is leaking (48-bits)-bits from the internal state. Which implies that the zip file name is the 32-bit high bits of the state so we only need to brute-force/exhustively-search the lower 16-bits which is doable.

What remains is to implemenet all internal details of the Random needed to emulate the password generation which uses the Random.ints method. The following python code does that exactly:

from pyzipper import AESZipFile
from struct import pack, unpack
from itertools import filterfalse, islice

multiplier = 0x5DEECE66D
addend = 0xB
mask = (1 << 48) - 1

def long2int(l):
    return unpack("<i", pack("<q", l)[:4])[0]

def Next(seed, bits):
    new = (seed * multiplier + addend) & mask
    return new, long2int(new >> (48 - bits))

def nextInt(seed, bound):
    assert bound > 0
    seed, r = Next(seed, 31)
    m = bound - 1
    if bound & m == 0:
        return seed, long2int((bound*r) >> 31)
    u = r
    while True:
        u, r = r, u % bound
        if u - r + m >= 0:
            return seed, r
        seed, u = Next(seed, 31)

def internalNextInt(seed, origin, bound):
    if (origin < bound):
        n = bound - origin
        if (n > 0):
            seed, r = nextInt(seed, n)
            return seed, r + origin
        while True:
            seed, r = Next(seed, 32)
            if origin <= r < bound:
                return seed, r
    return Next(seed, 32)

def ints(seed, origin, bound):
    while True:
        seed, r = internalNextInt(seed, origin, bound)
        yield r

def genpass(seed):
    return ''.join(map(chr, islice(filterfalse(lambda i: not ((i <= 57 or i >= 65) and (i <= 90 or i >= 97)), ints(seed, 48, 123)), 0, 100))).encode()

leak = 822926066

with AESZipFile('822926066.zip') as f:
    for seed in range(leak<<16, (leak <<16) + (1<<16)):
        try:
            f.pwd = genpass(seed)
            content = f.read('flag.txt')
            print(content)
            break
        except RuntimeError:
            pass
# Output: b'BSidesTLV2021{ProblemWithRandomnessYouCanNeverBeSure}'

The flag is BSidesTLV2021{ProblemWithRandomnessYouCanNeverBeSure}.