CS411-Project Phase 3 Solved

You are required to develop a simplified version of the TextSecure protocol, which provides forward secrecy and deniability. Working in the project will provide you with insight for a practical cryptographic protocol, a variant of which is used in different applications such as WhatsApp.

1      Introduction
The project has three phases:

•    Phase I Developing software for the Registration and the Station-to-Station (STS) protocols. All coding development will be in Python programming language.

•    Phase II Developing software for receiving messages from other clients

•    Phase III Developing software for sending messages from other clients More information about project is given in the subsequent section.

2 Phase I: Developing software for the Registration and Stationto-Station Protocols
In this phase of the project, you are required to upload one file: “Client.py”. You will be provided with “Client  basics.py”, which includes all required communication codes.

In the Registration protocol (see below) you will register your long term public key with a server. You will also simulate the STS protocol with the same server. The server is accessible via cryptlygos.pythonanywhere.com. You may find the connection details in “Client basics.py”. JSON format should be used in all communication steps.

In the Station-to-Station (STS) protocol, each party must have a long term public and private key pair to sign messages and verify signatures. A variant of Elliptic Curve Digital Signature Algorithm (ECDSA) will be used with NIST-256 curve in this project. See Section 2.3 for the description of the variant of the ECDSA algorithm that will be used in the project. You should select “secp256k1” for the elliptic curve in your python code. Note that you will NOT use the ECDSA algorithm in the slides.

2.1       Registration
The long term public key of the server QSL is given below.

X:0xc1bc6c9063b6985fe4b93be9b8f9d9149c353ae83c34a434ac91c85f61ddd1e9

Y:0x931bd623cf52ee6009ed3f50f6b4f92c564431306d284be7e97af8e443e69a8c

In this part, firstly you are required to generate a long-term private and public key pair sL and QL for yourself. The key generation is described in “Key generation” algorithm in Section 2.3. Then, you are required to register with the server. The registration operation consists of four steps:

1.    After you generate your long-term key pair, you should sign your ID (e.g. 18007). The details of the signature scheme is given in the signature generation algorithm in Section 2.3. Then, you will send a message, which contains your student ID, the signature tuple and your long-term public key, to the server. The message format is

{‘ID’: stuID, ‘H’: h, ‘S’: s, ‘LKEY.X’: lkey.x, ‘LKEY.Y’: lkey.y}

where stuID is your student ID, h and s are signature tuple and lkey.x and lkey.y are the x and y and coordinates of your long-term public key, respectively. A sample message is given in ‘samples.txt’.

2.    If your message is verified by the server successfully, you will receive an e-mail, which includes your ID, your public key and a verification code: code.

3.    If your public key is correct in the verification e-mail, you will send another message to the server to authenticate yourself. The message format is “{‘ID’: stuID, ‘CODE’: code}”, where code is verification code which, you have received in the previous step. A sample message is given below.

{‘ID’: 18007, ‘CODE’: 209682}

4.    If you send the correct verification code, you will receive an acknowledgement message via e-mail, which states that you are registered with the server successfully.

Once you register with the server successfully, you are not required to perform registration step again as the server stores your long-term public key to identify you. You need to store your long-term key pair as you will use them until the end of the project.

2.2         Station-to-Station Protocol
Here, you will develop a python code to implement the STS protocol. For the protocol, you will need the elliptic curve digital signature algorithm described in Section 2.3. The protocol has seven steps as explained below.

1.    You are required to generate an ephemeral key pair sA and QA, which denote private and public keys, respectively. The key generation is described in “Key generation” algorithm in Section 2.3

