25
\$\begingroup\$

I want to add a loophole about random stuff in CnR challenges to the standard loophole list, but I have a hard time formulating the post in a way that won't result in a lot of "... but what about xyz?", and "zyx is not really random, but it still requires brute forcing".

I want to add a loophole that disallows:

  • Cop posts that use random number generators
    • rand("seed",_____);rand(_____)(_:_) gives the 7 first integers of A088957. Good luck!
  • Cop posts that use something that could just as well be random
    • sin(cos(tan(________)) gives 1-9 if you take 9 consecutive digits starting at digit number k. Not random, but could just as well be.
  • Cop posts that create a program that generates its output by decrypting a sequence of bytes via RSA

The list goes on.


Cop posts like these are only possible to crack by brute-forcing it, and that's not very fun since it has nothing to do with programming skills, (everyone here can write a brute force solver, but it's not fun, and might take a lot of time). It's easy to think that downvoting "boring" solutions like this would prevent it -> Problem solved.

But, most CnR posts have hidden characters, and how would you know if _n_(" ee ")() is a clever post, or just some random "stuff" that happens to solve the challenge? It looks clever at first sight, you can't find a way to solve it, so you upvote it and think: "Man, that was a clever post".

Problems that might arise if we try to prevent this:

  • What about posts that are borderline random?
  • What about posts that require brute-force solving, but are not random?
  • Where do we set the limit, and how do we define it in an unambiguous way?

Note: I'm not suggesting to disallow all posts that requires some degree of brute forcing to solve, only posts that requires only brute forcing to solve.


Is it possible to ban such submissions? How could we phrase it?

\$\endgroup\$
  • \$\begingroup\$ Some additional reading \$\endgroup\$ – AdmBorkBork Dec 5 '16 at 13:51
  • 3
    \$\begingroup\$ I just want to state that I had to create a brute forcer in one of the CnR challenges to crack it. It was exciting since it was one of my first CnR challenge attempts, but after seeing multiple similar cop submissions where you need to brute force to crack them, it became annoying. \$\endgroup\$ – Kritixi Lithos Dec 5 '16 at 13:58
  • \$\begingroup\$ The only possible issue here is that whether or not RSA can be efficiently cracked is unknown (thanks to the P-NP problem). Though, given that it probably will not be known in our lifetimes, it's safe to assume that there is not an efficient way to crack RSA. \$\endgroup\$ – Mego Dec 5 '16 at 22:53
  • \$\begingroup\$ I don't see anything wrong with the first two examples. Cryptography is a real issue, which has nothing to do with "randomization". \$\endgroup\$ – feersum Dec 6 '16 at 0:48
  • \$\begingroup\$ And a hash function might be a red herring, too. saw one at the code ladder where the solution just nop'd it out by using the inner gap \$\endgroup\$ – masterX244 Dec 6 '16 at 8:38
3
\$\begingroup\$

I don't think we can or should ban such answers

You've already pretty much outlined why I think these answers cannot be banned. There are too many ways to make them and any definition we make will let bad answers through the cracks and prevent good answers from being posted or will be wildly subjective and will result in numerous arguments. Both of these are, in my opinion less ideal than the current situation.

So just do nothing?

Well no not quite. I don't think we should change policy but there are things I think we can do as users to help reduce the number of these answers or at least increase the number of high quality cops and robbers solutions. Here they are

Make such answer less lucrative

The main reason these types of answers are produced is because they are nigh impossible to crack not because they are very well scoring. So a good step in combating them is making them more likely to score lower than regular answers. This is the least useful of my 3 suggestions, it's one of those things that if you do well its not noticeable but if you do it poorly it can really blow up in your face.

Smaller problem space = better score

This one is done well in a lot of challenges.

The problem space is the number of possible cracks a robber might have to check on a given answer. The general idea here is that cryptographic answers thrive because they force robbers to search the entire problem space for the answer. While with most answers the robber can narrow down the problem space with clever thinking cryptographic answers cannot.

I then makes sense that a smaller problem space should correspond to a larger score this way higher scoring cryptographic answers are easier to crack. However when the scoring and problem space are not correlated it is often easy to make the problem space absolutely titanic, without incurring any penalty to your score.

An bad example of this is this question, which scores based on program length but is looking for an integer input, meaning that all programs have basically the same enormous problem space. Same with this one.

Make problem spaces smaller

This second suggestion is in the same thread as the last.

The idea here is that in general small problem spaces benefit fun answers and hurt cryptographic or random answers. For example here are two possible problem spaces:

  • All substrings (including non-continuous ones) of the program

  • Programs with one character changed from the original

The first is basically a powerset meaning that for programs of length n there are 2n programs to search while for the second there are only 256*n programs to search. Since the first is exponential you only need a handful of bytes before the problem space is completely out of hand, while the second is linear meaning to get large enough problem spaces for these to be an issue you need to pay more bytes making the answers less desirable. Some of my favorite smallish problem spaces are:

  • All continuous substrings of the program (O(n2))

  • All programs within a Levenshtein distance (O(nm) where m is the distance)

