CALIFORNIA STATE UNIVERSITY CHANNEL ISLANDS
|
COURSE: COMP 524 - SECURITY - FALL 2007
|
STUDENT: JOSIF KURUNCZI |
E-MAIL ADDRESS : jkurunczi@yahoo.com |
ASSIGNMENT #3 |
DUE DATE : October 8, 2007 |
Guideline: You are allowed to use internet to search for the answers, however it is not allowed to work with other students to solve this assignment. Each individual should solve/search the answer himself/herself.
Reading Assignment: Read Chapter 4: “Cryptographic Hash Functions”” from Fundamentals of Secure Computer Systems” by Brett C. Tjaden.
Q1) What would the subkeys for round 1, 2 and 3 of DES be if the encryption key was (in hexadecimal format):
a) D43CB19AE490D7C6
b) D43DB09AE491D7C7
DES KEY: D43CB19AE490D7C6
ROUND 1 SUBKEY:
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
ROUND 2 SUBKEY:
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
ROUND 3 SUBKEY:
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
DES KEY: D43DB09AE491D7C7
ROUND 1 SUBKEY:
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
ROUND 2 SUBKEY:
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
ROUND 3 SUBKEY:
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
Q2) If DES keys has been 128 bits long as IBM originally proposed, how long would one million computers, each trying one trillion keys per seconds, take to examine all possible keys. Assume perfect parallelism that is no two possible keys are examine by more than one computer. Provide approximate calculation.
In 1 second we have 1 trillion 1012 instructions
1 minute = 60 seconds
1 hour = 60 minutes = 3,600 seconds
1 day = 24 hours = 86,400 seconds
1 year = 365 days = 31,536,000 seconds
In 1 year one computer will execute 31,536 x 1015 instructions.
In 1 year 1,000,000 computers will execute 31,536x1015 x 106 = 31,536 x 1021 instructions.
A 128-bit DES key has 2128 combinations.
2128 = 3.4028236692092846346337460743177 x 1038
It will take 2128 divided by 31,536 x1021= 3.4028236692092846346337460743177 x 1038 / 31,536 x1021 years to go through all the combinations.
The answer is = 10,790,283,070,806.01418897052915499 years.
Q3) All zeros (000000000….) and all 1’s (11111111……) are weak DES keys. Explain why these keys are weak. (Hint: consider the subkeys that they generate and the effect these subkeys have on each round of the algorithms).
All zeros will generate all zeros initial permutation, which will be reduced to a 56-bit digit of all zeros. From here two blocks of 28-bits will be generated and then both blocks will be circularly left shifted. The result of these will be all zeros. The “key bit” that is generated is still all zeros. Going through the 16 rounds all subkeys are going to be all zeros.
The same happens with all ones. All ones will generate all ones initial permutation, which will be reduced to a 56-bit digit of all ones. From here two blocks of 28-bits will be generated and then both blocks will be circularly left shifted. The result of these will be all ones. The “key bit” that is generated is still all ones. Going through the 16 rounds all subkeys are going to be all ones.
These are the weakest keys since it is the easiest to guess.
Q4) How does message digest keep the integrity of the message intact?
A hash function or message digest keeps the integrity of the message intact by using a Message Authentication Code (MAC). The Message Authentication Code (MAC) is a special encrypted message digest function that is key (K) dependent. It looks like this: MAC(M,K) = h. DES can be used to encrypt the message.
Someone who wants to comprimise data integrity must know the key (K) in order to compute and verify the hash function (h). Only authorized users how know the key (K) can create of verify a Message Authentication Code (MAC).
Q5) Explain one security hole in using message digest without any encryption. Explain that how could you avoid this security hole?
To explain this consider the properties of a one-way hash function:
1) given M, it is easy to compute h
2) given any h, it is hard to find any M such that H(M)=h
3) given M1, it is difficult to find M2 such that H(M1)=H(M2)
The security hole could be property 3). Even though it is difficult to find M2, it is not impossible. If the message digest has m bits, it would take about 2(m/2) messages, chosen at random before one would find two with the same value. This means that if there were a 64-bit message digest function someone could search 232 messages before it can find two with the same value. In order to avoid this security hole use a message digest that has over 1024 bits. With this it would take 2512 messages to find two with the same value. With the current hardware today this could be quite unfeasible at this time.