How Do I Prove That I Am Spartacus Without Showing My ID?

How Do I Prove That I Am Spartacus Without Showing My ID?

True story … I phone my bank … and my bank asks me for my password to prove that I am who I say I am, and I say “No! … I’m not giving you that”, and I say “Can you prove to me that you are my bank?” … and they say … “Well, you phoned us!” … and I say “but how do I know you are my bank?” … “We just are! Okay … give me your password” and I say “No!”, and they say “Well we can’t help you if you don’t give us your password” … and they hung up! Doh!

On the Internet, we give away so much information, and the more we give away, the more that our data can be used by others for malicious purposes. Every time we give away our date of birth, someone could use it to crack our bank account details. So how do we prove something, if we don’t want to reveal our data?

The Internet we have created uses a trust model, where we have a trusted party — Trent — which will check the information. But what if we don’t trust anyone on the Internet — how can we still check?

Oblivious Transfer (OT)

So how do we determine if someone is of a certain height or a certain age, without them giving away their height or age? One method is to use oblivious transfers, where Bob and Alice can exchange information, but not reveal their core data. The core of this is OT, which is a privacy enhancing technology (PET).

So let’s take a simple example. Let’s say that Bob is 5 feet 8 inches, and he has six boxes which he adds labels to: Box1 (5 feet 2 inches); Box2 (5 feet 4 inches); Box3 (5 feet 6 inches); Box4 (5 feet 8 inches); Box5 (5 feet 10 inches); and Box6 (6 ft). Bob then buys six padlocks and, with some sticky tape, add them onto each of the boxes (but does not lock them).

He then throws away all the keys, apart from the one which relates to his height (5 feet 8 inches).

Bob then sends Alice all the open boxes, and she looks at the labels, and places a message in each. In boxes 1 to 5, she places “No!”, but in the box that relates to her height, she will put “Yes!”. As she is 6 feet tall, she puts “Yes!” into that box.

She then locks all the boxes with the padlocks provided by Bob, and sends them back to him. Bob can then only open one (the one that is 5 feet 8 inches), and finds the message of “No!”, and thus Bob knows he is not the same height as Alice. Eve, who has been listening, has no clue either what Bob’s height is, or Alice’s, or whether Bob and Alice are the same height.

In real-life, Bob uses public key to create six key pairs. He then sends six questions to Alice, and selects one key pair, and add the public key to the one that he wants to test for. He deletes all the other private keys, and sends the questions and associated public keys to Alice. Alice examines the questions, and answers them, and encrypts with the public keys provided, and sends them back to Bob. Bob then goes through all of the encrypted messages, and can only open one … which should reveal Alice’s answer.

Oblivious Transfer in action

So, we are Bob the Investigator and investigating a serious crime, and we suspect that Eve is the person who is involved in the crime.

We now need to approach her employer (Alice) and ask for some information on her. So how do we do this without Alice knowing that we suspect Eve? Well oblivious transfer (OT) performs this.

Let’s say that HackerZForU employ Eve and Trent, and we are only interested in getting information on Eve. Alice runs the company.

Now the method we will use is based on the Diffie-Hellman key exchange method, but is modified so that we generated two keys for Alice to pass the data. One will work and the other will be useless. Alice will have no idea which of the keys will work, and the information that we can look at. In this case we’ll ask for data from both Eve and Trent, and Alice will not know which of them is the suspect.

First Alice and Bob generate random numbers (a and b). Alice then takes a value of g and raises it to the power of a:

A=gᵃ

She passes this to Bob. If Bob is interested in the first record he calculates g to the power b, else if it is the second record, he calculates the value passed from Alice (A), and multiplies this value with g to the power of b. Bob then sends one of these back:

if(c==0):B=gᵇ

if(c==1):B=A×gᵇ

Alice receives the value from Bob (B). She then calculates two keys: the hash of B to the power of a, and the hash of B/A to the power of a.

K0=Hash(Bᵃ)

K1=Hash((B/A)ᵃ)

She then encrypts the two messages (M0 and M1) with each of the keys, and returns the ciphers to Bob.

e0=EK0(M0)

e1=EK1(M1)

Bob calculates the decryption key (which will only work for one of the them) as the hash of A to the power of b:

Kbob=Hash(Aᵇ)

Bob will then try to decrypt the two ciphers with Kbob and only one will work.

Here is the demo and code:

Code

An outline of the code is here:

Research

The Internet we have created is flawed, and we give away too much information about our identify whenever we answer questions. If you want to find out if someone is more than 18 years old, why must they give away their age?

The revealing of passwords, for example, is so bad, and the minute you reveal your password, it is now open for those who hear it, to use it. We normally store passwords in a hashed format, where intruders cannot reverse them, but when we talk to our bank, we are expected to tell some OVER A TELEPHONE LINE … one of the most insecure methods of communication around … and to someone who we have no idea they are who they say they are. It is basically one-way authentication over an insecure channel.

We have applied OT into digital investigations, and an outline paper is here. Our viewpoint is that an investigator should be able to investigate, without actually revealing what they are investigating.

So you have six people in your company (Bob, Alice, Eve, Trent, Carol, and Dan), and I suspect Eve, but need to know where she lives. So I generate six public keys, and send six questions to the company, asking where each of the people live. I delete five of my private keys, but send the six public keys with a question “Where does [name] live?”, and the company sends back the answers, and I can only read the one that is related to Eve… and so I have preserved the privacy of the others who are not in the investigation, and not revealed that Eve is the person I suspect.