Tag: algorithm

FreeBSD 14.0 釋出

FreeBSD 14.0-RELEASE 的公告也出來了：「FreeBSD 14.0-RELEASE Announcement」，比較完整的 release notes 在「FreeBSD 14.0-RELEASE Release Notes」。

先從官方列的 highlight 來看，首先比較重要的是 GENERIC kernel 支援 1024 cores：

FreeBSD supports up to 1024 cores on the amd64 and arm64 platforms.

看了一下 commit log 是從 256 變成 1024。

先就 x86-64 這邊來看，目前「家用」最多的應該是 AMD 的 7995WX (96 cores)，舊版的 256 限制應該也還能撐住，但看 commit log 有提到，主要是預期這幾年應該會有更暴力的機器出現。

另外一塊是伺服器端，Intel 這邊有 8 sockets 的版本 (參考「Intel Xeon Sapphire Rapids to Scale to 4 and 8 Sockets」)，如果都是接 8490H 的話就是 480 cores 了。

ARM 的話好像也可以堆，但不熟...

另外一個提到的重點是 TCP 預設的 congestion control 改成 CUBIC：

The default congestion control mechanism for TCP is now CUBIC.

翻 commit log 可以看到是從 NewReno 換成 CUBIC 的，這樣就跟 Linux kernel 預設值一樣了。

再來比較重要的是在 release notes 裡面提到的，FreeBSD 15.0 將會拔光 32-bit 環境的支援，只留 armv7，這代表 Raspberry Pi 第一代的 armv6 也被淘汰掉了：

FreeBSD 15.0 is not expected to include support for 32-bit platforms other than armv7. The armv6, i386, and powerpc platforms are deprecated and will be removed. 64-bit systems will still be able to run older 32-bit binaries.

然後有些我自己翻覺得還蠻有趣的。

首先是看到 non-root 的 chroot：

The chroot facility supports unprivileged operation, and the chroot(8) program has a -n option to enable its use. a40cf4175c90 (Sponsored by EPSRC)

然後把 OpenSSH 內對 FIDO/U2F 的支援開起來了：

The use of FIDO/U2F hardware authenticators has been enabled in ssh, using the new public key types ecdsa-sk and ed25519-sk, along with corresponding certificate types. FIDO/U2F support is described in https://www.openssh.com/txt/release-8.2. e9a994639b2a (Sponsored by The FreeBSD Foundation)

ASLR 預設開啟：

Address Space Layout Randomization (ASLR) is enabled for 64-bit executables by default. It can be disabled as needed if applications fail unexpectedly, for example with segmentation faults. To disable for a single invocation, use the proccontrol(1) command: proccontrol -m aslr -s disable command. To disable ASLR for all invocations of a binary, use the elfctl(1) command: elfctl -e +noaslr file. Problems should be reported via the problem reporting system, https://bugs.freebsd.org, or posting to the freebsd-stable@FreeBSD.org mailing list. b014e0f15bc7 (Sponsored by Stormshield)

然後先前被罵臭頭的 WireGuard 支援也放回來了：(「FreeBSD & pfSense 上的 WireGuard 問題」)

The kernel wg(4) WireGuard driver has been reintegrated; it provides Virtual Private Network (VPN) interfaces using the WireGuard protocol. 744bfb213144 (Sponsored by Rubicon Communications, LLC ("Netgate") and The FreeBSD Foundation)

然後看到 Netflix 贊助的 kTLS 支援 TLS 1.3：

KTLS (the kernel TLS implementation) has added receive offload support for TLS 1.3. Receive offload is now supported for TLS 1.1 through 1.3; send offload is supported for TLS 1.0 through 1.3. 05a1d0f5d7ac (Sponsored by Netflix)

然後 FreeBSD 長久以來 root 預設用的 /bin/csh 改成 /bin/sh 了：

The default shell for the root user is now sh(1), which has many new features for interactive use. d410b585b6f0

預設的 MTA 變成 dma (Dragonfly Mail Agent)，看名字加上翻了一下 manpage，確認是從 Dragonfly BSD 移植過來的：

The default mail transport agent (MTA) is now the Dragonfly Mail Agent (dma(8)) rather than sendmail(8). Configuration of the MTA is done via mailer.conf(5). sendmail(8) and its configuration remain available. a67b925ff3e5

然後 portsnap 被拔掉了，現在就建議直接用 git 拉了，算是功成身退了：

