處理很久前用 OpenSSL 加密的備份資料

因為想要翻一些舊的文章 (小說),想把以前 BBS 的備份拉出來看看裡面有沒有,結果發現 OpenSSL 解半天都解不開,還跑去玩了 bruteforce-salted-openssl 這個專案:

Try to find the password of a file that was encrypted with the 'openssl' command.

後來也是因為這個專案提醒,發現 openssl enc 指令在 OpenSSL 1.0.x (以及之前) 預設是用 MD5 當 digest algorithm,而 1.1.x 換成了 SHA-256,而我的備份資料應該是在 0.9.x 的年代就生出來了...

指定 -md md5 後就正常解出來了:

openssl enc -bf -d -md md5 -in ooxx.tar.gz.bf -out ooxx.tar.gz

另外一個收穫是 CPU 溫度降了不少:因為跑 bruteforce-salted-openssl 的時候 CPU 到 80 度,感覺撞到安全值卡在 4.0Ghz,所以就把 CPU 電壓降了 0.1V,看起來溫度低了不少 (少了五度),但跑起來還是 4.0Ghz...

講求速度的 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 的情況下好像沒有太多出場機會...

TCP Congestion Control Algorithm 的選擇

先前 Ubuntu 桌機用 BBR 跑了一陣子,但有遇到一些問題 (可以參考「Dropbox 測試 BBRv2 的結果」這篇),所以暫時換成 Westwood,但還是陸陸續續會看一下各種研究。

剛剛在「[tor-relays] TCP CCA for Tor Relays (and especially Bridges)」這邊看到一個經驗談:

Here are my completely unscientific scribbles of how all the various algorithms behaved. The scenario is uploading for a minute or so, observing the speed in MB/sec visually, then recording how it appeared to change during that minute (and then repeating this a couple of times to be certain).

tcp_bic.ko       -- 6...5...4
tcp_highspeed.ko -- 2
tcp_htcp.ko      -- 1.5...3...2
tcp_hybla.ko     -- 3...2...1
tcp_illinois.ko  -- 6...7...10
tcp_lp.ko        -- 2...1
tcp_scalable.ko  -- 5...4...3
tcp_vegas.ko     -- 2.5
tcp_veno.ko      -- 2.5
tcp_westwood.ko  -- <1
tcp_yeah.ko      -- 2...5...6

上面是「目視法」觀察到的速度 (MB/sec),看了一下維基百科上 TCP-Illinois 的說明,看起來設計的目的是提供給頻寬大、latency 高的情境下:

It is especially targeted at high-speed, long-distance networks.

來跑跑看好了...

Dropbox 測試 BBRv2 的結果

BBRv1 有不少問題,在 BBRv2 有一些改善 (目前還在測試階段,在「TCP BBR v2 Alpha/Preview Release」這邊可以看到一些說明),而 Dropbox 則是跳下去測試,並且公佈結果:「Evaluating BBRv2 on the Dropbox Edge Network」。


Spoiler alert: BBRv2 is slower than BBRv1 but that’s a good thing.

在文章開頭的這張圖就說明了 BBRv2 的速度比較慢,但是說明這是朝好的方向改善。

BBRv1 的問題其實我自己都有遇到:我自己的 Ubuntu 桌機跑 BBRv1,在我上傳大量資料的時候 (只開一條連線),會導致 PPPoE 的 health check 失敗,於是就斷線了,另外 VM 裡面的 Windows 7 因為也是 bridge mode 跑 PPPoE,也可以看到斷線嘗試重連的訊息,於是只好改掉...

上面提到的問題就是 BBRv1 造成 packet loss 過高,除了我遇到的問題外,這對於其他 loss-based 的 TCP congestion algorithm 來說會有很大的傷害 (i.e. 不公平):

Other tradeoffs were quite conceptual: BBRv1’s unfairness towards loss-based congestion controls (e.g. CUBIC, Compound), RTT-unfairness between BBRv1 flows, and (almost) total disregard for the packet loss:

另外一個改善是 BBRv2 加入了 ECN 機制,可以更清楚知道塞住的情況。

整體上來說應該會好不少,不知道之後正式釋出後會不會直接換掉 Linux Kernel 裡的 BBRv1,或是不換,讓 BBRv1 與 BBRv2 共存?

比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter

Bloom filter 算是教科書上的經典演算法之一,在實際應用上有更好的選擇,像是先前提到的 Cuckoo filter:「Cuckoo Filter:比 Bloom Filter 多了 Delete」。

現在又有人提出新的資料結構,號稱又比 Bloom filter 與 Cuckoo filter 好:「Xor Filters: Faster and Smaller Than Bloom Filters」。

不過並不是完全超越,其中馬上可以看到的差異就是不支援 delete:

Deletions are generally unsafe with these filters even in principle because they track hash values and cannot deal with collisions without access to the object data: if you have two objects mapping to the same hash value, and you have a filter on hash values, it is going to be difficult to delete one without the other.

論文的預印本可以在 arXiv 上下載:「Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters」。

CloudFront 的 BBR 效能提昇

