Cryptography overview

• Strength of crypto not by secret algorithms (security by obscurity), but by strength of algorithm and key
• Algorithms analysed and evaluated openly
  • empirically secure, provably secure, unconditionally secure
• Key problems: key management
  • Where are keys generated?
  • How are they generated?
  • Where are keys stored?
  • How are they transported there?
  • Where are keys used?
  • How are they revoked and replaced?

The strength of a cryptographic algorithm is given by the difficulty of breaking it.

Notation:

(a = b) mod m iff a-b = k*m for some integer k

Properties:

(a mod m)+(b mod m) = (a+b mod m)

(a mod m)*(b mod m) = (a*b mod m)

Security of crypto algorithms can often be reduced to these difficulties:

• Given p, a and y=a^x mod p, find x (Discrete Logarithm Problem)

• Given n, find prime factors (factorisation)

For large p and n, these are very difficult - maybe not with quantum computing?

• encryption/decryption
• hash functions (integrity check functions, manipulation detection codes (MDC)...)
• digital signatures

A:s public key can/should be known by all who want.
But how do we know a public key Ka+ really belongs to A (and corresponds to Ka-)?
And what can happen if it doesn't?

• Use digital signature of (identity,key) by someone we trust:
  • principle: cert = eKc-(A,Ka+) where Kc- is the private key of the trusted part

    C certifies that Ka+ belongs to A

    Verify using dKc+(cert)

• How do we know Kc+ belongs to C?
  • use digitally signature by someone we trust...

Two major trust systems:

• Certificate authorities (CA):
  • Hierarchical trust: each CA cert is signed by another, up to a Root CA, which you decide to trust
  • If you trust a Root CA, you trust the whole chain
  • You generate your key pair, send a certificate request to the CA
  • Simple to use, but implicit trust
  • X.509: format used e.g. in S/MIME certificates for email, SSL/TLS certs for e.g. web servers
• PGP style:
  • You decide precisely who you trust to sign keys
  • You decide how much you trust them - how many signatures are needed to trust a key
  • You can decide to trust a key's validity explicitly, but perhaps not to sign others
  • Varying levels of trust; short trust paths
  • Harder to use, but easier to trust?

You should get secure email keys! Two major systems

• S/MIME: most "commercial" email programs (e.g. Thunderbird, Mozilla, Outlook?)
• PGP: most "open source" email programs

S/MIME uses X.509 certificates. Free certs from http://www.thawte.com/email.

• Initially only your email address in the cert
• To get your name in the cert, use "Web of Trust" notaries (e.g. me, Lars-Åke Larzon, last year's students), collect "trust points". 50 => name in cert, 100 => notary
• Certification will be arranged

PGP: use pgp or gpg

• initially no trust
• get signatures from others, assign signing trust to keys from others
• verify identity and key fingerprint (hash value) before signing or assigning signing trust
• key signing can be arranged

IMPORTANT: key management

• protect your private key with a good passphrase (long password) - see e.g. http://www.stack.nl/~galactus/remailers/passphrase-faq.html, http://www.unix-ag.uni-kl.de/~conrad/krypto/passphrase-faq.html
• keep protecting it when installed in your email program: use the "Master Password" (Mozilla/Firefox/Thunderbird) or "Security level" (MSIE).

Shared key ciphers also need to distribute secret key safely.

• Key transport protocol: key generated and distributed by third party
• Key agreement protocols: shared key established without third party
  • Diffie-Hellman:
    • A and B create a shared secret key together:
    • p prime, g primitive root of p
      • primitive root: g^i mod p, for 0<=i<p, generate 0..p-1
      • example: 2 primitive root of 11 (2^10, 2^1, 2^8, 2^2, 2^4, 2^9, ...)
    • A picks random a, sends ya=g^a mod p to B
    • B picks random b, sends yb=g^b mod p to A
    • A computes yb^a, B computes ya^b (both mod p)
    • yb^a = g^(ab) = g^(ba) = ya^b - same, mod p! (this is K)
    • Need authentication: use K (station-to-station protocol)
      • A->B: g^a
      • B->A: g^b, eK(sSb(g^b,g^a)) (Sb: B's signature key, s signature alg.)
      • A->B: eK(sSa(g^a,g^b))
  • Needham-Schroeder
    • uses nonces: random numbers, one-time secrets
    • uses a third party

DH analysis:

• Given p, g, ya, and yb (all public), compute K
• For large enough p, computationally infeasible to solve ya=g^a mod p for a, which is necessary to get K (or symmetrically for yb and b).