あどけない話

Internet technologies

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

TLS Haskell

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

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

TLS Haskell

TLS 1.3 ID21までの仕様は、

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

という特徴があった。

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

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

  • ServerHelloの書式をTLS 1.2と同じにする
    • バージョンはTLS 1.2を指定する
    • 圧縮方式が復活。常に0
    • セッションIDが復活。互換性モードの場合、クライアントが指定したセッションIDをコピーする
    • サーバーが選択したバージョンは、supported_versions拡張でクライアントへ伝える
  • HelloRetryRequestを廃止する
    • ServerHelloを利用し、Randomに特定の値を持つServerHelloをHelloRetryRequestとみなす
  • レコードのバージョンは、TLS 1.2とする
  • ChangeCipherSpecを復活させる
    • ChangeCipherSpecを受け取ったら単に無視する
    • 互換モードの場合、適切なタイミングでChangeCipherSpecを送ってよい

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

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

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

PatternSynonymsのススメ

Haskell

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の使いどころ

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

0 A
1 B
2 C
その他 予約

のような対応があった場合、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)

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

DNSの書式

DNS

何度読んでもよく分からないDNS関連のRFCを自分なりに読みやすいようにまとめる私的メモ。
ちなみに、僕は Haskell DNS ライブラリの作者で今も精力的に開発中。

RFC 1035

RFC 1035で定められている構造をトップダウン的に列挙する：

メッセージ全体
    +---------------------+
    |        Header       |
    +---------------------+
    |       Question      | the question for the name server
    +---------------------+
    |        Answer       | RRs answering the question
    +---------------------+
    |      Authority      | RRs pointing toward an authority
    +---------------------+
    |      Additional     | RRs holding additional information
    +---------------------+

「問い合わせ」も「返答」も同じ形。ヘッダのQAフラグで区別される。

「返答」には「問い合わせ」のQuestionがコピーされる。

後述のように、Questionだけ独自の書式で、Answer、Authority、Additional は同じ書式。

ヘッダ
                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                      ID                       |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |QR|   Opcode  |AA|TC|RD|RA|   Z    |   RCODE   |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    QDCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    ANCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    NSCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    ARCOUNT                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

基本的にUDPで通信するので、IDでどの「問い合わせ」に対する「応答」なのか判断する。つまり、「問い合わせ」のIDが、応答にコピーされる。

XYCOUNTは、引き続くそれぞれのセクションに何個エントリがあるかを示す。

Question
                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                                               |
    /                     QNAME                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     QTYPE                     |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     QCLASS                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Resource record

Answer、Authority、Additional 用の書式。

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                                               |
    /                                               /
    /                      NAME                     /
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                      TYPE                     |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     CLASS                     |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                      TTL                      |
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                   RDLENGTH                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
    /                     RDATA                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
RDATAの例 (A)
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    ADDRESS                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

IPv4なので4バイト。

RDATAの例 (SOA)
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    /                     MNAME                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    /                     RNAME                     /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    SERIAL                     |
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    REFRESH                    |
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     RETRY                     |
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    EXPIRE                     |
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                    MINIMUM                    |
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

END0 (RFC 6891)

OPT RR

ヘッダを拡張する目的で、OPT RR が定義されている。OPT RR は Additional セクションに1つだけ格納される。

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                                               |
    /                                               /
    /                  NAME == 0                    /
    |                                               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |               TYPE == OPT (41)                |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                UPD payload size               |  was CLASS
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |     EXTENDED-RCODE    |       VERSION         |  was TTL
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |DO|                  Z                         |  was TTL
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                   RDLENGTH                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--|
    /                     RDATA                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

CLASS と TTL の意味が変わっている。

昔のCLASSには、問い合わせ側の UDP バッファサイズが入る。

昔のTTLは、ヘッダのRCODEやフラグが含まれている部分を拡張するために使う。

ヘッダ中のRCODEとEXTENDED-RCODEで拡張RCODEを構成する。EXTENDED-RCODEが上位8ビット、RCODEが下位4ビットで、合計12ビット。RRだけからは、拡張RCODEが得られない恐ろしい仕様。

VERSIONは0、すなわちEND0。

D0 は DNSEC OK ビット。Zは予約ビット。

OPT RDATA

RDATAに入るオプションの書式：

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                 OPTION-CODE                   |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                OPTION-LENGTH                  |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                                               |
    /                 OPTION-DATA                   /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
オプションの例

RFC 7871でClient Subnetが定義されている：

                                    1  1  1  1  1  1
      0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                 OPTION-CODE (8)               |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                 OPTION-LENGTH                 |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                     FAMILY                    |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    | SOURCE PREFIX-LENGTH  | SCOPE PREFIX-LENGTH   |
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    |                   ADDRESS...                  /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

TLS 1.3 開発日記 その20 TLS 1.3 ID21

TLS Haskell

