日本郵政的 CSV 資料

看到「Parsing the Infamous Japanese Postal CSV」這篇在抱怨日本郵政提供的 CSV 資料超級糟糕的問題覺得頗「有趣」的,在 Hacker News 上也有人「同病相憐」XDDD:「Parsing the Infamous Japanese Postal CSV (dampfkraft.com)」。

文章作者是「posuto」這個套件的維護人,這個套件讓開發者可以很方便的在 Python 下從郵遞區號推出對應的地點資訊:

import posuto as 〒

🗼 = 〒.get('〒105-0011')

print(🗼)
# "東京都港区芝公園"
print(🗼.prefecture)
# "東京都"
print(🗼.kana)
# "トウキョウトミナトクシバコウエン"
print(🗼.romaji)
# "Tokyo To, Minato Ku, Shibakoen"
print(🗼.note)
# None

作者建立的資料是從「読み仮名データの促音・拗音を小書きで表記するもの(zip形式)」這邊取得並且分析,然後這篇文章就是在描述這些 CSV 檔的資料裡面有超級多奇怪的例外,用機器讀取超哭爸的 XDDD (好像不怎麼意外?)

不過最有趣的應該還是他提到的這個:

Oh, and if you need a Win3.1 or DOS program to copy the data onto an IBM H floppy disk, just check the bottom of JP Post's page - they've got you covered.

看起來是頁面下方的這塊:

這就真的太哭爸了啊 XDDD

Google 與 AWS 都釋出往 OpenTelemetry 靠攏的消息

前幾天看到 GoogleAWS 都釋出往 OpenTelemetry 靠攏的消息:「OpenTelemetry's First Release Candidates」以及「Public Preview – AWS Distro for OpenTelemetry」。

AWS 這邊的 AWS X-Ray 看起來跟 OpenTelemetry 有點關係,找了一下果然發現之前有些計畫在跑:「AWS X-Ray SDK w/ OpenTelemetry API」,不過看起來後續應該是由「AWS Distro for OpenTelemetry」這個計畫接手了。

另外 Google 這邊看起來則是 Cloud Trace 這個產品線,本來在推的 OpenCensusOpenTracing 從網站上可以看到決定會再支援兩年,但重心會改放到 OpenTelemetry 上:

OpenCensus and OpenTracing have merged to form OpenTelemetry, which serves as the next major version of OpenCensus and OpenTracing. OpenTelemetry will offer backwards compatibility with existing OpenCensus integrations, and we will continue to make security patches to existing OpenCensus libraries for two years.

翻了一下 Azure 相關的消息,先前有一些稿子是會往 OpenTelemetry 支援,但這一波沒看到新聞稿...

DuckDB

看到篇有趣的介紹,在講 DuckDB:「DuckDB」。

[I]t uses the PostgreSQL parser but models itself after SQLite in that databases are a single file and the code is designed for use as an embedded library, distributed in a single amalgamation C++ file (SQLite uses a C amalgamation).

看起來是個以 OLAP 為中心而設計出來的資料庫,然後在 Python 下可以直接透過 pip 裝起來。

看起來像是個用單機拼 throughput 的東西,但提供大家熟悉的界面。

Hacker News 上可以看到「DuckDB – An embeddable SQL database like SQLite, but supports Postgres features (duckdb.org)」這邊給了不少方向,

新的 TLS 攻擊:Raccoon Attack

這次看到的是針對 TLS 實做上的問題產生的 Raccoon Attack,反正先取個名字就對了,原圖有點大張,設個 medium size 好了 XDDD:

Why is the attack called "Raccoon"?
Raccoon is not an acronym. Raccoons are just cute animals, and it is well past time that an attack will be named after them :)

先講影響的產品,首先是經常中槍的 F5,這次連 timing measurement 都不需要太準確就可以打穿:

In particular, several F5 products allow executing a special version of the attack, without the need for precise timing measurements.

OpenSSL 的部份因為從 1.0.2f 之後因為其他的 security issue 所以改善了實做方式,就不會受到這次的攻擊手法影響。

剛剛翻了一下 Ubuntu 上的的資料,看起來 16.04 (xenial) 上的 OpenSSL 就已經是 1.0.2g 了,所以目前只要是有在 Ubuntu 支援的版本應該都不受影響:

OpenSSL assigned the issue CVE-2020-1968. OpenSSL does use fresh DH keys per default since version 1.0.2f (which made SSL_OP_SINGLE_DH_USE default as a response to CVE-2016-0701).

Firefox 直接拔了 DH 與 DHE 相關的 cipher suite,反正在這次攻擊手法出來前本來就已經計畫要拔掉:

Mozilla assigned the issue CVE-2020-12413. It has been solved by disabling DH and DHE cipher suites in Firefox (which was already planned before the Raccoon disclosure).

微軟的部份則是推更新出來:

Microsoft assigned the issue CVE-2020-1596. Please refer to the Microsoft Security Response Center portal.

回到攻擊手法,這次的問題是因為 DH 相關的實做造成的問題。

