ROCA:Infineon Technologies 的 RSA 實做問題

最近的另外一個大包,不過這包是 Infineon Technologies 在實做 RSA 算法時的問題,倒不是 RSA 算法本身有問題。之所以會「大」是因為有太多人用了:「ROCA: Vulnerable RSA generation (CVE-2017-15361)」。

起因於 Infineon Technologies 在產生 key 時的組合有限,於是要猜測的 keyspace 小很多。

以研究者的估算,可以看出 CPU year 都被大幅減少了,都是屬於「可行」的範圍:

The time complexity and cost for the selected key lengths (Intel E5-2650 v3@3GHz Q2/2014):

512 bit RSA keys - 2 CPU hours (the cost of $0.06);
1024 bit RSA keys – 97 CPU days (the cost of $40-$80);
2048 bit RSA keys – 140.8 CPU years, (the cost of $20,000 - $40,000).

而且這邊是用 CPU year 估算,如果考慮 FPGA 加速計算,應該會短更多...

另外從發現到公開的時間線也拉得很長,可以看到中間一直在找解決方案:

2nd of November 2017 - Presentation of all details at the ACM CCS conference (to come)
16th of October 2017 - The initial version of the public disclosure published
May to October 2017 - Cooperation with the manufacturer and other affected parties to help evaluate and mitigate the vulnerability
1st of February - The vulnerability disclosed to Infineon Technologies AG
End of January - The vulnerability found

過一陣子就會去 conference 上報告了...

Branchless UTF-8 解碼器

看到「A Branchless UTF-8 Decoder」這篇,先來回憶一下「非常經典的 UTF-8...」這篇,以及裡面提到的 encoding:

因為當初在設計 UTF-8 時就有考慮到,所以 decoding 很容易用 DFA 解決,也就是寫成一堆 if-then-else 的條件。但現代 CPU 因為 out-of-order execution 以及 pipeline 的設計,遇到 random branch 會有很高的效能損失,所以作者就想要試著寫看看 branchless 的版本。

成效其實還好,尤其是 Clang 上說不定在誤差內:

With GCC 6.3.0 on an i7-6700, my decoder is about 20% faster than the DFA decoder in the benchmark. With Clang 3.8.1 it’s just 1% faster.

而後來的更新則是大幅改善,在 Clang 上 DFA 版本比 branchless 的快:

Update: Björn pointed out that his site includes a faster variant of his DFA decoder. It is only 10% slower than the branchless decoder with GCC, and it’s 20% faster than the branchless decoder with Clang. So, in a sense, it’s still faster on average, even on a benchmark that favors a branchless decoder.

所以作者最後也有說這是個嘗試而已 XD:

It’s just a different approach. In practice I’d prefer Björn’s DFA decoder.

PostgreSQL 10 發表

PostgreSQL 10 發表,有不少重要的功能 (進步):「PostgreSQL 10 Released」。

首先提到的是 Logical Replication:

Logical Replication - A publish/subscribe framework for distributing data

以往內建的 replication 是 block level change (同步哪個 block 改變的內容),對於版本不同的 PostgreSQL 就會痛。所以在 10 之前,想要處理 PostgreSQL 版本不同的問題都會使用第三方套件 (一種常見的情境就是資料庫的版本升級)。在 10 內建支援 Logical Replication 後就不需要掛其他套件了:

Logical replication extends the current replication features of PostgreSQL with the ability to send modifications on a per-database and per-table level to different PostgreSQL databases. Users can now fine-tune the data replicated to various database clusters and will have the ability to perform zero-downtime upgrades to future major PostgreSQL versions.

於是就可以達到 zero-downtime upgrade,這對於商業維運考量是個很重要的進展。

另外一個是 Improved Query Parallelism (在 9.6 就有,現在又再改善了),針對可平行化的 CPU-bounded SQL query 可以利用多 CPU 大幅加速,這點也是目前在 MySQL 上還沒看到的:

