CTFZone Paper: Little Knowledge

Intro

Why a cryptographic task was necessary

How we chose our development stack

How we decided on the task idea

A. What is graph Hamiltonicity?

B. How Hamiltonicity can be used for identification

  • publish the graph with an embedded hamiltonian cycle. It should be visible to everyone;
  • connect to a team server and prove, the we know the cycle without revealing the cycle itself.

How we developed the task

Protocol: high-level view

  • the graph;
  • the round flag for the team
  • a 16-byte random string RANDOMR received previously from the team’s server;
  • an RSA signature of all the above.

Protocol: internals

  1. The desired number of vertices in the graph.
  2. The number of parallel proofs.
  3. The chosen commitment schemes.
  1. Compute around 2¹⁷ values of CRC32_FH with random b_1, b_2, b_3 and put them in a hash table, so that we can look up a precursor for each computed value of CRC32_FH in near constant time
  2. We compute CRC32_SH_INVERTED with the initial value of the CRC32 we are trying to find a collision to as input and random values b_4, b_5, b_6 in a loop. During each iteration we check if the result is in the hash table we compiled earlier. This should take around 2¹⁵ — 2¹⁶ iterations.
  3. Once we’ve found a collision in the hash table, we’ve also found a collision for CRC32. y=CRC32(b_1, b_2, b_3, b_4, b_5, b_6)

The final vulnerability

Development quirks

Testing

Anti-cheat

  1. Simple pull. Checker simply proves that it knows the cycle. Anything goes wrong — team’s SLA (Service Level Agreement) points are deducted.
  2. Checker creates valid commitments, but before sending them to the team’s server, damages them in a random fashion, ensuring that the Verifier will treat the resulting commitment as erroneous. It repeats the cycle of wrong proofs for several seconds. Then it completes one correct interaction and pulls the flag. If at any point the answer from the team’s server is an unexpected one, or the server drops connection, team loses SLA points.
  3. Checker initializes the protocol, sends a valid commitment. Then it tells the Verifier to send the challenge in a loop for several seconds. After the time runs out, it picks the latest challenge, creates a packet that reveals the commitment and sends it to the team’s server. If the server replies with the flag, everything is alright. Any deviations from checker’s expectations are once again penalized by deducting their SLA points.

Conclusion

--

--

--

International community conference for cybersecurity researchers and professionals. No suits, no business — only hardcore research.

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
OFFZONE

OFFZONE

International community conference for cybersecurity researchers and professionals. No suits, no business — only hardcore research.

More from Medium

Is spyware present in peer to peer (file sharing) applications?

QakBot Detection: DUCK HUNT

Deepfence and Lightstream Partner to Deliver Comprehensive Runtime Security for Enterprises…

Cyber attack bee-havior

A honey dipper in a pool of honey on a wood paneled surface sits next to a glass jar of that same honey