Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?

Note: This question is on a list of "google interview questions". As a result, there are tons of versions of this question on the web, and many of them don't have clear, or even correct answers.

Note 2: The snarky answer to this question is that Bob should write "call me". Yes, that's very clever, 'outside the box' and everything, but doesn't use any techniques that field of CS where we call our hero "Bob" and his eavesdropping adversary "Eve".

Update:
Bonus points for an algorithm that you and Bob could both reasonably complete by hand.

Update 2:
Note that Bob doesn't have to send you any arbitrary message, but only confirm that he has your correct phone number without Eve being able to decode it, which may or may not lead to simpler solutions.

share|improve this question
1  
But "call me" doesn't make sense at all, he doesn't have your correct phone number yet or at least you're not sure if he does, so I don't think it's very clever. –  Gigili Mar 14 '12 at 8:45
1  
@Gigili if you get a call from him, then he has your number, if you don't get a call, then he doesn't. –  Joe Mar 14 '12 at 8:49
1  
Oh, right. I still think it's not clever! –  Gigili Mar 14 '12 at 9:02
    
Another tongue-in-cheek answer may be Caesar cipher. Even if Eve tries all possible offsets, she has no reason to choose any one sequence of digits over another (short of trying to call all of them). –  Raphael Mar 14 '12 at 9:18
2  
@Raphael Aren't there are only 10 possible caesar ciphers over digits? –  Joe Mar 14 '12 at 19:02
show 2 more comments

7 Answers 7

up vote 10 down vote accepted

First we must assume that Eve is only passive. By this, I mean that she truthfully sends the card to Bob, and whatever she brings back to Alice is indeed Bob's response. If Eve can alter the data in either or both directions (and her action remains undetected) then anything goes.

