Crypto fundamentals

Basics

One-Time Pad

  • Start with random sequence of letters
  • Write message without spaces and punctuation
  • Add numbers mod 26

  • Unbreakable if truly random

  • Different keys may give different resulting messages

Entropy

  • Toss of coin generates 1 bit of entropy
  • Toss coing 8 times -> 8 bits of entropy -> 8 bits of storage to record outcome
  • Using OTP in takes log2(26) = 4.7 bits of information to record one letter
  • In OTP with 1000 letters we get 4700 bits of entropy
  • If truly random and only used once we get maximun entropy
  • Entropy does not increase witout adding more randomness

Engima

  • Much weaker then OTP (though still hard to break!)
  • Used interconnecting rotors applied in order
  • Rotors rotated with each keystroke (central rotor stepped twice to prevent consecutive patterns)
  • Also used a plug board to be able to swap letters in a fourth mapping
  • Same machine could be used to encrypt and decrypt but this prevented an output letter from ever being the same as the input

Cryptanalysis

  • One mapping represents multiple different offsets

  • Entropy of 26 letters in OTP: 4.7*26 = 122.2

  • Entropy of 26 letters in Enigma rotor: 4.7 bits (internal wiring is constant)

  • Usage of reflector for decryption reduces entropy from log(26) to log(25) = 4.6 bits

  • Usage of double stepping central rotor also decreased entropy from 262626=17576 to 262526=16900

  • Same initial rotor settings used for a full day
  • No repeated initial rotor settings in a month
  • Key was encrypted twice in message and prepended (generated pattern)
  • Same message sent twice with different encryption (play cipher texts agains each other)
  • Plugboard configuration did not change during day so it was possible to combine intercepts to guess configuration

Diffie-Hellman key exchange

  • Whitfield Diffie and Martin Hellman (assisted by Raplh Merkle)
  • Key agreement and generation can be done over an untrusted channel

  • 2048 bit is smallest prime considered secure (616 digits)

  • Number of water molecules on earth (46 digits)

  • Very vulnerable to MitM since a MitM can send different values to Alice and Bob

Summary

  • Entropy is critical
  • Scrambling does not increase entropy
  • OTP can be proven secure but are hard to use
  • Patterns can be exploited
  • Weakest link is the human operator

Algorithms

  • Comes in 3 flavours to create a crypto system
    • Symmetric – Encrypts and decrypts
    • Asymmetric – Encrypts and decrypts
    • Hash Functions – Verifies authenticity
  • Relationship between key and ciphertext is called Confusion
    • Small change in key -> large change in ciphertext
    • XOR not sufficient; one-to-one
    • Key schedule gives us a large change
  • Relationship between message and ciphertext is called Diffusion
    • Diffuse the information so that small change in message -> large change in ciphertext
    • Hides patterns within message

Symmetric

  • Uses same key to encrypt and decrypt

Block ciphers

  • Block ciphers used to make it possible to use shorter key then message
  • Typical block size is 16 bytes
  • Operates in rounds where part of key (Round Key) is applied on block with some other operations
  • After some number of rounds, we end up with cipher text
Round Key
  • Derived from key using a key schedule
  • Key Schedule is an algorithm that can Shift, XOR, Multiply and perform other operations on original key
Electronic Code Book (ECB)
  • Encrypt blocks induvidually
  • Easy to crack since we get a lot of patterns and repeated information
Cipher Block Chaining (CBC)
  • XOR’s next adjacent block with previous block
  • First block is XOR’d with an Initialization Vector (IV) same size as block
  • Diffuses information
  • Makes it possible to encrypt message of arbitrary length when having fixed length key

Data Encryption Standard (DES)

  • Key length 64 bits using 8 bits for parity check -> 56 bit key
  • Has theoritical issues but key length is also much to short
  • Used in 3DES where DES runs 3 times with 3 different keys -> key length 168 bits

Advanced Encryption Standard

  • Uses Rijndael as encryption algorithm
  • 128, 192 or 256 bit keys
  • Block size 16 bytes organize din 4×4 matrix

Rounds

  1. Uses key expansion to confuse the key and create a round key
    • Shift orignal key then;
    • XOR then;
    • Multiply
  2. XOR block with Round Key
  3. Substitution using S-Box
    • Essentially a lookup table with 256 entries where each byte is substituted
  4. Shift rows
    • Move top to bottom
  5. Mix columns to further confuse the key
    • Rotate the bytes in each row with a different number
    • First row is not rotated
    • Second row with one byte
    • Third row with two bytes
    • Fourth row with three bytes

