Use BinToImg.py to analyze UEFI BIOS

We can use BinToImg.py to analyze UEFI BIOS. Below is the input files.

• BIOS.rom - A capsule file built by EDK build system.
• SPI0.bin - A binary file dumped from SPI ROM 0 after first booting.
• SPI1.bin - A binary file dumped from SPI ROM 1 after first booting.

The tool BinToImg.py transfers a byte to 8 pixels with black-white color. For example,

Byte = 55h = 01010101

Pixels 
  = 1 -> 0 -> 1 -> 0 -> 1 -> 0 ->1 -> 0

  = black, white, black, white, black, white, black, white

We use the below commands to generate PNG files with black-white bit pixels from the input files.

python3 BinToImg.py -w 6000 BIOS.rom
python3 BinToImg.py -w 6000 SPI0.bin

python3 BinToImg.py -w 6000 SPI1.bin

The option -w 6000 means that the tool generates an image of which width is 6000 pixels.

Below are the generated PNG files. I consider any BIOS engineer know what happens by observing  these images, especially for BIOS.rom.png and SPI1.bin.png.

BIOS.rom.png


SPI1.bin.png


SPI0.bin.png


-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