UPSERT

維基百科對 UPSERT 的說明:(取自「Merge (SQL)」條目)

A relational database management system uses SQL MERGE (also called upsert) statements to INSERT new records or UPDATE existing records depending on whether or not a condition matches.

MySQL 裡的兩種語法其實就是在實做這個需求:

  • REPLACE INTO ...
  • INSERT INTO ... ON DUPLICATE KEY UPDATE ...

而前者其實是後者的一個特例 (當 INSERT 發現有 dupe key 時把現有的 record 改成與 INSERT 時相同的條件)。

而計數器是後者常見的 case 之一:當 record 不存在的時候塞一筆進去,並且將 counter 設為 1;當 record 存在的時候對 counter 加一更新。像是這樣的 SQL query:

INSERT INTO my_table SET id = ?, num = 1 ON DUPLICATE KEY UPDATE num = num + 1;

由於這是常見的需求,使得這個語法是目前少數 MySQL 比 PostgreSQL 好用的地方。

在「A Case for Upserts」這篇就看到抱怨 PostgreSQL 不實做這個功能...

不過我覺得作者寫得有點誇張,INSERT INTO ... ON DUPLICATE KEY UPDATE ... 應該是可以模擬出來的功能:當 INSERT 失敗後再跑 UPDATE。而 REPLACE INTO ... 是特例,也就當然可以模擬出來。

資料庫裡 Primary Key 的選擇...

Ingram Chen 寫的「Obvious Choice」這篇舉的例子剛好是在討論資料庫裡 Primary Key 的設計。

這個問題之前在 interview 的時候曾經拿出來問。問到資料庫相關的題目時,有些人在設計 schema 會多放一個 id 欄位,有些人則不會放。

有放 id 欄位的我就會問「為什麼要放」,沒有 id 欄位的我就會問「為什麼不這樣設計」。重點不在於哪個才是正確的,而是在於要能夠說明為何這樣選擇。

不過大多數人都是「看別都這樣做,所以我就這樣做」,可惜...

利用機器噪音的 Side-channel attack,解 GnuPG 的 RSA key...

Daniel GenkinAdi ShamirEran Tromer 發表的論文:「RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis」。

在維基百科上有「Acoustic cryptanalysis」的條目,不過好像還沒補上這次的事情...

2004 年的 Eurocrypt 時,後面兩位就已經發表過「Acoustic cryptanalysis - On nosy people and noisy machines」,可以針對機器的噪音取得「部份資訊」:

這次攻擊者利用「麥克風」可以對機器的聲音攻擊 (side-channel attack),進而「得到完整的 private key」:

左邊那台機器... 好像是隻手機啊... @_@

收音的設備愈好,效果愈好:

這次直接把 GnuPG 打趴真是太過分了... (被 assign 了 CVE-2013-4576)

Adi Shamir 老人家還是很活躍啊...

用 InnoDB 時關於 PRIMARY KEY 的建議

Percona 的「InnoDB scalability issues due to tables without primary keys」這篇文章在討論 InnoDB 在沒有 PRIMARY KEY 時的效能問題。

在討論效能問題前,應該先讀過 MySQL 官方文件裡提到 InnoDB index 架構的文章,其中就有提到 PRIMARY KEY 以及其他的 INDEX KEY 的底層架構:「InnoDB Table and Index Structures」。

InnoDB 是 clustered index 架構 (關於 clustered index 的完整說明,可以參考維基百科的「Database index」條目),也就是說,資料本身 (row data) 存放時會按照某個順序存放,這邊的順序是按照這樣的方式定義的:

  • 如果你有指定 PRIMARY KEY,那麼就會直接用 PRIMARY KEY 當作 clustered index。
  • 如果沒有指定 PRIMARY KEY,但有 UNIQUE INDEX,而且所有欄位都是 NOT NULL,那麼就用這組 UNIQUE INDEX (NOT NULL) 當作 clustered index。
  • 如果都沒有指定 PRIMARY KEY,那麼就會產生一個隱藏的欄位,是一個 6 bytes 的 auto increment 的數字,用這個欄位當 clustered index。也因為如此,在這種情況下,資料會依照建立的順序存放。

另外,InnoDB 的 secondary index 會指到 PRIMARY KEY (B+Tree 的 value 部分是放 PRIMARY KEY)。

所以,一般在規劃資料庫時建議的作法是:

  • 所有的表格都要有 PRIMARY KEY。
  • PRIMARY KEY 必須是 INT UNSIGNED (4 bytes),只有在需要 BIGINT UNSIGNED (8 bytes)的時候才用 BIGINT UNSIGNED。