Cryptanalysis – Why is Enigma weaker then AES?

  • Engima

    • 47.1 bits in plugboard
    • 14.1 bits in rotors
    • Total: 61.2 bits
    • No memory -> No diffusion
    • Predictable key exchanges -> little confusion
  • DES

    • 56 bits of entropy
    • CBC and IV -> Good diffusion
    • Rounds -> Good confusion
  • AES

    • 128-256 bits of entropy
    • CBC and IV -> Good diffusion
    • Rounds -> Good confusion

Compression

  • English text has about 0.6 – 1.3 bits of information per character
  • Compressed ASCII can be compressed to about 40% (although theoretical limit is 7.5 to 16%!)
  • Squeezes out redundancy and preserves information

Encryption vs Compression

  • Encryption masks patterns and adds information
  • Compression after encryption os not effective
  • Compression uses redundancy and removes compression
  • Compress before encrypting -> More diffusion

Error Correction

  • Operation
    • Checksums
    • Discover errors
    • Correct errors
  • Combined with encryption
    • Adds redundancy
    • Makes ciphertext easier to crack
  • Only error check at time of transmission, not encryption!
    • Does not weaken encryption but still protects the message

Summary

  1. Compress
  2. Encrypt
  3. Transmit and correct

Assymetric

  • Diffie-Hellman first example of asymetric algorithm
  • Needs proof of identity (public key)

  • Find numbers to use for exponents using RSA

Elliptic Curve Cryptography (ECC)

  • A non-vertical line intersecting 2 points will also intersect a third
  • No line intersects at more than 3 points
  • The curve is symmetrical
  • Basic operation

  • Easy to find An if A0, A1 and n are given

  • Very difficult to find n if A0, A1, An are given

  • Example function: y^2 = x^3 + 3x + 5 mod p where x and y are integers and p is prime

    • Private key: n
    • Public key: An
  • Can use shorter keys then RSA (163-359 bits)

Hash functions

  • One way functions that can digest a message
  • Encrypt message digest with private key -> signed message
  • Receipient computes same hash and decrypts signature to verify

CRC 32

  • Produces a 32-bit hash based on Cyclic Redundancy Check
  • Uses a 33 bit polynomial and stores 32 bits of it
  • Easily reversible since intended for error detection, not suitable for signatures
  • A MitM can reverse the algorithm and replace the original message with an evil message with same hash

Cryptographically Strong Hash Functions

  • Uses bit shifts, modulus addition and XOR in rounds to diffuse message
  • Makes it difficult to reverse the process
MD5
  • Very popular but very weak
  • No longer suitable for use
SHA-1
  • 160-bit hash
  • Invented by NSA
  • Also has severe weaknesses
  • No longer recommended after 2010
SHA-2
  • Invented by NSA
  • Contains many different
    • SHA-256
    • SHA-512
SHA-3
  • 2012 NIST competition
  • Collection of functions
  • Based on Keccak algorithm
  • 224-512 bit hash
  • Has much larger internal state

Birthday Attack

  • Probability that two share a birthday in the same room: 1 – everybody has unique birthday
  • 1 person enters room -> 365/365 likelihood for unique birthday
  • 2 person enters room -> 364/365 likelihood for unique birthday
  • 3 person enters room -> 363/365 likelihood for unique birthday
  • 20 person enters room -> 346/365 likelihood for unique birthday 94.7%
  • Probability that all above happend and all were unique: 365/365 * 364/365 * … -> 58.9% for 20 people
  • 23 people -> greater then 50% probability that two have same birthday
  • MitM does not try to match a specific document that is to be signed
  • MitM tries to have signer sign one of MitM documents
  • MitM tries to find hash collisions

  • Protocols demand that we never sign someone else’s document

  • Always append randomness

Identity

  • We sign public keys to proove identity
  • Can be done by individuals in a Web Of Trust
  • Can be done by authorities in a Chain Of Trust

Summary

  • Asymmetric crypto
    • RSA
    • Elliptic Curve
  • Symmertic crypto
    • DES
    • AES
  • Hash Functions
    • MD5
    • SHA 1, 2 and 3
  • Combine algorithms to provide confidentiality and authenticity
    • Encrypt message with symmetric key
    • Encrypt symmetric key with public key
    • Compute digest with hash
    • Encrypt digest with private key

API’s

  • Java Cryptography Extensions (JCE)
  • KeyGenerator generates SecretKey
  • KeyPairGenerator generates Private/Public Key pair
  • SecureRandom is a PRNG and IvParameterSpec for IV’s in block ciphers
  • Cipher and Signature classes perform crypto operations
  • CipherInputStream and CipherOutputStream hooks into the Java stream model
  • JCE uses maximum AES key size 128 bits
  • Unlimited JCEPolicy extra policy files that allow 256 bits
  • Bouncy Castle can be used as well if default JCE is not enough