TLS 要求去掉 premaster secret 裡開頭的 0,造成會因為開頭的 0 數量不同而實做上就不會是 constant time,所以有了一些 side channel information 可以用:

Our Raccoon attack exploits a TLS specification side channel; TLS 1.2 (and all previous versions) prescribes that all leading zero bytes in the premaster secret are stripped before used in further computations. Since the resulting premaster secret is used as an input into the key derivation function, which is based on hash functions with different timing profiles, precise timing measurements may enable an attacker to construct an oracle from a TLS server.

然後一層一層堆,能夠知道 premaster secret 開頭是不是 0 之後,接下來因為 server side 會重複使用同一組 premaster secret,所以可以當作一個 oracle,試著去計算出更後面的位數:

This oracle tells the attacker whether a computed premaster secret starts with zero or not. For example, the attacker could eavesdrop ga sent by the client, resend it to the server, and determine whether the resulting premaster secret starts with zero or not.

Learning one byte from a premaster secret would not help the attacker much. However, here the attack gets interesting. Imagine the attacker intercepted a ClientKeyExchange message containing the value ga. The attacker can now construct values related to ga and send them to the server in distinct TLS handshakes. More concretely, the attacker constructs values gri*ga, which lead to premaster secrets gri*b*gab. Based on the server timing behavior, the attacker can find values leading to premaster secrets starting with zero. In the end, this helps the attacker to construct a set of equations and use a solver for the Hidden Number Problem (HNP) to compute the original premaster secret established between the client and the server.

所以針對這個攻擊手法的解法就是用「新鮮的」premaster secret (像是完全不重複使用),然後保留開頭的 0,不需要去掉。而 TLS 1.3 在定義的時候把這兩件事情都做了,所以不會受到影響:

Is TLS 1.3 also affected?
No. In TLS 1.3, the leading zero bytes are preserved for DHE cipher suites (as well as for ECDHE ones) and keys should not be reused.

另外在這邊提到的 Hidden Number Problem (HNP) 也是個不熟悉的詞彙,網站上有提到論文,也就是「Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes」這篇:

Given an oracle Oα(x) that on input x computes the k most significant bits of (α * gx mod p) , find α mod p.

是個離散對數類的問題,之後有空再來翻一翻好了。

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 雖然大,但其他幾家的支援度應該也是重點...

cURL 支援 Zstandard

在「curl 7.72.0 – more compression」這邊看到新版的 cURL 要支援 Zstandard 了,查了一下發現 Zstandard 有對應的 RFC,在 RFC 8478:「Zstandard Compression and the application/zstd Media Type」。

對應到 server 端的部份,看起來可以用 tokers/zstd-nginx-module 搭 (在 nginx 環境下),不然就是 application 端要自己壓縮了。

不過普及率比較高的演算法是 Google 主導的 Brotli,查了一下壓縮率大概在同一個等級。

Facebook 沒有自家瀏覽器,推這些東西比較辛苦一點,但這次 cURL 決定支援 Zstandard 算是一個開始,讓開發者多了一個選擇可以用...

KataGo 最近的進展

KataGo 是目前 open source 裡最強的計算引擎了,不過先前的缺點就是得透過 OpenCL 或是 CUDA 才能跑,所以基本上得有張夠力的顯示卡才行。

如果要想要在 CPU 上跑 (不透過硬體顯示卡),一種方式是透過 OpenCL 的方式模擬,在 Linux 下可以透過 pocl 達成,效能就普普通通,但算是會動的東西,不過 Windows 下好像不太好弄... 這也是先前蠻多人還是繼續使用 Leela Zero 的原因。

最近 KataGo 在 1.5 版實做了純 CPU 版本的程式碼,是透過 Eigen 這套 library 達成的,不過大家測過以後發現慢到爆炸 XDDD

因為作者沒有提供 CPU 版本的 binary,我自己在 Linux 下抓程式碼 compile 後測試發現只會用一個 CPU (沒有 multi threading),對比於在 1080Ti 上跑 OpenCL 版本大約 150 visits/sec (40b),但 CPU 版本是 0.0x visits/sec 啊 XDDD

作者自己在 GitHub 上討論時也有提到這個版本只有確認正確性,完全沒有考慮效能...

不過就有其他人跳出來改善了,在「Optimization of Eigen backend #288」這邊可以看到 kaorahi 拋出了不少修改,可以看到從一開始的 eigen_naive_loop (對比 1.5 版有 13x 的成長) 一路到 borrow_tensorflow (1400x) 的版本,使得在 CPU 上面跑 15b 也有 10 visits/sec 了:

"borrow_tensorflow" version: x1400 speed up from 1.5.0 (70% of libtensorflow backend). Now 15b net is usable for me. I get 19 visits/s in benchmark and 10 visits/s in GUI with 15b net.

這樣看起來已經快了不少,這樣子 Leela Zero 應該會逐漸淡出了,CPU-only 算是最後一塊 Leela Zero 還可以爭的地盤...

GPU.js

前幾天在 Hacker News Daily 上看到的專案:「GPU.js - GPU accelerated JavaScript」,對應的 GitHub 頁面在 gpujs/gpu.js 這邊。

