Name____________________________________

 

ICOM 5018 EXAM I - Spring 2005

March 3, 2005

 

Open books and notes. Only the text, slide printouts and your own notes may be used.

In the interests of originality and creativity please turn off all electronic communication devices including celulares, laptops, pocket computing devices and telepathic capability if you have it.

1.       The following relate to symmetric (private-key) cryptography.

a.       The RC4 algorithm is described on page 194ff.  It is used in IEEE 802.11, which is the usual standard for wireless networks (PRTC uses it in its DSL modems).  The keyword to be used is a 10-digit decimal number printed on the bottom of the modem.

i.                     Assuming that number is truly random, what is the expected time to discovery by brute-force analysis.  Assume the data rate is 11 Mbits/sec and that the device is running continuously.

Average detection time = Average attempts * bits_in_detectable_sample/bitrate
Assume bits_in_detectable_sample=50 bits about 6 characters – I got 18000 sec – 5 hours

ii.                   What is the propagation length for a single-bit reception error?  Explain how you obtain this result.  (Read carefully).

One bit – the single-bit error is xor’ed with the stream, and only that single-bit is in error

b.       RC5, described on page 188ff, is not a Feistel block cipher, but it is invertible.  Each round uses three types of operations.  Please answer the following.

i.                     The three operations are as described.  If shifting is replaced by Galois field multiplication, what do you use for an inverse of this operation?

You have to derive the inverse of the side input in the Galois field – this takes a modified Euclid’s algorithm, which takes 2w steps.


ii.                   Why is addition mod 2w rather than addition mod a prime used?

Addition mod 2w covers the entire space, addition mod a prime doesn’t, because a 2w bit prime is smaller.

iii.                  Suppose the connection to the right input of the first XOR on the left of the encryption round is moved just after the right hand XOR instead of before it.  How does this make the cipher no longer invertible.

It creates a feedback loop.

iv.                 Suppose instead the connection is moved to just ahead of the addition of S(1).  Is this now invertible?  Explain.

Yes, no feedback loop is created, so you can just reverse the direction of signal flow and replace each operation by its inverse.

 

2.       The following apply to public-key cryptography.  Please answer the following, briefly, but avoiding the dreaded RADQ.

a.       Text problem 9.7

Answer


b.       Text problem 11.6.

Answer

3.      On the following page is the description of a seminar to be given tomorrow.  Since it relates quite closely to the material of this course I chose to ask about some of the implications of this proposal.

a.       The proposal implies that at least a public-key, with its associated private key is stored in the smart card.  It also implies that the smart card actually computes the signature of the memo.  What information does Bob need at the receiving end to foil a person-in-the middle attack that suppresses this message and substitutes another?

Either Alice’s public key, distributed separately, or some other independent secret.

b.       Suppose the corrupted software in the conference computer can substitute a different message to the smart card for signature computation and transmission.  Can you devise a protocol that works by splitting the message in two or more parts, and mixing some of the verification info.  (This is an email transaction, so you can’t use a challenge/response method or anything that depends on a reply).

You can’t use a feedback message, but you can use clocks set some time before, and a significant delay between messages.  Then the idea is to transmit something based on the encrypted version of the message yet to be sent inside the first segment.  Then Mallory doesn’t know what information to fake.


c.       The proposal mentions the use of artificial intelligence techniques to achieve data integrity in this protocol.  What would be a possible nature and benefit of this method?

The idea is to use something the computer can’t detect readily, but that a human user can.  An example is for Bob to know anything legitimate contains 7 Spanglish spellings or other odd grammar, such as list, etc. (this is incorrect in English, typical in Spanish); the misspellings might include profesor, analisis, assisting at a meeting, or buying textbooks at the library.

 

The description below is taken from the announcement of a seminar Enabling Humans to Sign by Dr. Andre L. M. dos Santos of Georgia Tech to be given October 4, 2005.  The description is slightly shortened.  You may remove this page from the exam if convenient.  These comments form the basis for problem 3 of the exam, which is on the previous pages.


Suppose Alice is on a trip to a computer security conference. Her coworker, Bob, stays behind. Suddenly, Alice remembers that she forgot to send an important memo to Bob. She decides to an email to Bob in order to sign the memo. Because Alice always carries a smartcard that has her private key, she can sign the memo using a smartcard that has her private key. She sits down at a conference computer, plugs her smartcard into the computers reader, and types out the memo. She presses the send button, and the memo is sent to her card for signing; the signature comes back to the computer and is emailed with the memo to Bob. Or is it? What did the smartcard really sign? How does Alice know its the same thing that was on her screen? How does Alice even know if anything was sent to her card?  The Public computers are convenient, but those computers act not in the interests of their users, but of programs running inside them. Even if the owner of a computer is trusted, there is no guarantee that the system is not actually under the control of a virus, worm, or other attacker. Even when using a trusted computing base (TCB), the user may have to rely on untrusted computers.  This talk will present an approach for ensuring the integrity and authenticity of messages sent through an untrusted terminal by a user to a remote trusted computing base and vice versa. The approach is both secure and easy to use, leveraging on the difficulty computers have in addressing some artificial intelligence problems. Because of the easiness that user can solve the same problems the approach requires no complex computation on the part of the user. The talk will describes the general form of the approach, discuss its security and user-friendliness, and describes an example implementation based on rendering a 3-D scene.