Imposter Puzzle

[tomtom2357]

Okay, the problem is as follows: You are a member of a secret organisation that is bent on destroying the Thurns, shape-shifting aliens that can take any form they choose. However, the Thurns know you're on to them, and will try to infiltrate your group every time you meet. Therefore, you have to design a system so that you will know whether you are meeting you friend, or a Thurn. The one drawback is, the Thurns are capable of telepathy, so if you discover that they are a Thurn, they will communicate all the information they have gathered so that they can work out your code. Therefore you have to come up with a system that will work forever.

[mfb]

Two solutions which came to my mind:

Spoiler:

1) Use an asymmetric encryption method. Each member i has a public key A_i which is known by all, and a private key B_i only known to them. In a meeting of 2 persons, both exchange their number i. Both generate a random string, encypt it with the public key of the other person and look whether they can decrypt it. If yes, they have the private key and are member of the organisation. If not, Thurns don't get any information about the keys: The public keys can be common knowledge anyway, the random string itself is free of any useful information. Thurns can check the identity of their meeting partner (and find a member of the organisation with this), but I assume that they don't have a reason to meet other Thurns anyway.
2) Use the algorithm of the socialist millonaire problem

[tomtom2357]

Wow, that was fast. I had a few ideas (none of them worked) that I will show below.
1. Put a tracking chip inside everyone so you know whether the person there is there or is not (and obviously if not then the person standing in front of you is a Thurn). This method is easily shot down, as the Thurns can easily capture him/her, put the chip in them instead. An interesting advantage of using this, in conjunction with a different technique, is that once you know that the other person is a Thurn, you also know that they have captured the original person.
2. Have a codename for each person, so that the Thurns would not know it. This would work for the first time, but after that the Thurns know someone's passcode (the original that they are copying), then they can trick everyone.
3. Having it attached to something random. Doesn't work, they can figure it out quick enough.
4. Changing the passcode every time you meet, doesn't work, as it could be a while before you run into the real them again.
So, your solutions work pretty well, even though I don't know enough cryptography to understand them.

[Yat]

Two solutions which came to my mind:

Spoiler:

1) Use an asymmetric encryption method. Each member i has a public key A_i which is known by all, and a private key B_i only known to them. In a meeting of 2 persons, both exchange their number i. Both generate a random string, encypt it with the public key of the other person and look whether they can decrypt it. If yes, they have the private key and are member of the organisation. If not, Thurns don't get any information about the keys: The public keys can be common knowledge anyway, the random string itself is free of any useful information. Thurns can check the identity of their meeting partner (and find a member of the organisation with this), but I assume that they don't have a reason to meet other Thurns anyway.
2) Use the algorithm of the socialist millonaire problem

Those solutions seem to be more complex than needed for the problem, because they use an individual key for each person, and they are based on the assumption that thurns know everything except the member's keys.
I think it would be easier to just

Spoiler:

agree on a function. When two members meet, the first gives a random number and the second answers the value of this function for this number, then the other way around. Without knowing anything on the function, it is not possible to determine it with only a finite number of samples extracted telepathically by the thurns at each failed attempt.

If I am not mistaken, this method is enough for the given problem.

[mfb]

Your solution requires even more:

Spoiler:

A really large number of function values, stored by each member. So large that any random collision is really unlikely within any reasonable time.
A function which can be expressed analytically (shorter than just storing a lot of its points) is easy to reconstruct with enough data points.

And my second solution just requires that all members can remember a single number.

Important theorem: All systems based on [finite knowledge and known algorithm] or [finite data transfer] can be eventually hacked by Thurns, just by chance: They can generate answers (or the knowledge) at random, eventually hitting the right one.

[mward]

If the Thurns are capable of telepathy, why do they need to infiltrate your meetings in order to discover your plans?

Spoiler:

Each member i has a public key A_i which is known by all, and a private key B_i only known to them.

