あどけない話

Internet technologies

あなたの知らないSemigroupの世界

自分で定義するデータの中には、足し算したくなるようなデータがある。たとえば、送信と受信のカウンターを定義したとしよう。

data Metrics = Metrics {
    rx :: Int
  , ts :: Int
  } deriving (Eq, Show)

これは以下のように足し算できると嬉しいだろう。

> Metrics 1 2 + Metrics 3 4
Metrics {rx = 4, ts = 6}

しかしこれは Num のインスタンスにすべきではない。このデータ型に掛け算は定義できないからだ。かといって、addMetrics みたいな関数を定義するのはかっこ悪い。

> Metrics 1 2 `addMetrics` Metrics 3 4
Metrics {rx = 4, ts = 6}

このように演算子が一個だけ欲しいと思ったら、それは多分 Monoid だ。

import Data.Monoid

instance Monoid Metrics where
    mempty = Metrics 0 0
    Metrics r1 t1 `mappend` Metrics r2 t2 = Metrics (r1 + r2) (t1 + t2)

GHC 7.10までは、(<>) が mappend の別名であるので、以下のようなコードが書ける。

> Metrics 1 2 <> Metrics 3 4
Metrics {rx = 4, ts = 6}

やったね!

GHC 8.4へようこそ

上記のコードを GHC 8.4 で読み込むと以下のようなエラーが出る。

Example.hs:8:10: error:
    ・ No instance for (Semigroup Metrics)
        arising from the superclasses of an instance declaration
    ・In the instance declaration for ‘Monoid Metrics’
  |
8 | instance Monoid Metrics where
  |          ^^^^^^^^^^^^^^

これはどういうことだろう? その疑問に答えるのがこの記事の主旨である。

mappendよりも(<>)の方がかっこいいのに、長い間 (<>) はMonoidのメソッドにはしてもらえなかった。あくまで別名であった。それは一部の人に、SemigroupをMonoidのスーパークラスにするという野望があったからだ。

数学での定義を思い出そう:

半群 (Semigroup)
モノイド (Monoid)
群 (Group)
  • 結合則: (a <> b) <> c = a <> (b <> c)
  • 単位元:e <> a = a <> e = a
  • 逆元:a <> inv a = e

さっきの疑問に答えると、GHC 8.4ではSemigroupがMonoidのスーパークラスとなり、Metricsに対する(<>)の定義がないために、エラーが出たという訳だ。

状況把握

今後どのようなコードを書けばよいかという疑問に答えるためには、GHCの各バージョンでの状況を把握しなければならない。

GHC 7.10 (base 4.8)

GHC 7.10 では、みなさんご存知のように base パッケージに Data.Monoid モジュールがある:

-- base : Data.Monoid
class Monoid a where
    mempty :: a
    mappend :: a -> a -> a

(<>) :: a -> a -> a
(<>) = mappend

Monoid型自体はPreludeの仲間入りを果たしたが、(<>)は明示的にimportする必要がある。

Data.Semigroupは、semigroupsパッケージで定義されている:

-- semigroup : Data.Semigroup
class Semigroup a where
    (<>) :: a -> a -> a

default (<>) :: Monoid a => a -> a -> a
  (<>) = mappend

最後の default は、DefaultSignatures という拡張で、Monoidの制約を持てば Semigroupの方の (<>) は mappend で代用できると読む。親子関係がひっくり返っていて、なんだかなぁという感じである。

GHC 8.0 (base 4.9)

Data.Semigroupがsemigroupパッケージからbaseパッケージへ移った:

-- base : Data.Monoid
class Monoid a where
    mempty :: a
    mappend :: a -> a -> a

(<>) :: a -> a -> a
(<>) = mappend

--base : Data.Semigroup
class Semigroup a where
    (<>) :: a -> a -> a

親子関係はない。

フラグ -Wnoncanonical-monoid-instances が定義された。これは、MonoidのインスタンスなのにSemigroupのインスタンスになってないと警告を出すフラグである。デフォルトは off。上位互換性に関するフラグ -Wcompat を付けても、警告が出る。

まだ GHC 8.4 を使えない人は、-Wall の横に -Wcompat を書き足して遊んでみるとよい。

