시간과 공간 그리고 진실의 방

At CloudFlare, we’re committed to making sure the encrypted web is available to everyone, even those with older browsers. At the same time, we want to make sure that as many people as possible are using the most modern and secure encryption available to them. Improving the cryptography used by the majority requires a coordinated effort between the organizations building web browsers and API clients and those working on web services like CloudFlare. Cryptography is a two-way street. Even if we support the most secure cryptographic algorithms for our customers, web visitors won’t get the benefit unless their web client supports the same algorithms.

In this blog post we explore the history of one widely used cryptographic mode that continues to cause problems: cipher block chaining (CBC). We’ll explain why CBC has proven difficult to use safely, and how recent trends in the adoption of secure ciphers by web clients have helped reduce the web’s reliance on this technology. From CloudFlare’s own data, we’ve seen the percentage of web clients that support safer cipher modes (such as AEAD) rise from under 50% to over 70% in six months, a good sign for the Internet.

What’s in a block cipher?

Ciphers are usually grouped into two categories: stream ciphers and block ciphers. Stream ciphers encrypt data on a bit-by-bit basis. Plaintext and ciphertext are always the same length. Examples of pure stream ciphers are RC4 and ChaCha20. Although RC4 is no longer considered secure, we can still rely on ChaCha20 as a secure stream cipher for use on the web, but it was only recently standardized by the IETF and therefore does not have broad adoption.

Unlike stream ciphers, which can encrypt data of any size, block ciphers can only encrypt data in "blocks" of a fixed size. Examples of block ciphers are DES (8-byte blocks) and AES (16-byte blocks). To encrypt data that is less than one block long using a block cipher, you have several options. You can either turn the block cipher into a stream cipher (using something called counter mode, more on this later), or you can include extra bytes as padding to align the data to the block size. If the data is longer than one block, then the data needs to be split into multiple blocks that are encrypted separately. This splitting process is where things get tricky.

The naïve approach to encrypting data larger than the block size is called Electronic Code Book (ECB) mode. In ECB mode, you split your data into chunks that match the cipher’s block size and then encrypt each block with the same key. ECB turns out to be a very bad way to encrypt most kinds of data: if the data you are encrypting has redundant portions, say an image with many pixels of the same color, you end up with the "Tux" problem (demonstrated below). If two blocks have the same value, they will be encrypted to the same value. This property lets an attacker know which plaintext blocks match by looking at the ciphertext blocks.

For example, here’s what a high-resolution version of Linux’s "Tux" looks when encrypted in ECB mode:

Image from Filippo Valsorda’s blog

The fact that identical plaintext blocks are encrypted to identical ciphertext blocks gives an unwanted structure to encrypted data that reveals information about the plaintext.

One solution to this is to "chain" blocks together by taking the output of one encryption and mixing it into the input for the next block. There are several block cipher modes, but the one that was originally standardized in SSL (and continues to be used in TLS) is Cipher Block Chaining (CBC). In CBC, the plaintext of one block is combined with the ciphertext of the previous block using the exclusive OR operation (XOR). The first block is XOR’d with a randomly generated initialization vector (IV).

Decryption works by XORing the previous block of ciphertext (or the IV) into the output of the decryption.

CBC has some nice properties. The ciphertext produced by a block cipher is encrypted, so it (hopefully) looks random. In CBC, you’re mixing this random looking encrypted data into the plaintext, making it very unlikely that there will be patterns in the output. Another advantage is that decryption can be done in parallel to speed things up. However, CBC has proven to be more trouble than expected when used in the context of the HTTPS and the web.

How records are encrypted in TLS

TLS provides both encryption—via a cipher—and integrity—via a message authentication code (MAC). When SSL was originally designed, one open question was: should we authenticate the plaintext data, or should we encrypt and then authenticate the encrypted data? This is sometimes stated as MAC-then-encrypt or encrypt-then-MAC? They chose MAC-then-encrypt (encrypt the authenticated data) which has since proven to be the less than ideal choice.

In cryptographic protocol design, leaving some bytes unauthenticated can lead to unexpected weaknesses (this is known as the Cryptographic Doom Principle). When encrypting data using a block cipher mode like CBC, the last block needs to be padded with extra bytes to align the data to the block size. In TLS, this padding comes after the MAC. (There is a TLS extension, described in RFC 7366, that enables encrypt-then-MAC, but it’s rarely implemented.)

