Crypto 101: An Overview

This is an overview of “modern” (post-WW2) cryptography covering some properties and cryptographic primitives. Definitions and proofs omitted.

  1. Properties
    1. Confidentiality – Unauthorized can’t read message.
    2. Integrity – Message not changed by unauthorized.
    3. Authentication – Message from authorized.
  2. Primitives
    1. Symmetric key ciphers and public key cryptosystems
      1. Block (AES) and stream (RC4)
      2. RSA and ElGamal
    2. Hashes
      1. SHA-256
    3. MACs (symmetric key) and Digital Signatures (public key)
      1. HMAC
      2. RSA and DSA

Kerckhoffsprinciple: Always assume everything about a cryptosystem is publicly known except for the key. In other the encryption and decryption algorithms should be public. This means e.g a ciphertext-only attacker is able to try out different keys for decryption, since he knows the encryption and decryption algorithms but not the key.

Confidentiality is provided by symmetric key ciphers and public key cryptosystems. Without the shared symmetric key or private key an adversary cannot gain information about the plaintext.

  • IND-CPA and IND-CCA.
    • IND-CCA -> IND-CPA.

Integrity is provided by a hash. Actually this is not really true because a man in the middle can easily change the message and generate a new hash for it. But if the hash is transmitted through a secure channel then if the message gives the same hash then the message is unchanged.

  • Collision resistance, 2nd preimage resistance, and preimage resistance.
    • Collision resistance -> 2nd preimage resistance.
    • 2nd preimage resistance -/> preimage resistance.
    • Preimage resistance -/> 2nd preimage resistance.

Authentication is provided by a message authentication code (symmetric key) or a digital signature (public key). These also ensure integrity (and a digital signature additionally provides non-repudiability since only one person possesses the secret signing key). Without the shared symmetric key or secret signing key an attacker cannot produce a valid MAC for the shared symmetric key or a valid digital signature for the public verification key.

Symmetric and public key cryptosystems:

  • Encryption alone does not provide integrity.
  • Symmetric key: Block and stream ciphers
    • Block ciphers (e.g AES)
      • ECB – Deterministic. Not IND-CPA secure. Both parallel.
      • CBC – Encryption sequential, decryption parallel. Bit error affects 2 blocks.
      • CFB – Encryption sequential, decryption parallel. Bit error affects 2 blocks. Only uses encryptor. Self-synchronizing stream cipher.
      • OFB – Both sequential. Keystream precomputable. Bit error affects only 1 bit. Only uses encryptor. Synchronous stream cipher.
      • CTR – Both parallel. Bit error affects only 1 bit. Only uses encryptor. Synchronous stream cipher.
    • Stream ciphers (e.g RC4)
      • Use a generated keystream to XOR the message.
  • Public key: RSA and ElGamal
    • Textbook RSA
      • Deterministic: not IND-CPA secure.
    • RSA-OAEP
      • IND-CCA secure under RSA assumption in random oracle model.
    • ElGamal
      • IND-CPA secure under DDH assumption.
      • Malleable: not IND-CCA secure.

MACs and digital signatures:

  • MACs: HMAC
  • Digital signatures: RSA and DSA
    • Textbook RSA
      • Not EUF-CMA secure. Selective forgery under CMA. Existential forgery under key-only attack.
    • RSA-FDH
      • EUF-CMA in random oracle model.
    • DSA / EC-DSA
      • Believed to be EUF-CMA, however not proven.
      • Broken if the discrete log can be calculated.

To add confidentiality to a message, you encrypt it. Since public key crypto is slower than symmetric key (by thousands of times) what people normally do is to encrypt a message using the symmetric key and then encrypt that key using public key encryption. This is called hybrid encryption and is used by practically all existing public key implementations, such as TLS.

To add integrity and authentication to a message, you add a digital signature. You could also hash the message and sign the hash instead of the entire message. In fact that is the way it is normally done.

If you want both confidentiality and integrity+authentication, you first encrypt and then you hash the ciphertext and sign the hash.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s