對於有大量 secondary index 的表格更應該這樣做 (因為可以省下大量空間)。而對於現代的 ORM 來說,也都幾乎要求要有 PRIMARY KEY,甚至有些 ORM 要求 PRIMARY KEY 必須是 single column。

如果你都能了解後,再去看 Percona 討論沒有 PRIMARY KEY 的情況時,才能了解他們想要討論什麼事情... 裡面還包含了 InnoDB 格式的差異。

GoDaddy 將 Lavabit 的 SSL Certificate 撤銷了...

在「美國法院可以強制公司交出 SSL Private Key...」這篇提到法院文件顯示 Lavabit 的 SSL Certificate 已經被 FBI 拿走。

消息公開後幾天,GoDaddy 終於記得要依照程序,主動把 Lavabit 的 SSL Certificate 撤銷:「GoDaddy Pulls Lavabit's Security Creds Because The FBI Got Ahold Of Its Encryption Keys」。

巡迴庭的消息好像還沒出來...

美國法院可以強制公司交出 SSL Private Key...

前幾天解密的文件證實了先前的傳言:美國法院可以以協助犯罪搜查的名義,強制商業公司交出 SSL Private Key 給 FBI,並且可以用「偵查犯罪中」的理由要求公司不得公開這件事情。

報導在這:「Edward Snowden’s E-Mail Provider Defied FBI Demands to Turn Over Crypto Keys, Documents Show」,解密的文件 (整個系列的文件) 則在「Redacted Pleadings Exhibits 1 23」這邊可以讀到。

Edward Snowden 的 E-mail 服務提供商 Lavabit 在七月時被法院要求配合調查,其中被要求交出 SSL Private Key:

A week later, prosecutors upped the ante and obtained the search warrant demanding “all information necessary to decrypt communications sent to or from the Lavabit e-mail account [redacted] including encryption keys and SSL keys.”

而且「交出 SSL key 這件事情」不得公開:

The judge also rejected Lavabit’s motion to unseal the record. “This is an ongoing criminal investigation, and there’s no leeway to disclose any information about it.”

而 Lavabit 最後決定以紙本形式提供:

In an interesting work-around, Levison complied the next day by turning over the private SSL keys as an 11 page printout in 4-point type. The government, not unreasonably, called the printout “illegible.”

在法院要求提供電子格式後,Levison (Lavabit 的頭) 決定讓 Lavabit 停止服務,同時因為受限封口令,網站上只能寫得很隱晦,表達對美國的不信任:

這件事情預定要到第四巡迴庭去打:「Let's rally for Lavabit to fight for the privacy rights of the American people. | Rally.org」。

Amazon CloudFront 上 Protected Content 的 URL Sign...

Amazon CloudFront 也可以設定要簽名才能抓檔案,只是 URL Sign 設計的觀念跟 Amazon S3 完全不一樣,這不一致的調調很... 詭異...

大致上有這些差異:

  • Amazon S3 用的是 HMAC-SHA1 的機制簽名 (shared secret,也就是 Amazon S3 與你都有同一把 key),而 Amazon CloudFront 則是用 RSA key 簽名 (public key,也就是 Amazon CloudFront 存放 public key,你自己存放 private key)。
  • 也因為是使用 RSA key,有人會誤解跟 Amazon EC2 用的 RSA key 相同。但實際上需要在 Security Credentials 頁裡設,有專門對 Amazon CloudFront 用的 RSA key 的段落。
  • 自己對 Base64 編碼再處理,避開使用 += 以及 /。但不是有標準可以用嗎,為什麼要自己發明呢...
  • 引入 Policy 的彈性機制,不僅可以對時間控制,也可以對 IP address 控制,但 Policy 這是帶在 URL 裡傳進去的... 你可以看到我的程式碼內產生出 $json_str 後簽完名帶到 URL 內了。

官方的 CloudFront Signed URLs in PHP 這篇的範例程式碼其實很清楚了,要直接拿去用其實也沒麼問題。我自己整理後是這樣:

<?php

$key_pair_id = 'APKA...';
$pem_file = '';
$resource = 'http://test2-cdn.gslin.org/test.txt';

$expires = time() + 3600;

$json_str = json_encode(
    array(
        'Statement' => array(
            array(
                'Resource' => $resource,
                'Condition' => array(
                    'DateLessThan' => array(
                        'AWS:EpochTime' => $expires
                    )
                )
            )
        )
    ),
    JSON_UNESCAPED_SLASHES
);

$buf = file_get_contents($pem_file);
$key = openssl_get_privatekey($buf);

openssl_sign($json_str, $signed_policy, $key, OPENSSL_ALGO_SHA1);