A TLS record has the following format. Each one has an 8-byte sequence number that is stored and incremented on each new one. The encrypted part of a request needs to add up to a multiple of 16 bytes, but for the purposes of this post, let’s assume that this length is 64 bytes (4 blocks).

In TLS, valid padding looks like a number preceded by that number of copies of itself. So, if the number is 0x00, it’s repeated 0 times:

If the number is 0x02, it’s repeated 0x02 times:

To decode a block, decrypt the entire message, look at the last byte, remove it, and remove that many bytes of padding. This gives you the location of the HMAC.

To compute the MAC, take the sequence number, the 5-byte header, and the message, then HMAC them using the shared integrity key.

Padding oracle

The problem with this construction is that it is susceptible to a technique called the padding oracle attack. This attack was first reported against TLS by Serge Vaudenay in 2002. A padding oracle is a way for an attacker with the ability to modify ciphertext sent to a server to extract the value of the plaintext.

Attackers don’t have to be an ISP or a government to get in the middle of requests. If they are on the same local network as their victim they can use a technique called ARP spoofing. By tricking the victim’s machine to forward data to the attacker’s machine instead of the router, they can read, modify and measure the time it takes for every encrypted message sent from the browser to the server. By injecting JavaScript into an unencrypted website the client is visiting, they can get the browser to repeatedly send requests to a target HTTPS site. The

1. AES 암호 알고리즘(Advanced Encryption Standard)이란?

고급 암호화 표준(Advanced Encryption Standard)이라고 불리는 AES 암호 알고리즘은 DES를 대체한 암호 알고리즘이며 암호화와 복호화 과정에서 동일한 키를 사용하는 대칭 키 알고리즘이다.

DES에 비해서 키 사이즈가 자유롭다. 즉, 가변 길이의 블록과 가변 길이의 키 사용이 가능하다.(128bit, 192bit, 256bit)

또한 속도와 코드 효율성 면에서 효율적이다.(즉, 디자인을 간단하게 하였다는 것이다.)

그리고 DES와 차이점은 페이스텔 구조가 아닌 SPN 구조를 이용한다.

SPN 구조

SPN은 Substitution - Permutation Network의 약자로

말 그대로 Substitution Layer와 Permuation Layer를 이용하여 Confusion과 Diffusion을 만족시켜주는 암호다.

아래 그림은 SPN 구조를 나타내고 있다.

장점은 Feistel 구조와 반대로 병렬연산이 가능하고

단점은 복호화시 별도의 복호화 모듈을 구현해줘야 한다는 것이다.

SPN 구조 :: http://reinliebe.tistory.com/76

Feistel 구조와 SPN 구조의 차이

Feistel 구조는 암복호화 과정에서 역함수가 필요 없다는 장점이 있지만 구현시 스왑(Swap)단계 때문에 연산량이 많이 소요 되며 암호에 사용되는 라운드 함수를 안전하게 설계해야 한다는 단점이 있다. 

대표적인 암호로는 DES가 있으며 Single DES는 안전성 문제로 현재 사용하고 있지 않다.

SPN 구조는 암복호화 과정에서 역함수가 필요하도록 설계되어야 한다는 단점이 있지만 중간에 비트의 이동없이 한번에 암복호화가 가능하기 때문에 페스탈 구조에 비해 효율적으로 설계할 수 있다. 대표적인 암호로는 AES가 있으며 AES는 현재 널리 상용되고 있다.

https://ko.wikipedia.org/wiki/%EB%B8%94%EB%A1%9D_%EC%95%94%ED%98%B8

2. AES 암호 알고리즘 용어 설명

Cipher Key

Round Key들을 생성하기 위해 Key Expansion Routine에 의해 사용되어지는 암호키이다.

Key Expansion (= Key Schedule)

Cipher Key로부터 Round Key들을 생성하기 위해 사용되는 Routine이다.

Word

4 bytes의 배열이나 또는 한 entity로서 다뤄지는 32bits의 한 Group이다.

S-Box

Byte 값의 대체를 수행하기 위해 Key Expansion Routine과 여러 SubBytes 변환에서 사용되는 비선형 대칭표다.

파라미터

Nb : State를 구성하는 열의 수(Nb = 4)

Nk : 암호키를 구성하는 32-bit words의 수(Nk = 4, 6, 8)

Nr : 라운드의 수(Nr = 10, 12, 14)

State

암호화 중간 단계의 결과물로서 (4, Nb)의 이차원 행렬로 표현된다.(Nb는 128, 192, 256에서 4로 고정이다.)

3. AES 암호화 과정

AES 암호화 과정은 위의 과정이 전부이다.

