← Double Ratchet
Bölüm 5 / 10

5. Sparse Post-Quantum Ratchet

Bu bölüm, Sparse Continuous Key Agreement (SCKA) protokolü üzerine kurulmuş güvenli bir mesajlaşma protokolü olan Sparse Post-Quantum Ratchet protokolünü açıklamaktadır.

Yukarıda açıklanan Double Ratchet protokolü, kriptografik açıdan anlamlı kuantum bilgisayarlar kullanan saldırılara karşı güvenlik sağlamaz. Bant genişliği kısıtı olmayan uygulamalar için [7], yukarıda sunulan Double Ratchet protokolünün Continuous Key Agreement (CKA) adı verilen bir protokolü kullanacak şekilde genelleştirilebileceğini göstermektedir. Gayriresmî olarak CKA, Alice ile Bob arasında ileri geri mesajlar gönderilen ve her mesajla birlikte yeni bir paylaşılan anahtarın üretildiği bir protokoldür. Örneğin, Bölüm 3'teki Double Ratchet protokolü, tarafların her mesajla birlikte yeni geçici anahtarlar gönderdiği bir CKA'ya karşılık gelir; herhangi bir turdan sonraki çıktı anahtarı da önceki iki turda değiş tokuş edilen geçici anahtarların Diffie-Hellman anahtar anlaşmasıdır (ve bu değer hem Alice hem Bob tarafından verimli biçimde hesaplanabilir). Dahası, ML-KEM gibi kuantum sonrası güvenli herhangi bir Anahtar Kapsülleme Mekanizması (KEM) kullanılarak kuantum sonrası güvenli CKA protokolleri kurmak kolaydır; dolayısıyla Double Ratchet protokolünün kuantum sonrası güvenli bir varyantı da elde edilebilir. Bu yaklaşım zarif olsa da, mevcut kuantum sonrası KEM'ler, eliptik eğri anahtarlarından kat kat büyük mesajların değişimini gerektirir; bu da bant genişliği kısıtlı uygulamalarda pratik olmayabilir.

Bu sorunu ele almak ve bant genişliği kısıtlı ortamlarda sağlam, kuantum güvenli ratchet protokollerini mümkün kılmak için [8] tarafından Sparse Continuous Key Agreement (SCKA) protokolleri sunulmuştur. CKA protokollerinde olduğu gibi SCKA protokolleri de iki tarafın düzenli olarak paylaşılan sırlar üretmesini sağlar. Ancak burada her mesajla birlikte yeni paylaşılan anahtar üretilmesi koşulu bırakılır; ayrıca tarafların mesajlaşmada sırayla ilerlemesi zorunluluğundan da vazgeçilir. Böylece artık her uygulama mesajında tam bir kuantum sonrası anahtar değişim mesajı taşımaya gerek kalmadığından, bant genişliği sınırlı ortamlarda doğal ve kuantum sonrası güvenli SCKA protokolleri tasarlanabilir [8]. SCKA'nın sözdizimini ve sezgisel güvenliğini Bölüm 5.1'de açıklıyoruz; uygun bir kuantum sonrası SCKA tasarımının (ML-KEM Braid protokolü olarak adlandırılır) ayrıntıları ise eşlik eden başka bir belgede [9] bırakılmıştır.

Bölüm 5'in geri kalanında, herhangi bir SCKA protokolünden genel biçimde türetilen güvenli bir mesajlaşma protokolü olan Sparse Post-Quantum Ratchet'ın ayrıntılarını sunuyoruz. Sezgisel olarak, genelleştirilmiş protokol yalnızca SCKA yeni bir sır ürettiğinde yeni gönderici ve alıcı zincirleri oluşturacaktır. Buradaki incelik şudur: ardışık SCKA sır üretimleri arasındaki sürede her iki taraf da uygulama mesajları değiş tokuş edebileceği için, bu yeni sırla hem bir gönderici zinciri hem de bir alıcı zinciri oluşturulmalıdır. Ayrıca, kuantum sonrası güvenlik ve iyi bant genişliği kullanımı yanında, özgün Double Ratchet protokolüne benzer güvenlik özelliklerini de devralacaktır. Sezgisel olarak, SCKA protokolü olarak ML-KEM Braid kullanıldığında bu Sparse Post-Quantum Ratchet kuantum sonrası güvenlik kazanır; ancak ihlal sonrası güvenliğe ulaşmak için daha fazla mesaj değiş tokuş edilmesi gerekir.

5.1 Sparse Continuous Key Agreement

SCKA, [8]'de biçimsel olarak tanımlanmıştır ve [9]'da üst düzey bir açıklaması bulunmaktadır.