How can anyone have a private key known only to them, if the Thurns are capable of telepathy?

[jobriath]

I took it as meaning that the Thurns talk amongst themselves but not humans. Our brains are too primitive to be susceptible. It would be like talking to a rock. Presumably we are hell-bent on destroying them in a fit of pique.

[tomtom2357]

I took it as meaning that the Thurns talk amongst themselves but not humans. Our brains are too primitive to be susceptible. It would be like talking to a rock. Presumably we are hell-bent on destroying them in a fit of pique.

This is the meaning I intended, otherwise it is impossible to stop infiltration.

[jonachin]

establish some kind of secret key, like a password or a handshake or what have you. at every meeting, if the key is wrong (they say the wrong word or give the wrong handshake), don't let them know. just hold a fake meeting and feed them misinformation.

[t1mm01994]

Important theorem: All systems based on [finite knowledge and known algorithm] or [finite data transfer] can be eventually hacked by Thurns, just by chance: They can generate answers (or the knowledge) at random, eventually hitting the right one.

I think this invalidates that..

[eligitine]

establish some kind of secret key, like a password or a handshake or what have you. at every meeting, if the key is wrong (they say the wrong word or give the wrong handshake), don't let them know. just hold a fake meeting and feed them misinformation.

With the fake meeting, or the fake handshake, it only stands if the thurns initate the handshake, if a non-thurn does it, the thurns can work out the handshake eventually, or word immediately.

[WarDaft]

If you require gradually increasing data size handshakes, you can reduce the probability that they will eventually compromise your system to near 0.

[mfb]

establish some kind of secret key, like a password or a handshake or what have you. at every meeting, if the key is wrong (they say the wrong word or give the wrong handshake), don't let them know. just hold a fake meeting and feed them misinformation.

This does not work: After the first meeting with X, they know how person X has to begin the meeting (like saying "hi and hello"), in a similar way they can extract the first move for all. If they know the first move of X and Y, they can appear as X, make the correct first move and watch the first two moves of Y. Like this, they can work their way through every finite ritual which is the same every time.

[jonachin]

establish some kind of secret key, like a password or a handshake or what have you. at every meeting, if the key is wrong (they say the wrong word or give the wrong handshake), don't let them know. just hold a fake meeting and feed them misinformation.

This does not work: After the first meeting with X, they know how person X has to begin the meeting (like saying "hi and hello"), in a similar way they can extract the first move for all. If they know the first move of X and Y, they can appear as X, make the correct first move and watch the first two moves of Y. Like this, they can work their way through every finite ritual which is the same every time.

As the problem is stated, I understood that I only had to worry if the other person is a Thurn or my friend. no where is it stated that Thurns are meeting other members of the group.

[tomtom2357]

Sorry, I meant that the Thurns can meet other people too in my form or some other form, so they can use my password that I give and use it against someone else.

[eligitine]

I've been running through my mind a senario, where there is a starting, and return action, lets say for this example a fist bump and a handshake respectively. If a party fails to innitate one or the other, they are shot(since I infer this is the future, lets say with a disintegration pistol.). Since thurns only tell others thurns once they are found out, if they are shot (and therefore dead) they cannot transmit.

[tomtom2357]

I've been running through my mind a senario, where there is a starting, and return action, lets say for this example a fist bump and a handshake respectively. If a party fails to innitate one or the other, they are shot(since I infer this is the future, lets say with a disintegration pistol.). Since thurns only tell others thurns once they are found out, if they are shot (and therefore dead) they cannot transmit.

The Thurns can transmit instantaneously, so that plan cannot work. If I allowed that, the solution would be easy.

[Pazuzu]

Does the puzzle assume that no Thurns are present when the system is designed/put to use? If not, I don't see how it would be secure without the use of biological testing or something similar to ensure each person indeed is human. For instance, assigning public and private keys only work if you already know that the person you are assigning keys to is not a Thurn.

[tomtom2357]

