CSCI E-170 Calendar - Fall 2005

Homework #3: Hashing and Crypto Solutions

By Joe Foley

1. Find an English language word which has the MD5 hash of df53ca268240ca76670c8566ee54568a. (2 points)

Answer: computer
There were a couple of ways to do this. The most straightforward was to simply do question 2, but look for that particular hash.

The fastest way to do this was to use the method that Simson mentioned during the lecture: go to your favorite search engine and put the hash string in. The site I found it at via google was: http://mina.naguib.ca/dist/digest/digest-648.txt

2. Find a few an English language words in which the first 3 hexadecimal digits of the word's MD5 hash are equal to the first 3 hexadecimal digits of the word's SHA-1 hash. Your professor found 59 such words in the file web2.txt, as well as 2 words where the first 4 hexadecimal digits of each hash were equal. Show the program that you use to find the matches, and report the matches. (2 points)

Answer: 3 digits
acetylcyanide
Aeacides
aslope
balaniferous
bedown
biophilous
broguish
Cakchikel
cattishness
celibatarian
chilenite
confirm
daffish
diblastula
disabled
Electra
electrode
electrogalvanic
epinine
erugation
foremark
furciferine
Gargantua
genomic
hazelwood
Heliothis
hookheal
imprevision
inthronize
inveiglement
lacerative
lituus
luciferase
macraucheniid
mulloway
nonbacterial
oligolactia
palsied
panic
paten
pedicular
prefamiliarly
prepartake
pretermission
raiser
reapprobation
rehead
screenwriter
Strongyloides
subterraneously
suffixment
teatime
thermostatically
tilefish
trigonocerous
unbar
unreflectingness
urger
vellicative

4 Digits
rehead
trigonocerous

If you got different words, it's most likely because you forgot to strip the newline character, commonly represented as "\n" at the end of each line. The perl program used to generate the matches is e170-hw3-prob2.pl.

3. Assuming that hash residues are randomly and evenly distributed, what is the odds that the first four hexadecimal digits for two hash residues will be the same? Do the odds match the findings in problem #2? (2 points)

Answer: 16^-4 = 1/65536 = approx 0.0000152 = 0.00152% The chances of a match on any given digit will be 1 in 16 (0123456789ABCDEF). Since these are independant probabilities, we simply multiply them together. There are 234937 words in the file, which means at that we should get 3.58 words that match and since we get 2, that's about right, maybe a little low.

4. Obtain a free personal email certificate from Thawte, install it on your mail client, and send a digitally signed message to the course staff. The subject line of the message should say 'signed message from ljuser' where ljuser is your LiveJournal username. (2 points)

Answer: Follow the directions and send us email.
There were some complications if you were not using one of the email readers that Thawte recommended. If you ran into this complication, the easist thing to do was get the certificate via firefox/mozilla, then export it to a pkcs12 certificate format using the "Backup" option.

5. Using OpenSSL, report and explain each of the fields that are in your Thawte certificate. (2 points)

The usual invocation starting with a pkcs12 cert to do this was:

  openssl pkcs12 -in file.p12 -clcerts -out mycert.pem
  openssl x509 -text -in mycert.pem

