hashcat v3.00

hashcat 是個用暴力法拿來計算各種 reverse hash 的的工具,也就是對於 HASH(key) = value 時,給 value 的值,要求得出 key 的值 (被稱為 Preimage attack)。

雖然是暴力法,但還是花了很多力氣加速,尤其在這個 GPU 已經很常見的年代,這套軟體也支援透過 GPU 加速運算。

先前的版本是 CPU 與 GPU 分開兩個版本可以用 (CPU 版本的叫 hashcat,GPU 版本的叫做 oclHashcat),而 GPU 的版本只支援 nVidiaAMD 兩家大廠的顯卡。

而在 v3.00 版,透過 OpenCL 的界面將這些全部都合而為一了:「hashcat v3.00」,所以不只是支援 CPU 與 nVidia + AMD 的 GPU,還包括了:

  • GPU
  • CPU
  • APU
  • DSP
  • FPGA
  • Coprocessor
  • Anything else which comes with an OpenCL runtime

也特別提到,Intel CPU 上內建的 GPU 部份也可以拿來用了:

For example, Intel CPUs will now instantly pop up as an available OpenCL device after you've installed the Intel OpenCL runtime.

也因為透過 OpenCL,如果有多種不同類型的加速方式,新版 hashcat 也可以同時使用。

另外這次效能評估 (與舊版比較) 也做出來了:「hashcat 2.01 / 3.00 performance comparison」,可以看到比較新一點的卡整體都有進步,而舊的卡有可能是對 OpenCL 的最佳化或是 overhead 比較敏感,慢了不少...

自適應演算法與 A/B Testing

Hacker News Daily 上看到三年前的舊文章,講自適應演算法取代常見的 A/B testing:「20 lines of code that will beat A/B testing every time」。

就拿原文裡面的例子來說明,我想要測試 "Buy Now!" 這個按鈕的顏色來得知哪個顏色的 click rate 最高,而我有 Orange、Green 以及 White 三種顏色為候選。

一開始我初始值都設為「展示了 1 次,被點擊了 1 次」,所以每個點擊率都是 100%:

Orange Green White
1/1 = 100% 1/1=100% 1/1=100%

然後你的網站上只要展示「點擊率最高的那個顏色」,並且記錄下來展示次數與點擊率就好,而整個過程會是自適應而被自動被淘汰掉,最後可能會變成這樣,就會固定是綠色的了:

Orange Green White
114/4071 = 2.8% 205/6385=3.2% 59/2264=2.6%

而這樣做的好處是節省人力成本:你不需要 A/B Testing 完後再人工介入修改。

對於更複雜的例子,雖然原文沒有提到,但你可以直接展開來做,舉例來說,你假設顏色與地區兩個變數所帶出來的 click rate 不是 i.i.d.,那麼你可以針對每個 Color + Region 都存數值去比較。

當然還是有他的問題 (comment 有提到),不過可以架出一些全自動的 workaround 來解決,比起要兩階段人工介入省了不少人力。

另外可以想像在大的產品上會遇到效能問題 (因為對同樣資料大量的 read + write),但這個數字不需要太即時,只要量大就會準確,所以技術上也可以解決...

密碼系統的 Monoculture

這篇文章講到最近密碼系統的現象:「On the Impending Crypto Monoculture」。

目前常在用的密碼系統包括了 RSA、DH、ECDH、ECDSA、SHA-2、AES 這些演算法,而最近這幾年大家在推廣使用的演算法都出自於同一個人手裡,Dan Bernstein,也就是 djb:

A major feature of these changes includes the dropping of traditional encryption algorithms and mechanisms like RSA, DH, ECDH/ECDSA, SHA-2, and AES, for a completely different set of mechanisms, including Curve25519 (designed by Dan Bernstein et al), EdDSA (Bernstein and colleagues), Poly1305 (Bernstein again) and ChaCha20 (by, you guessed it, Bernstein).

這些演算法或是定義,包括了 Curve25519、EdDSA、Poly1305、ChaCha20。而這篇文章試著說明造成這樣情況的背景以及原因,以及這樣會導致什麼問題。

當實際分析時會發現,檯面上沒幾個能用的演算法,而看起來能用的那幾個又有專利 (像是 OCB),不然就是看起來被 NSA 放了一些說明不了的參數 (像是 P-256 Curve)。

然後 djb 弄出來的演算法不只看起來乾淨許多,也直接用數學模型證明安全性。而且他的實作也很理論派,像是還蠻堅持要做到 constant time implementation 以避開各種 side channel attack。

就... 理論很強,又很實戰派的一個人啊,檯面上真的沒幾隻可以打的贏啊 XD

