An example that is not Semantic Security

We suppose that there is an algorithm A that can always deduce LSB of plaintext from ciphertext. We describe the statement as below formula,

LSB (m) = A (c) 
where 
m is a plaintext
c is a ciphertext
A is the algorithm.

It is an example of the Stanford on-line course, Cryptography I, that describes the stream cipher is not semantically secure.

I explain it in my way as the below picture.

An adversary input m0 and m1 to attach the challenger. There are two worlds of the challenger, World 0 and World 1.

In World 0, the challenger picks m0 and returns c = E (k, m0).
In World 1, the challenger picks m1 and returns c = E (k, m1).

The adversary accepts the c and determines if the c comes from m0 or m1. The adversary defines an algorithm B,

If LSB (mb) == 1, then output "1"

For World 0, the probability of the algorithm that outputs "1" is 0.
Pr [EXP(0) = "1"] = 0

For World 1, the probability of the algorithm that outputs "1" is 1.
Pr [EXP(1) = "1"] = 1

ADV [B, E] = |0 - 1| = 1

It means that the adversary can fully distinguish the c comes from m0 or m1.

The adversary can also use another algorithm B2 to distinguish the c.

If LSB (mb) == 0, then output "0"

Pr [EXP (0) = "1"] = 1
Pr [EXP (1) = "0"] = 0
ADV [B2, E] = |1 - 0| = 1

-Count

The 1-bit PRP is not a secure PRF

The Stanford on-line course, Cryptography I, describes that the following 1-bit PRP is secure,

X = {0, 1}
E: E x X ---> Y
E (k, x) = x xor k
E is a secure PRP

but it is not a secure PRF. How do we explain it? We can imagine that there are two worlds as the below picture, World 0 and Word 1. World 0 is for 1-bit PRP and World 1 is for truly random function.

There are two permutations in World 0. and four functions in World 1. An attacker wants to find an algorithm to distinguish both worlds.

The attacker uses the algorithm A1,
if f(0) == f(1), then output "1"

The attacker inputs x = 0 and x = 1 to distinguish both worlds.

For World 0, the probability of the algorithm that outputs "1" is 0.
Pr [EXP(0) = 1] = 0

For World 1, the probability of the algorithm that outputs "1" is 1/2.
Pr [EXP(1) = 1] = 1/2

Adv [A1, E] = |0 - 1/2| = 1/2

The attacker uses the algorithm A2,
if f(0) != f(1), then output "1"

The attacker inputs x = 0 and x = 1 to distinguish both worlds. We just use the below formulas.

Pr [EXP(0) = 1] = 1
Pr [EXP(1) = 1] = 1/2
Adv [A2, E] = |1 - 1/2| = 1/2

In conclusion, no matter the attacker uses A1 or A2, the Adv is always 1/2. It means that the attacker can easily distinguish both worlds, 1-bit PRP and truly random function. Therefore the 1-bit PRP is not a secure PRF.

-Count

Why is 1-bit PRP with XOR secure?

The Stanford on-line course, Cryptography I, describes that the following 1-bit PRP is secure.

X = {0, 1}
E: K x X ---> Y
E(k, x) = x xor k
E is a secure PRP

How do we understand it?

Permutation.

A function f: X ---> Y is a permutation means that it is an one-to-one and onto function, and the domain X is equal to the codomain Y.

Pseudo Random Permutation (PRP)

The function E(k, .) is a PRP means that E(k, .) is a permutation and k is a random variable that defines the permutation.

Secure PRP.

The function E(k, .) is a Secure PRP means that it is indistinguishable from a random function in the set of all permutations.

The above 1-bit PRP is secure.

We can imagine that there are two worlds as the below picture, World 0 and Word 1. World 0 is for 1-bit PRP and World 1 is for truly random permutation for the 1-bit.

There are two permutations in World 0 and they are same in World 1. We can say that World 0 is equals World 1. An adversary cannot distinguish both worlds.  Therefore the 1-bit PRP is secure.

-Count

Is double AES more secure?

Is double AES more secure? The answer is YES, but it is not much more secure as you expect.

Do you remember why to use 3DES instead of double DES? The reason is double DES can be compromised with meet-in-the-middle-attack.

Time taken for DES with a 56 bits key size is 2^56. How about double DES with different keys? The time take is not expected to 2^112. It is smaller than 2^63 by using meet-in-the middle-attack, that is developed by Merkle and Hellman.

The result can be applied to any block ciphers including AES. For example, time taken for AES with a 128 bits key size is 2^128. Time taken with double AES with different keys is much smaller than 2^256. It is,

Time = 2^128 x log (2^128) + 2^128 x log (2^128) << 2^256

-Count

Why is 2-round Feistel not Secure PRP?

The theorem, Luby-Rackoff'85, describes that, 3-round Feistel is a secure PRP if f is a secure PRF. I have many questions,

1. Why 3-round? 
2. Is 2-round a secure PRP?
3. Is 1-round a secure PRP? 

Now, we use the below picture to check if 1-round Feistel a secure PRP?

We specify 

Funcs [M, C] as set of all functions from M to C.

We specify 

F as the 1-round Feistel.

F: K x M ---> C, 

where 

K is a key space,

M = {0,1}^(2n), is a message space,

C = {0,1}^(2n), is a cipher text space.

f1 is a secure PRP

f1: K x {0,1}^n ---> {0,1}^n

After we input a message

m = R || L, 

,the output cipher text is

c = L1 || R.

When we check the cipher text and the message, we can say that the cipher text is produced by F because the left block of the cipher text is R that comes from the right block of the message. Therefore F is distinguishable from the Funcs. F is not sure PRP.

OK, Let's use the below picture to check if 2-round Feistel is secure PRP.

We specify 

F as the 2-round Feistel.

F: K x M ---> C, 

where 

K is a key space,

M = {0,1}^(2n), is a message space,

C = {0,1}^(2n), is a cipher text space.

f1 and f2 are secure PRP

After we input two message, ma and mb,

the output cipher text are ca, cb.

ma = R || La ---> ca = R2a1 || La1
mb = R || Lb ---> cb = R2b1 || Lb1

We observe that.

La1 = La xor f1(R)
Lb1 = Lb xor f1(R)

La1 xor Lb1 = La xor Lb ---- (formula 1)

When we check the two cipher texts and the two messages with this formula 1, we can say that they are produced by F. Therefore F is distinguishable from the Funcs. F is not sure PRP.

 -GY

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

Use a computer to emulate devices of temperature connecting to AWS IoT

I modified the sample basicPubSub of the project aws-iot-device-sdk-python to develop the Python tool AwsIotPythonTest.py to test AWS IoT service.

My project is AwsIotPythonTest.

We can use the tool to emulate 3 connected devices, two sensors of temperature and one monitor. They are run in PC environment by opening 3 consoles. When running, they connect to AWS IoT service and exchange temperature information via MQTT as below picture.

The Sensor 1 and Sensor 2 devices connect to AWS IoT Service and publish temperature information to the service. The Monitor device connects to the service and subscribe it to receive temperature information coming from sensor devices. The publish/subscribe model follows MQTT. I described the idea of emulator in the project AwsIotPythonTest in details.

-Count