일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 개성국밥
- JanusWebRTC
- PersistenceContext
- pytest
- PytestPluginManager
- preemption #
- vfr video
- 헥사고날아키텍처 #육각형아키텍처 #유스케이스
- kotlin
- tolerated
- VARCHAR (1)
- addhooks
- JanusWebRTCServer
- 겨울 부산
- 티스토리챌린지
- 깡돼후
- table not found
- 코루틴 빌더
- taint
- JanusWebRTCGateway
- JanusGateway
- python
- 오블완
- terminal
- 자원부족
- Value too long for column
- mp4fpsmod
- 코루틴 컨텍스트
- Spring Batch
- 달인막창
너와 나의 스토리
[컴퓨터 보안] AES 개념과 구조 본문
왜 Block Cipher에 대해 Finite Field를 이용하는가?
- AES를 구성하는 함수들
- Substitution
- Transposition (permutation)
- Multiple rounds
- Simple bit operations (XOR 같은 )
- Bit randomizion effect
- input에 대해 output이 랜덤하게 나오는 것 같은 느낌을 줌
- Field multiplication이나 Field inversion이 이런 randomizion effect 역할을 함
- 덧셈은 그다니 randomizion 효과가 없음
- 덧셈 반복해도 효과 x
- 곱셈이나 역연산은 복잡도를 증가시킬 수 있음
Binary Field의 근거
- 우리는 편의성과 구현 효율성을 위해 낭비되는 비트 패턴이 없는, 주어진 수의 비트에 정확히 맞는 정수로 작업을 하고 싶다.
- 즉, (mod $2^n$)을 해서 0부터 ($2^n$-1)까지 쓰려고 한다.
- 하지만 $2^n$을 modulus로 쓰게 되면, 이런 modular연산에 대해서는 field를 구성할 수 없다.
- 즉, 이런 수(예: $2^3$=8)를 정수 그대로 쓸 수는 없고, 이거를 binary field로 바꿔서, 모든 원소들을 숫자가 아닌 계수가 2진수인 다항식으로 표현하면 잘 연산할 수 있다.
- GF($2^n$)에 속하는 모든 다항식은 n-bit로 표현할 수 있다.
AES에 대한 Finite Field Arithmetic
- Advanced Encryption Standard(AES)를 위해 우리는 GF($2^8$)를 사용한다.
- 모든 연산은 8-bit bytes 단위이다.
- finite field GF($2^8$)를 쓰기 때문에, irreducible polynomial이 필요하다.
- irreducible polynomial: $x^8 + x^4 + x^3 + x + 1$
- binary field는 (mod 2)에 대한 연산을 하는 것이다.
- 예를 들어, $x^2±1$는 irreducible polynomial이 아니다.
- $x^2 + 2x + 1$ = $(x+1)^2$로 나타낼 수 있기 때문
- (mod 2)에서는 양수와 음수가 동일하게 작동하기 때문에 $x^2+1$=$x^2-1$이다.
- 예를 들어, $x^2±1$는 irreducible polynomial이 아니다.
AES
-> DES에서 key의 길이가 짧아서 생기는 안전성 문제를 해결하기 위해 나온 방법
AES의 구조
- plaintext, ciphertext, intermediate data 모두 4x4 matrix of bytes 구조를 가짐
- 파라미터로 들어오는 key size는 128, 192, 256 bits이다.
- 셋 중 하나 선택해서 사용하면 되는데, key 길이가 길어지면 안전해지지만 연산 속도는 느려지게 된다.
- SPN(Substitution-permutation network)
- 하나의 round에서 4개의 연산이 이루어진다.
- Permutation: ShiftRows
- Substitution: SubBytes / MixColumns / AddRoundKey
- AES는 복호화할 때, 암호화 과정을 역으로 올라간다. 이를 위해 모든 연산은 역연산이 존재한다.
- 하나의 round에서 4개의 연산이 이루어진다.
AES 파라미터
* 1 byte = 8 bits
* 1 word = 4 bytes
- key size는 128, 192, 256 bits로 3가지.
- Plaintext의 Block size는 128-bytes로 항상 고정
- key 길이가 길수록 round 수가 많아짐 -> Subkey(RoundKey) 수도 많아짐 (하나의 size는 똑같고 개수만 많아짐)
- (#subkey) = (#round) +1
AES Encryption Process
- 44 words의 subkey가 필요하다.
- state 하나는 4 words이다(16 bytes)
- 이게 10 round일 때, (각 round에 하나씩) + (final state)해서 11개가 있으므로 총 44 words가 된다.
- w[0]~w[43]
- DES는 '절반은 유지, 절반은 업데이트'하면서 매 round를 진행했었다.
- 순방향으로 복호화를 진행하기 위해서
- DES 설명
- 하지만 AES는 SPN 방식으로 전부를 업데이트한다.
- 역방향으로 복호화가 진행됨
AES에서 사용되는 4개의 stage
- Substitute bytes - S-box를 이용해서 byte끼리의 대치를 수행
- ShiftRows - 간단한 permutation
- MixColumns - GF($2^8$)를 사용하며 행렬을 사용하여 업데이트.
- AddRoundKey - bitwise XOR
* Encryption의 마지막 round에는 'Mix columns' 단계가 빠져있다.
-> 구현상의 편의성을 위한 것으로, 안정성에는 문제가 없는 수준이다.
1. SubBytes
SubBytes
: byte 단위로 치환
S-box
: 각 byte를 대치시키는 규칙을 정해 놓은 것
*1
: 각 칸은 1byte(8 bits)이다. 이를 4 bits씩 잘라서 S-box의 x값, y값으로 사용하여 대치할 값을 찾는다.
ex)
<Encryption>
(0, 0) -> 63
<Decryption>
(6,3) -> 00
S-box를 사용하는 이유
- input과 output의 상관관계를 줄임 -> 공격하기 힘들어짐
- 어떻게 상관관계를 줄일 수 있을까?
- input에 대해 linear하지 않은 수학적 함수를 사용하여 output을 낸다.
- '곱셈에 대한 역원'을 사용할 수 있다.
2. Shift Rows
- 입력의 하나의 열이 출력의 모든 열에 영향을 끼치게 됨
3. Mix Columns
- 각 열이 행렬 곱 연산을 통해 새로운 값을 가지게 됨
4. AddRoundKey
- state의 128 bits가 round key의 128 bits와 XOR 된다.
AES의 중요 포인트!
- 입력의 일부분이 출력의 여러 부분에 분산해서 영향을 미치게 한다.
- 입출력 사이 관계가 자명하게 드러나지 않도록 한다. Not linear하게 (복잡스~)
AES Key Expansion
- (w[0]~w[3]), (w[4]~w[7]), ... 들이 각각 subkey이다.
- $w_4 =w_0$ XOR $g(w_3)$
- $RC_j$ -> 어떤 상수
왜 Key Expansion을 사용하는가?
- xor(substitution), shift(transposition) 연산을 통해 공격에 강함
- round마다 달라지는 상수 값(RC)을 사용해서 규칙성을 없앰
- 이렇게 하면, 공격자가 key의 일부를 알거나, 어떤 round의 key를 알아도 다른 round의 key를 알기 힘들다.
- cipher key의 diffusion이 round key에 적용이 된다.
- diffusion: 한 bit가 다른 여러 곳에 영향을 줌 (확산)
- 한 round key의 일부 비트만 바뀌어도 다른 round key들에 영향을 주게 됨.
- 충분히 nonlinearity 하다
- 특정 bit를 알아서 연립방정식을 하더라도 답을 쉽게 얻을 수 없음
bit 하나만 달라져도
- 맨 처음 bit 하지만 다르게 넣어도, 2 round부터 64 bits에 가깝게 변화한다.
- 많이 바뀔수록 좋은 거 아닌가?
- 우리는 최대한 randomize하려고 한다.
- 총 128 bits에서 절반인 64 bits에 가깝게 변해야 랜덤하다고 할 수 있다.
출처:
- [Cryptography and Network Security: Principles and Practices]
'Computer Security' 카테고리의 다른 글
[컴퓨터 보안] 암호모듈 검증제도, 한국표준블록암호, SEED/ARIA/LEA (0) | 2020.10.25 |
---|---|
Block Cipher Operation - ECB/CBC/CFB/OFB/CTR (0) | 2020.10.25 |
Ch4. Block Ciphers and the Data Encryption Standard(DES) (0) | 2020.10.24 |
[컴퓨터 보안] Classical Encryption Techniques (2) | 2020.10.23 |
Group, Finite Fields, Polynomial GCD, 다항식을 bit string으로 계산 (0) | 2020.10.23 |