h32j00

오늘은 ​해시 함수​에 대해서 알아보도록 합시다. 요즘 포렌식 공부를 시작하고 있는 데 포렌식에서도 해시값이 쓰여서 더 자세히 읽어 봤던 것 같네요!!

​

해시 함수(hash function)이 쓰이는 곳

: 디지털 서명(digital signature), 공개 키 암호화(public-key encryption), 무결성 검증(integrity verification), 메세지 인증(message authentication), 패스워드 보호(password protection), 키 합의(key agreement) 프로토콜과 기타 여러 암복호화 프로토콜

​

현실 세상에서의 용도

: 클라우드 저장 시스템에서 동일한 파일 식별 및 수정된 파일 검출

: Git에서 저장소 안의 파일들을 식별

: 호스트 기반 침입 탐지 시스템(host-based intrusion detection systems, HIDS)에서 수정된 파일 검출

: 네트워크 기반 침입 탐지 시스템(network-based intrusion detection systems, NIDS)에서 악의적인 자료가 네트워크로 유입되었는지 파악

: 디지털 법의학 분석가(forensic analyst)들은 디지털 증거물이 수정되지 않았음을 증명할 때

: 비트코인은 작업증명(proof-of-work) 시스템

​

핵심 내용!

*해시 함수의 보안성 - 충돌 저항성(collision resistance), 역상 저항성(preimage resistance)

*구조 - SHA-1, SHA-2, SHA-3, BLAKE2의 내부 구조

6.1 보안 해시 함수

암호의 목적 : 자료의 기밀성

해시 함수의 목적 : 자료의 무결성

​

6.1.1 다시 등장한 비예측성

보안 해시 함수의 해시 값들이 예측 불가이기 때문에 SHA-256("a"), SHA-256("b"), SHA-256("c") 값을 알고 있어도 SHA-256("d") 값을 예측 할 수 없다.

보안 해시 함수는 입력이 주어질 때마다 무작위한 비트열을 돌려주는 블랙박스와 같아야 한다.

​

6.1.2 역상 저항성

주어진 해시 값 H에 대해 Hash(M) = H를 만족하는 임의의 메세지 M을 역상(preimage)라고 함.

역상 저항성 : 어떤 무작위 해시 값이 주어졌을 때 공격자가 그 해시 값의 역상을 결코 찾아낼 수 없다는 보안 보장 속성.

실제로 해시 함수를 일방향 함수(one-way function)라고 부른다.

역상 저항성은 제1 역상 저항성과 제2 역상 저항성으로 나뉜다.

제1 역상 저항성(first-preimage resistance) : M을 찾을 수 없다.

제2 역상 저항성(second-preimage resistance) : 어떤 메세지 M1의 해시 값과 동일한 값을 산출하는 M2를 찾을 수 없다. // 메세지 M1, M2가 있을 때 같은 해시 값을 가질 수가 있는 데 이유는 정보의 양이 너무 많아서 충돌을 피할 수 없기 때문이다.

​

6.1.3 충돌 저항성

해시 값의 충돌은 앞서 말했던 것처럼 서로 다른 메세지들이 같은 해시 값을 내는 것 또는 그러한 메세지들을 말한다. -> 비둘기집 원리(pigeonhole principle) : m개의 구멍(비둘기 집)에 n마리의 비둘기를 집어넣을 때 m<n이면 적어도 하나의 구멍에는 두 마리 이상의 비둘기가 들어가게 된다는 것

충돌 저항성은 제2 역상 저항성 개념과 관련있음.

​

6.1.4 충돌 찾기

역상 찾는 데 : 2^n회의 연산

충돌 찾는 데 : 2^(n/2)회의 연산

즉 충돌 찾는 게 더 빠르다. -> 생일 공격(birthday attack) : N개의 메세지와 그만큼의 해시 값이 주어졌을 때, 두 해시 값의 쌍들을 점검해서 최대 N x (N-1) / 2개의 잠재적 충돌을 만들 수 있다.

​

*소박한 생일 공격 : 생일 공격으로 충돌을 찾는 가장 간단한 방법이지만 상당히 많은 메모리가 필요함

1. 2^(n/2)의 임의로 선택한 메세지들로 2^(n/2)개의 해시 값을 계산하고, 각 메시지-해시 쌍을 하나의 목록에 저장한다.

2. 그 목록을 해시 값을 기준으로 정렬한다. 그러면 해시 값이 같은 쌍들이 인접한 위치에 놓이게 된다.

3. 정렬된 목록을 훑어서, 해시 값이 같은 두 쌍을 찾는다.

-> 이러한 정렬에 평균 n2^n회의 기본 연산이 필요

​

*로 방법(Rho method) : 메모리를 조금만 사용하는 충돌 검색

1. n비트 해시 값을 산출하는 해시 함수가 주어졌다고 할 때, 무작위 해시 값 H1을 선택하고 H1=H1' 로 정의한다.

2. H2 = Hash(H1)과 H2' = Hash(Hash(H1')) 을 계산한다. 전자는 해시 함수를 한 번, 후자는 해시 함수를 두 번 적용

