Monday, September 26, 2016

Uniform Random Variable v.s. Identify Function.

We know that a random variable r.v. is actually a function. Can we say a uniform random variable must be an identify function? I don't think so. I also have not found that the identify function is a part of the definition of the uniform r.v. yet. Let me explain why.

Below is the r.v. definition:

X: U ---> V

Because r.v.  is also a function, I like write it as below only for easily thinking for me.

f: X ---> Y

The uniform r.v. is defined as below.

f: X ---> Y, Y = X
Pr [f(x) = y] = 1 / |X|

Below is the definition of identity function.

f: X ---> X
f(x) = x for all x is X

Let's draw two tables for the uniform r.v..

We define X and Y as below.

X = {0, 1, 2, 3}
Y = {0, 1, 2, 3}

Table 1

x f(x)
- ----
0 0
1 1
2 2
3 3

Table 2

x f(x)
- ----
0 3
1 2
2 1
3 0

Table 1 and Table 2 show that both f(x) are uniform r.v. because

Pr [f(x) = y] = 1 / |X|

but obviously f(x) of Table 2 is not an identity function because 

f(x) <> x for all x is X.

However, we prefer to select an identity function for the uniform r.v., f(x).

So far, I answer the question myself because I have not found the answer on Internet yet otherwise I always be confused on uniform r.v. and identify function. 


Saturday, September 24, 2016

Summarize of Apple Watch unlocking Mac

The macOS Sierra was released on 9/20 this year. One of the most interesting feature, I think, is Apple Watch unlocking Mac. I tried the feature on 9/21, Chinese time. I'm summarizing it as below.

  • Apple devices unlock model:
    • Unlocked iPhone unlocks Apple Watch.
    • Unlocked Apple Watch unlocks MacBook.
  • Enable the unlocking feature in MacBook.
    • Connect to Internet
    • Setup Two-Factor Authentication via iCloud account (Apple ID).
    • Specify the unlocked password for the MacBook that is different from iCloud account password.
  • The unlock conditions:
    • Apple Watch is unlocked.
    • Direct Wi-Fi (It is not necessary to connect to Internet or to Wi-Fi station)and Bluetooth must be enabled. 
    • Apple Watch is near to MacBook.
    • Press any key on MacBook or open the cover to unlock it. 


How does a companion device verify the service HMAC comes from a Windows device?

The Windows Companion Device Framework (CDF) is a Windows framework that defines a security protocol between a Windows device and a companion device (e.g., Android phone.) so that a companion device can unlock a Windows device.

The question is, how does a companion device verify the service HMAC comes from a Windows device?

The answer was not provided by the old version of CDF site page, but I found, the answer appeared in the latest updated version, 9/19/2016.

In the Authentication protocol section, it describes:

Validate Service HMAC = HMAC (authentication key, service nonce||device nonce||session nonce).

I write the process of verification as below for coding better.
  • The companion device accepts data from the Windows device.
    • (HmacSrv, NonceSrv, NonceDk, NonceSk)
  • It verifies the data by the formula.
    • HmacSrv2 = HMAC-SHA256 (AuthKey, NonceSrv||NonceDk||NonceSk)
  • It checks if HmacSrv equals to HmacSrv2.
    • If yes, continue to unlock the Windows device.
Another question is why does the companion device need to verify HmacSrv? The reason is to make sure that data comes from the windows device that was trusted by the companion device because both has been registered each other in the registration process.


Tuesday, September 20, 2016

If PRG is predictable, PRG is insecure.

The Stanford on-line course, Cryptography I, proof that "If PRG is secure, PRG is unpredictable". The statement is equal to "If PRG is predictable, PRG is insecure".

Below is the definition of "predictable".

The steps of the proof are below.

(I'm sorry I directly copy the pictures from the course because it is hard to write the math statements by typing. If the original author concern it, please let me know and I'll remove them.)

The question is, why is the statement true?

Pr[B(r)=1] = 1/2 

The statement in the probability


is equal to

A(r(i...i)) = r(i+1)

Let's calculate the probability.

A(r(i...i)) r(i+1)
----------- ------
          0      0
          0      1
          1      0
          1      1

We specify that

Pr[A=0] = p0
Pr[A=1] = p1
where p0 + p1 = 1

(We cannot say p0 = p1 = 1/2.)


