0
\$\begingroup\$

I asked this question on another exchange "Encrypted content in games" and it made me wonder about game design.

The basics of that question is that you are using user-input, either directly or indirectly through the current game state, to generate a decryption key which unlocks/decrypts some secret content. This input would be the solution to some puzzle or come from a series of clues.

The problem is that the input space has to have high entropy to prevent it from being brute-forced, even by a computer. Having a series of levers would mean you need to have 90-120 or so of them. If I want a shorter input like let's 7, then you need 7500 different symbols to match those 90 levers which is way to many for people to distinguish between.

So I would like to hear ideas about how you could make an engaging/fun input method with high entropy. Ideally one that's visible to the user, meaning that the user is aware of it and not happening in the background.

Here is one example I thought about:

Imagine a secret altar outside of any quest lines. In front of it are 10 slots. Any of the 500+ game objects can be placed in the slots. Based on the game objects used and their permutation, a unique decryption key is generated using the object's game-IDs. Then the clues to what objects to use and in what order could be cleverly hidden through the game or somewhere else.

It still suffers from users possible being unable to effectively distinguishing the 500 different objects in the game. Also if your game is small and doesn't have that many objects it doesn't work.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Hi @Christer, this question seems too open-ended to me for this site, as you're primarily asking for people's opinions on fun rather than a solution to a concrete problem. You might be able to change the wording to ask for solutions to your example approach or you might want to open the discussion on a general game design forum like those on gamedev.net. \$\endgroup\$ Feb 7, 2016 at 21:10
  • \$\begingroup\$ @SeanMiddleditch I do feel this question is right for this site, however he wording of my title may have been bad. Changed it, hopefully this is better. \$\endgroup\$
    – Christer
    Feb 7, 2016 at 21:32
  • \$\begingroup\$ @Christer: Removing or qualifying the word "fun" isn't going to make your question less opinion-based. You need to narrow down the scope of your question from "any idea that could work" to something that could be put into a single answer. \$\endgroup\$ Feb 8, 2016 at 5:26

3 Answers 3

1
\$\begingroup\$

Generally speaking, you don't.

What you're talking about is a general kind of puzzle that I would describe as a "combination lock". There's some interface for the user to enter a combination, but the number of entries is too vast to brute-force for the user. So instead, the user actually solves the clues needed to solve the puzzle.

Myst and its ilk thrive on such kinds of puzzles. The solution to the Mechanical Age in Myst I was a combination of 4 "digits", with each "digit" having between 8 and 10 different images. For a human, that's far too much to even consider brute-forcing.

Your problem is that you're not designing these puzzles for humans; you're designing them for machines. Your design goal is to make them unable to be brute-forced by a modern computer.

See, the Myst designers choose 4 digits rather than 5, 6, 20, etc, because 4 is a small number. It's small enough that you could quickly jot down the values you find on the age, then bring them to the place to enter it. The number of digits was choose for a similar reason. In total, you have a puzzle that has enough entropy to make brute force hard, but the scope is small enough to make remembering/copying the symbols easy.

If you are designing a puzzle that's hard for a computer to brute force, then you will have to create an interface that a human will find tedious to enter, even if they know the solution.

Take your idea. Boiled down, what you have is a 10-digit code, with 500 different possible values for each digit. Now maybe the user won't have collected all 500 before they know the solution. But they're still carrying around a satchel of 300-400 different things (which presumably have no other in-game function).

When they go through the various clues to figure out what the right ones are, they will have to sort through hundreds of choices. Even if you tell them outright which ones to use (the way Myst puzzles tend to do), they still have to search through their satchel to fish them out.

10 times.

That's not an interesting puzzle anymore. Or rather, whatever interest the puzzle may have generated is sabotaged by having to go through a great deal of tedium to tell the game the puzzle has been solved.

Remember: coming up with the solution to the puzzle is what people find interesting. Everything the user has to do after finding the solution is just dragging things out. If I spend 2 hours solving a puzzle, and then have to spend 15 minutes poking through a UI just to let the computer know I solved it, that's a problem.

Here's an example of a puzzle that had high entropy in Myst: the fireplace puzzle. You have to enter what is effectively a long binary number. It's a big pain to copy the pattern from the book, walk 5 feet, and then type it all in.

How much entropy does it provide? It's a binary matrix with 8 columns and 6 rows, which makes it 48-bits. The average smartphone can probably crack that. And remember: this is a puzzle that has reached the level of being tedious, since pretty much nobody likes it.

Admittedly, it's not actually a "puzzle"; at one point in the game, you're just told which pattern to enter.

But there is perhaps some chance for hope. Riven presents to you the Fire Marble puzzle. It's a 25x25 grid of locations. And you have to put 5 colored gems (from a set of 6; one of the tricks to the puzzle is knowing that 1 of them is superfluous) into 5 specific locations in the grid.

I'm no expert on determining the number of possible solutions for this scenario. However, when I computed 125 choose 5 to get an idea of what a similar reverse problem would be (choose 5 of 125 balls), an unordered choice represents an entropy only in the hundreds of millions. An ordered choice breaks a billion. But that's even less than the 48-bit encryption from before. It's nothing extraordinary.

