elikaski/ecc_attacks타원 곡선 암호화에 대한 알려진 공격
최근 몇 년 동안 타원곡선 암호(Elliptic Curve Cryptography) 방식은 높은 효율성과 강력한 보안성 덕분에 널리 사용되고 있습니다. 이 글의 목적은 이 주제를 현재 인터넷에 존재하는 것보다 비교적 더 명확하게 제시하는 것입니다.
이 글에서 나는 타원곡선이 무엇인지, 타원곡선에서 수행할 수 있는 기본 연산들, 그리고 이들이 암호학적 맥락에서 어떻게 사용될 수 있는지를 소개하겠습니다. 이 글의 대부분은 잘못된 구현이나 잘못된 사용에 대한 알려진 공격 사례로 구성됩니다. 글 전반에 걸쳐 나는 설명을 직관적이고 높은 수준의 부분과 더 자세한 내용을 다루는 수학적 부분으로 나누려고 합니다. 독자께서는 해당 위치에서 자신이 관심 있는 부분에 집중하고 덜 관심 있는 부분은 건너뛰셔도 좋습니다.
즐거운 읽기 되세요!
일반적으로 타원곡선은 일종의 곡선입니다. 그 예로는 방정식의 형태가 $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ 인 포물선이 있으며, 다음과 같이 생겼습니다:
암호학적 맥락에서는 다음과 같은 형태의 방정식을 갖는 타원곡선을 사용하는 것이 일반적입니다.
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
예를 들어, 방정식 $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ 에 해당하는 타원곡선은 다음과 같습니다:
곡선의 방정식은 곡선 위 점의 𝑥 좌표와 𝑦 좌표 사이의 관계를 정의합니다. 암호학적 맥락에서 우리는 𝑥, 𝑦, 𝑎, 𝑏 를 정수로 제한하고, 계산을 어떤 큰 소수로 나눈 나머지(modulo)로 제한합니다. 따라서 타원곡선의 방정식은 다음과 같습니다:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
이는 곡선 위에 유한한 수의 점이 존재한다는 것을 의미합니다. 수학적 언어로는 곡선이 위수 𝑝 인 유한체 위에 정의된다고 말합니다. 그 결과 이제 모든 𝑥 좌표에 곡선 위의 점이 반드시 대응되지는 않습니다. 그에 대응하는 𝑦 좌표가 정수가 아닐 수 있기 때문입니다.
곡선 위의 점들의 집합은 곡선의 방정식을 만족하는 정수 쌍 (𝑥, 𝑦) 들로 구성됩니다. 이러한 점들 외에도 "무한대(Infinity)"라고 불리는 또 다른 특별한 점이 정의되며, 이는 𝒪 로 표기됩니다. 수학적 언어로 이 점은 덧셈 연산에 관한 곡선 위 점들 집합의 항등원(neutral element)입니다. 덧셈 연산은 다음 섹션에서 정의하겠습니다. 곡선 위의 점의 수(점 𝒪 포함)를 "곡선의 위수(order of the curve)"라고 합니다.
또 다른 관찰로는 타원곡선이 X 축에 대해 대칭이라는 것입니다. 즉, 점 $𝑃 = (𝑥, 𝑦)$ 가 곡선 위에 있다면 점 $−𝑃 = (𝑥, −𝑦)$ 도 곡선 위에 있습니다. 실제로 이 점들은 서로의 "역원(inverse)"으로 간주되며(따라서 두 번째 점에 대해 −𝑃 로 표기), 이들 사이의 덧셈 연산 결과는 항등원 𝒪 로 정의됩니다.
Hasse의 정리라고 불리는 정리는 곡선의 위수인 #𝐸 에 대한 추정치를 제공하며, 그 크기는 Θ(𝑝) 입니다. 더 정확하게는:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
곡선 위의 두 점이 주어지면, 그들 사이의 덧셈 연산을 정의할 수 있으며, 그 결과는 곡선 위에 있는 세 번째 점이 됩니다. 이 점을 기하학적으로 찾으려면, 주어진 두 점 사이에 직선을 그리고 곡선과 세 번째 점에서 교차할 때까지 연장합니다. 이 점을 𝑋 축에 대해 대칭 이동한 점이 덧셈의 결과로 정의됩니다.
다음은 점 𝑃 와 𝑄 가 주어졌을 때 점 $𝑃 + 𝑄$ 를 어떻게 찾을 수 있는지 보여주는 다이어그램입니다:
이 설명에서 생길 수 있는 질문은 두 점 사이에 그린 직선이 곡선과 다시 교차하지 않으면 어떻게 되는가입니다. 이 경우 직선이 "무한대"에서 곡선과 교차한다고 말하며, 덧셈의 결과는 점 𝒪 입니다. 이 경우는 그린 직선이 수직일 때 발생합니다. 즉, 점 𝑃 를 그 역점인 −𝑃 와 더하려고 할 때입니다:
이로부터 두 가지 기본 항등식이 도출됩니다. 모든 점 𝑃 에 대해 다음이 성립합니다:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
기하학적 설명에서 생기는 또 다른 질문은 점을 자기 자신에 어떻게 더하는가입니다. 서로 다른 두 점 𝑃 와 𝑄 를 더하기 위해 두 점 사이에 직선을 그리고 그 연장선과 곡선의 교차점을 본다는 것을 확인했습니다. 직관적으로, 𝑃 를 고정시켜 두고 𝑄 가 𝑃 와 "점점 더 가까워지도록" 이동하면서 𝑄 가 𝑃 와 합쳐질 때까지 생기는 직선을 보겠습니다. 우리가 얻는 것은 점 𝑃 에서 곡선에 점점 더 "접하는" 직선이며, 이것이 바로 𝑃 를 자기 자신에 더할 때 보게 될 직선입니다:
점 𝑃 를 자기 자신에 더하려면 점 𝑃 에서 곡선에 접선을 그리고, 곡선과 두 번째 점에서 교차할 때까지 연장합니다. 이 점을 𝑋 축에 대해 대칭 이동한 점이 덧셈의 결과로 정의됩니다. 덧셈의 결과를 $𝑃 + 𝑃 = 2𝑃$ 로 표기하는 것이 일반적입니다. 다시 말하지만, 접선이 곡선과 두 번째 점에서 교차하지 않으면 "무한대"에서 곡선과 교차한다고 말하며, 이 경우 덧셈의 결과는 점 𝒪 입니다.
이러한 시각적 기하학적 설명은 점 덧셈이 어떻게 작동하는지 훌륭하게 보여주고 이해를 돕습니다. 하지만 실제로는 어떻게 계산할까요? 물론 수학 방정식입니다!
점 $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ 와 $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$ 가 주어졌을 때, 덧셈의 결과는 $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ 이며 다음과 같습니다:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
여기서 𝜆 는 두 점이 서로 다른 경우 두 점을 연결하는 직선의 기울기로 정의되고, 점이 자기 자신에 더해지는 경우 곡선의 그 점에서의 접선의 기울기로 정의됩니다. 공식적으로는:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
점 덧셈 뒤의 수학적 계산은 이 글의 나머지 부분에 중요하지 않습니다. 그런 의미에서 우리는 점 덧셈을 곡선 위의 두 점을 받아 곡선 위에 있는 세 번째 점을 반환하는 블랙박스로 볼 수 있습니다.
점 𝑃 를 자기 자신에 더할 수 있고, 그 결과 점을 2𝑃 로 표기한다는 것을 확인했습니다. 이 결과에 다시 점 𝑃 를 더하면 3𝑃 로 표기되는 점에 도달하고, 이런 식으로 계속됩니다. 이러한 방식으로 점을 반복적으로 자기 자신에 더함으로써(숫자 간의 곱셈과 유사하게) 점을 상수로 "곱하기"를 정의할 수 있습니다:
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
겉보기에는 점을 숫자 𝑛 으로 곱하려면 점 사이의 덧셈 연산을 𝑛 번 수행해야 하는 것처럼 보입니다. 이는 시작점이 주어졌을 때 "한 단계씩" 도달하지 않고서는 "마지막" 점이 어디에 위치할지 미리 알기 어렵기 때문입니다. 𝑛 이 매우 클 수 있으므로 이러한 계산은 매우 비효율적일 것입니다.
이를 위해 Double And Add 알고리즘이 존재합니다. 이 알고리즘에서는 점 𝑃 에서 시작하여 𝑛 의 이진 표현에서 각 비트에 대해 현재 점을 2 로 곱하고(즉, 자기 자신에 더하고), 비트 값이 1 이면 결과에 더합니다. 이 알고리즘의 실행 시간 복잡도는 $𝑂(log 𝑛)$ 이며, 매우 큰 수로 점을 효율적으로 곱할 수 있게 해줍니다.
나중에 사용할 점 곱셈의 중요한 속성은 모든 점 𝑃 와 숫자 쌍 𝑎, 𝑏 에 대해 다음이 성립한다는 것입니다:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
직관적으로, 점 𝑃 에서 시작하여 그로부터 𝑎 단계를 이동해 점 𝑎𝑃 에 도달한다고 가정해 봅시다. 이 점에서 "크기" 𝑎 의 단계를 𝑏 번 이동하여 점 $𝑏(𝑎𝑃)$ 에 도달합니다. 또는 다른 시나리오에서는 점 𝑃 에서 시작하여 𝑏 단계를 이동해 점 𝑏𝑃 에 도달할 수 있습니다. 이 점에서 "크기" 𝑏 의 단계를 𝑎 번 이동하여 점 $𝑎(𝑏𝑃)$ 에 도달합니다.
두 시나리오 모두에서 점 𝑃 로부터 총 동일한 양의 𝑎𝑏 단계를 이동했으므로, 두 시나리오 모두에서 동일한 최종 점에 도달했습니다. 수학적으로, 점을 상수로 곱하는 것은 결합 법칙이 성립합니다.
점 𝑃 에서 시작하여 그것을 계속해서 반복적으로 더하면, 각 단계마다 곡선 위의 어떤 새로운 점에 도달하게 됩니다. 곡선 위에는 유한한 수의 점이 있기 때문에, 어떤 단계에서는 이전에 도달했던 점들에 다시 도달하게 되고, 일종의 루프 또는 "원(circle)" 안에 있게 됩니다. 더 정확히 말하면, 어떤 단계에서는 점 -𝑃 에 도달하고, 다음 단계에서는 점 𝒪 에 도달하며, 그 다음 단계에서는 우리가 시작했던 점 𝑃 에 다시 도달하게 됩니다.
이러한 "원"을 만드는 점을 생성자(Generator)라고 합니다. 전체 "원"이 그 점으로부터 생성될 수 있기 때문이며, 보통 문자 𝐺 로 표기합니다. "원" 안의 점의 수(점 𝒪 포함)를 "생성자 𝐺 의 위수(order)"라고 하며, 보통 𝑛 으로 표기합니다. 곡선 위의 각 점은 어떤 종류의 "원"을 형성합니다. 수학적으로 이 "원" 위의 점들의 집합은 순환군(cyclic group)입니다.
이로부터 나오는 흥미로운 속성은 점 𝐺 에 그 위수 𝑛 을 곱하면 무한대의 점이 된다는 것입니다:
𝑛𝐺 = 𝒪
"점 𝑃 와 𝑄 가 어떤 𝑥 에 대해 $𝑄 = 𝑥𝑃$ 를 만족할 때, 𝑥 를 찾는 것은 어렵다."
말로 표현하면, 어떤 사람이 어떤 시작점에서 출발하여 그 지점에서 일정한 수의 단계를 이동해 최종 점에 도달했다고 가정해 봅시다. 시작점과 최종 점이 주어졌을 때, 그들이 몇 단계를 이동했는지 어떻게 알 수 있을까요?
이 질문에 대한 답은 그렇게 직관적이지 않습니다. 시작점에서 단계를 이동하여 어떤 점들에 도달할지 미리 예측하기 어렵기 때문입니다. 순진한 해결책은 우리 자신이 𝑃 에서 시작하여 그 지점에서 한 번에 한 단계씩 앞으로 나아가며 𝑄 에 도달할 때까지 이동한 단계 수를 세는 것입니다. 이 해결책의 복잡도는 $𝑂(𝑥)$ 이며, 𝑥 가 큰 수임이 알려진 경우, 예를 들어 𝑥 가 256 bit 인 경우 실행 불가능합니다.
이 문제를 타원곡선 이산 로그 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)라고 하며, 이는 어려운 문제입니다. 하지만 얼마나 어려울까요?
암호학적 맥락에서는 "문제의 어려움" 또는 "암호 시스템의 강도"를 Security Level 이라는 지표로 측정하는 것이 일반적입니다. 이 지표에서 어떤 문제가 $𝑂(2^𝑛)$ 단계로 해결하는 가장 잘 알려진 공격이 있다면 그 문제는 "𝑛 비트 보안"을 가진다고 말합니다.
현재 ECDLP 문제를 해결하는 최고의 알고리즘은 $𝑂(\sqrt n)$ 의 복잡도로 해결하며, 여기서 𝑛 은 점 𝑃 의 위수이고, Meet In The Middle 공격을 사용합니다. 충분히 큰 위수를 가진 점이 선택되면 이를 해결하는 것은 실행 불가능하므로, 이 문제의 강점이 됩니다.
예를 들어, 𝑛 을 256 bit 크기로 선택하면 ECDLP 문제가 128 bit 보안의 보안 수준을 갖게 됩니다. 비교를 위해, 정수 인수분해 문제에 기반한 RSA 암호화에서 동일한 128 bit 보안 수준을 달성하려면 3072 bit 크기의 공개 키가 필요합니다.这使得 타원곡선을 사용하는 것이 상대적으로 계산적으로 더 효율적입니다.
타원곡선 세계에 대한 이 모든 소개 후에, 이제 암호학적 맥락에서 이들을 가지고 무엇을 할 수 있는지 살펴보겠습니다. 우리가 알다시피, 암호 시스템은 일반적으로 해결하기 어려운 "어려운 문제"에 기반합니다. 예를 들어 우리가 언급한 숫자 인수분해 문제를 사용하는 RSA, 또는 이산 로그 문제를 사용하는 Diffie-Hellman 프로토콜이 있습니다. 타원곡선에서 ECDLP 문제에 기반한 암호 시스템은 타원곡선 암호(Elliptic Curve Cryptography) 계열, 줄여서 ECC에 속합니다.
이야기 하나로 시작해 봅시다. 당신이 파티에 있다고 상상해 보세요. 모두가 서로 대화할 수 있고 모두가 서로의 말을 들을 수 있는 사람들로 가득 찬 방입니다. 이 방에는 서로 만난 적이 없는 Alice와 Bob도 있습니다. Alice는 Bob을 좋아하고, 그에게 데이트를 신청하고 싶어 합니다. Alice는 약간 수줍음이 많아서, 다른 파티 손님들이 듣지 못하게 이 비밀 메시지를 Bob에게 전하고 싶어 합니다. Alice와 Bob은 사전에 아무것도 조율하지 않았으며, Alice가 Bob에게 말하는 모든 것은 파티의 다른 모든 손님들이 듣게 됩니다. Alice가 다른 사람이 듣지 못하게 Bob에게 메시지를 전하려면 어떻게 해야 할까요?
만약 "타원곡선"이라고 대답하셨다면, 맞습니다!
Alice는 어떤 타원곡선과 그 안의 생성자를 선택하여 Bob에게 알려줄 것입니다. 구체적으로 Alice는 Bob(그리고 방 안의 다른 모든 사람)에게 두 곡선 매개변수 𝑎, 𝑏, 법(modulus) 𝑝, 그리고 생성자 𝐺 를 전달할 것입니다. 또한 Alice는 $1 ≤ 𝑑_𝐴 ≤ 𝑛 − 1$ 범위의 어떤 값 $𝑑_𝐴$ 를 선택할 것입니다. 여기서 𝑛 은 𝐺 의 위수입니다. 값 $𝑑_𝐴$ 는 Alice의 개인키라고 합니다. Alice는 점 $𝐴 = 𝑑_𝐴𝐺$ 를 계산할 것이며, 이는 Alice의 공개키라고 하며, Bob에게 알려줍니다. 마찬가지로 Bob은 개인키 $𝑑_𝐵$ 를 선택하고, 점 $𝐵 = 𝑑_𝐵𝐺$ 를 계산할 것이며, 이는 Bob의 공개키라고 하며, Alice에게 알려줍니다.
Alice는 Bob의 공개키를 가져와 자신의 개인키로 그 점을 곱하고, 세 번째 점 $𝑃_𝐴 = 𝑑_𝐴𝐵$ 에 도달할 것입니다. 마찬가지로 Bob은 Alice의 공개키를 가져와 자신의 개인키로 곱하고, 자신만의 세 번째 점 $𝑃_𝐵 = 𝑑_𝐵𝐴$ 에 도달할 것입니다. Alice와 Bob이 각자 도달한 점들을 살펴보면, 그들이 같은 점에 도달했음을 발견할 수 있습니다! 이 사실은 앞서 본 점을 상수로 곱하는 것의 결합 법칙 속성에서 비롯됩니다:
$𝑃_𝐴 = 𝑑_𝐴𝐵 = 𝑑_𝐴(𝑑_𝐵𝐺) = 𝑑_𝐵(𝑑_𝐴𝐺) = 𝑑_𝐵𝐴 = 𝑃_𝐵$
전체 과정이 끝나면 Alice와 Bob은 곡선 위의 어떤 점에 대해 합의에 도달했으며, 어느 단계에서도 둘 중 누구도 그 점을 상대방에게 전달하지 않았습니다. 모든 사람이 들은 정보는 𝑎, 𝑏, 𝑝, 𝐺, 𝐴, 𝐵 입니다. 방 안에서 이 정보를 듣고 있는 사람은 이 정보만으로 Alice와 Bob이 합의한 점을 찾을 수 없습니다.
이는 방 안의 다른 사람이 그 점을 찾으려면 Alice의 개인키나 Bob의 개인키 중 하나를 알아야 𝐵 또는 𝐴 에 그것을 곱할 수 있기 때문입니다. 예를 들어 Alice의 개인키를 찾으려면, 그들은 $𝐴 = 𝑑_𝐴𝐺$ 를 볼 것입니다. 왜냐하면 이것이 전송된 유일한 정보이면서 Alice의 개인키를 "포함"하기 때문입니다. 𝐺 와 $𝑑_𝐴𝐺$ 가 주어졌을 때 $𝑑_𝐴$ 를 찾는 것은 타원곡선에서의 이산 로그 문제를 푸는 것과 동일하며, 앞서 언급했듯이 어려운 문제입니다.
이 아름다운 프로토콜을 타원곡선 디피-헬만(Elliptic Curve Diffie-Hellman, ECDH)이라고 합니다.
우리의 이야기는 아직 끝나지 않았습니다. Alice와 Bob이 공유 비밀 점에 합의했지만, Alice는 여전히 그토록 원했던 데이트 신청을 Bob에게 하지 못했습니다.
당사자들이 공유 비밀 점에 합의한 후에는, 이를 AES와 같은 어떤 암호화 방법의 암호화 키로 사용할 수 있으며, 그 시점부터 암호화를 통해 안전하게 통신할 수 있습니다.
점의 𝑥 또는 𝑦 좌표 중 하나를 가져와 사용하는 것이 일반적입니다. 안전을 유지하기 위해 선택된 값을 해시하고 해시 결과만 암호화 키로 사용하는 것이 권장됩니다. 실제로는 값이 암호화 키로 사용하기에는 너무 큰 경우가 있습니다. 예를 들어 사용된 해시 함수가 SHA-1인 경우 출력 길이는 160 bit 인 반면, AES 암호화는 128 bit 만 필요합니다. 이러한 경우 160 비트 중 128 bits 만 사용하고 나머지는 버리는 것이 일반적입니다.
어쨌든, 이 시점에서 Alice와 Bob은 암호화 키에 합의하며, 그들만이 그것을 알고 있습니다. 이 시점부터 그들은 암호화를 통해 통신하며, 방 안에서 엿듣는 사람은 그들이 말하는 내용을 이해할 수 없습니다.
다음은 프로토콜의 다이어그램입니다:
합의된 키를 사용하여 Alice는 "밥, 내일 저녁에 커피 마시러 갈래?"라는 메시지를 암호화하고, 암호화된 메시지를 Bob에게 전달합니다. Bob은 자신도 알고 있는 키로 메시지를 복호화합니다. Alice는 Bob이 "좋아"라고 대답하길 바라지만, 그것은 프로토콜의 일부가 아닙니다.
잘 알려진 디피-헬만(DH) 프로토콜에서, 당사자들은 소수 𝑝 와 값 𝑝 에 해당하는 그룹에 속하는 생성자 𝑔 를 공개적으로 전송합니다. Alice는 개인키 𝑎 를 무작위로 생성하고 자신의 공개키 $𝐴 = 𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ 를 공개적으로 브로드캐스트합니다. 마찬가지로 Bob은 개인키 𝑏 를 무작위로 생성하고 자신의 공개키 $𝐵 = 𝑔^𝑏\ \ \ \ (mod\ 𝑝)$ 를 공개적으로 브로드캐스트합니다. 그런 다음 Alice는 Bob의 공개키를 가져와 자신의 개인키로 거듭제곱하여 값 $𝐾 = 𝐵^𝑎 = (𝑔^𝑏)^𝑎 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$ 을 계산합니다. 같은 방식으로 Bob은 값 $𝐾 = 𝐴^𝑏 = (𝑔^𝑎)^𝑏 =𝑔^{𝑎𝑏}\ \ \ \ (mod\ 𝑝)$ 을 계산합니다. 과정이 끝나면 Alice와 Bob은 그들 사이에 전송하지 않고도 공통된 𝐾 값에 합의할 수 있었습니다.
그들을 엿듣는 공격자는 브로드캐스트된 값 𝑝, 𝑔, 𝐴, 𝐵 가 주어졌을 때 𝐾 를 찾을 수 없습니다. 이를 위해서는 Alice 또는 Bob의 개인키 중 하나를 찾아야 합니다. 예를 들어 Alice의 개인키를 계산하려면 𝑔 와 $𝑔^𝑎\ \ \ \ (mod\ 𝑝)$ 가 주어졌을 때 𝑎 를 찾아야 하는데, 이는 어려운 문제입니다. 이 문제를 이산 로그 문제(Discrete Logarithm Problem, DLP)라고 합니다.
DLP에 기반한 DH와 ECDLP에 기반한 ECDH 사이에는 매우 명확한 유사점이 있습니다(기본적으로 동일하며, 단지 EC 접두사만 붙을 뿐입니다). 두 프로토콜 모두에서, 서로 대화하는 두 당사자는 사전에 아무것도 조율하지 않고도 어떤 공유 비밀 값에 합의할 수 있습니다. 당사자들 사이의 메시지를 엿듣는 사람은 그들이 주고받는 공개 정보에 노출되지만, 그들 사이에 공유된 비밀 값에는 도달할 수 없습니다.### 타원 곡선의 두 번째 용도 - 메시지 서명 이야기를 계속해서, 앨리스와 밥이 데이트를 하고 즐거운 저녁을 보냈다고 가정해 보자. 다음 날 앨리스는 "안녕 앨리스, 나는 밥이야. 어제 너와 정말 즐거운 시간을 보냈고, 이번 주말에 다시 만나고 싶어"라는 메시지를 받는다. 앨리스는 그 메시지를 보낸 사람이 밥이 아닐 것이라고 의심한다. 그녀는 밥이 어제 그녀와 너무 재미있게 놀아서 주말까지 기다리지 않고 내일 만나고 싶어 할 것이라는 것을 알기 때문이다! 앨리스는 메시지를 쓴 사람이 정말 밥인지 어떻게 확인할 수 있을까?
"타원 곡선"이라고 대답했다면, 또 맞춘 것이다!
ECDLP 문제의 어려움은 메시지 서명에도 사용될 수 있다. 데이트 중에 앨리스와 밥은 어떤 타원 곡선과 그 안의 생성자 𝐺에 합의했다. 밥은 밥의 개인 키라고 불리는 어떤 값 $𝑑_𝐵$를 생성하고, 밥의 공개 키라고 불리는 점 $𝑃_𝐵 = 𝑑_𝐵𝐺$를 계산했다. 밥은 앨리스에게 자신의 공개 키를 주었고, 그녀가 나중에 받은 메시지가 정말로 자신이 서명한 것인지 확인하는 데 사용할 수 있게 했다.
밥이 특정 메시지 𝑚에 서명하려 한다고 가정해 보자. 그는 어떤 안전한 해시 함수를 사용하여 $z = hash(m)$ 값을 계산하고, 그 결과에서 생성자 𝐺의 위수인 n의 비트 길이만큼의 비트를 유지한다. 밥은 $1 ≤ 𝑘 ≤ 𝑛 − 1$ 범위의 임의의 값 𝑘를 생성할 것이다. 그런 다음 밥은 점 $𝑘𝐺 = (𝑥_1, 𝑦_1)$을 계산하고, 그 𝑥 좌표를 취하여 $𝑟 = 𝑥1\ \ \ \ (mod\ n)$을 계산한다. 마지막으로 밥은 $𝑠 = 𝑘^{−1}(𝑧 + 𝑟𝑑_𝐵)$ 값을 계산한다.
메시지 𝑚의 서명은 계산된 값 𝑟와 𝑠의 쌍으로 정의된다.
앨리스가 어떤 메시지 𝑚와 그 서명(값 𝑟와 𝑠의 쌍)을 받았다고 가정해 보자. 앨리스는 메시지에 서명한 사람이 정말 밥인지 확인하고 싶다. 앨리스는 밥과 같은 방식으로 $z = hash(m)$ 값을 계산할 것이다. 그런 다음 앨리스는 $𝑢_1 = 𝑧𝑠^{−1}$ 및 $𝑢_2 = 𝑟𝑠^{−1}$ 값을 계산한다. 마지막으로 앨리스는 밥의 공개 키 $𝑃_𝐵$를 사용하여 점 $𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = (𝑥_1, 𝑦_1)$을 계산한다. $𝑟 ≡ 𝑥_1\ \ \ \ (mod\ n)$이 성립하면 서명이 유효한 것으로 간주된다. 이것이 맞는 이유는 다음이 성립하기 때문이다:
$𝑢_1𝐺 + 𝑢_2𝑃_𝐵 = 𝑧𝑠^{−1}𝐺 + 𝑟𝑠^{−1}𝑃_𝐵 = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑃_𝐵) = 𝑠^{−1}(𝑧𝐺 + 𝑟𝑑_𝐵𝐺) = 𝑠^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘(𝑧 + 𝑟𝑑_𝐵)^{−1}(𝑧 + 𝑟𝑑_𝐵)𝐺 = 𝑘𝐺$
서명이 유효하면, 이 점의 𝑥 좌표는 메시지 서명에 정의된 대로 실제로 𝑟가 되어야 한다. 생성자 𝐺의 위수를 나타내는 문자 𝑛은 소수여야 한다는 점에 유의해야 한다. 그래야 서명 및 검증 알고리즘에서 역수를 계산하는 것이 실제로 가능해진다.
개인 키 $𝑑_𝐵$를 보유한 사람만이 공개 키 $𝑃_𝐵$에 대한 유효한 서명을 만들 수 있다는 것을 알 수 있다. $𝑑_𝐵$ 값을 갖고 있지 않은 공격자는 서명에서 $𝑃_𝐵$에 해당하는 𝑠 값을 계산할 수 없다. 공격자가 특정 메시지와 일치하는 서명을 만들고 싶다면 ECDLP 문제를 풀어야 한다. 즉, $𝐺$와 $𝑃_𝐵 = 𝑑_𝐵𝐺$가 주어졌을 때 개인 키 $𝑑_𝐵$를 찾아야 하는데, 이는 어려운 문제이다.
이 서명 프로토콜을 타원 곡선 디지털 서명 알고리즘(Elliptic Curve Digital Signature Algorithm), 줄여서 ECDSA라고 한다. 이 프로토콜은 서명된 메시지가 변경되거나 위조되지 않았음을 보장하며, 추가로 메시지에 서명한 사람이 자신이 만들었다는 사실을 부인할 수 없도록 보장한다.
당사자들이 사전에 아무것도 조정할 필요가 없었던 ECDH 프로토콜과 달리, ECDSA 프로토콜에서는 당사자들이 사전에 공개 키에 합의해야 한다. 각 당사자가 보유한 공개 키가 자신이 통신하려는 사람의 것임을 확실히 알게 된 후에만 프로토콜을 사용할 수 있다. 그렇지 않으면 각 당사자가 보유한 공개 키로 서명을 검증하는 것은 의미가 없다.
이야기로 돌아가자. 앨리스는 자신이 보유한 공개 키 $𝑃_𝐵$가 정말 밥의 것임을 확실히 안다. 왜냐하면 밥이 데이트 때 그녀에게 명시적으로 주었기 때문이다. 앨리스는 그 키로 메시지를 검증해 보지만 일치하지 않는다는 것을 발견한다. 당연하다! 앨리스가 의심했던 대로, 다른 누군가가 메시지를 만들고 서명한 것이다.
프로토콜의 다이어그램은 다음과 같다:
메시지 서명을 위한 ElGamal 프로토콜에서 당사자들은 큰 소수 𝑝와 생성자 숫자 𝑔에 합의한다. 서명 당사자는 개인 키라고 불리는 $1 ≤ 𝑑 < 𝑝 − 1$ 범위의 어떤 값 𝑑를 생성하고, 공개 키라고 불리는 $𝑦 = 𝑔^𝑑\ \ \ \ (mod\ p)$ 값을 계산하여 공개한다.
특정 메시지에 서명하기 위해 그들은 $z = hash(m)$ 값을 계산하고 $(p-1)$과 서로소인 $1 ≤ 𝑘 < 𝑝 − 1$ 범위의 임의의 값 𝑘를 생성한다. 그들은 $𝑟 = 𝑔^𝑘\ \ \ \ (mod\ p)$ 및 $𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)\ \ \ \ (mod\ (p-1))$을 계산한다. 메시지 m의 서명은 계산된 값 𝑟와 𝑠의 쌍으로 정의된다.
특정 메시지 𝑚와 그 서명(값 𝑟와 𝑠의 쌍)을 받은 당사자는 공개 키 𝑦를 사용하여 $𝑢_1 = 𝑟^𝑠𝑦^𝑟$ 및 $𝑢_2 = 𝑔^𝑧$ 값을 계산함으로써 서명을 검증한다. $𝑢_1 = 𝑢_2$이면 서명이 유효한 것으로 간주된다. 그 이유는 𝑠의 정의에 따라 다음이 성립하기 때문이다:
$𝑠 = 𝑘^{−1}(𝑧 − 𝑑𝑟)$, 따라서 $𝑘𝑠 = 𝑧 − 𝑑𝑟$, 그러므로 $𝑧 = 𝑘𝑠 + 𝑑𝑟$. 따라서:
$𝑢_2 = 𝑔^𝑧 = 𝑔^{𝑘𝑠+𝑑𝑟} = 𝑔^{𝑘𝑠}𝑔^{𝑑𝑟} = (𝑔^𝑘)^𝑠(𝑔^𝑑)^𝑟 = 𝑟^𝑠𝑦^𝑟 = 𝑢_1$
공격자는 개인 키 𝑑를 모르는 상태에서 공개 키 𝑦에 대한 유효한 서명을 만들 수 없다. 공개 키가 주어졌을 때 개인 키를 얻으려면 공격자는 어려운 문제인 DLP 문제를 풀어야 한다.
여기서도 ECDLP에 기반한 ECDSA와 DLP에 기반한 ElGamal 사이에 분명한 유사점이 있다. 두 경우 모두 당사자들은 사전에 공개 키를 조정해야 하며, 새 메시지에 서명할 때마다 임의의 𝑘 값을 생성해야 한다. 또한 두 경우 모두 당사자들 사이의 메시지를 도청하는 공격자는 서명을 위조할 수 있게 해주는 유용한 정보를 추론할 수 없다.
우리는 타원 곡선이 비밀 값 합의와 메시지 서명을 위한 암호화 시스템에서 어떻게 사용될 수 있는지 살펴보았다. 인생의 모든 것과 마찬가지로, 무언가를 실제로 적용할 때 일이 항상 계획대로 진행되지는 않는다. 이 기사의 나머지 부분에서는 사용자가 잘못 사용했거나 안전하지 않은 방식으로 구현된 ECC 기반 암호화 시스템을 공격하는 다양한 방법을 제시할 것이다.
당연히 나는 이 부분을 ECDH 공격과 ECDSA 공격으로 나누었다. 두 경우 모두 당사자 중 한 명의 개인 키를 찾으면 공격에 "성공"했다고 말하고 거기서 멈출 것이다. ECDH의 경우, 개인 키에서 공유 비밀 값과 이후에 그 값으로 암호화된 모든 정보에 도달할 수 있으므로 충분하다. ECDSA의 경우, 개인 키를 사용하여 원하는 대로 메시지에 서명할 수 있으므로 충분하다.
SageMath는 무료 오픈 소스 수학 소프트웨어이다. Python과 거의 동일한 구문으로 작성할 수 있으며 Python 라이브러리로도 사용할 수 있다. 이 라이브러리는 타원 곡선과 관련된 유용한 함수를 구현하므로 ECC 맥락에서 수행해야 하는 계산에 매우 유용하다. 이 기사의 일부로 이 라이브러리로 작성된 코드 스니펫을 제공한다. Ubuntu 운영 체제, 특히 22.04 버전에 설치하는 것이 가장 쉽다는 것을 알았다. 설치하려면 다음 명령을 실행하기만 하면 된다: sudo apt install sagemath.
코드가 포함된 파일을 실행하려면 파일을 .sage 확장자로 저장하고 다음 명령을 실행한다: sage file.sage.
또한 Python의 인터프리터와 유사하게 sage 명령을 실행하여 인터프리터를 사용할 수 있다. sage.all 라이브러리를 가져오는 .py 파일을 만들고 python3 file.py 명령으로 실행하는 것도 가능하다. sage 명령으로 파일을 실행하면 ^ 표기법이 거듭제곱으로 해석되지만, python3으로 실행하면 이 표기법이 xor로 해석된다는 점에 유의하라.
이 기사에서는 주로 SageMath에서 다음 함수를 사용한다:
E.gens() - 곡선 E에서 생성자 찾기G.order() - 생성자 G의 위수 계산n*G - 생성자 G에 숫자 n을 곱하기n.factor() - 숫자 n을 인수들로 인수분해 - 함수는 (𝑝, 𝑒) 쌍의 목록을 반환하는데, 여기서 𝑝는 소인수이고 𝑒는 그 지수, 즉 n의 분해에 𝑝가 나타나는 횟수이다crt - 중국인의 나머지 정리의 연립 방정식 풀기아마도 공격하기 가장 쉬운 ECDH의 잘못된 사용은 위수 n이 너무 작은 생성자를 선택하는 것이다.
앞서 언급했듯이 ECDLP 문제는 $O(\sqrt{n})$의 복잡도로 풀 수 있다. 𝑛이 너무 작을 때, 예를 들어 32비트라면, 이 문제를 푸는 것이 실현 가능해진다. 이 문제를 푸는 여러 알고리즘에는 Baby-Step Giant-Step, Pollard's Rho, Pollard's Lambda가 포함된다. 이 알고리즘들은 SageMath의 discrete_log 함수를 사용하여 블랙 박스로 실행할 수 있다:```python
import random
p = random_prime(2^32)
a = random.randrange(p)
b = random.randrange(p)
E = EllipticCurve(GF(p), [a,b])
G = E.gens()[0]
n = G.order()
private_key = random.randrange(n)
A = private_key * G
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
이 코드 스니펫에서는 `𝑝`가 32비트 길이로 제한된 상태에서 곡선의 매개변수를 무작위로 선택합니다. 이 제한 덕분에 곡선 위의 점 개수가 $O(2^{32})$임이 보장되며, 따라서 각 점의 위수도 최대 $O(2^{32})$입니다. 그런 다음 곡선을 만들고, 그 안에서 생성자를 선택하고, 무작위 개인 키를 생성한 뒤 공개 키를 계산합니다. 마지막으로 생성자와 공개 키로부터 이산 로그를 계산하여 개인 키를 찾고, 찾은 키가 실제로 올바른지 검증합니다. 이 코드는 개인 키를 찾는 데 기껏해야 몇 초밖에 걸리지 않습니다.
## 생성자의 위수는 매끄러운 수이다
앞서 언급했듯이, 생성자의 위수는 생성자 점을 계속해서 더해 나갈 때 형성되는 "원" 위의 점 개수로 정의되며 `𝑛`으로 표기됩니다. 만약 `𝑛`이 더 작은 소인수들로 분해될 수 있는 합성수라면, ECDLP를 효율적으로 풀 수 있습니다. 이러한 수를 매끄러운 수(Smooth Number)라고 하며, 이 글의 목적상으로는 우리의 공격이 동작할 만큼 각각 충분히 작은 소인수들로 충분히 분해될 수 있는 수를 의미합니다. 매끄러운 수의 공식적인 정의는 조금 다르지만 우리에게는 관련이 없습니다.
직관적으로, 이 공격은 각 소인수를 개별적으로 "공격"하는 방식으로 수행됩니다. 매우 큰 "원"을 형성하는 생성자 점 `𝐺`와 그 "원" 위의 어떤 점 `𝑃`(여기서 `𝑃 = 𝑘𝐺`)가 주어졌다고 합시다. 큰 "원"은 `𝑛`의 각 소인수의 크기를 갖는 여러 개의 작은 "원"들로 분해될 수 있습니다. 각각의 작은 "원"에서 `G`와 `P`를 작은 "원" 안에 위치하는 대응하는 다른 점 `G'`와 `P'`로 매핑할 수 있으며, 이들은 `𝑃′ = 𝑘′𝐺′`를 만족합니다. "원"이 작기 때문에 문제를 풀어 `𝑘′`를 찾는 것은 상대적으로 쉽습니다. 마지막으로, 찾은 모든 작은 `𝑘′` 값들을 결합하여 원래 "원"에서 원하는 `𝑘`를 얻을 수 있습니다.
제가 설명한 작업을 수행하는 알고리즘은 Pohlig-Hellman 알고리즘이라고 합니다. 이 알고리즘의 실행 시간 복잡도는 $O(\sqrt{p_{max}})$이며, 여기서 $p_{max}$는 `𝑛`을 분해했을 때 가장 큰 소인수입니다. 이는 직관적으로도 타당한데, 알고리즘에서 가장 "무거운" 부분은 작은 "원"들 중 가장 큰 "원"에서 ECDLP 문제를 푸는 것이기 때문입니다. 예를 들어, `n`은 128비트 수일 수 있고, 소인수로 분해했을 때 가장 큰 소인수가 30비트 수일 수 있습니다. 이 알고리즘은 문제를 푸는 복잡도를 $2^{64}$에서 $2^{15}$로 줄여서, 실현 불가능하던 것을 실현 가능하게 만듭니다.
다행히도 SageMath의 `discrete_log` 함수는 내부 구현에서 이 알고리즘을 수행합니다. 공격을 실행하려면 다음 함수를 호출하기만 하면 됩니다:```python
p = 183740305291166889900894879302858411333
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(123764810000715262449972298016641419881,
144640915410606177233842123838934486566)
n = G.order()
print("number of bits in n:", n.nbits())
print("n's factors:", n.factor())
print("number of bits in n's greatest factor:", n.factor()[-1][0].nbits())
import random
private_key = random.randrange(n)
A = private_key * G
print("Calculating discrete_log...")
found_key = G.discrete_log(A)
assert found_key * G == A
assert private_key == found_key
print("success!")
이 코드 조각에서는 타원 곡선과 그 안의 생성원을 정의하고, 그 위수의 소인수를 출력합니다. 출력은 다음과 같습니다:``` number of bits in n: 128 n's factors: 2 * 3 * 13 * 101 * 211 * 21141581 * 38581057 * 60652309 * 2234328781 number of bits in n's greatest factor: 32 Calculating discrete_log... success!
생성자의 위수가 128비트 길이임에도 불구하고, 가장 큰 소인수가 32비트가 되도록 소인수들로 분해된다는 것을 알 수 있습니다.
그 후, 이전 공격에서와 마찬가지로 - 임의의 개인 키를 선택하고, 그로부터 공개 키를 계산한 다음, 생성자와 공개 키가 주어졌을 때 개인 키를 계산하여 그것이 올바른지 검증합니다.
비록 우리는 끝냈지만, "작은" 원들이 어떻게 정의되는지, 점 `𝐺`와 `𝑃`를 대응하는 점 `𝐺′`와 `𝑃′`로 어떻게 매핑하는지, 그리고 모든 작은 해들을 하나의 큰 해로 어떻게 결합하는지는 아직 보지 못했습니다. 다음 공격도 이 부분에 기반하므로, 여기서 직관적으로 설명하겠습니다.
위수 `3𝑥5𝑥7 = 105`인 "원"이 있고, 그 생성자가 `𝐺`라고 가정합시다. 점 `𝐺′ = (5𝑥7)𝐺 = 35𝐺`를 정의하고, 그로부터 생성되는 "원"을 살펴봅시다. `𝐺′`에서 한 "단계" 전진한다면, 즉 `𝐺′`를 자신에게 더한다면, 원래 "원"에서 `35𝐺` 지점으로부터 35단계 전진하는 것과 같으며, `2𝐺′ = 70𝐺` 지점에 도달하게 됩니다. 한 "단계" 더 전진하면 `3𝐺′ = 105𝐺 = 𝒪`에 도달하고, 거기서 또 한 "단계" 전진하면 `4𝐺′ = 35𝐺 = 𝐺′`, 즉 시작점으로 돌아오게 됩니다. `G′`가 이루는 "원"의 위수는 `3`이며, 이는 우연이 아닙니다. 위수 `105`인 "원"에서는 정확히 크기 `35`의 "단계"를 `3`번 밟을 수 있기 때문입니다. 마찬가지로, 점 `𝐺′ = (3𝑥7)𝐺 = 21𝐺`를 정의하여 위수 `5`인 "원"을 만들 수 있고, `𝐺′ = (3𝑥5)𝐺 = 15𝐺`를 정의하여 위수 `5`인 "원"을 만들 수 있습니다.
반대로 바라보면 더 흥미로워집니다. 원래 "원"에서 점 `G`로부터 `𝑛` 단계를 전진하여 점 `𝑛𝐺`에 도달했다고 가정합시다. 작은 "원"에서도 점 `𝐺′`로부터 `𝑛` 단계를 전진한다면, `𝑛 ≡ 𝑛′ (𝑚𝑜𝑑 3)`을 만족하는 점 `𝑛′𝐺′`에 도달하게 됩니다. 그런데 왜 흥미로운가요? `𝐺′`의 위수는 `𝐺`의 위수보다 훨씬 작기 때문에, `𝐺′`와 `𝑛′𝐺′`가 주어지면 `𝑛′`를 비교적 쉽게 찾을 수 있습니다. 이를 수행하고, "원"의 위수의 다른 두 소인수인 `5`와 `7`에 대해서도 동일하게 수행하면 다음 값들을 얻게 됩니다:
𝑛 ≡ $𝑛'_1$ (𝑚𝑜𝑑 3)\
𝑛 ≡ $𝑛'_2$ (𝑚𝑜𝑑 5)\
𝑛 ≡ $𝑛'_3$ (𝑚𝑜𝑑 7)
이 세 값으로부터 `𝑛`은 중국인의 나머지 정리(Chinese Remainder Theorem)를 사용하여 쉽게 찾을 수 있으며, 따라서 원래 문제를 해결할 수 있습니다.
## 생성자의 위수는 거의 매끄러운 수(smooth number)이고, 개인 키는 작습니다
이전 공격과 유사하게, 생성자의 위수가 소인수들로 분해되는 곡선을 얻었지만, 이번에는 가장 큰 소인수가 ECDLP를 실제로 풀기에는 너무 크다고 가정합시다. 예를 들어, 생성자의 위수가 `256 bit`인데 가장 큰 소인수가 `128 bit`인 경우입니다.
Pohlig-Hellman 알고리즘은 개인 키를 찾기 위해 약 $O(2^{64})$ 번의 연산이 필요하므로, 이는 실행 불가능합니다.
사용된 개인 키가 비교적 작다는 것을 알고 있다면, 여전히 효율적으로 찾을 수 있습니다.
개인 키가 `256 bit` 대신 `64 bit`라고 가정해 봅시다. 공개 키가 생성될 때 생성자에 개인 키가 곱해져 생성자가 만드는 "원" 안의 어떤 점이 얻어집니다. "원"은 약 $2^{256}$ 개의 점 크기이지만, 이 점은 "첫 번째" $2^{64}$ 개의 점 어딘가에 "떨어지게" 됩니다. 개인 키와 더 큰 값에 해당하는 "원"의 점들 사이에는 "상호작용"이 없습니다.
Pohlig-Hellman 알고리즘을 실행할 수는 있지만, 나머지 "원"들의 위수의 곱이 적어도 개인 키의 길이만큼이 된다는 조건 하에 너무 큰 "원"들은 "버릴" 수 있습니다. 충분히 작은 소인수들을 찾아서 그 곱이 적어도 `64 bit`가 된다면, 해당 "원"들로 앞서 보았던 것과 동일한 공격을 수행하기에 충분합니다.
앞서 코드 작성 측면에서 쉬웠다면, 이번에는 SageMath의 `discrete_log` 함수가 일부 소인수를 "버리려는" 의도를 알지 못하기 때문에 직접 구현해야 합니다. 다음 코드 스니펫은 이를 수행합니다:```python
p = 88664572752015126127869404674421545790506871948117527783533589813159111825511
a = 13
b = 37
E = EllipticCurve(GF(p), [a,b])
G = E(19374976316789648652022260955836934561553454311144967863145605756652014623129,
68630819472054489323664324766002023315775509214344811025345735680440707888471)
n = G.order()
print("Number of bits in n:", n.nbits())
factors = n.factor()
print("n's factors:", factors)
PRIVATE_KEY_BIT_SIZE = 64
import random
private_key = random.randrange(2^PRIVATE_KEY_BIT_SIZE)
P = private_key * G
print("We know that the private key is", PRIVATE_KEY_BIT_SIZE, "bits long")
print("Lets find which of the factors of G's order are relevant for finding the private key")
# find factors needed such that the order is greater than the secret key size
count_factors_needed = 0
new_order = 1
for p, e in factors:
new_order *= p^e
count_factors_needed += 1
if new_order.nbits() >= PRIVATE_KEY_BIT_SIZE:
print("Found enough factors! The rest are not needed")
break
factors = factors[:count_factors_needed]
print("Considering these factors:", factors)
print("Calculating discrete log for each quotient group...")
subsolutions = []
subgroup = []
for p, e in factors:
quotient_n = (n // p ^ e)
G0 = quotient_n * G # G0's order is p^e
P0 = quotient_n * P
k = G0.discrete_log(P0)
subsolutions.append(k)
subgroup.append(p ^ e) # k the order of G0
print("Running CRT...")
found_key = crt(subsolutions, subgroup)
assert found_key * G == P
assert private_key == found_key
print("success!")
이 코드 조각에서는 타원 곡선과 그 안의 생성기를 정의하고, 그 위수의 소인수를 출력합니다. 출력은 다음과 같습니다:``` Number of bits in n: 256 n's factors: 2 * 3 * 29 * 2699 * 28751 * 831913766251 * 92996710252298530263979 * 84878782522781478604307230464271
생성기의 차수는 `256 bit`이며, 여러 소인수로 분해되는데, 그중 가장 큰 두 개는 `77 bit` 및 `107 bit`입니다. 이들은 ECDLP를 푸는 것이 비현실적일 만큼 충분히 큽니다. 그런 다음, `64 bit` 개인 키가 무작위로 생성되고 공개 키가 계산됩니다. 다음 단계에서는 차수가 적어도 `64 bit` 길이가 될 때까지 충분한 소인수를 "수집"합니다. 출력은 다음과 같습니다:```
We know that the private key is 64 bits long
Lets find which of the factors of G's order are relevant for finding the private key
Found enough factors! The rest are not needed
Considering these factors: [(2, 1), (3, 1), (29, 1), (2699, 1), (28751, 1), (831913766251, 1)]
두 개의 가장 큰 인자는 중복되며, 우리가 남게 되는 가장 큰 인자는 40 bit임을 알 수 있습니다. 다음 단계에서는, 남은 각 인자에 대해 앞서 설명한 대로 점 𝐺′와 𝑃′를 계산하고, 각각에 대해 ECDLP를 풉니다. 결과와 소인수는 각각 subsolutions와 subgroups 리스트에 저장됩니다. 마지막으로, 모든 결과는 중국인의 나머지 정리(Chinese Remainder Theorem)를 사용하여 개인 키로 결합되며, 그것이 실제로 올바른지 검증합니다.
타원 곡선에서 점 덧셈의 정의를 살펴보면, 점 덧셈에는 𝑏 값이 사용되지 않고 𝑎와 𝑝 값만 사용된다는 흥미로운 성질을 발견할 수 있습니다. 즉, 한 곡선 위에 있는 점들을 더하는 것은 𝑏 값만 다른 또 다른 곡선에서도 유효할 수 있다는 뜻입니다. 물론 이는 점에 숫자를 곱하는 경우에도 마찬가지입니다. 사용자가 상대방으로부터 공개 키로 받은 점이 실제로 자신의 곡선 위에 있는지 검증하지 않으면, 무효 곡선 공격(Invalid Curve Attack)에 노출됩니다.
두 당사자가 어떤 타원 곡선 $E_1$에 합의했다고 가정해 봅시다. 공격자는 $𝐸_1$과 동일한 𝑎와 𝑝 값을 가지지만 𝑏 값이 다른 악의적인 곡선 $𝐸_2$를 만들 수 있습니다. 공격자는 곡선 $𝐸_2$에서 위수가 작은 점 𝑃, 예를 들어 위수가 3인 점을 선택할 것입니다. 물론 점 𝑃는 $𝐸_1$과 다른 𝑏 값을 가진 방정식을 만족하므로 $𝐸_1$ 위에 있지 않습니다. 공격자는 점 𝑃를 자신의 공개 키로 사용자에게 보냅니다. 사용자가 받은 점이 실제로 당사자들이 합의한 곡선 $𝐸_1$ 위에 있는지 확인하지 않는다고 가정해 봅시다. 사용자는 공격자로부터 받은 공개 키를 가져와 자신의 개인 키와 곱하여, ECDH 프로토콜의 정의에서 본 것처럼 공유 비밀 점이 되어야 할 점에 도달합니다. 사용자의 관점에서 볼 때, 그들은 곡선 $𝐸_1$에서 곱셈 연산을 계산할 것입니다. 그러나 점 𝑃는 전혀 $𝐸_1$ 위에 있지 않고 $𝐸_2$ 위에 있으므로, 사용자는 실제로 곡선 $𝐸_2$에서 곱셈 연산을 계산하게 됩니다. 이후 사용자는 공유 비밀 점을 사용하여 공격자와 통신을 계속합니다. 당사자들이 점의 𝑥 좌표를 AES 암호화 키로 사용한다고 가정해 봅시다. 이 경우 사용자는 어떤 메시지를 암호화하여 공격자에게 보냅니다.
𝑃의 위수가 3이므로 사용자가 계산할 공유 점은 3가지 가능성뿐입니다. 공격자는 이 가능한 점들을 모두 살펴본 다음, 그중에서 사용자가 보낸 암호화된 메시지를 성공적으로 복호화하는 키에 해당하는 점을 찾아냅니다. 이 점과 시작점 𝑃가 주어지면 공격자는 사용자의 개인 키를 3으로 나눈 나머지를 알아낼 수 있습니다. 공격자는 위수가 점점 커지는 추가 악성 𝑃 점, 예를 들어 5, 7 등의 점을 사용자에게 보낼 수 있습니다. 이러한 방식으로 공격자는 작은 수들로 사용자의 개인 키를 나눈 나머지를 나타내는 충분한 값들을 수집할 수 있습니다. 마지막으로 공격자는 이전 공격에서 본 것과 같은 방식으로 중국인의 나머지 정리를 사용하여 사용자의 개인 키를 계산할 수 있습니다.
여기에 더 직관적인 설명이 있습니다. 공격자는 사용자에게 예를 들어 길이가 2인 아주 작은 "원" 위의 점을 제공할 수 있습니다. 사용자는 이 "원"에서 어떤 수의 걸음이든 앞으로 나아가 도착점에 도달합니다. 공격자는 사용자의 도착점을 알고 있으며, 그 도착점은 2가지 가능성 중 하나입니다. 따라서 공격자는 사용자가 원에서 짝수 걸음 또는 홀수 걸음을 걸었는지 알 수 있습니다. 공격자는 사용자에게 길이가 3, 5, 7 등인 "원"들의 추가 점을 제공할 수 있습니다. 공격자가 이러한 인자들을 충분히 모을 때까지, 각 인자는 사용자가 걸은 걸음 수에 대한 약간의 정보만을 담고 있습니다. 마지막으로 공격자는 이 모든 값들을 결합하여 사용자가 걸은 정확한 걸음 수, 즉 사용자의 개인 키를 알아낼 수 있습니다.
다음 코드는 이 공격을 보여줍니다:```python from ecdsa.ecdsa import generator_128r1, curve_128r1 from Crypto.Util.number import long_to_bytes from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES import random
curve = curve_128r1 G = generator_128r1 n = G.order() p = curve.p() a = curve.a()
private_key = random.randrange(n)
def encrypt_data(shared_point, message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
message = pad(message.encode(), 16)
return cipher.encrypt(message)
def decrypt_data(shared_point, enc_message): if shared_point.is_zero(): x, y = 0, 0 else: x, y = shared_point.xy() key = long_to_bytes(int(x)).rjust(16, b"\x00") iv = long_to_bytes(int(y)).rjust(16, b"\x00") cipher = AES.new(key, AES.MODE_CBC, iv)
decrypted = cipher.decrypt(enc_message)
return unpad(decrypted, 16)
def ECDH(A): # Send our public key to the other side # Have them reach the shared point and # Send us an encrypted message using the shared point as key
# This part takes place remotely and is unknown to the attacker
shared_point = private_key * A
message = "Inconceivable!"
return encrypt_data(shared_point, message)
def brute_force_encrypted_message(A, encrypted_message, max_order): # Returns n such that n*A matches the key used to encrypt the message for i in range(1, max_order): shared_point = i * A try: # If both padding is correct and all characters are ascii # Then it is probably the correct encryption key decrypted = decrypt_data(shared_point, encrypted_message) decrypted = decrypted.decode() return i except: continue raise Exception("Did not find a value for one of the encrypted messages")
def find_curves_with_small_subgroup(p, a, max_order): # Yield tuples of (order, point) such that the point is # on a curve with the same a & p values, but different b # and the point's order is <= max_order orders_found = set() b = 0 while True: b += 1 if b == p: # Ran out of b values break if (4a^3 + 27b^2) % p == 0: # Curve is singular continue
E = EllipticCurve(GF(p), [a, b])
for _ in range(100):
R = E.random_point()
n = R.order()
for f, e in n.factor():
if f in orders_found:
continue
if f > max_order:
break
# Create a point with order f
orders_found.add(f)
P = (n // f) * R
assert P.order() == f
yield (f, P)
subsolutions = [] subgroup = [] max_order = 10000 upto = 1 for order, A in find_curves_with_small_subgroup(p, a, max_order): upto *= order print("Found point with order", order, "so now can find keys of size up to", upto)
# Send this point as our public key and get an encrypted message from other side
encrypted_message = ECDH(A)
# Find the value n such that: private_key = n (mod order)
key_mod_order = brute_force_encrypted_message(A, encrypted_message, max_order)
# Save result to be used in CRT later
subsolutions.append(key_mod_order)
subgroup.append(order)
# Found enough values to calculate private key
if upto >= n:
break
print("Found enough values! Running CRT...") found_key = crt(subsolutions, subgroup) print("Found private key", found_key) assert private_key == found_key print("success!")
이 코드 스니펫에서는 곡선과 생성자가 선택되고, 사용자가 개인 키를 무작위로 생성하여 ECDH 프로토콜의 모든 사용에 동일한 개인 키를 사용한다. `find_curves_with_small_subgroup` 함수는 각 점의 위수(order)가 비교적 작고, 그 점이 원래 곡선과 `𝑏` 값만 다른 어떤 곡선 위에 있도록 하는 점-위수 쌍들을 찾는다. 코드는 충분한 쌍이 발견될 때까지 이러한 쌍을 생성한다. 각 쌍에 대해 공개 키가 사용자에게 전송되고 사용자로부터 암호문이 수신된다.
암호문에 대해 무차별 대입을 수행하여 사용자의 개인 키 값을 현재 위수로 나눈 나머지로 알아낸다. 이 모든 결과는 저장되며, 마지막으로 중국인의 나머지 정리(Chinese Remainder Theorem)를 사용해 사용자의 개인 키를 계산하고 올바른지 검증한다. 이 경우 당사자들은 통신을 AES로 수행하기로 합의했으며, 암호화 키는 공유 비밀 점의 `𝑥` 좌표이고 IV는 해당 점의 `𝑦` 좌표이다.
공격의 복잡도는 $𝑂(𝑛_{𝑚𝑎𝑥})$이며, 여기서 $𝑛_{𝑚𝑎𝑥}$는 악성 점들의 위수 중 가장 큰 값이다. 이는 공격에서 "가장 무거운" 부분이 작은 "원"들 중 가장 큰 "원"에 대한 무차별 대입이기 때문이며, 운 좋게도 공격자는 이 값을 거의 완전히 제어할 수 있다. 따라서 이 공격은 복잡도 측면에서 비교적 효율적이다. 앞서 언급했듯이, 이 경우 문제의 근본 원인은 사용자가 수신한 점이 작업 중인 곡선 위에 있는지조차 확인하지 않는다는 것이다. 게다가 사용자는 ECDH를 새로 사용할 때마다 동일한 개인 키를 사용하는데, 이는 그리 안전하지 않다.
## 곡선이 특이한 경우
타원 곡선이 암호학적으로 안전하려면 가져야 하는 중요한 성질 중 하나는 비특이(non-singular) 곡선이라는 것이다. 비특이 곡선은 곡선의 "판별식(discriminant)"이라고 하는 특정 값이 0이 아닌 곡선이다. 이는 매개변수 `𝑎`와 `𝑏`가 다음 부등식을 만족할 때 성립한다:
$4a^3 + 27b^2 ≠ 0$
이 부등식을 만족하지 않는 곡선은 `특이점(singular point)`이라고 하는 "문제가 있는" 점을 갖는다. 이러한 점에는 두 가지 유형이 있다: 노드(node)와 첨점(cusp). 노드 점은 특이점에서 자기 자신과 교차하는 일종의 고리를 가진 곡선 위에 존재하며, 이 점을 지나는 서로 다른 두 접선을 그을 수 있다.
첨점은 곡선이 "뾰족한" 점으로, 마치 두 직선이 그 점에서 나오는 것처럼 보이지만 그 점에서 곡선에 접하는 접선은 단 하나뿐이다.
<img src="https://assets.kitploit.com/production/public/readmes/48932/a40d8ce67ecb97eeabe85b52937a8935bc917b622e02168d9047200ed54feafc.png" alt="Singular Elliptic Curves" width="500">
노드형 점에서는 이중근(double root)이 존재하므로 곡선의 방정식을 다음과 같이 쓸 수 있다:
$y^2 = (x-x_0)^2(x-x_1)\ \ \ \ (mod\ p)$
변수 $x$를 $(𝑥 + 𝑥_0)$로 치환하면 곡선을 왼쪽으로 "이동"시켜 다음 형태에 도달할 수 있다:
$y^2 = x^2(x+x_0-x_1)\ \ \ \ (mod\ p)$
이제 특이점은 좌표축의 원점에 있다. $t = (x_0-x_1)$의 수치를 사용하여 곡선 위의 점에서 정수로의 매핑을 만들 수 있으며, 곡선 위의 점들 간의 덧셈 연산은 수들 간의 곱셈 연산과 동등하게 된다. 각 점 `(𝑥, 𝑦)`에 대해 다음 수를 대응시킨다
$\frac{y+\sqrt{t}x}{y-\sqrt{t}x}$. 특히 `𝑄 = 𝑛𝐺`인 점의 쌍 `𝐺`와 `𝑄`에 대해 $𝑞 ≡ 𝑔^𝑛\ \ \ \ (mod\ p)$를 만족하는 수 `𝑔`와 `𝑞`를 대응시킬 수 있으며, 이는 "일반적인" DLP 문제이다. 이 과정을 설명하기 위해, 이 글의 끝에 있는 참고 자료에 작은 수를 사용한 예시 링크를 추가해 두었다. 우리가 수행한 매핑에서는 두 직선 $y+\sqrt{t}x$와 $y-\sqrt{t}x$의 방정식을 사용했으며, 이들은 (곡선을 "이동"시킨 후) 특이점에서 그을 수 있는 두 접선에 해당하는 직선이다. 이것이 기본적으로 이 공격을 사용할 수 있는 이유이다.
이러한 DLP 문제는 앞서 이미 살펴본 Pohlig-Hellman 알고리즘을 통해 효율적으로 풀 수 있는데, 이 알고리즘은 곡선 위의 점 대신 정수에도 사용할 수 있기 때문이다. 점의 맥락에서는 생성자의 위수가 매끄러운 수(smooth number)일 때 이 알고리즘이 유용하다는 것을 보았다. 곡선 위의 점들의 "원(circle)"은 어떤 위수든 가질 수 있는 반면, 소수 `𝑝`에 대한 정수체에서 위수는 `𝑝 − 1`이다. `𝑝 − 1`이 매끄러운 수라면, 이 알고리즘은 DLP 문제를 효율적으로 풀어 개인 키 `n`을 찾을 수 있다.
다음 코드 스니펫은 이를 수행한다:```python
p = 102360775616927576983385464260307534406913988994641083488371841417601237589487
a = -3
b = 2
assert (4*a^3 + 27*b^2) % p == 0
Gx = 1777671135698746847568710125129424132255529153914112337834835240247819869964
Gy = 6786424314307625790108882554225666781375821855884993473586521771737454762217
Qx = 45541468695354471317248123146376609839909398850045396377931300808635064950836
Qy = 42191909885728105279718027025083923092282618497451601162405594991792376530066
x = GF(p)["x"].gen()
f = x^3 + a*x + b
roots = f.roots()
assert len(roots) == 2 # two roots, so one must be double
if roots[0][1] == 2:
double_root = roots[0][0]
single_root = roots[1][0]
else:
double_root = roots[1][0]
single_root = roots[0][0]
print("double root:", double_root)
print("single root:", single_root)
# map G and Q to the new "shifted" curve
Gx = (Gx - double_root)
Qx = (Qx - double_root)
# Transform G and Q into numbers g and q, such that q=g^n
t = double_root - single_root
t_sqrt = t.square_root()
def transform(x, y, t_sqrt):
return (y + t_sqrt * x) / (y - t_sqrt * x)
g = transform(Gx, Gy, t_sqrt)
q = transform(Qx, Qy, t_sqrt)
print("g:", g)
print("q:", q)
# Find the private key n
print("Factors of p-1:", factor(p-1))
print("Calculating discrete log for g and q...")
found_key = discrete_log(q, g)
print("Found private key:", found_key)
from Crypto.Util.number import long_to_bytes
print("The secret is:", long_to_bytes(found_key).decode())
이 코드 스니펫에서 우리는 타원 곡선의 매개변수를 정의하고 그것이 실제로 특이(singular)한지 검증합니다. 곡선에 해당하는 다항식의 근을 찾고, 그중 어느 것이 이중근인지 식별합니다. 이중근을 사용하여 곡선을 "이동"하고, "이동된" 점 𝐺와 𝑄에 도달합니다. 그런 다음 찾은 근들로부터 $\sqrt{t}$를 계산하고 이를 사용하여 점 𝐺와 𝑄를 숫자 𝑔와 𝑞로 매핑합니다. 𝑝 − 1을 소인수로 분해한 결과를 출력합니다(DLP가 실제로 효율적으로 풀릴 수 있는지 확인하기 위함). 마지막으로 DLP를 계산하고 결과를 문자열로 해석합니다.
출력은 다음과 같습니다: ``` double root: 1 single root: 102360775616927576983385464260307534406913988994641083488371841417601237589485 g: 79308184675041981395063385790064051127319168083579208141274962436724168376607 q: 72551144069373709737718398534799929820619379063890479978458954196900267190559 Factors of p-1: 2 * 41 * 2422091127107 * 3224683479179 * 3224849279789 * 3269304069319
이번에는 개인 키 자체에 메시지를 숨겼습니다. 이 곡선은 특이 곡선이므로 SageMath에서 이전처럼 일반적인 방식으로 곡선을 만들고 그 위의 점을 정의한 뒤 연산을 수행할 수 없다는 점에 유의해야 합니다. 이 코드에서는 점들의 좌표를 상수 변수로 정의했습니다. 점 `𝑄`를 계산하기 위해 Double And Add 알고리즘을 직접 구현하여 개인 키와 생성자를 곱했습니다.
## 이 곡선은 초특이 곡선입니다
`𝑝`를 법으로 하는 타원 곡선과 위수가 `𝑛`인 생성자가 주어졌을 때, 이 생성자에 대한 곡선의 매립 차수(Embedding Degree)는 $p^k ≡ 1\ \ \ \ (mod\ 𝑛)$ 방정식을 만족하는 가장 작은 수 `k`로 정의됩니다. 특정 변환을 사용하면 ECDLP 문제가 위수 $𝑝^𝑘$인 체에서의 DLP 문제로 축소될 수 있습니다. `𝑘` 값은 보통 매우 큰 수(`𝑝` 자체와 거의 같은 크기)이지만, 상대적으로 작을 때(예: `6`보다 작을 때) 그 곡선을 `supersingular`라고 부르며, 이 DLP 문제를 효율적으로 해결하는 것이 가능해집니다. 이 공격은 세 명의 발명자(Menezes-Okamoto-Vanstone)의 이름을 따서 MOV 공격이라고 합니다.
제가 언급한 변환은 두 점을 입력받아 복소수 체의 어떤 수를 반환하는 함수입니다. 사용할 수 있는 변환으로는 Weil Pairing 또는 Tate Pairing이 있으며, 우리는 이를 블랙박스로 사용할 것입니다. 이러한 변환 `𝑇`는 모든 점의 쌍 `𝑃`, `𝑄`에 대해 다음 성질을 만족합니다:
$T(mP, nQ)=T(P,Q)^{mn}$
따라서 두 점 `𝐺`와 `𝑄 = 𝑚𝐺`가 주어졌을 때, 세 번째 점 `𝑅`을 임의로 선택하고 다음 두 값을 계산할 수 있습니다: \
$g = T(G, R)$ \
$q = T(Q, R)=T(mG,R)=T(G,R)^m=g^m$
이로부터 위수 $p^k$인 체에서 `𝑔`와 `𝑞`에 대한 DLP 문제를 풀어 개인 키 `𝑚`을 찾을 수 있습니다. 이 공격의 배후에 있는 수학에 대한 더 자세한 설명은 이 글의 끝에 있는 참고 자료에 링크를 포함해 두었습니다.
다음 코드 조각은 이 공격을 수행합니다:```python
p = 682209701131405092329016993551
a = -35
b = 98
E = EllipticCurve(GF(p), [a, b])
G = E(516365702870683577608927237052,
524474557735717484100814381066)
# Find embedding degree k
Gn = G.order()
k = 1
while p^k % Gn != 1:
k += 1
print("Found k:", k)
# Select private key, and calculate public key Q
private_key = 5072587499125503347
Q = private_key * G
# Define new curve mod p^k and the points on it
Ek = EllipticCurve(GF(p ^ k), [a, b])
Gk = Ek(G)
Qk = Ek(Q)
Rk = Ek.random_point()
# Find a point T with order d such that d divides G's order
m = Rk.order()
d = gcd(m, Gn)
Tk = (m // d) * Rk
assert Tk.order() == d
assert (Gn*Tk).is_zero() # Point INFINITY
# Using T, pair G and Q to integers g and q such that q=g^n (mod p^k)
g = Gk.weil_pairing(Tk, Gn)
q = Qk.weil_pairing(Tk, Gn)
# Alternatively:
#g = Gk.tate_pairing(Tk, Gn, k)
#q = Qk.tate_pairing(Tk, Gn, k)
# Make sure the pairing did not break anything
assert g ^ private_key == q
print("Calculating private key...")
found_key = q.log(g)
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
이 코드 스니펫에서는 곡선과 생성점을 정의하고, 그 임베딩 차수 값을 계산합니다. 이 경우 값은 2이므로 공격을 수행하기에 실용적입니다. 원래 곡선과 동일하되, 계산이 모듈로 $𝑝$ 대신 모듈로 $𝑝^𝑘$로 수행되는 곡선을 정의합니다. 두 점 𝐺와 𝑄도 새 곡선 위에 있습니다. 그런 다음 위수가 𝑛을 나누는 세 번째 점을 찾습니다.
세 번째 점을 사용하여 점 𝐺와 𝑄를 숫자 𝑔와 𝑞로 매핑하고 이들에 대한 이산 로그를 계산합니다. 마지막으로 얻은 결과가 실제로 올바른지 검증합니다.
출력은 다음과 같습니다:``` Found k: 2 Calculating private key... success! The private key is: Festivus
계산적인 관점에서, 오늘날에는 DLP 문제를 비교적 효율적으로 해결할 수 있는 Index Calculus 알고리즘이 존재하며, 이들은 $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ 의 복잡도로 이를 수행합니다. 이 식은 무섭게 보일 수 있지만, 복잡도가 $O(\sqrt{p})=e^{O(log\ p)}$ 인 ECDLP 알고리즘과 비교하면, Embedding Degree(`𝑘`로 표기)가 실제로 작다고 가정할 때 DLP 문제를 푸는 것이 더 쉽다는 것을 알 수 있습니다.
## 곡선이 변칙적인 경우
만약 어떤 곡선이 곡선의 위수(곡선 위의 점의 개수)가 정확히 모듈러스 `𝑝`와 같다는 성질을 가진다면, 그 곡선은 `Anomalous Curve`라고 불리며 Smart's Attack이라는 공격에 취약합니다. 이 공격은 `𝑝-adic numbers`를 사용합니다. 이러한 수는 계수를 가진 `p`의 거듭제곱(양의 거듭제곱과 음의 거듭제곱)의 합으로 표현할 수 있습니다. 형식적으로, 그러한 수 `s`는 다음 형태의 급수입니다:
$s=\sum_{i = -k}^{\infty} a_{i}p^i = a_{-k}p^{-k} + \cdots + a_0 + a_1p + a_2p^2 + \cdots$
계수가 $0 ≤ 𝑎_𝑖 < 𝑝$ 범위의 정수일 때, 그 합은 `𝑝`의 양의 거듭제곱 방향으로 무한할 수 있습니다. 이러한 수에서는 숫자를 왼쪽에서 오른쪽으로 보는 대신 오른쪽에서 왼쪽으로 "보며", 따라서 그러한 급수는 어떤 값으로 수렴할 수 있습니다. 이러한 수는 우리가 익숙한 수 체계와는 다른 수 체계에 속하며, "정상적인" 수학 규칙과는 매우 다르게 동작합니다. 이 주제만으로도 별도의 글 하나를 작성할 수 있으며, 이에 관심이 있는 분들을 위해 이 글의 끝에 있는 참고 문헌에 이 내용을 비교적 명확하게 소개하는 비디오 링크를 포함해 두었습니다.
어쨌든, 이 공격에서는 주어진 곡선으로부터 p진수 위에 정의된 새로운 곡선이 생성됩니다. 원래 곡선 위의 두 점 `𝐺`와 `𝑄 = 𝑚𝐺`가 주어졌을 때, 우리는 이를 새 곡선 위의 대응하는 점들로 매핑합니다. 얻어진 점들의 좌표로부터 `𝑚`을 쉽게 계산할 수 있습니다.
다음 코드는 이 공격을 수행합니다:```python
def lift(P, E, p):
# lift point P from old curve to a new curve
Px, Py = map(ZZ, P.xy())
for point in E.lift_x(Px, all=True):
# take the matching one of the 2 points corresponding to this x on the p-adic curve
_, y = map(ZZ, point.xy())
if y % p == Py:
return point
p = 82880337306360052550952380657384418102169134986290141696988204552000561657747
a = 26413685284385555604181540288021678971301314378522544469879270355650843743231
b = 10017655579196313780863100027113686719855502076415017585743221280232958057095
E = EllipticCurve(GF(p), [a, b])
G = E(37991937053350834320678619330546903567320901767090609881924528835279022654346,
28947208718252880061735762506756351277969075978732800286053352115837132331595)
assert E.order() == p
private_key = 28153370716511608040616395150859085058202177279382452583684367923334520519740
P = private_key * G
# Lift the points to some new curve over p-adic numbers
E_adic = EllipticCurve(Qp(p), [a+p*13, b+p*37])
G = p * lift(G, E_adic, p)
P = p * lift(P, E_adic, p)
# Calculate discrete log
Gx, Gy = G.xy()
Px, Py = P.xy()
found_key = int(GF(p)((Px / Py) / (Gx / Gy)))
assert found_key == private_key
print("success!")
from Crypto.Util.number import long_to_bytes
print("The private key is:", long_to_bytes(found_key).decode())
이 코드 스니펫에서는 lift 함수가 정의되는데, 이 함수는 원래 곡선 위의 한 점을 받아 새 곡선 위의 한 점에 대응시킵니다. 그런 다음 타원 곡선과 그 위의 생성자를 정의하고, 곡선의 위수가 실제로 p인지 확인합니다. 개인 키를 선택하고 해당 공개 키를 계산한 다음 공격을 수행합니다. 𝑝-adic 수 위에 새 곡선을 정의하고, lift 함수를 사용하여 원래 점 𝐺와 𝑃를 새 곡선 위의 대응 점으로 매핑한 뒤 𝑝를 곱합니다.
각 새 점에 대해 𝑥 좌표와 𝑦 좌표 사이의 비율을 계산합니다. 이 두 값의 몫이 원래 점들의 ECDLP 해가 됩니다.
출력은 다음과 같습니다:``` success! The private key is: >>>>> Extraordinarily Nice <<<<<
이 계산이 성립하는 이유는 곡선 위의 점의 개수가 정확히 `𝑝`라는 사실과 관련이 있습니다. 이 속성 덕분에 여러 매핑을 수행할 수 있으며, 그중 마지막 매핑은 𝑝-adic 수 위의 곡선 위의 점들을 모듈로 $p^2$ 수에 대응시킵니다. 이 매핑은 두 원본 점에 대응하는 숫자 쌍의 비율이 정확히 두 점의 로그 결과와 같다는 속성을 가집니다. 우리는 이 모든 매핑을 블랙박스로 남겨 두지만, 기사 끝부분에 관련 수학적 설명에 대한 참조를 추가했습니다.
# ECDSA 공격
## 메시지를 서명하기 전에 해시하지 않기
메시지 서명 과정에서 먼저 메시지의 해시를 계산하고, 그 해시의 상위 비트를 서명 계산에 사용한다는 것을 보았습니다. 어떤 서명 생성 및 검증 구현에서 이 해싱 단계가 생략되고, 해시의 상위 비트를 사용하는 대신 메시지의 비트를 그대로 사용한다고 가정해 봅시다. 이러한 구현에서 메시지의 서명에 영향을 주는 유일한 부분은 메시지의 시작 부분입니다. 다시 말해, 메시지와 그 서명이 있다면 메시지의 시작 부분을 유지하고 나머지를 변경해도 서명은 유효하게 유지됩니다. 정말 간단한 공격입니다.
예를 들어, 은행에 다음과 같은 메시지를 작성하고 해시 없이 서명한다고 가정해 봅시다:```
"Please transfer 1,000$ from my account to GitHub so that they can continue hosting awesome repositories"
은행은 이 메시지를 성공적으로 검증하고 해당 작업을 수행할 것입니다. 일부 ... 공격자는 ... 다음과 같은 메시지를 생성할 수 있습니다:``` "Please transfer 1,000$ from my account to GitHub and 1,000,000$ to Eli Kaski"
그리고 방금 만든 서명을 사용하세요. 서명은 이 메시지에도 유효하며, 은행은 작업을 수행할 것입니다. 좋지 않습니다 (음, 누구에게는 다르겠지만).
다음 코드는 공격을 보여줍니다:```python
from ecdsa import SigningKey, NIST256p
signing_key = SigningKey.generate(NIST256p)
verifying_key = signing_key.verifying_key
class MyHash:
def __init__(self, data):
self.data = data
def digest(self):
return self.data
# Sign the message and verify the signature
message = "Please transfer 1,000$ to GitHub"
signature = signing_key.sign(message.encode(), hashfunc=MyHash)
assert verifying_key.verify(signature, message.encode(), hashfunc=MyHash)
# Construct an evil message and verify the original message's signature is valid for it as well
evil_message = "Please transfer 1,000$ to GitHub and 1,000,000$ to Eli Kaski"
assert verifying_key.verify(signature, evil_message.encode(), hashfunc=MyHash)
print("success!")
이 코드 스니펫에서는 알려진 곡선과 함께 ecdsa 라이브러리가 사용됩니다. 해시 함수를 구현해야 하지만 그렇게 하지 않고 메시지를 그대로 두는 클래스를 정의합니다. 따라서 메시지에 서명할 때 해시가 아닌 원본 메시지의 첫 비트만 사용됩니다. 그런 다음 메시지가 서명되고 성공적으로 검증됩니다. 이후 악의적인 메시지가 생성되고, 코드는 원본 메시지의 서명이 악의적인 메시지와도 일치하는지 검증합니다.
이러한 시나리오에서는 우리만의 새 서명을 생성하기 위한 개인 키를 얻지 못했을 수 있지만, 서명 하나가 주어지면 동일한 접두사로 시작하기만 하면 원하는 만큼 많은 메시지에 서명할 수 있습니다.
k 값 재사용메시지 서명 과정의 일부로, 사용자는 𝑘 값을 무작위로 생성하여 메시지에 서명하는 데 사용해야 합니다. 서로 다른 서명에서 서로 다른 𝑘 값을 사용하는 것이 매우 중요합니다. 그렇지 않으면, 사용자가 다시 생성하지 않고 동일한 𝑘 값을 사용한 두 개의 서명된 메시지가 주어졌을 때, 공격자가 사용자의 개인 키를 계산할 수 있습니다.
앞서 언급했듯이, 메시지 서명 중에 사용자는 $r=x_1\ \ \ \ (mod\ p)$ 및 $s=k^{-1}(z+rd_A)$를 공개적으로 전송합니다. 사용자가 $𝑧_1$과 $𝑧_2$에 해당하는 두 개의 서로 다른 메시지에 서명하고, 두 쌍의 값 $𝑟, 𝑠_1$과 $𝑟, 𝑠_2$를 공개적으로 전송했다고 가정합니다. 즉, 이 두 서명에서 동일한 𝑘 값을 사용했습니다. 다음을 확인할 수 있습니다:
$s_1-s_2=k^{-1}(z_1+rd_A)-k^{-1}(z_2+rd_A)=k^{-1}(z_1+rd_A-z_2-rd_A)=k^{-1}(z_1-z_2)$
이로부터 공격자는 다음을 계산하여 𝑘 값을 찾을 수 있습니다:
$\displaystyle k=\frac {z_1-z_2}{s_1-s_2}$
공격자가 𝑘를 찾은 후, 서명 중 하나에서 사용자의 개인 키를 계산할 수 있습니다. 다음을 참고하세요:
$r^{-1}(ks-z)=r^{-1}(kk^{-1}(z+rd_A)-z)=r^{-1}(z+rd_A-z)=r^{-1}rd_A=d_A$
메시지와 해당 서명의 𝑟, 𝑠, 𝑧 값과 공격자가 찾은 𝑘 값을 알고 있다면, 공격자는 $d_A=r^{-1}(ks-z)$를 계산할 수 있습니다. 이 시점부터 공격자는 개인 키를 획득한 사용자를 대신하여 원하는 모든 메시지에 서명할 수 있습니다.
다음 코드 스니펫은 이 공격을 수행합니다:```python from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key from Crypto.Util.number import bytes_to_long, long_to_bytes from hashlib import sha256 import random
curve = curve_256 generator = generator_256 n = generator.order()
secret_key = 6743529130774090927928101169617481154782309 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
k = random.randrange(curve.p()) message1 = "Life is like a box of chocolates." message2 = "You never know what you're gonna get." z1 = bytes_to_long(sha256(message1.encode()).digest()) z2 = bytes_to_long(sha256(message2.encode()).digest())
signature1 = private_key.sign(z1, k) signature2 = private_key.sign(z2, k)
found_k = (z1 - z2) * inverse_mod(signature1.s - signature2.s, n) % n assert k == found_k
found_key = inverse_mod(signature1.r, n) * (found_k * signature1.s - z1) % n assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
In this code snippet, the library ecdsa is used, along with a known curve. We define a private key and use it to sign two messages. The value of `𝑘` is randomly generated, but it remains the same for the two signatures. Given the two messages and their signatures, the code performs the calculation we saw to find `𝑘`. Finally, we use the value of `𝑘` we found to calculate the private key as we saw. The output is:```
Success!
The secret is: Mistakes were made
이 공격은 실제로 2010년에 사용되었다는 점이 흥미롭다. 당시 소니는 PlayStation 콘솔 소프트웨어에 서명 메커니즘을 안전하지 않게 구현했다. 소니는 서명에 𝑘의 정적 값을 사용했고, 이로 인해 공격자는 위의 계산을 사용하여 소니의 개인 키를 얻을 수 있었다. 이로 인해 임의의 코드에 서명하고 PlayStation이 이를 실행하도록 할 수 있게 되었다. 이후 이 기능은 콘솔에 불법 복제 및 비공식 게임을 설치하는 데 사용되었다.
k 값을 안전하지 않게 생성하기사용자가 𝑘를 충분히 무작위적이지 않은 방식으로 선택하면 개인 키를 찾을 수 있다. 예를 들어, 공격자가 𝑘가 매우 작은 값 범위에 있다는 것을 알거나 𝑘의 일부 바이트를 알고 있다면, 단일 서명된 메시지만으로도 단순한 무차별 대입을 통해 사용자의 개인 키를 찾는 것이 가능하다. 공격자는 이전 공격에서 본 계산을 다양한 𝑘 값에 대해 반복 실행하여 올바른 값에 도달하면 그로부터 개인 키를 얻는다.
이 문제를 해결하기 위해 사용자는 때때로 어떤 값을 무작위로 생성하고, 특정 해시 함수로 그 해시를 계산한 다음, 그 결과를 𝑘로 사용한다. 이 방법은 문제를 일으킬 수 있다. 예를 들어, 생성자의 위수 𝑛가 256 bit이고 선택된 해시 함수가 SHA-1이라고 가정하자. 이 함수의 출력은 160 bit 숫자이다. modulo 𝑛 계산에서 𝑘 값의 시작 부분에 96개의 0이 포함되는 것으로 알려져 있으며, 이는 𝑘가 상대적으로 작은 숫자임을 의미한다. 이러한 상황에서 𝑘 값들은 biased(편향)되었다고 하며, 동일한 개인 키로 서명된 여러 메시지가 주어지면 개인 키를 찾을 수 있다.
이 공격은 격자(Lattice)라고 하는 대수적 구조에 기반한다. 비공식적으로, 격자는 𝑚차원 공간의 벡터 집합으로 생각할 수 있으며, 각 벡터는 정수 계수를 가진 기저(basis) 벡터들의 선형 결합으로 표현될 수 있다. 수학적으로, $\{b_1,\dots,b_d\}$가 $ℝ^𝑚$ 위의 기저 벡터들이라면, 이에 대응하는 격자는 $L=$ $\{\sum_{i=1}^d a_ib_i\mid a_i \in Z\}$이다. 이 구조에는 잘 알려진 문제가 있다: 격자의 기저가 주어졌을 때, 격자에 존재하는 가장 짧은 벡터를 찾는 것이다. 이 맥락에서 비공식적으로 '짧은 벡터(short vector)'란 각 원소가 가능한 한 0에 가까운 벡터를 의미한다. 이 문제는 SVP(Shortest Vector Problem, 최단 벡터 문제)라고 불리며 NP-난해(NP-hard)로 간주된다. 유사하지만 더 쉬운 문제 - 격자에서 최단 벡터에 상대적으로 '가까운' 어떤 짧은 벡터를 찾는 문제 - 를 해결하는 알고리즘들이 있다. 이 문제는 CVP(Closest Vector Problem, 최근접 벡터 문제)라고 불리며, 이를 해결하는 알고리즘 중 하나가 LLL(Lenstra-Lenstra-Lovász) 알고리즘이다. 이 공격에서는 이 알고리즘을 블랙박스로 사용할 것이다.
𝑑개의 서명된 메시지가 주어지면 $(𝑘_1, \dots , 𝑘_𝑑)$ 벡터를 포함하는 격자를 구성할 수 있다. 여기서 벡터의 각 원소는 하나의 서명에 해당하는 𝑘 값이다. LLL 알고리즘은 이 격자에서 최단 벡터에 대한 근사치를 찾을 것이다. 𝑘 값들이 작은 것으로 알려져 있으므로, 알고리즘이 찾은 짧은 벡터가 적어도 하나의 올바른 k 원소를 포함할 확률이 높다. 올바른 𝑘를 찾으면 이전 공격에서 보았듯이 개인 키를 계산할 수 있다.
이 격자를 구성하려면 기저 벡터들을 정의해야 한다. 이 기사 끝부분의 참고 자료에 이러한 기저 벡터가 어떻게 정의되는지 설명하는 문서 링크를 포함해 두었다. 기술적으로, 격자의 기저 벡터들은 행렬로 표현할 수 있으며, 행렬의 각 행은 하나의 기저 벡터의 원소들로 구성된다. LLL 알고리즘의 정확도를 높이기 위해, 이 행렬에 𝑘 값의 예상 크기와 𝑘와 𝑛 사이의 비율에 대한 정보를 담은 두 개의 열을 추가하는 것이 권장된다. 이러한 개선 사항은 내가 첨부한 참고 자료에도 설명되어 있다. 다음 코드 조각은 이 공격을 보여준다:```python
from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from Crypto.Util.number import bytes_to_long, long_to_bytes
from hashlib import sha1
import random
def build_matrix(signatures, bias, q): # M matrix should be: """ [ B 0 m'1 m'2 m'2 ... m'n 0 B/q r'1 r'2 r'3 ... r'n 0 0 0 0 q * I 0 0 ] where: m' = s^-1 * m r' = s^-1 * r """
# Construct the first 2 rows of M:
row1 = [bias, 0]
row2 = [0, bias / q]
for m, r, s in signatures:
row1.append((inverse_mod(s, q) * m) % q)
row2.append((inverse_mod(s, q) * r) % q)
top_rows = Matrix(QQ, [row1, row2])
# Construct the q*I block along with 2 columns of zeros
zero_cols = zero_matrix(QQ, len(signatures), 2)
qI = q * identity_matrix(QQ, len(signatures))
bottom_rows = block_matrix([[zero_cols, qI]])
# Combine all rows into one matrix
M = top_rows.stack(bottom_rows)
return M
def find_private_key(L, signatures, public_key): # Check if any valid k was found in L generator = public_key.generator q = generator.order() for row in L.rows(): for i in range(len(signatures)): m,r,s = signatures[i] # Skip the first two vector components we used to improve LLL possible_k = row[i+2] # LLL might have swapped the sign of the found short vectors for k in [possible_k, -possible_k]: d = inverse_mod(r,q)(ks-m) % q if d*generator == public_key.point: return d
curve = curve_256 generator = generator_256 q = int(generator_256.order())
secret_key = 1793056234309773077862125006843383726029262764680727851636 public_key = Public_key(generator, generator * secret_key) private_key = Private_key(public_key, secret_key)
messages_to_sign = [ "And then I go and spoil it all", "By saying somethin' stupid like", "I love you" ]
signatures = [] for message in messages_to_sign: message_hash = bytes_to_long(sha1(message.encode()).digest()) k = bytes_to_long(sha1(long_to_bytes(random.randrange(q))).digest()) signature = private_key.sign(message_hash, k) signatures.append((message_hash, signature.r, signature.s))
bias = 2^160 M = build_matrix(signatures, bias, q)
L = M.LLL()
found_key = find_private_key(L, signatures, public_key) assert found_key == secret_key print("success!") print("The secret is:", long_to_bytes(found_key).decode())
이 코드 스니펫에서는 표준 곡선이 사용되고, 개인 키가 선택된 다음 이로부터 해당 공개 키가 계산됩니다. 3개의 메시지가 생성되고 SHA-1 해시 함수의 결과인 3개의 임의의 `k` 값으로 서명됩니다. 그런 다음 기사에서 설명한 대로 격자의 기저에 해당하는 행렬을 만들고, 그 행렬에 LLL 알고리즘을 실행합니다. 이후 결과 행렬의 행들을 살펴보며 그중 하나에서 올바른 `𝑘` 값이 발견되는지 확인합니다.
이 확인은 이전 공격에서 살펴본 것처럼 잠재적인 `𝑘`로부터 개인 키를 계산하고, 수신된 키가 실제로 올바른지 확인하는 방식으로 수행됩니다. 마지막으로, 찾은 개인 키가 실제로 올바른지 확인합니다. 출력은 다음과 같습니다.```
success!
The secret is: I am Jack's broken heart
이 공격의 복잡도는 LLL 알고리즘의 복잡도와 동일하며, 이는 $O(d^6\ \log^3B)$입니다. 여기서 𝐵는 𝑘의 바이어스 길이(이 경우 $2^{160}$)를 나타내고, 𝑑는 서명된 메시지의 수(이 경우 3)를 나타냅니다. 공격을 실행하는 데 필요한 서명된 메시지의 최소 수는 얼마인가에 대한 질문이 제기됩니다. 이에 대한 답은 $\displaystyle d=O(\frac {\log n}{\log n-\log B})$ 입니다. 여기서 𝑛은 생성자의 차수이고 𝐵는 바이어스입니다. 이에 대한 설명은 이 글의 끝에 참고 문헌으로 첨부한 두 번째 링크에 나와 있습니다.
실제로 이 공격의 변형은 𝑘의 상위 비트가 알려진 경우나 𝑘의 임의의 비트가 알려진 경우에도 실행할 수 있습니다. 단 하나의 비트 값만 알려진 경우에도 공격을 실행할 수 있으며, 단 하나의 비트 값이 50%보다 높은 확률로 알려진 경우에도 실행할 수 있습니다! 물론 이러한 경우에는 공격을 수행하기 위해 훨씬 더 많은 서명된 메시지가 필요합니다.
서명 검증 과정에서 서명 당사자는 𝑟 및 𝑠 값의 쌍을 검증 당사자에게 보낸다는 것을 살펴보았습니다. 예를 들어 HTTPS 프로토콜을 구현하는 브라우저에서는 이 값 쌍을 인증서에 포함하여 보내는 것이 일반적이며, 인증서에는 서명 당사자가 사용한 곡선에 대한 데이터도 포함될 수 있습니다. 검증 당사자는 인증서에서 찾은 곡선 데이터가 사전에 합의된 곡선과 일치하는지 확인해야 합니다. 일치하지 않으면 문제가 발생할 수 있습니다.
특정 곡선에서 Alice가 개인 키 $d_A$와 이에 대응하는 공개 키 $𝑃_𝐴$를 가지고 있다고 가정해 봅시다. 즉, 이 곡선의 생성자 𝐺에 대해 $𝑃_𝐴 = 𝑑_𝐴𝐺$가 성립합니다. Alice는 개인 키 $𝑑_𝐴$를 사용하여 ECDSA 프로토콜 정의에서 살펴본 것처럼 자신의 메시지에 서명할 수 있습니다. 이제 서명을 검증하는 당사자가 사용자로부터 생성자 𝐺도 수신하지만, 사용자로부터 받은 생성자가 실제로 합의된 생성자인지 확인하지 않는다고 가정해 봅시다. 공격자는 Alice의 공개 키인 점 $𝐺^′ = 𝑃_𝐴$를 생성자로 보낼 수 있습니다. 공격자는 "가짜" 개인 키로 $𝑑_𝐴^′ = 1$ 값을 선택할 것이며, 따라서 $𝑃_𝐴 = 𝑑_𝐴^′𝐺^′$이 성립함은 명백합니다. 이는 공격자가 Alice의 공개 키에 대응하는 개인 키를 가지고 있다고 "증명"할 수 있음을 의미합니다. 따라서 공격자는 원하는 메시지를 만들고, $𝑑_𝐴^′$를 사용하여 일반적인 방식으로 𝑟 및 𝑠 값 쌍을 계산할 수 있으며, 결과 서명은 성공적으로 검증될 것입니다.
직관적으로, 서명 검증 과정에서 서명 당사자는 자신이 공개 키의 "소유자"임을 증명합니다. 공개 키는 사실상 곡선 위의 "목적지" 점입니다. 이는 시작점에서 목적지 점에 도달하기 위해 몇 단계를 이동해야 하는지 아는 사람이 서명자뿐이기 때문입니다. 검증 당사자가 사용자로부터 받은 시작점이 실제 시작점인지 확인하지 않으면, 공격자는 시작점이 곧 목적지 점이고, 그곳에서 이동할 단계 수가 0이라고 결정할 수 있습니다. 서명 검증의 다른 모든 부분은 동일하게 유지되며, 서명은 성공적으로 검증됩니다. 이 공격을 Curveball이라고 합니다.
이 공격은 추가 값으로 일반화할 수 있습니다. 공격자는 어떤 값 𝑥를 선택하고 $𝐺^′ = 𝑥𝑃_𝐴$를 계산합니다. 가짜 개인 키는 $𝑑'_𝐴 = 𝑥^{−1}\ \ \ \ (mod\ n)$이 됩니다. 그러면 $𝑑'_𝐴𝐺^′ = 𝑥^{−1}𝑥𝑃_𝐴 = 𝑃_𝐴$가 성립함이 분명합니다.
다음 코드는 공격을 보여줍니다:```python from ecdsa.ecdsa import generator_256 from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random
def hash_message(message): return bytes_to_long(sha256(message.encode()).digest())
def verify(public_key, G, message, r, s): n = G.order() if r < 1 or r > n - 1 or s < 1 or s > n-1: return False hash = hash_message(message) u1 = (hash * inverse_mod(s, n)) % n u2 = (r * inverse_mod(s, n)) % n P = u1 * G + u2 * public_key return P.x() % n == r
def sign(private_key, G, message): n = G.order() k = random.randrange(n) hash = hash_message(message)
r = (k * G).x() % n
s = inverse_mod(k, n) * (hash + r * private_key) % n
return r, s
G = generator_256 n = G.order() private_key = random.randrange(n) public_key = private_key * G
message = "Let me be the one that shines with you" r, s = sign(private_key, G, message) assert verify(public_key, G, message, r, s)
x = random.randrange(n) fake_G = x * public_key fake_private_key = inverse_mod(x, n) assert fake_private_key != private_key assert fake_G != G
evil_message = "Where did I go wrong?" r, s = sign(fake_private_key, fake_G, evil_message) assert verify(public_key, fake_G, evil_message, r, s)
이 코드 스니펫에서는 알려진 생성기, 개인 키 및 공개 키를 선택합니다. 메시지에 서명하고 성공적으로 검증되는지 확인합니다. 그런 다음 원래 공개 키와 모두 일치하는 가짜 개인 키와 가짜 생성기를 만듭니다. 악의적인 메시지가 가짜 키로 서명되고, 마지막으로 가짜 서명이 원래 공개 키로 성공적으로 검증됩니다. 이 코드의 문제는 검증 알고리즘이 생성기 `𝐺`가 공개 키와 일치하는지 검증하지 않는다는 것입니다. 이 공격에서 사용자의 개인 키를 찾지는 못했지만, 공격자는 서명 검증의 잘못된 구현을 악용하여 성공적으로 검증되는 서명을 만들 수 있습니다. 그러나 공격자는 올바른 서명 검증 구현에서 실제로 성공적으로 검증될 "실제" 서명을 만들 수는 없습니다.
흥미롭게도 이것은 Windows CryptoAPI 아키텍처에 존재했던 실제 취약점입니다. 인증서의 서명을 검증하는 기능에서는 인증서 자체에 곡선 매개변수가 포함된 경우 해당 매개변수에 대한 검증이 충분하지 않았습니다. 특히, 생성기가 공개 키에 대응하는 실제 생성기인지 확인하는 검사가 없었습니다. 공격자는 신뢰할 수 있는 인증 기관(Certificate Authority)이 서명한 것처럼 보이기 때문에 신뢰할 수 있는 것으로 간주되는 가짜 인증서를 만들 수 있었습니다. 이는 인증서에 악의적인 곡선 필드를 추가하고 제가 설명한 방식으로 생성기를 선택함으로써 이루어졌습니다. 이 취약점은 NSA 기관이 발견했으며, 2020년에 수정되었고 CVE-2020-0601 번호를 받았습니다.
# 결론
## ECDH 공격 개요
| 문제 유형 | 문제 | 공격 | 공격 방식 | 공격 복잡도 |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| 안전하지 않은 생성기를 가진 곡선 선택 | 생성기 `n`의 위수가 너무 작음 | Baby-Step Giant-Step | 중간 일치(Meet In The Middle) | $𝑂(\sqrt n)$ |
| 안전하지 않은 생성기를 가진 곡선 선택 | 생성기 `n`의 위수가 스무스(smooth)한 수임 | Pohlig-Hellman | `𝑛`을 소인수로 분해하고, 각각을 개별적으로 공격한 후, 중국인의 나머지 정리를 사용하여 결과를 결합 | $O(\sqrt{p_{max}})$ 여기서 $p_{max}$는 `𝑛`의 분해에서 가장 큰 소인수 |
| 안전하지 않은 생성기를 가진 곡선 선택 + 안전하지 않은 개인 키 선택 | 생성기 `n`의 위수가 거의 스무스한 수이고, 개인 키가 작음 | Improved Pohlig-Hellman | `𝑛`을 소인수로 분해하고, 너무 큰 인자는 버린 다음, 각각을 개별적으로 공격하고, 중국인의 나머지 정리를 사용하여 결과를 결합 | $O(\sqrt{p_{max}})$ 여기서 $p_{max}$는 `𝑛`의 분해에서 가장 큰 소인수 |
| ECDH의 잘못된 구현 | 점이 곡선 위에 있는지 검증하지 않음 | Invalid Curve Attack | 악의적인 곡선에서 작은 위수를 가진 점들을 공개 키로 보내고, 각각을 개별적으로 공격한 후, 중국인의 나머지 정리를 사용하여 결과를 결합 | $𝑂(𝑛_{𝑚𝑎𝑥})$ 여기서 $𝑛_{𝑚𝑎𝑥}$는 악의적인 점들의 위수 중 가장 큰 위수 |
| 곡선 매개변수를 안전하지 않게 선택 | 곡선이 특이(singular)함 | ECDLP를 DLP로 축소 | 점의 덧셈을 정수의 곱셈으로 변환하는 방식으로 점들을 숫자에 매핑 | $O(\sqrt{p_{max}})$ 여기서 $p_{max}$는 $(p-1)$의 분해에서 가장 큰 소인수 |
| 곡선 매개변수를 안전하지 않게 선택 | 곡선이 초특이(supersingular)함 | ECDLP를 DLP로 축소 | 점의 덧셈을 정수의 곱셈으로 변환하는 방식으로 점들을 숫자에 매핑 | $e^{O((log\ p^k)^{1/3}(log\ log\ p^k)^{2/3})}$ 여기서 `k`는 생성기에 대한 임베딩 차수(embedding degree) |
| 곡선 매개변수를 안전하지 않게 선택 | 곡선이 변칙적(anomalous)임 | Smart 공격 | 곡선 위의 점들을 `p-adic` 수 위의 곡선 위의 점들로, 그리고 다시 정수로 매핑하는 일련의 매핑 | $O(1)$ |
## ECDSA 공격 개요
| 문제 유형 | 문제 | 공격 | 공격 방식 | 공격 복잡도 |
| ------------- | ------------- | ------------- | ------------- | ------------- |
| 서명 및 검증의 잘못된 구현 | 서명하기 전에 메시지를 해시하지 않음 | 서명된 메시지가 주어졌을 때, 동일한 서명에 해당하는 추가 메시지를 위조 | 메시지 접두사는 그대로 두고 나머지를 수정 | $O(1)$ |
| 서명 알고리즘의 잘못된 사용 | 서로 다른 서명에서 동일한 `k` 값을 재사용 | 사용자의 개인 키 찾기 | `k` 값을 찾고, 이를 통해 사용자의 개인 키를 계산 | $O(1)$ |
| 서명 알고리즘의 잘못된 사용 | `k` 값을 안전하지 않게 생성 | 여러 개의 서명된 메시지가 주어졌을 때, 사용자의 개인 키 찾기 | 문제를 격자(lattice)에서 짧은 벡터 찾기로 축소하고, `k` 값을 찾은 다음, 이를 통해 사용자의 개인 키를 계산 | $O(d^6\ \log^3B)$ 여기서 `B`는 `k`의 바이어스(bias)이고, `d`는 서명된 메시지의 수 |
| 검증의 잘못된 구현 | 생성기가 유효한지 검증하지 않음 | 성공적으로 검증되는 서명 위조 (Curveball) | 다른 사용자의 공개 키에 대응하는 가짜 생성기와 개인 키를 선택 | $O(1)$ |
## 이러한 공격에 대한 보호
ECDH에서는 프로토콜 시작 시 양 당사자가 곡선에 동의해야 한다는 점에 유의해야 합니다. 사용자가 공격자와 통신하고 있고 공격자가 곡선 매개변수를 제공하는 경우, 공격자는 안전하지 않은 매개변수를 제공할 수 있습니다. 그 결과 공격자는 사용자의 개인 키를 얻을 수 있습니다. 사용자가 항상 동일한 개인 키를 사용한다면, 공격자는 해당 사용자와 다른 사용자 간의 모든 대화를 복호화할 수 있습니다. 따라서 신뢰할 수 없는 낯선 사용자가 곡선 매개변수를 제공하는 것을 허용하지 않는 것이 매우 중요합니다. 또한 외부 사용자로부터 수신한 모든 점이 실제로 합의된 곡선 위에 있는지 확인해야 합니다. 그리고 물론 선택한 곡선 자체가 우리가 본 알려진 공격 중 하나에 취약하지 않은지도 확인해야 합니다. 또한 ECDH 프로토콜을 사용할 때마다 새 개인 키를 사용하는 것이 좋습니다.
마찬가지로 ECDSA에서도 서명 및 검증 알고리즘을 올바르게 구현하기 위해 주의를 기울여야 합니다. 프로토콜을 사용할 때마다 메시지 해시와 `𝑘` 값의 무작위적이고 안전한 생성을 건너뛰지 말고, 물론 서명 검증에서 생성기가 사용자로부터 수신된 경우 이전에 합의된 생성기가 맞는지 확인하십시오.
## 참고 자료
- 이 글에서는 Christof\
paar: 저서 Understanding Cryptography의 그래프 차트를 사용했습니다.\
https://gnanavelrec.wordpress.com/wp-content/uploads/2019/06/2.understanding-cryptography-by-christof-paar-.pdf
- 암호화 타원 곡선이 어떻게 생겼는지 보여주는 사이트:\
https://graui.de/code/elliptic2/
- 타원 곡선에서 덧셈과 곱셈 연산에 대한 자세한 설명:\
https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- 타원 곡선 및 점 덧셈에 대한 소개 강의 - Christof Paar:\
https://www.youtube.com/watch?v=vnpZXJL6QCQ
- 생성기, ECDLP, 문제의 난이도, ECDH, Double And Add에 대한 강의 - Christof Paar:\
https://www.youtube.com/watch?v=zTt4gvuQ6sY
- 다양한 암호화 알고리즘의 보안 수준(Security Level) 설명:\
https://en.wikipedia.org/wiki/Security_level
- ECDH 설명:\
https://en.wikipedia.org/wiki/Elliptic-curve_Diffie%E2%80%93Hellman
- ECDSA 설명:\
https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
- ElGamal 서명 설명:\
https://en.wikipedia.org/wiki/ElGamal_signature_scheme
- 중국인의 나머지 정리 설명:\
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
- 특이 곡선의 판별식과 이 곡선이 이중 근을 갖는 사실 사이의 관계에 대한 설명:\
https://www.quora.com/For-an-elliptic-curve-in-the-form-Y-2-X-3+AX+B-why-is-4A-3+27B-2-neq-0-the-condition-for-non-singularity
- 특이 곡선에서 점과 숫자 사이의 매핑에 대한 작은 숫자의 예:\
https://crypto.stackexchange.com/questions/61302/how-to-solve-this-ecdlp/61434#61434
- 𝑝-adic 수에 대한 설명:\
https://en.wikipedia.org/wiki/P-adic_number \
https://www.youtube.com/watch?v=3gyHKCDq1YA
- MOV 공격의 수학적 배경 설명:\
https://risencrypto.github.io/WeilMOV/
- Smart 공격의 수학적 배경 설명 (상당히 복잡하니 주의하세요):\
https://wstein.org/edu/2010/414/projects/novotney.pdf \
http://www.monnerat.info/publications/anomalous.pdf
- 격자 기반 공격과 LLL 알고리즘에 대한 설명:\
https://forum.vac.dev/t/lattice-attacks-on-ecdsa/136 \
\
이 공격은 Joachim Breitner와 Nadia Heninger의 논문 파트 4에 기반합니다:\
https://eprint.iacr.org/2019/023.pdf
- CVP 문제 설명:\
https://en.wikipedia.org/wiki/Lattice_problem#Closest_vector_problem_(CVP)
- LLL 알고리즘 설명:\
https://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm