Imposter Puzzle

[Sandor]

Hmm, actually, we need stronger physical commitment to make the system secure. The Thurns can set up a perfect real world MITM attack, and any security system has to take this into account.

So you're going to need end-to-end encryption as well as authentication. You all are just trying to re-implement SSH, aren't you?

[WarDaft]

Hmm, actually, we need stronger physical commitment to make the system secure. The Thurns can set up a perfect real world MITM attack, and any security system has to take this into account.

So you're going to need end-to-end encryption as well as authentication. You all are just trying to re-implement SSH, aren't you?

SSH isn't going to be enough. You'll need physical components to the security as well.

[mfb]

Well, if you encrypt every part of your communication, it is secure against man-in-the-middle attacks by Thurns.
You can never be sure about the identity of your meeting partner. But you can be sure that only the proper other member of your organisation can read your messages.

[ejv]

But the thurn wouldn't know your password, so the member, seeing this, would know that they had just given their password to a thurn, and could go straight to you to remedy the situation. Aside from being present at every meeting, I don't see how a thurn could break the system outright...

[mfb]

>> and could go straight to you to remedy the situation
How do they identify "you", and how do "you" identify them?

If any member has a private meeting with a single other member (or Thurn) and reveals all his knowledge (his password), he has nothing left which the Thurns do not have.

[redrogue]

Spoiler:

If you do, however, incorporate the date/time into your algorithm, the plan works better for the short run. The Thurns will eventually break any formulaic code with enough data points. However, if meetings are never held on the same date or at the same time of day, and if they aren't very frequent, and if any given meeting is fairly small, and of course if the scratch-paper is burned immediately and never viewed by anyone but the writer, the Thurns will probably have to wait a while before cracking it.

So, do this:

Spoiler:

Incorporate a variable that changes every day, but is easy to reference.

Have a public test, rather than test your neighbor privately, to avoid false accusations.

Change the algorithm every once in a while.

In detail...

Spoiler:

At the first meeting, determine a group salt and a secret variable that changes every day. For instance, lets say "AllThurnsMustDie" and that day's (or most recent) DOW opening as a nod to geohashing.

At each subsequent meeting, the organizer announces a public one-time code word for that meeting. Everyone busts out their laptop and secretly computes an encrypted string from the code word concatenated with the group salt and the daily-changing variable.

To test, everyone writes down the first character of their computed string and reveals them at the same time. I suggest a big piece of paper and a sharpie. Repeat for each subsequent character in the string in turn.

It should be pretty obvious to humans which are the thurns. Use bullets.

Have your meeting thurn free.

To prevent the thurns from getting enough data points, every once in a while summon every member to one big meeting and change the salt and random variable to something else. 'Ok guys, last item of business, we are going to change from "AllThurnsMustDie" to "DieThurnsDie" for all future meetings, and instead of the DOW opening, use the temperature Celsius at Greenwich Observatory from the most recent midnight.'

That may not be the best method of doing a zero knowledge proof http://en.wikipedia.org/wiki/Zero-knowledge_proof, but it would do a pretty good job

[Bolzan]

http://xkcd.com/936/

This comic has quite a good answer to it.

Invent ten words that make no sense to anyone EXCEPT your own members. Swear them to secrecy and let them be on their merry way.

When they encounter another agent, bluntly ask "What is the passcode?" ensuring that they are alone.

Assuming that a four word password with known words takes about 550 years at 1000 guesses/second, ten made up words should take much longer, millenia, even. If the Thurns only had a knowledge of common words, it'd work even better.

Let's say the Thurns had a supercomputer specifically made for this. Just switch the order of the words every week and completely change the passcode every month to ensure maximum efficacy.

This may not be the perfect solution, but it sure as hell would work for a really, REALLY long time.

