Kaspersky Password Manager 的漏洞

Hacker News Daily 上看到「Kaspersky Password Manager: All your passwords are belong to us」這篇,講 Kaspersky Password Manager (KPM) 嚴重的安全漏洞,另外在 Hacker News 上的討論「Kaspersky Password Manager: All your passwords are belong to us (ledger.com)」也有提到一些有趣的東西。

標題的 All your passwords are belong to us 是出自「All your base are belong to us」這個梗的變形。

這包安全問題主要的原因是因為 KPM 沒有使用 CSPRNG,而且也沒有正確 seed,所以極為容易被猜出密碼本身。

KPM 的 Web 版使用了 Math.random(),在各家瀏覽器主要是用 xorshift128+ 實做 Math.random(),作者沒有針對這塊再花時間研究,但很明顯的 Math.random() 不是個 CSPRNG:

The underlying PRNG used by Chrome, Firefox and Safari for Math.random() is xorshift128+. It is very fast, but not suitable to generate cryptographic material. The security consequences in KPM has not been studied, but we advised Kaspersky to replace it with window.crypto.getRandomValues(), as recommended by the Mozilla documentation page previously mentioned.

Note: Math.random() does not provide cryptographically secure random numbers. Do not use them for anything related to security. Use the Web Crypto API instead, and more precisely the window.crypto.getRandomValues() method.

而桌機版則是用了 MT19937,理論上取得 624 bytes 的輸出後就可以重建整個 PRNG 的內部狀態 (於是就可以預測後續的 output),但這代表你要知道其他網站的密碼,這點其實有點困難。

但作者發現 KPM 在產生 MT19937 的 seed 只跟時間有關,超級容易被預測:

So the seed used to generate every password is the current system time, in seconds. It means every instance of Kaspersky Password Manager in the world will generate the exact same password at a given second.

於是可以直接暴力解出所有的可能性:

The consequences are obviously bad: every password could be bruteforced. For example, there are 315619200 seconds between 2010 and 2021, so KPM could generate at most 315619200 passwords for a given charset. Bruteforcing them takes a few minutes.

Hacker News 上有不少陰謀論的討論,像是:

Getting some DUAL_EC prng vibes.

Insert Kaspersky owned by Russia intelligence conspiracy here...

另外 Kaspersky 跟俄羅斯軍方的關係也是很知名,這些東西大概要到十來年後才會知道...

GTA Online 釋出官方修正,大幅改善啟動效能

看到「GTA Online load time fix released, shaves off actual minutes of waiting for some」這邊的消息,先前在「GTA 的啟動讀取效能問題」這邊提到 GTA Online 啟動速度很慢的問題,官方正式推出修正版本了:「GTAV Title Update 1.53 Notes (PS4 / Xbox One / PC)」。

抓了一些在 Reddit 的討論「Loading Times Have FINALLY been patched - Discussion Thread」。

這則降的比率與當時 workaround 的修正差不多:

Insane. GTA menu -> GTA: Online.

Dropped from 7 minutes to 1:57

i7-2600k,GTX1070,16GB RAM and the game is on HDD.

這個就有點誇張了,這是 90% 吧?

Dropped from 5-8 minutes to 35 seconds

這個差不多 70%~80%:

Loading time 2m 20s for online directly from steam. Before it was like 8-10 minutes for me. Damn

Edit: 50s for story mode. 35s from story mode to online. So it seems it's still faster to load into online from story mode.

這個也差不多 70%:

From 4-5 minutes to 1 a minute and 22 seconds. Y e s p l e a s e

然後 PS4 的版本原來也受到一樣的影響?

Currently tested on PS4 , from main menu to online : 3min 45 sec From story mode to online: 1min 20sec (😩 i can't tell for sure )

整體看起來是正面的,畢竟大家等這個問題等超久了... 另外也可以看出來當初的 workaround patch 其實相當精準的把問題都解掉了,官方的修正並沒有快更多。

來繼續關注 libc 那邊的問題...

sscanf() 與 strlen() 的故事繼續發展

昨天在「GTA 的啟動讀取效能問題」這邊提到了 sscanf()strlen() 的問題,剛剛在 Hacker News Daily 上又看到一篇「It Can Happen to You」,在講他自己的專案也中獎。

他提到了一個解法,用 strtof() 取代 sscanf() 讀數字,結果大幅降低了 parsing 的時間:

Replacing the sscanf call with strtof improved startup by nearly a factor of 10: from 1.8 seconds to 199 milliseconds.

文章的最後面題到了不少目前正在進行中的討論與 patch。

首先是 FreeBSD 上的 patch 已經在測試:「address a performance problem w/ partial sscanf on long strings...」,裡面可以看到有很小心的在研究會不會造成 performance regression。

然後是 glibc 這邊,在 2014 年就有被開了一張票提出來:「Bug 17577 - sscanf extremely slow on large strings」,不過下面只是多了幾個 comment,目前沒有任何進度。

然後是 cppreference.com 上的「std::scanf, std::fscanf, std::sscanf」頁面則是加注了複雜度的問題:

Complexity

Not guaranteed. Notably, some implementations of sscanf are O(N), where N = std::strlen(buffer) [1]. For performant string parsing, see std::from_chars.

感覺接下來應該還會有更多人提出自己的災情,或是有人發現某個跑很慢的專案也是因為這個原因...

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)。

MySQL 的 TIME 範圍

這篇算是考古文,找出 MySQLTIME 資料型態奇怪範圍的由來:「TIME for a WTF MySQL moment」。

