NIST 타원곡선의 25년 된 미스터리, 드디어 풀렸습니다

암호 기술을 잘 모르는 사람도 한 번쯤은 P-256, ECDSA, X25519 같은 이름을 본 적이 있을 수 있습니다. 웹 보안, 인증서, 전자서명, TLS 같은 곳에서 널리 사용되는 타원곡선 암호 기술입니다.

그런데 이 가운데 NIST가 표준으로 정한 타원곡선들은 오랫동안 한 가지 의문을 안고 있었습니다.

“이 곡선들은 도대체 어떤 기준으로 선택된 것일까?”

곡선 자체는 공개되어 있었지만, 그 곡선을 만들 때 사용한 초기값, 즉 seed를 어떻게 골랐는지가 명확히 알려져 있지 않았기 때문입니다.

최근 Anthropic 연구팀이 이 오래된 미스터리의 상당 부분을 풀어냈습니다.

핵심은 의외로 단순했습니다.

NIST 타원곡선의 seed는 어떤 비밀 문장의 해시가 아니라, 1997~1998년 당시 시간을 초기값으로 넣은 drand48 난수 생성기의 출력에서 만들어졌다는 것입니다.

먼저, 왜 타원곡선의 “선택 과정”이 중요할까요?

타원곡선 암호에서는 아무 곡선이나 사용하는 것이 아닙니다.

예를 들어 NIST는 다음과 같은 곡선을 표준으로 정했습니다.

P-192
P-224
P-256
P-384
P-521

이 가운데 P-256은 지금도 매우 널리 사용됩니다.

문제는 가능한 타원곡선이 매우 많다는 점입니다.

즉 자연스럽게 이런 질문이 생깁니다.

“수많은 곡선 중 왜 하필 이 곡선을 골랐을까?”

이 질문은 단순한 호기심이 아닙니다.

만약 곡선을 선택한 사람이 수많은 후보를 자유롭게 시험할 수 있었다면, 자신만 알고 있는 특수한 약점을 가진 곡선을 고른 뒤 그것을 표준으로 제안할 가능성을 완전히 배제하기 어렵기 때문입니다.

NIST는 seed를 공개했지만, seed의 출처는 알려지지 않았습니다

NIST 곡선은 대략 다음과 같은 절차로 만들어졌습니다.

Seed
 ↓
SHA-1
 ↓
곡선 후보 생성
 ↓
수학적 조건 검사
 ↓
NIST Curve

즉 곡선 자체를 임의로 적어 넣은 것은 아니었습니다.

문제는 첫 번째 단계였습니다.

Seed는 어디서 왔을까?

seed 값은 공개되어 있었지만, 왜 그 값을 사용했는지 설명되지 않았습니다.

이 때문에 오랫동안 여러 추측이 나왔습니다.

특히 미국 NSA가 곡선 선택 과정에 관여했다는 사실 때문에 일부에서는 다음과 같은 의혹을 제기했습니다.

수많은 seed를 시험
     ↓
특정 약점을 가진 곡선 발견
     ↓
그 seed를 표준으로 선택

과거에는 “영어 문장을 해시했다”는 이야기가 있었습니다

한동안 알려진 설명은 이랬습니다.

NIST 곡선 설계에 관여했던 Jerry Solinas가 어떤 영어 문장을 정한 다음:

영어 문장
   ↓
 SHA-1
   ↓
 Seed

형태로 seed를 만들었다는 이야기입니다.

하지만 문제가 있었습니다.

정작 그 문장이 무엇이었는지는 남아 있지 않았습니다.

즉 검증할 방법이 없었습니다.

암호 표준에서 이런 불투명성은 꽤 큰 문제입니다.

실제 seed는 ‘시간 + drand48’에서 나왔습니다

Anthropic 연구팀이 밝혀낸 생성 방식은 다음과 같습니다.

당시의 UNIX timestamp를 가져와:

srand48(timestamp);

로 난수 생성기를 초기화합니다.

그리고 drand48 계열의 출력에서 바이트를 생성합니다.

대략적인 흐름은 다음과 같습니다.

1997~1998년 특정 시각
        ↓
UNIX Timestamp
        ↓
srand48()
        ↓
drand48()
        ↓
20바이트 생성
        ↓
ANSI X9.62 절차
        ↓
곡선 후보 생성

즉 지금까지 정체를 알 수 없었던 seed가 사실은 당시 시간을 기반으로 생성된 의사난수였다는 것입니다.

P-256도 실제로 재현됩니다

이 방식의 신뢰도가 높은 이유는 단순히 “그럴듯하다”는 수준이 아니기 때문입니다.

예를 들어 P-256은 다음 시간에서 생성 과정을 다시 돌렸을 때 나타납니다.

1997-08-16 01:52:34 UTC

해당 timestamp를 초기값으로 넣고 곡선 후보를 계속 만들면, 1,842번째 후보에서 P-256이 등장합니다.

다른 곡선들도 같은 방식으로 재현됩니다.

P-192
P-224
P-256
P-384
P-521

이 모두가 1997~1998년의 특정 timestamp와 동일한 생성 방식으로 설명됩니다.

즉 우연히 하나의 곡선만 맞아떨어진 것이 아니라, 여러 NIST 곡선이 하나의 공통된 생성 절차로 재현된다는 점이 중요합니다.

그런데 drand48은 안전한 난수 생성기가 아닌데 괜찮을까요?

여기서 한 가지 오해하기 쉬운 부분이 있습니다.

drand48은 오늘날 기준으로 암호학적으로 안전한 난수 생성기가 아닙니다.

따라서 다음 용도로 사용하면 안 됩니다.

비밀키 생성
Nonce 생성
Password 관련 난수 생성

하지만 이번 사례에서는 목적이 다릅니다.

