An overview of Cryptography

Created by Aymeric Barthe

September 10th, 2014

What is covered

  • Cryptographic Hashes
  • Symmetric Ciphers
  • Random Number Generators (CSPRNG)

 

What is not covered

  • Public/Private Key Cryptography
  • Digital Signature Algorithm (DSA)
  • Diffie Hellman
  • TLS/SSL
  • Maths…

Part I

Cryptographic Hash Functions

Cryptographic Hash Functions Properties

  • It's a hash function
    • A function: data of any size => N bits
    • Deterministic
    • Uniformity
  • It's cryptographically secure
    • One way function, trapdoor function
    • Collision resistance
    • Pre-image resistance
    • Second pre-image resistance
  • Avalanche effect
  • Optimized for speed

Usage of Hash functions

  • Message Authentications (MAC, HMAC)
  • Password storage and verification
  • Password-Based Key Derivation
  • Authentication with shared secret (OAuth, HMAC)
  • Random Number Generators (CSPRNG)
  • Proof of work (Bitcoin)

Common hash functions

Name Year Size (bits) Author Comments
MD5 1992 128 Ron Rivest Broken
SHA1 1995 160 NSA Avoid
SHA2
SHA‑224, SHA‑256, SHA‑384, SHA‑512
2001 up to 512
224, 256, 384, 512
NSA Use
SHA3 (Keccak)
SHA3‑224, SHA3‑256, SHA3‑384, SHA3‑512, custom
Now… up to 512
224, 256, 384, 512, custom
Academics (NIST competition) Almost ready
RIPEMD 1996 up to 320
129, 160, 256, 320
Academics Bitcoin
Whirlpool 2000 512 Academics (NESSIE competition) AES team

Hash Function Design

  • Block functions (input data sliced into blocks and padded)
  • The total hash is computed by chaining blocks
  • Multiple rounds
  • Merkle–Damgård construction
    • All hashes except SHA-3 (sponge functions)
    • Apply linear transformations (byte shifts, additions, etc...)
    • Apply non-linear transformation
    • If non linear transformation is collision resistant then the whole hash function is also collision resistant
    • Drawback: length extension

SHA1

SHA1

A, B, C, D and E are 32-bit words of the state F is a nonlinear function that varies; left shiftn denotes a left bit rotation by n places; n varies for each operation; Wt is the expanded message word of round t; Kt is the round constant of round t; Addition denotes addition modulo 232.

Attacks

Birthday Attack

  • Birthday Paradox
    • Probability of birthday on given day 1/366
    • Probability of two people having the same birthday?
      • 50% with 23 people
      • 97% with 50 people
      • 99.99997% with 100 people
  • Birthday Attack
    • Meed in the Middle (MITM)
    • N bits. 2N hashes. But only 2N/2 random hash until collision chance is 50%
    • Attack: pre-compute 2N/2 hashes of fraudulent message, wait for collision, replace message.
    • That's why hash size is double the key size in bits (AES-SHA2)

Other Attacks

  • Pseudo oauth scheme example:
    • HTTP API protected by shared secret
    • sig computed with SHA1(secret || str_parameters)
    • http://example.com/image/2500?action=show&gps=yes&sig=8b08c466e38ba98e8fb7972a49a8294ac2e472d9
    • if computed_hash == received_hash { … }

  • Problems
    • Length extension attack
    • Replay attack
      • Use a nonce or timestamp
    • Side channel attack (timing response)
      • Use constant time comparison
    • Use a better hash function (SHA2)

Other Attacks

  • Storing password into a database
    • Why? Password re-use, legislations
    • Hash = SHA256(password)

  • Attacks
    • Rainbow tables
    • Hash functions are optimized for speed!

  • Same techniques for key derivation password => key

Part 2

Symmetric Ciphers

