Uniform Random Variable v.s. Identify Function.

We know that a random variable r.v. is actually a function. Can we confirm that a uniform random variable must be an identity 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

We define two random variables, f1 and f2, with same X and Y as below.

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

f1: X ---> Y
f2: X ---> Y

Obviously, f1 and f2 are uniform r.v. because

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

but f2(x) is not an identity function because 

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

However, we prefer to select the identity function, f1(x), as an uniform random variable.

So far, I answer the question myself because I have not found the answer on Internet yet. 

-Count

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. 

-Count

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.

-Count

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

B(r)=1, 

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.)

Obviously,

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.


-Count

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 in the below table:

       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

Be careful that:
The "0" in the table means nearby zero.
The "1" in the table means nearby one.

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

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

The formula is equal 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. Therefore we cannot find any statistical test to determine r is not random.

For Case 3, the PRG, G, 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,

Pr[A(G(k))=1] 

is not exactly equals to one.

-Count

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.

-Count

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. We specify f(x) as below, that is an example,

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

The f(x) is 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.

g(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, g(x) = 2^x - x >= 0, 
           if x >= x1. x1 is any real number.

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

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

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

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

-Count

XOR encryption is a randomized algorithm

We exactly describe that One Time Pad (OTP) encryption, that uses XOR operation, is a randomized algorithm.

Below is the definition of Randomized Algorithms:

A cipher (E, D) over (K, M, C) is OTP, so that

c = E (k, m) = k xor m

K = M = C = {0, 1}^n

For the definition of Randomized Algorithms, if k and c are uniform random variables, the OTP encryption, E, is a randomized algorithm. 

The k, selected in K, must be a uniform random variable for the reason,

Why must the key of the encryption be random?

Why is the c, calculated by the OTP encryption, also a uniform random variables? The question is same to proof the below formula that is the definition of uniform random variable.

Pr [c = c0] = 1 / |C|

Please remember that a random variable is really a function. So transform the formula to display the function E (k, m0),

Pr [c = c0] = 

Pr [E (k, m0) = c0] =

OTP encryption uses XOR operation.

Pr [k xor m0 = c0] = 

Pr [k = c0 xor m0] =

Pr [k = k0] = 1 / |K|

because there is only one k0  that encrypts m0 to generate c0. 

Pr [c = c0] = 1 / |K| = 1 / |C|  

because |K| = |C| = 2^n

We proof that the OTP encryption is a randomized algorithm.

-Count

My Proof for Shannon Theorem

In this topic, I use my informal way to proof Shannon Theorem. Yes, it is informal but easy to understand the theorem. I also proof that the substitute cipher is not perfect secrecy.

Shannon Theorem:

A cipher (E, D) over (K, M, C) has perfect secrecy
=>
|K| >= |M|

The theorem is identical the below statement.

|K| <= |M|
=>
A cipher doesn't have perfect secrecy

My proof of the theorem is to give an example.

Lets

K = {0, 1}, M = C = {0, 1}^2

We define the encryption algorithm E as below.

if k = 0,

 m  c
-----
00 00
01 01
10 10
11 11

if k = 1,

 m  c
-----
00 01
01 10
10 11
11 10

We use the below formula to verify if the cipher is perfect secrecy. It it is perfect secrecy,

Pr [E (k, m) = c] = constant

I use the both pairs

(m, c) = (00, 00) or (00, 10)

to verify it.

Pr [E (k, 00) = 00] = (# of keys) / |K| = 1/2, 

Only one key, k=0, exists.

Pr [E (k, 00) = 10] = (# of keys) / |K| = 0/2 = 0,

We cannot find a key to make the equation.

Pr [E (k, m) = c] = 1/2 or 0

Obviously, it is not constant. Therefore the cipher is not perfect secrecy. We proof it. Actually, the cipher is called substitute cipher.

-Count

Why must the key of the encryption be random?

When I learn the Stanford online course, Cryptography I, I ask my self the question: "Why must the key of the encryption be random?"

The encryption algorithm is written below.

C = E (M, K) 

where
C is ciphertext,
M is plaintext message,
K is a key,
E is an encryption algorithm.

We use XOR algorithm as encryption algorithm.

C = M XOR K.

The purpose is to make C an uniform random variable even though M is not, and specify:

Pr [M=0] = m0

Pr [M=1] = m1
m0 + m1 = 1 and 
m1 <> m2

Pr [K=0] = k0

Pr [K=1] = k1

k0 + k1 = 1

If K is not an uniform random variable, then

k0 <> k1

Below is the table of the equation, C = M XOR K.

M	K	C	Probability
0	0	0	m0 * k0
0	1	1	m0 * k1
1	0	1	m1 * k0
1	1	0	m1 * k1

We can calculate that:

Pr [C=0] = m0 * k0 + m1 * k1 <> 1/2
Pr [C=1] = m0 * k1 + m1 * k0 <> 1/2

Thus C is not a uniform random variable.

I draw the below picture to explain why the two inequalities are right.

m0 * k0 + m1 * k1 <> 1/2
m0 * k1 + m1 * k0 <> 1/2



When I see the two areas m0 * k0 and m1 * k1, I FEEL that m0 * k0 + m1 * k1 <> 1/2.

In conclusion, if we want to build a ciphertext randomly, the key must be random.

We also make sure that XOR encryption is a randomized algorithm because if the key is a uniform random variable, the output ciphertext  is also a uniform random variable.

The next page explain why XOR encryption is a randomized algorithm.

-Count