Security and Cryptography (CSS 322)

Answers and Results

Tasks 1 and 2

For those that could not get RC4 working correctly, in Task 3 you can use the code of other groups. Here is an example that you may use, courtesy of Thanapa Chimmi and Ekaphan Pattanavijit. Their group was the first to submit which had both Diffie-Hellman and RC4 working correctly.

Results and comments on Tasks 1 and 2 are here. I have given a score out of 10 for each task (Diffie Hellman and RC4). The tasks may not be equally weighted (that is, in the final assignment score, the RC4 task will be weighted higher than the Diffie Hellman task - the weights will be determined once all tasks are completed).

Although most people implemented Diffie Hellman ok, some groups used bcmod(bcpow(a,b),q) instead of the much more efficient bcpowmod(a,b,q). When using large numbers, calculating exponentials (power) is time consuming EXCEPT if using modular arithmetic because then the algorithm can take advantage of the multiplication expansion covered in lectures, i.e. (axaxa)mod n = [((axa) mod n)x(a mod n)]mod n.

Task 3

Results and comments on Task 3 are here. An explanation of scores and comments follows:

1. PU Score (out of 5): 5 marks were given if you emailed me ciphertext that successfully decrypted using RC4 and our shared secret key K. If you did not send me the encrypted Public key, or it did not successfully decrypt, then you received 0. For some groups although the decryption was successful, their value of e was 1 - they received only 2 marks.
2. E/D Score (out of 5): 5 marks were given if your implementation of RSA Encrypt and Decrypt were correct. If you did not implemented these functions or they were wrong, you received 0 marks. Some groups passed in both the public key and private key to the function. That is incorrect: only one key can be passed in (because in most cases only one key will be known when encrypt/decrypt are used). Those groups received 2 marks.
3. Gen Score (out of 10): Score for the implementation of GenerateKeys. You lost marks for the following:
   • Using Sec_Totient() to find the totient of n, instead of calculating directly from p and q: (p-1)*(q-1). For large n, Sec_Totient will take too long.
   • Not (correctly) checking that p and q are not equal.
   • Not checking that the value of e chosen is not equal to 1.
   • Not checking that, when choosing e, there may be less than 100 possible values (thereby if you choose a random index between 1 and 100, but there are less than 100 values in the array, you may get an error).
   • Including echo statements in the functions (it is ok to use echo statements for debugging and testing purposes, but they should not be sent in the final code you submit).
   • Not checking that e and d are not equal (however you did not lose any marks for this).

Assignment

This assignment requires you to implement some simple security algorithms, and apply them. Everything is to be implemented in PHP. Although at first it may seem very difficult, PHP has been chosen because eventually you will find you only need several lines of code to implement most the algorithms. The assignment is a group task (groups of 2 - see the group list). Any cheating between groups, or copying code from the Internet will be penalised.

PHP

This assignment involves developing and using ciphers using PHP. I have a brief overview of using PHP which should be sufficient to get users new to PHP started. In addition I provide template PHP source code (Note: after downloading the template source code, change the file extension from .txt to .php). You should use this template and make use of the functions provided.

Terminology and Formats

• The system consists of multiple entities, which are either groups or the CA.
• Each group is identified by their number, e.g. Group01, Group02, ..., Group30. Each group also has an email address, e.g. [email protected].
• The Certificate Authority is identified as CA. Its email address is [email protected].
• Communications between entities is via email. Each email must be in the following format:
  • To: the email address of the destination entity (group or CA)
  • Subject: CSS322 Assignment message
  • Body:

    From: Entity
    To: Entity
    Task: Number
    ---Start of message
    [contents of the message]
    ---End of message
    

  As an example, an email in Task 1 sent by Group 1 to the CA ([email protected]) would have the contents:

  From: Group01
  To: CA
  Task: 1
  ---Start of message
  4637
  ---End of message
  

Task 1

Complete the following steps:

1. Implement Diffie-Hellman Key Exchange. Use q = 128903289023 and a = 23489.
2. Using Diffie-Hellman, initiate an exchange with the CA to establish a shared secret key with the CA. The CA may take up to 24 hours to respond.

Task 2

Once the secret has been shared with the CA, the CA will send a message encrypted using RC4 and the shared key.

1. Convert the secret generated by Diffie Hellman (a decimal integer) into a key that can be used by RC4 using the function Crypto_SecretToRC4Key().
2. Implement RC4.
   • RC4_Encrypt() needs to convert the plaintext string into binary values (e.g. using Crypto_ASCII2BinString($plaintext,8), where each character is converted to an 8 bit value). Then it should call RC4_GenerateStream() to generate a stream to XOR with the plaintext. For example, if the plaintext is 3 characters (and hence 24 bits), then RC4_GenerateStream() will output a 24 bit stream. Once the XOR has been performed, RC4_Encrypt() should convert the binary ciphertext to Hex using Crypto_BinString2Hex().
   • RC4_GenerateStream() needs to initialise the state vectors, perform the initial permutation and generate the stream, which is multiple values of k. In the Lecture Notes, the RC4 algorithm generates values of k forever (infinite while loop). However in your code you only need to generate enough values to XOR with the plaintext. Therefore if you have 3 characters of plaintext, then you will generate 3 values of k, convert them to binary, concatenate them and return.
   • If you want to convert between a string and array in PHP you can use str_split() and implode().
   • The following can be used to test your implementation of RC4:

     $s = '1234567890';
     $k = Crypto_Secret2RC4Key($s);
     $p = 'MyNameIsSteve';
     $c = RC4_Encrypt($p,$k);
     $p2 = RC4_Decrypt($c,$k);
     echo $p2 . "\n" . $c . "\n";
     // Output:
     // MyNameIsSteve
     // 4e1f055b160ef902bd6ddd6d77
     