TLS 1.3 ID21に追従した。

  • Add a per-ticket nonce so that each ticket is associated with a different PSK.

NewSessionTicket に ticket_nounce が増えた。

struct {
    uint32 ticket_lifetime;
    uint32 ticket_age_add;
    opaque ticket_nonce<1..255>;
    opaque ticket<1..2^16-1>;
    Extension extensions<0..2^16-2>;
} NewSessionTicket;

ID 20 までは、key schedule でいうところの PSK の値は、resumption_master_secret そのものだった。ID 21 では、以下のように算出するようになった。

PSK = HKDF-Expand-Label(resumption_master_secret, "resumption", ticket_nonce, Hash.length)

セッションで複数回NewSessionTicketが発行される場合は、ticket_nounceはユニークな値でなければならない。それを守れば、チケットごとにユニークなPSKの値が生成される。ID 20の仕様に対する明らかな攻撃方法は発見されていないが、ID 21の方が直感的に安全だろうと思われている。

セッションで1回しかNewSessionTicketが発行されない場合は、固定の文字列でもよい。(空文字列も許容するよう使用を変更すべき？)

なお、ID 21の HKDF-Expand-Label は曖昧になってしまったので、そのまま実装すると他の実装とは通信できない。具体的には、HKDF-Expand-Label は以下のように定められている。

HKDF-Expand-Label(Secret, Label, HashValue, Length) = HKDF-Expand(Secret, HkdfLabel, Length)

struct {
    uint16 length = Length;
    opaque label<7..255> = "tls13 " + Label;
    opaque hash_value<0..255> = HashValue;
} HkdfLabel;

ID 20 までは、HashValue の部分は、本当にハッシュ値か空文字列しか取らなかった。空文字列は、特殊なハッシュ値だと解釈されていた。HashValue の長さと、HKDF-Expand-Label の出力の長さを表す Length は、たまたま一緒であった。

今回、ticket_nounce も取るようになったので、その前提が崩れたことを OpenSLL の担当者が発見した。OpenSSLでは、上記の仕様を以下のように解釈して、実装している。

HKDF-Expand-Label(Secret, Label, Value, OutputLength) = HKDF-Expand(Secret, HkdfLabel, OutputLength)

struct {
    uint16 length = OutputLength;
    opaque label<7..255> = "tls13 " + Label; // フィールドの長さが先頭に付く
    opaque value<0..255> = Value; // フィールドの長さが先頭に付く
} HkdfLabel;

picotls と Haskell tls も、OpenSSLの解釈を採用している。

TLS 1.3 開発日記 その19 OpenSSL

TLS Haskell

OpenSSLで、TLS 1.3を使う方法の覚書き。以下が参考になる。

ビルド

OpenSSL が現在サポートしているのは draft 20。そのソースの取り出し方はこう：

% git clone https://github.com/openssl/openssl.git

(修正：)draft 22のソースの取り出し方はこう：

% cd openssl
% git checkout -t origin/tls1_3-draft-22

ビルドの仕方はこう：

% ./config enable-tls1_3
% make
% make test

OpenSSL サーバ

s_server の使い方：

% cd util
% ./opensslwrap.sh s_server -accept 13443 -www -key $SOMEWHERE/key.pem -cert $SOMEWHERE/certificate.pem -curves X25519:P-256
  • ORTT を受けるには -early_data が必要。現時点で、-www とは両立しない。
% ./opensslwrap.sh s_server -accept 13443 -early_data -key $SOMEWHERE/key.pem -cert $SOMEWHERE/certificate.pem -curves X25519:P-256

OpenSSL クライアント

Full nego:

./opensslwrap.sh s_client -debug -connect 127.0.0.1:13443

HRR:

  • curves の先頭が keyshare となる。
./opensslwrap.sh s_client -debug -connect 127.0.0.1:13443 -curves P-521:P-256

PSK:

./opensslwrap.sh s_client -debug -connect 127.0.0.1:13443 -sess_out ticket
./opensslwrap.sh s_client -debug -connect 127.0.0.1:13443 -sess_in ticket

0RTT:

./opensslwrap.sh s_client -debug -connect 127.0.0.1:13443 -sess_out ticket
./opensslwrap.sh s_client -debug -connect 127.0.0.1:13443 -sess_in ticket -early_data $SOMEWHERE/early-data.txt

TLS 1.3 開発日記 その18 TLS 1.3 ID20

TLS Haskell

TLS 1.3 ID20に追従した。

やったのは、これだけ。

  • Shorten labels for HKDF-Expand-Label so that we can fit within one compression block

つまり、ラベルの文字列を変えただけ。現在、OpenSSLと相互試験中。

ちなみに、Haskell tls ライブラリの TLS 1.3 対応状況は、issue 167 にまとめてある。

追記：

サーバが early data を受け入れなかった場合、EndOfEarlyData は送ってはならず、従って Client Finished の計算に含めてはならない。