You'd get something like this:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 1029973 (0xfb755)
        Signature Algorithm: md5WithRSAEncryption
        Issuer: C=ZA, O=Thawte Consulting (Pty) Ltd., CN=Thawte Personal Freemail Issuing CA
        Validity
            Not Before: Oct 21 16:47:41 2005 GMT
            Not After : Oct 21 16:47:41 2006 GMT
        Subject: CN=Thawte Freemail Member/emailAddress=foley@mit.edu
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (2048 bit)
                Modulus (2048 bit):
                    00:f7:ef:a2:19:1d:72:b8:3e:99:6b:b0:d4:63:aa:
                    53:64:f1:fa:cc:10:e6:11:ac:cf:1d:e6:fd:08:ef:
                    db:65:44:7f:7b:1d:62:53:82:6f:96:d9:d3:b3:c6:
                    58:cc:23:53:a0:f9:d2:c6:66:d3:92:2e:49:76:6c:
                    85:6f:a4:d0:fc:ac:99:48:c7:71:61:07:e9:1f:71:
                    2f:18:ea:c5:7c:36:60:b7:b4:1e:04:4d:d4:7d:01:
                    64:67:56:07:99:92:7f:2d:3a:8c:27:18:07:2f:9f:
                    f0:30:7c:8d:2d:3d:6d:15:ec:fc:6b:1b:ee:0c:09:
                    f9:fc:3c:6b:6b:4f:f2:d8:66:0c:f5:6c:91:22:d9:
                    dc:00:e6:61:e0:ca:17:bd:1e:54:90:4c:25:1c:14:
                    18:ab:d2:ea:73:93:0b:94:81:3e:98:77:93:80:0f:
                    1e:0c:8f:39:d9:ec:29:8a:f3:66:01:2e:4c:1f:9d:
                    b2:89:88:9e:ca:d3:f7:a2:2b:46:b1:60:bc:4c:f2:
                    6e:18:04:bc:18:ae:ed:4b:28:d3:f7:79:71:3d:0c:
                    78:50:cc:1d:d2:8b:91:64:78:44:3f:52:be:a0:34:
                    fc:d0:e4:da:fd:4a:a3:65:ea:e6:de:d5:8c:84:f9:
                    13:ba:4c:c5:2b:b0:b0:b0:9c:82:39:cb:d1:13:2b:
                    c1:97
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            X509v3 Key Usage: critical
                Digital Signature, Non Repudiation, Key Encipherment, Data Encipherment, Key Agreement
            Netscape Cert Type: 
                SSL Client, S/MIME
            X509v3 Subject Alternative Name: 
                email:foley@mit.edu
            X509v3 Basic Constraints: critical
                CA:FALSE
    Signature Algorithm: md5WithRSAEncryption
        4a:17:9b:ba:fd:67:f6:02:7a:a4:10:f8:08:26:a1:7e:68:b6:
        a4:05:69:10:cb:be:9a:da:52:b7:55:b2:b4:05:75:a6:f5:13:
        05:9b:03:b6:53:87:2e:58:3d:66:cd:a0:9b:ab:79:10:8c:97:
        14:b3:8c:66:89:2e:71:ae:49:68:57:7d:c5:86:e2:24:ee:7c:
        f2:70:6f:26:f9:33:00:b7:8c:a6:74:df:02:16:60:c1:56:c2:
        98:6a:14:aa:bf:01:85:25:28:21:da:54:50:cc:62:c5:27:58:
        c9:ad:4c:24:94:8a:76:4b:e3:1c:bc:fa:d6:b5:9d:8c:20:95:
        24:90
-----BEGIN CERTIFICATE-----
MIIC6jCCAlOgAwIBAgIDD7dVMA0GCSqGSIb3DQEBBAUAMGIxCzAJBgNVBAYTAlpB
MSUwIwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQD
EyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgSXNzdWluZyBDQTAeFw0wNTEwMjEx
NjQ3NDFaFw0wNjEwMjExNjQ3NDFaMD8xHzAdBgNVBAMTFlRoYXd0ZSBGcmVlbWFp
bCBNZW1iZXIxHDAaBgkqhkiG9w0BCQEWDWZvbGV5QG1pdC5lZHUwggEiMA0GCSqG
SIb3DQEBAQUAA4IBDwAwggEKAoIBAQD376IZHXK4PplrsNRjqlNk8frMEOYRrM8d
5v0I79tlRH97HWJTgm+W2dOzxljMI1Og+dLGZtOSLkl2bIVvpND8rJlIx3FhB+kf
cS8Y6sV8NmC3tB4ETdR9AWRnVgeZkn8tOownGAcvn/AwfI0tPW0V7PxrG+4MCfn8
PGtrT/LYZgz1bJEi2dwA5mHgyhe9HlSQTCUcFBir0upzkwuUgT6Yd5OADx4MjznZ
7CmK82YBLkwfnbKJiJ7K0/eiK0axYLxM8m4YBLwYru1LKNP3eXE9DHhQzB3Si5Fk
eEQ/Ur6gNPzQ5Nr9SqNl6ube1YyE+RO6TMUrsLCwnII5y9ETK8GXAgMBAAGjTTBL
MA4GA1UdDwEB/wQEAwID+DARBglghkgBhvhCAQEEBAMCBaAwGAYDVR0RBBEwD4EN
Zm9sZXlAbWl0LmVkdTAMBgNVHRMBAf8EAjAAMA0GCSqGSIb3DQEBBAUAA4GBAEoX
m7r9Z/YCeqQQ+AgmoX5otqQFaRDLvpraUrdVsrQFdab1EwWbA7ZThy5YPWbNoJur
eRCMlxSzjGaJLnGuSWhXfcWG4iTufPJwbyb5MwC3jKZ03wIWYMFWwphqFKq/AYUl
KCHaVFDMYsUnWMmtTCSUinZL4xy8+ta1nYwglSSQ
-----END CERTIFICATE-----