PostgreSQL 10 provides better support for parallelized queries by allowing more parts of the query execution process to be parallelized. Improvements include additional types of data scans that are parallelized as well as optimizations when the data is recombined, such as pre-sorting. These enhancements allow results to be returned more quickly.

上面提到這兩點其實對於某些需求是相輔相成的。

因為很多報表分析是可平行化的 CPU-bounded SQL query,但以前在 RDBMS 都不能被平行運算,於是很多單位就會想要倒出來到其他類型的資料庫運算 (以現在比較紅的產品,像是 Amazon RedshiftAmazon Athena,或是 BigQuery,甚至是丟進 ELK 裡)。但你用 PostgreSQL 又會痛在沒辦法很方便的把資料同步拉出來... (於是就會稍微妥協,用 cron job 每天倒資料)

現在 10 的這兩個功能剛好從兩個面向解決:一個是對於剛開使用 PostgreSQL 的人,他們可以繼續只用 PostgreSQL 撐久一點,因為報表需求的 SQL query 快很多;另外一方面也讓目前用 cron job 每天倒資料的人有了同步的選擇 (用 replication 同步到其他系統上)。

再來是 Quorum Commit for Synchronous Replication 這個功能,把分散式架構中需要「正確性」的底層技術做起來:

PostgreSQL 10 introduces quorum commit for synchronous replication, which allows for flexibility in how a primary database receives acknowledgement that changes were successfully written to remote replicas. An administrator can now specify that if any number of replicas has acknowledged that a change to the database has been made, then the data can be considered safely written.

整體來說,PostgreSQL 10 有非常多進步,而且這些進步對於商業營運考量都很有幫助...

MySQL 8.0-rc 的效能測試

Oracle 的 Dimitri KRAVTCHUK (dim) 做了測試,整理出 MySQL 8.0-rc 與其他版本效能的比較:「MySQL Performance : 2.1M QPS on 8.0-rc」。

不過先不管 MySQL 8.0-rc,這個測試其實也在說 MySQL 在 5.6 到 5.7 的過程中,對於高階伺服器效能改善非常的多 (有非常多 CPU core 的機器):

就更不用說 5.5 版 (甚至已經沒支援的 5.0 & 5.1),差距就更大了...

最新的 Firefox 56 對 AES-GCM 效能的改善

昨天釋出的 Firefox 56 對於 AES-GCM 在老電腦上改善了不少效能:「Improving AES-GCM Performance」。

首先是 Firefox 自己的數據分析,可以看到 AES-GCM 佔目前加密連線裡的大宗,再來是 AES-CBC:

先以 Linux 64bits 環境的數據來看,Firefox 56 的 NSS 3.32 大幅改善了老電腦的效能 (不支援 AES-NI 硬體加解密的 CPU,甚至是不支援 PCLMUL 的 CPU,以及不支援 AVX 的 CPU):

在 Linux 32bits 環境上則是連預設值大幅改善,不過用的人應該少很多了:

Windows 下則是因為 64bits 或是 32bits 都有足夠的使用者,所以平常就花了不少力氣。但也可以看出對於老電腦的速度提升:

Mac (64bits only) 算是這次比較大的提升,連新電腦的預設值都大幅變快:

加上之後陸續的改善 (尤其是下一版 Firefox 57 的 Project Quantum),這幾版應該會拉出不少效能...

Facebook 把 InnoDB 換成 MyRocks 的計畫

在「Migrating a database from InnoDB to MyRocks」這邊講到了 FacebookMySQL 的 InnoDB 換成 MyRocks 的計畫。

Facebook 已經大量導入全 Flash 的環境,於是現在 InnoDB (Compressed) 的情況類似於這樣:

可以看到空間是最大的問題 (Space-bound),而非 CPU 或是 I/O,這在純 Flash 的機器上還蠻有可能的,因為純 Flash 能提供的 I/O capacity 超高,加上 Facebook 把 MySQL 當作後端儲存設備而已,CPU 的使用量可以預期不高...

然後他們估算 MyRocks 可以省下一半的空間,於是有可能變成:

