Chapter 1
Reinforcement
Problem R-1.12
Compare and contrast symmetric encryption with public-key encryption, including the
strengths and weaknesses of each.
Problem R-1.14
Suppose the author of an online banking software system has programmed in a secret feature
so that program emails him the account information for any account whose balance has just
gone over $10,000. What kind of attack is this and what are some of its risks?
Problem R-1.16
Give an example of the false sense of security that can come from using the “security by
obscurity” approach.
Problem R-1.17
The English language has an information content of about 1.25 bits per character. Thus,
when using the standard 8-bit ASCII encoding, about 6.75 bits per character are redundant.
Compute the probability that a random array of tbytes corresponds to English text.
Solution Since each byte has 8 bits, the total number of t-byte arrays is T=28t=2
8t.
that a random array of tbytes corresponds to English text is given by E/T =2
3
Problem R-1.18
Suppose that a symmetric cryptosystem with 32-bit key length is used to encrypt messages
written in English and encoded in ASCII. Given that keys are short, an attacker is using
a brute-force exhaustive search method to decrypt a ciphertext of tbytes. Estimate the
probability of uniquely recovering the plaintext corresponding to the ciphertext for the
following values of t: 8, 64, and 512.
Solution Brute-force decryption generates 232 candidate plaintexts, one for each possible
Problem R-1.19
Suppose you could use all 128 characters in the ASCII character set in a password. What is
the number of 8-character passwords that could be constructed from such a character set?
How long, on average, would it take an attacker to guess such a password if he could test a
password every nanosecond?
Creativity
Problem C-1.2
Describe an instance of a file that contains evidence of its own integrity and authenticity.
Problem C-1.3
Suppose an Internet service provider (ISP) has a voice over IP (VoIP) telephone system
that it manages and sells. Suppose further that this ISP is deliberately dropping 25% of
the packets used in its competitors VoIP system when those packets are going through this
ISP’s routers. Describe how a user could discover that his ISP is doing this.
4
Problem C-1.5
Suppose that you are a computer virus writer; hence, you know that you need to store a
copy of the code for your virus inside the virus itself. Moreover, suppose you know that a
security administrator is also aware of this fact and will be using it to detect the presence of
your virus in operating systems files, as described in the previous problem. Explain how you
can hide the embedded copy of your virus so that it is difficult for the security administrator
to find it.
Problem C-1.9
Benny is a thief who tried to break into an Automated Teller Machine (ATM) using a
screwdriver, but was only able to break five different keys on the numeric keypad and jam
the card reader, at which point he heard Alice coming, so he hid. Alice walked up, put
in her ATM card, successfully entered her 4-digit PIN, and took some cash. But she was
not able to get her card back, so she drove off to find help. Benny then went back to the
ATM, and started entering numbers to try to discover Alice’s PIN and steal money from her
account. What is the worst-case number of PINs that Benny has to enter before correctly
discovering Alice’s PIN?
Problem C-1.10
As soon as Barack took office, he decided to embrace modern technology by communicating
with cabinet members over the Internet using a device that supports cryptographic proto-
cols. In a first attempt, Barack exchanges with Tim brief text messages, encrypted with
public-key cryptography, to decide the exact amounts of bailout money to give to the largest
10 banks in the country. Let pBand pTbe the public keys of Barack and Tim, respectively.
A message msent by Barack to Tim is transmitted as EpT(m) and the reply rfrom Tim
to Barack is transmitted as EpB(r). The attacker can eavesdrop the communication and
knows the following information:
•Public keys pBand pTand the encryption algorithm, such that there is exactly one
ciphertext for each plaintext.
•The total amount of bailout money authorized by congress is $900B
•The names of the largest 10 banks
•The amount each bank will get is a multiple of $1B
•Messages and replies are terse exchanges of the following form:
Barack: How much to Citibank?
Tim: $144B.
5
Barack: How much to Bank of America?
Tim: $201B.
···
Describe how the attacker can learn the bailout amount for each bank even if he cannot
derive the private keys.
Problem C-1.11
As a result of the above attack, Barack decides to modify the protocol of Exercise C-1.10
for exchanging messages. Describe two simple modifications of the protocol that are not
subject to the above attack. The first one should use random numbers and the second one
should use symmetric encryption.
Problem C-1.12
Barack often sends funny jokes to Hillary. He does not care about confidentiality of these
messages but wants to get credit for the jokes and prevent Bill from claiming authorship of
or modifying them. How can this be achieved using public-key cryptography?
Problem C-1.13
As public-key cryptography is computationally intensive and drains the battery of Barack’s
device, he comes up with an alternative approach. First, he shares a secret key kwith
Hillary but not with Bill. Next, together with a joke x, he sends over the value d=h(k||x),
where his a cryptographic hash function. Does value dprovide assurance to Hillary that
Barack is the author of xand that xwas not modified by Bill? Justify your answer.
Problem C-1.14
Barack periodically comes up with brilliant ideas to stop the financial crisis, provide health
care to every citizen, and save the polar bears. He wants to share these ideas with all the
cabinet members but also get credit for the ideas. Extending the above approach, he shares
a secret key kwith all the cabinet members. Next, he broadcasts each idea zfollowed by
value h(k||z). Does this approach work or can Tim claim that he came up with the ideas
instead of Barack? Justify your answer.
Problem C-1.15
Describe a method that allows a client to authenticate multiple times to a server with the
following requirements:
1. The client and server use constant space for authentication.
2. Every time the client authenticates to the server, a different random value for authen-
tication is used (for example, if you have nauthentication rounds, the client and the
server have to use ndifferent random values—this means that sharing a key initially
and using it for every round of authentication is not a valid solution).
Can you find any vulnerabilities for this protocol?
Problem C-1.16
Consider the following method that establishes a secret session key kfor use by Alice and
Bob. Alice and Bob already share a secret key KAB for a symmetric cryptosystem.
1. Alice sends a random value NAto Bob along with her id, A.
2. Bob sends encrypted message EKAB (NA),N
Bto Alice, where NBis a random value
chosen by Bob.
7
Suppose that the random values and the keys have the same number of bits. Describe a
possible attack for this authentication method.
Can we make the method more secure by lifting the assumption that the random values
and the keys have the same number of bits? Explain.
Solution In the first three steps, the attacker, Eve, observes random values NAand NB
Problem C-1.17
Alice and Bob shared an n-bit secret key some time ago. Now they are no longer sure they
still have the same key. Thus, they use the following method to communicate with each
other over an insecure channel to verify that the key KAheld by Alice is the same as the
key KBheld by Bob. Their goal is to prevent an attacker from learning the secret key.
1. Alice generates a random n-bit value R.
2. Alice computes X=KA⊕R, where ⊕denotes the exclusive-or boolean function, and
sends Xto Bob.
3. Bob computes Y=KB⊕Xand sends Yto Alice.
4. Alice compares Rand Y.IfR=Y, she concludes that KA=KB, that is, she and
Bob have indeed the same secret key.
Show how an attacker eavesdropping the channel can gain possession of the shared secret
key.
Problem C-1.18
Many Internet browsers “lock the lock” on an encrypted web site so long as the digital
certificate offered for this site matches the name for this web server. Explain how this could
lead to a false sense of security in the case of a phishing attack.
Problem C-1.20
Describe a good solution to the problem of having a group of students collaborate on a
software construction project using the directory of one of the group members in such a way
that it would be difficult for nonmembers to discover and would not require the help from
8
a system administrator, assuming that the only access rights the group leader can modify
are those for “everyone.” You may assume that access rights for directories are “read,”
“write,” and “exec,” where “read” means the files and subdirectories in that directory can
be listed, “write” means members of that directory can be inserted, deleted, or renamed,
and “exec” on a directory or subdirectory means the user can change his location to that
directory or subdirectory so long as he specifies its exact name.
Solution Create a directory, foo, in the home directory, which does not have read access
rights for everyone, but has exec rights for everyone. Then put a subdirectory inside foo
Problem C-1.22
Suppose, in a scenario based on a true story, a network computer virus is designed so as
soon as it is copied onto a computer, X, it simply copies itself to six of X’s neighboring
computers, each time using a random file name, so as to evade detection. The virus itself
does no other harm, in that it doesn’t read any other files and it doesn’t delete or modify
any other files either. What harm would be done by such a virus and how would it be
detected?
Solution This problem is based on the true story of the Cornell graduate student, Robert
9