SSH의 공개키 암호화에는 'RSA', 'DSA', 'ECDSA', 'EdDSA' 중 어떤 것을 사용하면 좋을까?

원격으로 컴퓨터에 액세스하기 위한 프로토콜인 SSH는 컴퓨터의 인증을 위해 공개키 암호화를 사용하고 있습니다. 공개키 암호화 방식인 RSA, DSA, ECDSA, EdDSA의 각각의 구조와 'SSH에 적합한 방식'에 대해 소프트웨어 기업 Gravitational의 Virag Mody 씨가 해설합니다.

Comparing SSH Encryption Algorithms - RSA, DSA, ECDSA, or EdDSA?
https://gravitational.com/blog/comparing-ssh-keys/

Comparing SSH Encryption Algorithms - RSA, DSA, ECDSA, or EdDSA?

공개키 암호화는 암호화와 복호화에 다른 키를 사용하는 암호화 방식. 예를 들어, 밥과 앨리스가 통신을 할 때, 앨리스는 비밀 키와 공개키를 생성하고 공개키를 밥에 전달해야 합니다. 밥은 앨리스의 공개키로 메시지를 암호화하고 앨리스에게 보냅니다. 암호화된 메시지를 받은 앨리스는 자신의 비밀키로 메시지를 해독합니다. 공개키에서 비밀키를 만들 수 없으므로, 앨리스의 공개키로 암호화된 메시지를 읽을 수 있는 것은, 대응되는 비밀키를 가진 앨리스뿐. SSH는 이 구조를 이용하여 컴퓨터 간의 인증을 실시하고 있습니다.

공개키 암호화에는 RSA, DSA, ECDSA, EdDSA 등이 있고 각각 암호화 방식이 다릅니다.

◆ RSA
RSA는 1977년에 등장한 공개키 암호화 방식으로, 자릿수가 큰 반소수의 소인수분해가 매우 어렵다는 성질을 이용하고 있다고 Mody 씨는 설명합니다. 구체적으로는 자릿수가 큰 두 소수 'p'와 'q'의 곱인 'n'만 주어졌을 때, n을 p와 q로 소인수분해할 수 있는 것은 처음부터 p와 q라는 답을 알고 있는 사람 이외에는 있을 수 없다는 것. p와 q를 비밀 키의 요소로, n을 공개키의 요소로 이용하여 비밀 키에서 공개키를 이끌어낼 수는 있어도, 공개키로부터 비밀키를 이끌낼 수 없다는 암호가 완성되는 구조입니다.

◆ DSA
DSA는 이산대수 문제의 난해성에 근거한 암호. DSA의 중요한 포인트는 난수 'm'을 이용하여 비밀키 'k'와 함께 메시지에 서명하는 점이라는 것. m은 은닉해야 합니다.

◆ ECDSA와 EdDSA
ECDSA와 EdDSA는 DSA와 마찬가지로 이산대수 문제의 난해성을 이용한 암호화이지만, ECDSA와 EdDSA는 타원곡선 암호와 에드워즈 곡선을 이용하여 공개키의 크기를 줄일 수 있다고 합니다.

Mody 씨는 각각의 암호 방식에 대해서는 아래의 평가 기준으로 'SSH 공개키 암호화에 적합한 지 여부'를 평가하고 있습니다.

· 구현 : 기술자가 취급가능한 라이브러리가 풍부한 지 여부
· 호환성 : SSH 클라이언트가 암호화를 지원하고 있는가
· 성능 : 키 생성에 얼마나 시간이 걸리나
· 보안 : 공개키로 비밀키를 생성할 수 있는가

RSA는 오랜 역사를 가지고 있기 때문에 JavaScript나 Python, Go 등의 주요 프로그래밍 언어로 라이브러리에 포함되어 있습니다. OpenSSH의 호환성은, 해시 함수 SHA-1을 이용한 키 및 공개키의 키 길이가 2048bit 미만인 키를 사용할 수 없지만, 최신 OpenSSL에서 생성할 수 있는 기본 키 길이가 2048bit라는 것을 생각하면 호환성은 높은 편이라고 말할 수 있을 것입니다. 그러나 컴퓨터의 계산 성능 향상과 함께 보안 확보에 필요한 키 길이도 증가하고 있어, 성능면에서는 평가되지 않고 있습니다. 또한 특정 정수를 소인수분해하는 알고리즘도 존재한다고 합니다.

DSA는 1994년에 등장한 암호화 방식으로, RSA와 같이 라이브러리는 충실하다고 합니다. 그러나 DSA의 보안은 완벽하지 않습니다. DSA는 난수 m을 키 생성에서의 일회용으로 사용하는 nonce값으로 사용하지만, DSA는 이 m을 은닉할 필요가 있어서, 일회용이어야 할 nonce값이 특성상 키와 유사해진다고 합니다. 한편, 완전한 난수를 생성하는 것은 어렵고, 프로그램의 구현 실수로 일정한 법칙의 값을 m로 사용해버릴 수도 있어서, m의 분석을 통해 암호화가 돌파되어 버리는 일도 있습니다. 이 때문에 DSA는 OpenSSH 7.0에서 기본적으로 비활성화되어 있습니다

ECDSA는 DSA보다 키 길이는 작지만 보안이 향상된 것은 아니라고 합니다. ECDSA 대해 EdDSA는 nonce값을 난수 생성하는 것이 아니라, 충돌에 대한 강도를 높이기 위한 해시로 생성한다고 합니다. EdDSA는 비교적 새로운 암호화이기 때문에 RSA와 DSA에 비해 구현과 호환성면에서는 떨어지지만, 높은 성능과 보안을 가지고 있으며, 공개키 기반 산업은 점차 EdDSA로 이행하고 있다고 Mody 씨는 지적합니다.

Mody 씨는 마지막으로, 구현과 호환성을 중시하는 경우에는 공개키의 키 길이가 2048bit 또는 4096bit의 RSA를, 성능과 보안을 중시하는 경우에는 EdDSA를 권장하고 있습니다. DSA나 ECDSA는 사용하지 않도록 권고하고 있습니다.