여기서 seed는 비밀키가 아닙니다.

핵심은:

곡선 설계자가 원하는 곡선을 고르기 위해 얼마나 많은 후보를 자유롭게 시험할 수 있었는가

입니다.

즉 drand48 자체의 보안성보다 선택 가능한 후보 공간의 크기가 더 중요합니다.

가장 중요한 숫자: 70비트와 30비트

이번 연구에서 가장 중요한 부분 중 하나입니다.

과거에는 특정한 백도어 곡선을 의도적으로 찾기 위해 약 70비트 수준의 선택 자유도가 있다면 가능한 시나리오가 제기된 적이 있습니다.

70비트는 후보 수로 보면:

2^70

입니다.

반면 이번에 밝혀진 실제 생성 방식에서는 선택 자유도를 매우 넉넉하게 잡아도 약:

2^30

수준으로 평가됩니다.

둘의 차이는:

2^40

즉 약 1조 배입니다.

따라서 과거에 제기됐던 “아주 많은 seed를 뒤져서 특정 취약 곡선을 고른다”는 방식의 대표적인 백도어 시나리오는 이번 생성 방식과 맞지 않는다는 결론이 나옵니다.

그렇다고 모든 의혹이 완전히 사라진 것은 아닙니다

이번 연구가 의미 있는 것은 맞지만, 모든 문제가 해결된 것은 아닙니다.

연구팀은 곡선을 생성하는 과정에서 문서화되지 않은 추가 선별 조건이 있었다는 점도 확인했습니다.

하나의 조건은 어느 정도 밝혀졌지만, 여전히 이런 의문은 남아 있습니다.

“유효한 후보 중 일부는 왜 건너뛰었을까?”

즉 현재 상태는 다음과 같습니다.

Seed 생성 방식
→ 밝혀짐

Timestamp
→ 밝혀짐

drand48 사용
→ 밝혀짐

곡선 생성 절차
→ 대부분 재현

일부 후보 제외 이유
→ 아직 완전히 미해결

따라서 이번 연구는 “모든 것이 완벽히 증명됐다”기보다는, 가장 큰 의문이었던 seed의 출처를 상당히 명확하게 설명한 결과라고 보는 것이 정확합니다.

NIST 곡선에 대한 신뢰도는 왜 올라갔을까요?

NIST 곡선에 대한 오랜 불신의 상당 부분은 수학적인 취약점 때문이라기보다:

“왜 이 seed를 선택했는지 알 수 없다.”

는 문제에서 시작되었습니다.

이번 발견으로 생성 과정은 대략 다음처럼 설명할 수 있게 되었습니다.

1997~1998년 Timestamp
        ↓
     srand48
        ↓
     drand48
        ↓
       Seed
        ↓
      SHA-1
        ↓
 Curve Candidate
        ↓
     NIST Curve

즉 “설명할 수 없는 숫자가 갑자기 등장했다”는 상황에서 벗어난 것입니다.

이 점이 NIST 곡선에 대한 신뢰 회복에 큰 의미가 있습니다.

Curve25519와 비교하면 어떻게 봐야 할까요?

NIST 곡선에 대한 불신이 커지면서 이후에는 더 투명한 설계 과정을 가진 타원곡선이 주목받았습니다.

대표적인 것이 다음 계열입니다.

Curve25519
X25519
Ed25519

이들은 파라미터 선택 근거를 명확하게 설명하는 것을 중요한 설계 철학으로 삼았습니다.

그래서 오랫동안 많은 개발자와 암호 전문가들이 NIST 곡선보다 Curve25519 계열을 더 선호했습니다.

그런데 이번 연구와 함께, 결정론적 ECDSA와 형식 검증된 구현 등 여러 기술적 개선까지 고려하면서 Filippo Valsorda는 개인적으로 NIST 곡선을 더 긍정적으로 평가하고 있습니다.

다만 이것은 암호학계 전체가 NIST 곡선이 더 낫다고 합의했다는 뜻은 아닙니다.

이번 연구의 진짜 의미는 ‘암호학적 고고학’에 가깝습니다

이번 연구는 새로운 암호 알고리즘을 만든 것이 아닙니다.

오히려 25년 전 만들어진 표준의 흔적을 따라가며:

이 숫자는 왜 나왔을까?
 ↓
당시 어떤 코드가 있었을까?
 ↓
어떤 난수 생성기를 썼을까?
 ↓
어떤 시간값을 넣었을까?

를 역으로 추적한 작업입니다.

그래서 이 연구는 일종의 암호학적 디지털 고고학이라고 볼 수 있습니다.

정리

이번 발견의 핵심은 간단합니다.

NIST 타원곡선의 seed는 오랫동안 출처가 불분명했고, 이 때문에 의도적인 백도어 가능성에 대한 의심이 계속 존재했습니다.

하지만 최근 연구를 통해 이 seed가:

1997~1998년 시간값
        ↓
srand48
        ↓
drand48
        ↓
20바이트 seed
        ↓
NIST 곡선

과 같은 방식으로 생성됐다는 사실이 밝혀졌습니다.

이 생성 방식에서는 곡선을 고를 수 있는 자유도가 과거 일부 백도어 시나리오에서 필요했던 수준보다 훨씬 작습니다.

따라서 이번 연구는 NIST 곡선에 새로운 보안성을 추가한 것이 아니라,

“이 곡선은 왜 선택되었는가?”

라는 오랜 의문에 꽤 설득력 있는 답을 제공했다는 점에서 의미가 있습니다.

결국 암호 기술에서 중요한 것은 알고리즘 자체의 강도뿐만 아니라, 그 알고리즘과 파라미터가 어떤 과정으로 만들어졌는지를 투명하게 설명할 수 있는가라는 점도 다시 한번 보여준 사례라고 할 수 있습니다.