8
\$\begingroup\$

I'm thinking of creating a challenge involving attacking a cryptographic function.

The challenge would be to take the specified function which would ostensibly offer XXX (>2^40?) bits of security and exploit (intentional) flaws in the crypt in order to bring the security into a reasonable exhaustible range (~2^24).

The winner would be the first person to report the/a correct answer.

For example, it might be something like:

Ciphertext was generated by XORing the Plaintext with random bytes generated using the PRNG specified here: [full spec here]. Given the ciphertext, recover the plaintext.

The intention is that you would attack the PRNG, using knowledge of the spec to reduce the search space for the initial state of the PRNG. With that sufficiently reduced space, an exhaust could be run over the initial state, generating potential keystreams which could then be XORed with the cipher in order to recover the plaintext.

The difficult part would be developing the attack on the PRNG, but a successful attack would require a non trivial amount of programming.

I'm curious whether:

  1. this would be on topic

  2. there might be any issues with this type of challenge that I haven't thought of, for example does a more powerful computer give too much of an advantage for this type of challenge?

  3. Should it be a requirement that the code used to perform the exhaust be included?

Despite the fact that there would be an undeniable first winner, my intent would be to leave the challenge open indefinitely because I'm sure people will come up with better attacks than I intended, and should be rewarded for doing so.

\$\endgroup\$
9
  • \$\begingroup\$ Scope aside, a ciphertext-only attack is impossible for a stream cipher. \$\endgroup\$
    – Dennis Mod
    Commented Nov 1, 2016 at 0:58
  • \$\begingroup\$ @Dennis I'm not sure I follow. You also have the key generation mechanism and I guess I was implicitly including statistics on the plaintext (i.e. it's ascii). I can make that more explicit. For example, if I use a LFSR (with fully known spec) with an initial fill of 10 bits to encrypt ascii plain text, you can trivially recover both the initial fill and the plaintext using merely brute force. \$\endgroup\$
    – Liam
    Commented Nov 1, 2016 at 1:51
  • 2
    \$\begingroup\$ The win condition (first-to-solve) is discouraged in general here, but I don't know that's it's outright banned. Anyone have a link to a clear answer one way or the other on meta? \$\endgroup\$
    – Geobits
    Commented Nov 1, 2016 at 2:18
  • \$\begingroup\$ @Geobits This is the one I remember. There was a meta post that went along with it somewhere too, if I recall correctly. \$\endgroup\$
    – Liam
    Commented Nov 1, 2016 at 2:22
  • \$\begingroup\$ OK, if enough about the plaintext is known (e.g., it is ASCII and sufficiently long) and the PRNG isn't horribly broken, cryptanalysis should be possible. \$\endgroup\$
    – Dennis Mod
    Commented Nov 1, 2016 at 2:40
  • 1
    \$\begingroup\$ I feel like we need to make the distinction between this kind of cryptography attack and malicious code (assuming there is) \$\endgroup\$
    – Nathan Merrill
    Commented Nov 1, 2016 at 17:33
  • \$\begingroup\$ @NathanMerrill there is nothing malicious about cryptographic attacks. \$\endgroup\$
    – Liam
    Commented Nov 1, 2016 at 19:49
  • \$\begingroup\$ @Liam I don't think that the challenge is malicious, but what if the challenge was "Access X database, which is encrypted using Y (flawed), and exploit the flaws", I'd definitely consider it to be malicious. It's a fine line we're walking here. \$\endgroup\$
    – Nathan Merrill
    Commented Nov 1, 2016 at 19:51
  • 2
    \$\begingroup\$ We are attacking theoretical crypt here. Most of the attacks that are of the type you describe are attacks on particular implementations. Any method I ask about will not be suitable for real world use. \$\endgroup\$
    – Liam
    Commented Nov 1, 2016 at 19:55

1 Answer 1

Reset to default
10
\$\begingroup\$

Let me start by saying that I like the idea. Cryptography has always fascinated me. I have even posted a kind of cryptanalysis challenge myself – Cryptographic hash golf (robbers) – and personally would welcome the idea of having more challenges of this kind.

Specifics aside (e.g., breaking a non-trivial steam cipher and performing frequency analysis as parts of the same task might be a bit too much), I think this would make an interesting code challenge if designed as one.

I'm curious whether [...] this would be on topic

In the format you proposed... maybe. Are pure programming puzzles on topic? is still trying to sort this out, and I personally agree with this answer (not the one with the most votes) in that programming puzzles should have an objective winning criterion other than posting time.

Posting time alone means that the contest is really over as soon as somebody posts a working solution, which is unfortunate for several reasons: it gives you no incentive (or possibility, really) to improve on your first working version, there's really no reason to keep working on your partial solution as soon as someone beats you to the punch, and the first answer doesn't even have to be good to finish the contest; the cat is already out of the bag. Granted , share these issues, so none of them is a deal breaker.

Having said all of the above, it's difficult to predict if the specific challenge you propose would remain open. The community seems divided on the issue, and it takes only five close voters to put a question on hold.

I'm curious whether [...] there might be any issues with this type of challenge that I haven't thought of, for example does a more powerful computer give too much of an advantage for this type of challenge?

Without having more details regarding the strength of the stream cipher and how much is known about the plaintext, it's hard to tell, but if a successful break is – as you mentioned – possible by reducing the effective strength of the stream cipher, the part that is left might put users with better hardware or deeper pockets at an advantage.

Should it be a requirement that the code used to perform the exhaust be included?

Objective computational challenges without "code" discusses this. The community seems to be leaning towards no, but as you'll be able to tell from my answer, I don't really agree. This site is about programming contests, so – in my personal opinion – answers should contain code.

In this particular case, an answer that contains nothing more than the correct plaintext would close the contest without adding valuable information of any kind to the site. Requiring the actual code that was used mitigates this and has no downsides I can think of.

A different approach

This is just an idea and might result in a better, worse, or simply different challenge type, but I think the underlying concept could make a nice challenge.

For example, the challenge could include a few test vectors, and answers would submit solvers that the challenge author or a trusted third party runs with undisclosed ciphertexts. This would mix cryptanalysis (finding vulnerabilities in the stream cipher) with coding (making the exhaustive search quick), without any potential scope issues (that I'm aware of, anyway), without unfair advantages to users with slow computers, and without the one-answer-and-this-is-over situation.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ I like the "different approach" you mentioned, the one that runs fastest and finds the answer on a hidden input. I think that provides the most room for competitive solving over time. \$\endgroup\$
    – isaacg
    Commented Nov 1, 2016 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .