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

11 Answers 11

up vote 14 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
1  
Just a quick comment, another weakness in the first protocol (Alice says "send me a hash of the phone number") is that it's vulnerable to a replay attack. If you were implementing this in the real world, Alice should send a random string (called a "nonce") which is hashed along with the phone number. –  Pseudonym Aug 12 at 5:39
    
You said that "anything goes" if Eve can modify the message, but this isn't necessarily a lost cause. Using RSA we can actually protect the message against MITM attacks, as well. Send a question: "Do you have my phone number?", plus your public key, plus a signature of (message + your phone number) signed with your private key. If Eve attempts to modify the message (change the public key to her own) she will be unable to generate a valid signature since she doesn't know your phone number. –  stevendesu Oct 29 at 14:19

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

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

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

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

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
3  
This answer is wrong. Simple, doable by hand, and totally insecure. It just plain doesn't work. Eve can recover a lot of information about the phone number from this. –  D.W. Aug 13 at 18:07

Send Bob a codeword encrypted with your phone number; if he sends you the code word back you know he has the correct number.

The weakness is that Eve can simulate Bob, so just try every phone number until she gets the one that gives the some codeword as Bob returned.

So get Bob to append a very large random number to the codeword then encrypt it before sending it back to you. This makes Eves search space as large as you wish.

share|improve this answer
    
This doesn't seem right. If Bob has the wrong number, he will first decrypt and get a wrong code word. After that he appends random number to the codeword, and encrypts with the wrong key. When the message is received and decrypted with the correct key, the first segment of the recovered message can possibly be the correct codeword even though the number Bob has is wrong. –  InstructedA Aug 14 at 11:33
    
@randomA You just need to make the code word(s) long enough that the probability of that happening is so small you don’t care about it. –  Ian Ringrose Aug 14 at 11:58
    
What you said is true, but the chosen solution is also very nice on this issue. I would only disagree with the chosen solution on the part of "so some information is confidentialy conveyed from Bob to Alice". If one uses a padding message that is large enough and contains no symbol used to represent phone number, then Bob can randomly put the phone number into it and Alice can easily recover the phone number from the decrypted message without knowing the random steps Bob took (no confidentially conveyed information is needed in this case). –  InstructedA Aug 14 at 12:19

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
1  
assuming i know bob's number and eve doesn't :P –  everlasto Apr 21 '13 at 14:10

I think the question is a lot simpler than everyone thinks. We are required to verify that the number Bob has is correct (or as it might be, incorrect). Since we are "checking" if the number is correct it can be assumed that Bob already has your number. Therefore there is no need to send Bob your number in some code. My answer would be, "Dear Bob, please phone my number. Thanks, Alice"

share|improve this answer
1  
The question already explicitly excludes this trivial answer. –  David Richerby 2 days ago

try doing a trik play like this

solution1: if the number is 37 the hash map would look like this

01 07

15 12

25 20

31 36

49 43

53 50

60 62

72 72

85 82

91 94

and do the same for 10 digits or even more just to confuse :P

solution2: or construct a polynomial in which your number becomes some other unique number

solution3: write this in the letter "dude call me"

solution4: write a function in such a way that it does operations on every digit and returns 0 then he send true or false solution5 : if both ends share a common hash function ... it makes life very easy

share|improve this answer
    
It's not at all obvious how your scheme codes 37. –  David Richerby Aug 24 at 14:25
    
all we need to do is map ... 31 in bold means 3 is in position 1 .... 72 means 7 is in position 2 ... sorry if it was not very intuitive to understand –  Ajay Reddy Aug 25 at 6:44
    
This should be explained in detail in the answer. But, seriously, if that's your coding scheme, it's not exactly secure, is it? –  David Richerby Aug 25 at 7:41

Please call me (my name is 1001001). If you can't reach me, please write down the phone number that you have and ask Eve to return me.

Explanation: if Bob got my correct #, he can reach me then I know it is a correct #; if Bob didn't get my right #, Eve cannot read my (correct) phone number as well. In this way, I already checked that my friend, Bob, has my correct phone number or not.

share|improve this answer
    
to everlasto: Eve can contact Bob so that most likely she has his #. Therefore, if you ask "Hey Bob, My number is next to your number, please verify", Eve would know you #. –  Pobol Wong Aug 29 at 15:11
1  
The question explicitly says that you can't just send Bob a card saying "call me". And Bob writing the incorrect number on the card if he couldn't get through doesn't add anything. –  David Richerby Aug 29 at 15:19
    
I wrote a LZW encode/decode program before. I may ask Bob to use it to send me the encoded # of my phone and also am able to use it to encode the correct part of my phone # to him. –  Pobol Wong Aug 29 at 15:31
    
to David Richerby: the question only mentions "you cannot ask him directly" which mean me, 1001001, cannot ask Bob directly, but should be able to ask him to call me with the phone # he got. –  Pobol Wong Aug 29 at 15:33
    
Read the question more carefully. "Note 2" in the question rejects the solution of sending a note asking Bob to call you because it doesn't use any computer science. –  David Richerby Aug 29 at 15:57

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.