The portsnap(8) utility has been removed. Users are encouraged to fetch the ports tree by using pkg install git and then git clone https://git.FreeBSD.org/ports.git /usr/ports. df53ae0fdd98

而 mergemaster 也被換成 etcupdate 了：

mergemaster(8) has been deprecated. Its replacement is etcupdate(8). 398b12691b4f (Sponsored by The FreeBSD Foundation)

然後支援 tarfs，而且可以用 zstd：

The tarfs(5) file system has been added, which is backed by POSIX tar archives optionally compressed with zstd(1). 69d94f4c7608 (Sponsored by Juniper Networks, Inc.) (Sponsored by Klara, Inc.)

好久沒看 FreeBSD 的 release notes...

NIST P-curve 的 Seed Bounty Program

Filippo Valsorda 發起了 seed bounty program，針對 NIST P-curve 裡 seed 的部分尋找 SHA-1 的 pre-image：「Announcing the $12k NIST Elliptic Curves Seeds Bounty」。

先講一下這次的 bounty program，希望找出下面這些 SHA-1 的 pre-image input (也就是找出 input，使得 SHA1(input) 會等於下面的東西)：

3045AE6FC8422F64ED579528D38120EAE12196D5
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
C49D360886E704936A6678E1139D26B7819F7E90
A335926AA319A27A1D00896A6773A4827ACDAC73
D09E8800291CB85396CC6717393284AAA0DA64BA

金額是 US$12288，但是要五個都找到。

話說在寫這篇時，查資料發現 P-384 有獨立條目，但 P-256 與 P-521 都是重導指到 Elliptic-curve cryptography 這個條目，但 P-384 看起來也沒什麼特別的，不知道當初編輯的人是怎麼想的...

回來原來的問題，要從一些背景開始講，橢圓曲線的表示法有多種，像是：

y^2 = x^3 + ax + b (Weierstrass form) y^2 = x^3 + ax^2 + bx (Montgomery form)

而這些常數 a 與 b 的選擇會影響到計算速度，所以通常會挑過，但畢竟是密碼學用的東西，挑的過程如果都不解釋的話，會讓人懷疑是不是挑一個有後門的數字，尤其 NIST (NSA) 後來被證實在 Dual_EC_DRBG 裡面埋後門的醜聞，大家對於 NIST 選擇或是設計的密碼系統都有很多疑慮。

舉個例子來說，2005 年時 djb 發明了 Curve25519 (論文「Curve25519: new Diffie-Hellman speed records」則是記錄 2006)，選擇的橢圓曲線是：

y^2 = x^3 + 486662x^2 + x

他就有提到這邊的 486662 是怎麼來的：他先在前一個段落說明，這邊數字如果挑的不好的話，會有哪些攻擊可以用，接下來把最小的三個值列出來，然後說明原因：

To protect against various attacks discussed in Section 3, I rejected choices of A whose curve and twist orders were not {4 · prime, 8 · prime}; here 4, 8 are minimal since p ∈ 1+4Z. The smallest positive choices for A are 358990, 464586, and 486662. I rejected A = 358990 because one of its primes is slightly smaller than 2^252, raising the question of how standards and implementations should handle the theoretical possibility of a user’s secret key matching the prime; discussing this question is more difficult than switching to another A. I rejected 464586 for the same reason. So I ended up with A = 486662.

而 P-192、P-224、P-256、P-384 與 P-521 的值都很怪，這是十六進位的值，在正式的文件或是正式的說明上都沒有解釋，屬於「magic number」：

3045AE6FC8422F64ED579528D38120EAE12196D5 # NIST P-192, ANSI prime192v1
BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5 # NIST P-224
C49D360886E704936A6678E1139D26B7819F7E90 # NIST P-256, ANSI prime256v1
A335926AA319A27A1D00896A6773A4827ACDAC73 # NIST P-384
D09E8800291CB85396CC6717393284AAA0DA64BA # NIST P-521

依照 Steve Weis 說，這些值當初是 Jerry Solinas 是隨便抓個字串，再用 SHA-1 生出來的：

Apparently, they were provided by the NSA, and generated by Jerry Solinas in 1997. He allegedly generated them by hashing, presumably with SHA-1, some English sentences that he later forgot.

這是 Steve Weis 的敘述，出自「How were the NIST ECDSA curve parameters generated?」：