Bir SCKA protokolü, paylaşılan sırlar üreten iki işlev sağlar. Bu paylaşılan sırlar sıralı "epoch tanımlayıcıları" ile tanımlanır ve SCKA işlevleri, bu sırların doğru kullanılabilmesi için gerekli epoch bilgisini üretir:

  • SCKAInitAlice(sk) -> state: Başlangıç paylaşılan sırrı sk kullanılarak Alice'in durumunu başlatır.
  • SCKAInitBob(sk) -> state: Başlangıç paylaşılan sırrı sk kullanılarak Bob'un durumunu başlatır.
  • SCKASend(state) -> (msg, sending_epoch, output_key)
    • msg: SCKA protokolü için opak mesaj verisi
    • sending_epoch: msg işlendiğinde alıcının bileceği garanti edilen en güncel epoch
    • output_key: Ya None ya da key'in epoch'unu belirten key_epoch ile birlikte (key_epoch, key)
  • SCKAReceive(state, msg) -> (receiving_epoch, output_key):
    • msg: SCKA protokolü için opak mesaj verisi
    • receiving_epoch: Gönderenin msg'yi üretirken sending_epoch olarak çıkardığı epoch
    • output_key: Ya None ya da key'in epoch'unu belirten key_epoch ile birlikte (key_epoch, key)

Sparse Post-Quantum Ratchet, Eliptik Eğri Double Ratchet'ın SCKA ortamına doğal bir uyarlamasıdır. Her uygulama mesajıyla birlikte Eliptik Eğri açık anahtarları göndermek yerine, SCKASend() çağrısının ürettiği mesajı göndeririz. SCKASend() ya da SCKAReceive() ne zaman boş olmayan bir key döndürürse, bunu kök anahtarımızla karıştırarak yeni bir kök anahtarı ve bu yeni epoch için yeni bir gönderici KDF zinciri ile alıcı KDF zinciri oluştururuz.

Bir mesaj şifrelenirken, kullanılacak doğru gönderme zincirini bulmak için SCKASend() tarafından döndürülen sending_epoch değeri kullanılır ve mesaj anahtarı bu KDF zincirinden hesaplanır. SCKA protokolü, sending_epoch değerinin gönderenin bildiği ve msg işlendiğinde alıcının da bileceği en güncel epoch olacağını garanti eder.

Benzer biçimde, bir mesaj alınırken, gereken alıcı zincirini bulmak için SCKAReceive() tarafından döndürülen receiving_epoch değeri kullanılır ve mesaj anahtarı bu KDF zincirinden alınır ya da hesaplanır. SCKA protokolü, alıcı tarafın msg işlendiğinde receiving_epoch için sırrı bileceğini ve msg'yi üreten SCKASend() çağrısının sending_epoch == receiving_epoch olacak şekilde sending_epoch çıktısını üretmiş olduğunu garanti eder.

5.2. Dış işlevler

  • KDF_SCKA_INIT(sk): 32 baytlık bir sır sk ile anahtarlanmış bir KDF'nin, kullanılan protokolü ve parametrelerini belirten benzersiz bir sabite uygulanmasının sonucu olarak bir üçlü (32 baytlık kök anahtarı, 32 baytlık gönderici zincir anahtarı, 32 baytlık alıcı zincir anahtarı) döndürür.

  • KDF_SCKA_RK(rk, scka_output): 32 baytlık bir kök anahtarı rk ile anahtarlanmış bir KDF'nin, SCKA protokolünün ürettiği bir anahtara uygulanmasının sonucu olarak bir üçlü (32 baytlık kök anahtarı, 32 baytlık gönderici zincir anahtarı, 32 baytlık alıcı zincir anahtarı) döndürür.

  • KDF_SCKA_CK(ck, ctr): 32 baytlık bir zincir anahtarı ck ile anahtarlanmış bir KDF'nin, ctr ile kullanılan protokolü ve parametrelerini belirten benzersiz bir sabitin birleşimine uygulanmasının sonucu olarak bir çift (32 baytlık zincir anahtarı, 32 baytlık mesaj anahtarı) döndürür.

  • KDFChain(ck): CK = ck zincir anahtarı ve N = 0 sayacı ile bir KDF Zinciri başlatır.

5.3. Durum değişkenleri

  • RK: 32 baytlık bir kök anahtarı.
  • epoch: SCKA anahtarlarının en son dahil edildiği epoch.
  • kdfchains: epoch ile indekslenen ve iki KDF zinciri içeren bir tablo: send ve receive.
  • MKSKIPPED: epoch'tan, mesaj numaralarından atlanmış mesaj anahtarlarına giden eşlemeleri tutan bir yapı.
  • direction: Katılımcının protokoldeki rolünü gösteren bir bayrak; A2B veya B2A değerlerinden biridir.
  • scka_state: Bir SCKA protokolünün opak durumu.

5.4. Başlatma