Failsafe: Provide each agent with a coded version of the passcode. If the Thurns capture one of the agents, ensure every agent is issued with a painless suicide pill that could be administered discreetly, regardless of outside interference (haven't thought of this bit yet)

[mward]

http://xkcd.com/936/
When they encounter another agent, bluntly ask "What is the passcode?" ensuring that they are alone.

How does the agent know that the being who is asking for the passcode is another agent and not a Thurn trying to find the password?

[tomtom2357]

Well, in my idea, for every pair of people, you have a password for each of them. Also, each person is embedded with a tracking chip, that would kill the person if it is taken out. This way, if the thurn did not have the tracking chip in him, he is killed immediately, without finding out the password. If the thurn did have the chip in them, they survive long enough to find out the password, but then they die when they say the wrong password, and the normal person now knows that the real other person is dead, so the password is useless to the thurns.

However, this is also inefficient, because it makes everyone remember 2(n-1) passwords, 2 for each of the n-1 other people (the one they will say, and the other that the other one will say).

[m0ffle]

Spoiler:

Initial meeting (safe, as it is the first)- everyone says their names, real information is shared; it is determined, that if captured, an agent will reveal that they will tell the aliens their real name. It is also determined that the next meeting everyone will say fake names. Second meeting "say your name"- everyone says a fake name, aliens are easily identifiable, we feed them fake info. (this was mentioned in the first meeting)The cycle is reversed from this point, as planned, if captured- the agent says a fake name to the aliens, and at the meeting they say their real names. the cycle reverses again and again, continuing as such. Aliens are either shot (after a few false questions, in order to throw them off the trail of it being the name that counts- so in their final moments they do not tele-communicate.) or fed fake information (to distract them, they think that they have been undetected.)

[snowyowl]

Moffle, as soon as the aliens work out that it's the names that are important (which will be the moment they think "hey, why do they say their names in the meeting if they all know each other, and why do their names change every other meeting?), they will realise that the agents are sometimes giving their real names and sometimes giving fake names. They will send two shapeshifters to the next meeting; the first one gives the real name of the person he's impersonating, the second gives a fake name. One of the two will be accepted.

[nishank]

This comic can have an even comical answer.
Do nothing.
Invite all members to a first meeting and ask them to do nothing.
Therns might have telepathy, anything.
can't figure out nothing till eternity.,

[mward]

This comic can have an even comical answer.
Do nothing.
Invite all members to a first meeting and ask them to do nothing.

That is not going to enable you to achieve your aim of destroying the Thurns!

Which suggests that a secondary objective for the communication system might be one which:
(a) encourages Thurns to attempt to infiltrate your meetings, and
(b) has a very good chance of catching them if they do infiltrate
so that you can destroy as many Thurns as possible.

For example, the system might involve a sequence of passwords where it appears possible to guess the next password, but the guess reveals the guesser to be a Thurn, who can then be destroyed.

[madd0ct0r]

while it cheats a little on the original premise, I would look at some physical aspect that the Thurns can't replicate - such as blood tests, allergies or such.
(if Thurns are similarly affected by alcohol, would they loose their self control over shapeshifting when drunk? Disadvantage is that if all meetings are under the influence is that the society may not be very effective...)

Spoiler:

the puzzzle's a pretty clear restatement of computer to computer communication in an open network so the public/private key method, but that'll be a little difficult to resolve in your head. Matrix transpostions are pretty good, but again still hard.

I'll have to think about this some more...

[nishank]

Well say" do nothing", in first meet.

Hide in plain sight.
Thrun will see you/ since you dont do nothing it sees nothing, it will do something eventually over time.
Kill the thurn that does something .
Well this is about the most robust things can get.

[Bolzan]

http://xkcd.com/936/
When they encounter another agent, bluntly ask "What is the passcode?" ensuring that they are alone.

How does the agent know that the being who is asking for the passcode is another agent and not a Thurn trying to find the password?

The asker will have to say how many words are correct and whether their order is correct. If there are any incorrect words or the incorrect order, the asker will know its a Thurn they're talking to and if the recipient of the question gives the wrong passcode, the asker will know the recipient is a Thurn. This way, both of them have to be correct for the meeting to commence.

Even with telepathy, since the words are randomly scrambled and generated, telepathy won't really help the Thurns much.

Of course, this is based off the assumption that the Thurns can only meet so many people each day since any higher and it'd get suspicious. The agents could have a program at HQ that tells others which agents have already been asked.

[Cervisiae Amatorem]

I have some meta questions.

Can we expect the Thurns to have advanced reasoning and sophisticated computing power at their disposal? Or are they limited to instant telepathy? I presume they have a perfect collective memory, so that anything they learn about our authentication methodology remains forever known by all of them.

Do the Thurns place any value on their own lives? Does the HTIC (Head Thurn In Charge) place any value on the lives of his soldier Thurns? I'm wondering if the Thurns can be expected to suicidally throw themselves on swords in a brute force attack to infiltrate, or if they will attempt to infiltrate with clever means.

Is there an acceptable human : Thurn loss ratio? Meaning do we sacrifice 10 humans to kill 1 Thurn? Or 1 human for 1 Thurn? Or 1 human for 10 Thurns? How about from the Thurn standpoint?

[krogoth]

Read to other members of your team the funniest joke in the word to each other in another language as the password.

When they decipher it they all die.
Monty python skit style
(the joke cause's you to die laughing apon hearing it)

lesser attempts at resolution

Spoiler:

**
Human1:How do I know I can trust you?
Human2:Walks away.
Human1:Walks away.

Thurn1:How do I know I can trust you?
Human1:Walks away.
Thurn1:

Human1:How do I know I can trust you?
Thurn1:Any answer that suggests knowledge or a guess
Human1:*shoots Thurn1*

Thurn1:How do I know I can trust you?
Human1:*walks away*
Notes:
This only applies to people in the group, The details if the group can't be passed on to other members.
Thurns can't exactly be hunted, but can't get any information from the group.
**
The only real way I can think is that you need to deliberately pass false knowledge to the Thurns. That cause's them to all simultaneously self terminate.

Human1:You remember our secret about how if all the Thurns shot themselves all the same time we would die they would?
Human2:*nods*
**
Collect all people in the world into rooms.
with agents watching, take people out 1 by one, and play the brown noise to them.

when a ton of people sh*t them self all at the one time, shoot them.
**

[madd0ct0r]

that's clever...

a variant on that might be useful for checking if there's more then one thurn present at the meeting - they can't turn their telepathy off. So split the meeting down into pairs...

[willaaaaaa]

Do Thurns have emotions?

[Pressed Bunson]

My solution isn't quite as impressive as any of the others, and meetings of more than two people isn't possible, but:

Spoiler:

Find a substance which is poisonous to Thurns but not humans (I'm assuming that a) such a substance exists and b) Thurns can only change their appearance, not their biological structure) Every time there is a meeting of two people, each person must force the other person to ingest the substance. Wait until the point where Thurns would be killed by it before divulging any crucial information.

[krucifi]

Spoiler:

Only way i can see it being done requires the memorizing of a vast amount of passwords, the number of members who join the meeting,. which change at every meeting but are decided upon there and then.
but perhaps someone can reduce the numbers with a bit of fine pruning
Also i am assuming the very first group meeting will be thurn free otherwise the plan is lost
Lets say there are ten members. then there will be ten passwords all of them know but are told to memorize one each
At the end of the meeting they will be assigned a random number (out a hat this is one that noone will know BUT the member) from 1-10 (number of members)
The beginning of the next meeting, in the order of the random number pulled out the hat, they must recite their passwords which they all know.
If the meeting has a thurn. then said thurn will get his password wrong and the order.
he will be killed, then the recitation will continue, if no other thurns are found, then new passwords are formulated and new orders to recite them.

I think this will work for most cases but if a meeting has thousands of members then there might be a problem.

[Lynx Cat]

Guys, guys - you are all talking about killing the Thurns or otherwise taking visible measures when they're found out. Remember that whatever one Thurn knows, all others know, so when that happens, you'll have compromised at least part of your algorithm, as well as the knowledge that you know about the infiltration. I'd suggest the following instead: (assuming, as usual, that the first meeting is Thurn-free, that the entire plan is laid out in the first meeting, and all relevant information is exclusively memorized, not recorded anywhere)

Spoiler:

1) In the first meeting, each member is given an individual password, that can be verified as correct by each other member privately. Use whichever means are appropriate to improve the passwords' security and the checking process. The passwords are assumed to be unguessable.

2) The place and time for the next meeting is determined.

3) (still in the first meeting) A backup place and time for meeting is determined. (The time should be relative, i.e. "X days/hours after the current meeting", so that it can be used at any time.) Each member also receives a backup password, which can also be confirmed by others. If you're worried about an infiltration to your backup meeting, you can set up one or two additional backup meetings, with an equal number of additional passwords.

