Week 6 - 난수, 해쉬 키, HMAC, RSA 공개키 암호화

1️⃣ 해시 함수

🔍 해시 함수 요구사항

1. 어떤 크기의 데이터 블록에도 적용 가능함
• 해시 함수는 데이터 크기에 상관없이 입력으로 받아들일 수 있다.

2. 고정된 길이의 출력 값 생성
• 입력 데이터 크기가 달라도 해시 함수는 항상 일정한 크기의 해시 값을 출력한다. 예를 들어, 입력이 1MB든 1GB든 256비트의 고정된 출력값을 생성하는 것과 같다.

3. 주어진 어떤 x에 대해 H(x)는 상대적으로 산출이 용이s 함
• 연산 속도가 중요한데, 입력값에 대해 해시 값을 빠르게 계산할 수 있어야 한다는 특징이다.

4. 단방향성 또는 역상저항성 (Pre-image Resistant)
• 단방향성이란 주어진 해시 값에서 원래의 입력값을 찾아내는 것이 매우 어려워야 한다는 것을 의미한다. 해시 값 h에 대해 이를 만족하는 x를 계산하는 것은 사실상 불가능해야 한다.

5. 제2 역상저항성 또는 약한 충돌 방지 (Second Pre-image Resistant)
• 주어진 입력 x에 대해 같은 해시 값을 가지는 다른 입력 y (y ≠ x)를 찾는 것이 어려워야 한다는 특성이다. 즉, 이미 알려진 해시 값을 가진 또 다른 입력값을 찾는 것은 매우 어려워야 한다.
이는 생일이 같은 사람을 찾는 것이 오늘이 생일인 사람을 찾는 것보다 쉽다는 것을 의미한다.

6. 충돌 저항성 또는 강한 충돌 방지 (Collision Resistant)
• 해시 함수는 서로 다른 두 입력값 x, y (x ≠ y)에 대해 같은 해시 값을 가지는 상황(충돌)을 발생시키기 어렵도록 설계되어야 한다. 이러한 충돌 저항성은 해시 함수가 암호학적으로 안전하게 사용될 수 있도록 하기 위해 중요하다.

🔍 해시 함수 보안성

1. 안전한 해시 함수를 공격하는 두 가지 접근:
• 암호 해독 공격:
• 알고리즘의 논리적 약점을 이용하여 해시 값을 역으로 계산하거나, 원래 입력값을 추정하는 시도이다. 이러한 공격은 해시 함수 알고리즘의 설계 오류를 이용하여 가능해진다.
• 무차별 대입 공격 (Brute Force Attack):
• 해시 함수는 일반적으로 고정된 길이의 해시 코드를 생성하는데, 이는 공격자가 모든 가능한 입력값을 대입해 해시 값을 맞추는 방식으로 공격할 수 있다는 것을 의미한다. 해시 길이가 짧을수록 무차별 대입 공격에 취약하다.

2. SHA (Secure Hash Algorithm)
• SHA는 가장 널리 사용되는 해시 알고리즘이다. 다양한 버전이 있으며, 일반적으로 SHA-1, SHA-256 등이 많이 사용된다. 이 알고리즘은 해시 함수의 안전성을 높이기 위해 설계되었으며, 데이터 무결성 검증 및 암호화 응용에서 자주 사용된다.

3. 안전한 기타 해시 어플리케이션:
• 패스워드:
• 사용자의 패스워드는 일반적으로 운영체제에 저장될 때 해시 값을 계산하여 저장된다. 이를 통해 원래 패스워드를 직접적으로 저장하지 않고 해시 값을 비교함으로써 보안을 강화한다.
• 침입 탐지:
• 각 파일에 대해 해시 값 H(F)를 시스템에 저장해 두고, 파일이 변경되었는지 여부를 쉽게 확인할 수 있다. 이는 파일 무결성 검사와 같은 역할을 하며, 시스템 침입 시 데이터를 보호하는 데 유용하다.

⚙ 보안 해시 함수

 

📌 보안 해시 함수의 특징

1. 각 비트 위치에 대한 단순 패리티 생성:
• 해시 함수는 입력 데이터의 각 비트 위치에 대해 간단한 패리티(짝수 또는 홀수)를 생성하여 무결성을 검사한다.

2. 세로 중복 검사:
• 입력 데이터가 여러 블록으로 나누어졌을 때 각 블록에서 동일한 비트 위치를 비교하여 중복성을 검사하는 방식이다.

3. 무결성 검사에 유효:
• 보안 해시 함수는 메시지 인증과 데이터의 무결성 검사를 위해 사용된다. 예를 들어, 데이터를 전송할 때 전송 중 변조가 발생했는지 확인하기 위해 사용된다.

4. n-비트 해시 값의 균등 분포:
• n-비트 해시 함수는 해시 값이 균등하게 분포하도록 설계되어야 한다. 이를 통해 에러를 감지할 확률이 1/2^n 정도로 유지된다. 균등한 분포는 충돌 가능성을 낮추어 보안을 강화하는 역할을 한다.

5. 데이터 포맷팅에 따른 취약성:
• 특정 형태의 데이터 포맷, 예를 들어 정형화된 데이터(각 텍스트 파일에서 최상위 비트는 항상 0인 경우)에서는 해시 함수가 취약할 수 있다. 이런 경우에는 충분히 무작위적인 해시 값 분포를 유지하기 어렵기 때문에 보안성이 떨어진다.
• 예를 들어, 128비트 해시 함수가 적용되어도 비트가 정형화된 데이터에서는 2^(-112)의 유효성을 가질 수 있다.

