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

Private Keys in Blockchain Transactions

If we can answer the question "Where is private keys?" for a secure feature, we almost understand the security framework. How about the private keys in blockchain transactions?

A private key is used to derive a public key and to make a signature in a transaction. A wallet program can use the same private key for each transaction but it is not secure because it is easy to trace a user's behavior of transaction and it has a risk of being compromised.

Bitcoin Developer Guide states: "For both privacy and security, we encourage you to build your applications to avoid public key reuse and, when possible, to discourage users from reusing address."

Please image that there are 1000 different private keys generated if we have 1000 transactions. Do we need to store the all private keys? I consider the answer is No because the private key is useless after the transaction is finished. Therefore a wallet program can clean the unused private keys if it can generate a unique private key for each transaction.

-Count

The padding problem between Java Security and Windows CryptoAPI

If we use Windows CryptoAPI to encrypt plaintext with RSA to get ciphertext, the Java BadPaddingException exception happens when we use Java Security to decrypt the ciphertext with RSA.

We suppose that it is padding problem between Java Security and Windows CryptoAPI, but Windows CryptoAPI default uses PKCS1Padding in RSA, and our Java program uses Cipher.getInstance("RSA/ECB/PKCS1Padding"). Therefore both padding algorithms are same. Where is the problem?

The problem is, ciphertext encrypted by Windows CryptoAPI is little-endian, but Java Security consider ciphertext is big-endian. We can reverse ciphertext before calling RSA decrypt of Java Security.

-Count

Apple Watch Wrist Detection

If we enable password in Apple Watch, it will be locked when we take it off at 15th second in default. There are two cases of the lock scenario as the below picture.

Case A: The watch is initially worn and locked.

• 0 sec: A user inputs password to unlock the watch.
• 0 - 15 sec: The unlocked period is 15 seconds in default. The period can be specified on the watch. If the user clicks the watch in the period, the period will be reset.
• 15+ sec: If the watch is worn, it is keep being unlocked (Case A), otherwise it locks itself (Case A.1).

Case B: The watch is not initially worn and locked.

• 0 sec: A user inputs password to unlock the watch.
• 15 sec: The watch locks itself at the time.

How does Apple Watch detects wrist? I suppose the mechanism is run by photodiode sensors not by G-sensor. There are two rules of wrist detection.

1. Primary rule: Sensors detect distance between watch and wrist via infrared LEDs.
2. Secondary rule: Sensors detect lighting change to determine locking.

The primary rule is easy to be proved. How about the secondary rule? I uses the 3 methods to cheat Apple Watch to keep wearing (unlocking) status.

1. Shake a paper below the watch.
2. Put watch on an iPad that is playing video.
3. Put watch on a glass and shake a paper below the glass. 

Photo 1

Photo 2

Photo 3

-Count

Connect MacBook to Ubuntu in Gen8 via AFP

The steps, referred to the page, of connecting MacBook to Ubuntu in Gen8 via AFP are as below.

1. Install AFP Server in Ubuntu
>sudo apt-get install netatalk
>sudo apt-get install avahi-daemon

2. Specify the config of Avahi
>sudo gedit /etc/avahi/services/afpd.service

<?xml version="1.0" standalone='no'?><!--*-nxml-*-->
<!DOCTYPE service-group SYSTEM "avahi-service.dtd">
<service-group>

<name replace-wildcards="yes">%h</name>

<service>
<type>_afpovertcp._tcp</type>
<port>548</port>
</service>

<service>
<type>_device-info._tcp</type><port>0</port>
<txt-record>model=Xserve</txt-record>
</service>

</service-group>

3. Specify the shared directories.
>sudo gedit /etc/netatalk/AppleVolumes.default

/home/your_home "your_home"
/media/your_hdd "your_hdd"

4. Restart the service

sudo service netatalk restart
sudo service avahi-daemon restart

5. Open MacOS Finder to connect the AFP server.

Input the IP address of the server. For example,

afp://192.168.11.10

Then the shared directories will display. For example.

your_home
your_hdd 

-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