Symmetric Key Crypto
1) Stream cipher: one-time pad 와 유사하다.
- 정해진 input 이 있는 것이 아니라 들어오는 bit를 받는다 -> 스트리밍 서비스
- one-time pad 와 달리 짧은 키를 key generator에 주고, 동일한 key를 이용하여 key generator가 key stream을 생성한다.
- Plaintext 5 bit xor key stream 5bit
2) Block cipher: Codebook 방식과 유사하다.
- paintext가 들어오면 그에 맞는 다른 값으로 암호화한다.
Stream Ciphers
- 실시간 환경에서 유용하다.
- 전보다 사용하는 곳이 적어짐
1) A5/1
- 3개의 LFSR을 이용한다. (X: 19 bits, Y: 22 bits, Z:23bits)
- Key는 64bits (x, y, z 다 더하면 64)
- bit 단위로 동작한다.
- 연산 방법: maj(0,1,0) = 0 and maj(1,1,0) = 1
- x 8자리, y 10자리, z 10자리를 검사하여 0과 1 중 뭐가 많으지 체크하여 결정 (major)
- 제일 마지막 비트를 xor 한 값이 key stream 값이다.
1. 64bits 를 각 레지스터 크기에 맞게 나눈다.
2. x 8자리, y 10자리, z 10자리를 검사한다. -> 1, 0, 0 이다.
3. maj(1,0,0) = 1 이므로 1이었던 레지스터들은 shift-right 연산을 수행해야 한다. 아직 하지 말고...
4. shift 연산을 하기 전에 레지스터 각 step을 진행한다. (x는 13,16,17,18 xor 연산, y는 20,21 자리 xor 연산, z는 7,20,21,22 자리 xor 연산)
5. 그리고 X, Y는 shift-right 진행한다. (맞겠지???)
6. Key Stream bit는 레지스터 마지막 비트들을 xor 연산한 결과이다. X와 Z는 shift 연산을 수행했으므로 마지막 비트가 각각 0이 되고, Y는 shift 연산을 수행하지 않았기 때문에 1이 된다. 0 xor 1 xor 0 = 1이다.
- Shift register를 이용한 알고리즘의 특징
1. 하드웨어로 구현하기 쉽고, 소프트웨어로 구현하기 어렵다.
2. 과거에 인기 있었지만 요즘은 사용이 줄었다.
2) RC4
- Byte 단위 연산
- 테이블에 0~255까지 수들이 한번씩 나오는데 섞여있다.
- 하나씩 뽑아서 쓰는데 뽑은 바이트 값이 Key stream이 된다.
연산방법이해해보려고했으나어렵다...
아무튼 Stream Ciphers 정리
- 과거에 많이 사용했다.
- 하드웨어에 효율적이다.
- 오늘날은 프로세서가 매우 빨라서 소프트웨어 기반 암호화를 사용한다.
- Stream Ciphers의 미래는 과장해서 거의 없다고 한다.
Block Cipher
- input이 들어오면 블록 단위로 쪼개서 암호화를 한다.
- round function: 여러 라운드를 거치는데 round마다 핵심이 되는 함수
Feistel Cipher
- block cihper의 대표 형태 (알고리즘 X)
- Plaintext를 두 개로 나눈다.
- 오른쪽 단은 그대로 다음 round의 왼쪽 값으로
- 왼쪽 값은 [F] 에서 나온 값 (오른쪽 값과 K를 이용한!)과 XOR 해서 다음 round의 오른쪽 값이 된다. 식으로 정리하면 아래와 같다.
- 최종으로 나오는 값이 cipher text block이 된다.
1) DES (Data Encryption Standard)
- block cipher의 대표적인 알고리즘
- Feister cipher 형태
- input, output block: 64bit
- key: 56bit
- 총 16 rounds
- 각 round 마다 변형되는 48bit key를 생성한다. (subkey)
- DES의 핵심 요소: S-Boxes
전체적인 구조
- 노란색 부분이 subkey 생성
한 라운드의 구조
이제 F 내부를 자세히 보자!
1. E table
- input: 32 bits
- output: 48 bits
- 즉, 확장을 하는 것이다.
위의 그림을 보면 안에 그려진 박스에는 1~32까지 숫자가 순서대로 배치되어 있다. 이것이 input. 그리고 양 끝단 비트들을 추가해줌으로써 테이블을 확장한다.
2. S-box
- DES의 핵심! 안전성을 확보해준다.
- 정해진 S-box 표준을 이용한다.
- 방법: 48bit를 6bit씩 쪼개서 순서대로 S1, S2,... 를 이용한다.
- 예시
- 6bit: 1 1 0 0 1 0 이라면, 1 (1 0 0 1 ) 0 이렇게 분류를 한다.
- 1 0 0 1은 col을 결정하는데, 1001은 9니까 s-box의 9번 col
- 남은 10은 row를 결정하는데 10은 2니까 s-box의 2번 row
- 정해진 값은 12이고 출력값은 2진수 1100이다.
- 이렇게 쭉 하면 32bit가 출력된다.
Subkey
- subkey는 48bit
- 매 라운드마다 바뀐다.
- 처음 입력 key 값에 따라 결정된다.
DES의 문제점
- DES의 key space는 2^56이다.
- key space가 크니까 ㄱㅊ겠지~ 하고 1970년에는 그랬다.
- 하지만 이제는 컴퓨팅 파워가 매우 좋아져서 2^56개의 키를 전수조사 할 수 있게 됐다. 그래서 90년대 말에 DES가 깨진다는 것을 발견했다 ("Deep Crack")
- 그러니까 이제 DES를 활용한 알고리즘을 만들자~
2) Triple DES
- 기존 DES 문제를 해결한다. Key 길이를 늘림!
-
이렇게 DES를 3개 이어서 붙이고 K도 두 개를 쓴다.
-
왜 E D E 과정이지? DES와의 호환성 때문이다. (K1, K2를 같은 값을 주면 무효화 되니까!)
-
왜 3번째에 다시 K1을 사용하지? Key가 길어지면 안전하지만 Key를 관리하기 어려워진다. 112bit만으로도 충분히 안전할 것이라고 판단.
-
요즘 DES는 안 쓰지만 3DES 쓰는 곳은 가끔 있다...
-
왜 DES를 3개 쓸까? 두 개만 쓰면 안 되나?? Double DES 는 Meet-in-the-Middle attack이 가능하다.
Meet-in-the-Middle attack
- 공격자에게 Plaintext, Ciphertext 주어지고 K1, K2를 알아내야 하는 상황이라고 하자.
- P에 K1 후보들을 전부 이용하여 암호화를 한다.
- C에 K2 후보들을 전부 이용하여 복호화를 한다.
- 그렇게 나온 값들을 쭉 펼쳐보면 두 상황에서 나온 값이 겹치는 곳이 있다. 그러면 Key를 알 수 있다. (크기순 sort를 하면 꼭 2^112번 뒤질 필요도 없다.)
의문점: 3DES도 결국 키를 두 개 사용하는 것은 같으니까 키 스페이스 값이 2^112로 똑같은데 왜 이건 안전한 거지? -> DES를 세 개 붙이면 세 개가 겹치는 값을 찾아야 하는데 그게 쉽지 않다.
3) AES (Advanced Encryption Standard)
- DES 대체
- 대표적 대칭키 알고리즘. 지금 대부분 사용한다.
- Not Feistel cipher
- Block size: 128bits
- key length: 128, 192 or 256 bits
- 10~14 rounds
- 교체와 위치 변경에 기반한다.
한 라운드의 구성
- S-box를 이용하여 값을 변경하고 그 이후에 섞는 과정을 한다.
AES 정리
- 128, 192, 256bit 중 하나를 키 길이로 정한다.
- 효과적인 공격이 없다.
- Feistel cipher 형태가 아닌 SP Network 형태이다. (Substitution-Permutation)
- IPsec 와 TLS의 표준
- 소프트웨어와 하드웨어에 효율적이다.
- 1.6Gbit/s 속도로 빠른 편이다.
