[araver]

This game thread continues the tradition of the first two games: and

One player plays the Evil Mastermind (that's me, replacing the original Evil Mastermind for this game) who nukes the states of the USA 3 at a time, the other players play Hackers who seek to stop the Evil Mastermind. The Evil Mastermind plays by posting commands which activate missile strikes. Each command has a unique password, which is derived from the command by a hashing algorithm. The Evil Mastermind devises a different algorithm at the start of each game, and posts the passwords along with the commands. The Hackers will see the commands and passwords and from this they should try to deduce the hashing algorithm. The Hacker who does this first, and correctly figures out the password to the command "ABORT", stops the Evil Mastermind and wins the game. Anyone can join in at any time as a Hacker.

Now hashing algorithms can be exceedingly difficult to crack, but there are restrictions placed on the kind of algorithm that the Evil Mastermind can use:

1) The Evil Mastermind must be able to derive an alphanumeric password of fixed length from any word (password length 8 characters or less, you choose). It doesn't have to be a cipher in the sense that it can be decrypted to the original word, indeed the fixed length makes that impossible.

2) You must be able to do it in your head, with no external aids, in 40 seconds or less. You may look at the word you are hashing but you should not have to look at the previous letters of the password, since real-life passwords are generally shown as ***** as you type (although you may use previous letters as far as your memory can handle it). It's up to you to ensure that you can do all this. A really classy algorithm is one which fulfils this condition better (quick and easy to perform, in other words).

3) Although it is quite possible to hold an alphabetic substitution table in your head, and apply it quickly, I'll rule this out because in conjunction with other techniques it's too difficult to crack. Any technique that requires a large amount of information to be memorised in advance is not allowed. Caesar ciphers with a large shift pretty much fall into that category.

4) Consistency. This is a matter of good sportsmanship. For example, since "ABORT" is the target word, you can't have a rule that comes into play only when the sequence "BOR" occurs. All rules should be general enough that they come into play in at least half of the clues. The algorithm should not be geared toward the specific commands used in this game, but should work on any word.

Commands

There are 51 commands, these being the names of US states (used by the Evil Mastermind to nuke another state), plus the word "ABORT" (used by hackers to stop the Evil Mastermind).

Commands and passwords are all uppercase.

ABORT

ALABAMA

ALASKA

ARIZONA

ARKANSAS

CALIFORNIA

COLORADO

CONNECTICUT

DELAWARE

FLORIDA

GEORGIA

HAWAII

IDAHO

ILLINOIS

INDIANA

IOWA

KANSAS

KENTUCKY

LOUISIANA

MAINE

MARYLAND

MASSACHUSETTS

MICHIGAN

MINNESOTA

MISSISSIPPI

MISSOURI

MONTANA

NEBRASKA

NEVADA

NEWHAMPSHIRE

NEWJERSEY

NEWMEXICO

NEWYORK

NORTHCAROLINA

NORTHDAKOTA

OHIO

OKLAHOMA

OREGON

PENNSYLVANIA

RHODEISLAND

SOUTHCAROLINA

SOUTHDAKOTA

TENNESSEE

TEXAS

UTAH

VERMONT

VIRGINIA

WASHINGTON

WESTVIRGINIA

WISCONSIN

WYOMING

Game Play

The Evil Mastermind posts 3 commands at a time, with their passwords. The interval for doing this is undefined, no point in imposing restrictions. The Evil Mastermind chooses the commands, but should generally do requests as soon as possible.

Each Hacker may make one guess at the password for "ABORT" each time the Evil Mastermind posts commands. If someone makes multiple guesses in between clues, only the first one counts, but if they make a mistake and correct it, the Evil Mastermind can accept the correction.

There is no need for spoilers when guessing the password, although please use spoilers if you reveal the algorithm.

The first one to get the password for "ABORT" wins.

