Gorpkornyy Institut — alfactf

Description

Горпкорный институт

The service accepted a YAML certificate and verified it server-side before granting admission. The goal was to submit a certificate for passport 1337676769 that parsed as all 5s while still matching the one stored signature.

Analysis

The challenge combined a web submission endpoint with a weak homemade signature scheme.

The important source-level details were:

• Go unmarshaled attacker-controlled YAML with gopkg.in/yaml.v3 v3.0.1 into:

type Attestat struct {
    Passport string         `yaml:"паспорт"`
    Grades   map[string]int `yaml:"оценки"`
}

• The service knew a valid signature only for one fixed YAML blob, originalAttestat, under passport 1337676769.
• The request handler normalized \r\n to \n, unmarshaled the submitted bytes with yaml.Unmarshal, and then hashed the exact normalized byte string.
• The signature was not a real MAC. It was a plain polynomial hash over bytes with base 256 modulo

p = 2^56 - 5

The original signed document was:

# Подтвержденный аттестат
паспорт: "1337676769"
оценки:
  физика: 4
  химия: 3
  информатика: 5
  английский: 4
  русский: 5
  литература: 4
  физкультура: 5
  обществознание: 3
  алгебра: 4
  история: 5
  география: 4
  биология: 3
  геометрия: 4

If

H(b0..bn-1) = Σ bi * 256^(n-1-i) mod p,

then for concatenation we have

H(x || y) = H(x) * 256^|y| + H(y) mod p.

The YAML behavior provided the second half of the exploit. From parser tests against gopkg.in/yaml.v3 v3.0.1:

• duplicate keys were rejected, so overwrite tricks did not work;
• yaml.Unmarshal parsed only the first YAML document;
• bytes after an explicit document end marker ... were ignored by unmarshaling;
• unknown helper keys outside the target struct were ignored, but they were not needed for the final solve.

So the useful primitive was simple: make the first YAML document parse to a perfect certificate, then place signature-only bytes after ....

So the plan was:

1. Build a new first YAML document with the same passport and all grades set to 5.
2. End that document with ... so the parser stops there.
3. Append extra bytes after ... that do not affect parsing but do affect the hash.
4. Choose those bytes so the final byte string has exactly the same signature as the known signed original.

Rolling-Hash Algebra

Let T be the forged first YAML document and z be the ignored suffix. We need

H(T || z) = H(orig).

By the append formula,

H(z) = H(orig) - H(T) * 256^|z| mod p.

The key shortcut came from the modulus:

256^7 ≡ 5 mod p.

Since 256^7 = 2^56 ≡ 5 (mod p), an 8-byte block z = z0 z1 ... z7 satisfies

H(z) = z0*256^7 + z1*256^6 + ... + z7
     ≡ 5*z0 + u56(z1..z7) mod p,

where u56(z1..z7) is the 56-bit integer encoded by the last 7 bytes. So the target residue becomes

target ≡ 5*z0 + u56(z1..z7) mod p.

That turns suffix forging into a small search problem: pick a printable prefix byte, derive the remaining 56-bit value, and check whether the resulting bytes are acceptable. The same idea can be extended with a slightly longer printable suffix if needed.

Solution

The exploit steps were:

1. Build a first YAML document with passport 1337676769 and all 13 required grades set to 5.
2. Terminate that first document with ....
3. Compute an appended printable suffix so that the full byte string hashes to the stored signature of originalAttestat.
4. Submit the forged payload to /submit.

The visible YAML document was:

---
паспорт: "1337676769"
оценки:
  физика: 5
  химия: 5
  информатика: 5
  английский: 5
  русский: 5
  литература: 5
  физкультура: 5
  обществознание: 5
  алгебра: 5
  история: 5
  география: 5
  биология: 5
  геометрия: 5
...

One working ignored printable tail was:

eUEZD3~i$V^Vz

Final payload:

---
паспорт: "1337676769"
оценки:
  физика: 5
  химия: 5
  информатика: 5
  английский: 5
  русский: 5
  литература: 5
  физкультура: 5
  обществознание: 5
  алгебра: 5
  история: 5
  география: 5
  биология: 5
  геометрия: 5
...
eUEZD3~i$V^Vz

The Go YAML parser ignored the tail after ..., so the application saw only the valid all-5s gradebook. The hash, however, was computed over the entire byte string, including the tail, so the forged payload matched the known signature and passed verification.

A short solver sketch for the suffix computation is:

#!/usr/bin/env python3

P = 2**56 - 5
BASE = 256

target_doc = '''---
паспорт: "1337676769"
оценки:
  физика: 5
  химия: 5
  информатика: 5
  английский: 5
  русский: 5
  литература: 5
  физкультура: 5
  обществознание: 5
  алгебра: 5
  история: 5
  география: 5
  биология: 5
  геометрия: 5
...
'''.encode('utf-8')

def H(data: bytes) -> int:
    h = 0
    for b in data:
        h = (h * BASE + b) % P
    return h

original_hash = ...  # stored signature of originalAttestat
need = (original_hash - H(target_doc) * pow(BASE, 13, P)) % P

# Search printable suffix bytes; one valid result was b"eUEZD3~i$V^Vz".
# The algebra above lets us reduce the search using 256^7 ≡ 5 (mod P).

The observed successful response confirmed all checks passed, including Подпись: верна (0x00c0f995c413ce93) and the final admission message with the flag.