즉, round를 거쳐 암호화가 이루어지는데 좀더 자세한 내용은 위의 그림을 참조하면 된다.

여기서 이 코드를 보면 마지막 Nr 단계에서는 MixColumns를 실행하지 않는데 

AES 암호 알고리즘에서 마지막 라운드에서는 MixColumn 단계가 없다는 것을 의미한다.

즉, 키가 128비트 였다면 Nr은 10이 되고 마지막 라운드인 10단계에서는 MixColumn이 없다는 것이다.

라운드 과정을 좀 더 자세히 살펴보자.

1. SubBytes 과정

바로 예를 들어 설명해보려 한다.

예를 들어 128 비트 입력이 16진수로 32 30 31 32 31 30 36 30 30 32 4B 4B 57 4B 4B 57와 같으면 이것의 state 상태는 다음과 같다.

(이는 2012106002kkwkkw를 키로 두었을 때 16진수로 변환한 값이다.)

",="" sans-serif;font-size:13px"="" style="border: none; border-collapse: collapse;">

32

31

30

57

30

30

32

4B

31

36

4B

4B

32

30

4B

57

<AES 상태의 예>

이때 1바이트 값이 9a였다면 S-Box에 의해 b8로 변한다는 것이다.

여기서 4B는 B3으로 치환된다.

2. ShiftRows 과정

상태 행렬의 행에 따른 왼쪽 방향의 Cyclic 회전을 수행한다. 

첫 번째 행은 회전되지 않고, 

두 번째 행은 1byte, 

세 번째 행은 2bytes, 

네 번째 행은 3bytes 만큼씩 왼쪽으로 Cyclic 회전한다. 

3. MixColumns 과정

State의 각 Column에 대해서 아래와 같이 행렬 곱셈을 수행한다. 

식에서 각 Symbol은 유한체 GF(28) 상의 요소이며 0 혹은 1의 계수를 갖는 7차 이하의 다항식으로 표현 가능하다. 

그리고 요소간 곱셈은 기약 다항식, x^8+x^4+x^3+x+1을 법으로 하는 다항식 곱셈이다. 

마지막 라운드는 MixColumn을 하지 않는다.

이 부분은 난해한 부분이므로 아 이런거구나 정도로 느끼면 될 듯합니다.

4. AddRoundKey 과정

실제 encryption은 이 과정에서 수행되는데, state내의 각각의 byte들이 각 RoundKey와 XOR연산 되어진다.

RoundKey는 key expansion schedule에 따라 key로부터 유도되어진다.

4. AES 암호 알고리즘 예제 코드 및 실습

AES 암호화 소스코드

AES 복호화 소스코드

2012106002kkwkkw를 2, 16진수로 표현하면 아래와 같다.

2진수 표현

00110010 00110000 00110001 00110010 00110001 00110000 00110110 00110000 00110000 00110010 01001011 01001011 01010111 01001011 01001011 01010111

16진수 표현

32 30 31 32 31 30 36 30 30 32 4B 4B 57 4B 4B 57

이를 키로 이용하여 암호화를 해보고자 한다.

평문은 ABCDEFGHIJKLMNOP를 이용한다.

복호화시에도 2012106002kkwkkw를 키로 이용하여 32 30 31 32 31 30 36 30 30 32 4B 4B 57 4B 4B 57로 변환하고

암호화된 결과값을 넣으면 원본으로 복호화 할 수 있음을 알 수 있다.

Advanced Encryption Standard (AES) is a specification for the encryption of electronic data established by the U.S National Institute of Standards and Technology (NIST) in 2001. AES is widely used today as it is a much stronger than DES and triple DES despite being harder to implement.

Points to remember

• AES is a block cipher.
• The key size can be 128/192/256 bits.
• Encrypts data in blocks of 128 bits each.

That means it takes 128 bits as input and outputs 128 bits of encrypted cipher text as output. AES relies on substitution-permutation network principle which means it is performed using a series of linked operations which involves replacing and shuffling of the input data.

Working of the cipher :
AES performs operations on bytes of data rather than in bits. Since the block size is 128 bits, the cipher processes 128 bits (or 16 bytes) of the input data at a time.

The number of rounds depends on the key length as follows :

• 128 bit key – 10 rounds
• 192 bit key – 12 rounds
• 256 bit key – 14 rounds

Creation of Round keys :
A Key Schedule algorithm is used to calculate all the round keys from the key. So the initial key is used to create many different round keys which will be used in the corresponding round of the encryption.