4) At each meeting, each member gives his or her password, which is verified. Passwords are given simultaneously, to avoid problems.

5) If the meeting is determined to be Thurn-free, it progresses as normal, arrangements are made for the next meeting, and new passwords are given.

6) If anyone shows a password that's recognized by other members as incorrect, everyone pretends it's correct, and the meeting proceeds apparently as usual, except that everything discussed is misinformation. The place/time and passwords for the next meeting are given as usual.

7) If infiltration occurs as above, the organization convenes again as per the backup scheduling and with the backup passwords. Once the backup passwords are verified and everyone is determined to be legitimate, the backup information is changed. From then, it proceeds as normal, only at a separate track from the "main" meetings which are known to be infiltrated.

8 ) If there's an infiltration in a "backup" meeting, proceed as 6 above and create a new "track". Optionally, you could take this opportunity to pretend you found out about the first infiltrator and take it out somehow, thus giving the Thurns a false sense of security and simplifying things for your group.

This method allows you to keep feeding the Thurns misinformation, which helps your cause, and maybe even get information out of them by carefully steering the conversation in meetings you know are infiltrated. You can also implement bogus security measures in meetings you know are infiltrated, in order to further confuse things. This way, the Thurns never get to learn your secret plans, and most of your security scheme remains hidden, while giving them the impression they're one step ahead of you, while it's actually the other way around. The key is to go into "bogus" mode and fall back into the backup plans without any need to coordinate these actions, since they've been planned out in advance.