Types of Ciphers

  • Cipher: plaintext => ciphertext
  • Kerckhoffs's principle
  • Types of Ciphers
    • Historical (substitution / transposition)
    • Modern
      • One Time Pads (XOR)
      • Public/Private key (RSA, ECC)
      • Symmetric Ciphers
        • Stream Ciphers
          • Block Ciphers

    Block Cipher Design

    • Operate on blocks: K-bits => K-bits
      • Block size and key size can be different

    • Sequence of reversible operations
      • Rounds, key schedule, sub keys
      • Linear operations: byte shifts, XOR, …
      • Non linear: s-boxes
        • Resist differential cryptanalysis (NSA, IBM)

    DES

    DES
    • Uses a Feistel structure
      • Two halves swapped and XORed
      • Decryption and Encryption very similar
    • The F function mixes plaintext with key and use s-box
    • DES Feistel

    Common Ciphers

    Name Year Key Size Block Size Author Comments
    DES (Lucifer) 1977 56 64 IBM, NSA Broken
    3DES 1998 168 64 ANSI? Slow, Avoid
    AES (Rijndael) 1998 128, 192 or 256 128 Academics Ok
    Blowfish 1993 32–448 64 Schneier Avoid
    Twofish 1998 128, 192 or 256 128 Schneier Ok
    Serpent 1998 128, 192 or 256 128 Anderson Ok

    Cipher Usage

    • Slice plaintext into blocks
    • Padding (last block)
      • PKCS #7 / RFC 5652
    • ECB mode
      • Disastrous
      • Same plaintext in block => same ciphertext
      ECB

    Modes of Operation

    • CBC mode
      • Chain outputs with XOR.
      • Use IV at start
    • OFB mode
      • Keystream from cipher (IV, XOR)
      • Plaintext XOR Keystream => Ciphertext
      • Cycles!
    • CTR mode
      • Keystream from nonce + counter

    CBC

    CBC Encryption CBC Encryption

    OFB

    OFB Encryption OFB Encryption

    CTR

    CTR Encryption CTR Encryption

    Attacks

    • Practical vs Theoretical
    • Ciphertext only
    • Known plaintext
      • Enigma, file formats
    • Chosen plaintext
      • Differential Cryptanalysis
    • Chosen ciphertext
    • Birthday Attack / MITM
    • Side channel attacks
      • Timing, power, etc…

    Padding Oracle Attack

    • Theoretical. Vaudenay's attack 2002.
    • Practical
    • Attack
      • Chosen ciphertext, man in the middle and side channel
      • Ciphertext sent to server using CBC and padding
      • Attacker modifies cipher text and cause padding errors
        • the Oracle
      • All blocks except the first one can be decrypted with block_size*128 tries per block on average

    Defeat Padding Oracle Attack

    • Mitigation measures (rate limiting…)
    • Stream ciphers, CTR mode, … are safe against this attack. But different attacks against non authenticated decryption exist.
    • Encrypt then MAC (EtM)
      • Beware of the Cryptographic Doom Principle
        • NOT: MAC and Encrypt (SSH)
        • NOT: MAC then Encrypt (SSL/TLS)
      • Caveats: slow, not on-line, two keys
    • Authenticated Encryption
      • Special modes of operation
      • Strong encryption AND authentication
      • One key

    Authenticated Encryption Modes

    • OCB: Offset Codebook Mode
      • Good: Easy to implement, fast, online
      • Bad: Patent, dropped from WPA2
    • CCM: Counter Mode with CBC MAC
      • Good: Easy to implement, no patents
      • Terrible hack to replace OCB for WPA2.
      • Bad: fixed 128 size, two-pass, offline, AES only.
    • EAX
      • Good: Easy to implement, no patents, online
      • Bad: two-pass (slow)
      • EAX(Prime) is totally broken
    • GCM: Galois Counter Mode
      • Good: No patents, online, fast
      • Bad: Hard to implement
    • How to choose an Authenticated Encryption mode

    Part III

    Cryptographically Secure Pseudo Random Number Generators

    CSPRNG

    • Generator
    • Pseudo Random
      • Computers are deterministic (mostly…)
      • Uniform Distribution
      • Seed / Large period
    • Cryptographically Secure
      • Next-bit test
      • Withstand state compromise extensions

    CSPRNG Usage

    • Key Generation
      • Session keys (SSL/TLS)
      • Keys encrypted with passwords
    • Salts, Initialization Vectors (IVs)
    • Nonces
    • One Time Pads (OTP)
    • Digital Signature Algorithm (DSA)

    CSPRNG implementation techniques

    • Entropy Pool
      • I/O timings (Disk, Network, …)
      • Timers and counters (CPU, OS, …)
      • OS State (Process ID, Thread ID, …)
      • RDRAND CPU instruction
    • Seeding the pool
      • Reverse Biased Diodes (dongles, /dev/hwrng)
      • Analog Noise (Camera, Microphone, …)
    • Cryptographic Primitive
      • Entropy seeds PRNG using hash functions or ciphers

    CSPRNG implementations

    • Windows
      • CryptGenRandom / RtlGenRandom
      • Not public
      • SHA-1 FIPS 186-2
    • Unix
      • /dev/random and /dev/urandom
      • OS X, iOS, FreeBSD uses Yarrow with 3DES in CTR mode
        • Bruce Schneier, Niels Fergusson
    • OpenSSL
      • Based on underlying CSPRGN + additionaly entropy Windows (heap walk…)
      • Exposed on Android with SecureRandom API

    CSPRNG caveats

    • Kernel Space vs User Space
    • Entropy starvation
    • Lack of entropy leads to bad crypto
    • Hardware Random Number generators for high entropy needs.

    FIN