[Jerry] told me that he used a seed that was something like:
SEED = SHA1("Jerry deserves a raise.")
After he did the work, his machine was replaced or upgraded, and the actual phrase that he used was lost. When the controversy first came up, Jerry tried every phrase that he could think of that was similar to this, but none matched.

如果可以證實當初的字串，那麼 NIST 在裡面埋後門的疑慮會再降低一些，這就是這次發起 bounty program 的原因。

Tor 的 Onion 導入防禦機制，在遭受 DoS 的時候要求用戶端執行 PoW 任務

在「Introducing Proof-of-Work Defense for Onion Services」這邊看到 0.4.8 的新機制，當 Onion 服務受到 DoS 時，會需要 client 提供 PoW 證明，有證明的會優先處理：

Tor's PoW defense is a dynamic and reactive mechanism, remaining dormant under normal use conditions to ensure a seamless user experience, but when an onion service is under stress, the mechanism will prompt incoming client connections to perform a number of successively more complex operations. The onion service will then prioritize these connections based on the effort level demonstrated by the client.

主要原因是傳統遇到 DoS 時可以透過 IP address 之類的資訊設計阻擋機制，但在 Onion 服務裡面沒有這個資訊，所以需要其他方式阻擋：

The inherent design of onion services, which prioritizes user privacy by obfuscating IP addresses, has made it vulnerable to DoS attacks and traditional IP-based rate limits have been imperfect protections in these scenarios. In need of alternative solutions, we devised a proof-of-work mechanism involving a client puzzle to thwart DoS attacks without compromising user privacy.

這個 PoW 機制的說明可以在「torspec/proposals/327-pow-over-intro.txt」這邊看到，看起來是三年前 (2020/04/02) 就提出來了，直到 0.4.8 才推出。

裡面有提到 PoW 的演算法是用 Equi-X：

For our proof-of-work function we will use the Equi-X scheme by tevador [REF_EQUIX].

看起來是個方法，而且從 cryptocurrency 後大家對 PoW 的用法愈來愈熟悉了，在這邊用還不錯...

SHA-256 的 Length extension attack

在 Hacker News 上看到「Breaking SHA256: length extension attacks in practice (kerkour.com)」，在講不當使用 SHA-256 會導致 Length extension attack 類的安全漏洞，主要是因為 MD5、SHA-1 以及 SHA-2 類的 hash function 最後生出 hash 值時會暴露出 hash function 的內部狀態而導致的問題。

這邊講的不當使用是指你沒有使用標準的 MAC，而是自己用字串組合實作造成的問題，通常是 S = H(secret || message) 這樣的形式，這邊的 || 是指字串相接。

拿 MD5 為例子，在維基百科上面可以看到 MD5 演算法對應的 pseudo code，最後輸出的部分可以看到是把 a0、a1、a2、a3 這四個 32-bit variable 接起來，也就是把內部的狀態丟出來了：

// Process the message in successive 512-bit chunks:
for each 512-bit chunk of padded message do
    // ...

    // Add this chunk's hash to result so far:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 // (Output is in little-endian)

於是你在可以反推 padding 的結構之後 (會需要知道 secret 的長度)，就可以往後接東西繼續算下去，這就是被稱作 length extension attack。

本來只有 S = H(secret || message)，你在不知道 secret 的情況下就可以疊字串到後面而且算出對應的 hash 值，變成 S' = H(secret || message || evildata)。

維基百科給的例子也示範了怎麼「用」，這是原始的資料以及 server 端簽出來的 hash 值：

Original Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo
Original Signature: 6d5f807e23db210bc254a28be2d6759a0f5f5d99

於是我們想要蓋 waffle 參數，就變成：

Desired New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo&waffle=liege

攻擊者則可以不斷的嘗試，去猜測 padding 的結構，把計算出來對應的 hash 值丟到 server 看反應，直到看到 200 OK 的回應：

New Data: count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x28&waffle=liege
New Signature: 0e41270260895979317fff3898ab85668953aaa2

如同前面提到的，這是 hash function 在最後把內部狀態直接暴露出來造成的問題，在 MD5、SHA-1、SHA-2 (SHA-256、SHA-384、SHA-512) 都有類似的問題，而比較新的 hash function 在設計時就已經有考慮到了，不會出現這個問題，像是 SHA-3。

另外一方面，不要自己發明演算法，使用標準的 MAC 演算法通常是比較好的選擇。這邊用的比較廣泛的應該就是 HMAC，超過 25 年了。

