GTA 的啟動讀取效能問題

這件事情也已經過了一個禮拜,來整理一下發生什麼事情...

起因是 GTA Online 的遊戲開啟速度很慢,而有人一路 reverse engineering 找出問題並且解決:「How I cut GTA Online loading times by 70%」,對應的 Hacker News 討論有提到其他有趣的事情也可以看看:「How I cut GTA Online loading times by 70% (nee.lv)」。

作者的電腦不算太差,但光開啟 GTA Online 就需要六分鐘,網路上甚至有辦投票蒐集大家的等待時間,發現也有很多人反應類似的問題:

接下來就開始 reverse engineering 了,先觀察各種狀態後發現是卡在 CPU,而不是網路或 Disk I/O,然後就拿出 Luke Stackwalker 這個工具 profiling,不過因為沒有 debug symbol 幫忙 group,所以只能人工判斷後,可以看到兩個問題:

第一個問題發現效能是卡在 strlen(),而 call stack 可以看出來是從 sscanf() 一路打進去的:

反追發現是在處理 10MB 的 JSON 檔造成的,裡面 sscanf() 因為拉出 strlen(),於是就造成把整個 10MB 的 JSON 掃過很多次 (一開始是 10MB,掃到後面會愈來愈少,平均下來應該是 5MB):

第二個問題產生的時間會在第一個問題跑完後,另外看問題的性質,應該跟第一個 JSON 處理有關,他會把 JSON 處理過的資料丟進 array,每個 entry 長這樣:

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

丟進 array 是 OK 的,但問題在於他需要判斷 entry 是否重複,卻沒有用 hash 或是 tree 的結構,而這邊大約有 63k 筆資料,用 array 實做就產生了 O(n^2) 的演算法:

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

作者在 PoC 的章節裡面描述他怎麼解這兩個問題。

第一個問題比較好的解法是修正 JSON Parser,但這太複雜,所以他用 workaround 解:把 strlen() 包起來,針對長字串加上一層 cache:

  • hook strlen
  • wait for a long string
  • “cache” the start and length of it
  • if it’s called again within the string’s range, return cached value

而第二個問題他直接把檢查是否有重複的跳過,因為資料本身不重複:

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

整個開啟的速度從六分鐘降到一分五十秒,還是偏慢,但算是大幅緩解的 GTA Online 啟動速度的問題了。

不過故事到這邊還沒結束,有人一路去挖,發現其實 sscanf() 的效能地雷已經不是第一次了:YAML 的 Parser 也中過一樣的問題:「Parsing can become accidentally quadratic because of sscanf」,這篇也一樣上了 Hacker News:「Parsing can become accidentally quadratic because of sscanf (github.com/biojppm)」。

然後這又帶出了六年前在 StackOverflow 上就有人問過這個問題:「Why is glibc's sscanf vastly slower than fscanf on Linux?」。

另外也有人整理出來,應該是大家把同樣的演算法拿來實做:

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

後續的更新動作可以再追一下進度 (包括 GTA Online 與各家的 libc)。

libtorrent 宣佈支援 BitTorrent v2

看到 libtorrent 宣佈支援 BitTorrent v2 (BEP 52) 的消息:「BitTorrent v2」。

BitTorrent v2 這個規格丟出來好久了,但一直都是 draft,而且沒什麼人想要理他,直到 Google 成功產生出 SHA-1 collision 的時候稍微有些音量跑出來,但沒想到居然有人跳下去支援了...

對使用者比較有感覺的差異是從 SHA-1 換成 SHA-2 的 SHA-256 了,這個會影響到整個 torrent file 的結構與 Magnet URI 的部份。

另外一個比較大的改變是 torrent 檔資料結構,有兩個比較大的改變。

第一個是以前用固定的 block size 切割,然後每個 block 產生出 hash,所以 torrent 檔會隨著 block size 選擇的大小 (成反比) 檔案大小 (成正比) 有關,現在會用 Merkle tree,所以只要有 root hash 就可以了。

第二個是以前是把所有檔案包在一起 hash,現在是個別檔案都有自己的 hash (改成 root hash),所以現在變成可以跨 torrent 檔共用檔案。

