How to verify number with Bob without Eve knowing?

Question

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.

Answer 1

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 02 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 \mathrm{\ 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 \mathrm{\ 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.)

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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" :)

Answer 9

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"

Answer 10

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

Answer 11

I think we can do this by using basic bit wise operations or may be customizing it for paper and pencil work. If number of alice is for ex: 663 than she can just convert the number using this methodology. Convert each digit to equivalent binary representation say this as A 663-> 110 110 011 than reverse the corresponding bits for each individual number say this as B-> 011 011 110 Now do A and B-> 010 010 010 Now send this number to bob and ask to do same if result comes same ask him to say yes or else No. In this case eve will not be able to decode the number and there is a very low probability to have different numbers ending up this same representation. Only way eve could guess is by writing all possible combinations and then trying them all but to cater that we can complicate this more by using left or right shift and adding dummy bits.

Answer 12

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.