6. Randomizing (무작위화):
• 해시 함수의 취약점을 극복하기 위해 데이터의 규칙성을 없애는 무작위화 기법을 사용한다. 이를 통해 동일한 데이터에 대해서도 다양한 해시 값을 가지게 하여 해시 함수의 충돌 가능성을 낮춘다.

🔍 보안 해시 알고리즘 (SHA)

⚙️ SHA-512 구조

1. 메시지 분할 및 패딩:
• 입력 메시지는 1024비트 블록으로 분할된다.
• 마지막 블록이 1024비트보다 짧다면 패딩이 추가된다. 여기서 패딩은 1 비트와 뒤따르는 0 비트들, 그리고 마지막에 메시지의 길이를 128비트로 표현한 부분이 포함된다.

2. 초기 벡터 설정:
• 해시 계산의 시작점으로 IV(Initial Vector) 또는 H₀ 값이 사용된다. 이는 SHA-512에서 미리 정의된 512비트의 초기값이다.

3. 해시 계산 과정:
• 각 1024비트 블록 (M₁, M₂, ..., )은 순차적으로 압축 함수 F를 사용해 처리된다.
• 첫 번째 블록 M₁은 초기 벡터 H₀와 함께 함수 F에 입력되고, 그 결과는 H₁이 된다.
• 이후 각 블록은 이전의 해시 값과 다음 블록의 데이터를 조합하여 계산된다. 즉, H₁이 다음 블록 M₂와 함께 함수 F에 입력되어 H₂를 얻고, 이 과정을 반복하여 마지막 해시 값 까지 계산한다.

4. 최종 해시 값:
• 각 단계의 결과는 word-by-word 덧셈(mod ) 연산으로 다음 단계의 입력과 결합된다.
• 마지막 블록까지 모든 해시 계산이 완료되면, 결과로 나온 이 최종 해시 코드로 사용된다.

1. 초기 상태 설정 (a, b, c, d, e, f, g, h):
• 입력 메시지 블록 Mᵢ와 이전의 해시 값 Hᵢ₋₁이 함께 입력되며, 8개의 레지스터 (a, b, c, d, e, f, g, h)로 구성된 초기 상태가 설정된다. 이 레지스터들은 중간 해시 값을 저장하고 업데이트하는 역할을 한다.

2. 80 라운드 반복 수행:
• 80 라운드가 수행되며, 각 라운드에서는 입력 메시지 Wₜ와 미리 정의된 상수 Kₜ가 사용된다.
• 각 라운드는 레지스터들 (a부터 h)의 값을 조정하고 업데이트하며, 각각의 레지스터가 압축 함수 역할을 한다. 각 라운드는 메시지와 상수의 조합으로 해시 상태를 갱신한다.

3. 최종 상태 계산:
• 80 라운드가 끝나면, 최종 상태의 값들이 초기 값에 word-by-word 덧셈(mod 2⁶⁴)을 통해 합산된다.
• 이 최종 합산된 값이 새로운 중간 해시 값 Hᵢ가 되며, 다음 메시지 블록의 처리에 사용된다.

4. 각 레지스터의 역할:
• a, b, c, d, e, f, g, h는 해시 상태를 나타내며, 매 라운드마다 서로의 값에 영향을 주면서 갱신된다.
• 최종적으로 모든 라운드가 끝난 후, 각 레지스터의 값이 합산되어 새로운 해시 값이 생성된다.

1. 메시지 분할 및 패딩:
• 메시지는 1024비트 크기의 블록으로 나누어지며, 각 블록에는 패딩이 추가되어야 한다. 마지막 메시지의 길이를 나타내는 부분도 포함되어 있다.
• 이 단계에서 메시지가 M₁, M₂, ..., 와 같은 개별 1024비트 블록으로 준비된다.

2. 초기 벡터 설정 (IV):
• 초기 해시 값인 H₀이 설정된다. 이 값은 SHA-512에서 미리 정의된 512비트의 초기값이다.
• 이 초기 값은 첫 번째 메시지 블록 M₁과 결합되어 첫 번째 라운드 계산을 시작한다.

3. 해시 계산 과정 (메시지 블록 처리):
• 각 메시지 블록 (M₁, M₂, ...)는 순차적으로 라운드 계산을 통해 처리된다.
• 각 메시지 블록은 80번의 라운드 반복 연산을 수행하며, 이 과정에서 a, b, c, d, e, f, g, h와 같은 초기 해시 버퍼가 사용된다. 이 버퍼들은 매 라운드마다 갱신되며, 중간 해시 값으로 저장된다.
• 첫 번째 블록 M₁은 초기 해시 값 H₀와 함께 함수 F에 입력되고, 그 결과는 H₁이 된다.
• 이후 H₁은 다음 블록 M₂와 함께 다시 라운드 계산을 거쳐 H₂를 생성한다. 이 과정이 반복되면서 각 메시지 블록이 처리되고, 최종적인 해시 값으로 이어진다.

4. 최종 해시 값:
• 모든 메시지 블록이 처리된 후 마지막 블록의 해시 값 ()이 최종 해시 값으로 반환된다.
• 이 최종 해시 값은 입력 메시지 전체에 대한 고유한 요약 정보로 사용된다.