How to verify number with Bob without Eve knowing?

Question Detail: 

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.

Asked By : Joe

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/358

Answered By : Thomas Pornin

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