What is cryptography?
What is cryptography?
암호 메커니즘 : 공유키를 가지고 메시지 교환 ⇒ 기밀성, 무결성 제공
Digital signatures(디지털 서명)
Anonymous communication(익명 통신) - mix net 누군지 알지 못해도 양방향 통신은 가능
ex) 현금 사용에서 개인의 익명성, 비밀 투표, 경매
암호화 응용 프로그램의 종류
1. Pivately outsourcing computation
ex) 사용자 검색 → 구글은 검색한 결과를 알지 X 쿼리의 암호화. → 사용자에게 암호 계산 결과 출력
2. Zero Knowledge
ex) Alice 는 N의 인수분해를 알고 있다. 이때 N은 두 개의 1000자리 소수의 곱. Bob은 N만 가지고 있음.
Alice가 N의 인수분해를 알고있음을 Bob에게 증명 가능
History of Cyptograpy
Symmetric Ciphers(대칭암호)
Alice와 Bob 사이 도청하려는 공격자가 있고 안전하게 통신하기 위한 비밀키 K가 있다. (E 암호화 D 복호화 메시지 M)
E는 M을 입력으로 사용. K를 입력으로 받는다. K를 사용하여 M을 암호화한다.
Bob은 암호 해독알고리즘에 K사용.
⇒ 암호화, 복호화 과정에 동일한 키 사용 ⇒ 대칭암호
Substitution cipher(대체 암호)
대체 암호의 키는 문자를 매핑하는 방법을 알려주는 대체 테이블. (A는 C에 매핑, B는 W에 매핑, C는 N, Z는 A)
메시지가 BCZA 암호화 ⇒ WNAC
카이사르 암호
: 같은 키를 사용하여 암호문 해독. 키가 고정된 방식으로 보안에 취약하다
1. 암호문을 보고 문자가 몇 번 나타나는지 세기 ⇒ 가장 일반적인 문자는 E일 확률이 높음 ⇒ 그 다음 흔한 문자는 T일 확률이 높음
2. 문자쌍의 빈도 세기 ⇒ HE, AN 순으로 흔함Vigener 암호
: 암호키는 단어
메시지를 덮는데 필요한 만큼 키 복제.(+Mod 26)
키의 길이 알고있을 때 각 그룹의 첫글자 살펴보기(H가 가장 많다고 가정)
⇒ 가장 일반적인 문자는 E의 암호화일 가능성이 높음
⇒ E에 키의 첫 번째 문자를 더한 것 = H
⇒ 키의 첫 번째 문자 = H-E
Hebern machine
비밀키가 디스크 안에 내장. 타자키를 누를 때마다 디스크 한 단계씩 회전하며 대체 테이블 인코딩
Enigma
비밀키는 로터의 초기 설정
ex) 4개의 로터를 가진 에니그마 → 키의 수는 26의 4
1974년 IBM에서 암호화의 표준 DES
keys : 2의 56승, 64비트(8자씩) 암호
Crash course in discrete probability
Uniform distribution(균일 분포) : 모든 요소에 동일한 가중치 부여
Point distribution
Point 에 가중치 할당. 다른 점에 대해서 가중치 0
random Vairables
U에 대한 확률 분포 P: U의 모든 요소에 0에서 1 사이의 가중치를 할당하는 함수
사건의 확률 : 가중치의 합
랜덤 변수 A ; V의 분포 정의
independence
사건 [A and B] = 사건 A * 사건 B
Xor
XOR 연산은 비트가 같으면 0, 다르면 1을 반환
Stream Ciphers 1: the one-time pad and stream ciphers
K 가능한 모든 키의 집합
M 가능한 모든 메시지의 집합
C 가능한 모든 암호문 세트
E(암호화) : K M ⇒ C D(복호화) : KC⇒M
The One Time Pad
- 키스트림 생성: 암호화를 위한 무작위의 키스트림을 생성. 키스트림은 메시지의 길이와 동일한 길이를 가지며, 이 키스트림은 오직 한 번만 사용.
- 메시지 암호화: 평문 메시지의 각 비트를 키스트림의 해당 비트와 XOR 연산을 수행하여 암호화.
- 메시지 복호화: 암호화된 메시지를 키스트림과 XOR 연산을 수행하여 원래의 평문 메시지를 복원
Shannon
- 트리플 KM과 C에 대한 정의된 Cypher ED: 키 공간(KM), 메시지 공간 및 암호 텍스트 공간(C)을 포함. 암호화에 필요한 구성 요소.
- 메시지 M0과 M1, 메시지 길이: 암호화를 위한 메시지로 M0과 M1을 사용하며, 두 메시지의 길이는 동일하다고 가정
- 암호화 및 복호화 과정: 메시지 M0과 M1을 암호화하여 암호문 C를 생성, 암호문 C를 복호화하여 메시지 M0 또는 M1을 얻음
- 확률과 완벽한 비밀성: Shannon은 키 K를 사용하여 M0을 암호화한 결과가 C가 되는 확률과 키 K를 사용하여 M1을 암호화한 결과가 C가 되는 확률이 동일하다고 가정. 이러한 확률이 동일하다면 암호화된 C만으로는 원래 메시지가 M0인지 M1인지 알 수 없다는 것을 의미 ⇒ 완벽한 비밀성
- 키의 균일한 분포: 키 K는 균일한 분포를 가져야 한다고 가정. 키를 선택할 때 어떤 키가 선택될 확률이 모든 키에 대해 동일.
Stream Ciphers and Pseudo Random Generators
선형합동생성기
- 초기값 R0 설정 : 시드(seed)
- 다음의 과정 반복
- Ri+1 = (A * Ri + B) mod P
- Ri+1 값을 출력 or 필요한 비트를 추출
- i 증가
Attacks on Stream Ciphers and The One Time Pad
Two Time Pad의 보안 취약성 : 동일한 패드로 둘 이상의 메시지를 암호화할 경우 C1,C2의 XOR을 이용해 두 메시지를 완전 복구 가능
Wired Equivalent Privacy (WEP)
- 키 공유: 클라이언트와 액세스 포인트는 비밀 키 K를 공유. 암호화와 복호화에 사용.
- 메시지 암호화: 클라이언트가 메시지를 암호화하여 액세스 포인트에게 전송하려고 할 때,
- 체크섬 추가: 클라이언트는 평문 메시지 M에 에러 검출을 위한 체크섬 추가.
- IV 사용: 클라이언트는 초기화 벡터(IV)라는 24비트 값과 키 K를 결합하여 스트림 암호를 초기화. IV는 각 프레임마다 변경되며, 암호화에 사용됨.
- 암호화: 클라이언트는 메시지와 IV를 결합하여 암호화.
- 복호화: 액세스 포인트는 암호문과 IV를 받아들이고, 키 K와 IV를 결합하여 동일한 스트림 암호를 초기화. 암호문을 복호화하여 원래의 메시지 M을 얻음
주요 취약점:
- IV의 한계: IV는 24비트로 길이가 제한되어 있기 때문에, 가능한 IV의 수는 제한적. 같은 키로 암호화된 여러 개의 프레임이 동일한 IV 사용.
- IV 순환 문제
- 약한 키 스트림: WEP에서 사용되는 키 스트림은 예측 가능하며, 보안성이 낮음
- 재사용된 IV: 액세스 포인트나 클라이언트가 재부팅될 때마다 IV가 초기화되며, 이로 인해 동일한 IV와 키로 암호화된 패킷이 중복해서 생성 될 수 있음
- 암호화 알고리즘 취약성: WEP에서 사용된 RC4 암호화 알고리즘에는 키 스트림을 예측할 수 있는 공격이 가능
Real-World Stream Ciphers
RC4
- RC4의 출력 편향
- RC4의 두 번째 공격: 긴 RC4 출력 시퀀스에서 '00'이 나타날 가능성이 높다
- WEP와 관련한 공격
css
CSS는 선형 피드백 시프트 레지스터(LFSR) 기반
두 개의 LFSR을 사용하며, 이들의 초기 상태를 찾는 공격을 사용하여 암호화를 깨뜨림
초기 상태를 찾기 위해 가능한 초기값을 시도, LFSR을 실행하여 출력과 실제 CSS 출력을 비교다.
논스(nonce) "한 번만 사용되는 숫자"
⇒ 암호화의 예측 불가능성 보안성 증가 (키 재사용 가능)
- 키와 논스를 결합하여 초기 상태 설정
- 초기 상태에서 스트림 암호의 내부 동작에 의해 연속적인 출력 생성
- 각 출력은 평문과 XOR 연산을 통해 암호화
논스는 각 암호화 작업에서 다른 값을 가지므로, 같은 키를 사용해도 논스의 변화에 따라 다른 출력이 생성된다.
PRG Security Definitions
- 생성기 G는 2/3의 확률로 출력의 첫 번째 비트를 1로 만듬
- 설계된 통계 테스트는 입력 데이터의 중요한 부분이 1이면 "1"을, 아니면 "0"을 출력
- 효과적인 통계 테스트는 생성기 G의 무작위성과 특성을 활용해 데이터와 구별할 수 있는 이점이 있어야 함
- 안전한 난수 생성기는 효율적인 통계 테스트로부터 생성된 데이터를 예측하기 어렵게 만들어 무작위성을 보장
Semantic Security
- 시맨틱 보안(Semantic Security): 암호화된 정보가 외부 공격자에게 노출되었을 때 평문 정보를 얻기 어렵다는 개념
- Shannon의 완전 비밀성 개념: 공격자가 암호문을 통해 원본 메시지를 유추하는데 어떠한 정보도 얻을 수 없어야 한다는 것을 의미
- 암호화 시스템의 구성: 두 개의 메시지 M0과 M1이 주어지고, M1은 M0과 연결되어 있는 상황을 가정했을 때 암호화 시스템은 M0을 암호화하고, M1을 암호화하는 방식으로 동작
- One Time Pad (원타임 패드): 원타임 패드는 매우 강력한 암호화 기법 중 하나로, 무작위 키를 사용하여 메시지를 XOR 연산하는 방식으로 암호화
