ed25519-unsafe-libs

Ed25519 이중 공개 키 서명 함수 오라클 공격

비밀 키와 공개 키를 서명 함수 입력으로 독립적으로 제공할 수 있는 공개 API를 허용하는 잠재적으로 안전하지 않은 ed25519 서명 라이브러리 목록입니다. 이러한 공개 API를 잘못 사용하면 개인 키가 노출될 수 있습니다.

분석 대상 저장소 대부분은 IANIX :: Things that use Ed25519에 등재되어 있습니다.

영향을 받는 라이브러리 수: 45
공지 후 문제를 수정한 라이브러리 수: 8
마지막 업데이트: 2023년 5월 4일

이 잠재적 익스플로잇을 시연하는 개념 증명 구현:

• Rust: ed25519-chalkias-exploit
• Python: Ed25519 Vulnerability in Python, Buchanan, William J (2022). Ed25519 Vulnerability in Python (Recovering Private Key). Asecuritysite.com.

발표:

• 미국 국립표준기술연구소(NIST) Crypto Reading Club 초청 발표: slides - Taming the Many EdDSAs (28-39페이지), Konstantinos Chalkias, François Garillot, Valeria Nikolaenko (2023). Taming the Many EdDSAs & Ed25519 Signing Attacks.

이 공격에 대한 뉴스 및 소셜 네트워크 보도

• NIST Crypto Reading Club "Taming the Many EdDSAs" (2023년 3월 8일)
• The Daily Swig "Dozens of cryptography libraries vulnerable to private key theft" (2022년 6월 28일)
• Risky Biz News "New crypto vulnerability: Tens of cryptography libraries have misimplemented the Ed25519 digital signature algorithm" (2022년 6월 28일)
• SafeHeron blogpost "Analysis on Ed25519 Use Risks: Your Wallet Private Key Can Be Stolen" (2022년 6월 17일)
• kryptera.se "Vulnerability in most ed25519 libraries" (스웨덴어) (2022년 6월 29일)
• Difesa e Sicurezza 및 Yoroi "Librerie crittografiche ed25519 potenzialmente non sicure" (이탈리아어) (2022년 7월 1일 및 6월 29일)
• Prof Bill Buchanan OBE의 Medium 게시물 "Ed25519 is Great, But ..." (2022년 7월 1일)
• Reddit r/crypto (이달의 베스트 게시물 - 2022년 6월 18일)
• Reddit r/cryptography (2022년 6월 17일)
• 흥미로운 트윗:
  • 트윗 1 (Kostas Kryptos 작성 - "The original 26 vulnerable libs")
  • 트윗 2 (Kostas Kryptos 작성 - "Aftermath of the 40 vulnerable libs")
  • 트윗 3 (Catalin Cimpanu 작성 - "40 cryptography libraries are impacted by same Ed25519 misimplementation")
  • 트윗 4 (Kenny Paterson 작성 - "Potential for widespread EdDSA private key recovery, cf. http://kopenpgp.com where same vector exploited in OpenPGP libs")
  • 트윗 5 (Steven Galbraith 작성 - "A hazard for deterministic signatures: better check it is the correct public key!")
  • 트윗 6 (Riyaz Faizullabhoy 작성 - "If you’re using EdDSA in prod please take a look")
  • 트윗 7 (Bart Preneel 작성 - "Reminder that implementing cryptographic algorithms securely and correctly is hard").
• 이 공격을 다루는 CTF(캡처 더 플래그) 챌린지:
  • ImaginaryCTF - JWT25519 (200pts) (2022년 6월 30일)

문제는 무엇인가?

참고로 일반적으로 관련 rfc8032에 따르면 EdDSA 서명은 결정적(deterministic)이므로, 서명할 동일한 입력 메시지에 대해 곡선 점 R과 스칼라 S라는 두 요소를 포함하는 고유한 서명 출력이 반환됩니다.

