Jun
27

Midnight CTF 2018 Finals – Snurre128

In this challenge we have a stream cipher based on LFSR and nonlinear filtering function. It has 128-bit LFSR secret state and we are also given 1600 keystream bits. Our goal is simply to recover the key which is the initial state. Here is the nonlinear filtering function:

f(v) =
v[0] ^ v[1] ^ v[2] ^ v[31] ^ 
v[1]&v[2]&v[3]&v[64]&v[123] ^ 
v[25]&v[31]&v[32]&v[126]

We can see that the two nonlinear terms are products of 4 and 5 variables. With high probability these terms are equal to zero and the filtering function becomes linear. More precisely, define

L(v) = v[0] ^ v[1] ^ v[2] ^ v[31]

Then the probability $p$ that $f(v) = L(v)$ equals to $15/16 \times 31/32 + 1/16 \times 1/32 = 233/256$. Moreover, for 128 keystream bits the approximation can be expected to hold with probability $p^{128} \approx 2^{-17.384}$ or roughly $1/171000$. That is, if we sample 128 keystream bits roughly 171000 times we can expect that once they all are filtered using the linear function $L$. Then we can solve the (noiseless) linear system and recover the key. We can sample bits from the 1600-bit keystream since we expect that roughly $233/256\times 1600$ of them are filtered using the linear function and we will succeed once we choose 128 bits out of them. We just need to know the linear function that maps the original key to each of output keystream bits (i.e. repeated LFSR step and linear filtering). This can be done simply by running Snurre with linear filtering function on keys with single bit set (i.e. basis vectors) and putting the resulting streams into columns of a matrix.

The solution may take some time, e.g. around 1 hour on a common laptop. But it can be easily parallelized simply by running multiple instances.

Solution code in Sage

The problem of solving noisy linear equations is called Learning Parity with Noise (LPN). There are various methods for approaching it. A good recent paper on this topic is “LPN Decoded” by Esser et al. For example, the described above method is called Pooled Gauss in the paper.

Apr
02

0CTF 2018 Quals – zer0C5 (Crypto 785)

0ops Cipher 4, hope you enjoy it:)
zer0C4.zip
nc 202.120.7.220 1234

Summary: related-key attack on weakened variant of RC4

Read the rest of this entry »

Apr
02

0CTF 2018 Quals – zer0SPN (Crypto 550)

0ops SPN, hope you enjoy it:)
zer0SPN.zip

Summary: linear cryptanalysis on toy block cipher

Read the rest of this entry »

Apr
02

0CTF 2018 Quals – zer0TC (Crypto 916)

0ops Toy Cipher, hope you enjoy it:)
zer0TC.zip

Summary: meet-in-the-middle and key-schedule constraints

Read the rest of this entry »

Oct
05

hack you ’17 :: easy CTF on Oct 8—14

hack you '17

As a tradition, every fall we host a fun lightweight Jeopardy CTF for our freshmen to attract them into all the CTFey goodness. This one will be our fifth year (holy shit!)

We invite everyone to check out hack you ’17 this year. Just as always, two separate scoreboards: one for SPbCTF meetups, one for everyone on the world. And yeah, we have some prizes this year!

28 challenges ranging from easy pen-and-paper to interesting. Noobies will have a taste of what CTFs are, skilled will have fun and check if they can pwn everything the fastest.

Registration open: now (sign up individually — no teams)
Game is live: October 8th, 2017 18:00 UTC
Game ends: October 14th, 2017 18:00 UTC

Sign up: https://hackyou.ctf.su/

Prizes:
Top-3 in the Overall board get a free ZeroNights 2017 entry each. Matrish Matrish Matrish
Top-50 in the Overall scoreboard qualify to the Final event in Saint Petersburg on October 29th.

So in just a few words: Fifth hack you. 28 good old speedhack tasks. October 8th.

Sep
04

