Month: July 2017

Authentication first
A new key is used for each session
Using shared (master) secret
encrypt the new key
Using public keys

Establish a shred key for the session even if a there is already a shared secret key
Typically a long term secret key is called a Master key, possibly derived from a password.
The master key is used to authenticate and establish a new session key.

Alice -> Bob: E(PRa, E(PUb, K))
diffie-Hellman with signing,i.e.,
Alice -> Bob:E(PRa, Y^a)
Bob -> Alice:E(PRb, Y^b)

Each communication pair needs to share a master key

Authentication protocols
Key exchange protocols
Kerberos

Alice and Bob want to communicate securely over the Internet, they need to:
– authenticate
– establish and exchange keys
– agree to cryptographic operations and algorithms
Building blocks:
public-key (asymmetric) and secret-key(symmetric) algorithms, hash functions

Mutual Authentication: Shared Secret
– R1 and R2 should not be easily repeatable and predictable
otherwise and adversary, Trudy, can record and replay challenge and/or response to impersonate Alice or Bob
– Use large random values
– Kap needs to be protected at Alice and Bob(end points of communication)

Reflection Attack
I’m Alice R2 -> connection -> R1, E[Kab,R2]

Fixes:
Different keys for initiator and res ponder
Trudy can’t get Bob to encrypt using Alice’s key

Different type of challenges for initiator and responder
e.g., even number for initiator and odd number for responder

Developed by NIST, specified in the Secure Hash Standard, originally 1993
Revised as SHA-1 in 1995
160 bit hash
NIST specified SHA2 algorithms in 2002
Hash value lengths of 256, 384, and 512
Similar to SHA-1

SHA-1, SHA-256, SHA-384, SHA-512
Message digest size, Message size, Block size, Word size, Number of steps, Security

Message Processing
Message Digest Generation using SHA-512

SHA-512 Processing of a Single 1024-bit block

Hash based message authentication
– cryptographic hash functions generally execute faster
– library code is widely available
– SHA-1 was not designed for use as a MAC because it does not rely on a secret key
– issued as RFC2014
– Has been chosen as the mandatory-to-implement MAC for IP security
– Used in other Internet protocols such as Transport Layer Security(TLS)

HMAC Security
– security depends on the cryptographic strength of the underlying hash function
– It’s much harder to launch successful collision attacks on HMAC because of secret key

How many people do you need in a room before you have a greater than 505 chance that two of them will have the same birthday?
Assume 356 birthdays(our containers)

% chance that two people in the room have the same birthday
100% requires 366 people (the pigeonhole principle)

Compute probability of different birthdays
Random sample of n people(birthdays) taken from k (365)days
k^n samples with replacement
(k)n=k(k-1)…(k-n+1) sample without replacement
Probability of repetition:
p = 1 – (k)n/k^n = n(n-1)/2k = 0.5 if n = √k

1-(k)n/k^n = the probability that a pair share the same birthday
If k = 365, n = 19
If there are 19 people in a room, there is a good chance that two of them share the same birthday!

There are many more ‘pigeons’ than ‘pigeonholes’
Many inputs will be mapped to the same output. That is, many input messages will have the same hash.
Conclusion: The longer the length of the hash, the fewer collisions.

Compute message digest of data of any size
Fixed length output:128-512 bits
Easy to compute H(m)
Given H(m), no easy way to find m
One-way function
Given m1, it is computationally infeasible to find m2 = m1 s.t. H(m2) = H(m1)
weak collision resistant
Computionally infeasible to find m1=m2 s.t. H(m1)=h(m2)
strong collision resistant

Requirements for a practical application of a hash function
The one way property
Hash functions are unique to each message

Sender: Message with encrypted hash code
-> generate an un-encrypted hash code
-> create an alternate message
-> Receiver: Forged message with encrypted hash code

Hash Function Weaknesses
-> Pigeonhole principle
-> The Birthday Paradox

n = numbers of pigeons
m = number of holes
n = m There is one pigeon per hole
n > m Then at least one hole must have more than one pigeon

Deterministic
– for the same key, a particular plaintext is always mapped to a particular ciphertext
– special-case plaintexts 0, 1, or -1 produce ciphertexts 0, 1, or -1 regardless of keys
Malleable
– Transforming a ciphertext into another leads to predictable transformation to plaintext
For c = m^e mod n, attacker change c to s^exc
-Receiver gets sxm instead of m

