Hatena::ブログ(Diary)

あどけない話

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)

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

2017-09-08

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                     /
    /                                               /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

CLASSTTL の意味が変わっている。

昔の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...                  /
    +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

2017-07-20

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

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の解釈を採用している。