Hatena::ブログ(Diary)

あどけない話

2017-12-12

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 である。

まとめ

結論はいたって簡単だ。

2017-12-05

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-draft22-variant -accept 13443 -key $SOMEWHERE/key.pem -cert $SOMEWHERE/certificate.pem -loop -early-data

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

2017-11-14

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^225 - 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 AlgorithmSignature Algorithm
RSArsaEncryptionshaxxxWithRSAEncryption,id-RSASSA-PSS
DSAid-dsaid-dsa-with-shaxxx
ECDSAid-ecPublicKeyecdsa-with-SHAxxx
EdDSA??

安全性

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

安全性 RSANISTX/EdDSA
128ビット3072P25625519
192ビット7680P384
224ビット 448
256ビット15360P521

2017-11-13

TLS 1.3 開発日記 その21 TLS 1.3 ID22

TLS 1.3 ID21までの仕様は、

  • ServerHelloの書式がTLS 1.2と異なる
  • ChangeCipherSpecがない

という特徴があった。

ServerHelloが異なるということは、TLS 1.3に非対応であったWiresharkで表示できなくて辛いとか、パーサーの中で分岐しなければならないので関数プログラミングの考えでコードが書きにくいなどの問題があった。

その後、はやり世の中にはTLS 1.3を遮断するミドルボックスが少数ながらも存在することが分かり、これらのミドルボックスを騙すための方法が考案された。現在 PR1091議論中だが、開発者の間ではこのPRをマージした版がID22とすることで合意が取れている。その方法とはこうだ:

  • ServerHelloの書式をTLS 1.2と同じにする
  • HelloRetryRequestを廃止する
    • ServerHelloを利用し、Randomに特定の値を持つServerHelloをHelloRetryRequestとみなす
  • レコードのバージョンは、TLS 1.2とする
  • ChangeCipherSpecを復活させる
    • ChangeCipherSpecを受け取ったら単に無視する
    • 互換モードの場合、適切なタイミングでChangeCipherSpecを送ってよい

確かに、これならミドルボックスを騙せそうだ。というか、初めからこうしておけばよかったのに。

例によって、IETFHackathon前に、OpenSSLHaskell tlsがこの仕様をサポートし、ある程度の相互互換性を確かめた後、11月11日と12日に開催されたIETF 100で他の実装が追いついて来るという流れになった。僕は日本から遠隔参加するために、サーバーを立ち上げたり、クライアントバイナリを作成したりした。

IETF 1.3のHackathonでは、遠隔参加が活発だった TLS 1.3チームが "best remote participant" 賞を頂いたそうだ。景品は、IETFに参加しているTLS 1.3チームのメンバーが受け取ったとこのこと。遠隔参加賞なのにぃ!

2017-09-19

PatternSynonymsのススメ

PatternSynonymsは、その名の通り、パターンの別名である。GHC 7.8.1 で導入された。GHC 7系のPatternSynonymsは、モジュール内に閉じて入れば何の問題もなかったが、モジュールの外へexportする際は、patternキーワードが必要であり、構成子らしくなかった。

{-# LANGUAGE PatternSynonyms #-}

module A (Foo, pattern Zero) where

newtype Foo = Foo Int

pattern Zero :: Foo
pattern Zero = Foo 0

GHC 8 からは、patternキーワードが不要となり、構成子らしくなった。

{-# LANGUAGE PatternSynonyms #-}

module A (Foo(Zero)) where

newtype Foo = Foo Int

pattern Zero :: Foo
pattern Zero = Foo 0

PatternSynonymsの使いどころ

(ビット幅が決まっている)数値が何らかの意味を持つような問題を考える。たとえば、

0A
1B
2C
その他予約

のような対応があった場合、Haskell では以下のようなコードを書くことが多いだろう。

data Foo = A | B | C deriving (Show,Eq,Ord,Enum,Bounded)

簡潔でいいのだが、このコードには以下のような問題がある。

  • 「その他」の数値が発生しうる場合にはどうするのか?

以下のように構成子を増やすと、Enum を導出できなくなる。

data Foo = A | B | C | Other Int deriving (Show,Eq,Ord)

他にも問題がある。

  • 値が0から始まらない場合どうするのか?
  • 値が連続してない場合どうするのか?

という訳で、この方法は筋が悪い。そこで、PatternSynonymsの登場である。

module A (Foo(A,B,C),fromFoo,toFoo) where

newtype Foo = Foo {
    fromFoo :: Int
  } deriving (Eq)

toFoo :: Int -> Foo
toFoo = Foo

pattern A :: Foo
pattern A = Foo 0

pattern B :: Foo
pattern B = Foo 1

pattern C :: Foo
pattern C = Foo 2

instance Show Foo where
    show A = "A"
    show B = "B"
    show C = "C"
    show x = "Foo " ++ (show $ fromFoo x)

少しコード量は増えるが、問題に柔軟に対応できるのでストレスがない。