GHC 8.2 (base 4.10)

何も変更なし。嵐の前の静けさだ。

GHC 8.4 (base 4.11)

なんとなんと、MonoidとSemigroupがPreludeの仲間に入った。そして、SemigroupがMonoidのスーパークラスとなった。

-- Prelude
class Semigroup a where
  (<>) :: a -> a -> a

class Semigroup a => Monoid a where
  mempty :: a

訂正:SemigroupがMonoidのスパークラスになったために、(<>) を定義してないとエラーが出るようになった。嵐がやってきたのだ。

対処方法

ここまで解説すれば、対処方法は明らかであろう。Semigroup (as superclass of) Monoid Proposalの最後に、semigroupsパッケージを使う方法と使わない方法が載っているので、よく眺めてほしい。

TLS 1.3 開発日記 その26 ID 24

TLS 1.3 ドラフト24で重要な変更は1つだけ。レコードのバージョン。

ドラフト23では

  • ClientHello のレコードバージョンは 0x0301 (TLS 1.0)
  • ServerHello のレコードバージョンは 0x0303 (TLS 1.2)

に定められた。これはこれでよい。

しかし、サーバから HelloRetryRequest なる ServerHello が返され場合はどうなるだろう? ある実装では

  • ClientHello のレコードバージョンは 0x0301 (TLS 1.0)
  • ServerHello (HRR) のレコードバージョンは 0x0303 (TLS 1.2)
  • ClientHello のレコードバージョンは 0x0301 (TLS 1.0)
  • ServerHello のレコードバージョンは 0x0303 (TLS 1.2)

となるだろう。また別の実装では、

  • ClientHello のレコードバージョンは 0x0301 (TLS 1.0)
  • ServerHello (HRR) のレコードバージョンは 0x0303 (TLS 1.2)
  • ClientHello のレコードバージョンは 0x0303 (TLS 1.2)
  • ServerHello のレコードバージョンは 0x0303 (TLS 1.2)

となるだろう。

どちらがミドルボックスを騙せるかというと、後者である。前者はレコードのバージョンがころころ変わるから、ミドルボックスが怪しいと思って通信を遮断するかもしれない。

というわけで、2回目の ClientHello のレコードバージョンは、0x0303 に定められた。なお、実装者間の合意ではドラフト 24 に対応しても、supported_versions 拡張に指定するTLSのバージョンにはドラフト 23 の値を使うことで合意が取れている。

個人的には、レコードの書式にバージョンフィールドがあるのはプロトコルの設計ミスだと思う。

TLS 1.3 開発日記 その25 picotls

kazuho さんが実装を進めている picotls を使う方法のまとめ。picotls は TLS 1.3 のみを実装している。またデフォルトで利用できる ECDHE は P256 のみである。

インストール

cmakeが必要なので、あらかじめインストールしておく。master ブランチが draft 23。

% git clone https://github.com/h2o/picotls
% cd picotls
% git submodule init
% git submodule update
% cmake .
% make

これで、トップディレクトリに "cli" というコマンドができる。"cli" は、サーバにもクライアントにもなる。

picotls サーバ

% ./cli -k $SOMEWHERE/key.pem -c $SOMEWHERE/certificate.pem 127.0.0.1 13443

picotls クライアント

Full:

% ./cli 127.0.0.1 443

HRR:

最初はkey_shareを空にして送るという裏技を使う

% ./cli -n 127.0.0.1 443

PSK:

最初の -s オプションでチケットを保存し、次の -s オプションでチケットを読み込む。

% rm ticket
% cli -s ticket 127.0.0.1 443
% cli -s ticket 127.0.0.1 443

0RTT:

% rm ticket
% cli -s ticket 127.0.0.1 443
% cat early-data.txt - | cli -s ticket -e 127.0.0.1 443

TLS 1.3 開発日記 その24 ID23

ID23での変更点:

key_share拡張

Canonのプリンターが40を使っていることが判明したので、key_share拡張の値を40から51へ変更。

signature_algorithms_cert拡張

signature_algorithmsに加えてsignature_algorithms_cert拡張を新設した。CertificateVerify用がsignature_algorithms、証明書用がsignature_algorithms_cert。signature_algorithms_certがなければsignature_algorithmsで代用する。

