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

YAML 常見的問題

Hacker News Daily 上看到「The yaml document from hell」這篇在抱怨 YAML 的問題,而 Hacker News 上對應的討論在「The Yaml document from hell (ruudvanasseldonk.com)」這邊。

翻了一下我之前也有提到好幾次不同來源的抱怨:「YAML 的地雷 (2014)」、「YAML 的痛點 (2019)」、「YAML 的問題 (挪威問題) (2021)」。

這篇提到的東西還是類似之前提到的,但整理的蠻不錯的?他給了一個看起來蠻正常的 YAML,然後裡面全部都是地雷,你可以看他的說明知道是什麼問題。

不過他提出來的問題都是可以加上 double quote 來避開,但把這個方式當作 common practice 用 YAML 會變得很痛苦。

不過市場上還沒有能取代的東西,只能先繼續邊用邊罵了,看了一下 Hacker News 上的留言,簡單一點的東西 (只是要放幾個值的) 大家都覺得 INI 還可以拿來用用...

fp32、fp16 與 bf16

nanoGPT 這個專案下面看到 bf16 這個浮點格式:(這段在新版的 README.md 被改寫了)

Currently fp16 is much faster than bf16. Potentially revert back to using fp16 and re-introduce the gradient scaler?

翻了一下 bf16,是由 Google 的團隊所提出來的想法,主打是與 fp32 相同的表示範圍,但是犧牲精度,這樣一來既有使用 fp32 的程式很有機會可以直接換成 bf16 降低計算量 & 提昇效率 (也就是 drop-in replacement):

然後同一頁也看到各家自己推出不同的格式,這邊看起來比較像是市場競爭的關係...

Python 的 Black

Hacker News 上看到 Black 這個幫你處理 Python 程式碼的工具:「Black, the uncompromising Python code formatter, is stable (pypi.org)」。

Black is the uncompromising Python code formatter. By using it, you agree to cede control over minutiae of hand-formatting. In return, Black gives you speed, determinism, and freedom from pycodestyle nagging about formatting. You will save time and mental energy for more important matters.

然後從 Hacker News 上討論的情況看起來大家都覺得很不錯?好像可以看看能不能拿來用...

另外一個在討論的時候看到學到的東西,是 git blame --ignore-revs-file 這個功能,可以在 git blame 時濾掉某些 commit,剛好拿來過濾 reformatting commit:

Ignore revisions listed in file, which must be in the same format as an fsck.skipList. This option may be repeated, and these files will be processed after any files specified with the blame.ignoreRevsFile config option. An empty file name, "", will clear the list of revs from previously processed files.

QOI 圖片無損壓縮演算法

Hacker News Daily 上看到「Lossless Image Compression in O(n) Time」這篇,作者丟出了一個圖片的無損壓縮演算法,壓縮與解壓縮的速度超快,但壓縮率又不輸 PNG 太多,在 Hacker News 上的討論也可以看一下:「QOI: Lossless Image Compression in O(n) Time (phoboslab.org)」。

裡面有提到在遊戲產業常用到的 stb_image.h

Yes, stb_image saved us all from the pains of dealing with libpng and is therefore used in countless games and apps. A while ago I aimed to do the same for video with pl_mpeg, with some success.

作者的簡介也可以看到他的主業也在遊戲這塊:

My name is Dominic Szablewski. I build games, experiment with JavaScript and occasionally tinker with low-level C.

圖片的無損壓縮與解壓縮算是遊戲創作者蠻常用到的功能,所以他想要看看這塊有沒有機會有更好的工具,於是他就用了四個很簡單的演算法幹完了 QOI (然後發現效果很讚):

  • A run of the previous pixel
  • An index into a previously seen pixel
  • The difference to the previous pixel
  • Full rgba values

其實從 Hacker News 的討論也可以看到這組演算法也常被拿出來在現代的壓縮演算法使用,所以雖然作者自稱不是 compression guy,但他用的演算法其實蠻專業的...

然後挑 single thread 主要是可以避免 threading 的複雜度以及 overhead,在「QOI Benchmark Results」這頁可以看到,無論是什麼類型的檔案,壓縮與解壓縮的速度都相當漂亮,而且壓縮率又沒有差 libpng 太多。

而且作者自己有提到,還沒用到 SIMD 指令集加速,這樣猜測應該還有不少空間...

在 command line 下生出全灰的圖片

因為需要一張 1920x1080 全灰色的圖片,翻了一下 DuckDuckGo 找到這篇:「Linux create Image pixel by pixel in command line」。