RSA in practice
– PKCS(public key cryptography standard) uses OAEP(optimal asymmetric encryption padding)
– Append padding(seeded from random byte) as prefix to m

Diffie and Hellman Key Exchange
– first published public-key algorithm
– by diffie and Hellman in 1976 along with the exposition of public key concepts
– Used in a number of commercial products
– Practical method to exchange a secret key securely that can then be used for subsequent encryption of messages
– Security relies on difficulty of computing discrete logarithms

Given KU = and KR =

encryption: c = m^2 mod n, m < n decryption: m = c^d mod n signature: s = m^d mod n, m < n verification: m = s^e mod n Given pub = and priv =
n = p*q,Θ(n) = (p-1)(q-1)
exd = 1 mod Θ(n)
x^exd = x mod n
encryption: c = m^e mod n
decryption: m = c^d mod n = m^exd mod n = m mod n = m(since m < n) digital signature (similar) 88^7 mod 187 = 11 -> 11^23 mod 187 = 88 -> plaintext 88

Factoring an integer with at least 512-bit is very hard!
But if you can factor big number n then given public key , you can find d, and hence the private key by:
knowing factors p, q, such that, n = p*q
then compute Θ(n)=(p-1)(q-1)
then find d such tat exd = 1 mod Θ(n)

Multiplication modulo M

Multiplicative inverse: multiplication MOD
M yields 1
e.g., M=10, 3 and 7 are inverse of each other because 3*7 MOD 10 = 1

Only some numbers have inverse
but 2, 5, 6, 8 do not have inverse when M=10

Use Euclid’s algorithm to find inverse
Given x, n, it finds y such that x*y mod n = 1
Only the numbers relatively prime to n has MOD n multiplicative inverse

Totient Function
x is relatively prime to n: no common factor other than 1
Totient function Θ(n): number of integers smaller than n and relatively prime to n
if n is prime, Θ(n)= n-1
if n = p*q, and p, q are primes, Θ(n)=(p-1)(q-1)
if n = p*q, and p, q are relative prime to each other, Θ(n)=Θ(p)Θ(q)

X^y mod n = X^ymodΘ(n)mod n
if y = 1 mod Θ(n)then x^y mod n = x mod n

RSA(Rivest, Shamir, Adleman)
– Widely used, and one of the first(1977)
– Support both public key encryption and digital signature
– Assumption/theoretical basis:
Factoring a very large integer is hard

Variable key length
Variable plaintext block size
– Plaintext treated as an integer, and must be “smaller” then the key
– Ciphertext block size is the same as the key length

Modular arithmetic
RSA
Diffie-Hellman

Public key algorithms are based on modular arithmetic
– modular addition
– modular multiplication
– modular exponentation

Addition modulo (MOD) M
Additive inverse: addition MOD M yields 0
e.g. M=10, for k=2, its inverse is k^-1=8 because 2+8 MOD 10 = 0
Reversible: by adding the inverse
– convenient for decryption
e.g., for c = 3, p = c + k = 3+2 MOD 10 = 5;
p+k^-1 = 5+8 MOD 10 = 3 = c

Calculating AB mod C for any B

Find: 5117 mod 19
Step 1: Rewrite B into its binary form

117 = 1110101 = 1 2^6 +1 2^5 + 1 2^4 + 1 2^2 + 1*2^0
117 = 64 + 32 + 16 + 4 + 1

Step 2: Convert to Powers of 2 and find the mod

5117 mod 19 = (52^6 52^5 52^4 52^2 52^0)

51 mod 19 = 5
52 mod 19 = (55) mod 19 = 25 mod 19 = 6
54 mod 19 = (66) mod 19 = 36 mod 19 = 17
58 mod 19 = (1717) mod 19 = 289 mod 19 = 4
516 mod 19 = (44) mod 19 = 16 mod 19 = 16
532 mod 19 = (1616) mod 19 = 256 mod 19 = 9
564 mod 19 = (99) mod 19 = 81 mod 19 = 5

Step3: Combine the individual powers to find the final answer

5117 mod 19 = (564532 5165451 ) mod 19
= (564 mod 19 532 mod 19 516 mod 19 54 mod 19 51 mod 19 )mod 19
= 61200 mod 19
= 1