3. Hi+1 = H'i+1 을 만족하는 i에 도달할 때까지 i를 증가하면서 Hi+1 = Hash(H1), H'i+1 = Hash(Hash(H'i))를 반복

말로 하면 어려우니까 그림을 살펴보자

주목할 점은 충돌을 찾으려면 이러한 순환마디를 찾기만 하면 된다는 것이다.

-> 순환마디(cycle) : 쉽게 말하면 그림에서의 동그라미~

다수의 값을 메모리에 저장하거나 긴 목록을 정렬하지 않기 때문에 메모리를 많이 소비하지 않는다.

​

6.2 해시 함수의 구축

메시지를 해싱하는 가장 간단한 방법 : 메시지를 작은 조각들로 나누고 각 조각을 비슷한 알고리즘을 이용해서 연달아 처리하는 것 -> 반복 해싱(interative hashing)

반복 해싱에는 크게 두 종류가 있다.

1. 머클-담고르 구성 : 입력을 더 작은 출력으로 변환하는 압축 함수(compression function)를 이용한 반복 해싱

2. 스펀지 함수 (sponge function) : 입력을 같은 크기의 출력으로 변환하는 함수를 이용한 반복 해싱

​

6.2.1 압축 기반 해시 함수: 머클-담고르 구성

MD4, MD5, SHA-1, SHA-2 족 해시 함수들 모두 머클-담고르 구성(M-D)을 따른다.

완벽하지는 않지만, 간단할 뿐만 아니라 여러 응용에 대해 충분히 안전함이 증명되었다.

M-D 구성을 따르는 해시 함수는 메시지를 같은 크기의 여러 블록으로 나눈 후 그 블록들을 하나의 압축 함수를 이용해서 하나의 내부 상태와 함께 섞는다.

compress : 압축 함수

H0, H1, ... : 연쇄 값(chaining value)

내부 상태의 마지막 값이 해시 값이다.

​

*블록 채우기

해싱할 메시지가 블록 단위로 떨어지지 않는다면? 블록을 채워야한다.

M-D 구성은 마지막 블록을 다음과 같이 구축한다: 남은 비트를에 '1'을 하나 추가하고 남은 비트들에는 0개를 추가하고 마지막으로는 원래의 메시지의 길이를 부호화한 고정된 개수의 비트들을 추가한다.

예를 들자면 520비트 메시지를 해싱하면 512비트 블록 하나와 8비트가 남고 그 8비트가 10101010 이라고 하면 10101010 1 000 ... 000 1000 이렇게 채우는 것이다. 처음에 1 추가, 그다음 0을 개수 맞춰서 추가, 마지막은 8비트가 남았었으니까 8이라는 2진수 표현인 1000을 추가하는 것.

​

*보안성 보장

압축 함수의 보안성 -> 해시 함수의 보안성 보장 (역은 성립 X)

​

*압축 함수의 구축 : 데이비스-마이어 구성

SHA-256이나 BLAKE2 같은 실제 해시 함수에 쓰이는 모든 암축 함수는 블록 암호에 기초.

상자 상단의 검은 역삼각형은 블록 암호의 키가 입력되는 지점.

Hi = E(Mi,Hi-1) xor Hi-1

여기서 Mi가 블록 암호의 키로 쓰이고 Hi-1은 평문 블록으로 쓰인다.

​

6.2.2 치환 기반 해시 함수: 스펀지 함수

좀 더 단순한 구조의 해시 함수를​ 스펀지 함수라고 부른다.

압축 함수와 블록 암호 대신 하나의 치환 함수를 사용.

스펀지 함수는 블록 암호를 이용하여 내부 상태와 메시지 비트들을 섞는 대신 XOR 연산을 사용

스펀지 함수가 쓰이는 용도 : 결정론적 난수 비트 발생기, 스트림 암호, 의사난수 함수, 인증 암호

가장 유명한 스펀지 함수 : Keccak(케착!) -> SHA3 함수임

*스펀지 함수의 작동 과정

1. 첫 메시지 블록 M1과 H0을 XOR한다. 여기서 H0은 내부 상태의 미리 정의된 초기치이다. 메시지 블록들은 모두 같은 길이이며, 함수의 내부 상태보다 작다.

2. 치환 함수 P를 이용해서 내부 상태를 같은 길이의 다른 값으로 변환한다.

3. 둘째 블록 M2와 내부 상태를 XOR하고, 내부 상태에 다시 P를 적용한다. 이러한 과정을 나머지 블록에 반복한다. 이것을 흡수 단계(absorbing phase)라고 부른다.

4. 모든 메시지를 흡수 했다면, 다시 P를 적용한 후 내부 상태로부터 비트들의 블록을 추출해서 해시 값을 만든다. 이것을 압착 단계(squeezing phase)라고 부른다.

​

스펀지 함수의 보안성은 내부 상태의 길이와 블록들의 길이에 의존.

스펀지 함수가 안전하려면 치환 P가 무작위 치환처럼 행동해야 한다.

​

6.3 SHA족 해시 함수

SHA(Secure Hash Algorithm) 해시 함수들은 군(military)에 속하지 않는 미국 연방 정부 기관들이 사용하도록 NIST가 정한 표준들.

​

6.3.1 SHA-1

SHA-0에 대한 충돌을 2^80회가 아니라 약 2^60회의 연산으로 찾아내는 방법을 발견하면서 SHA-1 표준이 나왔다. 이후 2^33회의 연산으로까지 줄여버렸다.

​

*SHA-1의 내부

SHA-1은 특별히 만든 블록 암호(SHACAL)에 기초해서 머클-담고르 해시 함수와 데이비스-마이어 압축 함수를 결합한 것이다.

SHA-1의 compress, blockcipher, expand, f 함수 중 f 함수에서 비선형 & 연산자를 이용하여서 이 덕분에 차분 암호해독 공격이 방지된다.

SHA-1의 연쇄값은 160 비트.

​

*SHA-1에 대한 공격들

크롬 브라우저는 HTTPS 연결에 SHA-1을 사용하는 웹사이트를 '안전하지 않음'으로 표시한다. (처음알았음 ㅋㅋ)

SHA-1은 안전하지 않아서 사용하지 말아야 한다. -> 충돌 저항성 수준이 80비트였는 데 결함을 찾아서 2^63 회의 연산으로 충돌을 찾을 수 있게 되었다.

​

6.3.2 SHA-2

NSA가 설계하고 NIST가 표준화했다.

SHA-224, SHA-256, SHA-384, SHA-512로 이루어져있다.

​

*SHA-256

SHA-256의 연쇄값은 256비트이다. 메시지 블록은 512 비트로 SHA-1과 동일하다.

메시지 확장 함수 expand256()이 쓰이는 데 SHA-1의 expand()보다 복잡하다.

SHA-1 expand() : xor와 1비트 회전 수행

SHA-256 expand256() : xor, and, 회전 수행.

SHA-256은 256비트의 역상 저항성을 보장하고 있다.

​

*SHA-512

SHA-512의 연쇄값은 512비트이다. 메시지 블록은 1024비트이다.

회전 거리 빼고 SHA-256과 거의 같다.

약 256비트의 충돌 저항성을 보장한다.

​

혹시나 SHA-2에 대한 공격 기법이 나타날지도 모른다는 대비책으로 NIST는 SHA-3을 개발했다.

​

6.3.3 SHA-3 공모전

요구 조건 : SHA-2만큼 안전하고 빠르고 SHA-2가 할 수 있는 일은 모두 할 수 있어야 한다. SHA-1, SHA-2와는 다른 구조여야 한다.

최종적으로 Keccak 이 우승작이 되었다.

NIST : "Keccak 은 설계가 우아하고, 보안 이득이 크고, 전반적인 성능이 좋고, 하드웨어 효율성이 탁월하고, 유연성도 훌륭하다."

​

6.3.4 Keccak ( SHA-3 )

스펀지 함수의 일종인 Keccak의 핵심 알고리즘은 1600비트 상태를 치환해서 1152비트나 1088비트, 832비트, 576비트 블록들을 처리하며, 그 결과로 224, 256, 384, 512 비트의 해시 값을 산출한다.

하나의 핵심 알고리즘을 사용해서 네 가지 길이의 해시 값들(224,256,384,512)을 모두 생성한다.

SHA-3 표준 명세서 FIPS 202에는 두 가지 알고리즘 SHAKE128, SHAKE256이 정의되어 있다.

이 두 알고리즘은 확장 가능 출력 함수(extendable-output function, XOF)라고 부른다. -> 가변 길이의 해시 값들을 산출할 수 있는 해시 함수이다.

​

표준 명세서 자체가 너무 길고 어려워서 tiny_sha3 이라는 구현 코드를 읽는 게 더 쉽다.

tiny_sha3은 Keccak의 치환 P를 구현하는 데 이 함수가 하나의 라운드를 여러번 수행한다.

하나의 라운드는 4개의 단계로 이루어져 있다.

1. Theta : 64비트 워드들의 XOR와 워드들의 1비트 회전이 포함

2. Rho Pi : 64비트 워드들의 회전이 포함 ( 회전 자릿수는 Keccakf_rotc[] 배열에 고정 )

3. Chi : XOR와 AND도 적용 -> 유일한 비선형 연산들

4. Iota : Keccakf_rndc[] 에 미리 고정된 64비트 상수와의 XOR 수행

​

6.4 BLAKE2 해시 함수

해시 함수에서 중요한 것 : 보안성 그리고 속도! 속도도 무시할 수 없는 요인

SHA-3 공모전 이후 나온 BLAKE2라는 해시 함수의 설계자들이 설계 시 염두에 둔 사항

: SHA-3만큼은 안전해야 한다.

: MD5를 비롯한 기존의 모든 해시 표준보다 빨라야 한다.

: 현대적인 응용들에 사용하기에 적합해야 하며, 대량의 자료를 해싱할 수 있어야 하며, 비밀 키를 지원하되 비밀 키 없이도 해싱 할 수 있어야 한다.

: 다중 코어 시스템에서 현대적인 CPU의 병렬 컴퓨팅 지원 기능은 물론이고 단일 코어 안의 명령 수준 병령성을 활용하기에도 적합해야한다.

-> BLAKE2b, BLAKE2s가 만들어졌음. 전자는 64비트 플랫폼 최적화, 후자는 8~32비트 플랫폼 최적화이다.

BLAKE2의 압축함수는 데이비스-마이어 구성의 한 변형으로 카운터(counter), 플래그(flag)라는 추가적인 매개변수를 받는다.

카운터 : 압축 함수의 각 실행이 매번 다른 함수처럼 행동하게 만드는 역할

플래그 : 압축 함수가 마지막 메시지 블록을 처리하는지의 여부 ( 보안성 높이기 위한 장치 )

압축 함수에 쓰이는 블록 암호는 스트림 암호 ChaCha(Salsa20의 변형)에 기초했다.

​

6.5 문제 발생 요인들

6.5.1 길이 연장 공격(length-extension attack)

머클-담고르 구성에 대한 주된 위협이 길이 연장 공격이다.

SHA-2 해시 함수는 길이 연장 공격에 취약하다.

이 공격은 마지막 압축 함수 실행을 이전의 모든 압축 함수 실행과 조금 다르게 만들기만 하면 해결된다. 방금 전 설명했던 BLAKE2에서 flag를 사용하는 것도 이러한 공격을 피해 보안성을 높이려는 것에 해당한다.

​

6.5.2 저장증명 프로토콜 속이기

클라우드 컴퓨팅 응용 프로그램들은 저장증명(proof-of-storage) 프로토콜(클라이언트가 저장해달라고 요청한 파일을 서버가 실제로 저장했음을 증명하는 데 쓰이는 프로토콜)안에서 해시 함수를 사용해왔다.

​

*저장증명 프로토콜

1. 클라이언트는 어떤 난수 값 C(시도, challenge라고 부른다)를 선택한다.

2. 서버는 그에 대한 응답(response)으로 Hash(M||C)를 계산해서 클라이언트에게 보낸다.

3. 클라이언트도 Hash(M||C)를 계산해서 그것이 서버가 보낸 응답 값과 일치하는지 확인한다.

​

만약 서버가 연쇄 값 H1=Compress(H0,M1)을 계산하고 M 자체를 폐기하면 Hash(M||C)를 계산하는 데는 아무 문제가 없지만 M을 사실상 저장하지 않고 클라이언트를 속일 수 있다.

​

이러한 문제의 해결책은 Hash(C||M)을 맞추어 보도록 하면 된다.

​

이번 글에서는 블록 암호에 이어서 스트림 암호를 공부해보도록 하겠습니다!!

​

스트림 암호는 블록 암호보다 취약하고 더 자주 깨졌다는 이유로 꺼리는 사람들이 있었는데요 지금은 다행히 안전한 스트림 암호를 설계하는 방법이 알려져 있고, 블루투스 연결, 이동전화의 4G 통신, TLS 연결 등이 스트림 암호 덕분에 안전하게 보호된다고 합니다!

​

5.1 스트림 암호의 작동 방식

스트림 암호는 DRBG( 결정론적 난수 비트 발생기 )처럼 결정론적이다. 스트림 암호와 DRBG의 차이는 DRBG는 하나의 값을 입력받지만 스트림 암호는 두 개의 값( 키, 논스(nonce) )을 입력받는다.

키는 반드시 비밀, 논스는 비밀일 필요는 없다.

스트림 암호의 암호화 방식

암호화 방식을 살펴 보면, 키와 논스를 입력 받아 스트림 암호 알고리즘을 통해 키스트림(KS)을 생성한다. 키스트림과 평문 P를 XOR 하면 암호문이 나오고, 그 암호문을 다시 키스트림과 XOR 하면 평문이 나온다.

스트림 암호에서 키와 논스는 각각 재사용이 가능하지만 같이 재사용을 하면 이전과 동일한 KS가 생성되므로 동시에 재사용은 하면 안된다.

​

5.1.1 상태 있는 스트림 암호와 카운터 기반 스트림 암호

크게 봤을 때, 스트림 암호는 상태 있는 스트림 암호(stateful stream cipher)와 카운터 기반 스트림 암호(counter-based stream cipher)로 나뉜다.

i ) 상태 있는 스트림 암호 ex) RC4