There's also another problem you folks have been overlooking - prior to each meeting, all electronics should be placed in a box that's completely sealed for light, sound and electromagnetic waves, and the premises and each attendant should get a thorough bug sweep. Infiltration might happen in ways that are not obvious at first...

[WarDaft]

That's compromised as soon as you have a single backup meeting infiltrated. You'd need an infinite layering of backup plans generated at your first meeting. Which is of course, quite possible. But then, why not just use those as your typical meetings?

In fact, if we want to be particularly abstract about these things, and not put an upper limit on the number of meetings we mind having to defeat the Thurns, we can do even better, and have people give wrong information half the time anyway. Then only one out of 2^{#conspirators} meetings will potentially contain information the Thurns even want. The computational complexity of discerning the password scheme also shoots up exponentially, because the Thurns now have to figure out which passwords actually represent information useful to actually break the scheme.

[Lynx Cat]

That's compromised as soon as you have a single backup meeting infiltrated. You'd need an infinite layering of backup plans generated at your first meeting. Which is of course, quite possible. But then, why not just use those as your typical meetings?

That's why I suggested setting up one or two additional backup meetings, aside from the initial one. I'm going from the principle that the chance of infiltration in more than one backup meeting in a row drops drastically with each additional infiltration, since the Thurns would pretty much have to chance upon these meetings by dumb luck (since they're not agreed upon anywhere Thurns can hear). Because, if the Thurns regularly infiltrate the majority of meetings even without previous information, then the resistance is really screwed anyway

I do admit, though, that my approach is much more practical than logically formal. Logically, the possibility of many successive infiltrations in backup meetings would indeed require a number of backup arrangements tending toward infinity. I'm still puzzling over how to develop a system that's logically airtight, both in detecting Thurns and in making sure they don't gather any information about the validation method (or secret plans) before they die. This is a really interesting puzzle, and one with great potential practical applications in the realm of information security.

[dudiobugtron]

I agree, this is a great puzzle! I've spent way too long thinking about it and not getting anywhere.

It seems like there are two different ways people have been trying to approach the puzzle:

Spoiler:

One is to try and find a method of checking for Thurns that is impossible for the Thurns to break, and the other is to find a method of checking for Thurns that works even if the Thurns know exactly how it works.

I wonder, for the second approach, whether the easiest way is just to find some way that Thurns can't perfectly imitate humans, despite their shapeshifting abilities. Eg: maybe we could just ask them to say "Shibboleth".

[foaly]

Although not realistic a save way would be:

Spoiler:

At the first meeting create a completely new language.
Ask an easy but completely random question every time when you need an identification check.
Someone not knowing the language will be killed.
The Thurns will need more data points to learn a new language then they will be able to get, if in doubt, new language every year.

[dudiobugtron]

Oooh, I just thought of another idea.

Spoiler:

At the first meeting (which is presumed to be safe?) agree on your plan of action, and make sure that it involves none of the members ever meeting each other again. Therefore, if you ever meet another member, you'll know they're actually a Thurn.

[Katt]

The simplest solution is:

Spoiler:

Get everyone to say the password one letter per person.

[Katt]

An addition to the solution:

Spoiler:

There is one hole in this solution, namely that when an impostor is spotted he and his peers will already know the part of the password that the people that preceed him will say. There are multiple solutions of this. For example after the impostor is killed, the group can arrange that next time they will start the password from the symbol that he doesn't know. That can be communicated in some way to all of its members (or even if someone is left unnotified, he could pretty much pick it up).
Of course an occasional meeting between all members should be held for adding symbols to the password.

And yes, I know that theoretically an impostor can manage to be the first in the row, and cause confusion, among everyone, but that is a little far fetched for me.