Encryption :
AES considers each block as a 16 byte (4 byte x 4 byte = 128 ) grid in a column major arrangement.

[ b0 | b4 | b8 | b12 |
| b1 | b5 | b9 | b13 |
| b2 | b6 | b10| b14 |
| b3 | b7 | b11| b15 ]

Each round comprises of 4 steps :

• SubBytes
• ShiftRows
• MixColumns
• Add Round Key

The last round doesn’t have the MixColumns round.

The SubBytes does the substitution and ShiftRows and MixColumns performs the permutation in the algorithm.

SubBytes  :
This step implements the substitution.

In this step each byte is substituted by another byte. Its performed using a lookup table also called the S-box. This substitution is done in a way that a byte is never substituted by itself and also not substituted by another byte which is a compliment of the current byte. The result of this step is a 16 byte (4 x 4 ) matrix like before.

The next two steps implement the permutation.

ShiftRows :
This step is just as it sounds. Each row is shifted a particular number of times.

• The first row is not shifted
• The second row is shifted once to the left.
• The third row is shifted twice to the left.
• The fourth row is shifted thrice to the left.

(A left circular shift is performed.)

[ b0  | b1  | b2  | b3  ]         [ b0  | b1  | b2  | b3  ]
| b4  | b5  | b6  | b7  |    ->   | b5  | b6  | b7  | b4  |
| b8  | b9  | b10 | b11 |         | b10 | b11 | b8  | b9  |
[ b12 | b13 | b14 | b15 ]         [ b15 | b12 | b13 | b14 ]

MixColumns :
This step is basically a matrix multiplication. Each column is multiplied with a specific matrix and thus the position of each byte in the column is changed as a result.

This step is skipped in the last round.

[ c0 ]         [ 2  3  1  1 ]  [ b0 ]
| c1 |  =      | 1  2  3  1 |     | b1 |
| c2 |      | 1  1  2  3 |     | b2 |
[ c3 ]      [ 3  1  1  2 ]     [ b3 ]

Add Round Keys :
Now the resultant output of the previous stage is XOR-ed with the corresponding round key. Here, the 16 bytes is not considered as a grid but just as 128 bits of data.

After all these rounds 128 bits of encrypted data is given back as output. This process is repeated until all the data to be encrypted undergoes this process.

Decryption :
The stages in the rounds can be easily undone as these stages have an opposite to it which when performed reverts the changes.Each 128 blocks goes through the 10,12 or 14 rounds depending on the key size.

The stages of each round in decryption is as follows :

• Add round key
• Inverse MixColumns
• ShiftRows
• Inverse SubByte

The decryption process is the encryption process done in reverse so i will explain the steps with notable differences.

Inverse MixColumns :
 This step is similar to the MixColumns step in encryption, but differs in the matrix used to carry out the operation.

[ b0 ]         [ 14  11  13  9  ]  [ c0 ]
| b1 |  =      | 9   14  11  13 |     | c1 |
| b2 |      | 13  9   14  11 |     | c2 |
[ b3 ]         [ 11  13  9   14 ]     [ c3 ]

Inverse SubBytes :
Inverse S-box is used as a lookup table and using which the bytes are substituted during decryption.

Applications:

AES is widely used in many applications which require secure data storage and transmission. Some common use cases include:

• Wireless security: AES is used in securing wireless networks, such as Wi-Fi networks, to ensure data confidentiality and prevent unauthorized access.
• Database Encryption: AES can be applied to encrypt sensitive data stored in databases. This helps protect personal information, financial records, and other confidential data from unauthorized access in case of a data breach.
• Secure communications: AES is widely used in protocols like such as internet communications, email, instant messaging, and voice/video calls.It ensures that the data remains confidential.
• Data storage: AES is used to encrypt sensitive data stored on hard drives, USB drives, and other storage media, protecting it from unauthorized access in case of loss or theft.
• Virtual Private Networks (VPNs): AES is commonly used in VPN protocols to secure the communication between a user’s device and a remote server. It ensures that data sent and received through the VPN remains private and cannot be deciphered by eavesdroppers.
• Secure Storage of Passwords: AES encryption is commonly employed to store passwords securely. Instead of storing plaintext passwords, the encrypted version is stored. This adds an extra layer of security and protects user credentials in case of unauthorized access to the storage.
• File and Disk Encryption: AES is used to encrypt files and folders on computers, external storage devices, and cloud storage. It protects sensitive data stored on devices or during data transfer to prevent unauthorized access.