Skip to content

Constant-time programming

Control flow'un, memory address'lerinin ve instruction latency'lerinin asla secret data'ya bağlı olmamasını sağlayarak secret'a bağlı timing'i ortadan kaldır.

Mechanism

Note

Bir timing side channel, execution time bir secret ile korele olduğunda sızdırır; bu yüzden constant-time disiplini secret data üzerinde üç şeyi yasaklar: secret'a bağlı conditional branch'ler (predictor/I-cache hangi yolun çalıştığını açığa çıkarır), secret'a bağlı memory address'ler (table index'leri data cache üzerinden sızar) ve secret'lar üzerinde variable-latency instruction'lar (integer division, değişken-mesafeli shift'ler, bazı multiply'lar). Bunun yerine, bir conditional'ın her iki kolu da koşulsuz hesaplanır ve secret'tan türetilen bir bitmask ile birleştirilir; table lookup'ları ise tüm entry'lerin masked taramasıyla değiştirilir.

Disiplin yalnızca kaynakta değil, machine-code seviyesinde de tutmalıdır, çünkü optimize eden compiler'lar legal olarak bir branch'i yeniden ekleyebilir.

Walkthrough

Kanonik branchless select ve full-width mask türetimi:

/* mask = 0xFFFFFFFF if select-a, 0x0 if select-b (computed branchlessly) */
uint32_t ct_select(uint32_t mask, uint32_t a, uint32_t b) {
    return (a & mask) | (b & ~mask);
}
/* full-width mask from a 1/0 condition, no branch: */
uint32_t mask = (uint32_t)0 - (uint32_t)cond;   /* {0,1} -> {0x0, 0xFFFFFFFF} */

BearSSL'in kodlama kuralları: unsigned type'lar kullan (tanımlı wraparound, UB yok), full-width control word'leri (0xFFFFFFFF / 0) lehine C boolean'larından kaçın ve sonuçları control flag'leriyle gate'le (constant-time copy için br_ccopy()).

Doğrulama araçları:

  • dudect — istatistiksel leakage detector'ı; timing üzerinde Welch'in t-test'ini çalıştırır, |t| > ~10 olduğunda leakage'ı flag'ler (kod modeli gerektirmez).
  • ctgrind — Valgrind/Memcheck patch'i: secret'ları "uninitialized" olarak işaretle; onlardan türetilen herhangi bir branch ya da address bir Memcheck hatasını tetikler.
  • ct-verif — bir fonksiyonun trace'inin secret'lardan bağımsız olduğunu formel olarak ispatlar.

Warning

Compiler seni yenebilir: BearSSL, yüksek optimization'da GCC'nin bir unsigned comparison'ı implemente etmek için kullanılan subtraction'ları kaldırdığını belgeliyor. Emit edilen assembly'yi incele — ama bu sana yalnızca bir compiler sürümünün ne yaptığını söyler.

Detection

dudect/ctgrind'i CI'da çalıştır. Hardware seviyesindeki leak'ler için (aşağıda) kaynak seviyesi araçlar kördür; detection, microarchitectural test ya da vendor advisory'leri gerektirir.

Mitigation

Garanti, hardware'in data-oblivious olduğunu varsayar. Data Memory-dependent Prefetcher (DMP) bunu bozar: GoFetch (USENIX Security 2024), Apple M serisi DMP'lerin pointer'a benzeyen in-memory value'ları dereference ederek secret'a bağlı erişimleri "victim adına" ürettiğini gösterdi — M1'de constant-time OpenSSL DH, Go RSA, Kyber ve Dilithium'dan uçtan uca anahtar çıkardı (GoFetch M2 ve M3'te de benzer exploit edilebilir DMP davranışı ölçtü, ancak bu çiplerde uçtan uca saldırı test etmedi). Mitigation'lar: Apple DIT / Intel DOIT data-independent-timing bit'leri — ancak DIT DMP'yi yalnızca M3'te (DOIT ise Raptor Lake'te) etkin biçimde kapatır; M1/M2'de kullanılabilir donanımsal düzeltme yoktur, yalnızca yazılım tarafı input/ciphertext blinding ve isolation mümkündür (GoFetch yazarlarının önerdiği blinding). İlgili: prefetch-side-channel KASLR break.

References