Midsems - 2017
=== Question 0 ===
(3 Marks)
What is the most important property for a cryptographic hash function to have to make it as resistant as possible to birthday attacks?
.[A] Preimage resistance
.[B] Collision resistance
.[C] Confidentiality
.[D] Symmetry
.[E] Second-preimage resistance
.[F] Non-determinism
A birthday attack is a cryptographic attack that has its roots in the following statistical scenario: If we are looking for at least a 50% chance that a particular person shares the same birthday with someone else in a room, we need at least 253 people; but if we are looking for just any one pair of people sharing the same birthday, we only need 23. A birthday attack exploits the exponential growth of the latter scenario by brute forcing a hash function to try find any random pair of inputs that output the same hash (i.e. a collision). Hence, a hash function will need strong collision resistance - B.
=== Question 1 ===
(3 Marks)
You are a developer of opensource fake-news software called "The trumpet shall sound", or "Trumpet" for short. You wish to use a cryptographic algorithm to generate a 64 character "digital fingerprint" of the "Trumpet" binary, which you will display on your web site so that people can check that they have downloaded a legitimate and unaltered copy of "Trumpet".
What is the most important property for this cryptographic fingerprint algorithm to have?
.[A] Preimage resistance
.[B] Collision resistance
.[C] Confidentiality
.[D] Symmetry
.[E] Second-preimage resistance
.[F] Non-determinism
Lets quickly revise the properties of a solid cryptographic function:
First pre-image resistance: it is easy to give an input to turn into a hash, but hard to reverse a hash to find the original input
Second pre-image resistance: given an input and its hash, it is hard to find another input that gives the same hash
Collision resistance: it is tough to find any pair of inputs that give the same hash
In this case, the idea of a digital fingerprint is to make sure you have an authentic version of product. That purpose would be defeated if a hacker could have an unauthentic product passing off as real by giving the same digital fingerprint as the real thing. Thus, the second pre-image resistance property would be the most important in this case - E.
=== Question 2 ===
(3 Marks)
A MAC is designed to provide
.[A] Neither Integrity nor Authentication
.[B] Authentication but not Integrity
.[C] Integrity but not Authentication
.[D] Integrity and Authentication
.[E] A Very Fashionable Device
A message authentication code (MAC) is a form of symmetric key encryption technique used to verify that a message came from the intended source and is unaltered. A sender and receiver shares a secret key. When the sender sends a message, the secret key is appended to the message, then hashed (the MAC). The message and the MAC are both sent to the receiver. Upon receipt, the receiver can verify that the message came from the source and that the message is unaltered from its original form by hashing the message with the secret key and comparing with the MAC. Hence, integrity and authentication are provided - D.
=== Question 3 ===
(3 Marks)
You have a password file of 1,000 password hashes. Assuming that 50% of the passwords used were weak passwords which can be found in a dictionary of 1,000,000 common passwords, and that hashing a password takes 12 bits of work on average, roughly how many bits of work would it take to discover all these 500 or so weak passwords?
Note: only enter DIGITS in your answer (or else the automarker will mark it wrong.)
To find the 500 or so weak passwords, we can hash the 1,000,000 common passwords in the dictionary, then compare it with the 1,000 password hashes in the file. Each password hash takes 12 bits of work on average, that is, 2^12 guesses on average. So:
2^12 amount of work * 1,000,000 passwords =~ 2^12 * 2^20 = 2^32. Therefore 32 bits of work. The work associated with the actual comparing of the hashes to the file is negligible.
=== Question 4 ===
(3 Marks)
As for Question 3 but now assume that each password is appended to a different 32 bit number (a salt) before the hash was computed, and that the salt number for each password hash is stored, unencrypted, next to the hash in the password file.
Roughly how many bits of work would it take to discover all the 500 or so weak passwords in this case?
Note: only enter DIGITS in your answer (or else the automarker will mark it wrong.)
For this question, we can’t use the previous method of just computing a rainbow table and comparing it with our password file hashes because the file hashes have been salted.
On average to discover a weak password, we will need 1,000,000/2 = 500,000 hashing attempts. There are 500 weak passwords. So:
2^12 work * 500,000 attempts * 500 passwords =~ 2^12 * 2^19 * 2^9 = 2^40 work
On average when encountering a strong password, we will need to exhuasatively try all 1,000,000 dictionary words before determining it is not one of the weak passwords in the file. There are 500 strong passwords. So:
2^12 work * 1,000,000 attempts * 500 passwords =~ 2^12 * 2^20 * 2^9 = 2^41 work.
2^40 + 2^41 =~ 2^41, therefore 41 bits of work.
=== Question 5 ===
(3 Marks)
Below are six lists of expenses submitted by six politicians. Sadly 3 of the politicians are dishonest and submitted made-up fake expense claims, not costs that they really incurred. :(
{{{
Albus Bert Carl Dave Egon Fred
269 6,296 543 1,137 503 206
1,428 3,217 220 638 4,195 74
3,840 520 3,080 696 5,780 257
2,163 456 5,070 543 7,774 350
165 111 108 113 986 50
2,701 2,176 8,078 145 884 426
339 476 7,963 313 6,530 3,226
64 2,607 68 236 50 108
942 824 2,457 701 9,801 94
17 10 7,952 422 5,717 17
423 112 5,332 5,723 29 158
37 13 5,705 964 3,933 609
723 9,048 8,851 750 6,122 5,769
172 295 99 7,905 91 19
498 165 6,424 9,953 89 275
5,583 3,008 48 491 19 898
56 1,396 8,339 2,675 758 506
158 19 1,945 8,212 427 3,467
1,244 238 916 897 8,503 9,217
2,445 51 3,618 392 3,617 26
866 921 4,219 941 338 1,349
}}}
Correctly identify the status of each politician.
==== 5.1 Albus ====
.[A] Honest
.[B] Dishonest
==== 5.2 Bert ====
.[A] Honest
.[B] Dishonest
==== 5.3 Carl ====
.[A] Honest
.[B] Dishonest
==== 5.4 Dave ====
.[A] Honest
.[B] Dishonest
==== 5.5 Egon ====
.[A] Honest
.[B] Dishonest
==== 5.6 Fred ====
.[A] Honest
.[B] Dishonest
One approach to this question is understanding that generally fake-up expenses should be inflated because human-nature of greed. Summing up all the expenses of individual politicians, the hugely inflated expenses will likely be the dishonest ones - C, D, E.
==== Part B ====
This part is worth 10 marks and consists of 1 question. Spend about 10 minutes on it.
=== Question 6 ===
(10 Marks)
What is the 5th word in the plaintext for the ciphertext below?
{{{
HHPET IAESR DTEHN SRAKA UASMI UEOYR CNWOK FNERA TRONE TNYLO
SOENO OHDAS RYUSW DONUR BNSGI STLAU HTTOO DSAHE EWSYO SRTEC
IFHWO EHNOC TIHGM AENUB EAERW DEYRV EYHTA OUGNS WSODE ROEVN
HLTLA ESSEE SRTEC ONSDA YVREE SNIEO ENHTI IAKRD WOENN AYROA
EOHTN OIYFR SAERU TNABU IIGNH RAAPN IFROK NSATN TEUBC OODUY
NOKTN AWHTO CAOLT AECDK TIENB RSUBI IEFDI ETFYF NTEBE YAHTE
LUBRO TNEKA YHNET EURAO ENHTI EAKRD HETNV YUHGO EURAO COATN
LULAT HITNY KDRAE
}}}
The cipher questions we will receive in the exam will most likely be either substitution or transposition, anything else will probably be way too hard in the time pressures of a 1 hour exam. It is good to first scan the cipher for any possible patterns, and consider various methods such as letters across different blocks, reverse order, forward order, rearrangement of letters in blocks, etc. A quick inspection of the cipher, I notice that I see the group of letters T,H,E occuring together several times. Since a tranposition cipher only rearranges the leters, it is highly likely that this group of letter could refer to the common word THE. The pattern turns out to be a rearrangement of letters in the blocks with the original order of the text formed by reading in the order {5, 2, 4, 3, 1} -> {1, 2, 3, 4, 5}. We get: THEPHRASEINTHEDARKASIAM... So the 5th word is DARK.
(==== Part C ====
This part is worth 20 Marks and consists of 1 question. Spend about 20 minutes on it.
=== Question 7 ===
(20 Marks)
Suppose we convert letters and other characters into numbers in the range 1..54 using the following table and then separately encipher each of these numbers using RSA with a public encryption key of 23 and a modulus of 55.
{{{
1 < 21 L 41 4
2 > 22 M 42 5
3 ? 23 N 43 6
4 / 24 O 44 7
5 : 25 P 45 8
6 ; 26 Q 46 9
7 “ 27 R 47 (
8 ' 28 S 48 )
9 @ 29 T 49 *
10 A 30 U 50 +
11 B 31 V 51 ,
12 C 32 W 52 -
13 D 33 X 53 .
14 E 34 Y 54 /
15 F 35 Z
16 G 36 SPACE
17 H 37 0
18 I 38 1
19 J 39 2
20 K 40 3
}}}
For example the plaintext ":)" would be converted into 5,48, and then each of these numbers would be individually encrypted using RSA to produce the cipertext 15,42.
The remainder of this question has been encrypted using RSA with an encryption key of 23 and a modulus of 55.
{{{
24,18,49,16,48,49,33,10, 2,12,
52,49,48,16,19,20,16,24,18, 2,
7,16,31,50,49, 7,24, 2,19,12,
16,18,10, 7,16,11,49,49,12,16,
49,12,23,48,34, 5,24,49,52,16,
50, 7, 2,12,26,16,48, 7,10,16,
43, 2,24,18,16,10,12,16,49,12,
23,48,34, 5,24, 2,19,12,16,25,
49,34,16,19,20,16,29,35,16,10,
12,52,16,10,16,33,19,52,50,21,
50, 7,16,19,20,16, 3, 3,47,16,
16,24,18,49,16,10,12, 7,43,49,
48,16,23,19,52,49,43,19,48,52,
16, 2, 7,16,53,53,53,53,53,53,
53,53.
}}}
What is the answer codeword?
You’ll need to understand how RSA cryptography works to solve this question. RSA works by having any user maintain a public key for encrypting messages (e,N) and private key (d,N) for decrypting messages. As the name implies, anyone can access the user’s public key to encrypt messages, but only the user can decrypt the messages with their private key.
To decode the codeword in the example, we need to brute force and find the private key. In this case, the user has chosen the public key (23,55). Lets consider how we can form our private key.
The traditional steps to generating a set of public and private key are as follows:
Choose any 2 prime numbers P and Q.
Calculate N = PQ.
Calculate Euler’s totient φ(N), which refers to how many numbers less than N are also co-prime (does not share common factors) with N. An easy formula to quickly calculate this is φ(N) = (P - 1)(Q - 1)
Choose an encryption key e by choosing a number that satisfies the properties
1 < e < φ(N), and co-prime with φ(N) and N
Choose a decryption key d by choosing a number that satisfies
e*d mod φ(N) = 1
We know that e = 23, N = 55. We can easily work out that the only possible combination of P and Q that gives N = 55 is P = 5 and Q = 11. φ(N) = (5 - 1)(11 - 1) = 40. So we can find d by solving for 23*d mod 40 = 1. Probably in this exam d will be the first instance that satisfies the condition (otherwise we could go on forever brute forcing). So lets try d = 7 to give the decryption key (7,55).
For a text, we can encode with RSA by using (t^d) mod 55 = c. Similarly, to decode a cipher text c, we need to simply apply (c^d) mod 55 = t. Working through the text applying t = (c^7) mod 55, we get our text “THE REMAINDER...” (You can decode the rest yourself :).
0 notes