然後 libtorrent 的文章裡有提到向前相容的方法,不過以產品面上來說沒有什麼太大的誘因,libtorrent 雖然大,但其他幾家的支援度應該也是重點...

產生模糊縮圖的 BlurHash

先從一張圖片算出大約 20~30 bytes 的字串,就可以在 API response 時快速產生出一個很模糊但是有有代表性的縮圖 (或是在 HTML 裡面放,用 javascript 產生):「BlurHash」。

從官方給的範例比較快理解:

以及:

另外也提供了展現在 app 上的效果:

有支援一些程式語言,不過看起來行動平台上的支援都是比較新的語言 (Swift & Kotlin),如果不是用這些語言而想用 BlurHash 的話就得自己整了...

另外在 Hacker News 上有翻到先前的討論:「BlurHash: Algorithm to generate compact representation of an image placeholder」,開頭就看到其他軟體的作法:

For comparison, Instagram sends ~200 byte base64 thumbnails in its API responses. It's a low-res JPEG with a fixed header to save a bit more space. This is also used to blur sensitive images. You can get even better results with webp.

這個方法就避開另外再弄一包 library 進去,用現成的 library 就會動了...

講求速度的 Cryptographic Hash Function:BLAKE3

今年年初發表的 cryptographic hash function,重點在於速度:「The BLAKE3 cryptographic hash function」。

在 1 thread 的情況下就遠遠拉開目前的 cryptographic hash function:

因為速度是主打項目,所以提供的範例已經是使用 x86 與 ARM 的 SIMD 加速的版本,另外也可以透過平行化加速。

所以是要拼 de-facto standard 嗎,不知道 browser 這邊有沒有機會採用,雖然在現在都是使用 AEAD cipher 的情況下好像沒有太多出場機會...

SHA-1 的 chosen-prefix collision 低於 2^64 了...

算是前陣子的大消息,SHA-1 的 chosen-prefix collision 需要的運算已經低於 2^64 了:「SHA-1 is a Shambles」。

基本的 collision 指的是演算法找出 p1p2 兩個字串,使得 hash(p1) == hash(p2)。但這個方法對於實際的攻擊價值並不大,因為 p1p2 是透過演算法找出來 collision,都是亂數字串。

