Bob The Investigator Uses Oblivious Transfer To Investigate Alice

Oblivious transfer allows a sender to not know the information that a receiver has read. If c is a ‘0’, we will be able to read Message 0, if it is a ‘1’, we will be able to read Message 1.

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 (DHE) method but is modified so that we generate 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 [1]:

First Alice and Bob generate random numbers (a and b) and agree on a prime number (N). Alice then takes a generator value of g and raises it to the power of a:

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:

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 BA to the power of a.

In this case, we can determine the inverse of A(modN) and then multiple the value with B. She then encrypts the two messages (M0 and M1) with each of the keys, and returns the ciphers to Bob.

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

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

Here is the code [here]:

# Find our more here:
# https://asecuritysite.com/encryption/ot

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import getPrime
import Crypto
import hashlib 
import random
import sys

import libnum

g=3

bits=128


a=random.randint(1, 2**64)

b=random.randint(1,2**64)




c=1

m0='Bob did it'
m1='Alice did it'

if (len(sys.argv)>1):
 c=int(sys.argv[1])
if (len(sys.argv)>2):
 g=int(sys.argv[2])
if (len(sys.argv)>3):
 m0=str(sys.argv[3])
if (len(sys.argv)>4):
 m1=str(sys.argv[4])
if (len(sys.argv)>5):
 bits=int(sys.argv[5])

n = getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
Alice=pow(g,a,n)


print ("Message 0",m0)
print ("Message 1",m1)

m0=pad(m0.encode(),16)
m1=pad(m1.encode(),16)

print('\nBits in prime: ',bits)
print('g: ',g,' n: ',n)
print('a (Alice random): ',a)
print('b (Bob random): ',b)
print('\nAlice value: ',Alice)


# === Bob calculates ===

if (c==0):
 Bob=pow(g,b,n)
else:
 Bob=(Alice*(pow(g,b,n))) % n

invAlice =libnum.invmod(Alice, n) # let's get A^{-1} (mod n)

# === Alice calculates ===

key0_bytes=(pow(Bob,a,n) & 0xffffffffffffffff).to_bytes(16,'big')
key1_bytes=(pow(Bob*invAlice,a,n) & 0xffffffffffffffff).to_bytes(16,'big')

key0 = hashlib.sha256(key0_bytes).digest()
key1 = hashlib.sha256(key1_bytes).digest()

cipher1 = AES.new(key0, AES.MODE_ECB)
cipher2 = AES.new(key1, AES.MODE_ECB)

print('\nAlice calculates these keys')
print('Key 0: ',key0.hex())
print('Key 1: ',key1.hex())

en0=cipher1.encrypt(m0)
en1=cipher2.encrypt(m1)


## === Bob decrypts
print('\nBob calculates this key:')

Bob_key_bytes=(pow(Alice,b,n) & 0xffffffffffffffff).to_bytes(16,'big')
Bob_key = hashlib.sha256(Bob_key_bytes).digest()
print('Bob key: ',Bob_key.hex())

cipher1 = AES.new(Bob_key, AES.MODE_ECB)

message_0=cipher1.decrypt(en0)
message_1=cipher1.decrypt(en1)

print('\nBob decrypts the messages:')
try:
 print('Message 0:',unpad(message_0,16).decode())
except Exception:
 print ("Message 0: not readable")

try:
 print('Message 1:',unpad(message_1,16).decode())
except Exception:
 print ("Message 1: not readable")

and a run [here]:

Message 0 It was Bob!
Message 1 It was Alice!

Bits in prime:  128
g:  3  n:  237711704973059895252541179946135728359
a (Alice random):  2108948494614650760
b (Bob random):  7718248666089572151

Alice value:  139715191493885985788716061158980136355

Alice calculates these keys
Key 0:  883f8d46670caf12f74eb80a94596081c613f0ac4fba271679e0ab542c596f80
Key 1:  6581c58555a476c75cd5eae910c8137f8307f673624ede71383069c34dae7b82

Bob calculates this key:
Bob key:  883f8d46670caf12f74eb80a94596081c613f0ac4fba271679e0ab542c596f80

Bob decrypts the messages:
Message 0: It was Bob!
Message 1: not readable

Conclusions

The method defined in [1] is the simplest of OT methods. We have advanced since then, such as using crypto pairing:

https://asecuritysite.com/ob/mir_ot

Reference

[1] Chou, T., & Orlandi, C. (2015). The simplest protocol for oblivious transfer. In Progress in Cryptology — LATINCRYPT 2015: 4th International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23–26, 2015, Proceedings 4 (pp. 40–58). Springer International Publishing.