Cara Memecahkan Kunci DKIM 512-bit dengan Biaya Cloud di Bawah US$8

 (dmarcchecker.app)
3 poin oleh GN⁺ 2025-01-09 | 1 komentar | Bagikan ke WhatsApp
  • Dalam survei terhadap 1 juta situs web teratas, ditemukan lebih dari 1.700 kunci publik DKIM di bawah 1.024-bit, dan eksperimen ini memeriksa apakah kunci DKIM RSA 512-bit milik redfin.com benar-benar dapat disalahgunakan
  • Setelah men-decode tag p pada record DKIM untuk mendapatkan modulus RSA n dan eksponen publik e=65537, modulus tersebut difaktorkan dengan CADO-NFS
  • Pada server Hetzner dengan 8 dedicated vCPU, RAM 32GB, n berhasil dipecah menjadi dua bilangan prima p dan q dalam sekitar 86 jam, lalu kunci privat RSA direkonstruksi berdasarkan hasil itu
  • Saat email dari security@redfin.com ditandatangani dengan kunci privat yang direkonstruksi, Gmail dan Outlook menolaknya, tetapi Yahoo Mail, Mailfence, Tuta mengembalikan dkim=pass
  • Pada kebijakan DMARC redfin.com p=reject; pct=100, DKIM yang lolos berujung pada DMARC yang lolos, sehingga penyedia email harus menolak tanda tangan DKIM RSA di bawah 1.024-bit

Masalah Kunci DKIM 512-bit yang Masih Ada

  • Dalam survei record SPF, DKIM, DMARC pada 1 juta situs web teratas, ditemukan lebih dari 1.700 kunci publik DKIM dengan panjang di bawah 1.024-bit
  • Kunci RSA di bawah 1.024-bit dianggap tidak aman, dan dalam DKIM penggunaannya sudah direkomendasikan untuk ditinggalkan sejak RFC 8301 pada 2018
  • Target eksperimen adalah kunci publik RSA 512-bit yang ditemukan di key1._domainkey.redfin.com
  • Tujuannya adalah memastikan apakah, hanya dengan kunci publik, kunci privat dapat dipulihkan dan dipakai untuk menandatangani email seolah-olah berasal dari domain asli
  • Juga diverifikasi apakah penyedia email utama seperti Gmail, Outlook.com, dan Yahoo Mail akan meloloskan tanda tangan DKIM yang dibuat dengan kunci pendek

Mengekstrak Komponen RSA dari Kunci Publik DKIM

  • Tag p pada record DKIM berisi kunci publik yang dienkode dalam format ASN.1 DER, lalu dienkode ulang dengan Base64
  • Kunci publik dibaca dengan Crypto.PublicKey.RSA.import_key di Python untuk mengekstrak komponen RSA
    • Modulus n: 10709580243955269690347257968368575486652256021267387585731784527165077094358215924099792804326677548390607229176966588251215467367272433485332943072098119
    • Eksponen publik e: 65537

Memfaktorkan Modulus dengan CADO-NFS

  • Untuk membuat kunci privat RSA, modulus n harus diuraikan menjadi hasil perkalian dua bilangan prima p dan q
  • Untuk faktorisasi, digunakan CADO-NFS
    • CADO-NFS adalah implementasi algoritma Number Field Sieve(NFS) yang digunakan untuk faktorisasi bilangan bulat besar
  • Agar komputer lokal tidak tersita selama berhari-hari, sebuah server cloud Hetzner disewa
    • Spesifikasi server: 8 dedicated vCPU, AMD EPYC 7003 series, RAM 32GB
    • OS: Ubuntu
    • Swap 32GB ditambahkan untuk memastikan memori yang cukup bagi pekerjaan ini
  • Modulus n dimasukkan ke cado-nfs.py untuk menjalankan faktorisasi
  • Keseluruhan pekerjaan memakan waktu sekitar 86 jam pada server 8-vCPU, dan n terurai menjadi dua bilangan prima berikut
    • p = 97850895333751392558280999318309697780438485965134147739065017624372104720767
    • q = 109447953515671602102748820944693252789237215829169932130613751100276125683257
  • Waktu dapat dipersingkat dengan server yang lebih kuat atau eksekusi terdistribusi di beberapa sistem, dan CADO-NFS menyederhanakan pekerjaan terdistribusi

Rekonstruksi Kunci Privat RSA

  • Setelah p, q, dan e diperoleh, kunci privat RSA dibuat dengan Python dan PyCryptodome
  • Perhitungan menggunakan nilai dan prosedur berikut
    • n = p * q
    • phi = (p-1) * (q-1)
    • d = inverse(e, phi)
    • RSA.construct((n, e, d, p, q))
  • Hasilnya adalah kunci privat RSA dalam format PEM, yang diintegrasikan ke konfigurasi OpenDKIM dan digunakan untuk menandatangani email uji