Başlatmadan önce her iki taraf da, 32 baytlık paylaşılan gizli anahtar SK üzerinde anlaşmak için bir anahtar anlaşma protokolü kullanmalıdır. Bu değer, Alice ve Bob'un başlangıç RK ve KDF zincirlerini doldurmak ve aynı zamanda SCKA durumunu başlatmak için kullanılacaktır.

function RatchetInitAliceSCKA(state, SK):
    state.scka_state = SCKAInitAlice(SK)
    state.direction = A2B
    state.RK, CKs, CKr = KDF_SCKA_INIT(SK)
    state.epoch = 0
    state.kdfchains = {}
    state.kdfchains[0] = {}
    state.MKSKIPPED = {}
    state.kdfchains[0].send = KDFChain(CKs)
    state.kdfchains[0].receive = KDFChain(CKr)

function RatchetInitBobSCKA(state, SK):
    state.scka_state = SCKAInitBob(SK)
    state.direction = B2A
    state.RK, CKr, CKs = KDF_SCKA_INIT(SK)  # CKs ve CKr sırasının değiştiğine dikkat edin
    state.epoch = 0
    state.kdfchains = {}
    state.kdfchains[0] = {}
    state.MKSKIPPED = {}
    state.kdfchains[0].send = KDFChain(CKs)
    state.kdfchains[0].receive = KDFChain(CKr)

5.5. Mesajların şifrelenmesi

SCKA, bir mesaj gönderilirken yeni bir paylaşılan sır üretebileceğinden, protokolün giden mesajı şifrelemek için kullanılan mesaj anahtarı hesaplanırken açık ratchet'i ilerletmesi gerekebilir. Bunun dışında, Sparse Post-Quantum Ratchet şifrelemesi Double Ratchet şifrelemesine benzerdir.

function SCKARatchetSendKey(state):
    msg, sending_epoch, output_key = SCKASend(state.scka_state)
    if output_key is not None:
        key_epoch, key = output_key
        # Yeni epoch'a ilerle
        assert state.epoch + 1 == key_epoch
        state.RK, CKs, CKr = KDF_SCKA_RK(state.RK, key)
        if state.direction == B2A:
            (CKs, CKr) = (CKr, CKs)

        # Yeni zincirleri oluştur
        state.kdfchains[key_epoch] = {
            'send': KDFChain(CKs),
            'receive': KDFChain(CKr)
        }
        state.epoch = key_epoch
        ClearOldEpochs(state, sending_epoch)

    # Mesaj anahtarı türetimine devam et
    state.kdfchains[sending_epoch - 1].send = None
    state.kdfchains[sending_epoch].send.N = state.kdfchains[sending_epoch].send.N + 1
    state.kdfchains[sending_epoch].send.CK, mk =
        KDF_SCKA_CK(
            state.kdfchains[sending_epoch].send.CK,
            state.kdfchains[sending_epoch].send.N)
    return msg, state.kdfchains[sending_epoch].send.N, mk

function SCKARatchetEncrypt(state, plaintext, AD):
    msg, n, mk = SCKARatchetSendKey(state)
    header = SCKA_HEADER(msg, n)
    return header, ENCRYPT(mk, plaintext, CONCAT(AD, header))

function ClearOldEpochs(state, sending_epoch):
    state.kdfchains[sending_epoch - 2] = None
    state.MKSKIPPED[sending_epoch - 2] = None

5.6. Mesajların şifresinin çözülmesi

Bir mesaj alınırken, Double Ratchet içindeki DHRatchet() işlevinin yerini SCKA protokolü alır. SCKA yeni bir paylaşılan anahtar ürettiğinde, bu anahtar kök anahtarı ilerletmek ve yeni epoch için gönderici ile alıcı KDF zincirleri oluşturmak amacıyla kullanılır.

function SCKARatchetReceiveKey(state, header):
    receiving_epoch, output_key = SCKAReceive(state.scka_state, header.msg)
    if output_key is not None:
        key_epoch, key = output_key
        assert state.epoch + 1 == key_epoch
        state.RK, CKs, CKr = KDF_SCKA_RK(state.RK, key)
        if state.direction == B2A:
            (CKs, CKr) = (CKr, CKs)

        # Yeni zincirleri oluştur
        state.kdfchains[key_epoch] = {
            'send': KDFChain(CKs),
            'receive': KDFChain(CKr)
        }
        state.epoch = key_epoch

    # Mesaj anahtarı türetimine devam et
    mk = TrySkippedMessageKeys(state, receiving_epoch, header.n)
    if mk is not None:
        return mk
    SkipMessageKeys(state, receiving_epoch, header.n)
    state.kdfchains[receiving_epoch].receive.N =
        state.kdfchains[receiving_epoch].receive.N + 1
    state.kdfchains[receiving_epoch].receive.CK, mk =
        KDF_SCKA_CK(
            state.kdfchains[receiving_epoch].receive.CK,
            state.kdfchains[receiving_epoch].receive.N)
    return mk

