X3DH Key Agreement Protocol

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

private_key = X25519PrivateKey.generate()
# another private key from other person
peer_public_key = X25519PrivateKey.generate().public_key()
shared_key = private_key.exchange(peer_public_key)

Sig(PK, M)

바이트 시퀀스 M에 대한 XEdDSA 서명을 의미하며, 공개키 PK로 인증된 상태이다.

구체적으로 M을 서명하면서, PK의 개인키를 이용한 것이다.

KDF(KM)

HKDF 알고리즘으로부터 도출되는 32바이트 결과물을 의미한다.

HKDF input은 F || KM인데, F는 0xFF로 이루어진 바이트 시퀀스이다.
curve가 X25519일 때에는 32 바이트, X448일 때에는 57 바이트의 0xFF를 이용한다.
F는 XEdDSA에서 cryptographic domain separation을 위해 이용된다.
HKDF salt는 hash output length 와 동일한 길이의 0x00 바이트 시퀀스
HKDF info는 info parmeter

시뮬레이션

비동기성, 오프라인일 때에도 메시지 전송, 키교환이 가능.

Alice : Bob에게 암호화된 데이터를 전송하기를 원하는데, 추후 쌍방향에 대화에 이용될 shared secret key를 확실히 하기를 원함.
Bob : Alice와 같은 사람들이 shared key를 establish하기를 허락하기를 원함. 그러나 Alice가 이것을 시도할 때에 Offline 상태일 수 있음. 따라서 서버와의 관계가 필요함.
Server : Alice → bob으로 전해지는 메시지를 저장하여 Bob이 나중에 받게할 수 있음. Bob으로부터 데이터를 받아서 Alice와 같은 사람들에게 전달해줄 수 있음.

키 종류

Bob의 키 배포

전부 다 public key임.

IK(B)
SPK(B)
Sig(IKB, Encode(SPKB)) : prekey signature
(OPK(B)1, OPK(B)2, OPKB(3, . . . ) : one set of Bob's one-time prekeys

identity key는 서버에 한 번만 보냄.

one-time prekeys는 종종 보냄. 서버에 남은 것이 다 떨어졌다거나 할 때, 서버가 요청함.

Signed Prekey와 prekey signature은 특정 기간마다 한 번씩 업로드함(일주일이나 한 달에 한 번)

새로운 키를 업로드한 이후에는 이전 키에 대응하는 private key들을 보관하고 있다가, Bob이 그것을 이용하는 메시지를 받을 때에 삭제된다) ..?

Initial message 전송

Alice는 Bob의 "key bundle"을 가져오는데, 그 내용은 아래와 같음

IK(b)
SPK(b)
Sig(IKB, Encode(SPKB))
(Optionally ... )OPK(B)1

서버는 OPK(B) 중에서 하나를 제공하는데(존재하는 경우에), 제공하고 나서는 삭제한다.

Bob의 OPK가 모두 삭제되면, 번들에는 OPK가 존재하지 않는다.

Alice는 prekey 서명을 확인하고, 인증이 실패하면 프로토콜을 파기한다.

번들에 OPK(B)가 없는 경우에는,

번들에 OPK(B)가 있는 경우에는,

결과적으로 아래와 같다.

DH1, DH2는 상호 인증을 제공하고, DH3, DH4는 추가적인 안전을 제공한다.

SK를 계산한 이후에, Alice는 EK(A)와 DH값들을 삭제한다.

이후에는 AD라는 "associated data" 바이트 시퀀스를 계산한다.

AD = Encode(IK(a)) ||  Encode(IK(b))
# AD 에 usernames, certificates 등 identifying information을 추가할 수 있음.

Alice는 드디어! Bob에게 initial message를 보내는데,

IK(A) : Alice Identify Key
EK(A) : Alice Ephemeral Key
Identifiers : Bob의 prekey 중에서 Alice가 사용한 것이 어떤 것인지
Initial Ciphertext : AD를 data로 하고, (SK 그자체 혹은 SK로부터 도출된 PRF 키)를 암호화 키로 사용하여 AEAD 암호화 방식으로 암호화한 것.

이 initial message는 2가지 역할을 하는데, post-X3DH protocol의 first message 역할, Alice의 X3DH initial message의 일부분의 역할을 한다.

이후에는 Alice는 (SK 혹은 SK로부터 도출된 키)를 post-X3DH 프로토콜 범위 내에서 Bob과의 소통을 위해 계속 사용할 것이다.

Security Considerations

4.1. 인증

IK(A)와 IK(B)는 별개의 경로(QR 코드 확인, 숫자 확인 등)로 인증되어야 한다.

이 인증이 수행되지 않으면, 자신이 누구와 통신하는지에 대한 암호학적 보호를 받을 수 없다.

4.2. 프로토콜 replay

Alice의 inital message가 OPK(B)를 사용하지 않을 경우에, Bob에게 replay되고 Bob이 accept할 위험이 있다.

...(자세한건 다음에)

Hunjison

비전공자 출신 화이트햇 해커

X3DH Key Agreement Protocol

Crypto

기본 요소

정의

DH(PK1, PK2)