あどけない話

インターネットに関する技術的な話など

SemigroupがMonoidに恋するとき

復習

Semigroup

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

Monoid

class Semigroup a => Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mappend = (<>)

本題

Haskellerの中には、「設定はMonoidであるべき」宗派が存在する。そのような信念を持つHaskellerが作ったライブラリを使おうとすると、Monoid のインスタンス(<>) でつないで設定データを構築することになる。

この記事では、SemigroupをMonoidに昇格させるのはいつかという話題を扱うので、まずSemigroupである設定データから始めよう。僕が最近秀逸だと思っているフラグを例として挙げる。

フラグには以下のような操作ができる:

  • フラグをセットする (FlagSet)
  • フラグをクリア(アンセット)する (FlagClear)
  • フラグをデフォルトに戻す (FlagReset)

これを実装するのは簡単だろう。(<>) の右が勝つことに決めれば、以下のようになる。

data FlagOp = FlagSet | FlagClear | FlagReset deriving (Eq,Show)

instance Semigroup FlagOp where
    _ <> op = op

使ってみよう:

> FlagSet <> FlagReset <> FlagClear
FlagClear

あとは、これを受け取って、

  • FlagSet ならフラグをセットする
  • FlagClear ならフラグをクリアする
  • FlagReset ならデフォルトの値を使用する

という関数を書くことになるだろう。そこは割愛する。

これで話が終われば、設定データは Semigroup で十分で Monoid にする必要はない。どうして、設定と言えば Monoid と言われるのだろう?

答えは「設定したい項目は複数あることが多い」からだ。FlagOpを複数格納しているデータをConfigとしよう。

data Config = Config { aflag :: FlagOp, bflag :: FlagOp } deriving (Eq,Show)

instance Semigroup Config where
    Config a1 b1 <> Config a2 b2 = Config (a1 <> a2) (b1 <> b2)

aflag をセットする setAFlag を作るとする。bflag は明らかに FlagSetFlagClear ではないので、FlagReset としてみる。

setAFlag :: Config
setAFlag = Config { aflag = FlagSet, bflag = FlagReset }

同様に、setBFlag も作る。

setBFlag :: Config
setBFlag = Config { aflag = FlagReset, bflag = FlagSet }

setAFlagsetBFlag を結合するとどうなるだろう?

> setAFlag <> setBFlag 
Config {aflag = FlagReset, bflag = FlagSet}

あれれれれ? aflagbflagFlagSet であるべきなのに、aflagFlagReset になってしまった。

どうやって直すべきだろうか? 元の値を保存する FlagKeep が必要そうだ。

元の値を保存する? それって、単位元では? ということは、Monoid に昇格するべきでは?

その通りだ。

data FlagOp = FlagSet | FlagClear | FlagReset | FlagKeep deriving (Eq,Show)

instance Semigroup FlagOp where
    op <> FlagKeep = op
    _ <> op = op

instance Monoid FlagOp where
    mempty = FlagKeep

data Config = Config { aflag :: FlagOp, bflag :: FlagOp } deriving (Eq,Show)

instance Semigroup Config where
    Config a1 b1 <> Config a2 b2 = Config (a1 <> a2) (b1 <> b2)

instance Monoid Config where
    mempty = Config mempty mempty

setAFlag :: Config
setAFlag = Config { aflag = FlagSet, bflag = mempty }

setBFlag :: Config
setBFlag = Config { aflag = mempty, bflag = FlagSet }

使ってみよう。

> setAFlag <> setBFlag 
Config {aflag = FlagSet, bflag = FlagSet}

めでたし、めでたし。

なお、僕は「設定はMonoidであるべき」宗派ではなく、「デフォルトの設定に対して変更関数を用意すべき」宗派なので、あしからず。

TLS 1.3 開発日記 その29 Key update

TLS 1.2で暗号路の鍵を更新する場合は、ハンドシェイクをやり直す(再ネゴシエーションする)必要があった。実装の視点からいうと、鍵更新はハンドシェイクに対して同期的だった訳だ。

TLS 1.3では、サーバやクライアントがハンドシェイクをし直すことなく、いつでも鍵を更新できる。(TLS 1.3 には再ネゴシエーションはない。)つまり、鍵更新はハンドシェイクに対して非同期的になった。プログラマーにとっては、腕が試されることになる。

TLS 1.3の鍵更新メッセージの書式は、以下のように定義されている。

enum {
    update_not_requested(0), update_requested(1), (255)
} KeyUpdateRequest;

struct {
    KeyUpdateRequest request_update;
} KeyUpdate;