Make it harder to produce these answers

The effects of this are two fold

  • If it is hard to produce these answers less will appear

  • If it is hard to produce these answers it will take significant effort to produce them and we can expect that those made are actually the result of significant effort and are then, hopefully, actually high quality interesting answers.

Now this is easier said than done so I have a couple tips for doing this in your questions.

Make the thing the Robber is looking for hard to detect

One of the most common things that robbers are searching for is a program that fulfills some relation to some provided code. This is really the prime scenario for cryptographic cops. You set up a program that does a hash of some code ensuring that code that satisfies the relation probably also has to do that same hash. However there are other ways to do this for example the programming languages quiz. Here the robbers are looking for a language. It is next to impossible to make a cryptographically secure answer to this question. The idea is that the normally a program is able to tell when it has been cracked. For example the right key has been provided as input. However detecting you have been run in the right language is next to impossible unless you are willing to write a massive polyglot.

I'm afraid I can't give very rock solid advice on how to make these because they are rare and I've never asked one myself. The best I can say is that questions asking robbers to discover properties of a cops program rather than producing something based on code seem to fit this bill often.

Give agency to the robbers rather than the cops

One of the most important parts of a cryptographic answer is that the cop has power over the robbers so that they can enforce the only reasonable way of solving their challenge. Hash based answers work because the robber has to use a hash to crack it. If you give agency to the robbers to make more varied cracks the cop becomes unable to force them to use their crypto method. Lets walk though an example of a CnR that is good at this and one that is bad.

Good example

In this mock CnR cops provide a set of characters and robbers must write programs using those characters that add two numbers.

Here robbers have a ton of freedom with making their own programs. Cops can impose restrictions on robbers but they will have a hard time forcing them to use crypto.

Bad example

In this mock CnR cops provide a program with no whitespace and robbers must add whitespace to make the program add. (Sound familiar?)

Here cops have all the power. Whitespace does very little in many languages so a cop need only choose a language where it is less significant and use that. Here is a pseudo code solution

if hash("")=="o A#,(^[|)JyD>?J" then add input

A robber obviously has no choice but to find the string of whitespace that has that hash.


Vote sensibly

Now many of us have been downvoting answers that are overtly cryptogrphic in nature for a while. And this may or may not stem the tide. You also pointed out in your question that it might be hard to tell if a uncracked answer is using crypto. However I think that it is more important that we vote sensibly on questions. If you are bothered by this issue I implore you to downvote questions that make no effort prevent such answers. This includes questions that include the

plz don't try to use crypto because you would win this challenge :(

If upset users continue to downvote and leave comments explaining why, question askers will get the message and hopefully make a change.

Of course if you do not feel like doing so these are your votes. I cannot tell you how to vote nor would I.

One last thought

Although it may go against what I have been hammering on this entire time I think that there is another way to approach the question.

Embrace the cryptographically secure answers

Now before you get your pitchforks I don't mean to say that you should encourage these answers in their current state; that we should adopt a defeatist attitude and allow these answers to fester. I mean to say that it might be nice to have CnR challenges that are tailored around these answers. Challenges which are drafted with these types of answers in mind such that the challenge is still enjoyable even if the majority of answers are cryptographic.

This is a rather new idea so I'm not entirely sure how it would play out but I thought I would put it out there as a more optimistic outlook on this issue.

\$\endgroup\$
1
\$\begingroup\$

If we all agree that the cops' challenge has an objective winning criterion, we should realize that their objective is usually not to make the robbers find it the most interesting, but to trade safety with some other criterion (such as golfiness), and write a submission doing the best in that criterion (and ideally being less safe) that is still safe.

It probably will make it less interesting if you plan a specific method for the robber to crack and leave hints in the code (not always if you are making a standalone puzzle, but always in the case of a challenge that everyone can add a submission). Banning sin(cos(tan(___))) is like requiring them to make it crackable, which is difficult and subjective. And it makes the cops' scores nonsensical.

It is expected that a cop's submission with an uncompetitive score would be very difficult to crack. We just ban the relevant builtins to not trivialize the task or give unadjustable crackability. We don't even need to downvote such answers. The robbers could simply choose to not crack them.

On the other hand, there were submissions using sin(cos(tan(___)))-like methods being cracked nevertheless on our site.

\$\endgroup\$
  • 1
    \$\begingroup\$ "The robbers could simply choose to not crack them. " Many CnR challenges have not being cracked as one of the criteria for winning. Not being cracked because of a boring challenge isn't really a disincentive. \$\endgroup\$ – JAD Sep 1 '17 at 11:29
  • \$\begingroup\$ @JarkoDubbeldam The premise is that they have an uncompetitive score. \$\endgroup\$ – jimmy23013 Sep 1 '17 at 12:31

You must log in to answer this question.

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