Tag: hash

SHA-1 的 chosen-prefix collision 低於 2^64 了...

算是前陣子的大消息，SHA-1 的 chosen-prefix collision 需要的運算已經低於 2^64 了：「SHA-1 is a Shambles」。

基本的 collision 指的是演算法找出 p1 與 p2 兩個字串，使得 hash(p1) == hash(p2)。但這個方法對於實際的攻擊價值並不大，因為 p1 與 p2 是透過演算法找出來 collision，都是亂數字串。

chosen-prefix collision 指的是先給定 p1 與 p2 (在實際攻擊中，兩組都會是有意義的字串)，然後攻擊的演算法可以算出 m1 與 m2，使得 hash(p1 // m1) == hash(p2 // m2)，其中的 // 就是字串加法。這樣的是先產生出有意義的字串，於是就可以在真實世界中使用。

舉例來說，我先產生出 blog.gslin.org 的 SSL certificate，然後再產生出一個 github.com 的 SSL certificate，這兩個分別就是 p1 與 p2。

接下來演算法算出 m1 與 m2，使得 hash(p1 // m1) 與 hash(p2 // m2) 相同。

接著，我就可以拿 p1 // m1 給 CA 簽名 (因為我有 blog.gslin.org 的擁有權)，而拿到的憑證因為 hash 值相同，就可以給 github.com 這組用。

2008 年的時候就用這個方法生出一個 sub-CA：

In 2008, researchers used a chosen-prefix collision attack against MD5 using this scenario, to produce a rogue certificate authority certificate. They created two versions of a TLS public key certificate, one of which appeared legitimate and was submitted for signing by the RapidSSL certificate authority. The second version, which had the same MD5 hash, contained flags which signal web browsers to accept it as a legitimate authority for issuing arbitrary other certificates.[14]

另外，如果跟 2017 年由 Google 與 CWI 打出來的 SHAttered 比較，當時的攻擊是 identicial-prefix，實際上的用途沒那麼大，這次是 chosen-prefix，就有很強的實際用途了。

所以這次的攻擊給了幾個重要的事情。

第一個是 SHA-1 的 chosen-prefix collision attack 運算已經降到 2^64 以下了，然後加上：

第二個是 2^64 的運算成本已經低於 USD$100k 了，作者是使用 GPUserversrental 這個租用 GPU 的服務跑出這次的運算，而這也表示攻擊安全層級是 2^64 的密碼系統，成本也是 USD$100k 了。

地球上還是有不少系統使用 SHA-1 (作者在網站上有提到)，看起來這陣子會有不少修正...

iOS 13 與 macOS 10.15 對憑證的限制

在 Slack 上看到同事丟出來的，關於之後要推出的 iOS 13 與 macOS 10.15 會對憑證限制的項目：「Requirements for trusted certificates in iOS 13 and macOS 10.15」。

主要是把不安全的演算法淘汰掉 (RSA 小於 2048 bits，以及 SHA-1 類的 hash algorithm)，這兩個部份相關的新聞應該不少，沒有什麼太大問題：

TLS server certificates and issuing CAs using RSA keys must use key sizes greater than or equal to 2048 bits. Certificates using RSA key sizes smaller than 2048 bits are no longer trusted for TLS.

TLS server certificates and issuing CAs must use a hash algorithm from the SHA-2 family in the signature algorithm. SHA-1 signed certificates are no longer trusted for TLS.

然後是要求憑證使用 SAN (Subject Alternative Name)，舊的標準 CN (CommonName) 將不會再被信任。

如果是公開簽發的憑證應該都沒問題 (像是 Let's Encrypt，或是花錢買的那些)，主要的問題應該會出現在自己建立的憑證，網路上蠻多舊資料還是產生 CN...

TLS server certificates must present the DNS name of the server in the Subject Alternative Name extension of the certificate. DNS names in the CommonName of a certificate are no longer trusted.

另外是 2019/7/1 之後發出的憑證，有額外兩個規範要注意，第一個是強制要透過 EKU 指定 id-kp-serverAuth，這是出自 RFC 5280：

   id-kp-serverAuth             OBJECT IDENTIFIER ::= { id-kp 1 }
   -- TLS WWW server authentication
   -- Key usage bits that may be consistent: digitalSignature,
   -- keyEncipherment or keyAgreement

TLS server certificates must contain an ExtendedKeyUsage (EKU) extension containing the id-kp-serverAuth OID.

再來是時間的限制，接下來的憑證最長只認得 825 天 (大約 27 個月多一些)，以前都惡搞 -days 3650，現在得兩年簽一次了：

TLS server certificates must have a validity period of 825 days or fewer (as expressed in the NotBefore and NotAfter fields of the certificate).

整體看起來主要是影響自己簽的部份...

改 Open Distro for Elasticsearch 預設密碼的方式

AWS 弄出來的 Open Distro for Elasticsearch 因為內建了安全性的功能 (參考「AWS 對 Elastic Stack 實作免費的開源版本 Open Distro for Elasticsearch」)，應該是目前新架設 Elasticsearch 的首選。

不過裝好後預設有五個帳號，但從 Open Distro 的 Kibana 介面無法修改改其中兩個使用者的密碼 (admin 與 kibanaserver)，要修改密碼發現得花不少功夫，不知道為什麼要這樣設計 :/

這邊講的是透過 RPM (以及 deb) 的方式的修改方式，如果是 Docker 的方式請參考後面提到在 AWS blog 上的文章：「Change your Admin Passwords in Open Distro for Elasticsearch」。

首先先透過 hash.sh 產生 bcrypt 的 hash，像是這樣 (輸入 password 當密碼)：

bash /usr/share/elasticsearch/plugins/opendistro_security/tools/hash.sh
WARNING: JAVA_HOME not set, will use /usr/bin/java
[Password:]
$2y$12$QchkpgY8y/.0TL7wruWq4egBDrlpIaURiBYKoZD50G/twdylgwuhG

然後修改 /usr/share/elasticsearch/plugins/opendistro_security/securityconfig/internal_users.yml 檔案裡面的值，順便改掉 readonly 的部分。

接下來是把這個 internal_users.yml 檔案的設定更新到 Elasticsearch 裡。由於這邊需要讀 /etc/elasticsearch/ 的東西，所以偷懶用 root 跑：

sudo bash /usr/share/elasticsearch/plugins/opendistro_security/tools/securityadmin.sh -cd ../securityconfig/ -icl -nhnv -cacert /etc/elasticsearch/root-ca.pem -cert /etc/elasticsearch/kirk.pem -key /etc/elasticsearch/kirk-key.pem

做完後可能要重跑 Elasticsearch 與 Kibana：

sudo service elasticsearch restart
sudo service kibana restart

或是重開機... 順便測試看看重開後有沒有生效。理論上修改完成後，就是用新的帳號密碼連到 Kibana。

上面的方法是參考了「Default Password Reset」(先找到這篇) 與「change admin password」(後來在 AWS blog 的文章上發現的 GitHub issue 連結) 這邊的資訊。

官方的說明文件則是在寫這篇文章時才找到的，平常搜尋時不太會出現：「Apply configuration changes」。

實際比較 Linode 的 Dedicated 主機與 AWS 的 c5.*

先前有提到 Linode 出了 Dedicated 主機：「Linode 推出 Dedicated CPU Instances」，現在找機會測試看看，拿了 Linode 的 Dedicated (4GB) 與 AWS 的 c5.large 比較，同樣都是 2 vCPU 與 4GB RAM。

這邊用了 n-st/nench 與 OpenSSL 的 speed (包括了 aes、md5、rsa、sha1 與 sha256) 測試，我把結果都貼到這邊：「Linode (Dedicated 4GB) v.s. AWS (c5.large)」。

可以看到在 CPU 方面主要的差異是 Linode 用的是 AMD，而 AWS 用的是 Intel，所以就會有蠻多不同的數字表現...

如果仔細看 OpenSSL 的測試數據，可以看到不同演算法的差異還蠻大的，馬上可以想到的應該是硬體加速方式與 cache 架構差異造成的：

  • 在 cipher 類的測試我只測了 AES (目前的主流)，小的 block (16/64/256 bytes) 時 AMD 會輸一些，但大的 block (1024/8192/16384 bytes) 反而會贏不少。
  • 在 hash 類的測試中，跑 MD5 時 Linode 則是輸一些，但 SHA1 反而是贏一些，然後 SHA256 時效能好到爆炸贏了一倍 XDDD
  • 在 public key 類的測試我測了 RSA，則是 Linode 輸的蠻慘的...

如果考慮到價位大約只有 AWS 的一半，應該是還不錯...

Amazon S3 提供更高的存取量...

AWS 宣佈提高了 Amazon S3 的效能：「Amazon S3 Announces Increased Request Rate Performance」。

每個 S3 prefix 都可以到 5500 RPS read 與 3500 RPS write：

Amazon S3 now provides increased performance to support up to 3,500 requests per second to add data and 5,500 requests per second to retrieve data, which can save significant processing time for no additional charge. Each S3 prefix can support these request rates, making it simple to increase performance exponentially.

舊的資料可以看「Request Rate and Performance Considerations」這邊，裡面沒有明講速度，但有提到如果超過 800 RPS read 與 300 RPS write 的門檻，建議開 case：

However, if you expect a rapid increase in the request rate for a bucket to more than 300 PUT/LIST/DELETE requests per second or more than 800 GET requests per second, we recommend that you open a support case to prepare for the workload and avoid any temporary limits on your request rate.

不過如果有量的話，還是建議照著原來的 prefix 建議，打散處理會比較好，通常在前面的 CDN 通常可以跑簡單的 url rewrite 處理掉 (像是 CloudFront 自家或是 Cloudflare)，像是把使用 unix timestamp (ms) 的 https://www.example.com/1531843366123.jpg 變成 https://www.example.com/6123/1531843366123.jpg，這樣可以讓 Amazon S3 的後端依照 prefix 打散 loading，避免當站愈來愈大的時候很難處理。

Twitter 密碼中槍...

Twitter 發了公告請大家改密碼：「Keeping your account secure」。不只是 Twitter 自家的密碼，如果你有重複使用同一組密碼，也建議一起修改：

Out of an abundance of caution, we ask that you consider changing your password on all services where you’ve used this password.

雖然使用 bcrypt，但因為透過 log 記錄下了未加密的密碼，所以就中槍了：

We mask passwords through a process called hashing using a function known as bcrypt, which replaces the actual password with a random set of numbers and letters that are stored in Twitter’s system. This allows our systems to validate your account credentials without revealing your password. This is an industry standard.

Due to a bug, passwords were written to an internal log before completing the hashing process. We found this error ourselves, removed the passwords, and are implementing plans to prevent this bug from happening again.

這時候就要再推 Password manager 這種東西了，在每個站台都使用完全不同的密碼，可以降低這類問題帶來的衝擊...

Ethereum Smart Contracts 裡的 PRNG

現代密碼學的安全性有很大一塊是基於亂數產生器 (RNG) 非常難被預測。如果這個前提不成立的話，利用亂數產生器產生出來的各種資訊都會被預測出來 (尤其是 Private Key)。

但真正的 RNG 需要靠硬體支援，而且產生速度很慢，一般都會使用 PRNG (Pseudorandom number generator) 產生。也就是「看起來」很亂的亂數產生器。

PRNG 通常是指在統計學上通過許多測試，像是在多種測試都是 Discrete uniform distribution，不需要防止有惡意人，可以從產生出的 PRNG 的值而推導出後續結果的用途。

在「Predicting Random Numbers in Ethereum Smart Contracts」這篇裡面，作者列出了一堆實做 Ethereum Smart Contracts 卻誤用 PRNG 的行為。

文章裡提到的問題都是因為 PRNG 拿著可被預測的資訊當作 entropy source (e.g. seed)，而且提出來的範例都是拿 block 本身或衍生的資訊 (像是 block 的 hash) 來用：

  • PRNGs using block variables as a source of entropy
  • PRNGs based on a blockhash of some past block
  • PRNGs based on a blockhash of a past block combined with a seed deemed private
  • PRNGs prone to front-running

然後列了大量的程式碼當例子，建議有需要接觸的人看過一次，或是有時間的人都值得看這些負面範例... XDDD

不過作者在文章裡面也給了一堆有問題的方法，像是從外部網站取得亂數之類的 XDDD

正確的方法是使用 CSPRNG (Cryptographically secure pseudorandom number generator)，這是專門設計給密碼學用的 PRNG。

CSPRNG 有幾種方法可以取得：

  • 在大多數的程式語言內都有對應的 library 可以用，另外在比較近代的瀏覽器內 (如果問 IE 的話，是 11+)，可以透過 RandomSource.getRandomValues() 得到。
  • 如果打算自己搞底層而需要直接取得 CSPRNG 的產出，在 Unix-like 的環境下可以透過 /dev/urandom 取得，在 Microsoft Windows 下則可以透過 CryptGenRandom 取得。

別學作者那邊奇怪方法啊 XDDD

兩個 gperf...

翻資料的時候覺得怎麼跟印象中的不太一樣，多花些時間翻了一下，發現原來有兩個東西同名...

一個是 GNU 的 gperf，給定字串集合，產生 C 或 C++ 的 perfect hash function (i.e. no collision)：

GNU gperf is a perfect hash function generator. For a given list of strings, it produces a hash function and hash table, in form of C or C++ code, for looking up a value depending on the input string. The hash function is perfect, which means that the hash table has no collisions, and the hash table lookup needs a single string comparison only.

另外一個是 Google 弄出來的 gperftools，malloc() 的替代品以及效能分析工具：

gperftools is a collection of a high-performance multi-threaded malloc() implementation, plus some pretty nifty performance analysis tools.

Etsy 介紹的 Cache Smearing

在 Etsy 的 engineering blog 上提到了他們怎麼設計 cache 機制：「How Etsy caches: hashing, Ketama, and cache smearing」。

使用 consistent hash 已經是基本款了，文章裡花了一些篇幅介紹為什麼要用 consistent hash。

後半段則是有了 consistent hash 後會遇到的問題，也就是講 hot key 怎麼處理：有些資料非常熱 (常常被存取)，就算用 consistent hash 也還是有可能搞爆單一機器。

他們做了幾件事情，第一件事情是設計 cache smearing 機制，把單一資料加上 random key，使得不同的 key 會打散到不同的機器上：

Let’s take an example of a hot key popular_user_data. This key is read often (since the user is popular) and is hashed to pool member 3. Cache smearing appends a random number in a small range (say, [0, 8)) to the key before each read or write. For instance, successive reads might look up popular_user_data3, popular_user_data1, and popular_user_data6. Because the keys are different, they will be hashed to different hosts. One or more may still be on pool member 3, but not all of them will be, sharing the load among the pool.

第二件事情則是監控哪些 key 比較熱門：

We’ve seen this problem many times over the years, using mctop, memkeys, and our distributed tracing tools to track down hot keys.

第三件事情是維護 hot key 的清單 (不是每個 key 都會上 cache smearing)：

We manually add cache smearing to only our hottest keys, leaving keys that are less read-heavy efficiently stored on a single host.

是個當規模大到單一 hot key 會讓單台伺服器撐不住時的 workaround...

下一代的 Tor Hidden Service

Tor 公佈了下一代的 Hidden Service (Onion Service)：「Tor's Fall Harvest: the Next Generation of Onion Services」。

三年前 Facebook 自己暴力算出 facebookcorewwwi.onion 這個很特別的名字 (參考「Facebook 證明 Tor 的 Hidden Service 不安全」)，這陣子連紐約時報也能暴力算出 nytimes3xbfgragh.onion 這個好名字 (參考「紐約時報網站上 Tor 的 Hidden Service (i.e. Tor Onion Service)」，這讓只有 16 chars 的 hostname 的 hashed-space 不夠大的問題愈來愈明顯 (只有 80 bits 的空間)。

如果你也想要找出一個有趣的 hostname 的話，可以用 lachesis/scallion 這樣的工具，這程式用 CPU 產生出 RSA key 後，再用 GPU 算 SHA-1：

The inital RSA key generation is done the CPU. An ivybridge i7 can generate 51 keys per second using a single core. Each key can provide 1 gigahash worth of exponents to mine and a decent CPU can keep up with several GPUs as it is currently implemented.

也因為如此，Facebook 與紐約時報在上線時並不是直接在 Hidden Service 上裸奔，而是上了 HTTPS 作為 workaround，以避免資料外洩。

但這畢竟是 workaround，Tor 的人還是希望協定本身就可以提供一個夠安全的架構，而花了四年多發展出下一代的 Hidden Service，也就是這次提到的成果了。

最大的改變就是 hostname 變長很多了，從本來的 16 chars 變成 56 chars：

And finally from the casuals user's PoV, the only thing that changes is that new onions are bigger, tastier and they now look like this: 7fa6xlti5joarlmkuhjaifa47ukgcwz6tfndgax45ocyn4rixm632jid.onion.

hostname 變長主要是因為把整個 256 bits public key 放進去，可以從 spec 看到：

6. Encoding onion addresses [ONIONADDRESS]

   The onion address of a hidden service includes its identity public key, a
   version field and a basic checksum. All this information is then base32
   encoded as shown below:

     onion_address = base32(PUBKEY | CHECKSUM | VERSION) + ".onion"
     CHECKSUM = H(".onion checksum" | PUBKEY | VERSION)[:2]

     where:
       - PUBKEY is the 32 bytes ed25519 master pubkey of the hidden service.
       - VERSION is an one byte version field (default value '\x03')
       - ".onion checksum" is a constant string
       - CHECKSUM is truncated to two bytes before inserting it in onion_address

  Here are a few example addresses:

       pg6mmjiyjmcrsslvykfwnntlaru7p5svn6y2ymmju6nubxndf4pscryd.onion
       sp3k262uwy4r2k3ycr5awluarykdpag6a7y33jxop4cs2lu5uz5sseqd.onion
       xa4r2iadxm55fbnqgwwi5mymqdcofiu3w6rpbtqn7b2dyn7mgwj64jyd.onion

   For more information about this encoding, please see our discussion thread
   at [ONIONADDRESS-REFS].

這是因為在 ECC 的安全性被廣泛認可後，ECC 的優點就被拿出來用在這次設計上了：

  • 256 bits 的 ECC key 強度大約是 3072 bits RSA key (以現在最好的攻擊演算法來估算)。
  • 直接放 public key 不需要經過 hash function 計算，可以避免掉 hash function 被找到 collision 時的風險。

於是因為 hostname 放的下，就硬塞進去了 XDDD

不過如果要玩的人需要裝 alpha 版本，目前的 stable 版本還沒有這個功能：

Tor as of version 0.3.2.1-alpha supports the next-gen onion services protocol for clients and services! As part of this release, ​the core of proposal 224 has been implemented and is available for experimentation and testing by our users.