[Cryptography] 블럭암호 AES 원리, 안전성

안녕하세요 오늘은 보다 강력한 블럭암호인 AES에 대해서 알아보겠습니다.

https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.197.pdf

 

 

AES란 ?

Advanced Encryption Standard의 약어로 DES를 대체하기 위한 목적으로 개발되었습니다.

DES는 2의 56승 키에 대한 전사적 공격이 가능했기 때문이죠

AES는 Nonlinearity(비선형성)을 가진 암호로, 보수 특성과 취약키가 존재하지 않습니다.

블럭사이즈는 128비트를 채택하고 128, 192, 256비트의 세 가지 종류의 키를 사용합니다.

당연하게도 키 길이에 따라 round 수가 달라지게 됩니다.

 

 

AES 원리

AES의 작동 과정에 대해 자세히 알아보겠습니다.

AES는 키 길이에 따라 round수가 달라집니다

• 128비트의 키 길이 → 10라운드
• 192비트의 키 길이 → 12라운드
• 256비트의 키길이 → 14라운드

비밀키를 입력받으면 키 확장함수를 통해서 키 스케쥴링이 됩니다. (여기서 라운드 결정)

그리고 각 라운드에 해당하는 키를 이용해서 128비트의 암호문 생성되는 것이 암호화 과정입니다.

이 포스팅에서는 키의 128비트의 인풋을 기준으로 설명해보겠습니다.

 

 

키스케쥴

먼저 라운드별로 사용하는 키의 생성과정을 알아보겠습니다.

해당 과정은 Key Expansion이라고도 합니다.

128비트 길의 키를 1칸에 1바이트의 크기를 가진 4x4 행렬의 형태로 나타낼 수 있습니다.

각 열 별로 4칸씩을 기준으로 연산을 수행합니다.

첫 라운드의 각 열을 w0~w3이라고 하겠습니다.

출처 :  https://www.wikiwand.com/en/articles/AES_key_schedule

 

w3을 RotWord 해줍니다. 위의 사진 기준 w3에서 k0(0,3)이 k0(3,3)밑으로 내려가게 됩니다.

즉 RotWord는 하나의 열을 Left Shift 하는 함수입니다.

RotWord를 거친 후, SubWord를 거칩니다. 이때 S-Box를 이용하고, 내용은 substitution 됩니다.

여기까지 거친 것을 subresult라고 해보겠습니다

RCon은 일종의 상수 테이블로 w0, subresult, RCon이 XOR된 것이 첫 라운드의 키 첫 열이 됩니다.

이러한 과정을 여러번 반복하게 되면 키스케쥴링이 됩니다.

키 길이가 128비트이니 최종적으로 10라운드의 키가 생성되겠죠?

 

https://youtu.be/gP4PqVGudtg?si=YisA5yhpjWWmMg6b&t=173

저는 위의 유튜브를 보고 많은 도움을 받았습니다. 꼭 시청하시는 것을 추천드립니다 ㅎㅎ

 

 

암호화 과정

키 스케쥴링에 대해서 알아봤으니 본격적으로 암호화 과정에 대해서 알아보겠습니다.

키스케쥴링과 비슷하게 128비트의 인풋은 16바이트 → 한칸에 1바이트씩 있는 4x4 행렬로 변환됩니다

이것을 State (상태)라고 하겠습니다.

출처  https://blog.naver.com/wnrjsxo/221711255389?photoView=1

크게 살펴보면

128비트의 인풋을 받고 해당 인풋은 Pre-Round를 거칩니다.

아래에서 추가적으로 설명하겠지만 Pre-Round는 AddRoundKey 과정을 이야기합니다.

이후 10개의 라운드를 거치게 됩니다. 각 라운드에서는 이전에 생성한 키 값을 이용하게 됩니다.

마지막 라운드는 조금 다르지만 해당 라운드를 거치고나면 128비트의 암호문이 생성되게 됩니다.

 

 

라운드 진행

한 라운드는 네 가지 레이어로 구성되어 있습니다.

출처  https://www.researchgate.net/figure/The-basic-AES-128-cryptographic-architecture_fig1_230853805

• SubBytes : DES의 S-Box에 해당하며 상태의 한 바이트를 대응되는 S-Box의 한 바이트로 치환합니다 상위 4비트가 Sbox행을 결정하고 하위 4비트가 열을 결정하는 구조입니다. 위에서 AES는 비선형적이라고 했는데 바로 Sbox를 이용하기 때문에 비선형적이라는 특징이 발생되게 됩니다. 이는 선형분석방법으로부터 비교적 안전해진다는 장점이 있습니다

S-Box

• ShiftRows: 상태의 한 행 안에서 바이트 단위로 자리바꿈이 수행되는 함수입니다. 이 역시 바이트 단위로 처리됩니다.
• MixColumns: 상태의 한 열 안에서 혼합이 수행. ShifRows와 함께 분산의 원리를 구현하는 역할을 합니다. 이 과정은 비트 단위로 섞어주는 역할을 합니다.
• AddRoundKey: 비밀키(128/192/256비트)에서 생성된 128비트의 라운드 키와 상태가 XOR됨.

처음 128비트의 input이 들어오면 AddRoundKey과정을 거치며 PreRound가 진행됩니다.

이후 10개의 라운드 진행. 마지막 라운드에서는 MixColumns 과정만 제외하고 나머지 세 과정을 처리합니다.

이렇게 되면 암호화 과정이 끝나게 됩니다.

 

 

AES 복호화 과정

AES 복호화가 가능하려면, 각 과정은 모두 Inversible 해야합니다.

 

InverseAddRoundKey : XOR 연산이기 때문에 두번 적용하면 자연스레 원래 값 얻기 가능

 

InvSubBytes

뒤섞는 과정에서 S-Box를 이용했으니, 해당 S-Box의 Inverse를 이용하면 됩니다.

 

InvShiftRows

나머지 세 행을 옮기는 과정을 통해서 Inverse 할 수 있습니다.

 

InvMixColumns

효율적인 역산을 위해 해당 과정에서는 갈루아 체를 이용합니다.

한칸이 8비트를 넘으면 안되기 때문에 이를 유념하여 기약 다항식을 적용한다고 생각하시면 됩니다.

이 표는 예전에 전공 수업시간에 공부했던 자료인데요, 결과적으로 MixColumns 과정에서는 갈루아체를 이용하고 해당 과정은 ShiftLeft와 XOR 연산으로 이해할 수 있습니다.

즉 해당 과정도 Inverse가 가능한 것이죠

 

 

AES 분석

AddRoundKey를 제외한 다른 세 단계를 살펴보면 키를 사용하지 않는 단계라서 그 자체만으로 뛰어난 보안성이 있다고 할 수 없습니다.

AddRoundKey 단계는 그 자체가 강력하다고 할 순 없지만 다른 세 단계와 작동하면서 비트를 뒤섞는 역할을 합니다.

블록에 AddRoundKey과정에서 XOR을 진행, 이후 다른 세 단계에서 계속해서 블록을 뒤섞는 과정을 통해서 보안을 강화시키는 것이죠.

이 구조는 매우 효과적이라고 평가받습니다.

AES는 또한 1급 비밀에 사용할 수 있도록 승인된 알고리즘 중 최초로 공개되어 있는 알고리즘이기도 합니다.

 

 

참고

https://www.youtube.com/watch?v=gP4PqVGudtg&t=152s

https://ko.wikipedia.org/wiki/고급_암호화_표준

고급 암호화 표준 - 위키백과, 우리 모두의 백과사전