CMAC and CCM

We are confused about CMAC and CCM. Especially what does mean AES-CMAC or AES-CCM? They are defined in the following specfications.

• NIST 800-38B CMAC
• NIST 800-38C CCM
• RFC 4493 AES-CMAC
• RFC 3610 Counter with CBC-MAC (CCM)

After I read them. I made conclusion that:

• CMAC is used for authentication.
• CCM is used for authentication and confidentiality.
• CBC-MAC, CMAC, and CCM have some differences.

I draw the below picture to explain their relationships.

Terminology

• MAC - Message Authentication Code
• HMAC - Hash-Based MAC
• CBC-MAC - Cipher Block Chaining MAC
• CMAC - Cipher-Based MAC
• CBC - Cipher Block Chaining
• CCM - Counter with CBC-MAC
• ECB - Electronic Code Book

MAC is a short piece of information used to authetnicate a message. There are two types of MAC, hash function based MAC and cipher based MAC.

The implementations of  hash function based MAC, abbreviated HMAC, are HMAC-MD5, HMAC-SHA1, and HMAC-SHA256. The postfix (e.g -MDB, -SHA1, or -SHA256)  is the hash function used in the MAC.

CBC-MAC is a cipher based MAC. CMAC is variation of CBC-MAC that has security deficiencies. AES-CMAC and TDEA CMAC are implementation of CMAC.

ECB, CBC, and CCM are block cipher modes. CCM is an adaption of CBC and is counter with CBC-MAC. AES-CCM is only one implementation of CCM.

In conclusion,

1. AES-CMAC is a MAC, implemented by AES algorithm for authentication. 
2. AES-CCM is an AES cipher with CCM mode for authenticatino and confidentiality.

-Count

Why cannot S-box of DES cipher be linear?

We cannot specify any S-box in DES cipher. One of the rules to choice of S-box is that, it cannot be linear. How do we understand it? Below is my explanation, but I'm not sure it is correct.

The Stanford on-line course, Cryptography I, describes that, if S-box is chosen as linear, the DES cipher would be linear.

DES(k, m) = B x |m  |= c    (statement 1)
                |k1 |
                |k2 |
                |.  |
                |.  |
                |.  |
                |k16|

where:
|m| = |c| = 64 (bits)
|ki| = 48 (bits)
B is a 64x832 matrix.

The course describes that, "You just need 832 input output pairs, and you'll be able recover the entire secret key." How to explain the description? We can use a simple example:

Lets
B is 2 x 4 matrix.
|m| = |c| = |k| = 2 (bits)

We transform the statement 1 as below.

|b1 b2 b3 b4| x |m1| = |c1|
|b5 b6 b7 b8|   |m2|   |c2|
                |k1|
                |k2|

We give the below statement.

b1m1 xor b2m2 xor b3k1 xor b4k2 = c1    (statement 2)
b5m1 xor b6m2 xor b7k1 xor b8k2 = c2    (statement 3) 

We assume that, we don't know any b and any k, but we know the input m and output c.

For statement 2, the number of unknown variables is 4. They are,
b1, b2, b3k1, b4k2.

For statement 3, the number of unknown variables is 4. They are,
b5, b6, b7k1, b8k2.

Total number of unknown variables is 8. Therefore we need 8 equations to derive all values of b and k.

Because,

|m| = |c| = 2

Each input/output pair has 2 equations. That is why we need 8/2 = 4 pairs of  input/output to derive all values of b and k.

-Count

Cross Platform Random Bitmap Generator

I created a project, RandomBitmap,  in the below GitHub.
https://github.com/CountChu/RandomBitmap

There are two purposes of the project:

1. to check if random variables generated by a specified platform (e.g., Windows, Android) are secure.
2. to check if a file is random or has patterns by observing the black-white bitmap file transformed by the file.

This idea comes from the page, Pseudo-Random vs. True Random. The author uses PHP to transform random numbers to a bitmap. I separated the transformation into two Python programs, GenRandom.py and BinToImg.py because I want to test random number generators on different platforms as the below picture.

GenRandom, is a set of tools written by different languages on different platforms, calls a specified random generator to produce random numbers. These numbers will be saved in a file. The different languages are specified from the below reasons:

• Python is a cross platform language so that I can use GenRandom.py to test Windows, Linux, and MAC.
• For Android device, Java is a candidate language. Therefore I'll create a Java version tool, GenRandom.java, to test Android's random generator. 
• For security IC or UEFI environment, C is a candidate language. The C version tool is named GenRandom.c.
• For Chrome Browser's Native Client written by C/C++,  the tool will be named GenRandom.c. I'll use it to test random generators of OpenSSL and LIBC in Native Client environment.
• C# is the first candidate language in, I'll have a C# version, GenRandom.cs, to test Windows CNG.