在官方的文件裡面可以看到 TIME 的範圍是個奇怪的數字,如果把各版本的文件都拉出來看,會發現都沒改過:「11.2.3 The TIME Type (8.0)」、「11.2.3 The TIME Type (5.7)」、「11.2.3 The TIME Type (5.6)」,「11.3.2 The TIME Type (5.5,靠 Internet Archive 的存檔頁面)」、「11.3.2 The TIME Type (5.1,靠 Internet Archive 的存檔頁面)」、「11.3.2 The TIME Type (5.0,靠 Internet Archive 的存檔頁面)」,裡面一直都是:

TIME values may range from '-838:59:59' to '838:59:59'.

這個數字看起來應該是某個限制,但作者粗粗算了幾種可能都不像,所以就一路考古,發現算是在 MySQL 3 年代因為某個特別公式留下來的遺毒,就一路用到現在了:

One of the bits was used for the sign as well, but the remaining 23 bits were an integer value produced like this: Hours × 10000 + Minutes × 100 + Seconds; in other words, the two least significant decimal digits of the number contained the seconds, the next two contained the minutes, and the remaining ones contained the hours. 223 is 83888608, i.e. 838:86:08, therefore, the maximum valid time in this format is 838:59:59.

話說回來,用 MySQL 的人還是很習慣用 INTBIGINT 來存時間,這樣可以自動遠離這些鳥問題,之前在「MySQL 裡儲存時間的方式...」與「Facebook 在 MySQL 裡存時間的型態」這邊都寫過...

不過最近用 PostgreSQL 比較多,可以比較「正常」的使用各種資料型態...

Network Time Security 正式成為 IETF 標準

在「NTS is now an RFC」這邊看到 Network Time Security 成為 IETF 的標準了:「Network Time Security for the Network Time Protocol」。

這個標準比較特別的是,因為 TLS 裡對 certificate 的驗證需要先有正確的時間,而導致 NTP 直接套用 TLS 會有「先有雞還是先有蛋」這樣的問題出現。這點在「8.5. Initial Verification of Server Certificates」這個章節裡面被討論到:

However, the expectation that the client does not yet have a correctly-set system clock at the time of certificate verification presents difficulties with verifying that the certificate is within its validity period, i.e., that the current time lies between the times specified in the certificate's notBefore and notAfter fields.

看起來還是頗複雜,但至少先給個方法出來了...

Cloudflare 降低 Workers 的 Cold Start 時間的方法...

Cloudflare 改善了 Workers 的 cold start 時間:「Eliminating cold starts with Cloudflare Workers」。

傳統的作法是連線結束後 application 層收到時去拉 worker 起來跑:

他們想到的方法是在收到 TLS 的 ClientHello 封包時就可以拉起來等了:

這點利用了 TLS 啟動時的交換時間,把 cold start 的時間疊起來,不過缺點應該就是同一個 domain 下的所有的 worker 都得拉起來,不過因為只有 cold start 的部份,應該是還好...

Chrome Extension 的效能分析

在「2020 Chrome Extension Performance Report」這邊看到有人對 Chrome Extension 上前一千名的效能分析,作者有提到是在 GCP 上的虛擬機測試的,跑七次取中位數:

I ran these tests on an n2-standard-2 Google Cloud instance, the numbers in this report show the median of 7 runs.

在「Chrome Extension Performance Lookup」這頁可以直接互動查詢,像是丟入 block 找跟擋廣告有關的關鍵字可以看到:

只看一般性的 blocker (中間還有 VPN 與一些不是一般性的先跳過),沒什麼意外的 uBlock Origin 的表現很好。

文章內的說明也可以翻一下,看看有沒有哪些 extension 其實不是很必要,但卻榜上有名,可以考慮拔掉省時間與資源...

Facebook 提供 Public NTP Service

在「Building a more accurate time service at Facebook scale」這邊 Facebook 講了不少跟 NTP 有關的東西,不過重點在他們提供 Public NTP service:

Having five independent geographically distributed endpoints helps us provide better service — even in the event of a network path failure. So we provide five endpoints:

  • time1.facebook.com
  • time2.facebook.com
  • time3.facebook.com
  • time4.facebook.com
  • time5.facebook.com

Each of these endpoints terminates in a different geographic location, which has a positive effect on both reliability and time precision.

看起來是混了 anycast 進去,從台灣 (HiNet) 走的話,time1.facebook.com 會到東京,time2.facebook.com 到大阪 (難得在 traceroute 上看到 ITM 這個代碼,代表 伊丹機場),time3.facebook.com 則是台灣,time4.facebook.com 到香港,time5.facebook.com 好像是馬來西亞?看 latency 與 maa 這個詞... (Update:應該是清奈國際機場)

可以考慮看看,另外 Google Public NTP 也是個選項。

讓手機上瀏覽器自動帶出數字鍵盤的方式

在「HTML attributes to improve your users' two factor authentication experience」這邊看到關於讓使用者輸入 2FA (通常是數字) 比較流暢的設定。

原始是上面這張這樣,目標是希望下面這張這樣,當透過 SMS 2FA 時可以提供選項直接貼上,而且也自動帶出數字鍵盤:

給出的幾個重點在於 inputmodepattern 以及 autocomplete

<input
  type="text"
  name="token"
  id="token"
  inputmode="numeric"
  pattern="[0-9]*"
  autocomplete="one-time-code"
/>

查了一下 caniuse.com 上面的支援度,pattern 基本上都支援了,autocomplete 在這邊用到的 one-time-code 基本上也沒問題,只有 inputmode 這邊支援度比較差,IE11 (基本上不會更新了)、FirefoxSafari 沒支援。