P.S. Alternatively if you've cracked the algorithm you can just use it to blow up more states if you're that way inclined (**per original Evil Mastermind's rules!)

Edited October 26, 2010 by araver

[Guest]

Command not recognized. Ignoring input.

(Maybe the coin was not fair? )

Dang! I need some more states blowing up so I get another chance. If I don't get it next time I'll have to go back to the drawing board

[araver]

Dang! I need some more states blowing up so I get another chance. If I don't get it next time I'll have to go back to the drawing board

Evil Mastermind's has gotten back to work as increased attacks on the system could possibly amount to a Denial-of-Service later ... better launch as soon as possible

OKLAHOMA

L0M4K3A4

OREGON

E0O3R1G3

TEXAS

X1S2T0A2

[Guest]

OK, this is it. This had better work, or I'm all out of ideas

ABORT

O0T2B0R2

[araver]

OK, this is it. This had better work, or I'm all out of ideas

ABORT

O0T2B0R2

Password accepted, system shutting down.

Oh, no, the former Evil Mastermind has cleverly regained control of the system and stopped it.

The rest of the states are safe (... for now).

P.S.: However, in order to reprogram the system, he needs to explain the algorithm so that the system recognizes its master.

[Guest]

Password accepted, system shutting down.

Oh, no, the former Evil Mastermind has cleverly regained control of the system and stopped it.

The rest of the states are safe (... for now).

P.S.: However, in order to reprogram the system, he needs to explain the algorithm so that the system recognizes its master.

This I can't yet do. There's a couple of [boolean] states that depend on something I haven't figured out (leaving 4 possible passwords, of which DudleyDude guessed one and I did the other 3). Still pondering...

[Guest]

Well, hell with it, I'll share what I know with the other hackers and see who can get to the bottom of it:

Each letter is defined differently:

1) 3rd letter of command

2) 1 if [unknown 1], otherwise 0

3) Last letter if command length is odd, otherwise 2nd to last

4) Number of vowels in command

5) 1st letter in command if [unknown 1], otherwise 2nd letter

6) Length of command mod 5

7) 4th letter in command if [unknown 2], otherwise 3rd letter

8) Vowel count if [unknown 2], otherwise vowel count + 1

Here's the values of unknowns 1 and 2 for various commands

NEVADA: true, false

MAINE: false, false

SOUTHCAROLINA: false, false

HAWAII: true, false

IOWA: false, true

LOUISIANA: false, false

NORTHDAKOTA: false, false

SOUTHDAKOTA: false, false

NORTHCAROLINA: false, false

NEBRASKA: false, true

MARYLAND: false, true

NEWYORK: false, true

OHIO: true, false

COLORADO: true, false

INDIANA: false, false

CONNECTICUT: false, true

IDAHO: true, true

UTAH: true, false

OKLAHOMA: false, true

OREGON: false, true

TEXAS: true, true

ABORT: false, true

As to what those unknowns might be, I'm stumped...

[Guest]

Well, hell with it, I'll share what I know with the other hackers and see who can get to the bottom of it:

Each letter is defined differently:

1) 3rd letter of command

2) 1 if [unknown 1], otherwise 0

3) Last letter if command length is odd, otherwise 2nd to last

4) Number of vowels in command

5) 1st letter in command if [unknown 1], otherwise 2nd letter

6) Length of command mod 5

7) 4th letter in command if [unknown 2], otherwise 3rd letter

8) Vowel count if [unknown 2], otherwise vowel count + 1

Here's the values of unknowns 1 and 2 for various commands

NEVADA: true, false

MAINE: false, false

SOUTHCAROLINA: false, false

HAWAII: true, false

IOWA: false, true

LOUISIANA: false, false

NORTHDAKOTA: false, false

SOUTHDAKOTA: false, false

NORTHCAROLINA: false, false

NEBRASKA: false, true

MARYLAND: false, true

NEWYORK: false, true

OHIO: true, false

COLORADO: true, false

INDIANA: false, false

CONNECTICUT: false, true

IDAHO: true, true

UTAH: true, false

OKLAHOMA: false, true

OREGON: false, true

TEXAS: true, true

ABORT: false, true

As to what those unknowns might be, I'm stumped...

Well, I was left with the same unknowns as you, plus a problem with the third character.

I missed the last/second to last bit. Instead I was working with: is the seventh character for every input of at least seven letters, and some other character if less than seven. But there was no consistency for those less than seven. Interesting that for every input of at least seven characters, the seventh one ended up being correct.

