‹ Back to blog

Ice Cream Generator

The handout is more than two hundred lines of ice-cream ordering machinery. I opened it, decided it was far above my level, and dropped it. When I came back later, the terrifying part turned out to be an LCG wearing a paper hat.

The generator behind the shop

The service creates an LCG with a random multiplier a, random increment b, modulus p and fixed seed 1337.

class lcg:
    def __init__(self, p):
        while (a := bytes_to_long(urandom(16))) > p:
            pass
        while (b := bytes_to_long(urandom(16))) > p:
            pass
        self.a, self.b, self.p = a, b, p
        seed = 1337

    def gen_next(self):
        self.seed = (self.a * self.seed + self.b) % self.p
        return self.seed

An LCG generates values using the recurrence:

X[n+1] = a·X[n] + c mod p

X0 is the seed, a is the multiplier, c is the increment and every value is reduced modulo p. If three consecutive outputs are known, subtracting two recurrence equations removes c:

X2 = a·X1 + c mod p
X3 = a·X2 + c mod p

X3 - X2 = a·(X2 - X1) mod p
a = (X3 - X2) / (X2 - X1) mod p
c = X2 - a·X1 mod p

In this challenge p and the seed can be leaked, so recovering a and c is enough to reproduce every later value.

Where the random values go

The order object advances the generator 1337 times and discards those outputs. It then generates 1338 more values as the flavor list. Customers may use indices 1 through 6, while index 1337 is kept private.

for _ in range(1337):
    self.inner_lcg.gen_next()

self.flavors = [
    self.inner_lcg.gen_next()
    for _ in range(1338)
]

self.flavor_map = {
    i: self.flavors[i]
    for i in [1, 2, 3, 4, 5, 6]
}

self.private = {
    i: self.flavors[i]
    for i in [1, 2, 3, 4, 5, 6, 1337]
}

The shop has three bowls. add puts a public flavor value into a bowl, while combine can add, subtract, multiply or divide one bowl by another modulo p. The second bowl in every combination is cleared afterwards.

if op == 'add':
    bowls[a] += bowls[b]
elif op == 'sub':
    bowls[a] -= bowls[b]
elif op == 'mult':
    bowls[a] *= bowls[b]
elif op == 'div':
    bowls[a] *= pow(bowls[b], -1, p)

bowls[b] = 0
bowls = [value % p for value in bowls]

finish bowl prints the user number p, the recipe and a signature equal to the sum of the three bowls modulo p. It requires at least three distinct unused flavors. Once a flavor contributed to a finished bowl, its use counter becomes 1337 and it no longer counts toward uniqueness in later bowls.

signature = sum(self.bowls) % self.p

print(f"User #: {self.p}")
print(f"Recipe: {recipe}")
print(f"Signature: {signature}")

The redemption function replays an arbitrary recipe using the private map. It gives the flag when the submitted signature equals private[1337].

if sum(bowls) % self.p == signature:
    print("You have successfully redeemed your lce cream!")
    if signature == self.private[1337]:
        print(flag)

The first idea that does not work

A normal LCG attack would request individual outputs and solve for the parameters. Here the interface only prints a sum after at least three distinct flavors have been used. A plain bowl containing X1 + X2 + X3 does not give enough information to separate the outputs.

The important realization is that bowls are not limited to sums. Modular subtraction and division let the shop itself evaluate the formulas for a and c before printing the signature.

Making the bowls solve the LCG

Let the six public flavors be consecutive outputs X1 ... X6. To recover a, I used the first three flavors and arranged the bowls as follows:

  1. Add X2 to bowl 1 and X3 to bowl 2.
  2. Subtract bowl 2 from bowl 1, leaving X2-X3.
  3. Add X1 to bowl 2 and another X2 to bowl 3.
  4. Subtract bowl 3 from bowl 2, leaving X1-X2.
  5. Divide bowl 1 by bowl 2.
bowl1 = (X2 - X3) / (X1 - X2) mod p
      = a

Both numerator and denominator use the opposite signs from the common formula, so the negatives cancel. Three distinct flavors were used, satisfying the uniqueness check. Finishing the bowl prints both p and a.

The first three flavors no longer count as unique, so the next finished bowl has to use X4, X5 and X6. Repeating the same difference-and-division construction gives the multiplier again:

(X5 - X6) / (X4 - X5) mod p = a

From there the recurrence gives c = X5 - a·X4 mod p. The bowls can evaluate that expression too:

  1. Leave the recovered a in bowl 1.
  2. Add X4 to bowl 2 and multiply bowl 2 by bowl 1, producing a·X4.
  3. Add X5 to bowl 1.
  4. Subtract bowl 2 from bowl 1, producing X5-a·X4 = c.

Finishing this bowl prints c as the second signature.

Reproducing the private flavor

Now all LCG parameters are known. I implemented the same generator locally, advanced it through the discarded values and rebuilt the complete flavor list.

class LCG:
    def __init__(self, a, c, p):
        self.a = a
        self.c = c
        self.p = p
        self.seed = 1337

    def gen_next(self):
        self.seed = (self.a * self.seed + self.c) % self.p
        return self.seed

lcg = LCG(a, c, p)

for _ in range(1337):
    lcg.gen_next()

flavors = [lcg.gen_next() for _ in range(1338)]
target_signature = flavors[1337]

The final bug is in recipe validation. The ordering menu exposes only flavors 1 through 6, but verify() accepts any recipe whose characters pass a small allowlist. The index 1337 is valid in private and every digit it needs is allowed.

A recipe containing [[1337,0]] puts the private flavor directly into bowl 1 during verification. Submitting the locally generated value as the signature makes both the normal signature check and the special flag comparison pass.

recipe    = [[1337,0]]
signature = flavors[1337]

The complete exploit automates the menu interactions with pwntools: create an order, perform the bowl operations for a, finish it, repeat with the remaining flavors for c, simulate the LCG and redeem the private recipe.

io.sendline(b"3")
io.sendline(str(p).encode())
io.sendline(b"[[1337,0]]")
io.sendline(str(target_signature).encode())

Flag:

amateursCTF{bruh_why_would_you_use_lcg_for_signature}

There is a lot of menu code between us and the flag, but the shop happily does modular division on hidden PRNG outputs and prints the answer. Once I noticed that, the ice cream stopped being intimidating.