裡面抓重點,主要的想法是 PPM 格式 (可以參考「Netpbm」這個條目),然後找到「PPM Format Specification」這份文件。

主要就是用 P3 模式下去產生檔案:

repeat 2073600 echo '127 127 127' >> grey.ppm

然後開頭的地方修一下,加上 P3、長寬資訊以及最大的值:

P3
1920 1080
255

接著就用 ImageMagick 轉檔:

convert grey.ppm grey.png

然後用 viewer 看一下,確認沒問題就收工了...

RFC 3339 與 ISO 8601 用範例的比較

Hacker News 首頁上看到「RFC 3339 vs. ISO 8601 (ijmacd.github.io)」這個連結,原始網站是「RFC 3339 vs ISO 8601」。

兩個都是試著定義日期與時間的表達方式,其中 ISO 8601 是在 1988 年定義出來的,被廣泛應用在很多 spec 裡,但最大的問題就是 ISO 8601 沒辦法公開免費取得,這點在前幾個月也在 Hacker News 上被討論過:「ISO-8601 date format reference not publicly available (twitter.com/isostandards)」。

RFC 3339 是在 2002 年訂出來,其中一個目標就是試著解決 ISO 8601 不公開的問題 (沒講明就是了):

This document includes an Internet profile of the ISO 8601 [ISO8601] standard for representation of dates and times using the Gregorian calendar.

這份 RFC 3339 與 ISO 8601 的比較可以讓設計 spec 的人可以看一下,在大多數的情況下,RFC 3339 應該是夠用的...

為資料庫提案新的 UUID 格式

前幾天在 Hacker News Daily 上看到的東西,今年四月的時候有人針對資料庫提案新的 UUID 格式:「New UUID Formats – IETF Draft (ietf.org)」。

在 draft 開頭有說明這個提案的目標:

This document presents new time-based UUID formats which are suited for use as a database key.

A common case for modern applications is to create a unique identifier for use as a primary key in a database table. This identifier usually implements an embedded timestamp that is sortable using the monotonic creation time in the most significant bits. In addition the identifier is highly collision resistant, difficult to guess, and provides minimal security attack surfaces. None of the existing UUID versions, including UUIDv1, fulfill each of these requirements in the most efficient possible way. This document is a proposal to update [RFC4122] with three new UUID versions that address these concerns, each with different trade-offs.

另外在 Hacker News 上有人整理出來,可以直接理解提案所提出的新格式是什麼:

A somewhat oversimplified summary of the new UUID formats:

UUID6: a timestamp with a weird epoch and 100 ns precision like in UUID1, but in a big-endian order that sorts naturally by time, plus some random bits instead of a predictable MAC address.

UUID7: like UUID6, but uses normal Unix timestamps and allows more timestamp precision.

UUID8: like UUID7, but relaxes requirements on where the timestamp is coming from. Want to use a custom epoch or NTP timestamps or something? UUID8 allows it for the sake of flexibility and future-proofing, but the downside is that there's no standard way to parse the time from one of these -- the time source could be anything monotonic.

這在不同的 storage engine 上面會有不同的討論,這邊先討論 MySQL 系列的 InnoDB,至於 PostgreSQL 的 engine 以及其他資料庫系統,就另外讓更熟悉的人討論了。

InnoDB 採用了 clustered index (可以參考「Database index」這邊的說明),也就是資料本體是以某種定義的大小順序存放。

在 InnoDB 裡面則是用 primary key 的順序來存放資料 (沒有指定 primary key 時會有 fallback 行為),其他的 unique key 與 index key 則是指到 primary key,所以你可以看到 primary key 的大小也會影響到其他的 index key。

所以 128 bits 的 UUID 在大型的 MySQL ecosystem 實在不怎麼受歡迎,在 2010 年的時候 FlickrTwitter 都有發表過 ticket system:「Ticket Servers: Distributed Unique Primary Keys on the Cheap」、「Announcing Snowflake」,兩個系統有不同的需求,但都是產生 64 bits 的 unique id。

其中 Flickr 的系統算是很簡單的,沒有要保證時間順序 (i.e. 先取的號碼一定比較小,以及後取的號碼一定比較大),就用兩台 MySQL 跑 active-active 架構,然後錯開產生的值:

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1

TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2

到現在還是一個蠻簡單的解法...

GitHub 的 API Token 換格式

GitHub 前幾天宣佈更換 API token 的格式:「Authentication token format updates are generally available」,在今年三月初的時候有先公告要換:「Authentication token format updates」。

另外昨天也解釋了換成這樣的優點:「Behind GitHub’s new authentication token formats」。