Does the puzzle assume that no Thurns are present when the system is designed/put to use? If not, I don't see how it would be secure without the use of biological testing or something similar to ensure each person indeed is human. For instance, assigning public and private keys only work if you already know that the person you are assigning keys to is not a Thurn.

Yes, it does assume that, because otherwise it is impossible to implement the system.

[eligitine]

A rather enjoyable solution I came up with is just to kill everyone in the society except yourself, but don't tell the thurns. Revenge all around.

[HonoreDB]

Spoiler:

At the initial meeting, agree on a group password and an easy-to-perform hash algorithm. When a group meets, they sit in a circle, and each person chooses a random word on the spot and announces it. Everybody then calculates two hashes: the hash of their own word concatenated with the password, and the hash of the person on their left's word concatenated with the password. Then everybody reveals the hash of their own word, and the person on their right checks them. If someone is revealed as a Thurn, recheck the person they checked. The chance of failure can be made arbitrarily low by using long passwords and large hash spaces.

Of course, we need a secure hash function that can be performed by hand. Off the top of my head:

1. Write the string to be hashed at the top of the page, and the number 0 at the start of a new row.
2. Select the first letter.
3. Cross out the selected letter. Write its alphanumeric equivalent (A=1, B=2...) at the end of the row of numbers. Then select the nth letter of the string, where n is the value you just wrote down modulo the length of the string, not counting crossed-out letters.
4. Repeat step three until all the letters are crossed out. You now have a row full of numbers, representing the original string in scrambled order.
5. Multiply each number by its position in the row, and sum the result.
6. Divide the sum by some large prime, and take the remainder. This is the hash value.

May not actually be that secure. Note though that we don't need to worry about "poisoned" inputs, since people only announce the hashes of their own chosen words.

[Gwydion]

HonoreDB, that plan will work exactly once:

Spoiler:

Have Thurn X sit in on a meeting and say random things. He's gonna die. Before he does, though, he gets a chance to hear everyone else's word-and-hash pair. Once those are transmitted to the group, the actual function or group password are unnecessary, unless the function involves the current date/time or some other frequently-changing variable. Future Thurns can just repeat the pair they learned, and should feel free to say the person on their left is equally legit. Or better yet, say they're wrong just to be dicks.

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.

[mfb]

You can fix this issue:

Spoiler:

Publicly announce every word used and do not allow words to be used twice.

However, I doubt that the hashing method is very secure.
Just bring your laptop to the meetings.

[eligitine]

You can fix this issue:

Spoiler:

Publicly announce every word used and do not allow words to be used twice.

However, I doubt that the hashing method is very secure.
Just bring your laptop to the meetings.

The thurns could steal your laptop and pose as you. I was thinking about the problem over the weekend, and I was thinking that each user would communicate across LAN, with a log on given to each person in the society. Thurns could not log in to find out information. I could think of several weaknesses of this, namely a man in the middle attack, but it should work in concept.

[mfb]

They can steal the laptop, but the hashing algorithm can be public anyway. I didn't say "save the password there", the laptop would be used to compute stuff only.

[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.

[mfb]

For every possible meeting time, use some algorithm to determine the place of the meeting.
Or, add the place of the meeting to the various hash/encryption methods proposed here.

[tomtom2357]

I have another idea: put a tracking chip in every person that you are going to meet with, that can only be taken out by killing the person. Then, you can instantly kill every Thurn that does not have a tracking chip in them. Now, for them to have a chance of infiltrating your system, they must kill the real person and take their tracking chip. This is where another system comes in, it will decide whether a person is a Thurn or not if the tracking chip is inside them. This system is simply that every 2 people have a password that they share between each other. If it is discovered that they are a Thurn, then the real person is dead, and so you know that any more Thurns that come in their form are not the real person and so can be killed. Now all the information that the Thurn gathered is absolutely useless, as the password only works between those two people.

[Pazuzu]

Problem is, when the Thurn is at the meeting he will be able to deduce that sharing a password with one other member is a requirement, and he will see which members pair up with which.
Also: You can't tell which one is lying. When the member says the Thurn gave the wrong password, the Thurn can just say "no, you gave the wrong password!"


Speaking of passwords, wouldn't that be the easiest solution? In the first secure meeting, agree on individual passwords for each member. On every meeting thereafter each first give their password to prove they are not a Thurn and then everyone selects a new individual password.

It's a hassle to remember new passwords, but given that everyone only has one attempt, the passwords don't need to be very difficult to remember as long as each password is unique and the following password isn't easy to guess (if your first password was 1234, your next can't be 12345).