openssl_free_key($key);

$signature = str_replace(
    array('+', '=', '/'),
    array('-', '_', '~'),
    base64_encode($signed_policy)
);

echo "${resource}?",
    "Expires=${expires}&",
    "Signature=${signature}&",
    "Key-Pair-Id=${key_pair_id}\n";

反正你搞不太懂 Amazon 為什麼要這樣設計的... =_=

各種密碼破解速度...

oclHashcat-plus 提供了透過 GPU 破解的 benchmark 數據:

可以看到 PBKDF2、sha512crypt $6$ 以及 bcrypt $2a$ 的速度慢得很漂亮 XD 不過 SHA512 的速度比 SHA256 慢不少倒是頗意外...

PBKDF2 的使用率很高 (因為無線網路 WPA/WPA2 的規格),所以各語言的普及率也高不少,如果要找個標準來用的話,PBKDF2 相當不錯...

SSL/TLS 的 Perfect Forward Secrecy...


寫這篇順便測試 MathJax 的效果...

因為 NSA 的惡搞,這陣子 PFS (Perfect Forward Secrecy) 突然被拿出來討論:

在講 PFS 前,得先講 Diffie-Hellman key exchange (D-H)。

D-H 是利用這個等式:

$$(g^a)^b \equiv (g^b)^a \mod p$$

其中 \(p\) 是大質數,而 \(g\) 是 \(p\) 的 primitive root (即不存在任何 \(n < p\) 可以使得 \(g^n \equiv 1 \mod p\))。 而因為當 \(p\) 夠大時,要從 \(g^a \mod p\) 計算 \(a\) 就是離散對數問題,而離散對數問題是已知沒有有效率計算的問題,所以我們會假定當 \(p\) 夠大時,傳輸 \(g^a \mod p\) 是無法用合理資源計算得知 \(a\)。

因此,Alice 與 Bob 就可以產生自己的 private secret \(a\) (Alice) 與 \(b\) (Bob),計算出 \(g^a\) 與 \(g^b\) 後公開傳輸給對方,當 Bob 收到 Alice 提供的 \(g^a\) 時就計算 \((g^a)^b \equiv g^{ab} \mod n\),而 Alice 收到 Bob 提供的 \(g^b\) 後可以計算 \((g^b)^a \equiv g^{ba} \equiv g^{ab} \mod n\)。

而攻擊者只拿到公開的 \(g^a\) 與 \(g^b\) 以及 \(g\),無法計算出 \(g^{ab}\),於是就雙方就建立一組 shared secret 了。

回到 SSL/TLS 的問題上,由於 RSA 加解密的速度並不快,所以 SSL/TLS 是在 RSA 的保護下交換 RC4 或是 AES 所需要的金鑰 (key)。

交換 key 這件事情除了可以直接交換以外,還可以利用 D-H 交換。

D-H 交換可以確保當 RSA key 被破解時還要再破每個 session 的 D-H 所產生出來的 key,而直接交換的話,只要破一把 RSA key 就可以解出所有 traffic 了。

而 PFS 會被提出來,是因為目前消息指出 NSA 其實有在錄下 SSL/TLS 流量,等哪天有機會取得 RSA key 的時候 (無論是硬解,或是其他方式),就有機會能夠一次破一卡車資料... (因為目前大部分的 SSL/TLS 流量都沒有上 PFS)

雖然 PFS 會慢一些,不過已經確認 NSA 打算來搞了,所以還是乖乖加上去吧... @_@

把 MySQL MyISAM 換到 Galera Cluster 的 InnoDB 上...

在「Switching from MySQL/MyISAM to Galera Cluster」這邊看到一個 script 可以檢查 MySQL MyISAM 換到 InnoDB,而且預定要換成 Galera Cluster 時的問題。

常見的問題都有檢查到,還蠻有用的:

  • 針對沒有 Primary Key 的表格提出警告,讓管理者規劃補上 Primary Key。
  • 針對 MyISAM 換成 InnoDB 後造成 Primary Key 太長的表格提出警告,讓管理者想辦法修改。

Galera Cluster 無法處理沒有 Primary Key 表格的刪除動作:(可以參考「MariaDB Galera Cluster - Known Limitations」這邊的說明)

DELETE operation is unsupported on tables without primary key. Also rows in tables without primary key may appear in different order on different nodes. Don't use tables without primary key.

不過每個表格都要有 Primary Key 並不難,因為如果有正規化時通常都會達到目標。就算不去用他也還是可以設計一個 INT UNSIGNED PRIMARY KEY AUTO_INCREMENT 放著。(過大的時候再換成 BIGINT UNSIGNED)