[araver]

Well, hell with it, I'll share what I know with the other hackers and see who can get to the bottom of it:

Each letter is defined differently:

1) 3rd letter of command

2) 1 if [unknown 1], otherwise 0

3) Last letter if command length is odd, otherwise 2nd to last

4) Number of vowels in command

5) 1st letter in command if [unknown 1], otherwise 2nd letter

6) Length of command mod 5

7) 4th letter in command if [unknown 2], otherwise 3rd letter

8) Vowel count if [unknown 2], otherwise vowel count + 1

Here's the values of unknowns 1 and 2 for various commands

NEVADA: true, false

MAINE: false, false

SOUTHCAROLINA: false, false

HAWAII: true, false

IOWA: false, true

LOUISIANA: false, false

NORTHDAKOTA: false, false

SOUTHDAKOTA: false, false

NORTHCAROLINA: false, false

NEBRASKA: false, true

MARYLAND: false, true

NEWYORK: false, true

OHIO: true, false

COLORADO: true, false

INDIANA: false, false

CONNECTICUT: false, true

IDAHO: true, true

UTAH: true, false

OKLAHOMA: false, true

OREGON: false, true

TEXAS: true, true

ABORT: false, true

As to what those unknowns can be, I'm stumped...

Original algorithm for character 3 is not that simple, but it is indeed impossible to distinguish from the proposed algorithm in the values seen so far.

There are only 7 states/commands (which have not been played) which actually contradict the proposed rule: "3) Last letter if command length is odd, otherwise 2nd to last".

However, it may be impossible to guess without seeing these states so I assume there is no way the original hash algorithm could be reconstructed - Occam's Razor always favors simplicity.

However, taking into account that:

-for WISCONSIN the third letter of the password is S.

-for WASHINGTON the third letter of the password is G.

can you deduce the original algorithm for the 3rd letter?

The rest is correct, or more clearly dependencies of the characters in the password to the unknowns is correct.

Again as few states have been played, it might or might not be possible to correctly distinguish unknown1 and unknown2 (as is the case with the 3rd character-spoiler above).

IMHO, this was generally the case in classic cryptography: being able to read at least some of the encrypted messages may count as breaking an encryption algorithm for practical purposes, but does not necessarily be enough to reveal the actual algorithm.

[Guest]

Well, hell with it, I'll share what I know with the other hackers and see who can get to the bottom of it:

Each letter is defined differently:

1) 3rd letter of command

2) 1 if [unknown 1], otherwise 0

3) Last letter if command length is odd, otherwise 2nd to last

4) Number of vowels in command

5) 1st letter in command if [unknown 1], otherwise 2nd letter

6) Length of command mod 5

7) 4th letter in command if [unknown 2], otherwise 3rd letter

8) Vowel count if [unknown 2], otherwise vowel count + 1

Here's the values of unknowns 1 and 2 for various commands

NEVADA: true, false

MAINE: false, false

SOUTHCAROLINA: false, false

HAWAII: true, false

IOWA: false, true

LOUISIANA: false, false

NORTHDAKOTA: false, false

SOUTHDAKOTA: false, false

NORTHCAROLINA: false, false

NEBRASKA: false, true

MARYLAND: false, true

NEWYORK: false, true

OHIO: true, false

COLORADO: true, false

INDIANA: false, false

CONNECTICUT: false, true

IDAHO: true, true

UTAH: true, false

OKLAHOMA: false, true

OREGON: false, true

TEXAS: true, true

ABORT: false, true

As to what those unknowns might be, I'm stumped...

I'm at the same point you and CL are at, but one thing I did notice was that for "Unknown1":

If true, no consonants will be consecutive to each other. It's not an equivalence because MAINE is false, so there's obviously more to it than that. But if you look, every time the consonants and vowels alternate, it's a 1. Then OHIO and HAWAII preclude that from being the solution.

[Guest]

Original algorithm for character 3 is not that simple, but it is indeed impossible to distinguish from the proposed algorithm in the values seen so far.

There are only 7 states/commands (which have not been played) which actually contradict the proposed rule: "3) Last letter if command length is odd, otherwise 2nd to last".