Then, you will send a message, which includes your student ID and the ephemeral public key, to the server. The message format is “{‘ID’: stuID, ‘EKEY.X’: ekey.x, ‘EKEY.Y’: ekey.y”, where ekey.x and ekey.y are the x the y coordinates of your ephemeral public key, respectively. A sample message is given in ‘samples.txt’.

2.    After you send your ephemeral public key, you will receive the ephemeral public key QB of the server. The message format is “{‘SKEY.X’: skey.x, ‘SKEY.Y: skey.y}”, where skey.x and skey.y denote the x and y coordinates of QB, respectively. A sample message is given in ‘samples.txt’.

3.    After you receive QB, you are required to compute the session key K as follows.

•    T = sAQB

•    U = {T.x||T.y||“BeY ourselfNoMatterWhatTheySay”}[1], where T.x and T.y denote the x and y coordinates of T, respectively.

•    K = SHA3  256(U)

A sample for this step is provided in ‘samples.txt’.

4.    After you compute K, you should create a message W1, which includes your and the server’s ephemeral public keys, generate a signature SigA using sL for the message W1. After that, you should encrypt the signature using AES in the Counter Mode (AES-CTR). The required operations are listed below.

•   W1 = QA.x||QA.y||QB.x||QB.y, where QA.x, QA.y, QB.x and QB.y are the x and y coordinates of QA and QB, respectively.

•   (SigA.s,SigA.h) = SignsL(W1)

•   Y1 = EK(“s”||SigA.s||“h”||SigA.h)

Then, you should concatenate the 8-byte nonce NonceL and Y1 and send {NonceL||Y1} to the server. Note that, you should convert the ciphertext from byte array to integer. A sample for this step is provided in ‘samples.txt’.

5.    If your signature is valid, the server will perform the same operations which are explained in step 4. It creates a message W2, which includes the server’s and your ephemeral public keys, generate a signature SigB using sSL, where sSL is the long-term private key of the server. After that, it will encrypt the signature using AES-CTR.

• W2 = QB.x||QB.y||QA.x||QA.y. (Note that, W1 and W2 are different.)
•   (SigB.s,SigB.h) = SignsL(W2)

•   Y2 = EK(“s”||SigB.s||“h”||SigB.h)

Finally, it will concatenate the 8-byte nonce NonceSL to Y2 and send {NonceSL||Y2} to you. After you receive the message, you should decrypt it and verify the signature. The signature verification algorithm is explained in Section 2.3. A sample for this step is provided in ‘samples.txt’.

6.    Then, the server will send to you another message EK(W3) [2] where, W3 = {Rand||Message}. Here, Rand and Message denote an 8-byte random number and a meaningful message, respectively. You need to decrypt the message, and obtain the meaningful message and the random number Rand. A sample for this step is provided in ‘samples.txt’.

7.    Finally, you will prepare a message W4 = {(Rand+1)||Message} and send EK(W4) [3] to the server. Sample messages for this step is given below.

W4 : 86987

MessagetoServer : 86987

8.    If your message is valid, the server will send a response message as EK(“SUCCESSFUL”||Rand + 2) 2

2.3              Elliptic Curve Digital Signature Algorithm (ECDSA)
Here, you will develop a Python code that includes functions for signing given any message and verifying the signature. For ECDSA, you will use an algorithm, which consists of three functions as follows:

•    Key generation: A user picks a random secret key 0 < sA < n − 1 and computes the public key QA = sAP.

•    Signature generation: Let m be an arbitrary length message. The signature is computed as follows:

1.    k ← Zn, (i.e., k is a random integer in [1,n − 2]).

2.    R = k · P

3.    r = R.x           (mod n), where R.x is the x coordinate of R

4.    h = SHA3  256(m + r)             (mod n)

5.    s = (sA · h + k)             (mod n)

6.    The signature for m is the tuple (h,s).

•    Signature verification: Let m be a message and the tuple (s,h) is a signature for m. The verification proceeds as follows:

–    V = sP − hQA

–    v = V.x           (mod n), where V.x is x coordinate of V

–    h0 = SHA3  256(m + v)           (mod n)

–    Accept the signature only if h = h0 – Reject it otherwise.

Note that the signature generation and verification of this ECDSA are different from the one discussed in the lecture.

3 Phase II: Developing software for receiving messages from other clients
In this phase of the project, you are required to upload one file: “Client phase2.py”. You will be provided with “Client basic phase2.py”, which includes all required communication codes. Moreover, you will find sample outputs for this phase in ‘sample vector.txt’, which is also provided on SUCourse.

You are required to develop a software for downloading 5 messages from the server, which were uploaded to the server originally by a pseudo-client, which is implemented by us, in this phase[4]. The details are given below.

In Phase I, you have already implemented the registration protocol. The details are explained in Section 2.1. If you have not implemented yet, you must implement the protocol before Phase II and register your long-term public key with the server.

3.1        Registration of ephemeral keys
Before communicating with other clients, you must generate 10 ephemeral public and private key pairs, namely (sA0,QA0),(sA1,QA1),(sA2,QA2),...,(sA9,QA9),, where sAi and QAi denote your ith private and public ephemeral keys, respectively. The key generation is described in “Key generation” algorithm in Section 2.3.

Then, you must sign each of your public ephemeral key using your long-term private key. The signatures must be generated for concatenated form of the ephemeral public keys (QAi.x||QAi.y). Finally, you must sent your ephemeral public keys to the server in the form of

{‘ID’: stuID, ‘KEYID’:i , ‘QAI.X’: QAi.x, ‘QAI.Y’: QAi.y, ‘SI’: si, ‘HI’: hi},

where i is the ID of your ephemeral key. You must start generating your ephemeral keys with IDs from 0 and follow the order. Moreover, you have to store your ephemeral private keys with their IDs.

3.1.1         Resetting the ephemeral keys
If you forget to store your ephemeral private keys or require to get new messages sent by the pseudo-client, you must sign your ID using your long-term private key and send a message to the server in the form of

{‘ID’: stuID, ‘S’: s, ‘H’: h }.

When the server receives your message, your ephemeral keys will be deleted. After you produce as new set of ephemeral keys and register with the server again, pseudo client will produce a new set of 5 messages for you.

3.2       Receiving messages
As mentioned above, you will download 5 messages from the server. In order to download one message from the server, you must sign your ID using your long-term private key and send a message to the server in the form of

{‘ID’: stuID, ‘S’: s, ‘H’: h }

to download one message from the server as follows

{‘IDB’: stuIDB, ‘KEYID’: i, ‘MSG’: msg , ‘QBJ.X’: QBj.x ,‘QBJ.Y’: QBj.y },

where stuIDB is the ID of the sender, i is the ID of your ephemeral key, which is used to generate session keys, msg contains both the encrypted message and its MAC, and QBj.x and QBj.y are x and y coordinates of the ephemeral public key of the server, respectively.

3.2.1         Session Key and msg Generation
As mentioned above, the message that you received includes the ciphertext as well as its MAC, which is concatenated to the end of the ciphertext. In order to create a message in this way, the pseudo-client will compute two session keys KABENC and KABMAC using your and its ephemeral keys which are QAi and QBj, respectively. Before the computation, the pseudo-client requests your ephemeral key from the server and the server sends your ephemeral key QAi with your key ID i. Then, it computes the session keys as follows:

•    T = sBjQAi, where sBj is the jth secret ephemeral key of the pseudo-client.

•    U = {T.x||T.y||“NoNeedToRunAndHide”} [5]

•    KABENC = SHA3  256(U)

• KABMAC = SHA3 256(KABENC)
After it computes the session keys, it encrypts the message with KABENC using AES-CTR[6] and computes HMAC-SHA256 [7]. of the ciphertext with KABMAC

3.2.2         Decrypting the messages
After you download a message, which is sent by the pseudo-client, from the server, you must generate session keys firstly. As mentioned above, QBj and i are given to you in the message. Therefore, you must compute KABENC and KABMAC as sAiQBj and SHA3  256(KABENC), respectively. Then, you must verify the HMAC code and decrypt the message. Finally, you must send the decrypted message with your ID as follows

{‘ID’: stuID, ‘DECMSG’: decmsg}. where decmsg is the decrypted message.

4       Phase III: Developing software to communicate with other clients
In this phase of the project, you are required to upload one file: “Client phase3.py”. You will be provided with “Client basic phase3.py”, which includes all required communication codes. Moreover, you will find sample outputs for this phase in ‘sample vector.txt’, which is also provided on SUCourse.

For testing purpose, you may send message to your groupmate and s/he may receive your message, if you are working in groups of two. Note that, if you have not registered with the server yet, you must register. The details are given in Section 2.1. If you are working alone, we will provide a dummy user for you.

In this phase of the project you will work on two parts. In the first part, you will develop a software to send message to other users.(You are not limited to send message to your group-mate or dummy user. You may send everybody who takes CS411/507.). In second part, you will manage your ephemeral keys. The details are given in the subsequent sections.

4.1        Sending Messages
In this part of Phase III, you are required to develop a software to send messages to other clients. Firstly, you are required to generate session keys. The details of session key generation is given in Section 3.2.1. In order to generate session keys to send a message to another client, ephemeral public key of the receiver is needed. Therefore, you must request an ephemeral key of the receiver from the server. The message format is given below.

{‘IDA’: stuIDA, ‘IDB’: stuIDB, ‘S’: s, ‘H’: h }

where stuIDA and stuIDB are your and the receiver’s IDs, respectively. s and h is a signature tuple which generated for stuIDB using your long-term private key. If your request is valid, the server will send the ephemeral key of the receiver as follows:

{‘I’: i, ‘J’: j, ‘QBJ.x’: OBj.x, ‘QBJ.y’: OBj.y, }

where i and j denote your and the receiver’s ephemeral key IDs, respectively. Moreover, OBj.x and OBj.x are x and y coordinated of the jth ephemeral key of the receiver, QBj. You must generate the session key using is your ith ephemeral key, sAi, and QBj as follows:

•    T = sAiQBj

•    U = {T.x||T.y||“NoNeedToRunAndHide”}

•    KABENC = SHA3  256(U)

• KABMAC = SHA3 256(KABENC)
Then you must encrypts your message with KABENC using AES-CTR and compute HMAC-SHA256 of the ciphertext with KABMAC. Finally, you must concatenate the nonce, ciphertext and MAC of the ciphertext and send to the server as follows:

{‘IDA’: stuIDA, ‘IDB’: stuIDB, ‘I’: i, ‘J’: j, ‘MSG’: msg } where msg includes the nonce, ciphertext and MAC of the ciphertext.

4.2        Status Control
As explained in several sections, the protocol which you are implementing in this project is an offline protocol. In other words, the messages which are sent by the sender are stored in the server until the receiver requests to get his/her messages. Moreover, ephemeral keys, which are generated by the sender and receiver, are used once (for only one message) to generate a new session key pair for encryption and MAC. Therefore, you are required to check the server for how many new messages you have and how many ephemeral keys are remaining. Moreover, you must generate new ephemeral keys and register with the server if needed. In order to be informed for new messages and remaining ephemeral keys, you must send your ID to the server as follows:

{‘ID’: stuID, ‘S’: s, ‘H’: h }

where s and h is a signature tuple which is generated for stuID using your long-term private key. If your request is valid, the server will send the number of new messages and remaining ephemeral keys. You may either get your messages from the server or

4.2.1         Registration of new ephemeral keys
In Phase II, you have generated 10 ephemeral keys and registered with the server and each ephemeral key is used for one message. On the other hand, you may send/receive more than 10 messages. Therefore, if some of your ephemeral keys are used, you must generate new ephemeral keys to cover to 10 and register with the server again. The registration protocol is explained in section 3.1.

On the other hand, more than 10 messages may be sent to a client, when s/he is offline. In this case, his/her last ephemeral key will be used more than once. For instance, if 12 messages is sent to an offline client, his/her first 9 ephemeral keys will be used for the first 9 messages and his/her 10th ephemeral key will be used for last 3 messages. As mentioned in section 3.1, you must follow the order for key IDs.

4.3          Sending message to pseudo-client for grading
For Phase III, your work will be graded automatically. After you develop the software, which is explained in Section 4.1 and Section 4.2, you are required to send the following quotes[8] to pseudoclient, whose ID is 18007. Quotes are:

1.    “The world is full of lonely people afraid to make the first move.” Tony Lip

2.    “I don’t like sand. It’s all coarse, and rough, and irritating. And it gets everywhere.” Anakin Skywalker

3.    “Hate is baggage. Life’s too short to be pissed off all the time. It’s just not worth it.” Danny Vinyard

4.    “Well, sir, it’s this rug I have, it really tied the room together.” The Dude

“Love is like taking a dump, Butters. Sometimes it works itself out. But sometimes, you need to give it a nice hard slimy push.” Eric Theodore Cartman
 
[1] https://www.youtube.com/watch?v=d27gTrPPAyk
[2] The first 8-byte of message, which you receive in this step, is nonce.
[3] All encrypted messages must be generated using unique nonce values. For each encryption, you must use AES.new(). Then, you must concatenate nonce and ciphertext.
[4] This is indeed an asynchronous messaging application, whereby other users can send you a message even if you are not online. Yes, exactly like WhatsApp application.
[5] https://www.youtube.com/watch?v=u1ZoHfJZACA
[6] For encryption, AES-CTR will be used in this project
[7] Note that, in this operation, SHA256 is used instead of SHA3-256
[8] Note that, you must send only quotes without “ ” and the names of sayers.