주어진 키와 논스로 상태를 초기화(init) 한 후 갱신 함수(update)를 통해서 상태값을 갱신하고, 상태로 부터 하나 이상의 키 스트림 비트들을 생성하고 평문과 XOR 해서 암호문을 얻는다.

​

ii ) 카운터 기반 스트림 암호

키와 논스, 카운터 값을 이용해서 키스트림 조각들을 생성한다.

​

스트림 암호의 내부는 대상 플랫폼에 따라 크게 두 범주로 나뉜다. 하나는 하드웨어 지향적 스트림 암호, 다른 하나는 소프트웨어 지향적 스트림 암호이다.

​

5.2 하드웨어 지향적 스트림 암호

암호의 하드웨어 구현은 암복호화 이외의 용도로는 쓰이지 않는다.

초창기 스트림 암호들은 복잡한 워드 단위 연산을 피하기 위해 비트들을 다루었기 때문에 하드웨어에서 더 효율적이었다. 또한 블록 암호보다 구현 비용이 낮아서 잘 쓰였었는 데 현재는 블록 암호가 스트림 암호보다 비싸지 않다. 그렇긴 하지만, 예전에 하드웨어에 대해 최고의 선택이었다는 이유로 지금도 스트림 암호를 하드웨어와 연관 시키는 경우가 많다.

​

5.2.1 FSR(되먹임 자리이동 레지스터)

되먹임 함수를 f 라고 하고 FSR의 각 갱신 연산에서는 그 상태의 값을 변경하고 하나의 출력 비트를 산출한다.

식으로 나타내보자면

Rt+1 = (Rt << 1) | f(Rt)

여기서 | 는 OR 이고 << 는 왼쪽으로 shift 이다.

ex) 되먹임 함수 f는 주어진 네 비트를 XOR로 결합하는 함수, 초기 상태 : 1 1 0 0

f(1100) = 1 xor 1 xor 0 xor 0 = 0

새로운 상태 : (1100<<1) | 0 = 1000

이런 식으로 계속해나가면

1100 -> 1000 -> 0001 -> 0011-> 0110 -> 1100 이렇게 되어서 주기(period)가 5가 된다.

보안을 위해서는 이러한 반복 패턴을 피해야 하며 주기가 길어야 한다.

​

i ) LFSR(선형 되먹임 자리이동 레지스터)

되먹임 함수가 선형 함수인 FSR이다.

암호학에서 선형성은 예측가능성과 같은 말이다. 바탕에 깔린 수학 구조가 단순함.

LFSR의 주기는 되먹임 함수가 레지스터의 어떤 비트들을 XOR하느냐에 크게 의존. -> 최대 주기인 2^n-1이 나오도록 비트들을 선택하는 방법이 알려져 있음.

만약 1번째, 3번째, 4번째 비트들을 xor 한다고 하면 다항식을 1+X^1+X^3+X^4 로 만들 수 있고 이렇게 만든 다항식이 원시다항식(기약다항식, 즉 더 이상 인수분해할 수 없는 다항식)이면 FSR의 주기가 최대가 된다.

1+X^1+X^3+X^4 = (1+X)(1+X^3) 이므로 원시다항식이 아님.

벌러캠프-매시 알고리즘(Berlekamp-Massey algorithm) 이용해서 LFSR의 수학 구조로 정의된 방정식들을 풀 수 있어서 LFSR은 안전하지 않다.

​

ii ) 필터링된 LFSR

LFSR이 출력한 비트들을 비선형함수로 변환한다면 LFSR의 선형성을 숨길 수 있고, 비보안성을 완화시킬 수 있을 것이다. 이러한 LFSR을 필터링된 LFSR이라고 부른다.

그림에서 g 함수는 반드시 비선형 함수여야 한다. -> XOR 뿐만 아니라 AND, OR 연산으로도 결합

하지만 아래의 공격을 이용하면 이 암호체계를 깰 수 있다.

1) 대수적 공격(algebraic attack) : 출력 비트들로부터 비선형 방정식들을 연역해서 푼다.

2) 큐브 공격(cube attack)​ : 비선형 방정식들의 도함수를 계산해서 방정식들의 차수를 1까지 끌어내린다.

3) 고속 상관 공격(fast correlation attack) : 비선형성을 가지고 있긴 하지만 선형함수처럼 행동하는 경향이 있는 필터링 함수들을 활용한다.

​

iii ) NFSR(비선형 FSR)

LFSR과 비슷하지만 되먹임 함수가 비선형이다.

장점 : 암호학적으로 강해진다

단점 : NFSR의 주기를 효율적으로 알아내는 것이 불가능하다.

주기가 짧으면 LFSR과 NFSR을 결합해서 최대 주기를 보장하고 암호학적 강도도 보장해서 사용 -> Grain-128a

​

5.2.2 Grain-128a

Grain-128a는 128비트 키와 96비트 논스를 사용한다.

128비트 키는 NFSR의 128비트 레지스터에 복사, 96비트 논스의 비트들은 LFSR 레지스터의 앞부분 96비트에 복사하고 나머지 32 비트 중 31개의 비트에는 1로 마지막 비트는 0으로 설정한다. 초기화 단계에서는 시스템 전체를 256번 갱신하고 그 다음에야 첫 번째 키스트림 비트를 출력한다.

<LFSR의 되먹임 함수>

f(L) = L32 + L47 + L58 + L90 + L121 + L128

<NFSR의 되먹임 함수>

g(N) = N32 + N37 + N72 + N102 + N128 + N44N60 + N61N125 + N63N67 + N69N101 + N80N88 + N110N111 + N115N117 + N46N50N58 + N103N104N106 + N33N35N36N40

필터 함수 h 역시 비선형함수이다. 이 함수는 NFSR에서 비트 9개, LFSR에서 비트 7개를 받아서 적절히 결합한다.

h(x) = bi+12 Si+8 + Si+13Si+20 + bi+95Si+42 + Si+60Si+79 + bi+12bi+95Si+94

​

5.2.3 A5/1

A5/1은 2G 이동통신 표준에서 음성 통신을 암호화하는 데 쓰였던 스트림 암호이다.

​

- A5/1의 작동 방식

그림에서 보듯이 A5/1은 비트 수가 각각 19, 22, 23인 LFSR들을 사용한다.

< 되먹임 다항식 >

LFSR 1 = 1 + X^14 + X^17 + X^18 + X^19

LFSR 2 = 1 + X^21 + X^22

LFSR 3 = 1 + X^8 + X^21 + X^22 + X^23

< 갱신 매커니즘 >

1. LFSR 1의 비트 9의 값, LFSR 2의 비트 11의 값, LFSR 3의 비트 11의 값이 모두 같거나 한 비트만 다르다. 이 비트들을 클로킹 비트 ( clocking bit ) 라고 한다.

2. 만약 클로킹 비트가 1 1 1 이면 1의 클로킹 비트를 가지고 있는 레지스터끼리 xor을 하고 1 0 0 이면 0이 더 많으니까 0의 클로킹 비트를 가지고 있는 레지스터끼리 xor을 한다.

​

- A5/1에 대한 공격 기법

1. 정교한 공격 ( subtle attack ) : 내부 선형성, 단순한 불규칙 클로킹 체계를 활용

- 추측 후 판정 ( guess-and-determine )이라고 부르는 한 정교한 공격 기법에서 공격자는 상태의 특정 비밀 값들을 추측해서 다른 비밀 값들을 알아낸다.

↓ 이러한 공격을 나타낸 의사코드다.

