CMPT471 19-1 Assignment 4 1 Problem 1 (8 points), due by 17:00 March 29
(1) (4 points) Substitution and transposition are basic techniques for encryption schemes. • Below is a substitution encryption scheme example defined by permutation π:
ABCDEFGHIJKLMNOPQRSTUVWXYZ VMLCBGKYQUSOPAXEJTWFRWHPZI
To encrypt a plaintext, the scheme substitutes each character α in the plaintext by the character π(α) (e.g., A is replaced by π(A) = V ) to create the ciphertext. To decrypt the ciphertext, the scheme substitutes each character β in the ciphertext by the character π−1(β) (e.g., V is replaced by π−1(V ) = A).
• Below is a transposition encryption scheme example.
To encrypt a plaintext, the scheme (1) cuts the plaintext into segments, each segment is a string of r × n (3 × 3 in this example) characters c1c2c3c4c5c6c7c8c9; (2) puts the string of characters into an r × n (3 × 3) array A as shown below (the plaintext is read from left to right on each row and from top to bottom by rows in A); and (3) reads the elements of A from top to bottom on each column and columns in the order of (1,2,3) (from left to right) to create the ciphertext c1c4c7c2c5c8c3c6c9. The decryption is the reverse process of the encryption.
An alternative description of Step (3) of the encryption scheme above is to change the positions of characters in A by the permutation Π on the positions of A to get array Π(A) as shown below and read the characters in array Π(A) from left to right on each row and from top to bottom by rows to get the ciphertext. The transposition encryption scheme is then defined by the permutation Π on the positions of array A.
Plaintext c1c2c3c4c5c6c7c8c9,
c1 c2 c3 c1 c4 c7 c1 c4 c7 A=c4 c5 c6 Π(A)=c2 c5 c8 Π−1(A)=c2 c5 c8 c7 c8 c9 c3 c6 c9 c3 c6 c9
ciphertext c1c4c7c2c5c8c3c6c9.
To decrypt the ciphertext, the scheme (1) puts each ciphertext segment (a string of 9 characters) into a 3 × 3 array Π(A) (the string is read from left to right on each row and from top to bottom by rows); (2) move the characters at position (i,j) of Π(A) to position (x,y) defined by the inverse permutation Π−1 of Π (which defines the transposition for the encryption above) to get array A (Π−1(Π(A)) = A, in this example, Π−1 = Π); and (3) reads the characters in array A from left to right on each row and from top to bottom by rows to get the plaintext.
Below is a secret key encryption scheme framework based on the substitution and trans- position techniques shown above for secure communications between a client and a server.
• Both the server and client have a list of N security schemes S0,…,SN−1.
CMPT471 19-1 Assignment 4 2
• Each security scheme Si, 0 ≤ i ≤ N − 1, specifies a substitution encryption scheme
and a transposition encryption scheme.
The substitution encryption scheme is defined by a permutation πi on the set Σ of m characters to be used for communication.
The transposition encryption scheme is defined by a permutation Πi on the positions of the r × n array.
Si specifies a two (or multiple) stage encryption scheme, one stage uses the substi- tution scheme and the other stage uses and transposition scheme defined above for encryption. Decryption is the reverse process of encryption.
• The client and server use the Diffie-Hellman algorithm (W. Diffie and M.E. Hellman, ”New Directions in Cryptography”, IEEE Trans. on Information Theory, Vol. IT-22, Nov. pp. 644-654, 1976, or refer to the lecture notes) to deliver a secret integer k (key) between them.
• Let i = k mod N. The client and server use the security framework Si to realize a secure communication between them: the sender uses the encryption scheme speci- fied by Si to encrypt the plaintext and the receiver uses the reverse process of the encryption to decrypt the ciphertext.
Design a substitution-transposition based encryption scheme for a secure TCP connection using the above framework with N ≥ 5, r,n ≥ 4 and m ≥ 40 characters, including at least the 26 letters, numbers 0 ∼ 9, a symbol for space, and punctuation marks of comma, full stop and question mark. Write programs (in JAVA, C++ or Python, please get the approval from your TA if other languages are used) which realize a secure communication by TCP between a client and a server using your encryption scheme.
Submit a document which specifies your design for the encryption scheme, the programs which realize the secure communication, and data samples (before the encryption, after the encryption, captured from the TCP connection in the network, and after the decryption) in the secure communication.
Your programs must work in the virtual networks.
(2) (2 points) Design a stream encryption scheme (Vernam Cipher) for a secure TCP connec- tion. You may cut the plaintext into segments, each segment is one character (or two or four consecutive characters) and viewed as a segment of binary bits, and use a pseudo-random number generator at the client and server to create a sequence of integers as keys for the encryption and decryption. The client and server can use the Diffie-Hellman algorithm to share a same seed for the pseudo-random generators so that the sequence of keys created at the client is identical to that created at the server.
Submit a document which specifies your design for the encryption scheme, the programs which realize the secure communication, and data samples (before the encryption, after the encryption, captured from the TCP connection in the network, and after the decryption) in the secure communication.
Your programs must work in the virtual networks.
CMPT471 19-1 Assignment 4 3
(3) (2 points) Select an English document (plaintext) of a reasonable length (at least 500 characters) and create the ciphertext of the plaintext by your substitution-transposition based encryption scheme designed in (1) above. Find the top 5 letters in terms of the high relative frequency in the plaintext and the ciphertext by a program. Compare the relative frequencies of the top 5 letters in the plaintext and these in the ciphertext.
Create the ciphertext by the stream encryption scheme designed in (2) above, view the ciphertext as a sequence of ”letters” and find the relative frequencies of the top 5 ”letters” in the ciphertext by a program. Compare the relative frequencies of the top 5 ”letters” in the plaintext and these in the ciphertext.
Compare the relative frequencies of the top 5 ”letters” in the ciphertexts created by the substitution-transposition based encryption scheme and stream encryption scheme.
You need to submit your programs to the directory /Assignment/4/yourid (yourid is your login name to the VNL) in the gateway machine cs-vnl by the due time. Notice that /Assignment is a directory under the root directory /, you may find the directory by cd / and then ls commands. Or you may use cd /Assignment to change your current directory to /Assignment. Please have clear comments in your programs to explain how they work.
Problem 2 (0 points)
1. IP must always check the destination addresses on incoming multicast datagrams and discard datagrams if the host is not in the specified multicast group. Explain how the host might receive a multicast destined for a group to which that host does not belong.
2. The IGMP general query message is used to monitor the memberships in multicast groups. This message may cause a large number of membership report messages. Explain briefly the main techniques used in the IGMP implementation to minimize the overhead of traffic caused by IGMP messages.
3. Assume that host H sends a leave report to router R, expressing H leaves multicast group G. What is the destination address in the IPv4 datagram which carries the leave report? What is the address in the address field in the IGMP leave report? Router R sends a group specific query to confirm the leave. What is the destination address in the IPv4 datagram which carries the query? What is the address in the multicast group address field in the query?
4. For the AS in Figure 1, assume that the routing tables for unicast are computed by OSPF. Assume that G is a multicast group with members in N2, N4, N5, N6.N7 and TRPF (Trun- cated Reverse Path Forwarding) is used by routers to deliver multicast messages. When Router R5 receives a multicast message P with source N2 and destination G from interface eth0, which interfaces R5 forwards P to? If P receives P from eth1, which interfaces R5 forwards P to?
5. For the AS in Figure 1, assume that G is a multicast group with 1,3,3,4,4 members in N2, N4, N5, N6.N7, respectively; the routing tables for unicast are computed by OSPF; and
CMPT471 19-1 Assignment 4
4
R2
3
4
N3
4
2
Ν1 Ν2
N5
23 25
N7
3
8
eth0
2
8 N4
eth1 eth2
3
R4
R1
R6
R3
R5
Figure 1: An autonomous system.
a multicast tree with the member in N2 as the root is formed by the shortest paths for unicast from the root to all other members in the AS. Assume that forwarding one datagram over one network uses one unit of bandwidth. How many units of bandwidth are used if the root sends one datagram to all other members in G by multiple unicast? How many units of bandwidth are used if the root sends one datagram to all other members by multicast?
6. Main items in an NAT translation table include internal IP addresses, internal port num- bers, external IP addresses, external port numbers, NAT port numbers, and payload type. Which items are used to identify a communication session between an NAT box and an internal host? Which items are used to identify a communication session between an ex- ternal host and an NAT box? Why is the payload type included as a main item in the table?
7. Which of the encryption schemes in (1) and (2) of Problem 1 reveals more information on the relative frequencies of the letters in the plaintext?
8. Vernam cipher is a stream encryption scheme works as follows: A plaintext M of n bits is partitioned into segments S1, .., Sr, each of m bits; a stream of keys K1, .., Kr, each of m bits, are created; in encryption, the ciphertext is computed by Ci = Si ⊕ Ki, 1 ≤ i ≤ r, ⊕ is the bit-wise exclusive-or; and in decryption, the plaintext is computed by Si = Ci ⊕ Ki = (Si ⊕Ki)⊕Ki.
Assume that every key Ki,1 ≤ i ≤ r, is uniformly selected from {0,1}m at random. Let Ci = ci1..cim be the bit string of the ciphertext Ci. Prove that Pr[cij = 1] = 1/2 for 1 ≤ j ≤ m, where Pr[cij = 1] is the probability that cij = 1.
9. A transposition encryption scheme works as follows.
To encrypt a plaintext, the scheme (1) cuts the plaintext into segments, each segment is a string of 4 × 4 characters c1c2…c15c16; (2) puts the string of characters into a 4 × 4 array A as shown below; and (3) reads the elements of A from top to bottom in each column and from left to right on columns to get the ciphertext. The order of reading columns is (1, 2, 3, 4). The decryption is the reverse process of the encryption. Give the permutation Π on the positions of A that defines the encryption. Given the inverse permutation Π−1 of
N6
CMPT471 19-1 Assignment 4
5
Π that defines the decryption.
c1 c2 c3 c4 A= c5 c6 c7 c8
c9 c10 c11 c12 c13 c14 c15 c16
Assume that in the encryption, the ciphertext is obtained by reading the elements of A from top to bottom in each column and reading the columns in the order of (2, 4, 1, 3). Give the permutation Π on the positions of A that defines the encryption. Given the inverse permutation Π−1 of Π that defines the decryption.
10. DES (Data Encryption Standard) has been widely used as secret key encryption scheme for many years. However, DES has been broken and is no longer considered as very secure. What weakness do you think DES has and how would you improve the security of DES if you are asked to modify it?
11. Explain briefly how public-key and secret-key encryption schemes are combined to make a more efficient encryption scheme.
Explain briefly how a public-key encryption scheme is used in digital signature.
12. Explain how the public key and private key are computed in RSA and the encryption and decryption processes of RSA.
The PGP protocols use several encryption/decryption keys. Explain the purpose of each key.