結論是 SHA-256 還是堪用，儘量拿現成的演算法套，不要自己搞。

GPT 的進程 (或是 LLM 的進程)

前幾天不知道在哪邊看到「Five years of GPT progress」這篇，裡面整理了這五年 GPT/LLM 的進程，算是回顧性質的文章，裡面當然有提到技術改善的地方 (像是參數大小，類神經網路層的架構差異)，另外裡面都有原始論文或是資料的連結，然後作者也有描述一些當時的背景，對於要釐清歷史脈絡也蠻有幫助的。

從 GPT、GPT-2、GPT-3 這三個 OpenAI 的作品開始講，然後提到 GPT-3 帶出來的新紀元。

接著提到的是各家都開始進來參與的年代，Jurassic-1 (AI21 Labs)、Megatron-Turing NLG (Nvidia)、Gopher (DeepMind)、Chinchilla (DeepMind)、PaLM (Google AI)。

然後是 LLaMa (Facebook)，第一個有參數夠大，而且效能夠好的 model，被放出來讓大家玩的 LLM。

最後又回到 OpenAI 的 GPT-4。

這樣整理讀起來清晰不少，但要注意裡面的發展不是線性關係，彼此之間互相影響交錯在跑 (因為中間還是有很多其他的論文互相影響)。

Vector clock 的發明時間軸

一樣是在 Hacker News 上看到「Who invented vector clocks? (decomposition.al)」這篇文章，在找出誰發明了 vector clock，原文在「Who invented vector clocks?」。

主要有兩個不同的時間點，一個是 vector clock 概念的提出，另外一個是第一次用到 vector 這個詞。

這篇讓我覺得有趣的地方是，vector clock 本來就是在處理分散式系統裡面事件順序的問題，而這篇文章則是在找出真實世界裡面這些發明的先後順序，而且也牽扯到了各種 citation (類比到分散式系統裡事件的 dependency)。

分散式系統的 clock

前幾天在 Hacker News 上看到「Clocks and Causality – Ordering Events in Distributed Systems (2022) (exhypothesi.com)」這篇，講分散式系統上 clock 的設計，作者也有跑出來在 Hacker News 上面跟大家聊一下 (帳號是 thoughtlede)，原文在「Clocks and Causality - Ordering Events in Distributed Systems」這邊。

文章裡面主要講空間是 O(1) 的 Lamport timestamp 與空間是 O(n) 的 Vector clock (這邊的 n 相對於節點數量)，以及這兩個對應的擴充版本：

作者會整理這些資料的原因是因為在研究 CRDT 的時候看到演算法中常常會需要處理分散式系統裡面事件的順序，所以花了一些時間整理常見的方式：

Author here. Pleasantly surprised to see the article here.

Some context behind the article. I studied CRDTs for a few months, and noticed that different CRDT designs use logical clocks in different and clever ways. And I haven't seen anyone narrate all those ways of use in one article. My attempt with this article was to dredge up those flavors of logical clocks into one article and give them names for future reference.

(To respond to a couple of other comments, I ignored atomic (and gps-based) clocks in this discussion, as indicated in my footnote 3).

我記得還有一個 Interval Tree Clocks 可以參考 (在「Interval Tree Clocks」這邊講的比較清楚)，是針對節點的動態增刪而改善的演算法，但不確定有什麼比較有名的系統有用。

大多數應該都是用 Vector clock，畢竟是在 2007 年的「Dynamo: Amazon’s Highly Available Key-value Store」被發揚光大，而且也算是還不錯的演算法？

OpenSSH 與 Dropbear 對 Ed25519 的支援

查了一下這兩個 server 端的軟體支援 Ed25519 的時間點。

OpenSSH 是在 2014/01/30 的 6.5 就支援了：

* ssh(1), sshd(8): Add support for Ed25519 as a public key type. Ed25519 is a elliptic curve signature scheme that offers better security than ECDSA and DSA and good performance. It may be used for both user and host keys.

算是相當久以前就支援了。對應到第一個支援的 Debian 版本是 Jessie 使用的 OpenSSH 6.7：「sshd(8) — openssh-server — Debian jessie — Debian Manpages」；第一個支援的 Ubuntu (LTS) 版本是 Trusty (14.04) 用的 OpenSSH 6.6：「openssh source package in Trusty」。