首先是 token 的字元集合變大了:

The character set changed from [a-f0-9] to [A-Za-z0-9_]

另外是增加了 prefix 直接指出是什麼種類的 token:

The format now includes a prefix for each token type:

  • ghp_ for Personal Access Tokens
  • gho_ for OAuth Access tokens
  • ghu_ for GitHub App user-to-server tokens
  • ghs_ for GitHub App server-to-server tokens
  • ghr_ for GitHub App refresh tokens

另外官方目前先不會改變 token 長度 (透過字元變多增加 entropy),但未來有打算要增加:

The length of our tokens is remaining the same for now. However, GitHub tokens will likely increase in length in future updates, so integrators should plan to support tokens up to 255 characters after June 1, 2021.

看起來當初當作 hex string 而轉成 binary 會有問題,不過就算這樣做應該也是轉的回來的。

回到好處的部份,這個作法跟 SlackStripe 類似,讓開發者或是管理者更容易辨識 token 的類型:

As we see across the industry from companies like Slack and Stripe, token prefixes are a clear way to make tokens identifiable. We are including specific 3 letter prefixes to represent each token, starting with a company signifier, gh, and the first letter of the token type.

另外這也讓 secret scanning 的準確度更高,本來是 40 bytes 的 hex string,有機會撞到程式碼內的 SHA-1 string:

Many of our old authentication token formats are hex-encoded 40 character strings that are indistinguishable from other encoded data like SHA hashes. These have several limitations, such as inefficient or even inaccurate detection of compromised tokens for our secret scanning feature.

另外官方也建議現有的 token 換成新的格式,這樣如果真的發生洩漏,可以透過 secret scanning 偵測並通知:

We strongly encourage you to reset any personal access tokens and OAuth tokens you have. These improvements help secret scanning detection and will help you mitigate any risk to compromised tokens.

還原被碼掉的 PEM 資訊 (SSH RSA key)

在「Recovering a full PEM Private Key when half of it is redacted」這邊看到的,起因是 _SaxX_ 幫客戶做滲透測試時找到客戶公開在網路上的 SSH key,然後他就碼掉一部分貼出來:

原圖是這樣,接下來就開始被還原 XD

首先是 OCR 的過程,被稱為是整個還原過程最難的一部分 (哭爸啊):

Ironically, this was the hardest part of the challenge. It took the longest time of all the steps and was the easiest to make errors in.

接下來就是解讀 PEM 檔的格式,可以藉此得到裡面的參數。

然後是套公式,窮舉運算裡面的值,可以看到迴圈 kp 只算了 365537,就推算出可能的 p

e = 65537
q = 0xc28871e8714090e0a33327b88acc57eef2eb6033ac6bc44f31baeac33cbc026c3e8bbe9e0f77c8dbc0b4bfed0273f6621d24bc1effc0b6c06427b89758f6d433a02bf996d42e1e2750738ac3b85b4a187a3bcb4124d62296cb0eecaa5b70fb84a12254b0973797a1e53829ec59f22238eab77b211664fc2fa686893dda43756c895953e573fd52aa9bb41d22306135c81174a001b32f5407d4f72d80c5de2850541de5d55c19c1f817eea994dfa534b6d941ba204b306225a9e06ddb048f4e34507540fb3f03efeb30bdd076cfa22b135c9037c9e18fe4fa70cf61cea8c002e9c85e53c1eaac935042d00697270f05b8a7976846963c933dadd527227e6c45e1
dp = 0x878f7c1b9b19b1693c1371305f194cd08c770c8f5976b2d8e3cf769a1117080d6e90a10aef9da6eb5b34219b71f4c8e5cde3a9d36945ac507ee6dfe4c146e7458ef83fa065e3036e5fbf15597e97a7ba93a31124d97c177e68e38adc4c45858417abf8034745d6b3782a195e6dd3cf0be14f5d97247900e9aac3b2b5a89f33a3f8f71d27d670401ca185eb9c88644b7985e4d98a7da37bfffdb737e54b6e0de2004d0c8c425fb16380431d7de40540c02346c98991b748ebbc8aac73dd58de6f7ff00a302f4047020b6cd9098f6ba686994f5e043e7181edfc552e18bce42b3a42b63f7ccb7729b74e76a040055d397278cb939240f236d0a2a79757ba7a9f09

for kp in range(3, e):
    p_mul = dp * e - 1
    if p_mul % kp == 0:
        p = (p_mul // kp) + 1
        if isPrime(p):
            print(f"Possible p: {p}")

後面就是跑驗證確認,就被打出來了...