The various fields:

Version: What version of X.509 certificate. The current rev is 3.
Serial Number: Each issuer gives a unique SN for each certificate.
Signature Algorithm: How the signature was generated. Mine was made with an md5 hash and RSA Encryption.
Issuer: Who issued the certificate
- C: Country. ZA is South Africa
- O: Organization: Thawte
- CN: Common Name: A description
Validity: Describes the period that the certificate is valid for
Subject: Me! (or at least who the certificate is for)
- CN: Common name: Description including my email address
Subject Public Key Info: Info about the key that the certificate is associated with.
- Public Key Algorithm: My key is an RSA key
- RSA Public Key Modulus and Exponent: The Modulus:pqand Exponent:n of my public key.
X509v3 extensions: Stuff that was added after the main V2 standard
- X509v3 Key Usage: This field is a critical one, that can be used for Signature, Non-repudiation, Encrypting Keys or Data, or making Agreements
- Netscape Cert Type: Says how the cert can be used by Netscape
- X509v3 Subject Alternative Name: A shorter name to use
- X509v3 Basic Constraints: This field is a critical one, indicating whether or not it can be used as a CA signer.
- Signature Algorithm: Repeat of before, how the certificate was signed/generated. The actual hex code for the signature follows.
BEGIN CERTIFICATE: Here is the actual ASCII-armored/Base64 certificate.

6. Using OpenSSL, connect to two different SSL servers. Report and explain each of the fields in the server's certificates. Are any of the fields in error? Why or why not? (2 points)

Answer: Do what you did on problem 5, but now on a server's certificate.

Easiest way to get a certificate description was to:

  openssl s_client -host hostname -port 443 > myserver.txt
  openssl x509 -in myserver.txt -text

As an example, when I ran that on ems.mit.edu, I got:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number: 1540 (0x604)
        Signature Algorithm: sha1WithRSAEncryption
        Issuer: C=US, ST=Massachusetts, O=Massachusetts Institute of Technology, OU=MIT Certification Authority
        Validity
            Not Before: Oct 13 16:00:00 2005 GMT
            Not After : Oct 12 16:00:00 2006 GMT
        Subject: C=US, ST=Massachusetts, L=Cambridge, O=Massachusetts Institute of Technology, OU=Emergency Medical Services, CN=ems.mit.edu/emailAddress=ems-webmaster@mit.edu
        Subject Public Key Info:
            Public Key Algorithm: rsaEncryption
            RSA Public Key: (1024 bit)
                Modulus (1024 bit):
                    00:c3:96:9a:c1:8d:15:60:41:9c:b7:6c:f0:2a:6b:
                    da:4c:f9:b4:bd:c6:05:ec:34:84:79:2a:e6:fa:eb:
                    af:d7:ab:08:2a:f6:33:d8:fa:ef:02:7b:3d:d2:c6:
                    1e:f6:8e:11:68:57:e1:a5:d9:71:e0:f1:ce:c3:00:
                    b3:46:f3:ed:e5:56:bd:b6:be:58:57:c9:2c:60:45:
                    ac:19:65:5b:1a:e1:cf:94:a2:f5:2a:54:36:30:19:
                    33:0c:f7:a8:5e:ef:6b:b7:b8:22:86:10:0a:f7:a1:
                    f5:c3:08:38:c8:bf:52:e7:1b:90:2f:52:88:42:8f:
                    7d:f7:7b:8d:c7:6a:fe:d3:2d
                Exponent: 65537 (0x10001)
        X509v3 extensions:
            X509v3 Basic Constraints: 
                CA:FALSE
            Netscape Cert Type: 
                SSL Server
            X509v3 Extended Key Usage: 
                TLS Web Server Authentication
            X509v3 Key Usage: 
                Digital Signature, Non Repudiation, Key Encipherment
            X509v3 Subject Key Identifier: 
                90:72:A4:9F:9C:2E:4B:3C:1A:B0:46:1D:BF:44:10:7A:96:15:61:A6
    Signature Algorithm: sha1WithRSAEncryption
        34:d9:29:9c:e7:41:88:fa:ca:08:6a:4c:70:1c:02:ef:28:0f:
        97:44:0e:d6:de:f8:1d:e5:a1:ce:8d:7c:77:2c:ce:b5:db:cd:
        79:8f:9f:d9:f4:ed:92:6f:ae:dd:3f:48:df:b8:39:6a:43:4c:
        f9:52:52:ca:cf:9c:d0:69:49:d3:d1:d2:07:f5:33:0a:f3:96:
        6f:ed:82:c2:81:bc:1f:7f:cb:0f:3d:35:2b:bd:0f:b1:1b:c9:
        b0:c5:9f:50:c3:b8:78:71:2e:1b:64:61:31:29:fc:80:3f:9c:
        ae:29:41:74:e8:fb:86:19:ca:b4:08:a3:4e:62:2f:af:16:cd:
        ae:ef