Hasil Verifikasi DKIM per Penyedia Email

  • Kunci privat yang direkonstruksi dimasukkan ke OpenDKIM, lalu email uji dengan alamat FROM security@redfin.com dikirim ke beberapa layanan hosting email
  • Sebagian besar penyedia menilai kunci 512-bit tidak aman dan menolak tanda tangan DKIM, tetapi tiga penyedia mengembalikan dkim=pass
  • Hasil per penyedia adalah sebagai berikut
    • Gmail: FAIL
    • Outlook: FAIL
    • Yahoo Mail: PASS
    • Zoho: FAIL
    • Fastmail: FAIL
    • Proton Mail: FAIL
    • Mailfence: PASS
    • Tuta: PASS
    • GMX: FAIL
    • OnMail: FAIL
  • redfin.com memiliki record DMARC valid berbentuk v=DMARC1;p=reject;pct=100;...
  • Keberhasilan verifikasi DKIM untuk redfin.com berujung pada keberhasilan verifikasi DMARC, dan juga memenuhi persyaratan BIMI

Biaya dan Langkah Operasional

  • 30 tahun lalu, memecahkan kunci publik RSA 512-bit adalah pekerjaan setingkat superkomputer, tetapi kini dapat dilakukan di server cloud dengan biaya di bawah US$8
  • Jika memiliki komputer rumahan yang kuat dengan 16 core atau lebih, pekerjaan ini mungkin bisa dilakukan lebih cepat dan lebih murah
  • Tidak ada alasan untuk mempertahankan kunci DKIM 512-bit atau 768-bit, dan penyedia email harus otomatis menolak tanda tangan DKIM yang dibuat dengan kunci RSA di bawah 1.024-bit
  • Hasil eksperimen dan rekomendasi telah disampaikan kepada Yahoo, Mailfence, dan Tuta
  • Pemilik domain harus memeriksa record DKIM lama dalam pengaturan DNS
    • Tag p pada record DKIM dapat diperiksa secara sederhana dengan menghitung jumlah karakter Base64
    • Kunci publik RSA 1.024-bit memiliki minimal 216 karakter dalam Base64

Bacaan terkait

