Skip to main content
Department of Information Technology

Cryptography overview

  • Cryptography: science of secret writing
  • Cryptanalysis: science of breaking ciphers
  • Cryptology: both

Cryptography is not enough to get computer security, but it helps to solve some problems. Computer security is necessary for cryptography.

Consider a distributed system:

    A ----------+---------- B
                |
		C

  • Traditional problem: C may intercept, interrupt, modify and fabricate messages between A and B, because it has access to the layer below.
  • Cryptography can help
    • data confidentiality: hide contents of messages
    • data integrity: detect a changed message
    • data origin authentication: verify source and integrity of messages
Data integrity vs data origin authentication: integrity useless without source verification; source verification useless without integrity - so do both.
  • "New" problem: A and B may try to cheat eachother (e.g. e-commerce)
    • replace the "intruder" C by the Trusted Third Party (TTP) C, who can resolve disputes

Cryptographic strength

Strength of crypto not by secret algorithms (security by obscurity), but by strength of algorithm and key. Beware of "snake oil security" (homebrewn "new and better" algorithms)!

  • 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?

Algorithm strengths

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

Modular arithmetic 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?
And the size of "large" decreases with time!

Mechanisms

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

Notation:

  • eK(m) = c : plaintext m encrypted with key K
  • dK(c) = m : ciphertext c decrypted with key K
  • dK(eK(m)) = m

Two variants:

  • Symmetric, shared-key, algorithms
    • same key for encryption and decryption: shared secret
    • new key for each pair of peers
    • typically fast
  • Asymmetric, public-key, algorithms
    • one public key (K+), one private (K-): inverses
    • dK+(eK-(m)) = m, dK-(eK+(m)) = m
    • typically slow

Encryption algorithms typically work on a fixed-size block to encrypt at a time. For larger data, two variants:

  • Block ciphers: split data in larger blocks, use same key for each block
  • Stream ciphers: encrypt bytes (or other small blocks) at a time, key changes (typically depends on previous small block)
  • Symmetric: Classic: DES, modern: AES/Rijndael, Blowfish, IDEA, ...
  • Asymmetric: classic: RSA
    • c = m^e mod n
    • m = c^d mod n
    • e and d inverse keys, encryption and decryption the same operation
  • Other asymmetric: El Gamal, Elliptic curve alg:s, ...
3.2. Hash functions
  • result: hash value = message digest = "checksum"
    • note: "checksum" too general, e.g. CRC checksums which are much weaker than cryptographic checksums

Desired properties of hash functions h:

  • ease of computation
  • compression: h maps arbitrary length input to fix length output n=h(x)
  • pre-image resistance: given y, computationally infeasible to find x s.t. y=h(x) ("one-way")
  • weak collision resistance: given x and h(x), computationally infeasible to find x1 different from x s.t. h(x)=h(x1).
  • strong collision resistance: computationally infeasible to find x and y (different) s.t. h(x)=h(y).

Typical hash function h uses a compression function f which takes a fix-length input:

  • break x in m blocks of fixed length
  • let h0=k (initialization value),
    hi = f(xi || h{i-1}), for i = 1,...,m
    return h(x) = hm

3.2.1. Message Authentication Codes (MAC)

MAC give data origin authentication (verify integrity and source) using a secret cryptographic key.

  • Properties: ease of computation, compression, plus
    • computation resistance: for secret key k and a set of pairs (xi,hk(xi)), computationally infeasible to compute hk(y) for new y
  • Example algorithm, based on MDC h:
    HMAC(x) = h(k||p1||h(k||p2||x))
    where p1, p2 padding making k a full block
  • Real algorithms:
    • SHA-1 (Secure Hash Algorith 1): 512-bit blocks, generate 160-bit hash value.
    • MD4, MD5 (Message Digest). (MD5 used for modern Unix/Linux passwords.)
    • RIPE-MD
3.3. Digital Signatures

MAC do not necessarily tell if A or B sent the message (since A and B share the key). Digital signatures do.

  • A dig.sig. must be unforgeable: impossible for anyone else to make A's signature
  • A dig.sig. must be authentic: B can check that a message m is signed by A, and the signature is "firmly attached" to m.
  • Two parts: signature algorithm, verification algorithm.
  • Signature uses private key known only to signer (plus (hash of) data to sign)
  • Verification uses public key (and signed data)

Examples:

  • El Gamal, DSA:
    • security related to DLP (discrete logarithm problem)
  • RSA signatures (Rivest, Shamir, & Adleman)
    • security related to factorisation
    • s = eKa-(h(m)): encrypt hash value using sender's private key
    • verify: h(m) = dKa+(s): decrypt signature with sender's public key, compare with hash value

Certificates

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 (often pre-installed)
    • X.509: format used e.g. in S/MIME certificates for email, and 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, earlier years' students), collect "trust points". 50 => name in cert, 100 => notary
  • Notarization 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

Key establishment

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).

Updated  2006-09-03 17:39:09 by Björn Victor.