[Guest]

One player plays the Evil Mastermind (that's me) 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 either one third of the clues posted at any given time, or 10 clues posted. 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 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" for 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!)

PENNSYLVANIA = N6432347

MICHIGAN = I4964346

KENTUCKY = E5297679

Edited November 11, 2010 by Vineetrika

[araver]

Ok, it is less far-fetched once you can actually see

... a recurrence.

First character

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

n = number of distinct vowels

The n-th letter in command is the first character of the password.

Second to eight character of password

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

For the i-th letter of the password - i=2..8 - denoted password [ i ].

Find the (n+i-1) letter of command (considering that command is read continuously from left to right)

If the letter you found is <=M then x=0 else x=1

If you finish the word once before finding this letter alpha = nr of letters of command.

Else If you finish the word the second time before finding this letter

alpha

= -1

.

Else

alpha

=

0.

Define previous digit of password (password[i-1]) as 0 for i=2 and actual previous digit of password for i=3..8

Then

 password[i] = WeirdMod(password[i-1]+n+i+x[i]-alpha[i]) 

where WeirdMod gives shifted 1..9 output instead of 0..8 normal modulo operation.

WeirdMod(a)=(a-1)%9+1

Still pondering at a more natural way to describe this.

So, if it is correct and we move on to the next CtC challenge, I had a question: I also have developed an algorithm, I'm not sure of the difficulty though. So if it at least sounds less difficult than the one octopuppy suggests ... should we do it next or after?

Edited November 21, 2010 by araver

[Guest]

Ok, it is less far-fetched once you can actually see

... a recurrence.

First character

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

n = number of distinct vowels

The n-th letter in command is the first character of the password.

Second to eight character of password

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

For the i-th letter of the password - i=2..8 - denoted password [ i ].

Find the (n+i-1) letter of command (considering that command is read continuously from left to right)

If the letter you found is <=M then x=0 else x=1

If you finish the word once before finding this letter alpha = nr of letters of command.

Else If you finish the word the second time before finding this letter

alpha

= -1

.

Else

alpha

=

0.

Define previous digit of password (password[i-1]) as 0 for i=2 and actual previous digit of password for i=3..8

Then

 password[i] = WeirdMod(password[i-1]+n+i+x[i]-alpha[i]) 

where WeirdMod gives shifted 1..9 output instead of 0..8 normal modulo operation.

WeirdMod(a)=(a-1)%9+1

Still pondering at a more natural way to describe this.

So, if it is correct and we move on to the next CtC challenge, I had a question: I also have developed an algorithm, I'm not sure of the difficulty though. So if it at least sounds less difficult than the one octopuppy suggests ... should we do it next or after?

I don't think that's quite it, though I am confused. Let's see what Vineetrika says. An easier way to check if you're on the money might be to just encode a few random words!

I think it's best if you host the next game, I'm a bit busy at the moment.

[araver]

I don't think that's quite it, though I am confused. Let's see what Vineetrika says. An easier way to check if you're on the money might be to just encode a few random words!

Better than random, these are the last states according to the algorithm I stated before:

ALABAMA - A3739768

ARKANSAS - A4842191

COLORADO - O4186568

CONNECTICUT - N6444583

DELAWARE - E4975557

FLORIDA - O6319251

GEORGIA - R6435841

HAWAII - A5175716

KANSAS - A5287938

LOUISIANA - I7545683

MAINE - I6358396

MARYLAND - A5286668

MINNESOTA - N6556793

MISSOURI - S6433358

NEBRASKA - E4176558

OKLAHOMA - K4965447

RHODEISLAND - D6444582

VERMONT - E5187714

WASHINGTON - S5219136

WYOMING - Y5176583

I think it's best if you host the next game, I'm a bit busy at the moment.

Then I will open a next CtC challenge soon, later today, while waiting for Vineetrika.

Edited November 21, 2010 by araver

[Guest]

Better than random, these are the last states according to the algorithm I stated before:

ALABAMA - A3739768

ARKANSAS - A4842191

COLORADO - O4186568

CONNECTICUT - N6444583

DELAWARE - E4975557

FLORIDA - O6319251

GEORGIA - R6435841

HAWAII - A5175716

KANSAS - A5287938

LOUISIANA - I7545683

MAINE - I6358396

MARYLAND - A5286668

MINNESOTA - N6556793

MISSOURI - S6433358

NEBRASKA - E4176558

OKLAHOMA - K4965447

RHODEISLAND - D6444582

VERMONT - E5187714

WASHINGTON - S5219136

WYOMING - Y5176583

I'd agree with that except you miscounted the vowels on a couple. Looks like you got it!

[araver]

I'd agree with that except you miscounted the vowels on a couple. Looks like you got it!

at least these two:

KANSAS - K3852136

MARYLAND - M3852999

Thank you for checking

[Guest]

Ok, it is less far-fetched once you can actually see

... a recurrence.

First character

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

n = number of distinct vowels

The n-th letter in command is the first character of the password.

Second to eight character of password

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

For the i-th letter of the password - i=2..8 - denoted password [ i ].

Find the (n+i-1) letter of command (considering that command is read continuously from left to right)

If the letter you found is <=M then x=0 else x=1

You got me up to this point and then I lost you

If you finish the word once before finding this letter alpha = nr of letters of command.

Else If you finish the word the second time before finding this letter

alpha

= -1

.

Else

alpha

=

0.

Define previous digit of password (password[i-1]) as 0 for i=2 and actual previous digit of password for i=3..8

Then

 password[i] = WeirdMod(password[i-1]+n+i+x[i]-alpha[i]) 

where WeirdMod gives shifted 1..9 output instead of 0..8 normal modulo operation.

WeirdMod(a)=(a-1)%9+1

Still pondering at a more natural way to describe this.

I am not sure I understand the alpha and weirdword concept but my logic is ...

Define previous digit of password (password[i-1]) as 0 for i=2 and actual previous digit of password for i=3..8

password = password[i-1] + i + x

Please let me know if this is not making sense. I hope you enjoyed solving this one.

[araver]

You got me up to this point and then I lost you

I am not sure I understand the alpha and weirdword concept but my logic is ...

Define previous digit of password (password[i-1]) as 0 for i=2 and actual previous digit of password for i=3..8

password = password[i-1] + i + x

Please let me know if this is not making sense. I hope you enjoyed solving this one.

I enjoyed it very much, thanks for the challenge

Well, I can explain how I arrived at my rather complicated formula because of IOWA. This state systematically broke every relation I was able to come up ...

IOWA - W5727359

Number of distinct vowels n=3.

First character of password is W.

Writing the command starting from 3rd position, repeating the command until I get a 8-letter word:

WAIOWAIO

Idea 1

-------

Now trying the simple recurrence: password = password[i-1] + i + x

with password[1]=n

Next character is A <=M so x[2]=0.

password[2] = password[1] + 2 + x[2] = 3 + 2 + 0 = 5

Next character is I<=M so x[3]=0.

password[3] = password[2] + 3 + x[3] = 5 + 3 + 0 = 8 !!!! instead of 7

Next character is O>M so x[4]=1.

password[4] = password[3] + 4 + x[4] = 7 (corrected) + 4 + 1 = 12.

Next character is W>M so x[5]=1.

password[5] = password[4] + 5 + x[5] = 2 + 5 + 1 = 8 !!! again difference

Idea 2

-------

So to patch this up, I came with the idea of adding n

password = password[i-1] + n + i + x

with password[1]=n

This actually worked for other words except that it gave somewhat shifted results when you get a password>10.

E.g. it would give 7,8,9 where it should, but it would give 10 instead of 1, 11 instead of 2, etc.

Idea 3

-------

So to patch this up, I came with a weird modulo function that would shift the output as needed (since Mod(a)=a%9 gives 0..8 output)

Weirdmod(a) = (a-1)%9+1. It gives what I needed: WeirdMod (x)=x for x=2..9 and WeirdMod(10)=1, WeirdMod(11)=2 and so on.

Again it worked for the first 2 characters for every command, except IOWA

See below.

Next character is A <=M so x[2]=0.

password[2] = password[1] + n + 2 + x[2] = 0 + 3 + 2 + 0 = 5

Next character is I<=M so x[3]=0.

password[3] = password[2] + n + 3 + x[3] = 5 + 3 + 3 + 0 = 11. WeirdMod(11)= 1 instead of 7.

Next character is O>M so x[4]=1.

password[4] = password[3] + n+ 4 + x[4] = 7 (corrected) + 3+4 + 1 = 15. WeirdMod(15)=6 instead of 2

Idea 4

-------

So to patch idea 4 up, I came with the idea of alpha. After you pass the beginning of the commands, you substract the nr of letters in command.

E.g. for IOWA - W5727359

The running command (starting from 3rd position, repeating the command)

WAIOWAIO

and alpha is

004444

It becomes 4 (nr of letters in command) when it reaches the beginning of the word (first I in case of IOWA).

Idea 4 password = WeirdMod(password[i-1] + n + i + x - alpha)

with password[1]=0

Next character is A <=M so x[2]=0.

alpha[2]=0

password[2] = WeirdMod(password[1] + n + 2 + x[2] -alpha[2])= WeirdMod(0 + 3 + 2 + 0 - 0) = WeirdMod(5)=5

Next character is I<=M so x[3]=0.

alpha[3]=4 since we started the word again.

password[3] = WeirdMod(password[2] + n + 3 + x[3] -alpha[3])= WeirdMod(5 + 3 + 3 + 0 - 4) = WeirdMod(7)=7 (correct this time).

Next character is O>M so x[4]=1.

alpha[4]=4 since we started the word again.

password[4] = WeirdMod(password[3] + n + 4 + x[4] -alpha[4])= WeirdMod(7 + 3 + 4 + 1 - 4) = WeirdMod(11)=2 (correct this time).

Next character is W>A so x[5]=1.

alpha[5]=4 since we started the word again.

password[5] = WeirdMod(password[4] + n + 5 + x[5] -alpha[5])= WeirdMod(2 + 3 + 5 + 1 - 4) = WeirdMod(7)=7 (correct this time).

And so on...

I understand that it's not the function either of you use and it just *coincidentally* gives the same results for 8 letter passwords, but I still don't see a simple function

Can you express it in terms of a recurrence and show it step by step for IOWA?

Thank you.

[Guest]

Sorry, my logic was flawed too.

Correction 1: x

x = 1 if the letter under observation is <= M

x = 2 if the letter under observation is > M

Correction 2: formula

password = password[i-1] + n + x => where n is the position of the ith letter in the command

Correction 3:

if the password value is greater than 10, add the digits and if the sum of the digits is again greater than 10, sum the digits again .. this is recursive until you get a single digit.

I am not sure if this formula is accurate either ... so ...

IOWA - W5727359

Number of distinct vowels n=3.

First character of password is W.

Writing the command starting from 3rd position, repeating the command until I get a 8-letter word:

WAIOWAIO

password[1] = W

password[2] = 0 (prev.) + 4 (position of A in IOWA) + 1 (<= M) = 5

password[3] = 5 (prev.) + 1 (position of I in IOWA) + 1 (<= M) = 7

password[4] = 7 (prev.) + 2 (position of O in IOWA) + 2 (> M) = 11 = 1 + 1 = 2

password[5] = 2 (prev.) + 3 (position of W in IOWA) + 2 (> M) = 7

password[6] = 7 (prev.) + 4 (position of A in IOWA) + 1 (<= M) = 12 = 1 + 2 = 3

password[7] = 3 (prev.) + 1 (position of I in IOWA) + 1 (<= M) = 5

password[8] = 5 (prev.) + 2 (position of O in IOWA) + 2 (> M) = 9

[araver]

Yes, your formula is indeed correct.

Just compiled them both in a spreadsheet.

They give the same results for all commands including ABORT.

Surprisingly, the methods may yield different results for 2 and 3 letter words, but are equal for longer-than-5 letter-words and 4 letter-words, except those with 4 distinct vowels.

It seems that my WeirdMod function + alpha + constant difference in definition of x (mine's is 0..1, yours is 1..2) just gives in a more complicated way the same array you do naturally with "position of the letter in command". E.g. for IOWA 41234123 is obtained by 2 variables and one function in my case. Not sure how exactly your digit adding function (if >10) is simulated with my variables, but it seems to work.

That's why it always seemed unnatural to me. I went on on a wrong path and constructed artificial variables just to fit the data and bring me back to it. Guess this is kind of a physicist nightmare

Thank you again for the challenge ... twice

I really enjoyed first discovering my alternate-oh-so-complicated-but-still-fits-the-data-so-it-must-be-true-right theory and then your simple-oh-so-simple-how-did-i-miss-that-wait-they-both-cannot-get-the-same-results-can-they-oh-my-god-they-can-how-the-hell-is-that-possible theory.

Edited November 22, 2010 by araver