알고리즘적 세부 사항으로는 서명자의 공개 키가 서명의 S 부분의 결정적 계산에만 관여하고 R 값에는 관여하지 않는다는 점입니다. 이는 공격자가 어떻게든 서명 함수를 오라클(임의의 공개 키를 입력으로 기대하는)로 사용할 수 있다면, 동일한 메시지에 대해 동일한 R을 공유하고 S 부분만 다른 두 개의 서명을 얻을 수 있다는 것을 의미합니다. 불행히도 이런 일이 발생하면 개인 키를 쉽게 추출할 수 있습니다. 이 StackOverflow 게시물이 이것이 가능한 이유를 설명합니다.

즉, 공개 API는 분리된 개인/공개 키 쌍을 서명 입력으로 허용해서는 안 됩니다. 이를 방지하기 위해 많은 구현은 공개 키를 개인 키(또는 시드)와 함께 저장하고 전체 키 쌍을 비밀로 간주하거나, 서명 함수 내부에서 항상 공개 키를 다시 파생합니다. 불행히도 많은 수의 기존 라이브러리가 입력 공개 키가 입력 개인 키와 일치하는지 확인하지 않고 임의의 공개 키를 입력으로 허용함으로써 이 문제를 해결하지 못하고 있습니다.

물론 이것이 이러한 라이브러리에 의존하는 모든 애플리케이션이 키 노출 공격에 취약하다는 것을 의미하지는 않습니다. 실제로 대부분은 일반적으로 영향을 받는 API를 사용자에게 공개하지 않고 sign 호출 직전에 공개/개인 키 쌍을 결합하기 때문에 안전할 가능성이 높습니다. 반면, 이러한 API가 노출되지 않은 경우에도 개인 키와 공개 키를 관리하고 저장하는 방식에 대해 서로 다른 TCB 위협 모델 전략을 가진 애플리케이션이 있습니다. 즉, 이 공격을 방지하려면 개발자는 공개 키에 대한 무결성 보호 프로토콜도 적용해야 합니다.

여기에서는 관련 코드 참조와 함께 일부 영향을 받는 라이브러리를 나열합니다.

그림 1. ed25519-dalek Rust 크레이트에서의 API 오용 예.

영향을 받는 라이브러리

• C: OpenGNB
  https://github.com/gnbdev/opengnb/blob/master/libs/ed25519/sign.c#L7

• C: GNU Nettle
  https://github.com/gnutls/nettle/blob/fe7ae87d1b837e82f7c7968b068bca7d853a4cec/ed25519-sha512-sign.c#L43

• ASM/C: iroha-ed25519 (Hyperledger Project)
  https://github.com/hyperledger/iroha-ed25519/blob/main/lib/ed25519/ref10/ed25519.c#L27 및 https://github.com/hyperledger/iroha-ed25519/blob/main/lib/ed25519/amd64-64-24k-pic/ed25519.c#L30

• C: ed25519-donna (Andrew Moon)
  https://github.com/floodyberry/ed25519-donna/blob/master/ed25519.c#L59

• C: ed25519 (Orson Peters)
  https://github.com/orlp/ed25519/blob/master/src/sign.c#L7

• C: libbrine (Kevin Smith)
  https://github.com/kevsmith/libbrine/blob/master/src/ed25519/sign.c#L7

• C++: Ed25519 (ArduinoLibs)
  https://rweather.github.io/arduinolibs/classEd25519.html#a36ecf67b4c5d2d39a31888f56af1f8a5

• C#: ed25519 (Hans Wolff)
  https://github.com/hanswolff/ed25519/blob/master/Ed25519/Ed25519.cs#L146

• C#: Ed25519 (CryptoManiac)
  https://github.com/CryptoManiac/Ed25519/blob/972829ac688847895d5105f19ca1e5777131b421/Chaos.NaCl/Internal/Ed25519Ref10/keypair.cs#L7

• Dart: ed25519_dart (Oleksii Semeshchuk)
  https://github.com/semolex/ed25519_dart/blob/master/lib/src/ed25519_dart_base.dart#L200