However, it may be impossible to guess without seeing these states so I assume there is no way the original hash algorithm could be reconstructed - Occam's Razor always favors simplicity.

However, taking into account that:

-for WISCONSIN the third letter of the password is S.

-for WASHINGTON the third letter of the password is G.

can you deduce the original algorithm for the 3rd letter?

Ahh, for those (unplayed) states,

that for inputs of at least seven letters, use the seventh letter as the 3rd character

is still true. But it doesn't help me get to the ABORT solution any better.

Edited October 27, 2010 by Cherry Lane

[Guest]

Original algorithm for character 3 is not that simple, but it is indeed impossible to distinguish from the proposed algorithm in the values seen so far.

There are only 7 states/commands (which have not been played) which actually contradict the proposed rule: "3) Last letter if command length is odd, otherwise 2nd to last".

However, it may be impossible to guess without seeing these states so I assume there is no way the original hash algorithm could be reconstructed - Occam's Razor always favors simplicity.

However, taking into account that:

-for WISCONSIN the third letter of the password is S.

-for WASHINGTON the third letter of the password is G.

can you deduce the original algorithm for the 3rd letter?

Looks like Cherry Lane was right after all!

The rest is correct, or more clearly dependencies of the characters in the password to the unknowns is correct.

Again as few states have been played, it might or might not be possible to correctly distinguish unknown1 and unknown2 (as is the case with the 3rd character-spoiler above).

IMHO, this was generally the case in classic cryptography: being able to read at least some of the encrypted messages may count as breaking an encryption algorithm for practical purposes, but does not necessarily be enough to reveal the actual algorithm.

Feel free to give us a few more examples if you think it would help. I'm still stumped!

[araver]

Well, I was left with the same unknowns as you, plus a problem with the third character.

I missed the last/second to last bit. Instead I was working with: is the seventh character for every input of at least seven letters, and some other character if less than seven. But there was no consistency for those less than seven. Interesting that for every input of at least seven characters, the seventh one ended up being correct.

cannot constitute a full rule since there is a small number of states with less than seven letters. It is true by pure coincidence (seven and last or second to last characters coinciding in states)

Why it contradicts the Game Rules: According to the game rules I was not allowed to use anything that does not appear in at least 50% of the cases. There are only 12 commands with less than 7 characters (4,5,6). So I cannot choose one rule for more than 7 characters and another rule for 6 characters or less - that would be cheating the rules. I must use the same deterministic rule for all cases.

BTW, If the situation were reversed, if one thought he had a rule for less than 7 or less than 8 characters, one could always try it on ABORT and see the result. Doesn't hurt

[araver]

Looks like Cherry Lane was right after all!

Yes,

between 7 to 13 letters. If different states were played (for example no states with 11 or more characters), her rule would have been flawless ... except for commands with 4,5,6.

[Guest]

I'm at the same point you and CL are at, but one thing I did notice was that for "Unknown1":

If true, no consonants will be consecutive to each other. It's not an equivalence because MAINE is false, so there's obviously more to it than that. But if you look, every time the consonants and vowels alternate, it's a 1. Then OHIO and HAWAII preclude that from being the solution.

Maybe double vowels are only allowed at the end? OREGON (false) remains as a counterexample, but I bet you're not far off the answer.

[Guest]

cannot constitute a full rule since there is a small number of states with less than seven letters. It is true by pure coincidence (seven and last or second to last characters coinciding in states)

Why it contradicts the Game Rules: According to the game rules I was not allowed to use anything that does not appear in at least 50% of the cases. There are only 12 commands with less than 7 characters (4,5,6). So I cannot choose one rule for more than 7 characters and another rule for 6 characters or less - that would be cheating the rules. I must use the same deterministic rule for all cases.

BTW, If the situation were reversed, if one thought he had a rule for less than 7 or less than 8 characters, one could always try it on ABORT and see the result. Doesn't hurt

Is your rule that you count 7 characters along, and if you hit the end you just alternate between the last 2 characters?

[araver]

OK, since the discussion is heating up, I'll refrain from any hints.

-------------------------------------------------------------------------------

