zkat’s diary

技術ブログ

MerkleTreeLeafをパースしようとしているけどうまくいかない

概要

Certificate Transparencyで用いられるデータ構造の一つであるMerkleTreeLeafを分解しようとしたのですが、 うまくいかないことがあったのでメモ（雑記）します。解決してません。

MerkleTreeLeafについて

CTログサーバーへget-entriesすることで取得できるデータ構造です。
応答データのjsonの、leaf_inputキーの値としてBase64エンコードされてデータが入っています。

tools.ietf.org

パースしてみる

適当なログサーバー(Testtube)から適当に拾ってきたデータを用いてみます。
base64をデコードしてhexdumpしてみます。 MTとかLETは、適当に自分が短縮した表現ですが、それぞれMercleLeafTypeと、LogEntryTypeを表しています。

00000000  00 00 00 00 01 48 8c b0  85 72 00 01 ba 9a 47 17  |.....H...r....G.|
          ^^ ^^ ^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^ ^^^^^^^^^^^
         Ver MT       Timestamp           LET     Issuer
00000010  2b d3 21 8c 73 39 09 e9  64 d4 f8 1e 62 60 65 a3  |+.!.s9..d...b`e.|
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                             Key Hash
00000020  cf c8 99 fc 65 cb 8e 96  b4 73 35 8d 00 02 1a 30  |....e....s5....0|
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^ ^^
              Rest of Issuer Key Hash           ?????   TBSCertificate
00000030  82 02 16 a0 03 02 01 02  02 04 07 5b cd 15 30 0d  |...........[..0.|
00000040  06 09 2a 86 48 86 f7 0d  01 01 0b 05 00 30 70 31  |..*.H........0p1|
00000050  0b 30 09 06 03 55 04 06  13 02 47 42 31 19 30 17  |.0...U....GB1.0.|
00000060  06 03 55 04 0a 13 10 41  73 63 65 72 74 69 61 20  |..U....Ascertia |
00000070  4c 69 6d 69 74 65 64 31  27 30 25 06 03 55 04 0b  |Limited1'0%..U..|
00000080  13 1e 41 73 63 65 72 74  69 61 20 53 6f 66 74 77  |..Ascertia Softw|
00000090  61 72 65 20 44 69 73 74  72 69 62 75 74 69 6f 6e  |are Distribution|
000000a0  31 1d 30 1b 06 03 55 04  03 13 14 41 44 53 53 20  |1.0...U....ADSS |
000000b0  53 61 6d 70 6c 65 73 20  54 65 73 74 20 43 41 30  |Samples Test CA0|
000000c0  1e 17 0d 31 34 30 39 31  39 30 36 35 32 35 31 5a  |...140919065251Z|
000000d0  17 0d 32 30 30 31 31 35  30 36 35 32 35 31 5a 30  |..200115065251Z0|
000000e0  55 31 12 30 10 06 03 55  04 03 13 09 54 65 73 74  |U1.0...U....Test|
000000f0  20 43 65 72 74 31 0f 30  0d 06 09 2a 86 48 86 f7  | Cert1.0...*.H..|
00000100  0d 01 09 01 16 00 31 12  30 10 06 03 55 04 0b 13  |......1.0...U...|
00000110  09 54 65 73 74 20 55 6e  69 74 31 1a 30 18 06 03  |.Test Unit1.0...|
00000120  55 04 0a 13 11 54 65 73  74 20 4f 72 67 61 6e 69  |U....Test Organi|
00000130  7a 61 74 69 6f 6e 30 81  9f 30 0d 06 09 2a 86 48  |zation0..0...*.H|
00000140  86 f7 0d 01 01 01 05 00  03 81 8d 00 30 81 89 02  |............0...|
略
000001f0  04 16 04 14 fb 22 4b dd  be 5b 72 65 48 12 4b cb  |....."K..[reH.K.|
00000200  7e bb 46 04 18 19 41 bc  30 13 06 03 55 1d 25 04  |~.F...A.0...U.%.|
00000210  0c 30 0a 06 08 2b 06 01  05 05 07 03 01 30 09 06  |.0...+.......0..|
00000220  03 55 1d 13 04 02 30 00  30 1f 06 03 55 1d 23 04  |.U....0.0...U.#.|
00000230  18 30 16 80 14 3a f1 05  c1 0c 07 f9 25 8f 80 72  |.0...:......%..r|
00000240  b7 95 ea 93 50 89 7d f0  17 00 00                 |....P.}....     |

なぜこのように対応づけられると考えるかというと、RFC 6962をはじめとするRFCに以下のように データ構造が定義されているからです。

MerkleTreeLeaf

struct {
    Version version;
    MerkleLeafType leaf_type;
    select (leaf_type) {
        case timestamped_entry: TimestampedEntry;
    }
} MerkleTreeLeaf;

Version

enum { v1(0), (255) }
         Version;

MerkleLeafType

enum { timestamped_entry(0), (255) }
  MerkleLeafType;

TimestampedEntry

struct {
    uint64 timestamp;
    LogEntryType entry_type;
    select(entry_type) {
        case x509_entry: ASN.1Cert;
        case precert_entry: PreCert;
    } signed_entry;
    CtExtensions extensions;
} TimestampedEntry;

LogEntryType

enum { x509_entry(0), precert_entry(1), (65535) } LogEntryType;

PreCert;

struct {
    opaque issuer_key_hash[32];
    TBSCertificate tbs_certificate;
} PreCert;

TBSCertificate

   TBSCertificate  ::=  SEQUENCE  {
        version         [0]  EXPLICIT Version DEFAULT v1,
        serialNumber         CertificateSerialNumber,
        signature            AlgorithmIdentifier,
        issuer               Name,
        validity             Validity,
        subject              Name,
        subjectPublicKeyInfo SubjectPublicKeyInfo,
        issuerUniqueID  [1]  IMPLICIT UniqueIdentifier OPTIONAL,
                             -- If present, version MUST be v2 or v3
        subjectUniqueID [2]  IMPLICIT UniqueIdentifier OPTIONAL,
                             -- If present, version MUST be v2 or v3
        extensions      [3]  EXPLICIT Extensions OPTIONAL
                             -- If present, version MUST be v3
        }

疑問

45バイト目から3バイト存在する、00 02 1aの値は一体何を表しているのかよく分かりませんでした。
状況的には、後続のデータ（TBSCertificate 1 ）のサイズを表していそうではあります。

その他

仮に45バイト目以降の3バイトがサイズであったとして、正しく、後続のTBSCertificateの値がとれたとしても、 それをいい感じにパースする仕組みがない気がするので、そもそも、leaf_inputの値を愚直に分解していく必要がない気がしてきました。 LogEntryTypeをみて、extra_dataのほうをパースするのがうまくいくかもしれません。 extra_dataのほうには、おなじみのASN.1形式をDERエンコードした証明書が入っているようなので。

補足

DERのエンコーディングに0x00は存在しないので、DER以外の別のものであることが分かります。 調べていると、以下の情報が見つかりました。

“0x00” isn’t a valid tag in DER. What is this? It’s TLS encoding. This is defined in RFC 5246, section 4 (the TLS 1.2 RFC). TLS encoding, like ASN.1, has both a way to define data structures and a way to encode those structures. TLS encoding differs from DER in that there are no tags, and lengths are only encoded when necessary for variable-length arrays.

letsencrypt.org

TLS encodingについて理解すればうまくパースできそうな気がします。

  1. TBSとは、to be signedの略の様で、署名対象のデータを表しているようです。↩