Go 1.6 把 HTTP/2 變成預設支援的功能

Go 的官方公告「Go 1.6 is released」提到了把 net/http 的 HTTP/2 預設啟用了:

In Go 1.6, support for HTTP/2 is enabled by default for both servers and clients when using HTTPS, bringing the benefits of the new protocol to a wide range of Go projects, such as the popular Caddy web server.

另外值得一提的是 sort 演算法的效能改善:

The algorithm inside sort.Sort was improved to run about 10% faster, but the change may break programs that expect a specific ordering of equal but distinguishable elements.

這應該算還蠻基本常用到的東西,會改善很多程式效能...

Google 推出 Brotli 無損壓縮法

Google 推出了 Brotli 這個無損壓縮法:「Introducing Brotli: a new compression algorithm for the internet」。

Google 推出的 Zopfli 相容於 DEFLATE 的超慢壓縮演算法,但可以多壓榨出 3%~8% 的壓縮率。而 Brotli 則是重新設計,壓縮與解壓縮速度跟 DEFLATE 差不多,但壓縮率比 Zopfli 多了 20%~26%。

This new format allows us to get 20–26% higher compression ratios over Zopfli. In our study ‘Comparison of Brotli, Deflate, Zopfli, LZMA, LZHAM and Bzip2 Compression Algorithms’ we show that Brotli is roughly as fast as zlib’s Deflate implementation.

由於目標是希望讓瀏覽器支援新的壓縮法,Google 把 Brotli 往 RFC 提案,試著變成公開標準:「Brotli Compressed Data Format」。

看了看 commit log,看起來已經開發一陣子了...

Mike Bostock 的 Visualizing Algorithms

Mike Bostock (D3.js 的創始人之一) 在 Eyeo 2014 上展現了要如何將演算法視覺化表現出來:「Visualizing Algorithms」。

既然是對演算法的展示,當然也都伴隨著對資料的處理。每一個圖形表示都有 D3.js 的 sample code 告訴你怎麼產生的。

與其他看到的 D3.js 範例不同,他給出來的範例可以感覺到「樸實無華」的壓迫感。文章開頭用梵谷「隆河上的星夜」也很配合整篇文章的風格。

有玩 D3.js 或是對資料視覺化的人有興趣或是有研究的人都應該去看他怎麼表現「動作」(演算法) 的部份。

Small Characteristic DLP (Discrete Log Problem) 被解決

最近幾天在密碼學領域還蠻紅的話題 (雖然預印本在去年就發了),EUROCRYPT 2014 上發表對 DLP (Discrete Log Problem) 的重大進展。

論文在 arXiv 上可以取得:「A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic」。

針對使用小特徵值的有限域 (finite field) 的 DLP 問題 (也就是 Zqk 上) 直接從 sub-exponential 降到 nO(logn) (quasi-polynomial)。最常見到的應該是 Z2n

雖然現有被廣泛使用的密碼系統在使用 DLP 建構時都是用 Zp,但這次的成果絕對寫下了 DLP cryptoanalysis 上的里程碑...

Linux kernel 內的資料結構與演算法...

Theoretical Computer Science Stack Exchange 上,有人問到有沒有哪些軟硬體的 source code 是可以跟學生說明某些經典演算法的重要性:「Core algorithms deployed」。

下面就有人列了 Linux kernel 內的演算法,以及對應的程式碼。相當長的一份列表...

除了 Linux kernel 外,也還有其他大型 open source 專案用到的資料結構與演算法...

不過看到 Bubble sort 是怎樣呢... XD

微軟將在 2016 年會拒絕 SHA-1 的 SSL 安全憑證...

微軟公告將在 2016 年拒絕只有 SHA-1 的 SSL Certificate:「Security Advisory 2880823: Recommendation to discontinue use of SHA-1」。微軟的力量主要是對 IE 瀏覽器的控制。

可以看到文章裡把 MD5 的歷史也拿出來比較,然後對照到 SHA-1,所以宣佈 2016 年後就不吃只有 SHA-1 的 SSL Certificate

比較新的簽章都包含了比較強的 cryptographic hash algorithm,像是 SHA-256 的:

現在差不多 2013 年年底,所以大約還有兩年的時間...

SHA-3 的歷史由來...

Bruce Schneier 的 blog 上看到 SHA-3 的由來:「SHA-3 Status」,而投影片在「Keccak and the SHA-3 Standardization」這裡,裡面有不少資料可以用...

像是 crypto hash function 速度的比較:

後半段看到蠻多有趣的東西,等有空回頭來看...