I know those aren't the right calculations for the puzzle. But as order-of-magnitude estimates, even if you added a couple more zeros onto them, it seems clear that the entropy on this puzzle is probably not cryptographically secure.

And that's the best Myst ever got, entropy-wise. Not only that, Riven bent over backwards to justify having that many gird squares. Plus, they made it easy for you to jot down the solution. See, the grid is subdivided into 5x5 blocks of 5x5 locations (5 is an arc-number for Riven. It's literally written into the world). So you don't need to carry around a 25x25 grid; just 5 separate 5x5's with each one specifying which of the larger sectors it is.

So I don't believe that it's possible for you to come up with a puzzle that has cryptographically secure entropy, without being tedious to enter that solution or for the user to generate it to begin with. Or both.

\$\endgroup\$
1
  • \$\begingroup\$ Used "your" 25x25 grid idea for my own answer. I think it does have potential. \$\endgroup\$
    – Christer
    Feb 8, 2016 at 14:18
1
\$\begingroup\$

I have found one system that could work well. I'd like to contribute some of it to Nicol Bolas which made me think of this while reading his answer.

The main difference here from what I've been thinking earlier is the realization that every input-slot doesn't need to be filled in. This "negative input space" as I like to call it adds to the number of combinations while not increasing the work necessary to input the key. So the input could have a high entropy while only requiring the user to input e.g. 7 out of 7 symbols. Having the input-slots arrange themselves in 2D also helps by shortening the distance to each one and making it easier to navigate while having many slots. 225 slots put end to end would not really be manageable.

Example input grid

Here is an example showing a 15x15 grid with 7 different colored marbles. A solution would consist of a certain number of colored marbles place correctly on the grid. This grid by itself with an unknown amount of marbles required have an entropy of 675 bits. This is way more than what's needed to keep someone out. However the point was to make the inputting process more engaging and less of a chore, so requiring the player to possibly fill all 225 squares it too much work. So the player might suspect this and assume you only need 4-12 marbles, but even then the entropy is still very high at about 98 bits. Even with a fully known input length of let's say 7 marbles the entropy is still a respectable 62 bits. This would make a computer doing one combination per nanosecond reach 1% of all combinations after about 1.5 years. Just increasing the number of marbles to 8 would mean it would have taken the computer 264.5 years instead to reach 1%.

Even though it's hard for both a human and a computer to randomly guess the input, it's still should be rather painless to actually input it if you know the solution. Both locating a square and identify a color should be easy for most players to do quickly. The grid should have a helper grid (here in dark blue) to allow the player to more quickly identify the square he/she needs.

One negativ factor with this system is that each input is independent and for each clue known the puzzle becomes easier. So with a known size of 7 marbles and 6 marbles known, the last should be within reach of even a human to figure out through brute force with only 1575 possibilities. Two ways of negating that is to not letting the size of the input be known and releasing clues in bunches where e.g. 3-4 marbles are revealed at once.

Plot of entropy vs missing marbles

This is a plot of entropy vs the number of missing marbles. This assumes that the number of marbles needed is known (8 here). As you can see the plot falls fast as marbles are revealed. Remember that entropy is log2 of number of combinations, so the y-axis is logarithmic. So a single bit lost of entropy means number of combinations cut in half. On average about 8.4 bits of entropy is lost each time a marble is revealed meaning that each time there are about 337 times fewer combination then before.

Pros:

  • Can increase entropy easily without a lot of extra effort on the player.
  • Can be done without a keyboard input, so still doable on consoles or in VR.
  • The solution/clues can be compactly written, e.g. "RED-8-4".
  • It's easy and direct to do with a known solution. Compare with asking to get a Rubik's Cube to a fixed configuration, not something everybody can do.

Cons:

  • Entropy drops exponentially as clues become known. Hard to split up the solution.

Unfortunately I don't know if this drop of entropy problem can really be efficiently solved.

\$\endgroup\$
2
  • \$\begingroup\$ "Even with a fully known input length of let's say 7 marbles the entropy is still a respectable 62 bits." I'd like to see your math on this. And even if you're right, 62-bits is not "respectable" for encryption these days. \$\endgroup\$ Feb 8, 2016 at 15:31
  • \$\begingroup\$ @NicolBolas Well 62 bits would still take a while, you saw my calculation 1% after about 1.5 years. Wouldn't store government secrets with it, but I think it's good enough. Note that encryption such as RSA uses 2048 bit because the number could be factorized, kinda short-cutting a brute-force approach by trying every key. Number of bits in an encryption scheme doesn't mean the same for all encryption schemes. Also here you go (you may have to copy it manually): wolframalpha.com/input/?i=log2(sum+C(15%5E2,+n)+*+7%5En+from+7+to+7) \$\endgroup\$
    – Christer
    Feb 8, 2016 at 15:43
0
\$\begingroup\$

You're going in the wrong direction in my opinion. You want to have locks, wich can't be bruteforced. Making it like that makes the people angry and makes the feel of the game go away.

Ypu should make locks, wich no one wants to bruteforce.

If someone sees a lock with 7 levers, and 7 symbols in each of them, he either rage quits or checks the answer on the internet. You can't stop this.

And also, no matter what you do, entering the exct symbol in to 90 locks is tedious, frustrating and not very fun. Especially if someone f**ks it up somewhere.

\$\endgroup\$

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