1 komentar

 
GN⁺ 2025-01-09
Komentar Hacker News

  • Bahkan 14 tahun lalu, kunci DKIM RSA 512-bit sudah mungkin dipecahkan: https://blog.jgc.org/2010/06/facebooks-dkim-rsa-key-should-b...

    • Selama beberapa waktu, penggunaan kunci DKIM yang lemah secara tidak resmi juga dianggap seperti fitur
      Logikanya, dengan kunci pendek, tanda tangan DKIM tidak bertahan lama sebagai bukti, sehingga lebih sulit membuktikan di kemudian hari apakah sebuah email benar-benar asli, dan ini bisa menjaga plausible deniability
      Tentu saja, bukan berarti kebanyakan perusahaan memakai kunci pendek karena alasan itu; maksudnya, ada suasana bahwa kunci pendek tidak sepenuhnya buruk
      Plausible deniability DKIM adalah topik yang secara pribadi sudah lama saya geluti [1]. Kunci pendek seperti ini jelas bukan solusi, tetapi saya melihatnya sebagai hasil dari cara berpikir yang membingungkan seputar DKIM dan suasana komunitas yang enggan menerima implikasi dari semua sistem tanda tangan email
      [1] https://blog.cryptographyengineering.com/2020/11/16/ok-googl...
    • Saya teringat kisah seseorang yang memecahkan kunci DKIM karena mengira itu adalah tantangan rekrutmen Google
      https://www.wired.com/2012/10/dkim-vulnerability-widespread/
    • Pada 1999, pemfaktoran RSA-155 dengan ratusan komputer menunjukkan bahwa kunci 512-bit bisa dipecahkan secara praktis, dan ada yang mengatakan sekarang bisa dilakukan dalam beberapa minggu dengan perangkat keras biasa
      Jadi kira-kira dalam 14 tahun, waktunya turun dari beberapa minggu menjadi 8 jam
    • Sebagai catatan, penulis komentar induk adalah CTO CloudFlare
    • Blog itu juga disebut di komentar http://www.wired.com/threatlevel/2012/10/dkim-vulnerability-...

  • Kalau ingin mencobanya untuk iseng, buat saja kunci DKIM 4096-bit
    Pemeriksa DKIM/SPF online, jika hanya melihat DNS, semuanya akan mengatakan normal, tetapi email uji akan gagal
    Mereka menampilkan penjelasan hebat seperti STATUS: Fail, DKIM: Pass, SPF: Pass
    Menggunakan kunci yang lebih besar dari 2048-bit pada entri DKIM memang diizinkan dan valid, tetapi verifier tidak wajib menangani kunci yang lebih besar dari 2048-bit
    Saya kehilangan sebagian rambut saat mempelajari ini secara langsung

    • Sebagai tambahan, untuk melihat kegagalan pemeriksaan, Anda harus menetapkan kebijakan DMARC yang ketat
      Menariknya, situs-situs mengatakan ketiga entri semuanya benar dan valid, tetapi email tetap diproses sebagai gagal
      Kemungkinan karena pemeriksaan record DNS dan verifikasi email ditangani oleh perangkat lunak yang berbeda
    • RFC terbaru, RFC8301, memiliki persyaratan terkait hal ini
      Verifier harus dapat memverifikasi tanda tangan dengan kunci dari 512-bit hingga 2048-bit, dan disebutkan bahwa mereka juga boleh memverifikasi kunci yang lebih besar
      Setahun lalu saya menulis tesis master tentang topik ini, dan saat ini semua penyedia email besar mendukung 4096-bit, sebagian bahkan mendukung hingga 16384-bit

  • Saya penasaran mengapa di seluruh kriptografi kita tidak secara umum memperbesar ukuran kunci secara signifikan
    Kalaupun bukan solusi, tampaknya bisa menjadi langkah untuk membeli waktu
    Performa komputasi meningkat cepat dan pembicaraan tentang komputer kuantum terus muncul, tetapi rasanya semua orang diam saja
    Memang kunci besar lebih mahal secara komputasi, tetapi sumber daya komputasi kita juga bertambah, jadi bukankah seharusnya dipakai untuk pertahanan juga, bukan hanya untuk serangan
    Bahkan hal sederhana seperti memaksa TLS 1.3 di sisi klien alih-alih TLS 1.2 membuat banyak hal rusak, termasuk situs HN

    • Tulisan lama tetapi masih relevan: https://www.schneier.com/blog/archives/2009/09/the_doghouse_...
      Angka-angka ini berkaitan dengan batas maksimum yang diizinkan termodinamika, bukan tingkat teknologi perangkat
      Kesimpulannya, memecahkan AES-256 atau RSA-4096 dengan brute force secara fisik tidak mungkin
    • Kita sudah melakukan itu
      Kunci 1024-bit sudah lebih dari 10 tahun dipensiunkan di berbagai sistem kriptografi
      Begitu adanya, kecuali satu pengecualian yang tertinggal; satu-satunya yang mengancam kunci 2048-bit adalah komputer kuantum, dan itu mengancam RSA itu sendiri
      Kemajuan tidak bersifat linear, jadi hanya karena 1024 melemah bukan berarti 2048 secara mekanis akan segera runtuh; 1024 pun hari ini tidak mudah diserang di dunia nyata
    • RSA-2048 belum dipecahkan, dan setelah itu kita bisa bersandar pada RSA-4096, yang sudah umum di sebagian besar penggunaan RSA
      DKIM adalah salah satu pengecualian
      Di sisi DKIM, kita menunggu Ed25519 diadopsi luas, dan itu akan menyelesaikan berbagai ketidaknyamanan
    • Karena untuk memaksa penggunaannya, pada akhirnya harus ada sesuatu yang dibuat rusak
      Biasanya rasa sakit itu langsung dialihkan kepada pengguna, bukan operator layanan, dengan harapan pengguna akan banyak mengeluh sehingga operator peduli
      Namun pengguna juga sangat mungkin pindah ke pesaing yang memastikan hal kecil seperti keamanan tidak menghalangi pendapatan
    • Bahkan 8 tahun lalu saat saya bekerja di industri email, DKIM 512-bit sangat jarang
      Pada dasarnya ini seperti bertanya, “mengapa kita tidak melakukan sesuatu yang sebenarnya sudah kita lakukan?”

  • Dengan CADO-NFS, ini ternyata cukup mudah dilakukan
    Beberapa minggu lalu, karena urusan pekerjaan, saya memfaktorkan kunci RSA DKIM 512-bit dengan komputer desktop, dan hanya butuh 28 jam
    Spesifiknya, itu adalah AMD Zen 5 9900X
    Sayangnya kunci 1024-bit masih sulit untuk upaya tingkat hobi, tetapi mungkin dapat dilakukan oleh proyek akademis sebesar proyek yang memfaktorkan kunci 768-bit pada 2010: https://eprint.iacr.org/2010/006.pdf

  • Kemarin saya menerima email dari Bank of America tentang masalah pengaturan akun
    Memang benar saya membuat akun baru, dan email itu juga mengetahui fakta tersebut, nama perusahaan, dan sebagainya
    Tidak ada tautan; hanya instruksi untuk menelepon nomor bisnis BofA, dan setelah saya memeriksa nomor itu di situs web BofA ternyata sama, jadi saya menelepon
    Namun tidak ada yang bisa memberi tahu mengapa saya menerima email itu atau apa masalah pada akun saya, dan petugas layanan pelanggan juga tidak bisa menemukan catatan pengiriman email tersebut
    Saya 100% yakin email ini berasal dari Bank of America
    Tidak ada unsur phishing, tidak ada tautan, dan tidak ada nomor telepon berbahaya
    SPF, DKIM, dan DMARC semuanya lulus di ARC-Authentication-Results milik Google, dan kunci DKIM-nya juga 2048-bit
    Ketika saya meminta Bank of America menyelidikinya, mereka mengatakan “mungkin itu pesan phishing” dan mengirim tautan tentang cara waspada terhadap phishing
    Kemungkinan besar ini hanya kesalahan sederhana: suatu sistem menjalankan pemeriksaan konsistensi terlalu dini saat pembuatan akun lalu menghasilkan email
    Namun karena mereka menyebutnya “phishing”, saya mengirim FedEx kepada CTO dengan seluruh materi terlampir
    Hanya ada dua kemungkinan: kunci DKIM mereka bocor sehingga mereka harus segera mengeluarkan peringatan publik, atau pegawai dan sistem IT yang tidak kompeten membuat saya dioper-oper dan membuang satu jam waktu saya
    Apa pun itu, saya menginginkan investigasi dan penyelesaian menyeluruh

  • Beberapa penyedia DNS sangat buruk sehingga hanya mengizinkan pengaturan hingga kunci sepanjang 1024-bit
    Contohnya wordpress.com

    • 1024-bit beberapa orde magnitudo lebih sulit dipecahkan daripada 512-bit
      Sebagai referensi, angka RSA terakhir yang berhasil dipecahkan adalah RSA-250, yaitu 829-bit, dan pada 2020 membutuhkan 2700 core-year [1]
      Sementara RSA-155, yaitu 512-bit, sudah difaktorkan pada 1999
      Itu belum termasuk kondisi berbahaya
      [1]: https://sympa.inria.fr/sympa/arc/cado-nfs/2020-02/msg00001.h...
    • NIST bahkan berencana melarang RSA 2048-bit sampai 2035
      Alasannya karena tidak memberikan tingkat keamanan yang memadai
    • RSA-1024 bisa dianggap kira-kira 8 juta kali lebih baik daripada RSA-512, jadi biaya komputasi saja untuk memecahkannya mungkin sekitar 64 juta dolar
      Itu bukan tingkat yang mampu menahan NSA, tetapi mengingat DKIM hanyalah salah satu dari beberapa lapisan perlindungan, tampaknya cukup untuk menahan spammer
    • Rekor DKIM hanyalah rekaman DNS TXT
      Saya penasaran apakah ada batasan ukuran rekaman TXT, atau apakah mereka sengaja mencoba mem-parse rekaman TXT yang terlihat seperti DKIM, lalu gagal dan menolak penambahannya

  • Memecahkan kunci 512-bit demi demonstrasi yang baik adalah riset keamanan yang sangat bernilai, meskipun hal itu sudah pernah dilakukan
    Mengumumkan secara publik bahwa “berikut daftar tempat yang masih memakai 512-bit, jadi harus migrasi” juga sah-sah saja
    Namun secara pribadi saya merasa memecahkan langsung kunci dunia nyata yang sedang beroperasi melampaui batas etika, jadi saya tidak nyaman
    Saya bukan pengacara, tetapi sepertinya itu mungkin juga tindak pidana, dan terasa agak tidak perlu

    • Mereka memberi tahu perusahaan terkait tentang kerentanan itu, memperbaikinya, lalu memublikasikan tulisannya
      Cari now no longer available di teks asli
      Biasanya ketika menunjukkan bahwa sistem online rentan, peneliti mereproduksi kerentanan dengan itikad baik, mendokumentasikan risetnya, lalu meminta peninjauan
      Prosesnya sama, entah itu memecahkan sistem kriptografi, memperoleh eksekusi kode arbitrer di konsol game yang terkunci, membuktikan bahwa data mesin pemungutan suara bisa dimanipulasi, atau menunjukkan bahwa komentar Q&A Google Meet bisa diubah
      Jika hanya mengatakan bahwa sesuatu rentan, mereka bisa mengabaikannya; tetapi jika mengatakan rentan dan membuktikannya, itu menjadi sulit diabaikan
      Jika ditambah tenggat pengungkapan standar industri dan upaya menghubungi selama sekitar 60 hari sebelum kerentanan dipublikasikan, praktis tidak ada lagi ruang untuk mengabaikannya
    • Memecahkan kunci bukanlah kejahatan
      Itu hanya matematika
      Yang ilegal adalah mengandalkan matematika itu untuk mengirim email yang termasuk penipuan atau melanggar hukum di yurisdiksi tertentu
      Intinya bukan matematika, melainkan tindakan dan niat
      Menunjukkan bahwa seseorang melakukan hal bodoh juga bukan hal ilegal, meski mereka bisa saja mencoba membuat hidup Anda sulit
    • Hal yang sama bisa dikatakan tentang banyak riset keamanan
      Misalnya, “menunjukkan bahwa bug bisa dieksploitasi itu boleh, tetapi menulis kode proof-of-concept sudah melewati batas”
      Masalahnya, jika tidak menunjukkan bahwa itu benar-benar mungkin, kebanyakan orang tidak akan mendengarkan riset keamanan
    • Dari sekitar 1700 domain yang memakai kunci lebih pendek dari 1024-bit, hanya satu yang benar-benar disebutkan namanya secara publik
      Sebaliknya, dari 10 penyedia email besar yang tidak mengikuti RFC DKIM dengan benar, 3 di antaranya, yaitu Yahoo, Tuta, Mailfence, diumumkan setelah diberi tahu
    • Jika hanya menggunakan informasi publik dan tidak melakukan apa pun dengan hasilnya, kemungkinan besar memecahkan kunci yang digunakan di dunia nyata itu sendiri bukanlah kejahatan

  • Inilah alasan saya harus berhenti mengelola DNS dengan Hover
    Mereka tidak mendukung rekaman TXT yang lebih panjang dari 255 karakter, dan saya juga tidak menemukan contoh bahwa rekaman yang dipecah berfungsi di Hover
    Akhirnya saya menggunakan Digital Ocean
    Jika masalah seperti ini akan berlanjut 10 tahun lagi, saya berharap kriptografi kurva eliptik menjadi standar

  • Pada bagian yang mengatakan “sebagian besar penyedia dengan benar mengidentifikasi kunci 512-bit sebagai tidak aman dan menolak tanda tangan DKIM, tetapi tiga penyedia besar — Yahoo Mail, Mailfence, Tuta — melaporkan dkim=pass”, saya penasaran apakah Google benar-benar gagal karena tanda tangan DKIM tidak aman, atau karena SPF gagal

    • Verifikasi DKIM gagal sesuai RFC 8301 dengan hasil dkim=policy (weak key)
      Persis seperti persyaratan bahwa “verifier tidak boleh menganggap tanda tangan yang menggunakan kunci RSA kurang dari 1024-bit sebagai tanda tangan yang valid”

  • Apakah angka 512 bit itu besar atau kecil bergantung pada apakah itu kriptografi simetris atau kriptografi asimetris
    Anggap saja kriptografi asimetris selalu 8 kali lebih lemah daripada kriptografi simetris
    DKIM menggunakan pendekatan asimetris, jadi DKIM 512 bit setara dengan 64 bit berdasarkan hash simetris, dan sudah berada pada tingkat yang telah ditembus sejak lama
    Bahkan SHA-1 160 bit pun dianggap sudah ditembus
    Jika menginginkan DKIM dengan kekuatan yang mirip SHA-3 512 bit, setidaknya diperlukan 4096 bit, dan itu pun belum mencakup teknik mitigasi serangan replay milik SHA-3

    • DKIM bukan algoritma enkripsi
      DKIM adalah standar untuk memasukkan tanda tangan ke header email dan memverifikasinya
      Sayangnya, DKIM hanya mendukung tanda tangan rsa-sha1 dan rsa-sha256: https://datatracker.ietf.org/doc/html/rfc6376/#section-3.3
      Akan bagus jika DKIM direvisi agar mengizinkan Ed25519 atau tanda tangan serupa
    • Enkripsi RSA 10 kali lebih lemah daripada kriptografi kurva eliptik
      Misalnya, ECC 224 bit kira-kira setara dengan RSA 2048 bit
      Keduanya sama-sama asimetris
      Sebaliknya, kurva eliptik asimetris memiliki kekuatan yang mirip dengan AES, yang merupakan kriptografi simetris
      Tentu saja, ia rentan terhadap komputer kuantum