Saturday, January 13, 2018

speed test results

Primary router - TP-Link Archer C60 AC1350 - Dual band
Repeater(bridge) - tp link wr841n
ISP: ACT Broadband
Device: MI A1

ping time, download speed, upload speed

5g - primary
1, 43.92, 34.93
1, 60.44, 48.84
1, 65.8, 51.82
1, 56.5, 48.67
1, 60.67, 51.61

2.4g - primary
1, 32.63, 32.53
1, 49.3, 33.92
1, 44.85, 23.27
1, 40.19, 33.38
1, 58.69, 30.95
1, 37.07, 32.14

2.4g- bridge
1, 39.21, 22.05
1, 31.09, 21.7
1, 22.55, 20.02

Sunday, January 7, 2018

Cryptography course - Basic key exchange

Online Trusted third party(TTP)
If A,B want to communicate, Eavesdropper sees E (K_a, "A,B" || K_ab) and E (K_b, "A,B" || K_ab)
Similar mechanism is basis of Kerberos system.
It's only safe against evaesdropping attacks not against an active attacker.
TTP should always be online.

Active attack
 - If a money transaction is taking place, what if the attacker just replays the request? Since the key is still the same, another transaction would take place.

Key question
 - can we design key exchange protocols without online TTPs?
- Yes! Public key cryptography.

Merkle puzzles
- Quadratic gap between participants and attackers (2^32 vs 2^64)
 - This looks like the best we can achieve from symmetric block ciphers

Diffie Hellman protocol
 - exponential gap
- Fix a large prime p (e.g. 600 digits), Fix an integer g in {1,...,p}
- Alice: choose random a in {1,...,p-1}
- Bob: choose random b in {1,...,p-1}
- A <- g^a mod p
- B <- g^b mod p
- Alice sends A to Bob and she sends B back
- Now the shared key is : g^ab mod p since both of them can compute it.

How hard is DH function mod p?
- suppose Prime p is n bits long
- best known algo (GNFS): run time exp (O(n^1/3)), so exponential in cube root of n.
- to achieve same security as AES 256 bits, we need modulus size 15360 bits in DH
- but only 512 bits if we use Elliptic curves in place of mod p
- as a result there is slow transition away from (mod p) to elliptic curves

The way we have defined it so far it's insecure against MiTM
Public key encryption

Intro. to Number theory
Z_N = {1,2...N-1} a ring where addition and multiplication mod N can be done.
x.(y+z) = x.y + x.z
For all ints x,y there exist ints a,b s.t. a.x + b.y = gcd(x,y) and a,b can be found efficiently using the extended Euclid alg. For e.g. 2.12 - 1.18 = 6 = gcd(12,18)

If gcd(x,y)=1 we say that x and y are relatively prime.

Modular inversion
Over the rationals, inverse of 2 is 1/2. 
Def: The inverse of x in Z_N is an element y in Z_N s.t. x.y = 1 in Z_N

Lemma: x in Z_N has an inverse iff gcd(x,N) = 1 so Z_N* = set of invertible elements in Z_N = all x s.t. gcd(x,N) = 1

Solving modular linear equations
Solve a.x + b= 0 in Z_N
=> a.x = -b
=> x = -b.a^-1
Find a^-1 in Z_N using extended Euclid. Run time: O(log^2 N)

Fermat's theorem
Let p be a prime. For all x in (Z_p)*: x^(p-1) = 1 in Z_p
Example p=5. 3^4 = 81 = 1 in Z_5

This gives us another way to compute inverses, but less efficient than Euclid
x e (Z_p)* => x.x^(p-2) = 1 => x^(-1) =x x^(p-2) in Z_p

but it doesn't work for non primes.
Run time O(log^3 N)
So, less general and less efficient.

Application of Fermat's theorem - Generating random primes
Let's say we want to generate a large random prime
say, prime p of length 1024 bits (i.e. p ~ 2^1024)

Step 1: choose a random integer p e [2^1024, 2^1025 -1]
Step 2: test if 2^(p-1) = 1 in Z_p
If so, output p and stop. Else goto Step 1.

For 1024 bits prime Pr[p not prime] < 2^-60

We can also get False primes through this method.

Structure of (Z_p)*
It's a cyclic group, there exists g e (Z_p)* {1,g,g^2,...g^p-2} = (Z_p)*

g is called a generator of (Z_p)*
Not every element is a generator.

Lagrange theorem: ord_p(g) always divides p-1
ord_p(g) = |<g>| = generated group of g

Euler's generalization of Fermat
phi(N) = |(Z_N)*|
phi(12) = |{1,5,7,11}| = 4
Phi(p) = p - 1 where p is prime.

If N = p.q where p,q are prime then phi(N) = N-p-q+1  = (p-1)(q-1)

Euler's theorem - For all x in (Z_N)* x^phi(N) = 1 in Z_N - basis of RSA

Example : 5^phi(12) = 5^4 = 625 = 1 in Z_12