PSSを分割した。たとえばrsa_pss_sha256は、rsaEncryption用のrsa_pss_rsae_sha256とRSASSA-PSS用のrsa_pss_pss_sha256に分かれた。

不変条件

不変条件が加筆された:

  • クライアントは提案したものは必ず実装してないといけない
  • サーバはわからないものは単に無視(異常終了してはいけない)
  • TLSを終端するミドルボックスはその両方を満たせ
  • 単にリレーするミドルボックスは中身を触るな

CSS

状態を持たないサーバは、一番目と二番目のClientHelloの間に到着するCSSを無視すること。

静的なRSA

静的なRSAは、Bleichenbacher-type攻撃を防止するために使用不可にすべき。

goな関数

これは「Haskell (その2) Advent Calendar 2017」の1日目の記事です。遅くなってすいません。

読者として末尾再帰ぐらいは理解しているHaskellerを想定しています。

トップレベルとローカル関数

再帰を用いて関数を書いているとき、トップレベルで再帰するか、ローカル関数で再帰するか、ときどき迷う。この記事では、僕なりの判断基準を示したい。

Data.Listで定義されている再帰が必要な関数は、ほとんどがトップレベルで再帰している。代表例のmapの例を見てみよう。

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

mapをローカル関数を使う実装にしてみよう。この記事では、ローカル関数名としてgoを用いる。(loopを使う流儀もある。)

map' :: (a -> b) -> [a] -> [b]
map' f xxs = go [] xxs
  where
    go acc []     = acc
    go acc (x:xs) = go (acc ++ [f x]) xs

Haskellerなら、(++)を使いリストの末尾に要素を追加していることに違和感を覚えるだろう。

以前、NTT Dataで利用されたHaskellドリルが話題となった。全体的にはよいのだけれど、上記のmap'のように、必ずwhereの中にローカル関数を定義させていたことには賛同できなかった。

Haskellを習得する際は、リストプログラミングから入ることが多く、初心者はどうしてもトップレベルで再帰しがちである。Haskellドリルには、これを矯正する効果が多少はあるかもしれない。

一方、ローカル関数で再帰する例として、以下のコードを取り上げる。

udpLookup :: ByteString
          -> Socket
          -> Int
          -> (DNSMessage -> Bool)
          -> Int
          -> (Socket -> IO DNSMessage)
          -> IO DNSMessage
udpLookup query sock tm checkSeqno retry rcv = go 0 False
  where
    go cnt mismatch
      | cnt == retry = if mismatch then
                         E.throwIO SequenceNumberMismatch
                       else
                         E.throwIO RetryLimitExceeded
      | otherwise    = do
          mres <- timeout tm (send sock query >> rcv sock)
          case mres of
              Nothing  -> go (cnt + 1) False
              Just res
                | checkSeqno res -> if trunCation $ flags $ header res then
                                      E.throwIO TCPFallback
                                    else
                                      return res
                | otherwise      -> go (cnt + 1) True

このコードの意味は分からなくてもよいが、このコードをトップレベルでの再帰に書き直してみると、次のようなことが分かるだろう。

  • 引数の数が多くなって、再帰の際に変化する引数がどれなのパッと見分からなくなる
  • 蓄積変数など本来関数に閉じているべきパラメータを外に見せなければならなくなる

さてさて、トップレベルとローカル関数を使い分ける基準はあるのだろうか?

遅延評価とトップレベ

Data.Listの関数がトップレベルで定義されているのは、遅延評価と関係がある。私は遅延評価のファンではない。なぜなら、遅延評価が役立つ場面は、以下の3つしかないからである。

  • リスト処理
  • CASでの変数の更新
  • 純粋性のテスト

Haskellのデフォルトの評価戦略が正格評価だったらよかったのにと思う。ただし、遅延評価がリスト処理に役立つのは間違いない。狭義の意味では、関数プログラミングはリストプログラミングであるから、関数プログラミングに遅延評価が必要であると勘違いしやすい。

