16 ms·

The solution doesn't seem to work on its face. If the spy simply gives the guard Y, the scheme is the same as having a bunch of fixed passwords. If the spy gi

The solution doesn't seem to work on its face. If the spy simply gives the guard Y, the scheme is the same as having a bunch of fixed passwords. If the spy gives the guard X, X becomes public to the enemy. Some machine that lets the spy input X (with the input hidden to the guard) and displays Y to the guard would work, assuming the guard doesn't snoop around to discover X.

kenjackson 16y ago
The answers are not recycled. So after given they throw it away.
- losvedir 16y ago
  I don't see how that solves anything. If the guard knows the answer, then you assume the enemy knows the answer. So all "throwing it away" does, is allow the enemy to cross the border once and the spy stranded!
  - harterrt 16y ago
    In this situation the guard only knows the answer (or x value) once the spy gives it to him or her.
  - jamwt 16y ago
    Well, the guard knows Y, and the enemy knows Y... but the guard's authentication procedure involves taking an X (not Y) supplied by the friendly spy, executing the calculation, and asserting the result is equal to Y. Since the enemy does not know X, and X cannot be trivially derived from Y (one-way function), the scheme is secure.
    - losvedir 16y ago
      Yikes, teach me to post when I'm in a hurry! I misunderstood. Thanks for clearing it up.
  - ernestobad 16y ago
    The machine is necessary. Although the spy is able to produce a Y number with the machine and the guard knows Y, if the guard doesn't know X he also doesn't know how to generate a Y number with the machine.
    - brianpan 16y ago
      Yeah, you have to make a leap that's not explained in the puzzle. An intermediate machine or some other method has to be used to keep the secret a secret, yet the answer can be "public".
  - robinhouston 16y ago
    Wow, a lot of confusion here! The idea is that X is the credential, and Y is a sort of digital signature of X. So the spy knows X, and the border guard has a record of Y. When the spy wants to cross the border, he tells the guard X, and the guard can check that the credential is legitimate by seeing whether it matches the signature Y.
  - InclinedPlane 16y ago
    The guards don't know the password, they only know how to verify the password. It's public / private key encryption, or one way hashing.
blahedo 16y ago
Well, in this formulation, they're one-time passwords; but once the spy is back in the country they could get a fresh one. Of course the more complete solution would be public-key encryption, but they didn't know that yet in 1958---this idea of a one-way function is basically a precursor to that.
- eru 16y ago
  And nowadays we would probably use the discrete logarithm problem or factoring integers as the one-way functions of choice.
  - cdavidcash 16y ago
    The suggested solution (modular squaring) already reduces to factoring. http://en.wikipedia.org/wiki/One-way_function#Modular_squaring_and_square_roots http://en.wikipedia.org/wiki/One-way_function#Modular_squari... (And we'd use a cryptographic hash function anyway.)
    - eru 16y ago
      Thanks!
  - sirclueless 16y ago
    No, we probably wouldn't. These one-way functions have some nice properties that we use in RSA and Diffie-hellman, like commutativity and the fact that encryption is a permutation, but these properties come with caveats in that they are considerably easier to break. A simple consequence is that we need something like 1024 bits for a strong RSA key, but SHA-256 is still miles out of reach of being attackable.
- tzs 16y ago
  A chaining method can be used to reduce the frequency of the guard having to go back for a new password. Let F be the one-way function. You give the spy a value x0. Then you compute x1=F(x0), x2=F(x1), ..., x_n = F(x_{n-1}). The guard is given x_n. When the guard challenges the spy, the guard gives the spy x_n, the spy iterates F starting on x0 until he finds x_{n-1}, and gives that to the guard, who checks it. The guard then replaces x_n with x_{n-1} and uses that for the next challenge, and so on. This allows for n border crossings before the spy and guard need to come to headquarters for new numbers. Each spy can either have his own x_0, in which case the guard has to have an x_n for each spy, or you can have all the spies share the same x_0, or you can do something in between such as having the less important spies share a value and have your most important spies have their own values.