RandomGenerator.py provides different random generators that are consumed by GenRandom.py:

• rg1() is a Python default random generator that is random.randint().
• rg2() is a random generator comes from the page.

BinToImg.py is a python tool that transforms data in a file into an PNG image file with black-white pixels so that we can observe the image to check if these numbers are random. The tool can be used independently. For example, we input any type of file in the tool to generate an picture with black-white pixels to check if the file is randomly.

I use the both tools to verify if the MAC random generator is secure.

>python GenRandom.py Random.bin

>python BinToImg.py Random.bin

I use the tool BinToImg.py to check a PDF file. We can find some patterns in the below picture.

>python BinToImg.py One.pdf

-Count

If PRG is secure, PRG is unpredictable

Below is the definition of secure PRG.




Below is the definition of predictable PRG.



How do we proof the below theorem?

PRG is secure => PRG is unpredictable

The previous page proofed it by:

PRG is predictable => PRG is not secure

This pare proofs it in a direct way. Before proofing it, I  draw the below picture, where G is PRG, to understand the definition of secure PRG and unpredictable PRG.



We keep the picture in our mind and use simple formulas to proof it.

The fact is that G is secure:

Adv = |Pr [A (G) = 1] - Pr [A (r) = 1]| <= e (e is epsilon)

Because the statement, that is proofed by the page, is also true.

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

Therefore

Pr [A (G) = 1] <= 1/2 + e

We can transfer the statement from A to B for the definition of A that is a statistical test.

Pr [B (G|1...i+1) = G|i+1] <= 1/2 + e

Therefore G is unpredictable.

-Count

Use Advantage to Define Secure PRG

Below is the Advantage definition:




We use Advantage to define Secure PRG as below:



How do we understand the definition of secure PRG with Advantage? We can draw the below picture to describe the definition.




-Count

Understand that, One Time Pad (OTP) has perfect secrecy

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

K = M = C = {0, 1}^n
c = E(k, m) = k xor m
m = D(k, c) = k xor c
where c in C, k in K, m in M

OTP has perfect secrecy because |k| = |m|.

How do we understand the statement?

We can give a simple example.

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

Below is the table of the OTP cipher.



We focus on c = 11 to guess the probability of m where k is a uniform random variable.

Pr[E(k, 00) = 11] = 1/4 
Pr[E(k, 01) = 11] = 1/4 
Pr[E(k, 10) = 11] = 1/4 
Pr[E(k, 11) = 11] = 1/4 

It describes that the OTP is perfect secrecy because

Pr[E(k, m) = c] = 1/4, for all c in C,
where k is a uniform random variable.


-Count

Perfect Secrecy ==> Key Length >= Message Length

Here is a theorem:

If a cipher (E, D) over (K, M, C) is a perfect secrecy,
then k length >= m length, where k is K, and m is M.

How do we proof it?

We transfer the theorem as below.

If k length < m length, the cipher is not a perfect secrecy.

Therefore we just give an example to explain the theorem.

Lets

K = {0, 1}^2 = {00, 01, 10, 11}
M = {0, 1}^3 = {000, 001, ..., 111}
C = {0, 1}^3 = {000, 001, ..., 111}

Obviously k length = 2 and m length = 3

Give a table.

  M   K    C
---  --  ---
000  00  000
001  01  001
010  10  010
011  11  011
100      100
101      101
110      110
111      111

I consider it may be easy to explain the theorem if specifying elements in the table as numeric symbols.

M K C
- - -
0 0 0
1 1 1
2 2 2
3 3 3
4   4
5   5
6   6
7   7

We understand the meaning of "Perfect Secrecy". We focus c=0 and try to guess the message.

We know that

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

We can design  a cipher (E, D) for c=0 and for all k is k as below.

D = {(k,c,m)} 

where

k c m 
- - -
0 0 0
1 0 1
2 0 2
3 0 3

There is a problem that the number of keys is not enough to cover another m values:4, 5, 6, 7.

Because k is a uniform random number, we expand the probability as below.

Pr[E(k,0)=0] = 1/4
Pr[E(k,1)=0] = 1/4

Pr[E(k,2)=0] = 1/4

Pr[E(k,3)=0] = 1/4
Pr[E(k,4)=0] = 0