Haskellで構造が遅延する一般的なデータ型はリストかData.Sequenceぐらいである。Data.Mapでさえ構造は遅延しない。私の定義では、関数プログラミングとは不変データプログラミングである。Haskellでは、構造が正格な不変データが多いので、デフォルトは正格評価であってほしい。

デフォルトを正格評価にするStrict/StrictDataプラグマは、GHC 8.0で実装された。GHC 8.4がリリースされれば、3つのメジャーバージョンを保守するポリシーでは GHC 7.x を捨てられるので、Strict/StrictDataプラグラマを活用できるようになるだろう。

前置きが長くなったが、遅延評価がリスト処理に役立つ例を見てみよう。以下は、map とhead を組み合わせた例である。

   head $ map (+1) [1,2,3,4,5]
-> head (2 : map (+1) [2,3,4,5])
-> 2

mapでは、トップレベルで再帰しているため、構造を再帰の外で作っている。そのため、遅延評価の下では無駄な計算が起こらない。一方、ローカル関数を使うmap'だと次のようになる。

   head $ map' (+1) [1,2,3,4,5]
-> head [2,3,4,5,6]
-> 2

という訳で、リストを生成する関数はトップレベルで再帰するべきである。

ローカル関数の利点

では、リストを生成しない関数はどうだろうか? 上記のローカル関数を使う関数をトップレベルに書き換えたときの欠点が、ローカル関数を使う関数の利点であるから:

  • 再帰の際に変化する引数がどれなのかパッと見て分かる
  • 関数に閉じているべきパラメータを外に見せなくて済む

実は、もう一つ性能が良くなるという利点もある。Haskellの通常のデータはポインターで指されており、即値ではない。Intであろうと本当の値はポインターで指されている。トップレベルの再帰に、たとえば Int を使うと、関数を呼び出すごとにポインターをたどることになる。公開されている関数の引数は、即値に最適化できないからである。

ローカル関数を使うと、コンパイラは最適化に積極的になれる。

  • ローカル関数の引数は、可能であれば即値が使われる
  • ローカル関数から見たトップレベルの引数も可能であれば即値が使われる

こういう形式をWorker Wrapperと言って、プログラマーが少し手助けすることでコンパイラーに最適化を促す手法の一種である。たとえば、udpLookupなら、go が Worker、udpLookup が Wrapper である。

まとめ

結論はいたって簡単だ。

  • リストを生成する関数はトップレベルで再帰せよ
  • それ以外の関数ではローカル関数で再帰せよ

TLS 1.3 開発日記 その23 BoringSSL

BoringSSLでTLS 1.3を使う方法のまとめ。

インストール

ビルドシステムNinjaをあらかじめインストールしておく。

% git clone https://boringssl.googlesource.com/boringssl
% cd boringssl
% mkdir build && cd build && cmake -GNinja .. && ninja bssl

ビルドは感心するほど速い!

BoringSSLサーバ

% tool/bssl server -tls13-variant draft28 -accept 13443 -key $SOMEWHERE/key.pem -cert $SOMEWHERE/certificate.pem -loop -early-data

追記:-tls13-draft22-variantはなくなったようだ。
追記:-tls13-variant は引数を取るようになった。

BoringSSLクライアント

Full:

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443

HRR:

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443 -curves P-521:x25519

PSK:

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443 -test-resumption

0RTT:

% tool/bssl client -tls13-variant draft22 -connect 127.0.0.1:13443 -test-resumption -early-data @$SOMEWHERE/early-data.txt

TLS 1.3 開発日記 その22 公開鍵暗号の動向

P256とかX25519とかPSSとか聞いても、よくわからない人のための用語解説。

長い間TLSの世界では、鍵交換にも認証にもRSAが使われてきた。必要となる安全性が大きくなると、RSAの公開鍵は急激に大きくなり、したがって鍵交換や認証のコストが大きくなるという問題がある。

楕円曲線暗号(ECC: Elliptic Curve Cryptography)は、RSAやDiffie Hellmanに比べると、小さな公開鍵で同程度の安全性を実現するという特長を持つ。特許問題が不透明なせいで楕円曲線暗号は長年敬遠されてきたが、この数年で(少なくとも鍵交換に対しては)一気に普及してきた感じだ。