Practice questions:
2^10001 % 11 = 1 (Fermat), since gcd(2,11) = 1 and 11 is prime => 2^(11-1) = 2^10 % 11 = 1 => 2^10001 % 11 = 2^1 % 11 = 2
2^245 % 35 = 1 (Euler's generalization) since gcd(35,2) =1 and 35 is not prime, N = 35 = 7.5, so |phi(N)| = 7-1.5-1 = 24 => 2^24 % 35 = 1 => 2^245 % 35 = 2^5 = 32

Modular e'th root
When does the root exist?

e=2, square roots
x, -x => x^2
If p is an odd prime then gcd(2, p-1) !- 1
In Z_11 * , (1)^2 = 1 (-1)^2 = 1 where -1 = 10 (since mod 11)
similarly 2 and 9 map to 4, 3,8 map to 9 and so on.

x in Z_p is a quadratic residue if it has a square root in Z_p.
p odd prime => the number of Q.R. (Quadratic Residue) in Z_p is (p-1)/2 + 1 , extra 1 is for 0.

Euler's theorem about when does a number have a Q.R.
This theorem is not constructive, i.e. it tells us about existence but not how to construct it.

Arithmetic algorithms
Addition,subraction - linear in n (input size)
Division O(n^2)
Multiplication is naively O(n^2) if inputs are n-bits. Karatsuba's algorithm O(n^1.585)
Best(asymptotic) algo: On(n.logn).but is practical on very large numbers.
But Karatsuba's more practical and most crypto libraries use it.

Modular exponentiation is O(n^3).

Some hard problems
District log base 2 mod p for (1) (Z_p)* for large p, (2) Elliptic curve groups mod p
An application: collision resistance
If H(x,y) = g^x.h^y where g,h are generators of G where G = (Z_p)* for large p the finding collisions of H is as difficult as DLog problem.

Now look at some difficult problems modulo composites(above is modulo prime)

Wednesday, January 3, 2018

Making deleted files unrecoverable in Windows

2 ways:

For C: (similarly for other drives)
1. Download sdelete from here: then sdelete -z C: for a folder (sdelete folder/), for a file (sdelete file)
2. cipher /w:C

Wednesday, December 27, 2017

cryptography course - Authenticated Encryption

Authenticated Encryption
How to secure against tampering.

If message needs integrity but no confidentiality - use MAC
If message needs integrity and confidentiality - use Authenticated Encryption

3 options:
SSL(Mac-then-Encrypt),IPSec(Encrypt-then-MAC),SSH (Encrypt-and-MAC) => IPSec is the best one to provide AE

OCB : a direct construction from a PRP - Efficient in the sense that you don't have to invoke AES(or another block cipher) twice - once each for encryption and MAC
- parallel
But OCB is not widely used and not a standard - primarily due to various patents

AE in real world

Padding Oracle
Attacking non-atomic decryption => 

HKDF - key derivation function from HMAC (Generating multiple keys from one key)
Password based KDF - PBKDF/PKCS

Searching on Encrypted data
Deterministic Encryption - cannot be CPA secure. Solution - pair (k, m) is unique. Same message won't be encrypted by the same key. CBC with fixed IV is not det. CPA secure.
SIV with wide PRP.

Disk Encryption
Encryption cannot expand original text. Sector size fixed.
If 2 sectors have same content, their cipher texts will also be the same. Information will leak.
First, approach - let's use different keys for different sectors.
But even with this approach, user can still change the text and then revert it to find a leakage or pattern.
Tweakable block cipher - where tweak comes from sector number.
XTS tweakable block cipher

Use tweakable encryption when you need many independent PRPs from one key.

Format preserving encryption
Credit card encryption - 

Wednesday, December 13, 2017

Cryptography course - Message integrity

Let's talk about how to ensure integrity rather than confidentiality - for e.g. banner ads.
CRC is not enough. We need a shared key with both parties.
MAC - Message Authentication Codes => S,V
S(k,m) -> t
V(k,m,t) -> 0,1

Popular variations using AES

Truncated PRF is also secure if 1/2^w is negligible where w is the length after truncation.

Encrypted CBC-MAC (ECBC)
Raw CBC which doesn't do the final encryption with a different key.

NMAC (Nested MAC)
Output is in the key space. As opposed to ECBC where output is in X.

In both NMAC and ECBC last encryption step is required else it's insecure.

AES based ECBC is the most popular MAC algo.
AES based ECBC should not be used for more than 2^48 messages.

Message padding
If we append 0s at the end to pad the message, it's risky. Let's a cheque of amount 1 is the message. We pad 0s at the end, which makes it 1000. Now, both 1 and 1000 have the same tag!!
So, padding must be invertible. If m0 != m1, pad(m0) != pad(m1) should hold.

ISO standard
So, pad with 100..00. While removing the pad, keep removing till you get the first 1.
If the message is already a multiple of the block size, add a pad still.

Using CMAC we can avoid padding for messages which are multiple of block sizes.
If the message is multiple of block size, encrypt the last block with K2. If not, pad and encrypt with K1.

Parallel, incremental.

One time MAC - parallel of one time pad for integrity
Carter wegman MAC - build many time MAC from one time MAC

Collision resistance - Merkle Damgard paradigm
Davies meyer compression function.

Timing attacks on MAC verification

Thursday, December 7, 2017

Cryptography course - AES

AES is a subs-perm network not Feistel (in which half the bits remain unchanged in every round). Here all bits change in every round.
Intel Westmere and AMD Bulldozer architectures have special instructions for AES.
AES implementation will have shortest code when tables are not pre computed and vice versa.
So, to transmit AES implementation to browser, just the code is sent and browser pre computes the table.
On AES-128 best known attacks are only 4 times faster than exhaustive search - i.e. 2^126. AES-256 though can be broken in 2^99.

Can we build a PRF from a PRG? Though the ultimate goal is to build PRP.
Answer is yes. It's called GGM PRF.
If we have a PRF, we can plug it in Luby-Rackoff theorem which says that PRF + 3 round Fiestel will give us PRP.
But constructing a PRP like this is very slow in practice, so it's not used.

Any secure PRP is a secure PRF if |X| is sufficiently large. For e.g. |X| for AES is 2^128. 

How to correctly encrypt long messages with block ciphers?
If two parts of the message are same, and the block cipher is not long enough to encrypt the full message, attacker can gain information about the underlying text.
One way to solve it is to use - Deterministic Counter mode.

Sol 1
Randomized Encryption
Given the same PT, output different CT every time due to randomization. But the size of CT increases since the randomness is encoded in the message.

Sol 2
Nonce based Encryption
Message is encrypted using (k, n) and this pair never repeats. n could be public too. For e.g. for HTTP(s) packet counter can be used as n since packets arrive in order.

Cipher block chaining - with random IV
but if IV is predictable, CPA challenge will fail. In SSL/TLS this was a bug.

CBC -with nonce
Another key to encrypt nonce since nonce has to be random.

Randomized counter mode (CTR)
Parallelizable - Unlike CBC

Advantages of CTR over CBC
Requires PRF rather than PRP
Better error bounds
No Padding required

But all these encryptions don't really protect against message tampering. 

Wednesday, November 29, 2017

Cryptography course notes - Block Ciphers

PRP/PRF - Psuedo Random Permutations/Functions and Block Ciphers are the terms which can be used independently.
They map a block of size n to output block of size n. For 3DES, n = 64 bits and k(key size) = 168 bits. For AES, n = 128 bits, k = 128, 192, 256
Key is expanded in round keys which are in turn applied to input. It's parallel in nature.

Key expansion. Round function.

Basic building block - Feistel netwrok - take functions which map n bits to n bits and construct invertible functions which map 2n bits to 2n bits.
DES is 16 round Feistel network. Function is same in all rounds, just that key is different.

Luby Rackoff theorem - 3 round Feistel network gives a secure PRF. Argue that 2 round is not secure.

Breaking DES with exhaustive search
Given 1 m,c pair there is 99.5% probability that a certain key was used.
With 2 pairs, prob. is even higher.
56-bit DES has been broken in 3 months, 3 days, 22 hours. In 7 days with 120 off-the-shelf FPGAs.
With double-DES, it can be broken in 2^63 time (vs 2^56 for single-DES) due to man in the middle attack. For triple-DES it's 2^118. 

DES-X can be used to make DES more secure by doing k1 XOR (E (k2, m XOR k3))

Attacks on the implementation

Side channel attacks
For e.g. if a smart card has a key which is used for encryption/decryption - by observing power consumption you can guess 1) number of cycles (peaks/troughs count) 2) by zooming in on the graph even 0s and 1s can be guessed of the key. 3) Smart card companies try to mask the power but by differential power analysis it can still be broken.

Also, if one core is used for enc/dec, on another core the attack can run which can monitor cache misses since both the cores share the cache.

Fault attacks
Computing errors in the last round expose the secret key k

Linear and Differential attacks
Given many inp/oup pairs, can we recover key in time less than 2^56 (Exhaustive search).
Linear cryptoanalysis -
If you XOR subset of message bits with subset of CT resulting value should be equal to subset of original key with prob = 1/2
But if it's 1/2 + epsilon then there is some bias.
In case of DES epsilon is non-trivial which breaks DES in 2 POW 42. Turns out the 5th S-box (S5) has some linearity which results in 2 POW 42 attack.

Quantum attacks:
Generic search problem:
Given f:X->{0,1}
Goal : find x e X s.t. f(x) = 1

Classical computer will take O(|X|) time. Quantum computing can help us to solve this problem faster, in O(|X| pow 1/2). A quantum computer can break DES in 2 POW 28 as opposed to 2 POW 56. And AES in 2 POW 64. These days 2 pow 64 is considered insecure. 

Blog Archive