Johnny, an Ontario Tech graduate recently got a job at CSE in Ottawa. As part of...

 

Transcribed Image Text:

Johnny, an Ontario Tech graduate recently got a job at CSE in Ottawa. As part of a pilot project, every month CSE announces a list of 3 prime numbers (all less than 25) in proxy repositories which automatically sign the 3 numbers for Navy bases across the Country to fetch them. These numbers become part of public keys so confidentiality is not required, only signature. In his very first day at work, Johnny volunteers to take charge of the automatic signature generation in the Bay of Fundy proxy (as, according to Johnny, it was close enough to his native St. John's). He decided to sign the 3 numbers using a hash value consisting of the bitwise XOR amongst the bit representation of these 3 numbers and then encrypting the hash value using CSE's private RSA key. Further, he made sure his automatic process only signed the numbers if all of the 3 numbers were prime (i.e., if at least one of the 3 numbers were composite the process would refuse to sign). Last month's numbers were {251, 157, 191}. Johnny's program computed the hash to be 217 (because 251 XOR 157 XOR 191 = 217) which then was encrypted with RSA and appended to the set of numbers as signature. Shortly after, CSE suspected a probable compromise of the Bay of Fundy proxy since the Nova Scotia Navy Base ended up using composite numbers in their crypto operations causing serious disruptions in the pilot project! During his debrief, Johnny claimed that to forge the signature with probability 1/2, 28 27 128 sets of 3 random an attacker would need to compute the hash values of = 2 composite numbers, not to mention that the attacker would require to break RSA. But his boss, an experienced cryptographer advises that Johnny's claims were overly optimistic, saying that the attacker could forge a signature with probability greater than ½ by computing the hashes of only 28/2 = 24 =16 (not 128) sets of 3 random composite numbers, and that the attacker wouldn't even have to break RSA at all. Johnny was speechless! In her explanation, Johnny's boss alluded to the birthday paradox, a concept that for some reason Johnny never quite grasped while taking Crypto at Ontario Tech. Help Johnny understand the birthday paradox, after the fact, by following these steps in a Python program: (Notes: Of course, Johnny wasn't so naïve as to suggest such a simple scheme for signing; in reality he was using SHA- 256 but here we are simplifying things just to get the concept across (see Question 4). Also, CSE uses prime numbers in the order of 22048, not 2. As per Johnny's future at CSE, don't worry; his boss decided to give him a second chance. Johnny was spotted last evening close to the ByWard Market enjoying a beaver tail with his partner.) C (a) Compute the hashes of 24 = 16 sets of 3 random prime numbers less than 28. (b) Then keep selecting sets of 3 fraudulent composite numbers less than 28 until you find a set {C₁, C2, C3} with a hash value that matches one of the hashes computed in step (a); we will refer to that matching set as {p1, P2, P3}. (c) Explain to Johnny that the attacker would replace the legitimate prime set {251, 157, 191} with the fraudulent composite set {C1, C2, C3} in the Bay of Fundy proxy server. The attacker would then use Johnny's automatic signing process to sign the prime set {P₁, P2, P3} and append such signature to the composite set (C1, C2, C3). At this point the attacker has been successful at signing the composite set {C₁, C2, C3} without knowing CSE's RSA private key and by computing just over 16 hashes (i.e., 16 from Part (a) + some from Part (b)). (d) Submit your Python code and a screenshot like the one depicted in the figure below. 16 valid 157 7 67 29 149 13 227 17 83} {47 223 73 149 103 167 [229 197 73 [ 41 53 53 ) || {71 251 179 ) || 53 59 19 (149 227 151} | 225 [103 167 29221 { 79 113 223 |{ messages: 11 ) 89 } || 97 } || [ 7 211 83 IC 13 3 79 ) 145 7 249 161 185 85 105 41 15 29 225 | 135 1 65 C:\Windows\system32\cmd.exe 19 211 89 ) 153 looking for a fraudulent message that matches a valid message's hash... collision found after 3 attempts: 103 167 29 ) 221 { 74 135 16 ] | 221 Press any key to continue I Johnny, an Ontario Tech graduate recently got a job at CSE in Ottawa. As part of a pilot project, every month CSE announces a list of 3 prime numbers (all less than 25) in proxy repositories which automatically sign the 3 numbers for Navy bases across the Country to fetch them. These numbers become part of public keys so confidentiality is not required, only signature. In his very first day at work, Johnny volunteers to take charge of the automatic signature generation in the Bay of Fundy proxy (as, according to Johnny, it was close enough to his native St. John's). He decided to sign the 3 numbers using a hash value consisting of the bitwise XOR amongst the bit representation of these 3 numbers and then encrypting the hash value using CSE's private RSA key. Further, he made sure his automatic process only signed the numbers if all of the 3 numbers were prime (i.e., if at least one of the 3 numbers were composite the process would refuse to sign). Last month's numbers were {251, 157, 191}. Johnny's program computed the hash to be 217 (because 251 XOR 157 XOR 191 = 217) which then was encrypted with RSA and appended to the set of numbers as signature. Shortly after, CSE suspected a probable compromise of the Bay of Fundy proxy since the Nova Scotia Navy Base ended up using composite numbers in their crypto operations causing serious disruptions in the pilot project! During his debrief, Johnny claimed that to forge the signature with probability 1/2, 28 27 128 sets of 3 random an attacker would need to compute the hash values of = 2 composite numbers, not to mention that the attacker would require to break RSA. But his boss, an experienced cryptographer advises that Johnny's claims were overly optimistic, saying that the attacker could forge a signature with probability greater than ½ by computing the hashes of only 28/2 = 24 =16 (not 128) sets of 3 random composite numbers, and that the attacker wouldn't even have to break RSA at all. Johnny was speechless! In her explanation, Johnny's boss alluded to the birthday paradox, a concept that for some reason Johnny never quite grasped while taking Crypto at Ontario Tech. Help Johnny understand the birthday paradox, after the fact, by following these steps in a Python program: (Notes: Of course, Johnny wasn't so naïve as to suggest such a simple scheme for signing; in reality he was using SHA- 256 but here we are simplifying things just to get the concept across (see Question 4). Also, CSE uses prime numbers in the order of 22048, not 2. As per Johnny's future at CSE, don't worry; his boss decided to give him a second chance. Johnny was spotted last evening close to the ByWard Market enjoying a beaver tail with his partner.) C (a) Compute the hashes of 24 = 16 sets of 3 random prime numbers less than 28. (b) Then keep selecting sets of 3 fraudulent composite numbers less than 28 until you find a set {C₁, C2, C3} with a hash value that matches one of the hashes computed in step (a); we will refer to that matching set as {p1, P2, P3}. (c) Explain to Johnny that the attacker would replace the legitimate prime set {251, 157, 191} with the fraudulent composite set {C1, C2, C3} in the Bay of Fundy proxy server. The attacker would then use Johnny's automatic signing process to sign the prime set {P₁, P2, P3} and append such signature to the composite set (C1, C2, C3). At this point the attacker has been successful at signing the composite set {C₁, C2, C3} without knowing CSE's RSA private key and by computing just over 16 hashes (i.e., 16 from Part (a) + some from Part (b)). (d) Submit your Python code and a screenshot like the one depicted in the figure below. 16 valid 157 7 67 29 149 13 227 17 83} {47 223 73 149 103 167 [229 197 73 [ 41 53 53 ) || {71 251 179 ) || 53 59 19 (149 227 151} | 225 [103 167 29221 { 79 113 223 |{ messages: 11 ) 89 } || 97 } || [ 7 211 83 IC 13 3 79 ) 145 7 249 161 185 85 105 41 15 29 225 | 135 1 65 C:\Windows\system32\cmd.exe 19 211 89 ) 153 looking for a fraudulent message that matches a valid message's hash... collision found after 3 attempts: 103 167 29 ) 221 { 74 135 16 ] | 221 Press any key to continue I

Answer rating: 100% (QA)

include using namespace std int main ... View the full answer