Some students have noticed that it would be silly to specify more than a single significant figure in the numerical answers, since the input values are nothing more than broad estimates. All that really matters is the order of magnitude of the answers.
The computer can try one million (220) 40-bit keys every second, and there are 240 keys to try. Thus it will take (240 keys) / (220 keys/second) = 220 seconds to check them all. A million seconds is approximately 13 days.
It would take the same computer (2128 keys) / (220 keys/second) = 2108 seconds to brute-force check all 128-bit keys. That is about 1025 years.
The age of the universe is estimated to be on the order of 10 billion (1010) years. 1025 years is a trillion lifetimes of the universe, or 15 orders of magnitude.
A computer with a billion processing elements, each capable of trying a billion keys every second, would be 1012 times faster than the computer from the previous problems. Thus, it would take about 1025 / 1012 = 1013 years to crack the key, or about 1000 times the age of the universe.
There are 2128 possible keys. Today, our computer can process approximately (220 keys/second) * (226 seconds/18 month period) = 246 keys per 18 month period. Thus it will take approximately 128 - 46 = 82 eighteen-month doubling periods, or about 130 years, to check all possible keys.
Although a 192-bit or 256-bit key would take longer to break using a key-search attack than a 128-bit key, it's not clear how meaningful this is, since we've already seen that it would take a very long time to crack a 128-bit key by brute force. Although it is possible that an approach other than a keysearch attack will be discovered to crack AES during the next century, it is not known whether the 192-bit or 256-bit versions of AES will be less susceptable to the attack than the 128-bit version. Companies might decide to use the 192-bit or 256-bit version of these ciphers for marketing purposes --- that is, to brag that they have a longer key --- but at the present time it is not clear that these longer keys actually provide more security.
The SHA-1 of the string "Massachusetts Institute of Technology" with a trailing newline character is c29518134a6b47563b1e411b7401a52c081996a4.
% echo "Massachusetts Institute of Technology" | openssl sha1 c29518134a6b47563b1e411b7401a52c081996a4
The SHA-1 of the string without the trailing newline is:
% echo -n "Massachusetts Institute of Technology" | openssl sha1 2e8278757a25601c21d99fe299bebcca68d22c70
Let's be generous. Although there are roughly 10,000 students and 10,000 staff at MIT, many people have more than one computer and there are many computers operating as servers and the like. It seems possible that there could be as many as 100,000 computers at MIT. There are 689,670 files on my laptop running MacOS 10.3. Let's assume that the average computer has 100,000 unique files. Let's also generously assume that every computer has a different set of files. Multiplying the number of computers by the number of files per computer gives us 1010 unique files at MIT.
Assuming a random oracle model for SHA-1, each of these 1010 files has a one in 2160 chance (approximately one in 1048) of having the matching SHA-1. The probability that any of them will have the matching SHA-1 is therefore about 1010 / 1048 = 10-38. That's pretty small, but it's not quite zero! Of course, it's more likely that your computer will fail while calculating all of those hashes than that you will actually find one that's correct...
The link to the Birthday Paradox wasn't actually relevant to this problem; it is just additional background information. If you wanted to calculate the chance that two files at MIT had the same hash, you would need to use the Birthday Paradox concept to get the right answer, which is approximately 1010 * 1010 / 1048 = 10-28.
Some students noticed that there is no guarantee that any string will have the same hash as the given string, so there may be no amount of time that suffices to find a collision with it. While the pigeon hole principle proves that there must be a collision of some two inputs to SHA-1, it doesn't prove that there must be some collision with every input.
Under the random oracle model, however, you would expect that searching long enough would find a collision with any given input. (This is one demonstration of how the random oracle model is not a perfect model for a cryptographic hash function!) In this model, every new input results in a random output, so every new input should have a one in 2160 chance of colliding with our given input. Thus, we would expect to have to test approximately 2160 different inputs before finding a collision with our given input. If you can hash and test a million inputs per second, then this will take about (1048 inputs) / (106 inputs/second) = 1042 seconds, or about 1035 years.
Signing is an authentication technique that is used to prove that neither the message nor its signature was modified after the signature was created. Signing can also be used to establish the identity of the signer. Sealing is a confidentiality technique: it applies a cryptographic transformation to a message so that it is unintelligible to anyone who does not posses the appropriate unsealing key.
I imported the key by downloading it from the key server:
athena% gpg --keyserver pgp.mit.edu --recv-keys E3232682 gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information gpg: /afs/sipb.mit.edu/user/simsong/.gnupg/trustdb.gpg: trustdb created gpg: key E3232682: public key "MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu>" imported gpg: Total number processed: 1 gpg: imported: 1 athena% gpg --list-keys gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information /afs/sipb.mit.edu/user/simsong/.gnupg/pubring.gpg ------------------------------------------------- pub 1024D/E3232682 2004-03-27 MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu> sub 1024g/68853FD5 2004-03-27 [expires: 2004-05-26] athena%
Either the first document was modified or the signature on the first document was modified, as demonstrated by the transcript below:
athena% cp /mit/6.033/www/handouts/handson/gpg-message1.txt.asc . athena% gpg gpg-message1.txt.asc gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information gpg: Signature made Sat Mar 27 17:09:34 2004 EST using DSA key ID E3232682 gpg: BAD signature from "MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu>" athena% cp /mit/6.033/www/handouts/handson/gpg-message2.txt.asc . athena% gpg gpg-message2.txt.asc gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information gpg: Signature made Sat Mar 27 17:09:34 2004 EST using DSA key ID E3232682 gpg: Good signature from "MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu>" gpg: checking the trustdb gpg: no ultimately trusted keys found gpg: WARNING: This key is not certified with a trusted signature! gpg: There is no indication that the signature belongs to the owner. Primary key fingerprint: E8C3 1C3C F9DD 0B40 2E44 02BA 8D1C A881 E323 2682 athena%
A signature contains the result of a function that takes as inputs the message and the signer's private key. PGP signs messages by hashing them and signing the hash.
Note that PGP signatures do not include the SHA-1 hash of the message itself, nor do they include either the signer's private or public key. However, PGP signatures may be created either with or without the Key ID of the signing key. If they are created without the Key ID, then the signature can only be verified by trying every public key in your keychain. This is an expensive process, but it makes it considerably harder for an attacker to tell who signed a file, if that is considered condfidential information. Normally, PGP includes the Key ID in the signature block.
Also normally included are configuration parameters such as the hash algorithm used, the public key algorithm used, and the software version used to create the signature.
The key has three signatures on it. One is a self-signed signature, one is from key 903C9265, and one is from key D1BA664D.
Your problem set author regrets using keys 903C9265 and D1BA664D to sign key E3232682. Key 903C9265 has many signatures on it, but none of these signatures should be trusted by anyone in 6.033. For this reason, key 903C9265 should not be trusted on the basis of the signatures. Nevertheless, key 903C9265 is trustworthy, for two reasons that will be discussed below.
Here are the signatures on the keys:
athena% gpg --list-keys --verbose gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information /afs/sipb.mit.edu/user/simsong/.gnupg/pubring.gpg ------------------------------------------------- pub 1024D/E3232682 2004-03-27 MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu> sig 3 903C9265 2004-03-27 [User id not found] sig 3 D1BA664D 2004-03-27 [User id not found] sig 3 E3232682 2004-03-27 MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu> sub 1024g/68853FD5 2004-03-27 [expires: 2004-05-26] sig E3232682 2004-03-27 MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu> athena%
We can find out the owner of keys 903C9265 and D1BA664D by downloading them from the keyserver:
athena% gpg --keyserver pgp.mit.edu --recv-keys 903C9265 gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information gpg: key 903C9265: public key "Simson L. Garfinkel <simsong@vineyard.net>" imported gpg: Total number processed: 1 gpg: imported: 1 (RSA: 1) athena% gpg --keyserver pgp.mit.edu --recv-keys D1BA664D gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information gpg: key D1BA664D: public key "Simson L. Garfinkel <simsong@acm.org>" imported gpg: Total number processed: 1 gpg: imported: 1 athena%
Now if we run gpg --list-keys --verbose we will see the name of the person who signed the 6.033 keys:
athena% gpg --list-keys --verbose gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information /afs/sipb.mit.edu/user/simsong/.gnupg/pubring.gpg ------------------------------------------------- pub 1024D/E3232682 2004-03-27 MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu> sig 3 903C9265 2004-03-27 Simson L. Garfinkel <simsong@vineyard.net> sig 3 D1BA664D 2004-03-27 Simson L. Garfinkel <simsong@acm.org> sig 3 E3232682 2004-03-27 MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu> sub 1024g/68853FD5 2004-03-27 [expires: 2004-05-26] sig E3232682 2004-03-27 MIT 6.033 - Spring 2004 - Hands on #5 (This key is for hands-on #5) <6.033-tas@mit.edu> pub 1024R/903C9265 1994-07-15 Simson L. Garfinkel <simsong@vineyard.net> sig 903C9265 1997-07-21 Simson L. Garfinkel <simsong@vineyard.net> sig 0B2790DE 1999-10-02 [User id not found] uid simson sig 903C9265 1997-07-12 Simson L. Garfinkel <simsong@vineyard.net> sig 0B2790DE 1999-10-02 [User id not found] uid simsong@mit.edu sig 903C9265 1997-07-12 Simson L. Garfinkel <simsong@vineyard.net> sig 0B2790DE 1999-10-02 [User id not found] uid Simson L. Garfinkel <simsong@acm.org> sig FC0C02D5 1994-11-08 [User id not found] sig 903C9265 1994-11-10 Simson L. Garfinkel <simsong@vineyard.net> sig A28608F5 1999-02-15 [User id not found] sig FE5AF240 1999-03-18 [User id not found] sig 0B2790DE 1999-10-02 [User id not found] pub 1024D/D1BA664D 2003-02-12 Simson L. Garfinkel <simsong@acm.org> sig 3 D1BA664D 2003-02-12 Simson L. Garfinkel <simsong@acm.org> sub 1024g/77816A97 2003-02-12 sig D1BA664D 2003-02-12 Simson L. Garfinkel <simsong@acm.org> athena%
Note that we still don't know if we can trust these keys, because they are not signed by anybody that we trust. However, there are two ways to establish trust in these keys:
Note that it is incorrect to assert that the key is trustworthy because it was downloaded from pgp.mit.edu. The server at pgp.mit.edu is a simple database server. It is not a Certificate Authority (CA) and it does not certify keys, as is made clear by the next question.
The name on the key is "George W. Bush." But you shouldn't trust the key, because the signature on the key is made by a self-signed key that isn't itself trustworthy.
Note that whether or not the key is trustworthy has nothing to do with whether or not the MIT PGP keyserver is trustworthy. The function of the keyserver is to act as a distributed database: it allows anyone to upload any key that they wish. Anyone else can then search for and download that key. Trust in the keys is entirely removed from trust in the keyserver.
athena% gpg --recv-key 53BB7633 gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information gpg: key 53BB7633: public key "George Walker Bush (DOD) <president@whitehouse.gov>" imported gpg: Total number processed: 1 gpg: imported: 1 athena% gpg --list-sigs 53BB7633 gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information pub 1024D/53BB7633 2004-03-04 George Walker Bush (DOD) <president@whitehouse.gov> sig 3 BD670339 2004-04-08 [User id not found] sig 3 53BB7633 2004-03-04 George Walker Bush (DOD) <president@whitehouse.gov> sub 1024g/09756CDC 2004-03-04 [expires: 2009-03-03] sig 53BB7633 2004-03-04 George Walker Bush (DOD) <president@whitehouse.gov> athena% gpg --recv-key BD670339 gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information gpg: key BD670339: public key "Yes, it's really Bush!" imported gpg: Total number processed: 1 gpg: imported: 1 athena% gpg --list-sigs 53BB7633 gpg: WARNING: using insecure memory! gpg: please see http://www.gnupg.org/faq.html for more information pub 1024D/53BB7633 2004-03-04 George Walker Bush (DOD) <president@whitehouse.gov> sig 3 BD670339 2004-04-08 Yes, it's really Bush! sig 3 53BB7633 2004-03-04 George Walker Bush (DOD) <president@whitehouse.gov> sub 1024g/09756CDC 2004-03-04 [expires: 2009-03-03] sig 53BB7633 2004-03-04 George Walker Bush (DOD) <president@whitehouse.gov> athena%