典型的な使い方はこうだ:

  1. AがKeyUpdate(update_requested)を送り、送信側の鍵を更新
  2. BはKeyUpdate(update_requested)を受け取ったら受信側の鍵を更新し、KeyUpdate(update_not_requested)を送り、送信側の鍵を更新
  3. AがKeyUpdate(update_not_requested)を受け取ったら、受信側の鍵を更新

AとBが同時にKeyUpdate(update_requested)を送ってもよく、その場合、単に2回鍵が更新された状態に落ち着く。

さて、問題はここからだ。

私は update_not_requested を update_requested への応答だと解釈していた。そこで、update_requested を送信してない状態で、update_not_requested を受け取ると、エラーにしていた。しかし、レビュアーの Olivier さんから、一方向の更新も許されるのではないかと指摘を受けた。そう思った理由は、OpenSSL の s_client が、

  • k コマンドの場合、一方向の鍵を更新しようとし (update_not_requested を送信)
  • K コマンドの場合、双方向の鍵を更新しようとする (update_requested を送信)

からだった。

slack のTLS 1.3の実装者が集まるチャンネルに話題を振ったところ

  • 許されていない:無視すべき
  • 許されていない:エラーにすべき
  • 許されている

の3つの解釈が出てきて、やはり仕様が曖昧だと分かった。

結局、編集者の Eric さんが降臨し、「許されている」と言って決着した。

結論:TLS 1.3 では、一方向の鍵更新もOK!

TLS 1.3 開発日記 その28 RFC8446

はてなダイアリーからはてなブログに移行しました。今後も、細々とブログを書いていきます。

2018年8月、TLS 1.3がRFC8446になりました!(TLSRFCは、伝統的にXX46という番号になります。) RFC8446の貢献者リストに僕の名前が載っていることを聞きつけたIIJ広報から依頼されたので、TLS 1.3の標準化と実装というブログ記事を書きました。執筆中にはリリースされていませんでしたが、現在ではTLS 1.3 対応済みの Firefox 63 と Chrome 70 が、めでたくリリースされています。

RFC8446の策定後、Haskelltls ライブラリも、他の実装と相互接続性を確認しました。また、私の実装がtls ライブラリの本家にマージされました。Haskell tls ライブラリをリリースするには、

  • 鍵のアップデート
  • ダウングレード対策
  • クライアント認証

を実装する必要がありますが、前2つは実装できていて、今後レビューを受ける予定です。クライアント認証については、ただ今勉強中です。(TLS 1.2 とは変わってるんです。)

最後に宣伝です。IIJ Technical Day で「パーサーを用いたTLS 1.3の仕様書の検証」というタイトルで発表します。タイトルや概要からは読み取れないと思いますが、以下のような内容にするつもりです。

TLS 1.3 開発日記 その27 ID 25/26

ドラフト25

ドラフト24までは、AEADに使う additonal_data は空文字列だった。ドラフト25からは、正しいレコードヘッダが使われることを遵守させるために、additonal_dataが以下のように定義された。

       additional_data = TLSCiphertext.opaque_type ||
                         TLSCiphertext.legacy_record_version ||
                         TLSCiphertext.length

以下の TLSCiphertext の構造と見比べれば、これがレコードヘッダそのものであることが分かるだろう。

       struct {
           ContentType opaque_type = application_data; /* 23 */
           ProtocolVersion legacy_record_version = 0x0303; /* TLS v1.2 */
           uint16 length;
           opaque encrypted_record[TLSCiphertext.length];
       } TLSCiphertext;

注意したいのは、TLSCiphertext.lengthである。復号化の際は TLSCiphertext.length は、入力の長さを図ればよい。しかし、暗号化の際は AEAD-Encrypt を呼び出す前に、結果の暗号文の長さを計算する必要がある。

TLS 1.3のAEAD-Encryptは、暗号文+認証タグを生成する。暗号文の長さは、平文の長さに等しい。よって、以下のように計算できる。

      暗号文の長さ = 平文の長さ + 認証タグの長さ

一方 TLS 1.2 では、additonal_data に平文(本当は圧縮文)のレコードヘッダを使う。すなわち、復号化の際にあらかじめ平文の長さを計算しておく必要がある。TLS 1.2 の ADEAD では explicit IV が利用されるので、以下のように平文の長さを計算できる。

      平文の長さ = 暗号文の長さ - explicit IV の長さ - 認証タグの長さ

ドラフト26

supported_versions拡張では、TLS 1.2 以前のバージョンを交渉してはいけないことが明記された。

あなたの知らない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