(To honour long-standing traditions, the two honest parties involved in the conversation are called Alice and Bob. In your text, you said "you". My real name is not "Alice", but I will respond just as if you wrote that Alice wants to verify Bob's phone number.)

The simple (but weak) answer is to use a hash function. Alice writes on the card: "return to me the SHA-256 hash of your phone number". SHA-256 is a cryptographic hash function which is believed to be secure, as far as hash functions go. Computing it by hand would be tedious but still doable (that's about 2500 32-bit operations, where each operation is an addition, a word shift or rotate, or a bitwise combination of bits; Bob should be able to do it in a day or so).

Now what's weak about that ? SHA-256, being a cryptographic hash function, is resistant to "preimages": this means that given a hash output, it is very hard to recover a corresponding input (that's the problem that Eve faces). However, "very hard" means "the easiest method is brute force: trying possible inputs until a match is found". Trouble is that brute force is easy here: there are not so many possible phone numbers (in North America, that's 10 digits, i.e. a mere 10 billions). Bob wants to do things by hand, but we cannot assume that Eve is so limited. A basic PC can try a few millions SHA-256 hashes per second so Eve will be done in less than one hour (less than 5 minutes if she uses a GPU).

This is a generic issue: if Bob is deterministic (i.e. for a given message from Alice, he would always return the same response), Eve can simulate him. Namely, Eve knows everything about Bob except the phone number, so she virtually runs 10 billions of Bobs, who differ only by their assumed phone number; and she waits for one of the virtual Bobs to return whatever the real Bob actually returned. The flaw affects many kinds of "smart" solutions involving random nonces and symmetric encryption and whatsnot. It is a strong flaw, and its root lies in the huge difference in computing power between Eve and Bob (now, if Bob also had a computer as big as Eve's, then he could use a slow hash function through the use of many iterations; that's more or less what password hashing is about, with the phone number in lieu of the password; see bcrypt and also this answer).

Hence, a non-weak solution must involve some randomness on Bob's part: Bob must flip a coin or throw dice repeatedly, and inject the values in his computations. Moreover, Eve must not be able to unravel what Bob did, but Alice must be able to, so some information is confidentialy conveyed from Bob to Alice. This is called asymmetric encryption or, at least, asymmetric key agreement. The simplest algorithm of that class to compute, but still reasonably secure, is then RSA with the PKCS#1 v1.5 padding. RSA can use $e = 3$ as public exponent. So the protocol goes thus:

  • Alice generates a big integer $n = pq$ where $p$ and $q$ are similarly-sized prime integer, such that the size of $n$ is sufficient to ensure security (i.e. at least 1024 bits, as of 2012). Also, Alice must arrange for $p-1$ and $q-1$ not to be multiples of 3.

  • Alice writes $n$ on the card.

  • Bob first pads his phone number into a byte sequence as long as $n$, as described by PKCS#1 (this means: 00 01 xx xx ... xx 00 bb bb .. bb, where 'bb' are the ten bytes which encode the phone number, and the 'xx' are random non-zero byte values, for a total length of 128 bytes if $n$ is a 1024-bit integer).

  • Bob interprets his byte sequence as a big integer value $m$ (big-endian encoding) and computes $m^3 \mod n$ (so that's a couple of multiplications with very big integers, then a division, the result being the remainder of the division). That's still doable by hand (but, there again, it will probably take the better part of a day). The result is what Bob sends back to Alice.

  • Alice uses her knowledge of $p$ and $q$ to recover $m$ from the $m^3 \mod n$ sent by Bob. The Wikipedia page on RSA has some reasonably clear explanations on that process. Once Alice has $m$, she can remove the padding (the 'xx' are non-zero, so the first 'bb' byte can be unambiguously located) and she then has the phone number, which she can compare with the one she had.

Alice's computation will require a computer (what a computer does is always elementary and doable by hand, but a computer is devilishly fast at it, so the "doable" might take too much time to do in practice; RSA decryption by hand would take many weeks).

(Actually we could have faster by-hand computation by using McEliece encryption, but then the public key -- what Alice writes on the card -- would be huge, and a card would simply not do; Eve would have to transport a full book of digits.)

share|improve this answer
add comment

Looks like a classic application of Public Key Cryptosystem like RSA.

You send your public key along, BoB encrypts your phone number from his contacts list and sends it back to you.

share|improve this answer
    
Or did I miss the point? –  Aryabhata Mar 14 '12 at 8:30
5  
Given Bob and Eve, that's probably supposed to be the key idea. Is it practical in this context (pencil and paper)? Also, I was hoping for a little more than a link to a wikipedia article with a "this article needs editing" flag. –  Joe Mar 14 '12 at 8:40
    
@Joe: I have edited to include another link. I am pretty sure you have heard of RSA. RSA is probably practical enough, as writing say a 1000 digits should not take much time. –  Aryabhata Mar 14 '12 at 8:42
    
I didn't downvote? –  Joe Mar 14 '12 at 8:46
    
Joe didn't downvote, I did it mistakenly but I undid it afterwards. –  Gigili Mar 14 '12 at 8:55
add comment

One of the most basic things you can do is a Diffie-Hellman key exchange. It does not require you to have keys set up before the communication starts as it negotiates one in a way that listeners can not derive the key themselves. See the comprehensive Wikipedia article for details.

You send Bob DH parameters $p$ and $g$ ($p$ being a suitable large prime, and $g$ typically a small number) and your public key $g^{a} \mathop{\mathrm{mod}} p$, where $a$ is a large secret number (it's your private key), as well as instructions for Bob to send back the following:

  • his public key $g^{b} \mathop{\mathrm{mod}} p$, where $b$ is a large secret number of his choosing;
  • what he believes is your phone number, encrypted using a symmetric encryption algorithm with a key derived from the shared secret $g^{a\,b} \mathop{\mathrm{mod}} p$.

Eve can see $g^{a} \mathop{\mathrm{mod}} p$ and $g^{b} \mathop{\mathrm{mod}} p$, but effectively cannot calculate $g^{a\,b} \mathop{\mathrm{mod}} p$.

As long as implemented properly and both communicators and attacker have about the same calculation power at their disposal, this is secure.

share|improve this answer
add comment

Just ask Bob to multiply the number by 2 or 3 or anything else and xor that number with the number itself. It's doable by hand and reversible if the number is known. No sha, rsa or md5. Just plain maths.

share|improve this answer
add comment

Bob doesn't have to send any messages that you can decrypt. He only has to prove to you that he has your phone number. Therefore, Cryptographic Hash Functions, (one-way encryption) offers an alternative to a public key cryptosystem. SHA-2 is currently a popular example of such a function.

In this strategy, you never have to decrypt Bob's message back to you. You tell Bob which hash function you would like him to use, e.g. "Bob, please use SHA-2 to encrypt my phone number and have Eve pass the result back to me". Then you use the same algorithm to hash your phone number, and check if you get the same hash that Bob got. It is extremely unlikely that two different phone numbers would result in the same hash, and so you can determine whether or not Bob has your correct phone number.

If you, Bob, and Eve don't have computers available to compute the hash function (or perform a brute force attack) it may be possible to use hash function that sacrifices some security against brute force attacks but is much easier for you and Bob to calculate.

share|improve this answer
    
I was writing the same answer! Unlucky. I'll post it anyway as I spent time on it. –  Gigili Mar 14 '12 at 20:33
    
@Gigili I was hoping someone would write up this answer, but I decided to when I saw that no one was offering this alternative yet... I am still looking for a pencil-and-paper-friendly version. Honestly, I wouldn't want to ask my friend to do RSA or SHA-2 by hand. –  Joe Mar 14 '12 at 20:37
    
The problem is, every simple algorithm which can be done by hand would be encrypted by Eve. –  Gigili Mar 14 '12 at 20:53
    
@Gigili do you mean "decrypted by Eve"? The problem is very constrained. It seems like there should be a simpler one-way hash from 7-digit integers that Eve can't just undo to get back the original number. –  Joe Mar 14 '12 at 21:25
    
Oops, I meant decrypted obviously. –  Gigili Mar 14 '12 at 21:39
show 1 more comment

A simple solution would be:

Both Alice and Bob agree on the same colour. and it's no problem if Eve knows that one, we'll call this P. Let's say it's yellow. Now, Alice and Bob both randomly choose a private colour, say "x". Alice chooses red, and Bob chooses blue. Now they mix them together with the P. Alice now has orange, and Bob has green. Alice sends the orange colour to Bob, and Bob sends his green colour to Alice Eve now knows about yellow, orange, and green but Alice also knows her private colour red, and Bob knows his private colour blue, which nobody else knows. Both Alice and Bob take their original private colours and add them to the ones they just exchanged. Now, if they mix their original private colours, red and blue, into the shared colour, they both end up with the same colour, sort of brown, or brick red.

Instead of mixing colours together, you could use $g^x\pmod{p}$ such that p is a large prime number, and g is a primitive root of p because if you do $g^x\pmod{p}$ for any x, the result (a number between zero and p - 1) is equally likely to be any of those, that's why there's a primitive root. if p is a prime number 2n+1 such that n is also prime, then you know that 2 is a primitive root of p (which means you don't have to bother calculating the primitive root, which is kind of hard) thus the shared secret = $A^x\pmod{p}$ for Bob, and $B^y\pmod{p}$ for Alice.


I think you can write something like this on the card:

The number is multiple of 3,5 and 7 (for example).

There are $(10)^n$ ($n$ is the number of digits) possibilities and that idea will just invalidate some few possibilities for the one who has know idea about it. So decryption by Eve will not happen.

share|improve this answer
    
This is a narration of the image found on the Wikipedia article of Diffie-Hellmann key exchange. You should at least mention your source. –  Raphael Mar 15 '12 at 7:37
    
@Raphael: I didn't know it myself, someone explained it to me and I thought it was a good idea. –  Gigili Mar 15 '12 at 16:10
add comment

I will write some 10 phone numbers in the card and among those I'll make sure that My number would come next to Bob's number and I will mention "Hey Bob, My number is next to your number, please verify" :)

share|improve this answer
    
assuming i know bob's number and eve doesn't :P –  everlasto Apr 21 '13 at 14:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.