After stopping the system, the successful Hacker finds in the Evil Mastermind's abandoned lair an alphabetical list with some of the next passwords. As he tries to unravel the mystery of the algorithm, he shares the list with the community:

ALABAMA - A0A4L2A5

ALASKA - A0K3L1S3

ARIZONA - I0A4R2I5

ARKANSAS - K1A3A3K4

CALIFORNIA - L1R5C0I5

DELAWARE - L0R4E3A4

FLORIDA - O1A3F2O4

GEORGIA - O1A4G2O5

ILLINOIS - L1I4I3L5

KANSAS - N1A2K1N3

KENTUCKY - N0K2E3T2

MASSACHUSETTS - S0S4A3S4

MICHIGAN - C1A3M3C4

MINNESOTA - N0O4I4N4

MISSISSIPPI - S0I4I1S5

MISSOURI - S0R4I3S4

MONTANA - N0A3O2N4

NEWHAMPSHIRE - W0R4E2H4

NEWJERSEY - W1S3N4J3

NEWMEXICO - W1I4N4W5

Some states are still missing, but maybe the critical mass of information has been reached?

Edited October 27, 2010 by araver

[araver]

Is your rule that you count 7 characters along, and if you hit the end you just alternate between the last 2 characters?

Nope.

But that is indeed the simplest extension of Cherry Lane's observation to a full rule.

I still think that such a rule - expressed as an IF(C(x)) THEN A(x) ELSE B(x) rule - contradicts (at least the spirit of) the original Game Rules if the B branch is less than 50% than the number of cases.

If A(x) is constant I do not think that you can guess the algorithm B(x) due to a very small number of occurrences which is why I do not feel it is "practically" breakable in this game.

Edited October 27, 2010 by araver

[Guest]

Nope.

But that is indeed the simplest extension of Cherry Lane's observation to a full rule.

I still think that such a rule - expressed as an IF(C(x)) THEN A(x) ELSE B(x) rule - contradicts (at least the spirit of) the original Game Rules if the B branch is less than 50% than the number of cases.

If A(x) is constant I do not think that you can guess the algorithm B(x) due to a very small number of occurrences which is why I do not feel it is "practically" breakable in this game.

I agree, and looking at MASSACHUSETTS, MISSISSIPPI and NEWHAMPSHIRE this is evidently not so simple. They seem to follow the rule as I originally stated it. Intriguing...

[Guest]

Well, MICHIGAN, FLORIDA, CALIFORNIA and others all violate the rule I noticed about separated consonants, so it seems to have been something of a fluke.

Edit: I'm wondering if this algorithm breaks octopuppy's stipulation that the rule be easy to process in your head...

Edited October 27, 2010 by dawh

[araver]

Nope.[...]