3. Decrypt the ciphertext published here.
4. Submit the plaintext of the received ciphertext and source code for Diffie Hellman and RC4 via email to [email protected] by 9:00am Wednesday 20 January 2010. The email must contain the following (where you replace XX with your group number and YY with the value of the plaintext):
   • Subject: CSS322 Assignment Task 2: GroupXX
   • Body:

     Group: XX
     Plaintext: YY
     

   • Attachment: your PHP code, with the file named as task2-groupXX.php

Task 3

1. Implement RSA.
   • The function RSA_GenerateKeys() should randomly select primes p and q where 10,000 < p, q < 100,000.
   • The value of e should be randomly chosen from the the first 100 valid values (note sometimes there may be less than 100 valid values of e).
   • Make sure your implementation performs the necessary checks that correct values are used.
2. Generate your groups RSA keys. Make sure you record the values of p and q for your keys.
3. Ecnrypt your public key using RC4.
   • To encrypt the public key, you first need to convert it into a string using serialize(). For example:

     $RSAkeys = RSA_GenerateKeys();
     $rsapu = serialize($RSAkeys['pu']);
     echo $rsapu . "\n";
     $c = RC4_Encrypt($rsapu,$rc4key);
     echo $c . "\n";
     // Output:
     // a:2:{i:0;s:3:"115";i:1;s:10:"1028823403";}
     // 625c790000028a41d56a822828b64b95e0929dd879317d2c6f02f9920affc8e28e6b5dbc9bb227230f5f
     

4. Submit the encrypted public key and source code for RSA via email to [email protected] by 9:00am Tuesday 26 January 2010. The email must contain the following (where you replace XX with your group number and YY with the value of the encrypted public key):
   • Subject: CSS322 Assignment Task 3: GroupXX
   • Body:

     Group: XX
     Encrypted Public Key: YY
     

   • Attachment: your PHP code, with the file named as task3-groupXX.php

Task 4

Your group certificates (as well as the ID of your destination partner group) are available here. Each certificate is a string of the form:

PublicKeyOfUser IDOfUser Signature

where:

• PublicKeyOfUser is your Public Key in serialized form
• IDOfUser is your Group ID, e.g. Group01
• Signature is the signature from the CA. Note that the CA uses RSA to sign, as well as the hash function Hash_Simple(), which is available in the updated template PHP source code.

Note that the items are separated by a single space. Therefore one method to extract the certificate into 3 variables in PHP is:

$n = sscanf($certificate,"%s %s %s",$publickey,$id,$signature);	

The certificate of the CA (which you can trust is correct - it is signed by the CA itself) is:

a:2:{i:0;s:2:"97";i:1;s:10:"2845014301";} CA 866909010

Using the above information, complete the following steps:

1. Download and validate your groups certificate.
2. Download and validate your destination partner groups certificate.
3. Take the first 8 digits of your secret key from Task 1 and send it confidentially, as well as signed to your destination partner group. Use RSA and Hash_Simple for the signature and confidentiality.
4. When you receive a signed, confidential message, decrypt and validate it. If the message is valid, send the plaintext to the CA [email protected] containing:
   1. Your group ID
   2. The plaintext
   3. Values of p and q for RSA key
   4. Value of d for RSA key
   (If the message you received is invalid, see below). The CA will respond within 24 hours to indicate any further instructions.

Importantly, if a certificate or message validation fails then you must send an email to the CA [email protected] indicating your group ID, the certificate or message that failed validation, and the PHP code you used to determine the failure (do not send as an attachment; simply copy the relevant PHP lines into the body of the email - no functions are necessary). The CA will respond within 24 hours with further instructions.

Bonus points will be given to the first X groups that send correct messages to the CA (either with the plaintext or indicating an invalid message). You will lose points if you send incorrect messages to the CA.

You must complete the first 3 steps (including sending to your partner group) by 12noon Friday 5 February. You must complete all steps by 12noon Monday 8 February.

Examples and Test Vectors

The following shows an example of applying Diffie-Hellman, RC4 and RSA.

/* Diffie-Hellman example */
echo "Diffie-Hellman Example\n";
$Xa = '123451';
$Xb = '2435243';
$q = '128903289023';
$a = '23489';
$Ya = DH_GeneratePublic($q,$a,$Xa);
$Yb = DH_GeneratePublic($q,$a,$Xb);
$Ka = DH_GenerateSecret($q,$Xa,$Yb);
$Kb = DH_GenerateSecret($q,$Xb,$Ya);
echo $Ka . " " . $Kb . "\n";

/* RC4 Example */
echo "RC4 Example\n";
$p = 'pedia';
$k = array(87,105,107,105);
$c = RC4_Encrypt($p,$k);
echo $p . " " . $c . "\n";
print_r($k);

/* RSA Example */
echo "RSA Example\n";
$RSAkeys = RSA_GenerateKeys();
print_r($RSAkeys);
echo RSA_Encrypt("1034",$RSAkeys['pu']) . "\n";

The output of the above code was (note that the example used small values of p and q for RSA - you need to use larger values as described in Task 3):

Diffie-Hellman Example
68772533355 68772533355
RC4 Example
pedia 1021bf0420
Array
(
    [0] => 87
    [1] => 105
    [2] => 107
    [3] => 105
)
RSA Example
Array
(
    [pu] => Array
        (
            [0] => 191
            [1] => 31937
        )

    [pr] => Array
        (
            [0] => 16511
            [1] => 31937
        )

    [p] => 293
    [q] => 109
)
27094

Return to: CSS322 Home | Course List | Steven Gordon's Home | SIIT