看起來是用 WebGL 接進去的,不過他用來 benchmark 的硬體頗暴力啊:

Hardware: Xeon Gold 5217 + 8 x RTX 2080ti

這邊用了八張 2080Ti,如果一張就大約是 1/8 效能的話,看起來好像還好... 一張 2080Ti 跟 Xeon Gold 5217 跑出來差不多?價錢也在同一個範圍區間...

暫時不知道用途...

莎士比亞風格的 UUID

UUID 是個長 128 bits 的數字,轉成 16 進位也有 32 個字要記,對於人類記憶來說不太友善。

前幾天在 Hacker News 上看到的東西,把這 128 bits 的資訊轉成類莎士比亞的句子,相比前面 32 個 16 進位的數字來說好記不少:「uuid-readable」。

Generate Easy to Remember, Readable UUIDs, that are Shakespearean and Grammatically Correct Sentences

給的輸出範例包括了:

Loren Chariot Addy the Titbit of Cholame questioned Cele Garth Alda and 16 windy frogs

Drucill Hubert Lewse the Comer of Avera rejoices Fiann Craggy Florie and 5 hard trouts

Jacquette Brandt John the Pectus of Barnsdall doubted Glenn Gay Gregg and 12 noisy stoats

我不覺得有變簡單啊 XDDD 也許對於英文母語的人來說會簡單一些... 吧?

Mass Effect 的 3D 場景黑塊問題一路追到 Intel/AMD 的 SSE2 指令集...

Mass Effect 是個 2007 在 Xbox 上推出的遊戲,並且在 2008 推出 Windows 版,這個遊戲在 2011 年 AMD 推出的 CPU 上 (Bulldozer),某些場景會產生人物黑塊的 bug,社群有些猜測但一直都沒被證實,作者一路追出不少問題,並且給了一個還算乾淨的 workaround:「Fixing Mass Effect black blobs on modern AMD CPUs」,另外在 Hacker News 上有很精彩的討論:「Fixing Mass Effect black blobs on modern AMD CPUs (cookieplmonster.github.io)」。

這篇主要是看趣味的,裡面的狀況有點複雜。

社群有一些 workaround 可以避開這個問題,作者後來是從關閉 PSGP (Processor Specific Graphics Pipeline) 的方法找問題,然後發現在計算時會產生出 NaN 的問題,所以導致貼出來的圖就變成黑塊了...

一路追下去,發現遊戲本身好像沒什麼大問題,但跟 Direct3D 裡面的 D3DXMatrixInverse 有關,會依照 CPU 的支援度決定怎麼跑:

  • Disabling PSGP makes both Intel and AMD take a regular x86 code path.
  • Intel CPUs always take an intelsse2 code path.
  • AMD CPUs supporting 3DNow! take a amd_mmx_3dnow or amd3dnow_amdmmx code path, while CPUs without 3DNow take an intelsse2 code path.

會有這些邏輯是因為 AMD 在 2010 後決定放生 3DNow!,所以會需要這樣判斷。

接著寫了一隻小程式測試,用 memcmp() 判斷是不是一樣,結果發現 AMD 的 SSE2 跑出來的程式不被遊戲接受:(不一樣是正常的,因為這些指令本來就沒有要求完全正確,是可以接受誤差的)

接著就是翻資料,可以知道 XMMatrixInverse 算是接班人:

I figured that since we were to replace that matrix function anyway, I could try replacing it with XMMatrixInverse being a “modern” replacement for D3DXMatrixInverse. XMMatrixInverse also uses SSE2 instructions so it should be equally optimal to the D3DX function, but I was nearly sure it would break the same way.

所以就弄個一個 DLL,把本來呼叫 D3DXMatrixInverse 的部份用 XMMatrixInverse 改寫換掉:「SilentPatchME/source/D3DXMatrix.cpp」,這個方式算是乾淨的 workaround 掉,保持 API 相容性,以及該有的加速能力 (由 XMMatrixInverse 提供)。

Hacker News 上有討論到 Intel 與 AMD 這些指令在 SSE2 上的誤差值,都是在規格要求的範圍內:

Const-me 14 hours ago [–]

Here’s Intel versus AMD relative error of RCPPS instruction: http://const.me/tmp/vrcpps-errors-chart.png AMD is Ryzen 5 3600, Intel is Core i3 6157U.
Over the complete range of floats, AMD is more precise on average, 0.000078 versus 0.000095 relative error. However, Intel has 0.000300 maximum relative error, AMD 0.000315.

Both are well within the spec. The documentation says “maximum relative error for this approximation is less than 1.5*2^-12”, in human language that would be 3.6621E-4.

Source code that compares them by creating 16GB binary files with the complete range of floats: https://gist.github.com/Const-me/a6d36f70a3a77de00c61cf4f6c17c7ac

至於為什麼會生出 NaN 的原因,沒找出來還是有點可惜,不過這個解法還行,就是「新版的 library 既然沒問題,就大家也不要太計較舊版的問題」的概念...