5
\$\begingroup\$

Inspired from this question, I decided to submit an interweaved program (now deleted) written in Seed. This program uses a Mersenne twister to generate programs by entering a program that consists of two numbers. Using these two numbers, Seed generates a Befunge program. This is created by the randomization of the seed. After looking up what the definition was for cryptography and hashing I'm not really sure if it counts as hashing or cryptography. Seed only uses the randomization of the seed, but does not change anything else to the data received from the seed.

Although I only used Seed as an example, there certainly are more programming languages which use roughly the same algorithm. Do these programming languages fall under the category encryption or hashing?

Edit, for the ones interested in my post:

enter image description here

\$\endgroup\$
8
  • 4
    \$\begingroup\$ Sometimes, even valid answers are downvoted if people feel that they abuse loopholes. \$\endgroup\$
    – Martin Ender Mod
    Commented Nov 30, 2015 at 19:46
  • \$\begingroup\$ @MartinBüttner, so this is considered a loophole? \$\endgroup\$
    – Adnan
    Commented Nov 30, 2015 at 19:49
  • 2
    \$\begingroup\$ I'd consider it a loophole, because the submission didn't take any effort, has a high score and is practically impossible to crack. If any submission ticks all of those checkboxes it likely wasn't in the spirit of the challenge. \$\endgroup\$
    – Martin Ender Mod
    Commented Nov 30, 2015 at 19:50
  • 2
    \$\begingroup\$ @MartinBüttner, I disagree with the fact that this is practically impossible to crack, since there are maximally 16384 possible combinations. Also, why is having a high score against the spirit of the challenge? \$\endgroup\$
    – Adnan
    Commented Nov 30, 2015 at 20:22
  • \$\begingroup\$ "If any submission ticks all of those checkboxes..." Also I count a lot more combinations than that. There are at least 163840 ways to distribute the digits before and after the spaces (minus multiplicities due to repeated characters), times the ways to distribute the four numbers in between without causing either of the other two numbers to be empty. \$\endgroup\$
    – Martin Ender Mod
    Commented Nov 30, 2015 at 20:29
  • 1
    \$\begingroup\$ @MartinBüttner, yeah sorry. I made a miscalculation, but this still gives a maximum of 262144 combinations (2^4 * 2^14), and it is highly likely to be less than this amount. This would still be easily cracked. \$\endgroup\$
    – Adnan
    Commented Nov 30, 2015 at 20:38
  • 1
    \$\begingroup\$ Whether it's actually hard to crack or not, it doesn't make the answer any more interesting. As xnor's answer states, I think it's a cheap solution. In a completely different context Geobits said in chat yesterday "Here I judge [answers] more as useful to the site, as in, "do I want to see more of these here"." (when asked about when downvoting is appropriate). I definitely don't want to see the CnR tag derail into people posting quasi-arbitrary code that didn't take any effort and can only be cracked by brute force. \$\endgroup\$
    – Martin Ender Mod
    Commented Dec 1, 2015 at 10:36
  • \$\begingroup\$ And if the algorithm was chosen because of its flaws? (so that seeding can be reversed in small time (some seconds)) \$\endgroup\$
    – iovoid
    Commented Jul 28, 2017 at 20:44

3 Answers 3

Reset to default
18
\$\begingroup\$

It's more about the spirit of the rules.

Cops and robbers have had a problem of cop submissions that just do convoluted arithmetic. They are not solved by thinking about code, but by thinking numbers. This is boring because the structure of the code and language often matters little, and the robber is just trying to find the pre-image to some arithmetical function. With a convoluted enough operation, there's nothing better to do that brute-force search all possibilities.

This is what the rule is trying to avoid when it bans hashing or cryptography -- built ins that just give you a mangling function. Random number generators are much the same. Even if those were specifically banned though, there are many ways to home-brew something similar. We've seen lots of them, and feel boring and samey.

So, yes, the rules are vague and many people have "won" using the same idea. Even if your submission was legal, it may draw downvotes because it's cheap. It's the question's fault though that such cheap answers are a good path to winning by the rules as written.

Note that many top-voted cops give an interesting challenge that is meant to be cracked in a fun way, rather than trying to be uncrackable. Maybe it's best to think of cops as puzzles posed rather than code made to win an adversarial game.

\$\endgroup\$
5
\$\begingroup\$

Encryption: no, hashing: maybe

Wikipedia on encryption:

In cryptography, encryption is the process of encoding messages or information in such a way that only authorized parties can read it.

Typically how this works is, you encrypt some data using a key, pass the encrypted data to the other party, and they decrypt it with a key (which may or may not be the same key, depending on if the encryption algorithm uses symmetric or asymmetric keys). The defining feature of encryption is, without the decryption key, a third party would not be able to retrieve the original data. Some algorithms are more secure than others, but that's not a relevant discussion.

