pythonのECDSA署名鍵読み込みが意外と雑だった

# はじめに

いきなりですが, [ECDSA](https://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9ADSA) という楕円曲線を使った署名技術が存在します[^2]. そして, 

```
$ python3 pip install ecdsa
```

で導入されるライブラリを使うと, pythonでECDSAの鍵生成や署名をはじめとして, DER/PEM形式での鍵のインポートやエクスポートも可能となります. 

今回いろいろあってこのあたりの構造を調べていたら, タイトルの通り署名鍵インポートが適当だったことが判明したので, 自分への備忘録も兼ねてこれを記している次第です. 

なお, はじめに断っておくとこれはバグではなく, ただ単に(それを承知の上で)実装されていないだけです. 

# 環境
```
$ python3 --version                     
Python 3.10.12

$ python3 -m pip list | grep ecdsa
ecdsa                  0.18.0
```

OSはUbuntu 22.04です.

# ECDSAライブラリの扱い方

[公式ドキュメント](https://pypi.org/project/ecdsa/#description) のUsageに一番最初に掲載されているサンプルコードを引用しています. 

```py
from ecdsa import SigningKey
sk = SigningKey.generate() # uses NIST192p
vk = sk.verifying_key
signature = sk.sign(b"message")
assert vk.verify(signature, b"message")
```

これをベースとして, 署名鍵`sk`とシグネチャ`signature`の中身を解析していきます.


# シグネチャの構造

```py
from ecdsa import SigningKey
sk = SigningKey.generate() # uses NIST192p
vk = sk.verifying_key
signature = sk.sign(b"message")

print(signature)
# b'`2f\x9e\xfb\x06\x98\x95(\xcbQ\xe3hG\xb3V\x8f\xe95:K\xbc\x1c\xb1h*5\x9c5as\xf8\xff\xe07\xda\x84\xb6\xe1\\j:\x023m\x9f!\x81'
```

上記のような48バイトのバイト列がシグネチャとして出力されます. 

しかし, ECDSAについて少しばかり知識がある人は (あるいは[Wikipedia](https://ja.wikipedia.org/wiki/%E6%A5%95%E5%86%86%E6%9B%B2%E7%B7%9ADSA#%E7%BD%B2%E5%90%8D%E7%94%9F%E6%88%90)のセクションを見た人は) シグネチャが $(r,s)$ の２ペアからなることに気づくと思います. 

これについては至ってシンプルで, 前半24バイトが$r$, 後半24バイトが$s$となります.
```py
r = signature[:len(signature)//2]
print(r)
# b'`2f\x9e\xfb\x06\x98\x95(\xcbQ\xe3hG\xb3V\x8f\xe95:K\xbc\x1c\xb1'

s = signature[len(signature)//2:]
print(s)
# b'h*5\x9c5as\xf8\xff\xe07\xda\x84\xb6\xe1\\j:\x023m\x9f!\x81'
```

# 署名鍵の構造
```py
from ecdsa import SigningKey
sk = SigningKey.generate() # uses NIST192p

print(sk.to_der())
# b'0_\x02\x01\x01\x04\x18\xe2\xc8\x87\x1cJ0\x92\x12\xca,\xa9L7\x13\x18.\x8a\xe4l[\xb0\xa7\x85\xb5\xa0\n\x06\x08*\x86H\xce=\x03\x01\x01\xa14\x032\x00\x04r\x8d\x88-\xaf\xea\x80\x15\xc7C\xe9\xb8\xdeo\xf7\x81\xb1\xf5+\xf3i>\x18\xda\xc6\x15T\x13\xc4t\xe5\xaa\x17#S\xaf\xbccE.\x9b7\x1c\xb8t\x13m\xd1'
```

上記のような97バイトのバイト列がDERフォーマットの署名鍵として出力されます. これを解析というかparseしていきます. 

前提として, これらは基本的に
1. `data`の属性情報 (1バイト)
2. `data`の長さ (1バイト[^1])
3. `data`本体 (可変長)

の3つを塊としたブロックから構成されています. 

属性情報については以下のような番号が割り振られています. `constructed`だけ`tag`というのが付与されていますが, それについては後ほど取り上げます. 

|属性|番号|
|---|---|
|`integer`|0x02|
|`bitstring`|0x03|
|`octet string`|0x04|
|`object`|0x06|
|`sequence`|0x30|
|`constructed`|0xa0 + `tag`|


## 0, 1バイト目
0バイト目は`0`, つまり0x30 -> `sequence`属性[^3]
1バイト目は`_`, つまり0x5f -> このあとに`sequence`属性のデータ[A]が95バイト続きます. 

![ecdsa_der_A.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/8978ba88-9e75-d5e3-0d2a-05450d9104a2.png)


## 2-4バイト目
2バイト目は0x02 -> `integer`属性
3バイト目は0x01 -> このあとに`integer`属性のデータ[B]が1バイト続きます. 
4バイト目は0x01 -> [RFC 5915](https://tex2e.github.io/rfc-translater/html/rfc5915.html) に準拠しているバージョンを表すデータで, ここでは1で固定です. 

![ecdsa_der_B.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/46f58201-7407-c48e-fd8f-f8f1d5e41185.png)


## 5-30バイト目
5バイト目は0x04 -> `octet string`属性
6バイト目は0x18 -> このあとに`octet string`属性のデータ[C]が24バイト続きます. 
7-30バイト目 -> ここにECDSAの秘密鍵(厳密には署名鍵)の情報が入っています. 特に圧縮等もされておらず, 生のデータでそのまま格納されています. 

![ecdsa_der_C.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/9b4390ad-78ee-5f73-1bc2-b414646e7862.png)

## 31-42バイト目
31バイト目は0xa0 -> `tag`に0がセットされた`constructed`属性(0xa0 + `tag`で計算された値が31バイト目に入っています). この`tag`は後述する楕円曲線の選定に関連するもので, 0で固定です.
32バイト目は`\n`, つまり0x0a -> このあとに`constructed`属性のデータ[D]が10バイト続きます. 
33-42バイト目 -> ここにどの楕円曲線を使用するかの情報(OID, Object Identifier)が入っています. ここは少し手を加えられているので以下でも少し取り上げます. 

![ecdsa_der_D.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/558a6bc0-ac6a-764d-bf64-d4263db013a3.png)


## 43-96バイト目 
43バイト目は0xa1 -> `tag`に1がセットされた`constructed`属性. この`tag`は検証鍵に関連するもので, 1で固定です.
44バイト目は`4`, つまり0x34 -> このあとに`constructed`属性のデータ[E]が52バイト続きます. 
45-96バイト目 -> ここに検証鍵が入っています. ここもまだ生データではないので後に詳しく触れます. 

![ecdsa_der_E.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/43132a3a-2d9e-d02c-e32e-c51f7708dc25.png)


## OIDについて
33-42バイト目の[D]セクションについてさらに見ていきます. ここには現在`\x06\x08*\x86H\xce=\x03\x01\x01`が格納されています. 

33バイト目は0x06 -> `object`属性
34バイト目は0x08 -> このあとに`object`属性のデータ[F]が8バイト続きます. 
35-42バイト目 -> [0x2a, 0x86, 0x48, 0xce, 0x3d, 0x03, 0x01, 0x01]

ここの解読がこの記事中で最も複雑な処理かもしれません. 
1. 基本的に各要素の下7ビットを出力
2. ただし, 要素が0x80以上であるならば, 次の要素の下位7ビットを末尾に結合する

がルールとなります. 当然, 2.で取り出した次の要素も再び0x80以上であれば, さらにその次の要素も取り出すことになります. 

したがって, 
* 35バイト目 -> 0x2a < 0x80なので, 下位7ビットの`0101010`を出力 -> 42
* 36バイト目 -> 0x86 >= 0x80なので, 下位7ビットの`0000110`と, **次の37バイト目の下位7バイトを結合する**
    * 37バイト目 -> 0x48 < 0x80なので, 下位7ビットの`1001000`を末尾に結合して`0000110_1001000`を出力 -> 840
* 38バイト目 -> 0xce >= 0x80なので, 下位7ビットの`1001110`と, **次の39バイト目の下位7バイトを結合する**
    * 39バイト目 -> 0x3d < 0x80なので, 下位7ビットの`0111101`を末尾に結合して`1001110_0111101`を出力 -> 10045
* 40-42バイト目 -> 下位7ビットを出力 -> (3, 1, 1)

よって, この35-42バイト目は(42, 840, 10045, 3, 1, 1)を意味することになります. 

さらに, 35バイト目の42には, `40 * first + second`の値が入っています. これを満たす組はいくつか存在しますが, 
```py
    assert 0 <= first < 2 and 0 <= second <= 39 or first == 2 and 0 <= second
```
という条件があります([ソースコード](https://github.com/tlsfuzzer/python-ecdsa/blob/master/src/ecdsa/der.py#L102)を参照). よって, `first = 1`, `second = 2`のみが該当します

以上をまとめると, (1, 2, 840, 10045, 3, 1, 1)が[F]セクションに格納されているOIDになります. なお, これは当然ながらデフォルトで選択される楕円曲線NIST192p ([ここ](https://github.com/tlsfuzzer/python-ecdsa/blob/master/src/ecdsa/curves.py#L322)から確認できます) のものと一致しています. 

![ecdsa_der_F.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/4c4cf441-5d7b-bba0-edb9-a7be5c10719a.png)


## 検証鍵について
45-96バイト目の[E]セクションについてさらに見ていきます. ここには現在`\x032\x00\x04r\x8d\x88-\xaf\xea\x80\x15\xc7C\xe9\xb8\xdeo\xf7\x81\xb1\xf5+\xf3i>\x18\xda\xc6\x15T\x13\xc4t\xe5\xaa\x17#S\xaf\xbccE.\x9b7\x1c\xb8t\x13m\xd1'`が格納されています. 

45バイト目は0x03 -> `bitstring`属性です. さて, 冒頭のほうで
> 前提として, これらは基本的に
> 1. `data`の属性情報 (1バイト)
> 2. `data`の長さ (1バイト[^1])
> 3. `data`本体 (可変長)
> 
> の3つを塊としたブロックから構成されています. 

と言いましたが, `bitstring`属性は例外で, 以下のような構造となっています. 
1. `data`の属性情報 (1バイト)
2. `data` + `encoded_unused`の長さ (1バイト)
3. `encoded_unused`本体 (1バイト)
3. `data`本体 (可変長)

特にパラメータを設定しない場合, `encoded_unused = 0`です. したがって, 改めて45バイト目からの構造を追ってみると, 

45バイト目は0x03 -> `bitstring`属性
46バイト目は'2', つまり0x32 -> このあとに`bitstring`属性のデータ[G]と, `encoded_unused`が計50バイト続きます. 
47バイト目は0x00 -> デフォルトの`encoded_unused`
48-96バイト目にデータ本体[G]が入っています

![ecdsa_der_G.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/38dddfc7-6775-970b-5a7e-0b461cd6954b.png)

さらに[G]の構造を見ていきましょう. データは`\x04r\x8d\x88-\xaf\xea\x80\x15\xc7C\xe9\xb8\xdeo\xf7\x81\xb1\xf5+\xf3i>\x18\xda\xc6\x15T\x13\xc4t\xe5\xaa\x17#S\xaf\xbccE.\x9b7\x1c\xb8t\x13m\xd1`です. 

この先頭の0x04は`octet string`属性ではなく, 楕円曲線上の点の表現を圧縮するかどうかを表しています. 
特に指定しない場合, デフォルトでは`uncompressed`が選択されるようになっており, その場合
```py
        elif encoding == "uncompressed":
            return b"\x04" + self._raw_encode()
```
という感じで`\x04` + (検証鍵の$x$座標) + (検証鍵の$y$座標)となっています ([ソースコード](https://github.com/tlsfuzzer/python-ecdsa/blob/master/src/ecdsa/ellipticcurve.py#L482) 参照). したがって, 
* 48バイト目は0x04 -> `uncompressed`を意味
* 49-72バイト目 -> 検証鍵の$x$座標
* 73-96バイト目 -> 検証鍵の$y$座標

となります. 
![ecdsa_der_H.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334637/3c688865-697a-4bbe-ff1d-cf1480de100d.png)

# 署名鍵の読み込み
```py
from ecdsa import SigningKey
sk = SigningKey.generate() # uses NIST192p

sk2 = SigningKey.from_der(sk.to_der())
```
署名鍵をDER形式でインポートする場合, `from_der`を使います. この挙動を追うのが本題となります. 
該当するソースコードは [ここ](https://github.com/tlsfuzzer/python-ecdsa/blob/master/src/ecdsa/keys.py#L983) で, 以下にコメント部分をカットしたものを掲載します

また, `!!!REDACTED!!!`となっている箇所はとても長いのですが, 今回の場合だとこのif文に突入することがないのでバッサリ省略しています. この部分についても少し触れます. 

```py
def from_der(cls, string, hashfunc=sha1, valid_curve_encodings=None):

        s = normalise_bytes(string)
        curve = None

        s, empty = der.remove_sequence(s)
        if empty != b(""):
            raise der.UnexpectedDER(
                "trailing junk after DER privkey: %s" % binascii.hexlify(empty)
            )

        version, s = der.remove_integer(s)

        if der.is_sequence(s):
            !!!REDACTED!!!

        if version != 1:
            raise der.UnexpectedDER(
                "expected version '1' at start of DER privkey, got %d"
                % version
            )

        privkey_str, s = der.remove_octet_string(s)

        if not curve:
            tag, curve_oid_str, s = der.remove_constructed(s)
            if tag != 0:
                raise der.UnexpectedDER(
                    "expected tag 0 in DER privkey, got %d" % tag
                )
            curve = Curve.from_der(curve_oid_str, valid_curve_encodings)


        if len(privkey_str) < curve.baselen:
            privkey_str = (
                b("\x00") * (curve.baselen - len(privkey_str)) + privkey_str
            )
        return cls.from_string(privkey_str, curve, hashfunc)
```

さて, このparserを上から見ていきます.
## 6行目
```py
        s, empty = der.remove_sequence(s)
```
`sequence`属性情報[A]を取り出して`s`に格納

## 12行目
```py
        version, s = der.remove_integer(s)
```
RFC5915準拠のバージョン情報[B]を取り出し, 残りを`s`に格納. 
## 14行目
```py
        if der.is_sequence(s):
```

この時点で残っている`s`の先頭は署名鍵に関する`octet string`属性情報であり, `sequence`属性情報ではありません. したがって, 今回であれば14行目のif文がTrueになることはありません. 

## 23行目
```py
        privkey_str, s = der.remove_octet_string(s)
```
署名鍵[C]を取り出し, 残りを`s`に格納

## 25-26行目 

```py
        if not curve:
            tag, curve_oid_str, s = der.remove_constructed(s)
```

`curve = None`のままなので25行目のif文に突入. OIDに関するデータ[D]を取り出し, 残りを`s`に格納

さて, 26行目で[D]を取り出して以降, 残った54バイト分の`s`が呼ばれることがないのです. この`s`には検証鍵に関するデータが入っていて, RFC5915にも
> ```
>    ECPrivateKey ::= SEQUENCE {
>      version        INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),
>      privateKey     OCTET STRING,
>      parameters [0] ECParameters {{ NamedCurve }} OPTIONAL,
>      publicKey  [1] BIT STRING OPTIONAL
>    }
>       The fields of type ECPrivateKey have the following meanings:
> ```

とあり, 検証鍵(public key)は`OPTIONAL`であることが読み取れます. なので, 署名鍵を生成するにあたって必ず必要になる情報でないのは事実なのですが, この部分が正しいかどうかの検証はなされていません. 

さて, 後出しじゃんけんのようになって申し訳ないですが, 

> 以下にコメント部分をカットしたものを掲載します

と書いた割には, 実は25行目のif文を抜けた先に, 以下のようなコメントがあります. 

```py
        # we don't actually care about the following fields
        #
        # tag, pubkey_bitstring, s = der.remove_constructed(s)
        # if tag != 1:
        #     raise der.UnexpectedDER("expected tag 1 in DER privkey, got %d"
        #                             % tag)
        # pubkey_str = der.remove_bitstring(pubkey_bitstring, 0)
        # if empty != "":
        #     raise der.UnexpectedDER("trailing junk after DER privkey "
        #                             "pubkeystr: %s"
        #                             % binascii.hexlify(empty))

```

ただ, いずれにせよフォーマットに則った形式かどうかをチェックしているだけで, 「検証鍵と署名鍵のペアが正しいかどうか」のチェックはなされていません. つまり, 属性情報などを除いた検証鍵の生データが格納されている末尾48バイトには何をセットしてもよく, 
```py
from ecdsa import SigningKey
sk = SigningKey.generate() # uses NIST192p

sk_pollute = sk.to_der()[:-48] + b'\xff' * 48

sk2 = SigningKey.from_der(sk_pollute)
```
であれば, 上記のコメントアウトが仮になかったとしても`sk2`は正しい署名鍵として認識されます. 


# おわりに
一度`from_der()`が呼ばれてしまえば, 末尾が書き換えられても正しい鍵として扱われるので, これ単体ではまぁ大丈夫なんでしょうけどモヤモヤがありますね…

ヤバいシナリオを無理やりこじつけるなら, callerが`from_der()`を呼び出す前にdatabaseに保存している署名鍵と全く一致しているかどうかをチェックする機構を持っていたけど, 通信路上で末尾が書き換えられてFRR(本人拒否率)が上がるとかですか…


[^1]: 自分でDERフォーマットの署名鍵を作る際は, `data`が256バイト以上になることもありますが, このセクションでは1バイトに限定して話を進めていきます
[^2]: 残念ながらECDSAそのものの詳細については取り上げません. 
[^3]: 数字の`0`という文字はASCIIでは0x30に対応しています. 0x00ではないので注意を.