This year I wrote three challenges for DiceCTF, two fairly easy (
yaonet) and one difficult (
dicenet). Besides the writeups in this post, you can find my solution code at github.com/defund/ctf.
dicenet did not get any solves during the competition. I think this is mainly because there were too many moving parts in the challenge, and people felt bogged down by the implementation component. Ultimately it’s on me to write challenges that (at least some) people can enjoy and feasibly do within 48 hours, and I think I failed in this respect. I’ll be holding off on making a writeup for
dicenet, partly due to time and also because I have more to say on this topic. Stay tuned!
I got the idea to write this challenge from reading about Winternitz signatures on GeeksForGeeks. It’s a decent explanation for the intuition behind the scheme, but also blatantly insecure.
Basically, we can break unforgeability by finding two strings
m1, m2 such that the
i-th byte of
H(m1) is greater than or equal to the
i-th byte of
H(m2). This way, once we get a signature for
m1, we can forge a signature for
m2 just by hashing each component a few more times. The simplest way to do this is to brute-force a string whose hash bytes are all at least 128, and then brute-force another string whose hash bytes are all at most 128 (see the solution code for details).
P.S. How do you fix the Winternitz signature scheme? Essentially, you need to attach a checksum to whatever you sign, in order to guarantee that no message is “strictly greater” than the other message.
This is somewhat of a successor to
ssh, a challenge I wrote for ångstromCTF way back in 2018. In that challenge, you were given a partially redacted RSA key (of course, this concept has also been explored in other places). For
yaonet, I wanted to do something similar for a partially redacted ECDSA key. After some decoding, we find that all but a few bytes of the private exponent are revealed:
d = ??????dfb3ccae87f774d0a97aec2c494ba96da521dfffbbf9e0e7447fb7????
Since we also have the public key, the naive solution would be to guess the bytes via brute force. However, this would require 240 guesses. The better approach is to do a meet-in-the-middle algorithm (see the solution code for details). This is very similar to the baby-step giant-step attack, except in this case there is no contiguous range of unknown values. Through this challenge, I thought it would be nice to highlight that the idea behind BSGS can be applied a lot more generally when it comes to solving discrete logarithms.