TWCTF 2017 – Solutions for BabyPinhole, Liar’s Trap, Palindrome Pairs Challenge

Scripts with short explanations:

Jul
09

Polictf 2017 – Lucky Consecutive Guessing (Crypto)

We implemented a random number generator. We’ve heard that rand()’s 32 bit seeds can be easily cracked, so we stayed on the safe side.

nc lucky.chall.polictf.it 31337

chall.py

Summary: breaking truncated-to-MSB LCG with top-down bit-by-bit search.

Read the rest of this entry »

Jun
19

Google CTF 2017 Quals – BLT (Bleichenbacher’s Lattice Task – Insanity Check)

A slow descent into the dark, into madness, futility, and despair.

BLT.jar (not necessary)
STDOUT
Flag.java

Summary: DSA with short secrets, lattice + meet-in-the-middle attack.

Read the rest of this entry »

Jun
19

Google CTF 2017 Quals – Crypto writeups

Scripts with short explanations for all crypto tasks (except RSA) from Google CTF Quals 2017:

Mar
20

0CTF 2017 Quals – Zer0llvm

Talent Yang loves to customize his own obfuscator. Unfortunately, he lost his seed when he was watching Arsenal’s UEFA game. What a sad day! His team and his seed were lost together. To save him, could you help him to get back his seed? We can not save the game, but we may be able to find out his seed.
Compile: ollvm.clang -Xclang -load -Xclang lib0opsPass.so -mllvm -oopsSeed=THIS_IS_A_FAKE_SEED source.c
Clang && LLVM Version: 3.9.1
link
flag format: flag{seed}

Summary: deobfuscating and attacking AES parts.

Read the rest of this entry »

Mar
20

0CTF 2017 Quals – OneTimePad 1 and 2

I swear that the safest cryptosystem is used to encrypt the secret!
oneTimePad.zip

Well, maybe the previous one is too simple. So I designed the ultimate one to protect the top secret!
oneTimePad2.zip

Summary: breaking a linear and an LCG-style exponential PRNGs.

Read the rest of this entry »

Mar
20

33C3 CTF 2016 – beeblebrox (Crypto 350)

Make bad politicians resign!

nc 78.46.224.72 2048

files

Summary: factorization-based attack on a signature method

Read the rest of this entry »

Oct
15

hack you spb @ 17 Oct 2016

hack you spb

Remember hack you CTF? Yeah, that random event that we throw for our freshmen and everyone interested. We’re hosting a new one.

It’s fall already and that means the new CTF season is starting, and so is the new academic year in the universities.

This is the time when we want to attract more freshmen into our CTF tarpit. Specifically, to our SPbCTF meetups in our city.
So we are running — a CTF.

But it’s not just for the freshmen. Wouldn’t it be fun to allow the whole world to beat the shit out of our first-year students, right? So we are opening hack you spb to everyone interested, just separating the scoreboards: one for the world and other just for confirmed SPbCTF fresh blood (bonus: if you manage to soceng our padawans for a verification string, you can compete in that special chart too).

Registration open: October 15th, 2016 — October 21st, 2016
Game starts: October 17th, 2016 15:00 UTC
Game ends: October 21st, 2016 15:00 UTC

Sign up: http://hackyou.ctf.su/

Don’t expect it to be challenging, it will be more of a speed-hack contest.

So in just a few words: New hack you. School-level tasks. October 17th.

Oct
11

HITCON CTF QUALS 2016 – Reverse (Reverse + PPC 500)

At least our ETA is better than M$.
http://xkcd.com/612/

reverse.bin

Summary: optimizing an algorithm using Treap data structure and CRC32 properties.

Read the rest of this entry »

Oct
10

HITCON CTF QUALS 2016 – PAKE / PAKE++ (Crypto 250 + 150)

pake1.rb
pake2.rb

Summary: attacking password-based key exchange schemes based on SPEKE with MITM.

Read the rest of this entry »

Older posts «