LFSR 1의 초기 상태의 모든 가능한 2^19가지 값에 대해: LFSR 2의 초기 상태의 모든 가능한 2^22가지 값에 대해: 처음 11 클록 동안 LFSR 3의 클로킹 비트의 모든 가능한 2^11가지 값에 대해: LFSR 3의 초기 상태를 재구축한다. 추측이 맞는지 점검한다. 맞으면 반환하고 아니면 반복한다.

LFSR 1의 초기 상태의 모든 가능한 2^19가지 값에 대해: 
	LFSR 2의 초기 상태의 모든 가능한 2^22가지 값에 대해: 
    		처음 11 클록 동안 LFSR 3의 클로킹 비트의 모든 가능한 2^11가지 값에 대해: 
        		LFSR 3의 초기 상태를 재구축한다. 
            		추측이 맞는지 점검한다. 맞으면 반환하고 아니면 반복한다.

2. 무차별 공격 ( brutal attack ) : 짧은 키와 프레임 번호 주입의 가역성 활용

- 코드북 공격을 함. -> 실제로 2G 이동통신의 암호문을 코드북 공격을 이용해서 거의 실시간으로 복호화할 수 있었다.

​

5.3 소프트웨어 지향적 스트림 암호

현대적인 CPU는 비트에 대한 연산에 걸리는 시간과 워드에 대한 연산에 걸리는 시간이 다를 바가 없기 때문에 바이트나 워드를 다루는 것이 더 효율적이다. 그래서 소프트웨어 스트림 암호가 하드웨어 암호보다 더 낫다. 현재 암호학자들이 가장 주목하는 설계 두 가지는 RC4와 Salsa20이다.

​

5.3.1 RC4

오랫동안 가장 널리 쓰인 스트림 암호인 RC4는 역공학을 통해 취약점이 노출되었다.

최초의 Wi-Fi 암호화 표준인 WEP ( Wired Equivalent Privacy; 유선 동등 프라이버시 ) 와 HTTPS 연결에 쓰이는 TLS ( Transport Layer Security; 전송 계층 보안 ) 프로토콜에 사용됐다.

​

- RC4의 작동 방식

RC4의 내부 상태인 256개의 바이트로 이루어진 배열 S를 키 K를 이용해서 초기화한다. -> 키 스케줄링 알고리즘

S의 두 인덱스를 선택해서 swap 하고 두 특정 바이트를 통해 키스트림을 생성한다. 여기서 얻은 키스트림을 평문 P와 XOR 하여 암호문을 얻는다.

j=0 
S = range(256) 
for i in range(256): 
	j = (j + S[i] + K[i%n]) % 256 
   	S[i], S[j] = S[j], S[i]

i = 0
j = 0 
for b in range(m):
	i = (i + 1) % 256
   	j = (j + S[i]) % 256
   	S[i], S[j] = S[j], S[i]
   	KS[b] = S[(S[i] + S[j]) % 256]

위의 코드에서 m은 평문의 길이이고 그 길이 만큼 swap을 진행한다. 이 방식을 테이블 셔플링(shuffling) 방식이라고 한다.

​

- WEP의 RC4

: 무선망으로 자료를 전송하는 데이터그램인 802.11 프레임 안에 있는 페이로드 자료를 암호화한다. 한 세션에서 전송되는 모든 페이로드 자료는 40, 104 비트 길이의 동일한 비밀 키 사용. 각 페이로드 헤더에는 3 바이트 논스 값이 부호화되어있다.

여기서 문제!! RC4는 논스를 지원하지 않는다. -> WEP 설계자들은 무선 프레임 헤더에 24비트 논스를 포함하고 그것을 RC4의 비밀 키로 쓰이는 WEP 키의 앞에 붙였다.

* WEP의 논스 편법의 진정한 문제점

1. 논스가 너무 작다.

2. 논스와 키를 연결하는 방식 때문에 키를 복원하기 쉽다.

​

- TLS의 RC4

: TLS는 인터넷에서 쓰이는 가장 중요한 보안 프로토콜이다. HTTPS 연결의 용도로 널리 알려져 있지만 그 뿐아니라 VPN이나 이메일 서버, 이동통신 응용 프로그램 등의 여러 응용을 보호하는 데에도 쓰인다.

TLS의 약점은 전적으로 RC4 때문이다. -> 통계적 편향, 비무작위성

​

5.3.2 Salsa20

Salsa20은 현대적인 CPU에 최적화된 간단한 소프트웨어 지향적 스트림 암호이다.

Salsa20은 하나의 키 K와 하나의 논스 N, 카운터 값 Ctr로 이루어진 512 비트 블록을 핵심(core) 알고리즘을 이용해서 변환하고 그 결과를 원래 512비트 블록과 더해서 하나의 키스트림 블록을 산출한다.

​

- 쿼터 라운드 함수

이 함수는 네 개의 32비트 워드(a,b,c,d)를 다음과 같이 변환

b = b xor [(a + d) <<< 7]

c = c xor [(b + a) <<< 9]

d = d xor [(c + b) <<< 13]

a = a xor [(d + c) <<< 18]

​

- Salsa20의 512비트 상태의 변환

Salsa20 초기 상태

C0~C3 : 상수

K0~K7 : 키

V0, V1 : 논스

T0, T1 : 카운터

​

<변환 과정>

1. 열 라운드(column-round) - 홀수번째 라운드

2. 행 라운드(row-round) - 짝수번째 라운드

열 라운드와 행 라운드의 조합을 이중 라운드(double-round) -> salsa20은 이중 라운드를 10번 반복(2x10 = 20)

​

- Salsa20의 평가 : 10라운드 반복 후 무작위해 보이지만 그 자체가 보안성을 보장하지는 않는다.

하지만 RC4보다는 훨씬 안전하며, 통계적 편향이 없다.

​

- 차분 암호해독 : 상태들의 실제 값 자체가 아니라 상태들의 차이를 연구하는 차분 암호해독(differential cryptanalysis)

차분 암호해독으로 살펴본 결과 비트 하나 차이가 512 비트 상태의 거의 모든 비트로 전파되는 걸 확인할 수 있는 데 이 성질을 전확산(full diffusion)이라고 부른다.

상태의 진화가 XOR와 덧셈, 순환 자리 이동의 조합으로 이루어진 고도로 비선형적인 관계식이면 공격자가 미래의 상태 차이를 예측하기 어려워진다.

​

- Salsa20/8에 대한 공격

Salsa20/8은 라운드를 8회만 수행하는 버전으로 2^256회 미만의 연산으로 키를 복원하는 공격 기법이다.

통계적 편향을 활용하며 논스 N, 카운터 Ctr, 키 K를 알면 키스트림 계산을 거꾸로 수행해서 초기 상태를 복원할 수 있다.

키의 일부를 제대로 추측 -> 편향된 비트가 나타남 ( 편향된 비트가 나타났다? 추측한 키가 맞다 )

실제 공격시, 추측이 옳은지 판정하려면 키의 비트 220개가 필요하며 키스트림 블록들의 쌍 2^31개가 필요.

정확한 비트 220개를 알아낸 후에 나머지 비트 36 개는 무차별 대입 공격으로 알아내면 된다.

5.4 문제 발생 요인들

​

5.4.1 논스 재사용

: 같은 키에 대해 하나의 논스를 두 번 이상 재사용하는 바보!!

* SIV 모드 : 같은 논스를 두 번 사용해도 안전

​

5.4.2 잘못된 RC4 구현

: RC4의 알고리즘에는 swap이 사용된다. 그 때의 코드는

buf = S[i]
S[i] = S[j] 
S[j] = buf

이 때 buf라는 새로운 변수를 사용해야하는데 프로그래머들이 이를 피하기 위해 xor-swap 을 이용하여 코드를 짠다. 아래의 코드는 오류가 있는 코드의 일부이다.

#define SWAP(x,y) do {x^=y; y^=x; x^=y;} while(0)
... 
SWAP(S[i], S[j]);

이렇게 되어 있는 데 i=j 일때 문제가 생긴다.

xor swap에서 i=j이면 s[i]에 0이 배정된다. ( i와 j가 같아서 S[i]와 S[j]도 같음) -> 결국 모든 바이트가 0,,,,

​

이로써 스트림 암호도 알아봐버렸다!! 너무 어렵디만 하다보면 익숙해지겠지,, *^^*

더 열심히 해보자!! 바-위~

오늘은 블록암호에 대해 알아보자.

미국 정부에서 만든 DES(Data encryption Standard; 자료 암호화 표준), 벨기에에서 개발된 DES의 후계자 AES(Advanced Encryption Standard), KGB가 개발한 GOST 28147-89 의 공통점은 무엇일까?

바로 블록 암호(block cipher)라는 것이다.

4.1 블록 암호란 무엇인가?

하나의 블록 암호는 암호화 알고리즘 하나 + 복호화 알고리즘 하나로 구성

​

4.1.1 보안 목표