Symmetric Java API’s

Asymmetric Java API’s

Certificates

  • Defined by X.509 standard
  • Contains a subject, validity, public key and signature from CA
  • Subject is a Distinguished Name; hierarchy of information
    • Country (C)
    • State (ST)
    • Locality (L)
    • Organization (O)
    • Organizational Unit (OU)
    • Common Name (CN) (i.e. domain name on a site)
  • Uses Chain Of Trust
    • Certificate signed by intermediate CA
    • Intermediate CA signed by Root CA
    • Root CA pre-installed in browser and is self-signed
  • Used in different Public Key Cryptography Standards (PKCS)

PKCS #7

  • Cryptographic Message Syntax
  • Certificates

PKCS #10

  • Certification Requeste

PKCS #12

  • Personal Information Exchange Syntax
  • Private keys

Common File Formats

Commands

Summary

  • Certificate uses a Subject (Distinguished Name)
  • Certificate has a validity and public key
  • Certificate is signed by issuer
  • OpenSSL has multiple commands for working with different types of PKCS formats
    • genrsa
    • req
    • x509
    • pkcs12

Authentication and Authorization

  • Passwords are problemtic

    • Reused
    • Dictionary words
    • Not enough entropy
    • Phishing
  • Offline password attacks on leaked databases

    • Dictionary attacks
    • Rainbow tables
    • Same hash on different users
  • Using salted hashes makes it harder to attack

  • Password Based Key Derivation Functions (PBKDF) can be used

Computing Password Entropy

  • H = L * log2 * N
  • Common substitutions (0=o, 1=l, 1=i, etc)
    • Log2 of (size of sustitution dictionary * number of characters)
  • Dictionary words
    • Log2 of (size of dictionary * number of words)
  • Capitalization
    • Mostly caps or mostly lower?
    • 1 bit for each different capital not at the beginning of the word
  • Remaining characters
    • Log2 of (size of alphabet * number of characters)

PBKDF (Password Based Key Derivation Functions)

  • Intended for deriving a symmetric key and IV from a password
    • Used in openssl when encrypting RSA key with AES-256
    • Can be used to generate a salted hash
  • Slow down an offline attack
  • Uses Key Stretching

Steps

  1. Divide password into blocks
  2. Hash each block
  3. Hash the output of 2 again and xor with previous hash
  4. Repeat n times for each block (n > 10000 preferred)
  5. Append results

  • Might want to use different algorithms so we store the algorithm in the DB
  • Also good for future migration

Federation

  • Remove responsibility of identity from applications
  • Separate authentication from authorization
  • Based on trust between multiple parties
  • Identity proved once and authorization granted through different “tickets”

Roles

  • Identity Provider (IP) performs Authentication in centralized identity management
  • Secure Token Service (STS) performs Authorization in single repository of roles and responsibilities
  • Relying Party (RP) consumes STS token and takes action based on token claims and can focus on business logic
  • Both IP and STS are providing services so they are usually called IP-STS and RP-STS

Kerberos

  • Both authentication and authorization
  • Used in many OSs including Windows, OS X and some Linux distros
  • User receieves a Ticket Granting Ticket from Identity Provider (IP)
Steps
  1. User asks IP for token
  2. IP sends token (TGT) encrypted with symmetric key generated from users password (PBKDF)
  3. User can decrypt the TGT if he knows the password
  4. TGT used to request access from other services that perform authorization

WS-Trust and WS-Federation

  • Protocols for Web Services
  • Defines a protocol and XML schemas for SOAP web services to exchange security tokens
  • Active federation – client machine provides proof of identity
    • Client produces a Proof Key (often asymmetric)
    • Client signs a message to prove ownership of the key pair
  • Passive federation – browser redirects exchange tokens through cookies
    • Password based authentication
    • Bearer token signed by STS and encrypted for a specific RP
Secure Assertion Markup Language (SAML)
  • XML-based
  • Provides authentication and authorization claims (assertions)
  • Assertions signed by STS
  • Enveloped signature with reference to its assertion, usually by ID
  • STS signs the Assertion and Signature

XML Signature Wrapping Attack
  • Signature not always enveloped in the assertion, can appear anywhere
  • Certain SAML implementations vulnerable to exchange of elements
  • Signature has signed the “valid” token and the assertion has been added to another part of the document
  • Implementations might validate one assertion and then use another

OAuth

  • Used in social applications and mash-ups
  • Delegates access to services
  • Only provides authorization
  • Allows Agents (clients) to perform actions on behalf of User (like 3rd party Web Service)
  • The Agent (Client) is authorized, not the User
  • Relies on signed token request and share symmetric client secret