chosen-prefix collision 指的是先給定 p1p2 (在實際攻擊中,兩組都會是有意義的字串),然後攻擊的演算法可以算出 m1m2,使得 hash(p1 // m1) == hash(p2 // m2),其中的 // 就是字串加法。這樣的是先產生出有意義的字串,於是就可以在真實世界中使用。

舉例來說,我先產生出 blog.gslin.org 的 SSL certificate,然後再產生出一個 github.com 的 SSL certificate,這兩個分別就是 p1p2

接下來演算法算出 m1m2,使得 hash(p1 // m1)hash(p2 // m2) 相同。

接著,我就可以拿 p1 // m1 給 CA 簽名 (因為我有 blog.gslin.org 的擁有權),而拿到的憑證因為 hash 值相同,就可以給 github.com 這組用。

2008 年的時候就用這個方法生出一個 sub-CA:

In 2008, researchers used a chosen-prefix collision attack against MD5 using this scenario, to produce a rogue certificate authority certificate. They created two versions of a TLS public key certificate, one of which appeared legitimate and was submitted for signing by the RapidSSL certificate authority. The second version, which had the same MD5 hash, contained flags which signal web browsers to accept it as a legitimate authority for issuing arbitrary other certificates.[14]

另外,如果跟 2017 年由 GoogleCWI 打出來的 SHAttered 比較,當時的攻擊是 identicial-prefix,實際上的用途沒那麼大,這次是 chosen-prefix,就有很強的實際用途了。

所以這次的攻擊給了幾個重要的事情。

第一個是 SHA-1 的 chosen-prefix collision attack 運算已經降到 2^64 以下了,然後加上:

第二個是 2^64 的運算成本已經低於 USD$100k 了,作者是使用 GPUserversrental 這個租用 GPU 的服務跑出這次的運算,而這也表示攻擊安全層級是 2^64 的密碼系統,成本也是 USD$100k 了。

地球上還是有不少系統使用 SHA-1 (作者在網站上有提到),看起來這陣子會有不少修正...

iOS 13 與 macOS 10.15 對憑證的限制

Slack 上看到同事丟出來的,關於之後要推出的 iOS 13 與 macOS 10.15 會對憑證限制的項目:「Requirements for trusted certificates in iOS 13 and macOS 10.15」。

主要是把不安全的演算法淘汰掉 (RSA 小於 2048 bits,以及 SHA-1 類的 hash algorithm),這兩個部份相關的新聞應該不少,沒有什麼太大問題:

TLS server certificates and issuing CAs using RSA keys must use key sizes greater than or equal to 2048 bits. Certificates using RSA key sizes smaller than 2048 bits are no longer trusted for TLS.

TLS server certificates and issuing CAs must use a hash algorithm from the SHA-2 family in the signature algorithm. SHA-1 signed certificates are no longer trusted for TLS.

然後是要求憑證使用 SAN (Subject Alternative Name),舊的標準 CN (CommonName) 將不會再被信任。

如果是公開簽發的憑證應該都沒問題 (像是 Let's Encrypt,或是花錢買的那些),主要的問題應該會出現在自己建立的憑證,網路上蠻多舊資料還是產生 CN...

TLS server certificates must present the DNS name of the server in the Subject Alternative Name extension of the certificate. DNS names in the CommonName of a certificate are no longer trusted.

另外是 2019/7/1 之後發出的憑證,有額外兩個規範要注意,第一個是強制要透過 EKU 指定 id-kp-serverAuth,這是出自 RFC 5280

   id-kp-serverAuth             OBJECT IDENTIFIER ::= { id-kp 1 }
   -- TLS WWW server authentication
   -- Key usage bits that may be consistent: digitalSignature,
   -- keyEncipherment or keyAgreement

TLS server certificates must contain an ExtendedKeyUsage (EKU) extension containing the id-kp-serverAuth OID.

再來是時間的限制,接下來的憑證最長只認得 825 天 (大約 27 個月多一些),以前都惡搞 -days 3650,現在得兩年簽一次了:

TLS server certificates must have a validity period of 825 days or fewer (as expressed in the NotBefore and NotAfter fields of the certificate).

整體看起來主要是影響自己簽的部份...

改 Open Distro for Elasticsearch 預設密碼的方式

AWS 弄出來的 Open Distro for Elasticsearch 因為內建了安全性的功能 (參考「AWS 對 Elastic Stack 實作免費的開源版本 Open Distro for Elasticsearch」),應該是目前新架設 Elasticsearch 的首選。

不過裝好後預設有五個帳號,但從 Open Distro 的 Kibana 介面無法修改改其中兩個使用者的密碼 (adminkibanaserver),要修改密碼發現得花不少功夫,不知道為什麼要這樣設計 :/

這邊講的是透過 RPM (以及 deb) 的方式的修改方式,如果是 Docker 的方式請參考後面提到在 AWS blog 上的文章:「Change your Admin Passwords in Open Distro for Elasticsearch」。

首先先透過 hash.sh 產生 bcrypt 的 hash,像是這樣 (輸入 password 當密碼):

bash /usr/share/elasticsearch/plugins/opendistro_security/tools/hash.sh
WARNING: JAVA_HOME not set, will use /usr/bin/java
[Password:]
$2y$12$QchkpgY8y/.0TL7wruWq4egBDrlpIaURiBYKoZD50G/twdylgwuhG

然後修改 /usr/share/elasticsearch/plugins/opendistro_security/securityconfig/internal_users.yml 檔案裡面的值,順便改掉 readonly 的部分。

接下來是把這個 internal_users.yml 檔案的設定更新到 Elasticsearch 裡。由於這邊需要讀 /etc/elasticsearch/ 的東西,所以偷懶用 root 跑:

sudo bash /usr/share/elasticsearch/plugins/opendistro_security/tools/securityadmin.sh -cd ../securityconfig/ -icl -nhnv -cacert /etc/elasticsearch/root-ca.pem -cert /etc/elasticsearch/kirk.pem -key /etc/elasticsearch/kirk-key.pem

做完後可能要重跑 Elasticsearch 與 Kibana:

sudo service elasticsearch restart
sudo service kibana restart

或是重開機... 順便測試看看重開後有沒有生效。理論上修改完成後,就是用新的帳號密碼連到 Kibana。

上面的方法是參考了「Default Password Reset」(先找到這篇) 與「change admin password」(後來在 AWS blog 的文章上發現的 GitHub issue 連結) 這邊的資訊。

官方的說明文件則是在寫這篇文章時才找到的,平常搜尋時不太會出現:「Apply configuration changes」。

實際比較 Linode 的 Dedicated 主機與 AWS 的 c5.*

先前有提到 Linode 出了 Dedicated 主機:「Linode 推出 Dedicated CPU Instances」,現在找機會測試看看,拿了 Linode 的 Dedicated (4GB) 與 AWSc5.large 比較,同樣都是 2 vCPU 與 4GB RAM。

這邊用了 n-st/nenchOpenSSL 的 speed (包括了 aes、md5、rsa、sha1 與 sha256) 測試,我把結果都貼到這邊:「Linode (Dedicated 4GB) v.s. AWS (c5.large)」。

可以看到在 CPU 方面主要的差異是 Linode 用的是 AMD,而 AWS 用的是 Intel,所以就會有蠻多不同的數字表現...

如果仔細看 OpenSSL 的測試數據,可以看到不同演算法的差異還蠻大的,馬上可以想到的應該是硬體加速方式與 cache 架構差異造成的:

  • 在 cipher 類的測試我只測了 AES (目前的主流),小的 block (16/64/256 bytes) 時 AMD 會輸一些,但大的 block (1024/8192/16384 bytes) 反而會贏不少。
  • 在 hash 類的測試中,跑 MD5 時 Linode 則是輸一些,但 SHA1 反而是贏一些,然後 SHA256 時效能好到爆炸贏了一倍 XDDD
  • 在 public key 類的測試我測了 RSA,則是 Linode 輸的蠻慘的...

如果考慮到價位大約只有 AWS 的一半,應該是還不錯...

Amazon S3 提供更高的存取量...

AWS 宣佈提高了 Amazon S3 的效能:「Amazon S3 Announces Increased Request Rate Performance」。

每個 S3 prefix 都可以到 5500 RPS read 與 3500 RPS write:

Amazon S3 now provides increased performance to support up to 3,500 requests per second to add data and 5,500 requests per second to retrieve data, which can save significant processing time for no additional charge. Each S3 prefix can support these request rates, making it simple to increase performance exponentially.

舊的資料可以看「Request Rate and Performance Considerations」這邊,裡面沒有明講速度,但有提到如果超過 800 RPS read 與 300 RPS write 的門檻,建議開 case:

However, if you expect a rapid increase in the request rate for a bucket to more than 300 PUT/LIST/DELETE requests per second or more than 800 GET requests per second, we recommend that you open a support case to prepare for the workload and avoid any temporary limits on your request rate.

不過如果有量的話,還是建議照著原來的 prefix 建議,打散處理會比較好,通常在前面的 CDN 通常可以跑簡單的 url rewrite 處理掉 (像是 CloudFront 自家或是 Cloudflare),像是把使用 unix timestamp (ms) 的 https://www.example.com/1531843366123.jpg 變成 https://www.example.com/6123/1531843366123.jpg,這樣可以讓 Amazon S3 的後端依照 prefix 打散 loading,避免當站愈來愈大的時候很難處理。

Twitter 密碼中槍...

Twitter 發了公告請大家改密碼:「Keeping your account secure」。不只是 Twitter 自家的密碼,如果你有重複使用同一組密碼,也建議一起修改:

Out of an abundance of caution, we ask that you consider changing your password on all services where you’ve used this password.

雖然使用 bcrypt,但因為透過 log 記錄下了未加密的密碼,所以就中槍了:

We mask passwords through a process called hashing using a function known as bcrypt, which replaces the actual password with a random set of numbers and letters that are stored in Twitter’s system. This allows our systems to validate your account credentials without revealing your password. This is an industry standard.

Due to a bug, passwords were written to an internal log before completing the hashing process. We found this error ourselves, removed the passwords, and are implementing plans to prevent this bug from happening again.

這時候就要再推 Password manager 這種東西了,在每個站台都使用完全不同的密碼,可以降低這類問題帶來的衝擊...