블록 암호에서의 보안성?? "얼마나 무작위하게 보이는가" --> 반드시 의사무작위 치환(pseudorandom permutation, PRP) = 키를 알지 못하는 한 공격자는 임의의 입력으로부터 블록 암호의 출력을 계산할 수 없어야 한다.

4.1.2 블록 크기

블록 암호의 보안성은 (a) 블록의 크기 , (b) 키의 크기 에 의존한다.

DES - 64(2^6)비트 블록

AES - 128(2^7)비트 블록

*현대적인 CPU들이 64비트보다 128비트를 더 효율적으로 처리하며 128비트 블록이 더 안전

* 암호문의 길이나 메모리 사용량을 최대한 아껴야 하는 상황에서는 64비트 블록을 사용할 수 있다.

4.1.3 코드북 공격

메모리를 아낀다고 블록을 너무 작게 사용한다면? 코드북 공격(codebook attack)에 당할 수 있다.

코드북 공격은 블록이 작을 때만 효율적으로 작용하는 불록 암호 공격 기법이다. -> 32비트 블록까지는 감당할 수 있지만 블록이 그것보다 더 커지면 현실적으로 불가능!

​

4.2 블록 암호 구성

블록 암호를 구성하는 데 쓰이는 기법의 수는 그리 많지 않다.

1. 실제 쓰이는 블록 암호는 하나의 거대한 알고리즘이 아닌 짧은 라운드들을 반복하는 형태의 알고리즘이다.

2. 라운드를 구축하는 기법은 크게 두가지이다. ( 대입-치환 네트워크, 파이스텔 방안 )

​

4.2.1 블록 암호의 라운드

블록 암호의 알고리즘은 명세와 구현이 쉬운 기본적인 형태의 라운드를 여러 번 반복하는 것으로 구성된다.

ex) 평문을 세 개의 라운드로 암호화하는 블록 암호를 C = R3(R2(R1(P)))로 표현

- 각 라운드마다 서로 다른 라운드 키 존재.

- 각 라운드는 동일한 알고리즘을 사용하되 라운드 키로 매개변수 되서 다른 라운드 키를 가지면 다른 동작을 하게 된다.

- 각 라운드 키는 주 키 K 로부터 생성 ( 키 스케줄 알고리즘 사용 ), 주 키 K와는 다른 값.

4.2.2 슬라이드 공격과 라운드 키

모든 라운드가 같아버리면 어떤 일이 일어날까? 슬라이드 공격(slide attack)에 당하게 된다..

위 사진에서는 라운드가 세개라 C2=R(C1) 만 알수 있지만 라운드 수가 늘어나도 항상 성립한다.

공격자가 한 라운드의 입력과 출력을 알아내서 키 복원에 활용할 수 있다.

따라서 라운드 마다 다른 라운드 키를 사용해야 이런 슬라이드 공격을 좌절시킬 수 있다.

4.2.3 대입-치환 네트워크 ( substitution-permutation network, SPN )

- 혼돈(confusion) : 입력(평문과 암호화 키)이 복잡한 변환들을 거친다, 깊이에 관한 것

- 확산(diffusion) : 그러한 변환들이 모든 비트에 동일하게 의존한다, 너비에 관한 것

- 대입 연산은 대입 상자(substitution box; S-상자)로 구현된다.

* 대입 상자 : 4비트 또는 8비트의 자료 조각을 변환하는 작은 참조표

- 치환은 그냥 비트들의 순서를 바꾸는 정도로 간단한 치환일 수도 있지만 비트들을 많이 뒤섞진 못한다. 대신 어떤 암호들은 기본적인 선형대수와 행렬 곱셈을 이용해서 비트들을 섞는다.

* 대입-치환 네트워크 알고리즘을 사용하는 대표적인 암호는 AES이다. 뒤에서 자세히 알아보도록 하자.

​

4.3.4 파이스텔 방안 ( Feistel scheme )

- 파이스텔 방안의 작동 과정

1. 일단 암호화하려는 정보를 절반으로 잘라서 (L, R) 을 얻는다.

2. L = L xor F(R) // F는 하나의 대입-치환 라운드

3. L과 R을 교환하여 (R,L)을 얻는다

4. 단계 2와 3을 15번 되풀이 한다.

5. L과 R을 연결해서 하나의 64비트 출력 블록을 만든다.

이런 방식으로 동작을 한다. F 함수들이 받는 Ki는 라운드 마다 다르고 48비트 라운드 키이다.

여기서 F는 의사무작위 함수(PRP)일 수도 있고, 의사난수 함수(pseudorandom function, PRF)일 수도 있다.

- PRP : 서로 다른 두 입력에 대해 각각 다른 출력을 산출

- PRF : 서로 다른 두 입력에 대해 같은 출력을 할 수도 있다. ( F가 암호학적으로 강한 함수면 이러한 차이는 무시 )

* 이론적으로 F가 왕왕 강하다면 라운드가 4개만 있어도 충분하지만 현실은 그보다 많은 수의 라운드 사용.

4.3 AES(고급 암호화 표준)

* AES는 현재 이 세상에서 가장 많이 쓰이는 암호다.

​

4.3.1 AES의 내부

- AES는 128비트 블록들을 128비트나 192, 256비트 비밀 키 하나를 이용해서 처리한다.

- 가장 널리 쓰이는 것은 128비트. ( 대부분의 응용 프로그램에서 128비트와 256비트의 보안성 차이는 무의미 )

AES는 하나의 16바이트 평문을 2차원 배열로 취급한다. 이 배열을 AES의 내부 상태 (internal "state")

AES는 같은 구조의 SPN과 다수의 라운드를 사용해서 상태를 변환

위 그림에서 보듯이, 하나의 AES 라운드는 4가지 연산으로 이루어져 있음.

1) SubBytes : 각 바이트(S0, ... , S15)를 대입 상자에 따라 다른 바이트로 대체한다.

2) ShiftRows : 0에서 3 까지의 i에 대해, i번째 행을 i자리 만큼 순환 이동.

3) MixColumns : 상태의 네 열(column)에 대해 동일한 선형변환을 적용. ( 선형변환 : 예측가능 )3

4) AddRoundKey : 라운드 키와 내부 상태의 XOR.

* KeyExpansion이 없으면? 모든 라운드 키가 같음 -> 슬라이드 공격에 취약

* AddRoundKey가 없으면? 누구나 키 없이도 임의의 암호문을 복호화

* SubBytes가 없으면? 한 열의 변화가 다른 열들에 영향을 미치지 않아서 코드북 만들어 깰 수 있음

* MixColumns가 없으면? 참조표를 이용해서 암호문을 복호화할 수 있음

** 복호화 하는 과정은 모든 연산의 역함수 이용

4.4 AES의 구현

4.4.1 테이블 기반 구현

4.4.2 전용 기계어 명령

4.4.3 AES는 안전한가?

AES는 블록 암호가 안전할 수 있을 만큼 안전하며, 절대 깨지지 않는다.

왜냐하면 모든 출력 비트가 모든 입력 비트에 어떤 복잡하고도 의사무작위한 방식으로 의존하기 때문이다.

하지만 AES가 모든 가능한 공격에 면역이라는 증명은 없다. ( 우리가 모든 가능한 공격을 모르기 때문에 )

그리고 블록 암호에 대한 가장 큰 위협은 핵심 알고리즘이 아니라 "운영 모드"들에 존재한다.

​

4.5 운영 모드

4.5.1 전자 코드북(ECB) 모드

블록 암호의 암호화에서 가장 간단한 모드!!

하지만 안전하지 않으므로 사용하면 안 된다! -> 같은 키와 같은 평문으로 암호화를 반복하면 같은 암호문이 나옴, 전체 블록 단위의 자료들만 처리할 수 있음

* ECB 암호화는 원래 이미지와 색만 다른 이미지를 산출할 뿐이다.

​

4.5.2 암호 블록 연쇄(CBC) 모드

ECB와는 달리 CBC(Cipher block chaining) 모드는 Ci = E(K,Pi xor Ci-1) 로 암호화한다.

첫 블록 P1을 암호화할 때는 이전 암호문 블록이 없으므로 무작위 초기치(initial value, IV)를 사용.

CBC 모드의 복호화는 암호화와 달리 병렬 처리가 가능하여 더 빠르다.

Pi = D(K,Ci) xor Ci-1

위의 식으로 복호화 될 때 모든 암호문을 알고 있기 때문에 병렬계산과 함께 평문을 얻어낼 수 있다.

​

4.5.3 CBC 모드에서 임의의 길이의 메시지를 암호화하는 방법

EBC 모드의 단점 중 블록 단위 제약을 극복하는 방법 ( 블록 길이의 정수배가 아닌 길이의 평문 처리 방법 )을 두 가지 기법을 통해 알아보도록 하자.

1) 메시지 채우기(padding)

- 마지막 블록이 완전히 '채워질' 때 까지 평문에 여분의 바이트들을 추가한다.

- 블록들을 채우고 15 바이트를 더 채워야 하면 그 값을 0f(십진수로 15)로 메시지 끝에 15개 추가