Steps
  1. Client registers with OAuth Service Provider and receives a Client Key and Client Secret
  2. User wants Client to act on his behalf so Client requests a Request Token from Service Provider
  3. Client signs the request with the Client Secret
    • Secret is XORd with one constant and then prepended to the message
    • Result is hashed and key is XORd with a different constant and prepended to result
    • Result is hashed again so that the resulting hash is based on message and client secret
  4. Service Provider performs the same operation using the stored Client Key and generates a One Time Token
  5. One Time Token is sent to the Client
  6. Client redirects the User to the Service Provider passing along the One Time Token
  7. User grants Client access (authorization) to the Service Provider
  8. Service Provider redirects User to Client with a Bearer Token
  9. Client can use Bearer Token to get information from Service Provider on User behalf
Mobile and Desktop Apps
  • No backend, uses API calls from Client
  • Client secret embedded in mobile app
  • Apps can be decompiled to find secrets
  • Very problematic since a User may loose control of the access granted to an Agent

OpenID Connect

  • Originally user owned the identity provider
  • Now it is available through Facebook, Twitter, Google etc
  • Built on top of OAuth although OpenID is about Authentication rather then Authorization
  • Usually Authorization comes after authentication
  • OAuth is not authorizing User however, only authorizing an Agent to act on the User behalf
Steps
  1. User wants to access an Agent
  2. User is bounced to Service Provider
  3. User authenticates and creates an Access Token for the Agent
  4. Agent checks with Service Provider if user is authenticated

Summary

  • Passwords is most commong and should be hashed, salted and re-hash (bcrypt, scrypt ftw)
  • Tokes are signed to prove vercity of claims and assure trust relationships
  • Weak crypto is sometimes used with Bearer Tokens and unprotected Client Secrets
  • Crypto is great but must be used correctly!

Case studies

  • Some examples of incorrect usage of crypto

Snapchat

  • Social network
  • Reviewed by Gibson Research
  • Reverse Engineered API and published API
  • Snapchat did not act on notification
  • Bad use of crypto

Snap encryption

  • Used AES ECB (weak)
  • Changed to CBC later
  • Still used same symmetric key
  • Key available in Android and IOS apps
  • Find Friends API allowed user lookup by phone number with no rate limiting
  • Symmetric key should have been unique for each user
  • Users should also have unique Public Keypair to exchange symmetric key
  • Snaps should have been signed by the user who took it so receiver could reject invalid snaps (prevent DoS and spam)

Safari

  • Reviewed by Adam Langley
  • Goto fail allowed any signed certificate to be used although invalid
  • OpenSSL requires private key for signature so it could not be used to generate a key
  • Trivial to create one anyway using code
  • Should have had better code review

Heartbleed

  • OpenSSL library mistake
  • Heartbeat supposed to send back whatever the client sent the server
  • Pointer p with a TLS Heartbeat record could be used to overflow since the client provided the length of the buffer
  • Client could claim to send 64k of data although specifying much less like a few bytes
  • Server would send back 64k of memory that happen to sit next to the bytes from the client
  • Leaves no trace
  • Keys, certificates and other sensitive data could leak
  • Should have had better code review

Target

  • Reviewed by Brian Krebs
  • Attackers installed malware on Point of Sales systems
  • Pin pad gathered pin and credit card data and sent it to PoS
  • PoS intercepted the data and dumped it to a share
  • Attackers remote connected to get the file every now and then
  • Not a crypto attack, needed access to PoS
  • Track Data is unencrypted, chip with encrypted data would have helped
  • PIN number sent to chip causes a unique CVV (iCVV) is created that is used to process payment
  • PIN would then never have been sent to PoS
  • Some Chip and Pin systems have static iCVV numbers though, which opens up for replay attack
  • Dynamic Chip and Pin is much better but Pin Pad could also intercept the data if Pin Pad is infected
  • Pin Pad could then be MitM and steal pin or present different amount for transaction
  • Smartphone could be used to get rid of middle hand hardware

NSA

  • Knew about differential crypto analysis without telling the world
  • Dual Elliptic Curve PRNG has constants P, Q and Phi are defined in the specification being suspicious of a back door
    • If exponent e is known such thta Q^e=P it is possible to determine the internal state of the machine
    • Would make it possible to predict new keys
    • Could be that there is no issue, but understanding the full system is important
  • Peer review is critical
  • Simplicity is critical
  • Don’t trust math provided by 3rd party

Lessons learned

  • Avoid static symmetric keys
  • Keep private keys private
  • Use asymmetric crypto to establish trust
  • Dont write crypto code on your own
  • Audit all crypto code
  • Question crypto provided by 3rd party
    • Understand the source
    • Understand the implementation