IBM 的 50 qubit quantum computer

IBM 在展示他們做到了什麼:「IBM makes 20 qubit quantum computing machine available as a cloud service」。

不過重點應該在目前已經拉出 50 qubit prototype 了:

The company also announced that IBM researchers had successfully built a 50 qubit prototype, which is the next milestone for quantum computing, but it’s unclear when we will see this commercially available.

18 個月從 5 qubit 到 20 qubit:

IBM has been offering quantum computing as a cloud service since last year when it came out with a 5 qubit version of the advanced computers. Today, the company announced that it’s releasing 20-qubit quantum computers, quite a leap in just 18 months. A qubit is a single unit of quantum information.

如果是以這樣的速度成長 (每 18 個月變成原來四倍),五年後就有機會殺 RSA 2048 bits 了?(大約需要 4000 個 qubit)

這比想像中快好多,難怪現在密碼學都在討論抵抗 quantum computer 的演算法...

下一代的 Tor Hidden Service

Tor 公佈了下一代的 Hidden Service (Onion Service):「Tor's Fall Harvest: the Next Generation of Onion Services」。

三年前 Facebook 自己暴力算出 facebookcorewwwi.onion 這個很特別的名字 (參考「Facebook 證明 Tor 的 Hidden Service 不安全」),這陣子連紐約時報也能暴力算出 nytimes3xbfgragh.onion 這個好名字 (參考「紐約時報網站上 Tor 的 Hidden Service (i.e. Tor Onion Service)」,這讓只有 16 chars 的 hostname 的 hashed-space 不夠大的問題愈來愈明顯 (只有 80 bits 的空間)。

如果你也想要找出一個有趣的 hostname 的話,可以用 lachesis/scallion 這樣的工具,這程式用 CPU 產生出 RSA key 後,再用 GPU 算 SHA-1

The inital RSA key generation is done the CPU. An ivybridge i7 can generate 51 keys per second using a single core. Each key can provide 1 gigahash worth of exponents to mine and a decent CPU can keep up with several GPUs as it is currently implemented.

也因為如此,Facebook 與紐約時報在上線時並不是直接在 Hidden Service 上裸奔,而是上了 HTTPS 作為 workaround,以避免資料外洩。

但這畢竟是 workaround,Tor 的人還是希望協定本身就可以提供一個夠安全的架構,而花了四年多發展出下一代的 Hidden Service,也就是這次提到的成果了。

最大的改變就是 hostname 變長很多了,從本來的 16 chars 變成 56 chars:

And finally from the casuals user's PoV, the only thing that changes is that new onions are bigger, tastier and they now look like this: 7fa6xlti5joarlmkuhjaifa47ukgcwz6tfndgax45ocyn4rixm632jid.onion.

hostname 變長主要是因為把整個 256 bits public key 放進去,可以從 spec 看到:

6. Encoding onion addresses [ONIONADDRESS]

   The onion address of a hidden service includes its identity public key, a
   version field and a basic checksum. All this information is then base32
   encoded as shown below:

     onion_address = base32(PUBKEY | CHECKSUM | VERSION) + ".onion"
     CHECKSUM = H(".onion checksum" | PUBKEY | VERSION)[:2]

     where:
       - PUBKEY is the 32 bytes ed25519 master pubkey of the hidden service.
       - VERSION is an one byte version field (default value '\x03')
       - ".onion checksum" is a constant string
       - CHECKSUM is truncated to two bytes before inserting it in onion_address

  Here are a few example addresses:

       pg6mmjiyjmcrsslvykfwnntlaru7p5svn6y2ymmju6nubxndf4pscryd.onion
       sp3k262uwy4r2k3ycr5awluarykdpag6a7y33jxop4cs2lu5uz5sseqd.onion
       xa4r2iadxm55fbnqgwwi5mymqdcofiu3w6rpbtqn7b2dyn7mgwj64jyd.onion

   For more information about this encoding, please see our discussion thread
   at [ONIONADDRESS-REFS].

這是因為在 ECC 的安全性被廣泛認可後,ECC 的優點就被拿出來用在這次設計上了:

  • 256 bits 的 ECC key 強度大約是 3072 bits RSA key (以現在最好的攻擊演算法來估算)。
  • 直接放 public key 不需要經過 hash function 計算,可以避免掉 hash function 被找到 collision 時的風險。

於是因為 hostname 放的下,就硬塞進去了 XDDD

不過如果要玩的人需要裝 alpha 版本,目前的 stable 版本還沒有這個功能:

Tor as of version 0.3.2.1-alpha supports the next-gen onion services protocol for clients and services! As part of this release, ​the core of proposal 224 has been implemented and is available for experimentation and testing by our users.

The DUHK Attack:因為亂數產生器的問題而造成的安全漏洞

Bruce Schneier 那邊看到的:「Attack on Old ANSI Random Number Generator」,攻擊的網站在「The DUHK Attack」,論文在「Practical state recovery attacks against legacy RNG implementations (PDF)」。

攻擊的對象是 ANSI X9.31 Random Number Generator:

DUHK (Don't Use Hard-coded Keys) is a vulnerability that affects devices using the ANSI X9.31 Random Number Generator (RNG) in conjunction with a hard-coded seed key.

然後攻擊的對象是 FortinetFortiOS

Traffic from any VPN using FortiOS 4.3.0 to FortiOS 4.3.18 can be decrypted by a passive network adversary who can observe the encrypted handshake traffic.

如果照說明的只到 4.3.18,那麼去年 11 月更新的 4.3.19 (參考「FortiOS 4.3.19 Release Notes」) 應該是修正了?不過裡面沒翻到類似的資料,是剛好把 RNG 換掉了嗎?

歡樂的 md5crypt 密碼...

作者寫了一篇關於以前在 WHOIS 記錄上看到一串 $1$ 開頭的 md5crypt 密碼 XDDD:「I mean, why not tell everyone our password hashes?」。

Now the fields are filtered but this is a reasonably recent change. Prior to July 2015 the hashed passwords were shown to anyone who whois’d the maintainer object and used md5 passwords. Which was nearly all of them in my experience.

Mntner:         DTAG-NIC
Descr:          Deutsche Telekom Internet Services NIC
Admin-c:        KK281-RIPE
Tech-c:         HI56-RIPE
Auth:           MD5-PW $1$KQ3NSRfS$/bcvLAz2BKyf5HF4VkPMh/
Mnt-by:         DTAG-NIC
Referral-by:    RIPE-DBM-MNT

不知道有沒有人去跑看看... XD

話說 md5crypt 已經被認為不安全 (當初的發明人 phk 也有出來建議大家換掉了:「Md5crypt Password scrambler is no longer considered safe by author」),從目前 Hashcat 的攻擊速度就可以看出來... 找個最近的例子來說,可以參考「8x Nvidia GTX 1080 Hashcat Benchmarks」這篇。

Hashtype: md5crypt, MD5(Unix), FreeBSD MD5, Cisco-IOS MD5

Speed.Dev.#1.:  9918.1 kH/s (97.10ms)
Speed.Dev.#2.:  9830.1 kH/s (97.70ms)
Speed.Dev.#3.: 10017.4 kH/s (97.36ms)
Speed.Dev.#4.:  9986.5 kH/s (96.92ms)
Speed.Dev.#5.:  9976.8 kH/s (97.74ms)
Speed.Dev.#6.:  9889.2 kH/s (97.29ms)
Speed.Dev.#7.: 10010.5 kH/s (97.40ms)
Speed.Dev.#8.: 10083.0 kH/s (96.94ms)
Speed.Dev.#*.: 79711.6 kH/s

而隔壁的 bcrypt 對 Hashcat 的防禦性完全在不同等級:

Hashtype: bcrypt, Blowfish(OpenBSD)

Speed.Dev.#1.:    13094 H/s (47.51ms)
Speed.Dev.#2.:    13076 H/s (47.63ms)
Speed.Dev.#3.:    13292 H/s (46.88ms)
Speed.Dev.#4.:    13250 H/s (47.17ms)
Speed.Dev.#5.:    13296 H/s (46.86ms)
Speed.Dev.#6.:    13160 H/s (47.30ms)
Speed.Dev.#7.:    13260 H/s (46.98ms)
Speed.Dev.#8.:    13280 H/s (46.80ms)
Speed.Dev.#*.:   105.7 kH/s

直接相除是 754 倍左右。

以 85 個字元的組合計算 ([0-9A-Za-z] 62 個,特殊字元 22 個,加上空白 1 個),抗性多了 1.5 個字 (log85(754) 大約是 1.49)?如果以 62 個字元來看也有 1.6 個字,強了不少...

BoringSSL 的 FIPS 140-2 驗證

看到由 Google 主導的 BoringSSL 有計劃將其中一塊申請 FIPS 140-2 的驗證計畫 (BoringCrypto 的部份):「FIPS 140-2」。

其中 FIPS 140-2 最有名的後門應該是 Dual_EC_DRBG (定義於 NIST SP 800-90A,被 FIPS 140-2 引用),所以特地講清楚他們選擇哪個演算法:

FIPS 140-2 requires that one of its PRNGs be used (which they call DRBGs). In BoringCrypto, we use CTR-DRBG with AES-256 exclusively and RAND_bytes (the primary interface for the rest of the system to get random data) takes its output from there.

而且還花了不少篇幅解釋 PRNG 的細節。

GitHub 決定在 2018/02/01 停用不安全的 HTTPS/SSH 演算法

在「Discontinue support for weak cryptographic standards」這邊訂了日期,2018/02/01 將會關閉:

看起來最苦的應該是 Android 4.3 以及更早的版本,以現在的官方數字來看還有 13%+ (Dashboards),這些版本內建的瀏覽器不支援 TLSv1.2,不過另外裝 browser 就還能過...

對 SHA-3 的攻擊

隔壁棚剛順利打趴 SHA-1 (Google 與 CWI Amsterdam 合作,找到 SHA-1 第一個 collision),還是有人在針對比較新的演算法在攻擊:「SymSum: Symmetric-Sum Distinguishers Against Round Reduced SHA3」。

完整的 SHA-3 是 24 rounds,這次打的是 9 rounds 版本,雖然有段距離,但這等於是大進展:

Based on this we propose a new distinguisher called SymSum for the SHA3 family which penetrates up to 9 rounds and outperforms the ZeroSum distinguisher by a factor of four.

不過 SHA-3 用的人不算多,該不會在還沒成為主流就被打趴...

Google 與 CWI Amsterdam 合作,找到 SHA-1 第一個 collision

GoogleCWI Amsterdam 正式攻陷 SHA-1:「Announcing the first SHA1 collision」,然後也沒什麼意外的,現在大家都喜歡針對各種安全問題註冊一個 domain 來介紹:「SHAttered」。

shattered-1.pdfshattered-2.pdf 下載下來確認,可以看出來兩個不一樣的檔案有同樣的 SHA-1 value:

gslin@home [/tmp] [21:33/W4] sha1sum *.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-1.pdf
38762cf7f55934b34d179ae6a4c80cadccbb7f0a  shattered-2.pdf

gslin@home [/tmp] [21:33/W4] sha256sum *.pdf
2bb787a73e37352f92383abe7e2902936d1059ad9f1ba6daaa9c1e58ee6970d0  shattered-1.pdf
d4488775d29bdef7993367d541064dbdda50d383f89f0aa13a6ff2e0894ba5ff  shattered-2.pdf

直接拿 pdf 來打,表達的是「一次到位」以及「既然可以攻擊 pdf,那麼其他東西當然也有可能」...

攻擊計算量的部份,這次攻擊使用的資源其實不算少,但對於大公司與大單位已經不是問題了,猜這次 Google 應該是贊助不少雲端設施:

  • 6,500 years of CPU computation to complete the attack first phase
  • 110 years of GPU computation to complete the second phase

這衍生出另外一個頭比較大的問題是 Git 目前使用的 SHA1:

GIT strongly relies on SHA-1 for the identification and integrity checking of all file objects and commits. It is essentially possible to create two GIT repositories with the same head commit hash and different contents, say a benign source code and a backdoored one. An attacker could potentially selectively serve either repository to targeted users. This will require attackers to compute their own collision.

這下得來看 Git 核心團隊要怎麼從 SHA-1 migrate 到其他 hash function 了...

NIST 開始徵求 Post-Quantum Cryptography 演算法

現有常見的幾個加密基礎在量子電腦上都有相當快速的解 (像是整數質因數分解、離散對數),只是現在建不出對應夠大台的量子電腦... 但畢竟只是時間的問題了,所以 NIST 照著慣例對外尋求能夠抵抗量子電腦的演算法:「NIST Asks Public to Help Future-Proof Electronic Information」、「Announcing Request for Nominations for Public-Key Post-Quantum Cryptographic Algorithms」。

類似於 Google 先前在 Google Chrome 上實做的 CECPQ1,對 key exchange 的部份加上保護 (Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography),這次 NIST 是針對 public key crytpsystem 的部份而發的...

投稿時間在 2017 的十一月底,大約一年後就可以看到有哪些演算法要參加競賽了... 不過因為 NSA 的惡名,不知道會不會有其他單位在同個時段啟動類似的活動...

Google 測試 CECPQ1 的一些資料...

七月的時候提到「Google Chrome 引入 CECPQ1,開始測試 Post-Quantum Cryptography」,剛剛看到 Adam Langley 寫了一些數據出來:「CECPQ1 results」。

目前看起來對於網路速度不快的使用者會影響比較大,最慢的 5% 使用者大約慢了 20ms,最慢的 1% 使用者會慢 150ms:

Although the median connection latency only increased by a millisecond, the latency for the slowest 5% increased by 20ms and, for the slowest 1%, by 150ms. Since NewHope is computationally inexpensive, we're assuming that this is caused entirely by the increased message sizes. Since connection latencies compound on the web (because subresource discovery is delayed), the data requirement of NewHope is moderately expensive for people on slower connections.

由於實驗算是完成了,加上 TLS 已經有規劃了,所以 Google Chrome 打算拔掉這個功能等標準出來:

At this point the experiment is concluded. We do not want to promote CECPQ1 as a de-facto standard and so a future Chrome update will disable CECPQ1 support. It's likely that TLS will want a post-quantum key-agreement in the future but a more multilateral approach is preferable for something intended to be more than an experiment.