- 블록들을 채우고 13 바이트를 더 채워야 하면 그 값을 0d(십진수로 13)로 메세지 끝에 13개 추가

- 만약 블록 길이 16의 정수배에 해당하면 그대로 끝내는 게 아닌 10(십진수로 16)로 메세지 끝에 16개 추가

* 복호화 방법

1. 모든 블록(채우기된 상태)을 복호화한다.

2. 마지막 바이트들을 살펴본다. 01이 1개 있는지, 02가 2개 있는지 등등..

3. 혹시 그렇지 않다면 복호화 거부를 하고, 과정2를 만족한다면 채움 바이트를 제거하고 평문 바이트를 돌려준다.

2) 암호문 훔치기(ciphertext stealing)

- 채우기보다 더 복잡하고 덜 쓰이지만 3가지 장점이 있다.

1. 평문이 비트 단위의 길이라서 131비트 같은 평문을 암호화할 수 있다.

2. 암호문이 평문과 같은 길이이다.

3. 채움 오라클 공격에 취약하지 않다.

그림에서도 볼 수 있듯이 C2 = P3 xor (이전 암호문 블록의 마지막 비트들) 그 다음 암호화한 결과

C3 = 이전 암호문 블록의 처음 비트들

- 단점 : 별다른 문제점이 없지만, 별로 우아하지 않고 제대로 구현하기가 어렵다.

​

4.5.4 카운터(CTR) 모드

- 암호문 훔치기의 장점을 유지하면서 단점을 피하고 싶을 때 사용하는 모드

- 블록이라는 개념에 의존하지 않고 그냥 비트들을 받아서 비트들을 산출하는 형태의 암호로 바꾸는 역할

N(논스)은 한 번만 쓰이는 수(number used only once)인 일종의 토큰값으로 한 메시지의 모든 블럭은 같은 논스 값 사용

Ctr(카운터)은 하나의 메시지들이 같은 값을 사용할 수는 없다.

- 동작 과정 : N과 Ctr을 이어붙인 다음 암호화를 해서 나온 값과 평문을 xor 해서 암호문 블록을 만든다. ( 복호화 과정도 이와 동일하기 때문에 하나의 암호화 알고리즘을 암복호화에 사용할 수 있다. )

- 논스가 무작위일 필요가 없지만 각 암호화마다 고유(유일)해야한다.

- 장점 : 그 어떤 모드보다도 빠를 수 있다. ( 병렬화 and 평문 메시지가 주어지기 전에 암호화 시작 가능 )

​

4.6 문제 발생 요인들

블록 암호에 대한 공격 중 두 가지는 반드시 알아 두어야 한다.. 라고 써있네여..

중간값 일치 공격이랑 채움 오라클 공격인데 중간값 일치 공격이랑 중간자 공격이랑 다르대여 ㅋㅋ 같은줄알았는데.. 머-쓱

​

4.6.1 중간값 일치 공격

3DES의 보안 수준이 168비트가 아닌 112비트인 이유가 중간값 일치(meet-in-the-middle, MitM) 공격 때문이다.

4.6.2 채움 오라클 공격

2.1 무작위 대 비무작위

11010110 과 00000000

둘 중 무엇이 더 무작위해 보이는가?

대부분의 사람들은 11010110이 더 무작위해 보인다고 한다. 하지만 확률로 따져보았을 때, 둘은 1/(2^8)의 확률로 동일하게 생성된다. 여기서 사람들이 무작위성(randomness)을 식별할 때 저지르는 두 가지 오류를 확인할 수 있다.

1) 비무작위성(non-randomness)을 무작위성으로 오해 : 단지 무작위해보인다는 이유로 무작위하게 생성되었다고 생각하는 실수

2) 무작위성을 비무작위성으로 오해 : 어떠한 패턴을 보고 그런 패턴이 발생한 이유가 있을 것이라고 생각하는 실수

** 보안을 위해서 무작위해 보이는 것과 실제로 무작위한 것을 구별하는 것은 굉장히 중요!!

​

2.2 확률분포로서의 무작위성

- 확률분포

: 주어진 과정의 무작위성에 관해 알아야 할 모든 정보를 제공한다.

: 무작위 과정의 모든 가능한 결과에 부여된 확률(probability)을 나열한 것이다.

​

- 균등분포 ( uniform distribution : 또는 고른 분포 )

: 모든 결과의 발생 가능성이 같다.

ex) 128비트 키를 무작위로 고르게 선택한다면 1/(2^128) 만큼 의 확률로 선택

​

- 비균등분포 ( non-uniform distribution )

: 확률들이 모두 같지는 않은 분포

ex) 동전 던지기에서 앞면과 뒷면이 나올 확률이 다르다고 가정할 때.

-> 이러한 동전을 가리켜 ' 편향되었다(biased) ' 라고 한다.

​

2.3 엔트로피 : 불확실성의 측도​

- 엔트로피

: 시스템에 존재하는 무질서의 측도(measure)

: 어떤 무작위 과정이 의외의 결과를 내는 경우가 얼마나 많은지를 나타내는 값

: 정보를 비트들의 개수로 표현할 수 있게 이진 로그를 사용

: 수식에서 음의 합을 사용하는 이유 : log(1/2) 면 (물론 이진로그) 음의 값이 나오기 때문에 엔트로피를 음수가 아닌 값으로 맞춰주기 위해서 음의 합 사용

: 엔트로피는 확률분포가 균등분포일 때 최대 ( 균등분포는 모든 확률이 같기 때문에 불확실성이 최대 )

-> 만약 5가지의 선택사항이 있을 때

a) 모든 확률은 1/5로 같음

b) 1/25, 18/25, 2/25, 3/25, 1/25 각각 이런 확률

그러면 a)는 모든 확률이 같기 때문에 무엇이 선택될 지 예측 불가능

b)는 2번이 선택될 것이라 예측 가능

** 정리를 해보면

엔트로피가 높다??? 예측이 어렵고, 랜덤하다.

​

2.4 난수 발생기(RNG)와 의사난수 발생기(PRNG)

암호 시스템은 무작위성을 얻기 위해 다음과 같은 구성요소를 갖추어야 한다.

1) 불확실성의 원천 또는 엔트로피원(source of entropy) : 난수 발생기 ( random number generator, RNG )가 담당

2) 엔트로피원으로부터 고품질 무작위 비트를 산출하는 암복호화 알고리즘 : 의사난수 발생기 ( pseudorandom number generators, PRNG )가 담당

- RNG : 디지털 시스템 안에서 아날로그 세계의 엔트로피를 이용해서 예측 불가능한 비트들을 산출하는 소프트웨어 또는 하드웨어 구성요소 ( ex) 온도, 음향적 잡음, 공기의 난류, 정전기, 시스템에 부착된 sensor, 입출력장치, 네트워크나 디스크활동, 시스템 로그, 실행중인 프로세스들, 키 입력이나 마우스 이동 등 )

-> 좋은 엔트로피원일 수 있지만, 공격자의 조작과 악용에 취약, 난수 비트들을 생성하는 속도 느림

- PRNG : 적은 수의 진정한 난수 비트들로부터 다수의 인위적인 난수 비트들을 신뢰성 있게 산출

​

RNG          vs          PRNG

          느리다                    빠르다 (비교적)

비결정론적                결정론적

엔트로피가 높다는 보장 X             최고의 엔트로피 보장

** 결정론적 : 예측 그대로 동작하는 알고리즘, 어떤 특정 입력이 들어오면 언제나 똑같은 과정을 거쳐 언제나 똑같은 결과를 내놓는다.

2.4.1 PRNG의 작동 방식

주기적으로 RNG로부터 받은 난수 비트들을 이용해서 큰 메모리 버퍼(entropy pool)의 내용을 갱신.

엔트로피 풀이 PRNG의 엔트로피원이다.

의사난수 비트열을 생성하기 위해 DRBG( Deterministic random bit generator, 결정론적 난수 비트 발생기 ) 알고리즘 실행. DRBG는 같은 입력을 넣으면 같은 출력이 나옴 -> 같은 입력을 두 번 제공하지 말아야 한다.

작동과정에서 PRNG는 다음 세 가지 연산 수행

1) init() : 엔트로피 풀, PRNG 내부 상태 초기화

2) refresh(R) : 어떤 자료 R( RNG 에서 얻은 자료 ) 을 이용해서 엔트로피 풀 갱신 -> 임의의 통계적 편향 제거

3) next(N) : N개의 의사난수 비트 생성 후 엔트로피 풀 갱신

​

2.4.2 보안 관련 문제

PRNG에 요구되는 몇 가지 고수준 사항

1) 역추적 저항성 ( backtracking resistance; 순방향 비밀성 ) : 이전에 생성된 비트들을 절대로 다시 생성할 수 없어야 한다. -> refresh, next 연산에서 내부 상태를 갱신할 때 수행되는 변환들이 비가역적이어야 한다.