這是在找一些 TCP congestion algorithm 相關的資訊時發現的,看起來 Amazon CloudFront 導入 BBR 一陣子了:「TCP BBR Congestion Control with Amazon CloudFront」。

不過 BBR 被研究的愈來愈多,大家開始發現這個演算法的霸道,跟其他的 TCP congestion algorithm 並不太能和平共存,但這就跟軍事武器一樣,隔壁升級了你就得跟著升級,抱怨沒有用,只會被消滅...

Google 與 Cloudflare 測試 Post-Quantum 演算法的成果

這幾年量子電腦的進展不斷有突破,雖然到對於攻擊現有的密碼學看起來還有一段時間,但總是得先開始研究對量子電腦有抵抗性的演算法...

其中 Google Chrome 的團隊與 Cloudflare 的團隊手上都有夠大的產品,兩個團隊合作測試的結果在學界與業界都還蠻重視的:「Real-world measurements of structured-lattices and supersingular isogenies in TLS」、「The TLS Post-Quantum Experiment」。

Google Chrome 這邊是使用了 Canary 與 Dev 兩個 channel,有控制組與兩個新的演算法:

Google Chrome installs, on Dev and Canary channels, and on all platforms except iOS, were randomly assigned to one of three groups: control (30%), CECPQ2 (30%), or CECPQ2b (30%). (A random ten percent of installs did not take part in the experiment so the numbers only add up to 90.)

這兩個演算法有優點也有缺點。一個是 key 比較小,但運算起來比較慢 (SIKE,CECPQ2b);另外一個是 key 比較大,但是運算比較快 (HRSS,CECPQ2):

For our experiment, we chose two algorithms: isogeny-based SIKE and lattice-based HRSS. The former has short key sizes (~330 bytes) but has a high computational cost; the latter has larger key sizes (~1100 bytes), but is a few orders of magnitude faster.

We enabled both CECPQ2 (HRSS + X25519) and CECPQ2b (SIKE/p434 + X25519) key-agreement algorithms on all TLS-terminating edge servers.

感覺還是會繼續嘗試,因為這兩個演算法的缺點都還是有點致命...

Leslie Lamport 講 Paxos 與 TLA+

在「The Paxos Algorithm or How to Win a Turing Award」這邊看到 Leslie Lamport 在今年七月時親自講解 Paxos 這個經典演算法的錄影。另外一個有提到的主題是講形式規範的 TLA+,也是他的力作...

Leslie Lamport 是 2013 年的 Turing Award 得主,除了上面提到的事蹟外,LaTeX 也是他弄出來的東西,軟體名稱開頭的 La 就是他本人...

花些時間聽看看還不錯 (去聽看看他怎麼描述),不過現在的新軟體比較常實做 Raft,Paxos 比較少人選擇了...

Facebook 修正錯字的新演算法

先前 Facebook 已經先發表過 fastText 了,在這個月的月初又發表了另外一個演算法 Misspelling Oblivious Embeddings (MOE),是搭著本來的 fastText 而得到的改善:「A new model for word embeddings that are resilient to misspellings」。

Facebook 的說明提到在 user-generated text 的內容上,MOE 的效果比 fastText 好:

We checked the effectiveness of this approach considering different intrinsic and extrinsic tasks, and found that MOE outperforms fastText for user-generated text.

論文發表在 arXiv 上:「Misspelling Oblivious Word Embeddings」。

依照介紹,fastText 的重點在於 semantic loss,而 MOE 則多了 spell correction loss:

The loss function of fastText aims to more closely embed words that occur in the same context. We call this semantic loss. In addition to the semantic loss, MOE also considers an additional supervisedloss that we call spell correction loss. The spell correction loss aims to embed misspellings close to their correct versions by minimizing the weighted sum of semantic loss and spell correction loss.

不過目前 GitHub 上的 facebookresearch/moe 只有放 dataset,沒有 open source 出來讓人直接用,可能得自己刻...

用 Machine Learning 改善 Streaming 品質的服務與論文

Hacker News 上看到「Puffer」這個服務,裡面利用了 machine learning algorithm 動態調整 bitrate,以提昇傳輸品質。

測試得到的數據後來被整理起來一起放進論文:「Continual learning improves Internet video streaming」。

在開頭介紹了 Fugu 這個演算法:

We describe Fugu, a continual learning algorithm for bitrate selection in streaming video.

而 Puffer 就是實驗網站:

We evaluate Fugu with Puffer, a public website we built that streams live TV using Fugu and existing algorithms. Over a nine-day period in January 2019, Puffer streamed 8,131 hours of video to 3,719 unique users.

這個站台提供了許多真實的頻道進行測試:

Stream live TV in your browser. There's no charge. You can watch U.S. TV stations affiliated with the NBC, CBS, ABC, PBS, FOX, and Univision networks.

可以看到 Fugu 的結果很好,比起其他提出的方案是全面性的改善:

這邊是用 WebSocket 測試,並且配合了不同的 TCP congestion algorithm,沒有太考慮額外的計算成本...