Dropbear 這邊就晚不少，在 2020/06/15 的 2020.79 版本才支援：

- Support ed25519 hostkeys and authorized_keys, many thanks to Vladislav Grishenko. This also replaces curve25519 with a TweetNaCl implementation that reduces code size.

所以對應到第一個支援的 Debian 版本是 Bullseye 的 2020.81：「Debian -- Details of package dropbear in bullseye」；第一個支援 Ubuntu (LTS) 的版本是 Jammy (22.04) 的 2020.81：「Ubuntu – Details of package dropbear in jammy」。

這樣看起來如果就是想要用 Ed25519 的話，變成 server 端的軟體得配合：預設裝的 sshd 應該都是 OpenSSH，如果想要換 Dropbear 的話要看 distribution 內給的版本夠不夠新，或是透過 PPA 之類的方法裝新版。

但大多數採用 BusyBox 的機器應該沒有採用新版 Dropbear (像是 AP 刷機)，這邊還是得使用其他 key format，如果要避開 NIST 有介入的格式，就還是得用 ssh-rsa 了。

Intel 用 AVX-512 加速 NumPy 的排序演算法被整合進主線了

Intel 用 AVX-512 加速 NumPy 排序的實做被整合進主線了：「「Intel Publishes Blazing Fast AVX-512 Sorting Library, Numpy Switching To It For 10~17x Faster Sorts」」。

GitHub 的 PR 在「ENH: Vectorize quicksort for 16-bit and 64-bit dtype using AVX512 #22315」這邊，可以看到相關的留言：

This patch adds AVX512 based 64-bit on AVX512-SKX and 16-bit sorting on AVX512-ICL. All the AVX512 sorting code has been reformatted as a separate header files and put in a separate folder. The AVX512 64-bit sorting is nearly 10x faster and AVX512 16-bit sorting is nearly 16x faster when compared to std::sort. Still working on running NumPy benchmarks to get exact benchmark numbers

16-bit int sped up by 17x and float64 by nearly 10x for random arrays. Benchmarked on a 11th Gen Tigerlake i7-1165G7.

有點「有趣」的情況是，AVX-512 在新的 Intel 消費級 CPU 被拔掉了，只有伺服器工作站的 CPU 有保留。而 AMD 的 Zen 4 則是跳下去支援 AVX-512...

另外在「Intel Publishes Fast AVX-512 Sorting Library, 10~17x Faster Sorts in NumPy (phoronix.com)」這邊當然也有人提到，如果用更廣泛的 AVX2 (寬度是 256bits) 加速的話應該也會有很大的進步才對？幾乎這十年的 CPU 都有 AVX2 了... 不過看起來沒有什麼深入的討論？

NIST 更新了 SHA-1 的淘汰計畫

NIST 對 SHA-1 的新的淘汰計畫出來了：「NIST Retires SHA-1 Cryptographic Algorithm」。

先前 NIST 在 2004 年時是計畫在 2010 年淘汰掉 SHA-1，在「NIST Brief Comments on Recent Cryptanalytic Attacks on Secure Hashing Functions and the Continued Security Provided by SHA-1」這邊可以看到當時的宣佈：

The results presented so far on SHA-1 do not call its security into question. However, due to advances in technology, NIST plans to phase out of SHA-1 in favor of the larger and stronger hash functions (SHA-224, SHA-256, SHA-384 and SHA-512) by 2010.

但看起來當時沒有強制性，所以事情就是一直拖一直延期，中間經過了 2017 年 Google 與 CWI Amsterdam 展示的 SHA-1 collision：「Google 與 CWI Amsterdam 合作，找到 SHA-1 第一個 collision」。

以及 2020 年時的進展與分析，發現 chosen-prefix collision 已經是可行等級了：「SHA-1 的 chosen-prefix collision 低於 2^64 了...」。

然後 NIST 總算是想起來要更新 phase out 的計畫，現在最新的計畫是在 2030 年年底淘汰掉 SHA-1：

As today’s increasingly powerful computers are able to attack the algorithm, NIST is announcing that SHA-1 should be phased out by Dec. 31, 2030, in favor of the more secure SHA-2 and SHA-3 groups of algorithms.

這次就有一些強制的規範了，包括採購的部份：

“Modules that still use SHA-1 after 2030 will not be permitted for purchase by the federal government,” Celi said.

但 2030 年聽起來還是有點慢...