2) 예측 저항성 ( prediction resistance; 역방향 비밀성 ) : 이후의 비트들을 예측하는 것이 불가능해야 한다. -> 공격자가 알지 못하고 추측하기 힘든 R 값으로 refresh를 호출해야한다.

​

2.4.4 암호학적 PRNG와 비암호학적 PRNG

비암호학 PRNG : 응용 프로그램에서 균등 분포 무작위 비트열을 산출하도록 설계된 것들, 안전하지 않다.

암호 PRNG : 잘 분포된 비트들을 산출하는 데 쓰이는 바탕 연산들의 강도에 신경 쓰기 때문에 예측 불가능.

하지만 여러 시스템에 쓰이는 것은 대부분 비암호 PRNG임.​​ ex) 메르센 트위스터

​

- 메르센 트위스터 ( Mersenne Twister, MT )

: PHP, 파이썬, R, Ruby를 비롯한 여러 시스템에 쓰이는 비암호 PRNG이다.

: 통계적 편향이 없는 균등분포 무작위 비트열을 생성하지만 예측 가능하다 -> 내부 작동 방식을 살펴보면 죄다 xor 을 통해서만 상호작용하기 때문이다.

* 비트들의 XOR 결합을 선형결합이라고 부른다. -> 선형결합은 예측이 가능하다. ( AND 결합은 비선형결합 )

​

2.5 실제로 쓰이는 PRNG들

데스크톱과 노트북, 네트워크 라우터나 센톱박스 같은 내장 시스템을 비롯한 대부분의 플랫폼은 운영체제 차원에서 암호학적 PRNG를 제공.

가장 널리 쓰이는 PRNG는

1) 여러 Unix 기반 시스템이 제공하는 것

2) Windows가 제공하는 것

3) 인텔 마이크로프로세서에 쓰이는 하드웨어 기반 PRNG 이다.

​

2.5.1 Unix 기반 시스템에서 무작위 비트 생성

장치파일 /dev/urandom 은 암호 PRNG를 제공하는 사용자 영역 인터페이스이다.

신뢰성 있는 무작위 비트들을 얻을 때 이 장치 파일을 생성한다.

리눅스가 사용하는 PRNG는 drivers/char/random.c 에 정의되어있고 SHA-1 해시 함수를 이용하여 원본 엔트로피 비트 -> 신뢰성 있는 의사난수 비트를 만듦.

/dev/urandom은 비차단 ( non-blocking ) 풀 , /dev/random은 차단 풀을 사용

** /dev/urandom 과 /dev/random은 무슨 차이일까?

/dev/random은 엔트로피 양을 추정하여 엔트로피 수준이 낮으면 비트들을 돌려주지 않는다. 이것이 좋은 방식인 것 같지만 신뢰성이 낮기로 악명이 높고, 공격자가 그것을 속여 넘길 수 있다고 한다.

그리고 추정된 엔트로피를 상당히 빨리 소진하여, 엔트로피가 높아지길 기다리느라 응용프로그램이 느려진다. (DOS 가능)

이래서 /dev/random은 별로라고 한다!!

​

2.5.2 Windows의 CryptGenRandom() 함수

예전 버전의 Windows 에서는 운영체제의 PRNG에 대한 사용자 영역 인터페이스로 CryptGenRandom() 함수가 쓰였다.

최근 버전의 Windows 에서는 Cryptography API: Next Generation(CNG) 라는 API의 BCryptGenRandom()함수가 쓰인다.

윈도우 PRNG는 커널 모드 드라이버 cng.sys(전에는 ksecdd.sys) 에서 엔트로피를 가져오는데 느슨하게 말하면 포르투나에 기초한다. (난수를 얻는 과정 꽤나 복잡)

CryptGenRandom() - 핸들을 이용하여 암복호화 문맥 얻어야함 -> 이 과정에서 잘못될 기회가 늘어남

BCryptGenRandom() - 핸들 없이 가능!

​

2.5.3 하드웨어 기반 PRNG: 인텔 마이크로프로세서의 RDRAND 명령

응용 프로그램은 RDRAND라는 어셈블리 명령을 통해 인텔의 이 PRNG에 접근.

운영체제와는 독립적인 인터페이스 제공, 이론상 소프트웨어 PRNG보다 빠름

​

2.6 문제 발생 요인들

다음 4가지의 예시를 보쟈!

​

2.6.1 불충분한 엔트로피원

- 넷스케이프 브라우저 SSL 구현은 128 비트 PRNG 종잣값을 계산할 때

global variable seed;
RNG_CREATEContext()
    (seconds, microseconds) = 하루 중 시간
    pid = 프로세스 id; ppid = 부모 프로세스 id; /* 각 15 비트 */
    a = mklcpr(microseconds);
    b = mklcpr(pid + seconds + (ppid << 12));
    seed = MD5(a, b);

mklcpr(x)
 return ((0xDEECE66D * x + 0x2BBB62DC) >> 1);

MD5()

이 의사코드에 따라 계산을 하는데

seconds 를 알아버리면 microseconds의 seconds/10^6 이므로 이 때 엔트로피가 log(10^6) 즉 약 20비트.. 여기서 큰 빵꾸가 나기 때문에 엔트로피가 128비트가 안된다.. 그래서 문제 발생함.

또한 b를 구하는 과정에서 ppid 를 왼쪽으로 12비트 shift 해서 3비트가 겹쳐버려서 여기서의 엔트로피 15(pid)+12(ppid) 이므로 3비트 빵꾸남 원래 15+15 여야 하는 데 그래서 문제 발생!!

​

2.6.2 시동 시점의 엔트로피 부족

시동(booting) 도중 아직 엔트로피가 충분히 수집되지 않은 시점에서 엔트로피를 계산하는 장치가 많다는 것을 조사를 통해 얻음 -> 엔트로피가 충분치 않다 보니 서로 다른 시스템의 PRNG들이 동일한 기본 엔트로피원으로부터 동일한 난수비트들을 생성 -> 동일 키 생성됨

prng.seed(종잣값)
p = prng.generate_random_prime()
q = prng.generate_random_prime()
n = p*q
/* 결과적으로 n이 같아지는 시스템 */

생성 도중에 추가적인 엔트로피 주입되는 키 생성 방안을 의사코드로 나타내면 아래와 같다.

prng.seed(종잣값)
p = prng.generate_random_prime()
prng.add_entropy()
q = prng.generate_random_prime()
n = p*q

이 시스템에서 p가 같다 하더라도 추가적인 엔트로피 주입으로 인해 n은 달라진다. 하지만 n과 n' 의 최대공약수를 계산하면 공통인 소인수인 p를 알아낼 수 있기에 문제가 생긴다. (문제 : 개인키를 알아낼 수 있음)

​

2.6.3 비암호 PRNG

앞서 말했듯이 비암호 PRNG는 안전하지 않다.

예를 들어 위키백과를 비롯한 여러 위키 사이트는 Media Wiki를 사용한다. Media Wiki는 무작위성을 활용해서 보안 토큰이나 임시 패스워드를 생성했으며 이때 mt_rand() 함수를 이용하여 생성했다. mt_rand()는 메르센 트위스터이다.. 예측 가능하단 소리! 그래서 안전하지 않다!!

​

2.6.4 무작위성은 강하지만 표본 추출에 문제가 있는 사례

Cryptocat 이라는 채팅 프로그램은 보안 통신을 제공하도록 설계되었다.

0~9 의 숫자들을 고르게 분포하려고 했는데 0부터 255까지의 모든 수를 10으로 나눈 나머지에서는 0~9가 고르게 분포되지 않는다. ( 1 byte = 8 bits 라서 0부터 255 )

그래서 이 개발자들은 다음과 같은 방법을 사용했다.

Cryptocat.random = function() {
    var x,o ='';
    while(o.length < 16) {
          x = state.getBytes(1);
          if(x[0] <=250)
              o += x[0] % 10;
     }
}

10의 특정 배수인 250을 조건으로 해서 그 미만의 수에서만 10으로 나눈 나머지를 취하고 그외는 버리는 방법을 사용했다. 근데 250을 10으로 나누면 0이라는 수가 한번 더 나오게 되서 균등하지 못하게 된다. 그래서 엔트로피가 낮아진다.

3학년 겨울방학을 알차게 보내기 위해서 동아리에서 진행하는 암호 스터디를 신청하였다!!

책 이름은 "Serious Cryptography 처음 배우는 암호화"이다.

모든 챕터마다 간단하게 요약정리해서 글로 남기기로 했다.

​

암호화를 위해서는 알고리즘(암호) + 비밀 값(키 or 열쇠) 필요!

1) 대칭 암호화(symmetric encryption) : 암호화에 사용하는 키=복호화(decryption)에 사용하는 키

- 장점 : 빠르다.

- 단점 : 키를 주고받을 때 안전하지 않을 수 있다.

2) 비대칭 암호화(asymmetric encryption), 공개 키 암호화(public-key encryption) : 암호화에 사용하는 키 != 복호화에 사용하는 키

- 장점 : 키를 주고받지 않아도 안전하게 통신할 수 있다.