There is a very remote possibility that a Thurn could randomly guess the right password though. Also, for a big enough group it will be impossible to remember everyones passwords (and what password belonged to whom).

[mfb]

But how do you tell all in your organisation about your new password - without meeting them and without giving it to a Thurn?

[Pazuzu]

Well, the first time you do it it's assumed no Thurn is present. The second meeting, you start off with everybody saying their password. This will weed out any Thurn that may have infiltrated the group and you can safely exchange new passwords.

After a few meetings, it will be obvious to the Thurns that everybody changes passwords for each meeting, but this isn't really valuable information. As long as the new passwords are chosen arbitrarily it should be a fairly safe method - disregarding the fact that human memory sometimes sucks.

[mfb]

In that case, every meeting has to include all members, they have to kill all Thurns present before making new passwords, and members which are not at the meeting are basically excluded from the organisation as they cannot verify the new passwords of others.

[Pazuzu]

Well, what good is it to have a secret organization if it's members can't even be bothered to show up to the meetings? And if members start skipping meetings, I know I would be feeling very paranoid.

[mfb]

You want to organize a meeting with all members just to coordinate anything with a single other member, which might be required on a daily basis?

[mward]

Recently I was reading Houdini's book "A Magician Among the Spirits" which offers another solution to this problem. I quote from page 151:

Before leaving with Sir Arthur, Mrs. Houdini cued me. We did
a second sight or mental performance years ago and still use a system
or code whereby we can speak to each other in the presence of others,
even though to all outward appearances we are merely talking,
pointing or doing the most innocent looking things, but which have
different meanings to us.

[Pazuzu]

mfb: I personally would like to welcome our new overlords, the Thurns. There is no way we would be able to fight a shapeshifting race of aliens that can communicate telepathically.

The puzzle stated by the OP is to secure meetings against infiltration though. I assume this means group meetings. And I did say it was the easiest solution, not the best one

[ineon]

Well, the first time you do it it's assumed no Thurn is present. The second meeting, you start off with everybody saying their password. This will weed out any Thurn that may have infiltrated the group and you can safely exchange new passwords.

I think that the Thurns can break this by inviting a single human to a meeting consisting of only him and other Thurns. They can convince the human to reveal his password first take his password and then pose as him in the next real meeting.

[Pazuzu]

Good point. That is a major flaw.

[ejv]

Haven't read the possible solutions, so I'm sorry if I repeat anything:

Use the lack of a password as a password: ask each member individually--stressing the need for secrecy--what the password is. Any legitimate member will know that no password has been established, and will tell you so. A Thrum--and this is where the assumption of incomplete infiltration is important--will not know that no password has been created, and say that they do not know the password (or, even worse, guess the password). You can then establish individual passwords (two-way; e.g. I ask for your password, which is banana, and you ask for mine, which is waffle iron) with the confirmed legitimate members. This way, a Thrum would need an individual's password in order to successfully impersonate them--but a Thrum wouldn't know this. This fails if a Thrum has been present at every meeting or if a legitimate member assumes that a password has been created without them.

[mfb]

This fails, as Thurns can happen to ask other members for their password before they have to tell their own password (for n>1 members, one has to do something first, or both at the same time - anyway, Thurns can get information about that).
Btw.: "There is no password" is just a special password.