-----BEGIN CERTIFICATE-----
MIIDHjCCAoegAwIBAgICBgQwDQYJKoZIhvcNAQEFBQAwezELMAkGA1UEBhMCVVMx
FjAUBgNVBAgTDU1hc3NhY2h1c2V0dHMxLjAsBgNVBAoTJU1hc3NhY2h1c2V0dHMg
SW5zdGl0dXRlIG9mIFRlY2hub2xvZ3kxJDAiBgNVBAsTG01JVCBDZXJ0aWZpY2F0
aW9uIEF1dGhvcml0eTAeFw0wNTEwMTMxNjAwMDBaFw0wNjEwMTIxNjAwMDBaMIHK
MQswCQYDVQQGEwJVUzEWMBQGA1UECBMNTWFzc2FjaHVzZXR0czESMBAGA1UEBxMJ
Q2FtYnJpZGdlMS4wLAYDVQQKEyVNYXNzYWNodXNldHRzIEluc3RpdHV0ZSBvZiBU
ZWNobm9sb2d5MSMwIQYDVQQLExpFbWVyZ2VuY3kgTWVkaWNhbCBTZXJ2aWNlczEU
MBIGA1UEAxMLZW1zLm1pdC5lZHUxJDAiBgkqhkiG9w0BCQETFWVtcy13ZWJtYXN0
ZXJAbWl0LmVkdTCBnzANBgkqhkiG9w0BAQEFAAOBjQAwgYkCgYEAw5aawY0VYEGc
t2zwKmvaTPm0vcYF7DSEeSrm+uuv16sIKvYz2PrvAns90sYe9o4RaFfhpdlx4PHO
wwCzRvPt5Va9tr5YV8ksYEWsGWVbGuHPlKL1KlQ2MBkzDPeoXu9rt7gihhAK96H1
wwg4yL9S5xuQL1KIQo9993uNx2r+0y0CAwEAAaNhMF8wCQYDVR0TBAIwADARBglg
hkgBhvhCAQEEBAMCBkAwEwYDVR0lBAwwCgYIKwYBBQUHAwEwCwYDVR0PBAQDAgXg
MB0GA1UdDgQWBBSQcqSfnC5LPBqwRh2/RBB6lhVhpjANBgkqhkiG9w0BAQUFAAOB
gQA02Smc50GI+soIakxwHALvKA+XRA7W3vgd5aHOjXx3LM612815j5/Z9O2Sb67d
P0jfuDlqQ0z5UlLKz5zQaUnT0dIH9TMK85Zv7YLCgbwff8sPPTUrvQ+xG8mwxZ9Q
w7h4cS4bZGExKfyAP5yuKUF06PuGGcq0CKNOYi+vFs2u7w==
-----END CERTIFICATE-----

The only new/interesting fields to really check out are the Issuer and the Subject.

Issuer: C=US, ST=Massachusetts, O=Massachusetts Institute of Technology, OU=MIT Certification Authority

Country: US
State: Masssachusetts
O: Organization: MIT
OU: Organizational Unit: MIT CA

Subject: C=US, ST=Massachusetts, L=Cambridge, O=Massachusetts Institute of Technology, OU=Emergency Medical Services, CN=ems.mit.edu/emailAddress=ems-webmaster@mit.edu

C: Country: US
ST: State: Massachusetts
O: Organization: MIT
OU: Organizational Unit: EMS
CN: Common name: Blob of hostname and the contact email address

The most common mistakes you will find with most SSL server certificates is that they left the fields blank, or put strange information in some of the fields. A somewhat common error is to not put the hostname in the CN.