不過對於一般單位來說,這些前提就未必成立了... 但還是可以看到 Mark Callaghan 花不少力氣在調校一般性的效能,希望讓使用者多一點...

C++ 與組語的速度...

Hacker News Daily 上看到「Why is this C++ code faster than my hand-written assembly for testing the Collatz conjecture?」覺得很有趣...

作者寫了一段 assembly,但跑起來比用 C++ 同義的版本慢多了。目前最高分的答案給了很清楚的解釋...

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

上面這段 code 是作者寫的組語版本,用到 div 指令,這是非常慢的指令:

On Intel Haswell, div r64 is 36 uops, with a latency of 32-96 cycles, and a throughput of one per 21-74 cycles.

相較於 C++ 的版本,用到的是 shr (logical shift right,以位元方式往右平移,最高位補零),速度快太多:

shr rax, 1 does the same unsigned division: It's 1 uop, with 1c latency, and can run 2 per clock cycle.

這是用到無號整數透過 shr 平移一格剛好是除以二的特性,因為速度的關係,這個用法到現在還是很常被拿來用,但對於平常沒在寫 assembly 的人就會有上面的誤解 XDDD

DigitalOcean 推出 High CPU Droplets

DigitalOcean 推出了高 CPU 使用量的 VPS 服務:「Introducing High CPU Droplets」。

價位從 USD$40/month 開始。相較於 Standard Droplet,CPU 的速度提升到 2.5 倍速 (平均):

The current CPUs powering High CPU Droplets are the Intel Broadwell 2697Av4 with a clock speed of 2.6Ghz, and the Intel Skylake 8168 with a clock speed of 2.7Ghz. Customers in our early access period have seen up to four times the performance of Standard Droplet CPUs, and on average see about 2.5 times the performance.

目前早期先開放這些區,八月底會開 FRA1 與 LON1:

These Droplets are available through the Control Panel and the API starting today as capacity allows in SFO2, NYC1, NYC3, TOR1, BLR1, and AMS3. They will be available in FRA1 and LON1 by the end of August.

等 benchmark 數字出來後才會比較清楚跟 AWS 上的 c4.large 系列比起來如何... 不過現在看起來 DigitalOcean 想直接跟 AWS 對決?如果技術上沒有特別的東西,應該會蠻辛苦的... (因為只剩下價格)

MySQL 總算要拔掉 mysql_query_cache 了

半官方的 MySQL blog 上宣佈了拔掉 mysql_query_cache 的計畫:「MySQL 8.0: Retiring Support for the Query Cache」。

作者開頭引用了 ProxySQL 的人對 MySQL Query Cache 的說明:

Although MySQL Query Cache was meant to improve performance, it has serious scalability issues and it can easily become a severe bottleneck.

主要問題在於 MySQL Query Cache 在多 CPU 環境下很難 scale,很容易造成一堆 thread 在搶 lock。而且作者也同意 ProxySQL 的說法,將 cache 放到 client 的效能比較好:

We also agree with Rene’s conclusion, that caching provides the greatest benefit when it is moved closer to the client:

可以看到 Query Cache 在複雜的環境下對效能極傷。而之前也提到過類似的事情了:「Percona 對 mysql_query_cache 的測試 (以 Magento 為例)」、「關閉 MySQL 的 Query Cache」。

一般如果要 cache 的話,透過 InnoDB 裡良好的 index 應該還可以撐不少量起來。

Ruby 2.4 中 Hash Table 的效能改善

前幾天 Ruby 推出了 2.4.0 (Ruby 2.4.0 Released),其中特別被拿出來提的:「Introduce hash table improvement (by Vladimir Makarov)」。

討論串很長而且歷時很久,但可以看出來方向是提高 CPU cache 效率:

Modern processors have several levels of cache. Usually,the CPU reads one or a few lines of the cache from memory (or another level of cache). So CPU is much faster at reading data stored close to each other. The current implementation of Ruby hash tables does not fit well to modern processor cache organization, which requires better data locality for faster program speed.

中間還有拿 Redmine 當作測試項目... XD