각진 세상에 둥근 춤을 추자
암호 키 생성: 결정론적 난수발생기(DRBG) 본문
암호 키 생성 방법으로는 다음과 같이 나눌 수 있다.
1. 난수발생기(RBG)의 이용
2. 비대칭키 알고리즘의 키 생성
3. 대칭키 알고리즘의 키 생성
난수는 암호화 키, 인증 토큰, 디지털 서명 등 다양한 보안 요소를 안전하게 보호하는 핵심 요소로 사용된다.
난수 생성기는 이와 같은 난수를 생성하는 장치나 알고리즘으로, 보안 시스템에서 필수적인 구성 요소 중 하나이다.
난수 생성기는 크게 진정한 난수발생기(TRNG)와 결정론적 난수발생기(DRBG)로 나눌 수 있다.
그 중 결정론적 난수발생기(DRBG)에 대해 알아본다.
국내 표준인 KS X ISO/IEC 18031은 이러한 결정론적 난수발생기에 대해 다루고 있으며, 이는 NIST SP 800-90에서 정의한 DRBG와 동일한 기법을 사용한다.
| 용어 | 설명 |
| 시드 (Seed) |
난수 발생기에서 난수를 생성하기 위한 초기값 |
| 논스 (Nonce) |
인스턴스 생성 과정에서 시드를 만들기 위해 단 한 번 사용되는 예측할 수 없는 값 (예: 타임스탬프, 일련번호 등) |
| 내부상태 (Internal State) |
DRBG가 난수를 생성하기 위해 사용하는 현재의 상태 정보로, 시드 값과 이 값을 기반으로 생성된 난수 생성에 필요한 여러 값들이 포함되어 있다. |
| 엔트로피 입력 (Entropy Input) |
DRBG에서 제공되는 무작위 정보로, 난수의 예측 불가능성을 보장하기 위한 필수 요소 (비밀정보) |
| 개별화 문자열 (Personalization String) |
인스턴스 생성과정에서 시드를 생성하기 위해서 사용되어지는 값 (비밀정보일 필요는 없다) |
| 추가 입력 (Additional Input) |
DRBG가 난수를 생성할 때 추가적으로 입력되는 임의의 데이터, 필수 요소는 아니다. |
결정론적 난수발생기(DRBG, Deterministic Random Bit Generator)
결정론적 난수발생기는 초기 시드(seed) 값을 기반으로 암호학적으로 안전한 난수를 생성하는 알고리즘이다.
결정론적 난수발생기에는 여러 가지 종류가 있으며, 그 중에서 Hash_DRBG와 HMAC_DRBG가 있다.
둘다 NIST SP 800-90에 정의된 결정론적 난수발생기의 종류 중 일부이다.
인스턴스 생성 함수, 생성 함수, 리씨드 함수는 DRBG의 기본적인 함수들로 각각 초기화, 난수 생성, 시드 재설정을 담당한다.
| 난수 발생기 메커니즘 함수 | 설명 |
| 인스턴스 생성 함수 (Instantiate Function) |
엔트로피 입력, 논스, 개별화 문자열을 결합하여 초기 내부 상태를 구성하는 시드를 생성한다. |
| 생성 함수 (Generate Function) |
난수 생성 요청이 있을 때 현재 내부 상태에서 난수를 발생시키고, 다음 요청을 위해 새로운 내부 상태로 변경시킨다. |
| 리씨드 함수 (Ressed Function) |
새로운 시드를 이용해 내부 상태를 갱신한다. |
| 인스턴스 소멸함수 (Uninstantiate Function) |
내부 상태를 제로화시킨다. |
개별화 문자열, 논스, 추가입력은 난수 발생기의 선택적 구성 요소이며 나머지는 모두 기본 구성 요소이다.
1. Hash_DRBG (Hash-based Deterministic Random Bit Generator)
해시 함수(Hash Function)를 기반으로 난수를 생성하는 방식이다.
주로 SHA-256, SHA-512와 같은 암호화 해시 함수를 사용하여 난수를 생성한다.
시드 값과 내부 상태를 기반으로 해시 함수를 반본적으로 적용하여 난수를 생성한다. 해시 함수의 특성상 동일한 입력값이 주어지면 항상 같은 출력값이 나오기 때문에, 시드 값이 같으면 동일한 난수열이 생성된다.
2. HMAC_DRBG (HMAC-based Deterministic Random Bit Generator)
HMAC(Hash-based Message Authentication Code) 알고리즘을 기반으로 난수를 생성하는 방식이다.
HMAC은 키가 포함된 해시 함수로 내부적으로는 SHA-256, SHA-512 등의 해시 함수와 비밀키를 사용하여 난수를 생성한다.
KS X ISO/IEC 18031에 준수하는 결정론적 난수발생기(DRBG)를 사용하려면 다음과 같은 요구사항을 충족해야 한다.
1. 엔트로피 소스의 무작위성 및 보안성
- DRBG는 예측 불가능한 난수를 생성하기 위해 충분한 엔트로피 소스를 사용해야 한다. 해당 엔트로피는 외부에서 제공되며, 진정한 무작위성을 보장할 수 있어야 한다.
- 엔트로피 소스는 가능한 한 하드웨어 기반의 무작위 소스를 활용하여 보안성을 높인다.
2. 초기 시드 값 설정 및 리시드
- 초기 시드 값은 안전하게 설정되어야 하며, 필요할 때 주기적으로 리씨드 작업을 수행하여 난수 발생기의 예측 가능성을 최소화한다.
- 일정한 기간이 지나거나 새로운 엔트로피가 필요한 경우 DRBG는 새로운 시드를 받아 주기적으로 리씨드 작업을 한다.
3. 암호학적 알고리즘 기반
- DRBG는 암호학적으로 안전한 알고리즘(Hash_DRBG, HMAC_DRBG 등)을 사용해 난수를 생성한다.
4. 내부 상태 관리
- DRBG의 내부 상태는 언제나 안전하게 관리되어야 한다.
- 내부 상태가 변경되거나 리씨드될 때마다, 새롭게 생성되는 난수는 이전의 난수와 연관되지 않아야 한다.
5. 개별화 문자열 및 추가 입력 처리
- DRBG는 개별화 문자열을 사용하여 난수의 출력을 고유하게 만들어야 한다. 이는 동일한 DRBG가 다른 시스템이나 사용 환경에서 각기 다른 난수를 생성한다.
- 추가 입력을 통해 더 안전하고 무작위적인 난수를 생성해야 한다.
6. 테스트 및 검증
- DRBG의 품질은 지속적으로 테스트되고 검증되어야 한다.
DRBG로 난수를 생성하는 순서
1. 엔트로피 수집
2. 시드 설정
3. 내부 상태 초기화
4. 난수 생성
5. 리씨드 (필요시)
6. 난수 출력 및 사용
1. 엔트로피 입력 수집
난수 생성기는 처음에 엔트로피 소스로부터 충분한 무작위 데이터를 수집한다.
엔트로피는 하드웨어 기반의 난수 발생기나 시스템 상태에서 얻을 수 있다.
# 엔트로피 값 수집 예시
SecureRandom.getInstanceStrong().generateSeed(32)
2. 초기화 (시드 값 설정)
수집한 엔트로피는 시드 값으로 사용되며, DRBG의 초기 상태를 설정한다.
이 과정에서는 수집된 엔트로피와 추가적인 정보(개별화 문자열 등)를 기반으로 시드를 생성한다.
3. 내부 상태 설정
시드 값을 기반으로 DRBG의 내부 상태가 초기화된다. 내부 상태에는 시드 값과 난수 생성에 필요한 암호화 정보가 포홤되어 있다.
이 과정에서 DRBG의 암호화 알고리즘(Hash_DRBG, HMAC_DRBG 등)을 적용하여 내부 상태를 안전하게 설정한다.
4. 난수 생성 (Generate Function 호출)
DRBG가 내부 상태를 사용해 난수열을 생성한다.
이 과정에서는 DRBG 알고리즘이 해시 함수나 HMAC 등을 반복적으로 적용하여 예측 불가능한 난수를 출력한다.
생성된 난수는 요청한 비트 수만큼 출력된다.
# 난수 생성 함수 호출 예시
drbg.generate(128)
5. 리씨드
DRBG는 일정 주기나 특정 조건에서 리씨드 작업을 수행한다.
이 과정은 새로운 엔트로피 입력을 받아 시드를 다시 설정하는 과정이다.
6. 난수 사용 및 출력
DRBG에서 생성된 난수는 암호화 키 생성, 인증 토큰 생성, 보안 통신 등 다양한 보안 작업에 사용된다.
DRBG 방식 코드 예시
# 기존의 솔트 생성 코드 (권고하지 않음)
private static String createSalt() {
// 바이트 배열 초기화
byte[] bytes = new byte[SALT_LENGTH];
// 솔트 문자열 초기화
String salt = "";
// 솔트 생성 루프
while (salt.length() < SALT_LENGTH) {
// RANDOM: 보안 랜덤 생성기 객체
RANDOM.nextBytes(bytes);
// DigestUtils.md5DigestAsHex: MD5 해시 함수로 해싱하고 결과를 16진수 문자열로 변환
salt = salt + DigestUtils.md5DigestAsHex(bytes);
}
// 솔트 문자열을 SALT_LENGTH 길이 만큼의 부분 문자열을 잘라 반환
return salt.substring(0, SALT_LENGTH);
}
기존의 솔트 생성 코드를 보면 SecureRandom을 통해 생성한 난수를 MD5 해시로 변환한 후 문자열로 변환하는 방식으로 DRBG가 요구하는 수준의 암호학적 처리와는 차이가 있는 것을 알 수 있다.
1. DRBG와 SecureRandom의 차이점
| DRBG | SecureRandom (자바 난수 생성기) | |
| 내부 상태 관리 | 시드와 내부 상태를 명확하게 관리하며, 난수를 생성할 때 암호화 알고리즘(Hash, HMAC 등)을 사용해 난수를 생성한다. | 운영 체제 및 하드웨어에서 제공하는 무작위성을 사용하여 난수를 직접 생성하므로 내부 상태를 별도로 관리하거나 재설정하는 과정이 명시적으로 드러나지 않는다. |
| 리씨드 | 난수 생성 중간에 리씨드를 통해 새로운 엔트로피를 주기적으로 수집해 난수의 예측 가능성을 최소화한다. | 필요할 때마다 시스템 엔트로피 풀에서 새로운 값을 가져오지만, 명시적인 리씨드 과정은 없다. |
| 보안성 차이 | 시드 설정 및 암호화 알고리즘을 통해 더 안전한 난수를 생성하는 구조를 가지고 있다. | 충분히 안전한 난수를 제공하지만, DRBG와 같이 내부 상태를 관리하고 주기적으로 엔트로피를 갱신하는 구조를 따르지 않는다. |
2. MD5 사용
DRBG는 SHA-256이나 HMAC과 같은 안전한 해시 알고리즘을 사용하지만 위 코드는 MD5 해시 함수를 사용하고 있다. MD5는 보안적으로 취약한 해시 함수로 간주되며 이미 충돌 공격이 가능한 것으로 알려져 있어 암호화 및 난수 생성에서 더 이상 권장되지 않는다.
위 내용은 비트열 U와 V를 이용한 안전한 난수 생성과 관련된 XOR 연산을 설명하고 있다.
간단히 요약하면, U와 V라는 두 개의 독립적인 비트열을 생성한 후, 이 둘을 XOR 연산을 통해 결합하여 최종적으로 난수 K를 생성하는 방법을 말한다.
이때, U와 V는 서로 독립적이므로, U와 V중 하나를 알더라고 나머지 값을 유추하는 것이 불가능하다.
(1) U와 V 비트열
U는 안전한 난수 발생기로 생성된 비트열이다. 보통 SecureRandom 같은 보안 난수 발생기를 사용하여 생성한다.
U와 V는 독립적인 비트열이다. 즉 V는 U의 값과 상관없이 예측 불가능한 값을 가져야 한다. V는 여러 방법으로 생성될 수 있으며 예를 들어 해시 함수나 다른 방식으로 생성된 키를 기반으로 할 수 있다.
(2) XOR 연산
U와 V는 XOR 연산을 통해 K = U ⊕ V로 결합된다. XOR 연산은 두 비트열이 다를 때 1을, 같을 때 0을 반환하는 연산이다.
이 연산은 두 비트열을 결합하여 더 복잡하고 예측 불가능한 난수를 생성하게 하며, 하나의 비트열(U나 V)을 알더라도 다른 비트열을 알기 어려운 특성을 가진다.
(3) V의 생성
V의 생성 방식 중 하나는 안전한 키 유도 방법을 사용하는 것이다. 이는 주로 **키 유도 함수(KDF)**를 사용하여 보안성이 높은 값을 생성하는 것을 의미한다.
또 다른 방법으로, V'라는 상수(혹은 공유된 비밀)에서 해시 함수를 사용해 V 값을 유도할 수 있다. 해시 함수는 보안성이 높은 SHA-256이나 SHA-512 같은 알고리즘을 사용할 수 있다. 이 해시 값의 일부를 잘라내서 V로 사용하게 됩니다.
=> 요약
- U는 SecureRandom으로 생성된 256비트의 난수 비트열.
- V는 SHA-256 해시 함수를 통해 상수 비트열 또는 공유된 비밀을 입력으로 사용하여 생성된 비트열.
- 두 비트열을 XOR 연산하여 K라는 새로운 난수를 생성
따라서 위 코드를 DRBG의 방식에 부합하도록 하려면 추가적인 보안 강화 작업이 필요하다.
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.security.MessageDigest;
public class DRBGExample {
private static final int SALT_LENGTH = 32; // 256비트 솔트
private static SecureRandom secureRandom;
static {
try {
// 운영 체제에서 제공하는 가장 강력한 난수 생성기 사용
secureRandom = SecureRandom.getInstanceStrong();
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("SecureRandom 인스턴스 생성 실패", e);
}
}
// DRBG에서 난수 생성 후 키 유도 방법으로 V 비트열 생성
public static String createSalt() {
// U와 V 생성
byte[] U = new byte[SALT_LENGTH];
byte[] V = new byte[SALT_LENGTH];
// 보안 랜덤 생성기(SecureRandom)으로 난수 생성
secureRandom.nextBytes(U);
secureRandom.nextBytes(V);
// V를 SHA-256으로 해싱
byte[] hashedV = hashWithSha256(V);
// U와 해시된 V의 XOR 연산을 통해 K 값 생성
byte[] K = xor(U, hashedV);
String salt = bytesToHex(K);
return salt;
}
// SHA-256 해시 함수
private static byte[] hashWithSha256(byte[] input) {
try {
MessageDigest digest = MessageDigest.getInstance("SHA-256");
return digest.digest(input);
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("SHA-256 Hash failed...", e);
}
}
// XOR 연산 함수
private static byte[] xor(byte[] U, byte[] V) {
byte[] result = new byte[U.length];
for (int i = 0; i < U.length; i++) {
result[i] = (byte) (U[i] ^ V[i]);
}
return result;
}
// 바이트 배열을 16진수 문자열로 변환하는 함수
private static String bytesToHex(byte[] hash) {
StringBuilder hexString = new StringBuilder(2*hash.length);
for (byte b : hash) {
String hex = Integer.toHexString(0xff & b);
if (hex.length() == 1) hexString.append('0');
hexString.append(hex);
}
return hexString.toString();
}
}
추가로 독립적인 U, V를 xor 연산으로 생성한 솔트 값이 수 천번, 수 만번 생성했을 경우,
중복되는 솔트값이 생성되는 경우의 가능성에 대해 테스트하는 코드를 작성해 보았다.
package salt;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicInteger;
public class CreateSalt {
private static final int SALT_LENGTH = 32;
private static SecureRandom secureRandom;
// 중복 여부를 확인하기 위한 Set과 플래그
private static Set<String> saltSet = new HashSet<>();
private static AtomicBoolean duplicateFound = new AtomicBoolean(false); // 중복 발견 여부 플래그
// 스레드별로 몇 번째 salt를 생성했는지 추적할 변수
private static AtomicInteger saltCounter = new AtomicInteger(0);
static {
try {
secureRandom = SecureRandom.getInstanceStrong();
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("SecureRandom Instance not created...", e);
}
}
public static void main(String[] args) {
// 스레드 풀 생성 (10개의 스레드 사용)
ExecutorService executorService = Executors.newFixedThreadPool(10);
// 10개의 스레드
for (int i = 1; i <= 10; i++) {
final int threadNumber = i; // 현재 스레드 번호 저장
executorService.submit(() -> {
for (int j = 1; j <= 2000; j++) { // 각 스레드가 2000번 salt 생성 => 10*2000 = 20,000개 salt
// 중복이 발견된 경우 스레드 중단
if (duplicateFound.get()) {
System.out.println("################ duplicate salt ################ ");
break;
}
createSalt(threadNumber);
}
});
}
// 스레드 풀 종료 요청
executorService.shutdown();
}
public static String createSalt(int threadNumber) {
System.out.println("createSalt...");
// 몇 번째 salt를 생성 중인지
int currentSaltNumber = saltCounter.incrementAndGet();
System.out.println("Thread #" + threadNumber + " - Generating salt #" + currentSaltNumber);
// U와 V 생성
byte[] U = new byte[SALT_LENGTH];
byte[] V = new byte[SALT_LENGTH];
// 보안 랜덤 생성기(SecureRandom)으로 난수 생성
secureRandom.nextBytes(U);
secureRandom.nextBytes(V);
// V를 SHA-256으로 해싱
byte[] hashedV = hashWithSha256(V);
// U와 해시된 V의 XOR 연산을 통해 K 값 생성
byte[] K = xor(U, hashedV);
System.out.println("U: " + bytesToHex(U));
System.out.println("V (random): " + bytesToHex(V));
System.out.println("V (hashed): " + bytesToHex(hashedV));
System.out.println("K: " + bytesToHex(K));
String salt = bytesToHex(K);
System.out.println("Thread #" + threadNumber + " - Salt #" + currentSaltNumber + " generated: " + salt);
// 중복 체크
synchronized (saltSet) {
if (saltSet.contains(salt)) {
System.out.println("Duplicate salt found: " + salt);
duplicateFound.set(true); // 중복 발견
} else {
saltSet.add(salt); // 중복이 아니면 Set에 추가
}
}
return salt;
}
// SHA-256 해시 함수
private static byte[] hashWithSha256(byte[] input) {
try {
MessageDigest digest = MessageDigest.getInstance("SHA-256");
return digest.digest(input);
} catch (NoSuchAlgorithmException e) {
throw new RuntimeException("SHA-256 Hash failed...", e);
}
}
// XOR 연산 함수
private static byte[] xor(byte[] U, byte[] V) {
byte[] result = new byte[U.length];
for (int i=0; i<U.length; i++) {
result[i] = (byte) (U[i] ^ V[i]);
}
return result;
}
// 바이트 배열을 16진수로 변환
private static String bytesToHex(byte[] hash) {
StringBuilder hexString = new StringBuilder(2*hash.length);
for (byte b : hash) {
String hex = Integer.toHexString(0xff & b);
if (hex.length() == 1) hexString.append('0');
hexString.append(hex);
}
return hexString.toString();
}
}
20,000번 솔트값을 생성한 결과로는 중복된 값이 생성되지 않았다.
'보안' 카테고리의 다른 글
| 암호화 알고리즘과 암호화 키 생성 도구 (2) | 2024.09.05 |
|---|---|
| 암호 키 관리와 암호 키 보호 (1) | 2024.09.05 |
| 암호 키 생성 방식 (0) | 2024.09.05 |
| 개발자 도구 페이로드 평문 패스워드 노출: 클라이언트 측 RSA 암호화를 활용한 로그인 (2) - CAPTCHA 적용에 대해 (1) | 2024.08.26 |
| 개발자 도구 페이로드 평문 패스워드 노출: 클라이언트 측 RSA 암호화를 활용한 로그인 (1) (0) | 2024.08.22 |