redwood 16y ago
Just read your comment after posting the exact same thing above... it seems the key we both figured out is that you have a secure tool that does the work for the guard. But if this is the case then the problem isn't a problem at all: b/c with a secure tool you don't need to worry about a guard who blabbs... but that certainly didn't seem to be in the universe of hte problem that was posed
colanderman 16y ago
Right; you'd actually need some sort of public-key cryptography: the guard gives the spy a challenging problem which only the spy can solve correctly, but for which anyone (including the guard) can check the answer.

kenjackson 16y ago

The answers are not recycled. So after given they throw it away.

losvedir 16y ago
I don't see how that solves anything. If the guard knows the answer, then you assume the enemy knows the answer. So all "throwing it away" does, is allow the enemy to cross the border once and the spy stranded!
- harterrt 16y ago
  In this situation the guard only knows the answer (or x value) once the spy gives it to him or her.
- jamwt 16y ago
  Well, the guard knows Y, and the enemy knows Y... but the guard's authentication procedure involves taking an X (not Y) supplied by the friendly spy, executing the calculation, and asserting the result is equal to Y. Since the enemy does not know X, and X cannot be trivially derived from Y (one-way function), the scheme is secure.
  - losvedir 16y ago
    Yikes, teach me to post when I'm in a hurry! I misunderstood. Thanks for clearing it up.
- ernestobad 16y ago
  The machine is necessary. Although the spy is able to produce a Y number with the machine and the guard knows Y, if the guard doesn't know X he also doesn't know how to generate a Y number with the machine.
  - brianpan 16y ago
    Yeah, you have to make a leap that's not explained in the puzzle. An intermediate machine or some other method has to be used to keep the secret a secret, yet the answer can be "public".
- robinhouston 16y ago
  Wow, a lot of confusion here! The idea is that X is the credential, and Y is a sort of digital signature of X. So the spy knows X, and the border guard has a record of Y. When the spy wants to cross the border, he tells the guard X, and the guard can check that the credential is legitimate by seeing whether it matches the signature Y.
- InclinedPlane 16y ago
  The guards don't know the password, they only know how to verify the password. It's public / private key encryption, or one way hashing.

blahedo 16y ago

Well, in this formulation, they're one-time passwords; but once the spy is back in the country they could get a fresh one. Of course the more complete solution would be public-key encryption, but they didn't know that yet in 1958---this idea of a one-way function is basically a precursor to that.

eru 16y ago
And nowadays we would probably use the discrete logarithm problem or factoring integers as the one-way functions of choice.
- cdavidcash 16y ago
  The suggested solution (modular squaring) already reduces to factoring. http://en.wikipedia.org/wiki/One-way_function#Modular_squaring_and_square_roots http://en.wikipedia.org/wiki/One-way_function#Modular_squari... (And we'd use a cryptographic hash function anyway.)
  - eru 16y ago
    Thanks!
- sirclueless 16y ago
  No, we probably wouldn't. These one-way functions have some nice properties that we use in RSA and Diffie-hellman, like commutativity and the fact that encryption is a permutation, but these properties come with caveats in that they are considerably easier to break. A simple consequence is that we need something like 1024 bits for a strong RSA key, but SHA-256 is still miles out of reach of being attackable.
tzs 16y ago
A chaining method can be used to reduce the frequency of the guard having to go back for a new password. Let F be the one-way function. You give the spy a value x0. Then you compute x1=F(x0), x2=F(x1), ..., x_n = F(x_{n-1}). The guard is given x_n. When the guard challenges the spy, the guard gives the spy x_n, the spy iterates F starting on x0 until he finds x_{n-1}, and gives that to the guard, who checks it. The guard then replaces x_n with x_{n-1} and uses that for the next challenge, and so on. This allows for n border crossings before the spy and guard need to come to headquarters for new numbers. Each spy can either have his own x_0, in which case the guard has to have an x_n for each spy, or you can have all the spies share the same x_0, or you can do something in between such as having the less important spies share a value and have your most important spies have their own values.

redwood 16y ago

Just read your comment after posting the exact same thing above... it seems the key we both figured out is that you have a secure tool that does the work for the guard. But if this is the case then the problem isn't a problem at all: b/c with a secure tool you don't need to worry about a guard who blabbs... but that certainly didn't seem to be in the universe of hte problem that was posed

colanderman 16y ago

Right; you'd actually need some sort of public-key cryptography: the guard gives the spy a challenging problem which only the spy can solve correctly, but for which anyone (including the guard) can check the answer.