Cryptography

Página 1

Encryption- Encoding a message such that only authorised users may read it

Cipher- Encryption algorithm- Takes string of plaintext and converts it into string of ciphertext

Encryption can provide:

Confidentiality

Integrity

Authenticity

Encryption converts a plaintext message M into cipertext C under control of a key K

C is not secret but without the key should be impossible to reconstruct M

Comes in 2 forms:

Symmetric- same key for encryption/ decryption

Asymmetric- seperate keys

3 primitive types:

Stream ciphers- operate on a stream of input data

Block ciphers- operate on a fixed sized block

Hash functions- take data of any size and output block of fixed size

Caesar cipher

Substitution cipher

Replace each letter of plaintext with a shifted letter further down the alphabet

Vulnerable to frequency analysis- it is very bad cipher, can see patterns so can work out the key by brute force

Kerckhoffs principle- "A cryptographic system must be secure even if everything is known about the system with the exception of the secret key"

This is better than security through obscurity

One-time pad

Perfect secrecy

Lacking in portability- key is same size as message

Convenience- keys must never be reused

Modern stream ciphers attempt to approximate it with a pseudorandom key stream

Modern Stream Ciphers

Use initial seed key to generate infinite pseudorandom keystream

Message and keystream are combined with XOR

Stream ciphers

Used where hardware resources limited

Message stream of unknown length

Used for bluetooth, GSM

Block ciphers

Use key to encrypt fixed size block of plaintext to fixed size block of ciphertext

More computationally expensive, but have benefits

Not as vulnerable to known and chosen plaintext attacks

They diffuse changed throughout each block

SP Networks

Repeated substitution and permutation

Combine substitution process with a permutation into a single round

Rounds repeated enough times to ensure algorithm is secure

Substitution boxes add confusion by replacing values with other values (using lookup table)

Permutation boxes add diffusion by moving values around from input to output

One round isn't enough because analysis of input and output changes can reveal contents of S boxes

More rounds = more diffusion

Replacing permutation with linear transformation is more effective- each bit is the XOR combination of multiple previous sub box outputs

Having large block sizes is better- e.g. 8 bit would be vulnerable to dictionary attacks by pre computing all possible blocks

Typically 128 and 256 bit block sizes

Feistal Ciphers

Chains multiple rounds together using any round function

Basis of many modern block ciphers e.g blowfish, DES

3 rounds sufficient that plaintext attack wont work

4 rounds can also beat ciphertext attack

DES used to be standard- 64 bit, 16 round cipher, 56bit key

AES succeeded it in 2002

AES

Built around Rijndael algorithm

SP network, 128 bit block size, key length 128/192/256 bits

Round count 10/12/14 cycles depending on key

Would take 100 trillion years to break

Block cipher modes

Messages dont come in convenient 128 block lengths

Need to run block cipher repeatedly on consecutive blocks

Electronic Code Book- just encrypt one block after another- weak

Cipher Block Chaining- XOR output of each cipher block with next input- not totally immune to insertion of malicious blocks

Counter Mode- Encrypting a counter to produce stream cipher- can be parallelized

Galois Counter Mode- extends counter mode to add authenticity- combines ciphertext with authentication tag- extremely parallelisable, robust to message alteration

Public key (asymmetric) cryptography

2 keys- public and private

Premise that it is infeasible to calculate a private key from public key

Achieved through maths- modular arithmetic and integer factorisation

Can exchange private symmetric key in the open

Can verify sender of a message

Can't deny you've done something

As computer power increases, can increase size of numbers

Comparison:

2 keys

Much larger keys (1024/2048 bits vs 128/256bits)

Computationally slower

Mathematical principles rather than permutation and substitution

Discrete logarithms much harder to compute

Generator- number that is raised to a certain power

Diffie-Hellman key exchange

Public key protocol exchange symmetric key in private

Relies on difficulty of finding discrete logs

e.g. 2 users agree on large prime p and generator g that is primitive root of p

Users choose private values a and b at random, then send public A and B's to each other

1 user computes B^a mod p, other computes A^b mod p

Secret shared key is g^ab

Yet only g, p, A = g^a and B = g^b are public meaning only way to find a or b is complex logs

Vulnerable to man in the middle attack

Can be avoided by combining with another protocol

Logjam- specifies the kinds of prime p and generator g we must use

Ephemeral mode- running DH in this mode forces new key exchange every time - more secure, recommended for TLS

Elliptic curve cryptography- can be used in place of mod arithmetic in DHKEX, much stronger than public key schemes for the same key length

RSA

Based on integer factorisation

Can provide both encryption and authentication

Integer factorisation- any integer can be expressed as the multiplication of a list of prime numbers

Longer the value the harder and slower this gets

Semi primes are hardest numbers to factor

Hash functions

Takes message of any length and returns pseudorandom hash of fixed length

Used everywhere

Output must be indistinguishable from random noise

Bit changes must be spread through the entire output

One way

Must be long enough to avoid a birthday attack- collision after 2n/2 random attempts

Generated using block cipher

E.g. MD5- 128bit, 4 rounds (broken) SHA-2, considered safe

Message authentication codes- calculate hash of a message and append to end of message- provide integrity and authenticity not confidentiality, ensures messages have not been altered

Keyed hashing- using a shared key to preserve integrity, only those who know the key can alter the message or hash

Digital signatures- DSA or RSA, can use trusted third party in order to verify the ownership of a public key. Can be self signed. Part of TLS