Wikipedia on hash functions:

A hash function is any function that can be used to map data of arbitrary size to data of fixed size.

The key difference between hash functions and encryption is that encryption is designed to be reversible if you have the proper key. A hash function may or may not be reversible; a certain class of functions called cryptographic hash functions are designed to be irreversible, outside of brute-force attacks.

A Seed program is definitely not an encrypted form of a Befunge-98 program. There is no key that one could use to efficiently compute a Seed program from a Befunge-98 program.

As for hashing, possibly, depending on how you look at it. If you view the Seed program as being the input, and the Befunge-98 program as being the hash, the definition sort of works. Though it makes use of an RNG (specifically the Mersenne Twister algorithm), computing a Befunge-98 program from a Seed program is wholly deterministic, and can be done in an efficient manner. On the flipside, computing a Seed program from a Befunge-98 program (or even just a Seed program from a given expected output) can only be done by brute-forcing the seed space (unless the Mersenne Twister algorithm has some major flaws in its design).

As for the challenge in question, though submitting two interwoven Seed programs is not explicitly against the rules, some might interpret it as being against the spirit of the challenge, because it involves an RNG. That's barely relevant though, because Seed programs are wholly deterministic. Though the crack would likely come about through the use of brute force, I don't see a problem with that, as the brute forcing is not unbounded; there are a finite number of pairs of valid Seed programs that could be formed from your entry. I suspect the downvotes were from ignorance; people saw "RNG" in the language description and hastily downvoted without reading further and seeing that Seed is actually deterministic.

\$\endgroup\$
9
  • 3
    \$\begingroup\$ One of the downvotes was mine and I can assure you I was aware that the answer was deterministic. \$\endgroup\$
    – Martin Ender Mod
    Commented Nov 30, 2015 at 20:02
  • \$\begingroup\$ In general, seeded RNGs are deterministic. That doesn't stop them being RNGs, or stop them being unfun in cops-and-robbers. \$\endgroup\$
    – Peter Taylor
    Commented Nov 30, 2015 at 22:52
  • 1
    \$\begingroup\$ Generating a program from a seeded RNG given the seed and length is conceptually no different than transpiling a program. \$\endgroup\$
    – user45941
    Commented Nov 30, 2015 at 23:17
  • \$\begingroup\$ @PeterTaylor, so what you're saying is that my submission is "unfun"? Why? Because the only way to crack it is by using a brute force algorithm? \$\endgroup\$
    – Adnan
    Commented Dec 1, 2015 at 0:39
  • \$\begingroup\$ @Adnan, yes. One of the lessons which came out of the first ever cops-and-robbers question was that future cops-and-robbers questions should prohibit cops which just throw the hidden state through a trapdoor function. \$\endgroup\$
    – Peter Taylor
    Commented Dec 1, 2015 at 10:39
  • 1
    \$\begingroup\$ @PeterTaylor A Seed program is a trapdoor function, but the difficulty is in the Befune98-to-Seed direction. That's not relevant here. \$\endgroup\$
    – user45941
    Commented Dec 1, 2015 at 11:05
  • \$\begingroup\$ @Mego, if the cops weren't required to give the output of their programs, you might have a point. But as it is, the output of the two programs is derived from the output of the trapdoor function, so it's highly relevant. \$\endgroup\$
    – Peter Taylor
    Commented Dec 1, 2015 at 11:57
  • \$\begingroup\$ @PeterTaylor I believe (please correct me if I am mistaken) that you are assuming that the method of solving the cop answer would involve finding two Befunge98 programs that produce the given output and whose Seed representations can be interwoven to form the cop code. That is incorrect; there is no need to reverse the trapdoor function. Simply iterating over permutations of the interwoven code, splitting on the second space, and running each of the outputs until a suitable match is found is sufficient. No brute-forcing a seed from a program. \$\endgroup\$
    – user45941
    Commented Dec 1, 2015 at 12:06
  • 2
    \$\begingroup\$ I'm not assuming that at all. The fundamental problem is that because a trapdoor function is involved, it is impossible to say by "inspection" whether or not one possible solution is more likely than another: the only way to solve is brute force of the input space. That is against the spirit of cops-and-robbers, and in this case it's against the letter of the question as well. \$\endgroup\$
    – Peter Taylor
    Commented Dec 1, 2015 at 12:58
-6
\$\begingroup\$

To answer the question posed in your subject: Randomization is not hashing nor encryption. Hashing and Encrypting are both linear transformations. Randomization is not.

\$\endgroup\$
1
  • 6
    \$\begingroup\$ Neither hashing nor encrypting are linear transformations. \$\endgroup\$
    – Peter Taylor
    Commented Dec 2, 2015 at 22:03

You must log in to answer this question.

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