Pr[r(i+1) = 0] = 1/2
Pr[r(i+1) = 1] = 1/2

because r is a uniform random variable.

Pr [A = r(i+1)] = Pr[A=0] * Pr[r(i+1)=0] + Pr[A=1] * Pr[r(i+1)=1]
= p0 * 1/2 + p1 * 1/2 = (p0 + p1) / 2 = 1/2.

because the i+1 bit is independent of the first i bits.


What does mean "Advantage"

When I learn the Stanford online course, Cryptography I, I am confused on the Advantage definition:

The purpose is let Adv[A,G] be "negligible" . I can consider it is nearby zero. There are 4 cases of the Adv:

       Pr[A(G(k))=1] Pr[A(r)=1] Adv[A,G]
------ ------------- ---------- --------
Case 1             0          0        0
Case 2             1          0        1
Case 3             0          1        1
Case 4             1          1        0

We don't care about case 1 and case 2 where

Pr[A(r)=1] = 0. 

The formula is equals to

Pr[A(r)=0] = 1, 

that means the statistical test A determines the r is not random. Actually r is a uniform random variable on {0,1}^n, and we don't want to select the such statistical test to determine r is not random.

For Case 3, the PRG is bad because it is not random determined by  the statistical test, A.

Therefore only Case 4 are what we concern. Why is the Adv "negligible" in Case 4? I consider the reason is,


is not exactly equals to one.


Friday, September 16, 2016

Why has Apple removed PPTP VPN from iOS 10 and macOS Sierra 10.12?

When I upgraded my iPad and iPhone to iOS 10, my MacBook to macOS, I found that PPTP VPN was removed? Why did Apple decide to do it? I think the reason is, PPTP VPN is not secure. Why? The Stanford on-line course, Cryptography I, answers the question.

PPTP VPN uses the same key for encryption in both directions between client and server.

In the client side, the messages, m1, m2 and m3, are encrypted by G(k) before sending to the server. G is PRG.

CiphertextClient = [m1 || m2 || m3] xor G(k)

In the server side, the message, s1, s2, and s3, are encrypted by G(k) before sending to the client.

CiphertextServer = [s1 || s2 || s3] xor G(k)

If the ciphertext of client and server are intercepted, a hacker can break the ciphertext without knowing G(k) because,

CiphertextClient xor CiphertextServer = 
[m1 || m2 || m3] xor [s1 || s2 || s3]

Even though client and server use stream cipher, it is still not secure because client and server share the same G(k).

That is also why TLS uses different key for encryption in both client and server.


Thursday, September 15, 2016

Negligible and non-negligible

The Stanford online course, Cryptography I, describes:

What does mean lambda >= lambda d?

Because the epsilon is a function, we can write the lambda as x and the epsilon as f(x) for easy understanding. The f(x), that is an exponential function, is defined below.

f(x) = 1 / (2^x)

The f(x) is also negligible because,

f(x) = 1 / (2^x) <= 1 / (x^d), 
for all d and large enough x. (statement 1)

Why do we consider the statement 1 is true? I am not a mathematician. I prefer to use enough examples and tools to observe and understand problem. The tool, the iPad App Quick Graph+, is used to draw curves of the below functions.

f(x) = 1 / (2^x)
f(x) = 1 / x
f(x) = 1 / (x^2)
f(x) = 1 / (x^3)
f(x) = 1 / (x^4)

It is hard to verify the statement 1 with the picture because the curves are close to each other when x is large. Therefore we transfer the statement 1 as below.

f(x) = 2^x - x^d >= 0, 
for all d and an enough large x. (statement 2)

We give examples, d = 1, 2, 3, 4. The below picture contains the curves.

If we zoom in the picture, we can find an interesting thing.

The statement 2 is true for an enough large x.

For d = 1, f(x) = 2^x - x >= 0, 
           if x >= x1. x1 is any real number.

For d = 2, f(x) = 2^x - x^2 >= 0, 
           if x >= x2. x2 is 16

For d = 3, f(x) = 2^x - x^3 >= 0, 
           if x >= x3. x3 is about 9.94

For d = 4, f(x) = 2^x - x^4 >= 0, 
           if x >= x4. x4 is 4

Because x is also called lambda, that is what means "lambda >= lambda d".