Information Security
Contents
Introduction to Information Security
Confidentiality
- Prevention of unauthorised disclosure of information
- Privacy - protection of personal data
- Secrecy - protection of data belonging to an organisation
Integrity
- Prevention of unauthorised modification of information
Availability
- Prevention of unauthorised with-holding of information or resources
Access Control
- Protection of system resources against unauthorised access
Authentication
- Verifying an identity claimed by or for a system entity
Non-repudiation service
- A service that provides protection against false denial of involvement in a communication
Security Mechanisms
- feature designed to detect, prevent or recover from a security attack
- No single mechanism that will support all services required
- One particular element underlies many of the security mechanisms - cryptographic techniques
Threats and their classification
Security Attack
- Any action that compromises the security of information owned by an organisation
- Information Security is about how to prevent attacks, or failing that, to detect attacks on information-based systems
- Often threat and attack are used to mean the same thing
Passive Attacks
- Release of message contents - we want to prevent an opponent from learning the contents of exchanged messages
- Traffic analysis - the opponent could determine the location and identity of communicating hosts and could observe the frequency and length of messages being exchenged
Active Attacks
- Masquerade - takes place when one entity pretends to be a different entity
- Replay - Capture message from B to A, later replay the message to A
- Modification of message contents - some portion of the legitimate message is altered or the message is delayed or recorded to produce and unauthorised effect
- Denial of service - prevents or inhibits the normal use or management of communications facilities
Conventional Cryptography
In cryptography there are three types of security:
Computational Security - which means that the best algorithm for breaking the cryptosystem requires a very large number of operations, e.g. AES
Provable Security - which means that breaking the encryption is at least as hard as solving some other difficult problem, e.g. RSA, Diffe-Hellman
Unconditional Security - where the cryptosystem can never be broken, even with infinite resources, e.g. one time pad
Secure Ciphers Properties
Confusion
- It should not be possible to predict what changing one character in the plaintext will do to the ciphertext
- This involves making the relationship between the key and the ciphertext as complex and involved as possible
- Ideally every key bit influences every output bit
- Good confusion can only be achieved when each character of the ciphertext depends on several parts of the key, and this dependence appears to be random to the observer
- Ciphers that do not offer much confusion can be susceptible to frequency analysis
Diffusion
- A small change in the plaintext should affect large parts of the ciphertext, this involves the spreading of the plaintext over the ciphertext
- Diffusion propagates bit-changes from one part of a block to other parts of the block
- In contrast to confusion, diffusion spreads the influence of a single plaintext bit over many ciphertext bits
- Diffusion is associated with the dependency of bits of the output in bits of the input
The Avalanche Effect
- In a cipher with good diffusion, flipping an input bit should result in the change of many of the output bits
Strict Avalanche
- The change of a single input bit should result in each output bit having a probability of one half of changing
Various Encryption Algorithms
One Time Pad
- An encryption algorithm that can be proved to be perfectly secure
- The message is encrypted by combining (usually XORing) it with a perfectly random key at least as long as the message, and the key is only used once
- Apart from the problem of obtaining a perfectly random key (you cannot generate them on a computer) the main problem with one time pads is the distribution of the keys
Stream Cipher
- A type of symmetric encryption algorithm
- It can be designed to be exceptionally fast, much faster than any block cipher
- Typically operates on smaller units of plaintext, usually bits
- With a stream cipher, the transformation of plaintext units will vary, depending on when they are encountered during the encryption process
- A stream cipher generates what is called a keystream (a sequence of bits used as a key)
- Encryption is accomplished by combining the keystream with the plaintext, usually with the bitwise XOR operation
- The generation of the keystream can be independent of the plaintext and ciphertext, yielding what is termed a synchronous
- Or it can depend on the data and its encryption, in which case the stream cipher is said to be self-synchronising
- Most stream cipher designs are for synchronous stream ciphers
Stream Cipher Example - Vernam Cipher
A Vernam cipher is a stream cipher in which the plaintext is XORed with a random or pseudorandom stream of data the same length to generate the ciphertext. If the stream of data is truly random and used only once, then the cipher is a one-time pad.
Commutative Property of XOR
An operation is commutative if a change in the order of the operands does not change the result
e.g. A xor B = B xor A
Associative Property of XOR
An operation is associative if a change in the grouping of the operands does not change the result
e.g. A xor B xor C = (A xor B) xor C = A xor (B xor C)
Block Ciphers
- Operate on large blocks of data
- The encryption of any particular plaintext will result in the same ciphertext when the same key is used
- It is a type of symmetric key encryption
- It transforms a fixed-length block of plaintext data into a block of ciphertext of the same length
- This transformation takes place under the action of a user-provided secret key
- Decryption is performed by applying the reverse transformation to the ciphertext block using the same secret key
- The fixed-length is called the block size, and for many block ciphers the block size is 64 bits
Generic Example: Feistel Cipher Structure
- Many conventional symmetric key block ciphers use a structure developed by Horst Feistel
- Partitions input block through two halves, which is processed through multiple rounds. They perform a substitution on the left data half based on a round function of right half and substitution key. Then they have a permutation swapping the halves
Feistel Cipher Implementation
- Block size: larger blocks give greater security but reduce the speed of the cipher
- Key size: larger keys give greater security but mey reduce the speed of the cipher
- Number of rounds: a single round does not offer adequate security, multiple rounds increase security
- Subkey generation algorithm: the greater the complexity the greater the difficulty of cryptanalysis
- Round function: the greater the complexity the greater the difficulty of cryptanalysis
Feistel Example: DES
Block Cipher Example DES
DES Decryption must unwind the steps of data computation - do encryption steps again using subkeys in reverse order
Strength of DES - Key size
- 56 bit keys have 2^{56} = 7.2 * 10^{16} values
- Brute force search looks to be hard
- Recent examples have shown it to be possible
- Still must be able to recognise the plaintext
- Must now consider alternatives to DES
DES Operation Modes
ECB - Electronic Code Book
- In ECB each 64 bit block of plaintext is simply encrypted a block at a time
- Thus is a message contains several identical 64 bit plaintext blocks, this will show up as identical ciphertext blocks
- This is a weakness that may be possible to exploit
CTR - Counter Mode
- Counter mode essentially turns a block cipher into a stream cipher
- Each plaintext block is encrypted by XORing it with the encrypted value of a 'counter'
- The counter may literally be a counter, i.e. it increments by some fixed value, e.g. 1 or it can be a simple function which produces a sequence that has a long period
The advantages of counter mode in comparison with CBC are:
- It can be parallelised
- Any cipher block can be decrypted without having to decrypt previous blocks
- Encrypted values of the counter can be pre-calculated and stored
- Errors do not propogate
Modifications - Triple DES
- Triple DES applies the DES counter algorithm three times to each data block
- The original DES cipher's key size of 56 bits was generally sufficient when that algorithm was designed but the availability of increasing computational power made brute force attacks feasible
- Triple DES provides a relatively simple method of increasing the key size of DES to protect against such attacks without the need to design a completely new block cipher algorithm
Triple DES uses a 'key bundle' which comprises three DES keys K_{1}, K_{2},and K_{3}, each of 56 bits
DES encryption algorithm is:
- ciphertext = EK_{3}(DK_{2}(EK_{1}(plaintext))) - ie.e DES encrypt with K_{1}, DES decrypt with K_{2}, then DES encrypt with K_{3}
Decryption is the reverse
- plaintext = DK_{1}(EK_{2}(DK_{3}(plaintext))) - i.e. DES decrypt with K_{1}, encrypt with K_{2}, decrypt with K_{3}
Could we use double DES?
Is the length of the key duplicated? On this model we can expect that the effective length of the key is 2^{2n} where n represents the length in bits of K_{1} and K_{2} keys. The size of the resulting key, indeed in this case is equivalent to 2^{n+1}, an insignificant increase.
RC5
- RC5 is a block cipher notable for its simplicity
- It was designed by Ronald Rivest in 1994
- RC stands for "Rivest Cipher", or alternatively, "Ron's Code"
- The Advanced Encryption Standard (AES) candidate RC6 was based on RC5
- Unlike many schemes, RC5 has a variable block size (32, 64 or 128 bits), key size (0 to 255) and number of rounds (0 to 255)
- A key feature of RC5 is the use of data dependent rotations
- he general structure of the algorithm is a Feistel-like network
Substitution Cipher / Caesar Cipher
- Caesar cipher, also known as the shift cipher, Caesar's Code or Caesar Shift
- It is one of the simplest and most widely known encryption techniques
- It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet
Transposition Cipher
- The message is placed row-wise is a 2D array (in this case 3 * 5) starting at top left
- The encrypted message is read out column-wise starting at the bottom right
A | D | V | A | N |
C | E | A | T | |
N | O | O | N |
- So the encrypted message is NTNOAAO VNED CA
Hashing
Various Hashing Algorithms
One-Way Hash Function
One-way hash can be achieved using either a shared secret key or using public private key encryption. Public key encryption has two advantages over a secret key:
- It provides a digital signature as well as message authentication
- It does not require the distribution of keys
It is also possible to use a shared secret secret value, which is concentrated to the message and then hashed using a standard hashing function.
Block Ciphers as Hash Functions
- Using H_{0} and zero pad of the final block
- Compute H_{i} = E_{Mi}[H_{i} - 1]
- And use the final block as the hash value
- Resulting hash is too small
- Due to a direct birthday attack
- And due to "meet in the middle" attack
- Other variants also susceptible to attack
Birthday Attack
- Opponent generates 2^{m/2} variations of a valid message all with essentially the same meaning
- Opponent also generates 2^{m/2} variations of a desired fraudulent message
- The two sets of messages are compared to find a pair with the same hash (probability > 0.5 by birthday paradox)
- Have user sign the valid message, then substitute the forgery, which will have a valid signature
Conclusion is that we need to use larger hashes
Meet In The Middle attack
- Requires the ability to encrypt and decrypt, and the possession of pairs of plaintexts and corresponding ciphertexts
- C = E_{K2} (E_{K1} (P))
- P = D_{K1} (D_{K2} (C))
- E_{K1}(P) = D_{K2} (C)
- Subcipher
Hashing vs MAC
- MAC - Message Authentication Code (keyed hash)
- Accepts as input a secret key and arbitrary length message to be authenticated, and outputs a MAC
- Protects the message's integrity and authenticity because the verifiers also possess the secret key
- The security of HMAC relates to that of the underlying has algorithm
- Attacking HMAC requires either:
- Brute force attack on the key used
- Birthday attack, but since it is keyed you would need to observe a very large number of messages
- Choose has function used based on speed vs security constraints
Uses: to defend against active and passive attacks
Public Key Cryptography
Diffe-Hellman
Diffe-Hellman conditions
- It is easy for B to generate a pair of public and private keys KP_{b} and Ks_{b}
- It is easy for sender A, knowing the public key and the message to be encrypted, M, to generate the ciphertext
- It is easy for the receiver B to decrypt the resulting ciphertext using the private key to recover M
- It is infeasible for an opponent, knowing the public key, to determine the private key
- It is infeasible for an opponent, knowing the public key and a ciphertext, to recover the original message
Diffe-Hellman Key Exchange
- Exponential Key Exchange
- A public key system that provides a mechanism for setting up a secret, but unauthenticated connection between two parties
- It does not provide encryption or digital signatures
- It provides a method by which two parties communicating over a non-secure channel can agree on a shared secret key
- Its security is based on the discrete logarithm problem
- In its basic form it does not provide authentication
The Discrete Logarithm Problem
Given x, g, and p, where p is prime and g is a primitive root of p, and x = g^{r} mod p, find r. This is believed to be hard
Primitive Roots of a Prime Number
A number g, where 0 < g < p, is a primitive root of a prime number p if g^{x} mod p for x = 1, 2, ... p - 1 generates the integers 1 to p - 1 in some permutation. For example, 3 is a primitive root of 7.
3^{1} mod 7 = 3 | 3^{2} mod 7 = 2 | 3^{3} mod 7 = 6 |
3^{4} mod 7 = 4 | 3^{5} mod 7 = 5 | 3^{6} mod 7 = 1 |
The Diffe-Hellman Algorithm
- A and B share publicly a prime number p and a number g where 1 < g < p and g is a primitive root of p
- A and B each generate a random number S_{A} and S_{B} respectively and keeps them secret
- A computed T_{A} = g^{SA} mod p and B computes T_{B} = g^{SB} mod p
- A sends T_{A} to B and B sends T_{B} to A
- So now A knows p, g, S_{A} and T_{B} and B knows p, g, S_{B} and T_{A}
The choice of the prime number
Although Diffe-Hellman works with any prime, p, it is more secure if (p - 1)/2 is also prime. Such a prime is called a safe prime or Sophie Germain prime. The algorithm can also be weakened (if it still works) if g is not a primitive root of p
Diffe-Hellman Example
A and B wish to exchange a secret key using the Diffe-Helman method. They share the prime number 29 and the number 2. A's secret number is 4 and B's secret number is 5
S_{A} = 4; S_{B} = 5;
- A calculates T_{A} = 2^{4} % 29 = 16
- B calculates T_{B} = 2^{5} % 29 = 3
- A calculates K_{A} = 3^{4} % 29 = 23
- B calculates K_{B} = 16^{5} % 29 = 23
So the shared key is 23 or some agreed function of it.
RSA Encryption
RSA is the best known and most widely used public key scheme. It is based on exponentiation in a finite field over integers modulo a prime. It uses large integers (e.g. 1024 bits). Its security comes from the cost of factoring large numbers.
Key setup
Each user generates a public / private key pair by:
- selecting two large primes at random, p and q
- Calculate their system modulus n = p * q
- Define ø(n) = (p - 1)(q - 1)
- Select the encryption exponent e, where 1 < e < ø(n), gcd(e,ø(n)) = 1
- Compute d to satisfy the congruence relation de = 1, i.e. de = 1 + kø(n) for some integer k
- Publish their public encryption key PU = {e,n}
- Keep secret their private decryption key PR = {d,n}
RSA Use
To encrypt a message M the sender:
- Obtains the public key of the recipient PU = {e,n}
- Computes C = M^{e} % n, where 0 <= M < n
To decrypt the ciphertext C the owner:
- Uses their private key PR = {d,n}
- Computes M = C^{d} % n
The message M must be smaller than the modulus n
RSA Example 1
- Selected primes: p = 17, q = 11
- Compute n = pq = 17 * 11 = 187
- Compute ø(n) = (p - 1)(q - 1) = 16 * 10 = 160
- Select e: gcd(e,160) = 1; choose e = 7
- Determine d: de % 160 = 1 and d < 160
- de is 1 plus an integer multiple of ø(n), hence with i = 6, d = (1 + i + 160) / 7 = 23 or value is d = 23 since 23 * 7 = 161 = 160 + 1
- Publish public key PU = {7,187}
- Keep secret the private key = {23,187}
Encryption and Decryption
Given message M = 88
Encryption: C = 88^{7} % 187 = 11
Decryption: M = 11^{23} % 187 = 88
RSA works because of Euler's Theorem
RSA Example 2
- Let two primes be p = 7 and q = 13. Thus modulus n = p * q = 7 * 13 = 91
- Select e = 5, which is a valid choice since there is no number that is a common factor of 5 and (p - 1)(q - 1) = 6 * 12 = 72, except for 1
- The pair of numbers (n,e) = (91,5) forms the public key
- d is calculated correct by computing de = 29 * 5 = 145 = 1 mod 72
- Hence the public key is (91,5) and the private key is (91,29)
RSA Example 3
- p = 11, q = 5, e = 17, n = 55, ø(n) = 40
- pk = (55,17); sk = (55,33)
RSA Example 4
- p = 3, q = 19, e = 5, n = 57 ø(n) = 36
- pk = (57,5); sk = (57,29)
RSA Security
Possible approaches to attacking RSA are:
1. Brute force key search, or exhaustive key search, is used against any encrypted data (infeasible given the size of the numbers)
- Such an attack might be utilised when it is not possible to take advantage of weaknesses in an encryption system (if any exist) that would make the task easier
- It consists of systematically checking all possible keys or passwords until the correct one is found
- In the worst case, it involves traversing the entire search space
2. Mathematical attacks - based on the difficulty of computing ø(n), by factoring modulus n
3. Forward search attack - the plaintext from C can be discovered by simply encrypting all possible plaintext messages until the resultant ciphertext matches C
4. Dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by trying hundreds or sometimes millions of likely possibilities, such as words in a dictionary
5. Hybrid attack is a Combinator attack. One side is simply a dictionary, the other is a result if a brute-force attack. In other words, the full brute-force keyspace is either appended or prepended to each of the words from the dictionary
ElGamal Algorithm
- Is an asymmetric key encryption algorithm for public key cryptography, which is based on the Diffe-Hellman key exchange
- It was described by Taher ElGamal in 1984
- ElGamal encryption can be defined over any cyclic group G. Its security depends upon the difficulty of a certain problem in G related to computing discrete logarithms
- It is used in the free GNU Privacy Guard software, recent versions of PGP, and other cryptosystems
- The Digital Signature Algorithm is a variant of the ElGamal signature scheme, which should not be confused with ElGamal encryption
ElGamal Key Generation
Bob generates public and private keys as follows:
- He picks a large random prime p
- He finds a generator g mod p (i.e. g^{x} % p gives a different answer for every value of x, which means that g^{p-1} mod p in the first time the answer is one)
- He picks a ransom number a between 1 and p - 1
- He computes y = g^{a} % p
The public key is (p,g,y)
The private key is a
ElGamal Encryption
If Alice wants to send Bob a message, she looks up Bob's public key (p,g,y) and breaks the message up into blocks with each block less than p. Then for each message block m she takes the following steps:
- She generates a random number k between 1 and p - 1
- She computes:
- r = g^{k} % p
- x = y^{k} % p
- c = (m * x) % p
- She sends Bob the values r and c
ElGamal Decryption
Bob receives the ciphertext (r,c) from Alice. He decrypts it as follows:
- He computes r^{a} mod p = x
- {r^{a} = (g^{k})^{a} = g^{ka} = g^{ak} = (g^{a})^{k} = yk = x
- Now he can solve c = (m * x) mod p to find the value of m
Only Bob can do this because only Bob knows the value of the private key a
Comparing RSA and ElGamal
RSA | ElGamal |
---|---|
Security based on the difficulty of the factorisation problem | Security based on the difficulty of the discrete log problem |
The ciphertext is just one value c which is roughly the same size as the message m | The ciphertext is two values c and r, and so is twice the size of message m |
The encryption and decryption algorithms are the same (modular exponentiation) | The encryption and decryption algorithms are different (although both take about the same time to perform) |
RSA is a patented algorithm | ElGamal has no patent. This gives it a financial advantage over RSA |
PKI Authentication
CA Usage
- Anyone who wants a trusted copy of Y's public key can obtain it from X, or Y can present the certificate they received from X
- For Z to verify Y's public key they hash the first part of the certificate and decrypt the second part with X's public key
- If the hash that Z made is the same as the decrypted hash then Z is assured that the public key in the first part of the certificate is that of Y
- This is fine as long as you can trust X
Signing an email message
Verifying the digital signature of an email
Attacks on Digital Certificates
- If W can convince X that they are Y and gets X to issue a certificate to them, then W can masquerade to whoever they want as Y. Users of certificates signed by X must trust X's competence
- Users of certificates signed by X must also trust X's honesty
- Users of certificates signed by X must protect their copy of X's public key
- X must protect their private key
Comparison of Certificate Authorities and Key Distribution Centres
Both CAs and KDCs are trusted third parties
- KDCs distribute secret keys
- All users of a KDC system share secret keys with the KDC
- When a user wishes to securely communicate with another user it applies to the KDC for a secret key which is returned encrypted with the secret key shared with the KDC
- The secret key for communication is also sent to the other user encrypted with the secret key that they share with the KDC
- CAs confirm the identity of a user and bind that identity to the user's public key producing a digital certificate signed by the CA's private key thus verifying the user's public key
- Since CAs do not need to be online they can be made physically secure and are not liable to a 'network attack'
- Since CAs do not need to be online they can be less complex than KDCs as they do not need to perform network protocols
- If a CA crashed, the network would not be disabled as with a KDC, although new certificates and new revocation lists could not be produced
- A compromised CA cannot decrypt conversations but can issue bogus certificates allowing impersonation
Talking Points in Information Security
The Darknet
The darknet is the portion of the internet that does not show up in search engines results (closed, invite-only forums, private networks etc., as well as TOR .onion hidden services. TOR provides anonymity of browsing and PGP is used for communications. But it is important to create persistent identities for repudiation. Vendors have Ebay-like feedback nd bitcoin payments made through escrow services or multi-signature transactions.
TOR
- The message is first encrypted with several symmetric keys
- Then a routing onion is created, which contains directions to the next router on the path and the symmetric key for the current layer
- These are encrypted with the public keys of the chosen routers in order, starting with the last
- Each message is padded so that no meta-data can be used for identification
- Routers forward messages in batches, sorted in random order
Compromising one router is not a problem, they are only given enough information to track the next link in the chain. Even if someone monitors traffic from a majority of routers, as long as one router in the path is honest, anonymity is assured.
TOR weaknesses No protection on exit routers. The anonymity of TOR gives no confidentiality to messages that leave the onion network.
Marketplace take downs
- Silk Road - it is believed that a server misconfiguration caused the real IP to be leaked
- Operation Onymous
- Operation Hyperion
Cryptocurrency - Bitcoin
- Credit cards are symmetric, where the secret is widely distributed to many parties
- Paypal, Google Wallet, Apple Pay, are closed systems
- Bitcoin has no central authority, asymmetric cryptography. Spend using the private key, accept money using the public key
Each user needs to see a history of all transactions to know their balance and if payments are successful. The minting of bitcoins is a reward for the creation of a block. A block contains a list of all valid transactions since the last block (about 10 minutes), a hash of the previous block and a nonce. The hash of the block must be less than the current challenge value, meaning that a great many nonces must be attempted before the right one is found. The reward for creating a block is 12.5 bitcoins. The block chain can fork due to coincidence and network latency but the longest chain will be accepted. Modifying a block from the past would mean recreating all subsequent blocks and require 51% of the computing power of the network.
What is to stop...
Forging of bitcoins | Difficulty of block creation |
Forging transactions | Digital signatures |
Lack of availability of the ledger | Block creation reward and transaction fees |
Inflation | Bitcoin creation will slow down over time |
Stealing bitcoins from wallets | Protection of the private key |