Final Review B: Questions
Define the term denial of service attack, with an example.
Ben Bitdiddle reads that the one-time pad is perfectly secure, but he reasons that he can do a more efficient implementation by selecting a random 128-bit key and simply reusing it over and over - that is, we use the same 128-bit key to encrypt each group of 16 characters (16 ⋅ 8 = 128). Now suppose you receive a large body of English text encrypted using Ben's method, but you don't know the key. How might you attempt decode the message?
Suppose Alice and Bob wants to use public-key cryptography so that Alice can send a message to Bob securely. How would they go about it (without reference to a particular public-key algorithm)?
Describe the man-in-the-middle attack, whereby an attacker Eve can actually decrypt any messages sent from Alice to Bob.
In RSA encryption, what do the private key and public key consist of? Knowing the public key, how could one conceivably compute the private key given enough computation power?
In a major blunder, a file containing millions of Adobe passwords was published, and the passwords were encrypted using a symmetric key system. Why would it have been better if Adobe had stored passwords using a cryptographic hash function instead?
In storing passwords, what is “salt,” and how does it help keep the passwords secure?
How does TLS (on which HTTPS is based) address the possibility of a man-in-the-middle attack?
Final Review B: Solutions
In a denial of service attack, attackers essentially disable a system from regular use. This can often be done without explicit access to the system; for example, a Web server can be attacked by simply sending such a volume of spurious requests that the server can barely respond to legitimate requests.
Starting from the first byte, we look at every 16th byte in the encrypted text and see which byte value occurs most often among this selection of bytes. Since in English documents, the space character is by far the most frequent byte, we can safely assume that the most common byte value corresponds to a space, and we can do a bitwise XOR of the most common byte value with the ASCII code for space (0x20) to arrive at what is almost certainly the first byte of the key.
We can repeat the process starting from the second byte to get the second byte of the key, then the third byte, and so on to get all eight bytes of the key. Once we get our safe guesses for all eight bytes, we can then apply the key to the entire message to decrypt it.
First, Bob must generate a matching pair of keys, one designated as the private key and the other as the public key. He announces his public key to Alice, which Alice can then use to encrypt her message. Upon receipt, Bob will decrypt this message using his private key; he will be the only person who will be able to decrypt the message since he is the only person who knows the private key corresponding to the published public key.
Eve determines how she can position herself to intercept all communication between Alice and Bob. Eve generates her own matching pair of keys, one a private key and one a public key. When Bob publishes his public key, Eve intercepts the public key and sends her own public key on to Alice. When Alice sends a message, Eve intercepts the message encrypted with Eve's public key, decodes it using Eve's private key (so that she has intercepted the message). If she wants Bob to know that the message was sent, she uses Bob's public key to encrypts the decoded message and sends that encrypted version on to Bob. Neither Alice nor Bob have any way of detecting that Eve intercepted all communication.
To generate a pair of keys, we first generate two large prime numbers p and q and their product N = p ⋅ q. We find some number s that is relatively prime to (p − 1) ⋅ (q − 1); then we compute a k so that (s ⋅ k) mod ((p − 1) ⋅ (q − 1)) = 1. The public key consists of k and N, whereas the private key consists of s.
Knowing the public key, k and N, if we had enough computing power we could factor N to get its two prime factors p and q. Knowing that, we can compute the value of s so that (s ⋅ k) mod ((p − 1) ⋅ (q − 1)) = 1, which gives us the private key.
If we had a symmetric key system, knowing the encryption key would allow all passwords to be decrypted into their plaintext if the symmetric key were to be acquired; while the encryption key may not be known (and Adobe's key remains unknown), in principle it could be found, and in this case the entire database would open up. However, with a cryptographic hash function, there is no known way to decrypt all passwords at once.
Salt is just a random sequence of characters that is stored in plaintext along with the hash of the result of appending the password onto the hash. This is much more secure than simply storing the hash of the password, since doing the latter makes it far easier to perform a dictionary attack: The attacker can perform a single hash of a frequently-used password and compare it to all hashed values, whereas with a salted system, the attacker must try each individual salt value along with the frequently-used password, slowing the decryption process down considerably.
It relies on certifying authorities (CAs). Browsers are distributed with a relatively short list of CAs and their public keys. Sites generate their public keys and pay a CA to use its private key to generate a certificate of the site's public key. This CA certification process includes a check to make sure the site is who it says it is. Then, when a browser sends a request to the site, the site sends its public key as well as the CA-generated certificate. The browser can use its stored CA public key to authenticate the certificate, which ensures that the browser can be as sure of the site as the CA was during its initial check.
Note that a man-in-the-middle attacker could not uselessfully generate its own private key unless it could get the CA to certify the matching public key as corresponding to the site.