おおざっぱに言うと、楕円曲線暗号で実現できるのは、DH(Diffie Hellman)とDSA(Digital Signature Algorithm)であり、RSAは実現できない。

鍵交換のDHに関しては、証明書が付いた静的な公開鍵ではなく、動的に公開鍵を作って使い捨てるDHE(Diffie Hellman Ephemeral)が主流となっている。楕円曲線暗号版は、ECDHEと呼ばれる。

DSAは、ElGamal公開鍵暗号の署名版であり、それはすなわち署名の際に乱数を使うことを意味している。DSAは、秘密鍵と署名対象が同じでも、乱数のため異なる署名が生成されると言う特徴がある。同じ乱数を再利用してしまうと、秘密鍵を推測されてしまう。楕円曲線暗号版は、ECDSAと呼ばれる。

NISTのECDHEとECDSA

NISTは、楕円曲線のパラメータをいくつも定義しているが、普及しているのは以下の通りである。安全性については後述。

  • P256 (secp256r1)
  • P384 (secp384r1)
  • P521 (secp521r1) /* 512 ではないことに注意 */

ECDHE(P256)は、現時点での鍵交換のデファクトスタンダードと言ってもいいかもしれない。ECDSAでは、ハッシュ関数が選択式である。

符号化方式や圧縮方式など、仕様が階層的に定められており、実装のためにはたくさんの資料を読む必要がある。

Curve25519とCurve448

NISTが擬似乱数生成器アルゴリズムバックドアを仕込んでいたことが明るみに出て、セキュリティの専門家はNISTを信用しなくなった。そのため、NISTのECDHEとECDSAに対する代替を普及させようとしている。

qmailなどで有名なDJB氏は、Curve25519とCurve448を策定した。間違いやすいが、安全性は 25519、448の順に高くなる。その理由は、名前の由来となった素数を見れば明らかだろう。

  • 2^255 - 19
  • 2^448 - 2^224 - 1

この二つの曲線を使って、DHEを実現するのが、名前がXから始まる鍵交換である:

  • Curve25519を利用して実現されるDHEが X25519
  • Curve448を利用して実現されるDHEが X448

これらは符号化と一緒に定められており、実装したければRFC 7748だけを読めばよい。内容が理解できなくとも、書いてある通りに実装すれば動く。X25519は、現在急速に普及している。

一方、認証にはDSAとは異なる署名方式であるEdDSA(Edwards-curve Digital Signature Algorithm)を使う。ECDSAとEdDSAは間違いやすいので要注意だ。前述のようにECDSAは乱数を使うが、EdDSAは使わない。

  • Curve25519を利用して実現されるEdDSAが Ed25519
  • Curve448を利用して実現されるEdDSAが Ed448

ハッシュ関数は、Ed25519ではSHA512、Ed448ではSHAKE256に固定されてる。詳しくはRFC8032を参照のこと。

RSA

RSAの署名では、長い間、書式としてRSASSA-PKCS1-v1_5が使われきた。RSASSA-PKCS1-v1_5の安全性は証明されていない。不安視している専門家は、安全性の証明されているRSASSA-PSSを推奨している。これは単なる書式の違いなので、既存のRSAの公開鍵や秘密鍵が利用できる。詳しくはRFC 8017を参照のこと。

世の中の証明書

世の中の証明書は、ほとんどすべてがRSAで、少しだけECDSAがあり、DSAはほとんどなく、EdDSAはまったくない状況のようである。

openssl x509 -noout -text コマンドを使うと、証明書の内容が表示される。

  • Public Key Algorithm が公開鍵暗号の方式
  • Signature Algorithm がその証明書を署名している署名方式

である。参考までにそれぞれの値を示す。

Public Key Algorithm Signature Algorithm
RSA rsaEncryption shaxxxWithRSAEncryption,id-RSASSA-PSS
DSA id-dsa id-dsa-with-shaxxx
ECDSA id-ecPublicKey ecdsa-with-SHAxxx
EdDSA ? ?

安全性

最後に安全性の対応表を載せておく。

安全性 RSA NIST X/EdDSA
128ビット 3072 P256 25519
192ビット 7680 P384
224ビット 448
256ビット 15360 P521