- 단점 : 느리다.

​

1.1 기초

평문(plaintext) ---(암호화)--->​ 암호문(ciphertext)

평문(plaintext) <---(복호화)---​ 암호문(ciphertext)

​

암호문 C = E( K , P )으로 표기

복호문 P = D( K , C )으로 표기

​

** 암호문이 평문보다 짧은 암호는 없다!!

​

1.2 고전암호(classical cipher)

고전암호에는 대표적으로 시저암호와 비즈네르 암호가 있다.

​

1.2.1 시저 암호(Caesar cipher)

: 각 글자에서 3자리 뒤로 순환 이동 ( ex) A -> D ) -> 키가 3이라는 뜻!

: 복호화 하기 위해서는 3자리 앞으로 이동하면 됨 -> 깨기 쉬움

​

1.2.2 비즈네르 암호(Vigenere cipher)

: 시저 암호와 비슷, but 키가 일련의 글자로 이루어져 있음.

ex) 키가 DUH라고 가정하면, D는 A와 3차이, U는 20차이, H는 7 차이 -> 평문을 3자리씩 잘라서(키의 길이만큼) 3,20,7씩 이동

평문 : CRYPTO

키 : DUH

암호문 : FLFSNV ( C가 3만큼 뒤로 이동하면 F, R이 20만큼 뒤로 이동하면 L 이런 식으로 암호화 )

: 암호를 깨기 위해서는

1) 키의 길이 알아내기

- 예를 들어 암호문이 ABCJKIDJEABC 라고 치면 같은 패턴(ABC)이 9자리 간격으로 생김. 그러면 키의 길이를 9의 약수 중 하나라고 추론하는 것

2) 도수분석 ( frequency analysis; 또는 빈도분석 )

- 암호문에서 문자들의 빈도를 분석해서 제일 많은 문자를 E가 암호화되었다고 생각한다. ( 영어에서 가장 흔히 쓰이는 글자가 E, T, A, O, I 순이기 때문에 )

↓ english letter frequency ranking

1.3 암호의 작동 방식

암호의 주된 구성요소 = 치환 ( permutation ) , 운영모드 ( mode of operation; 운용 방식 )

- 치환 : 주어진 한 항목을 변환하는 함수 ( 조건 : 고유한 역원 존재해야 함 )

- 운영모드 : 치환을 이용해서 임의의 길이의 메시지를 처리하는 데 쓰이는 알고리즘

​

1.3.1 치환

고전암호는 대입 ( substitution ; 대체 )을 수행. -> substitution은 한 문자를 다른 문자로 바꿔서 confusion의 목적을 둠

암호를 위한 대입은 반드시 치환이어야 한다. -> 각 글자에 정확히 하나의 역원이 존재해야 한다.

"안전한 치환 ( secure permutation )" -> permutation은 문장 순서를 바꿔서 diffusion의 목적을 둠

1) 치환은 반드시 키로 결정되어야 함.

2) 키가 다르면 치환도 다름.

3) 무작위 해 보여야 함.

​

1.3.2 운영 모드

만약 평문에 BANANA와 같이 특정 패턴이 있어버리면 암호문에도 이것이 드러나게 된다.

운영모드를 사용하여 중복 글자 패턴이 드러나는 문제를 완화한다.

ex) ECB, CBC, CFB, OFB, CTR

​

1.4 OTP ( One Time Pad )

가장 안전한 암호 : 키가 엄청나게 길고 한번 쓰고 버림

bitwise XOR 연산을 통해서 암호화, 복호화를 한다.

키는 평문의 길이와 같으며 키를 위한 또 다른 공간이 존재해야 해서 활용하기 불편. ( 공간상의 낭비 )

완벽한 보안성을 달성하려면 키가 평문보다 짧아서는 안된다.

​

1.5 암호의 보안성

어떠한 시스템이 안전하다? 보안개념(security notion) 을 서술해야 함.

보안 개념은 보안목표 - 공격 모형 형태로 나타냄.

​

1.5.1 공격 모형

- 케르크호프스의 원리 ( Kerckhoffs's principle ) : 한 암호의 보안성은 오직 키의 비밀성에만 의존해야 한다. -> 적이 암호시스템 훔쳐 가도 문제가 되어서는 안된다. --> 모든 모형이 공통적으로 두는 가정

1) 공격 모형 - 블랙박스 모형

- COA ( ciphertext-only attackers ) : 공격자가 불리한 공격 , 암호문만 알뿐 해당 평문 알지 못함. 암호화 질의 X, 복호화 질의 X

- KPA ( known-plaintext attackers ) : 암호문에 대응하는 일부 평문을 알 수 있다, 암호문과 평문과의 관계로부터 키와 전체 평문을 추정하여 해독, 암호화 질의 X, 복호화 질의 X

- CPA ( chosen-plaintext attackers ) : 암호화 질의 O

- CCA ( chosen-ciphertext attackers ) : 암호화 질의 O, 복호화 질의 O

2) 공격 모형 - 그레이박스 모형

: 암호의 구현( implementation) 에 접근 가능

: 시스템에 물리적으로 접근해서 알고리즘 내부를 건드릴 수 있다.

- 부채널 공격(side-channel attack) : 공격자는 아날로그 특성을 관찰, 측정만 하여 구현의 무결성을 훼손 X

- 침습적 공격(invasive attack) : 암호 구현을 강하게 공격 , 구현의 무결성을 훼손할 수도 있다.

+ 공격 모형에 화이트박스 모형도 있음ㅎㅎ

1.5.2 보안 목표

- 비구별성(indistinguishability, IND) : 암호문은 무작위 문자열과 구분할 수 없어야 안전하다.

- 비가소성(non-malleability, NM) : 어떤 평문에 대한 암호문을 안다고 해서, 다른 평문에 대한 암호문을 얻을 수 없어야 안전하다.

​

1.5.3 보안 개념

- 의미론적 보안 IND-CPA

목적 : 키의 비밀이 유지되는 한 공격자가 암호문으로부터 평문에 관해 그 어떤 정보도 알아내지 못해야한다.

-> 이를 위해 무작위 암호화 ( randomized encryption ) 사용 , 이때 DRBG(결정론적 무작위 비트 발생기) 사용

** 보안 개념들의 함의 관계 -> 교수님께 여쭤보기 ㅜㅜ

​

1.6 비대칭 암호화

- 키가 2개 사용됨

- 암호화할 때는 receiver의 공개키를 사용

- 복호화할 때는 receiver의 개인키를 사용

- 공개키를 가지고 있는 사람이면 누구나 암호화 질의를 수행할 수 있다. -> 기본 공격 모형 : CPA

* 하이브리드 암호시스템 ( 대칭 암호화와 비대칭 암호화의 조합 )

-> 대칭 암호화의 장점 : 빠르다.

-> 비대칭 암호화의 장점 : 키를 안 주고 받아도 된다.

하이브리드 암호시스템의 암호화 과정

1.7 암 · 복호화 이외의 암호의 용도

1) 인증 암호화 ( Authenticated encryption, AE )

: 암호화하면 인증값 T 을 같이 돌려준다.

- AEAD ( Authenticated encryption with associated data )

: 흔히 평문 헤더와 암호화된 페이로드 ex) 네트워크 패킷들을 전송하기 위해서 목적지 주소는 평문이어야한다.

2) 형태 보존 암호화 ( format - preserving encryption, FPE )

: 평문과 같은 형태의 암호문을 생성!! ex) IP주소를 IP주소로 암호화, ZIP 코드( 미국의 우편번호 )를 ZIP코드로 암호화

3) 완전 준동형 암호화 ( fully homomorphic encryption, FHE )

: 암호문을 복호화하지 않고 또 다른 암호문으로 바꿈

: 느리다!!

4) 검색 기능 암호화 ( searchable encryption )

: 암호화된 데이터베이스에 대한 검색 가능

: 검색 질의 자체를 암호화해서 검색어 유출 방지

ex) 내가 클라우드에 고객들의 정보를 저장한다고 했을 때, '김포렌' 라는 고객의 정보를 알고 싶어서 쿼리를 날리면 검색 기능 암호화를 지원하면 '김포렌'를 암호화해서 암호화된 데이터베이스에 접근하여 정보를 나에게 다시 보내주고 우리는 그것을 복호화 해서 보면 된다. -> 마음 놓고 클라우드 서비스를 이용할 수 있다. ( 안전하기 때문 )

5) 조율 가능 암호화 ( tweakable encryption, TE )

: 조율값(tweak)이라고 부르는 추가적인 매개변수 있다.

: 주된 용도는 디스크 암호화 -> 저장 장치의 내용을 암호화 하는 데 쓰임. ( 무작위 암호화 같은 경우는 자료의 길이가 길어지기 때문에 사용할 수 없음, 암호화때문에 길이가 길어지면,,, 납득 불가! )

: 암호화되는 자료의 위치( 디스크 내의 섹터 번호, 블록 색인 )에 의존하는 조율값 활용