function SCKARatchetDecrypt(state, header, ciphertext, AD):
    mk = SCKARatchetReceiveKey(state, header)
    return DECRYPT(mk, ciphertext, CONCAT(AD, header))

function TrySkippedMessageKeys(state, key_epoch, n):
    if key_epoch in state.MKSKIPPED and n in state.MKSKIPPED[key_epoch]:
        mk = state.MKSKIPPED[key_epoch][n]
        remove state.MKSKIPPED[key_epoch][n]
        if len(state.MKSKIPPED[key_epoch]) == 0:
            remove state.MKSKIPPED[key_epoch]
        return mk
    else:
        return None

function SkipMessageKeys(state, epoch, until):
    if state.kdfchains[epoch].receive is None:
        return
    if state.kdfchains[epoch].receive.N + MAX_SKIP < until:
        signal Error
    while state.kdfchains[epoch].receive.N < until:
        state.kdfchains[epoch].receive.N =
            state.kdfchains[epoch].receive.N + 1
        state.kdfchains[epoch].receive.CK, mk =
            KDF_SCKA_CK(
                state.kdfchains[epoch].receive.CK,
                state.kdfchains[epoch].receive.N)
        if epoch not in state.MKSKIPPED:
            state.MKSKIPPED[epoch] = {}
        state.MKSKIPPED[epoch][state.kdfchains[epoch].receive.N] = mk

5.7. Geçmiş epoch durumunun temizlenmesi

Sparse Post-Quantum Ratchet, herhangi bir anda yalnızca iki epoch'a ait KDF Zincirlerini sakladığından emin olmak için ClearOldEpochs(state, epoch) işlevini çağırarak eski KDF Zinciri durumunu temizler. Bu işlevin, eski epoch'lar için MKSKIPPED içinde saklanan anahtarları da temizlediğine dikkat edin; bu da alıcının eski ve sırası bozuk mesajların şifresini çözme yeteneğini sınırlar. Bu tasarım, çok sayıda mesajın düşebildiği (örneğin yazıyor göstergeleri gibi geçici mesajlar) ancak mesajların nadiren çok geç ve sırası bozuk teslim edildiği dağıtımlar için amaçlanmıştır.

Gerçekleyiciler, Double Ratchet'ta yapıldığı gibi önceki epoch'ta gönderilen mesaj sayısını ileterek geçmiş KDF Zincirlerinin durumunu da temizleyebilir. Özellikle, durumlarına şu değişkenleri eklerler:

  • sending_epoch: Mesaj göndermek için şu anda kullanılan epoch.
  • receiving_epoch: Mesaj almak için şu anda kullanılan en güncel epoch.
  • PN: Son gönderme zincirinde gönderilen mesaj sayısı; gönderilen her mesajın başlığına eklenir.

Ardından şu işlevleri uygularlar:

function SealPrevSendingChain(state):
    state.PN = state.kdfchains[state.sending_epoch].send.N
    state.kdfchains[state.sending_epoch].send = None

function SealPrevReceivingChain(state, PN):
    SkipMessageKeys(state, state.receiving_epoch, PN)
    state.kdfchains[state.receiving_epoch].receive = None

Bu işlevler daha sonra bir epoch ilerlediğinde eski durumu temizlemek için kullanılabilir. Mesaj gönderme şu şekilde değiştirilir:

function SCKARatchetSendKey(state):
    msg, sending_epoch, key_epoch, key = SCKASend(state.scka_state)
    if sending_epoch > state.sending_epoch:
        assert sending_epoch == state.sending_epoch + 1
        SealPrevSendingChain(state)
        state.sending_epoch = sending_epoch
    # İşlevin geri kalanı değişmeden kalır
    # ...

function SCKARatchetEncrypt(state, plaintext, AD):
    msg, PN, n, mk = SCKARatchetSendKey(state)
    header = SCKA_HEADER(msg, PN, n)
    return header, ENCRYPT(mk, plaintext, CONCAT(AD, header))

Mesaj alımı da benzer şekilde değiştirilir:

function SCKARatchetReceiveKey(state, header):
    receiving_epoch, key_epoch, key = SCKAReceive(state.scka_state, header.msg)
    if receiving_epoch > state.receiving_epoch:
        assert receiving_epoch == state.receiving_epoch + 1
        SealPrevReceivingChain(state, header.PN)
        state.receiving_epoch = receiving_epoch
    # İşlevin geri kalanı değişmeden kalır.

Eğer bu yaklaşım ClearOldEpochs(state, epoch) yerine kullanılırsa, gerçekleyiciler MKSKIPPED veri yapısından eski anahtarları kaldırmak için başka bir yöntem bulmalıdır; aksi halde yapı sınırsız büyüyebilir.