Later edit (decided this part does not need spoilers - it's open and open to discussion).

I still think that such a rule - expressed as an IF(C(x)) THEN A(x) ELSE B(x) rule - contradicts (at least the spirit of) the original Game Rules if the B branch is less than 50% than the number of cases. If A(x) is constant I do not think that you can guess the algorithm B(x) due to a very small number of occurrences which is why I do not feel it is "practically" breakable in this game.

The argument above holds with one exception - If by chance the ABORT command is on the most probable branch, it can still be guessed because guessing does not hurt *that much* in the game.

when I was making the algorithm, even if I implemented a rule which might make an unbalanced tree of decisions, I checked that at least the ABORT command is on one of the most frequent branches.

I did not realize that doing this can lead to brute force attacks early in the game. Even if the rule is obscure - few boolean choices can always be attacked by brute force. IMHO, brute-force attacks are also not in the spirit of the game, but there is no natural protection against those

Also, I found no way to patch the algorithm up in time 'cause I was anxious to start the game

Unrelated: the 40 seconds restriction (and also the fact that you don't see the password letters so you need to recompute previous variables/letters) does impose serious constraints on the obscurity of a rule. Again, IMHO, it should be even simpler to decide these booleans if they are used more than once.

[araver]

Edit: I'm wondering if this algorithm breaks octopuppy's stipulation that the rule be easy to process in your head...

What if each of the unknown booleans takes no more than 1 second to decide?

[araver]

Well, MICHIGAN, FLORIDA, CALIFORNIA and others all violate the rule I noticed about separated consonants, so it seems to have been something of a fluke.

Yes, it's not the intended algorithm but I think it would be an interesting valid rule for an algorithm in a different game as ABORT does not have separated consonants and falls on the most frequent branch. It might still raise some objections depending on each player's view on the game rules.

[Guest]

Yes, it's not the intended algorithm but I think it would be an interesting valid rule for an algorithm in a different game as ABORT does not have separated consonants and falls on the most frequent branch. It might still raise some objections depending on each player's view on the game rules.

Maybe the consistency rule isn't working quite as I intended it. When writing that I was thinking in terms of operations which are used repeatedly (as in the first game). But here each operation applies only once within each clue and the 50% rule pretty much rules out any IF A THEN B ELSE C operation if applied only once per clue (since if B occurs more than half the time, C won't, and vice versa). That's probably too restrictive. What matters is that the hackers get to see enough examples of the rule that they can deduce it, so I wouldn't get hung up on that too much. It probably needs to be worded differently.

As to whether brute force attacks are appropriate, my inspiration for this game is the real-life problem of creating secure passwords as a hash of website names. Such a system needs to be resistant to a little guessing, since a hacker who has obtained some of your passwords may well try a few likely-looking combinations without knowing the entire system. IMO that is in the spirit of the game as it's part of the challenge to build in resistance to that. Plus, it would take enormous restraint not to make guesses knowing the password could only be one of four! It is, after all, a race between the hackers. The brute force applicable is limited by the fact that they only get one guess for every 3 states you destroy.

Unrelated: the 40 seconds restriction (and also the fact that you don't see the password letters so you need to recompute previous variables/letters) does impose serious constraints on the obscurity of a rule. Again, IMHO, it should be even simpler to decide these booleans if they are used more than once.

There is no need to recalculate anything you can keep track of in your head. For most people that would not be very much, but still, reusing a couple of booleans is fine, and cuts down on thinking time.

[araver]

Maybe the consistency rule isn't working quite as I intended it. When writing that I was thinking in terms of operations which are used repeatedly (as in the first game). But here each operation applies only once within each clue and the 50% rule pretty much rules out any IF A THEN B ELSE C operation if applied only once per clue (since if B occurs more than half the time, C won't, and vice versa). That's probably too restrictive. What matters is that the hackers get to see enough examples of the rule that they can deduce it, so I wouldn't get hung up on that too much. It probably needs to be worded differently.

I agree.

As to whether brute force attacks are appropriate, my inspiration for this game is the real-life problem of creating secure passwords as a hash of website names. Such a system needs to be resistant to a little guessing, since a hacker who has obtained some of your passwords may well try a few likely-looking combinations without knowing the entire system. IMO that is in the spirit of the game as it's part of the challenge to build in resistance to that. Plus, it would take enormous restraint not to make guesses knowing the password could only be one of four! It is, after all, a race between the hackers. The brute force applicable is limited by the fact that they only get one guess for every 3 states you destroy.

There is no need to recalculate anything you can keep track of in your head. For most people that would not be very much, but still, reusing a couple of booleans is fine, and cuts down on thinking time.

I know the real-life problem is often solved with brute-attacks, no argument for me there. This however is a small scale model - 51/3=17 - at most 16 guessing rounds.

I still would have liked to "patch" it up a little. I would have been much happier designing something that does not suggest a brute-force attack is feasible e.g. the algorithm in the first game. As I said, I was too anxious to start the game

[Guest]

I know the real-life problem is often solved with brute-attacks, no argument for me there. This however is a small scale model - 51/3=17 - at most 16 guessing rounds.

I still would have liked to "patch" it up a little. I would have been much happier designing something that does not suggest a brute-force attack is feasible e.g. the algorithm in the first game. As I said, I was too anxious to start the game

I haven't made much progress cracking your algorithm, but I do think I have a workable one of my own. Not sure if I would want to host it next since I'm not usually around much on Thursday evenings (or at all). I still have to encode everything and take another look at it, but I think it holds to octopuppy's guidelines and it's fairly easy to calculate in your head, so long as you know what it is.