Pr[E(k,5)=0] = 0

Pr[E(k,6)=0] = 0

Pr[E(k,7)=0] = 0

It describes that the cipher is not perfect secrecy because

Pr[E(k,m)=0] = 1/4 or 0, for all k is in K.

Let me explain it in English. If we know the ciphertext c is 0 and the cipher algorithm, (E, D), we can guess the message, m:

1. The event, m=4, 5, 6, or 7, doesn't happen.
2. The probability of the event, m=0, 1, 2, 3, is 1/4.

-Count

How does a software engineer understand "Perfect Secrecy"?

I consider, a definition in mathematic formula format is like source code written with a computer language. Mathematic formula is written for mathematician. Source code is written for a computer.

The way to understand a mathematic definition is the same as the way to understand a source code. How do we understand source code? I believe any experienced software engineers know the trick. I also believe we can understand some mathematic definition in the same way for understanding source code.

Don't worry, we have enough ability to understand some mathematic definition. For example, below is the definition of "perfect secrecy":



The definition is a formula that is compressed from many sentences. How do we understand it? A better way is try to decompress the formula to get original sentences and understand them.

We know that,

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

I explain the perfect secrecy that:

1. I know the ciphertext, c.
2. I know the encryption and decryption algorithms, E and D.
3. It is hard to guess the key, k, because it is a uniform random variable. The probability of successfully guessing is 1/|K|.
4. It is hard to get a correct m by decrypting c with a guessed key because the probability of getting the correct m is the same constant for all k in K.

Our purpose is to translate the four sentences into a formal definition with a formula.

First, try to translate the above sentences in a informal formula.

E(k?, m?) = c

It means:

• I know the ciphertext, c, and encryption algorithm, E.
• I don't know k and m.

Translate it into another informal formula.

E(k, m?) = c
where k is a uniform random variable on K

Because m is deterministic by D(k, c) = m, we translate it again.

E(k, mi) = c
where k is a uniform random variable on K

and i = 0, 1, ..., |M|

Finally we add the 4th sentence to complete the formal definition of "perfect secrecy".

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

where k is a uniform random variable on K

and i = 0, 1, ..., |M|

-Count

Negligible and non-negligible - A better explanation

The page, Negligible and non-negligible, explains what means

lambda >= lambda d 

in the definition of negligible and non-negligible,



by using the below formula,

g(x) = 2^x - x^d >= 0

to draw the below picture,



Actually, we can using another formula to draw a more beautiful picture. We derive the formula as below:

We except that:

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

We define that:

g(x) = (x^d) / (2^x) <= 1

And draw the below picture for d = 2, 3, 4.




Please look at the red lines:

For d = 2, g(x) <= 1, if x >= 4
For d = 3, g(x) <= 1, if x >= 9.94...
For d = 4, g(x) <= 1, if x >= 16

The values, 4, 9.94..., and 16 are of "lambda d".

-Count

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

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

Why XOR can be a symmetric encryption and decryption?

Why does Bluetooth security use XOR as an operation of symmetric encryption and decryption? The formula of symmetric as follows.

C = Enc (P, K)
P = Dec (C, K)

Where
C is cypher text.
P is plain text.
Enc is a symmetric encryption algorithm.
Dec is a symmetric decryption algorithm
K is a key of the encryption and decryption.

The true table of XOR is as follows.

A B X
-----
0 0 0
0 1 1
1 0 1
1 1 0

A XOR B = C
C XOR B = (A XOR B) XOR B =  A XOR (B XOR B) = A XOR 0 = A

Therefore we got the formula.
A XOR B = C
C XOR B = A

Lets rename A to P (plain text), and B to K (key), and keep C (cipher).
P XOR K = C
C XOR K = P

Transform it.
C = XOR (P, K)
P = XOR (C, K)

We proof that XOR can be a symmetric encryption and decryption.

-Count

Symmetric/Asymmetric Encryption and Hashing

I use the following simple formula to distinguish among symmetric/asymmetric encryption and hashing.

C = Enc (P, K1)
P = Dec (C, K2)

Where
C is cypher text,
P is plain text,
Enc is an encryption algorithm,
Dec is an decryption algorithm,
K1 is a key for encryption.
K2 is a key for decryption.

If K1 == K2, then Enc and Dec are symmetric encryption (e.g., AES).

If K1 != K2, then Enc and Dec are asymmetric encryption (e.g., RSA).

If Enc is an one-way function (there is not a Dec to recover C to P), we can call it hashing (e.g., SHA).