どさにっきキャッシュレス

by やまや
9月中旬

2019年9月20日(金)

アルゴリズムロールオーバーしてみた。

_ RFC8624 Algorithm Implementation Requirements and Usage Guidance for DNSSEC 曰く、

3.2.  DNSKEY Algorithm Recommendation

   Due to the industry-wide trend towards elliptic curve cryptography,
   ECDSAP256SHA256 is the RECOMMENDED DNSKEY algorithm for use by new
   DNSSEC deployments, and users of RSA-based algorithms SHOULD upgrade
   to ECDSAP256SHA256.
ということで、推奨されてる ECDSA 鍵が .jp でも 9/19から(やっと)対応したので鍵更新してみた。

_ 詳しい手順は RFC6781 と RFC7583 を読んでくださいませ。ぶっちゃけロールオーバー作業の細部なんてだいぶ忘れたし、ましてや初めてのアルゴリズムロールオーバーでかなり怪しかったりするけど、Knot DNS に乗り換えて完全にお任せしてるのであまり気にしなくても勝手にやってくれる。

_ まずは knot.conf を修正。

policy:
  - id: jp_ecdsa		# 新しいポリシー
    nsec3: on
    ksk-submission: jp
  - id: jp_rsasha256		# これまでのポリシー
    algorithm: rsasha256
    nsec3: on
    ksk-lifetime: 365d
    ksk-size: 2048
    zsk-size: 1024
    ksk-submission: jp
    cds-cdnskey-publish: none
zone:
  - domain: chigumaya.jp
    dnssec-signing: on
    dnssec-policy: jp_ecdsa	# ここを変更
ECDSAP256SHA256 がデフォルトなので、新しいポリシーではあえて明示していない。また、アルゴリズムを変更するだけでなく、以下の点も変更 ちなみに ksk-submission は「DS レコードが登録されたのを確認したら次の手順に進む」という作業を自動化するための設定で、これを設定しておくと DS 更新まわりがラクになる(今回が最後になるが)。詳しくは後述。

_ knotc conf-check してエラーがないことを確認したら knotc reload で反映。事前に鍵生成などの作業はしなくてよい。アルゴリズムが変わったことを検知して勝手に鍵を作って勝手にアルゴリズムロールオーバーがはじまる。

Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: control, received command 'reload'
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: reloading configuration file '/usr/local/etc/knot/knot.conf'
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing zone
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, algorithm rollover started
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 55776, algorithm ECDSAP256SHA256, KSK
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 15948, algorithm ECDSAP256SHA256, active+
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 65044, algorithm RSASHA256, KSK, public, active
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 10774, algorithm RSASHA256, public, active
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing started
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, successfully signed
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, next signing at 2019-09-17T17:55:23
Sep 17 16:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] zone file updated, serial 1568343751 -> 1568706923
鍵ごとに現在のステータスが記録されている。tag 55776 の鍵(KSK)は public とか active とか書いてなくて、ただ作っただけの状態。tag 15948 の鍵(ZSK)は active だから(DNSKEY 以外の)署名には使われるけど鍵自体は publish されておらず外からは見えない、はず。ほんとにそうなってるか dig って確認してみる。
% dig +noall +ans dnskey chigumaya.jp
chigumaya.jp.           2242    IN      DNSKEY  256 3 8 AwEAAb2dJ2ynrbCCYJkTLsf1CZUtsC72QBH/WZVE7XIrMrIbbe90RcwB AqWfPSBYYbdqJkrbEfikmxWxsQwH4eRio5l0idlhXqo+SeOyXpOdjx8d Z1GyBuwy8hwQsB4xM+5ydvTyB/k950sSzHar2h7VC2+ceRoml/KnjZSK 5SrvqNFV
chigumaya.jp.           2242    IN      DNSKEY  257 3 8 AwEAAZt3v64lrEhmX572QwKJI2D8TxM4XvJq02CALs7pE0FOyC3/lNb5 lzwg8tAcPQO90c1iSs3O9zm+FOAVP74QLi1tplCDog8+TmEDyfNLvpKq INAk0BDVDRiSlO/r90UafSOk6rQWPYK7DfzBHByoqiWdaIje05WyFtj8 oIZ6pHKiKtZaava471k+szphWi8fq73+aGtI5/ik5SgKI6xWWEwHBf2X bgo10jO/d59Cioxs8/NaUxTY0W9MGxi8q+9y3WBdmF//Z0DG7+ztWpoP GpPY1vdQzO0vjV8YlnEbApy7kN+/1Ujy8TkVI6BfDCf9yypgLPYFqJon kBXhT4BCySc=
% dig +noall +ans +dnssec chigumaya.jp
chigumaya.jp.           86400   IN      A       160.16.73.77
chigumaya.jp.           86400   IN      RRSIG   A 8 2 86400 20190927020231 20190913003231 10774 chigumaya.jp. A1HQYmpV4uEbgQk7n1czqIRavcaG8EnywwsYt3uHwdqbV7ybaK1hXYjz ZQh08wUXEZX4wq+ks+VfwAnLBU4N9g4RwlnERU3IuH3xnK0bAnveeyc8 bNQsfrZRoTOgGMOYqgeeb7Dg7agEubDhI5OM4LS8z6Rx05Vx+ir3YaCo MfA=
chigumaya.jp.           86400   IN      RRSIG   A 13 2 86400 20191001075523 20190917062523 15948 chigumaya.jp. /CF37jMkanyolNiHRs+zv0VqwqK73t2L+D5+Cv7yNvf+6nvCSgvadQra jH3TBSuU5hh6xFmyfUVHJTztkFgEeQ==
ということで、DNSKEY は更新前のアルゴリズム番号 8 の鍵だけ、それ以外のレコードに対する署名は新旧両方の鍵による署名が付与されていてログと一致する。鍵のステータスも同様に。
# keymgr chigumaya.jp list
6fcf6d0bd8190bae0b6444d00424f287cbebbdac ksk=no  zsk=yes tag=15948 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=0 ready=0 active=0 retire-active=0 retire=0 post-active=0 remove=0
a5ae4c186045c36d19014a8e7b2f110fe439b5a3 ksk=yes zsk=no  tag=65044 algorithm=8  size=2048 public-only=no  pre-active=0 publish=1538445746 ready=1538449346 active=1538485347 retire-active=0 retire=0 post-active=0 remove=0
c0c889cd7b9016269bd31587c611e75108eb1c9d ksk=yes zsk=no  tag=55776 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=0 ready=0 active=0 retire-active=0 retire=0 post-active=0 remove=0
cdf6b2aef9df6420dc5bd0cad1e8aee263ee0eb7 ksk=no  zsk=yes tag=10774 algorithm=8  size=1024 public-only=no  pre-active=0 publish=1567645351 ready=0 active=1567735351 retire-active=0 retire=0 post-active=0 remove=0
algorithm=13 が新規に作成された ECDSA の鍵で、publish も active も値が入ってない。8 はこれまでの RSA 鍵。

_ 1時間後。新旧の鍵が publish され、KSK も active になった。

Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing zone
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 55776, algorithm ECDSAP256SHA256, KSK, public, active+
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 15948, algorithm ECDSAP256SHA256, public, active+
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 65044, algorithm RSASHA256, KSK, public, active
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 10774, algorithm RSASHA256, public, active
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing started
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, successfully signed
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, next signing at 2019-09-18T18:55:23
Sep 17 17:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] zone file updated, serial 1568706923 -> 1568710523
ちなみに active と active+ の違いはよくわからん(調べろ)。KSK/ZSK ともに active かつ publish されたということは、新鍵が外から見えるようになって、その鍵による RRSIG も付与されてるはず。
% dig +noall +ans +dnssec chigumaya.jp dnskey 
chigumaya.jp.   83864 IN DNSKEY 256 3 8 AwEAAb2dJ2ynrbCCYJkTLsf1CZUtsC72QBH/WZVE7XIrMrIbbe90RcwB AqWfPSBYYbdqJkrbEfikmxWxsQwH4eRio5l0idlhXqo+SeOyXpOdjx8d Z1GyBuwy8hwQsB4xM+5ydvTyB/k950sSzHar2h7VC2+ceRoml/KnjZSK 5SrvqNFV
chigumaya.jp.   83864 IN DNSKEY 256 3 13 361vuxUWp5cUtlwayVHl7TXqdOWjEM0xBjKmVu3iWhoGDty75cMXckTI gvHsMbx6rbjRagB8fSGEhDvtzM0kGQ==
chigumaya.jp.   83864 IN DNSKEY 257 3 8 AwEAAZt3v64lrEhmX572QwKJI2D8TxM4XvJq02CALs7pE0FOyC3/lNb5 lzwg8tAcPQO90c1iSs3O9zm+FOAVP74QLi1tplCDog8+TmEDyfNLvpKq INAk0BDVDRiSlO/r90UafSOk6rQWPYK7DfzBHByoqiWdaIje05WyFtj8 oIZ6pHKiKtZaava471k+szphWi8fq73+aGtI5/ik5SgKI6xWWEwHBf2X bgo10jO/d59Cioxs8/NaUxTY0W9MGxi8q+9y3WBdmF//Z0DG7+ztWpoP GpPY1vdQzO0vjV8YlnEbApy7kN+/1Ujy8TkVI6BfDCf9yypgLPYFqJon kBXhT4BCySc=
chigumaya.jp.   83864 IN DNSKEY 257 3 13 RGNT++goDbzeT9tiPTo7cgooSJR5aprAsGHtr6zfPt4zqAT/2iq9bhnN mb59jeTe4K3Zei+myOPADRvvgh0tcw==
chigumaya.jp.   83864 IN RRSIG DNSKEY 8 2 86400 20191001085523 20190917072523 65044 chigumaya.jp. GEhis2G6g+OEcJ/2beuBZVlVEi2YwDXE9ELQTM1btQQyrXEU+A44pCRv I2rtDFZ3bH2nQb8KTkXrNr7ZIDlv0XRgRv5KweiGig3GRJOzyxAPBYTs DTRvYBurFAZp7BdLSdS/e+IYHd8fyWs+2fkSvd//zIKFvWe49ZwpobNI 2CQxMdk0+1nXUMS7ow6az5N/JBFLoRKailrSvbGAD2V4/9Nrwx318AAd n2c44tJ3IaFoJHnBWy7MWnrGgQIwIV+2VeBMQnBVngGzQnRvSd5FqBig v6zdinIUgD4YrU10Wu8aJvt+RDOWnWFXKSLE9n5gXdCeDpfsWajOuUCJ ye7rJw==
chigumaya.jp.   83864 IN RRSIG DNSKEY 13 2 86400 20191001085523 20190917072523 55776 chigumaya.jp. Wi9hYofK3WcP03nFbJp19bgTxgStdYYFKeTO/+Lyg0cOFCSDzZfTYsE/ M2aU5jzs/dAWVYu3bvn53LH/HD9gFA==
はい、そうなってますね。
# keymgr chigumaya.jp list
6fcf6d0bd8190bae0b6444d00424f287cbebbdac ksk=no  zsk=yes tag=15948 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=0 active=0 retire-active=0 retire=0 post-active=0 remove=0
a5ae4c186045c36d19014a8e7b2f110fe439b5a3 ksk=yes zsk=no  tag=65044 algorithm=8  size=2048 public-only=no  pre-active=0 publish=1538445746 ready=1538449346 active=1538485347 retire-active=0 retire=0 post-active=0 remove=0
c0c889cd7b9016269bd31587c611e75108eb1c9d ksk=yes zsk=no  tag=55776 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=0 active=0 retire-active=0 retire=0 post-active=0 remove=0
cdf6b2aef9df6420dc5bd0cad1e8aee263ee0eb7 ksk=no  zsk=yes tag=10774 algorithm=8  size=1024 public-only=no  pre-active=0 publish=1567645351 ready=0 active=1567735351 retire-active=0 retire=0 post-active=0 remove=0
こちらも ECDSA (alg=13) の鍵が publish されました。

_ 25時間経過。ゾーン内の最大 TTL (24時間) + 余裕をもって1時間、かな? 十分な時間がたって DS レコードを登録する準備ができました。

Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing zone
Sep 18 18:55:23 <daemon.notice> sakura knot[39674]: notice: [chigumaya.jp.] DNSSEC, KSK submission, waiting for confirmation
Sep 18 18:55:23 <daemon.notice> sakura knot[39674]: notice: [chigumaya.jp.] DNSSEC, KSK submission, waiting for confirmation
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 55776, algorithm ECDSAP256SHA256, KSK, public, ready, active
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 15948, algorithm ECDSAP256SHA256, public, active
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 65044, algorithm RSASHA256, KSK, public, active
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 10774, algorithm RSASHA256, public, active+
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing started
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, successfully signed
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, next signing at 2019-09-25T09:56:47
Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] zone file updated, serial 1568768207 -> 1568800523
新 KSK の登録準備が完了(ready)、確認待ち(waiting for confirmation) とログに出てる。
# keymgr chigumaya.jp list
6fcf6d0bd8190bae0b6444d00424f287cbebbdac ksk=no  zsk=yes tag=15948 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=0 active=1568800523 retire-active=0 retire=0 post-active=0 remove=0
a5ae4c186045c36d19014a8e7b2f110fe439b5a3 ksk=yes zsk=no  tag=65044 algorithm=8  size=2048 public-only=no  pre-active=0 publish=1538445746 ready=1538449346 active=1538485347 retire-active=0 retire=0 post-active=0 remove=0
c0c889cd7b9016269bd31587c611e75108eb1c9d ksk=yes zsk=no  tag=55776 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=1568800523 active=0 retire-active=0 retire=0 post-active=0 remove=0
cdf6b2aef9df6420dc5bd0cad1e8aee263ee0eb7 ksk=no  zsk=yes tag=10774 algorithm=8  size=1024 public-only=no  pre-active=0 publish=1567645351 ready=0 active=1567735351 retire-active=1568800523 retire=0 post-active=0 remove=0
こっちも KSK が reday に。また、RSA の ZSK がリタイア準備状態に。この後は人間が手作業でレジストラに DS 登録しにいくステップであり、自動化作業はいったん中断されるんだけど、Knot は CDS/CDNSKEY に対応しているので準備できたら自動でゾーンに DS を載せてくれる。ということで CDS を確認してみましょう。
% dig +noall +ans chigumaya.jp cds
chigumaya.jp.   0 IN  CDS 55776 13 2 71ADAAA442066E05A06BC03EEA348B6873B21FB3AB8D64B6BBAF64C6 39DC9152
わーい、載ってる。CDS に対応しているレジストリ/レジストラなら、CDS が存在するかどうか絶えず巡回してくれていて、見つけたら(一定の条件で)自動で登録してくれるはずなんだけど(RFC8078)、実際にそんなことをやってるのは .cz 以外に知らず、少なくとも .jp のレジストリも自分が使ってる指定事業者も対応してないのは確定なので、現実的には CDS に意味はない。ということで、手作業で DS 登録する必要があるのだが、.jp が ECDSA 鍵に対応するのは次の日からなのでそれまでこの状態で放置する。

_ DS 登録待ちの間、定期的にこういうログが出続けている。

Sep 18 18:55:23 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DS check, outgoing, remote 203.119.1.1@53, KSK submission attempt: negative
通常なら DS を登録したよ(人間様が作業するフェーズは終わったので自動化作業に戻ってね)、と指示をする必要があるのだが、Knot は賢いので登録が完了して DS がひける状態になってるかどうか自力でチェックして勝手にこちらからボールを奪っていく(ように設定することができる)。で、確認したけどまだ登録されてなかったよと報告するのがこのログ。これは以下のように設定する。
remote:
  - id: a.dns.jp
    address: [203.119.1.1, 2001:dc4::1]
submission:
  - id: jp
    parent: a.dns.jp
policy:
  - id: jp_ecdsa
    nsec3: on
    ksk-submission: jp
この例では登録されたかどうかチェックしにいく先を jp の権威サーバに設定しているが、手元のキャッシュサーバに聞きにいくようにすることもできる(その場合、キャッシュによって登録確認が数時間遅れることがある)。ksk-submission の設定をしない場合、DS 登録したら "knotc zone-ksk-submitted ゾーン名" というコマンドを叩いて教えてやる必要がある。

_ .jp の ECDSA 対応がはじまる 9/19 になった。新しい DS レコードを登録しにいく。DS 登録はレジストラ経由でおこなうので、レジストリが対応してもレジストラが対応してないと意味ないんだが、JPRS 直営の JPDIRECT はさすがに即日対応してた。無事登録を済ませて(ついでに住所その他が引っ越し前のものだったので変更して)、しばらく待つと新 DS が見えるようになった。

% dig +noall +ans chigumaya.jp ds +dnssec @a.dns.jp
chigumaya.jp.   7200  IN DS 55776 13 2 71ADAAA442066E05A06BC03EEA348B6873B21FB3AB8D64B6BBAF64C6 39DC9152
chigumaya.jp.   7200  IN RRSIG DS 8 2 7200 20191014174513 20190914174513 42078 jp. eOKVlx6p3OndUpzbZkzLWYRVtt9NmBF460LWY1u64d2REFhOjvUDkXRE JE7C0mnLuHzR4AdslG9vKpuM3V/AoSk8YJl9eVpWA9YVF1ttIPGIQ3Vp NdNrD/SUwgdSkH7Cgc+eLotfkCXehZX6z94n/kjntWRmphOpzz3Mqdz+ dvY=
RRSIG の署名アルゴリズムが 13 じゃなくて 8 (RSASHA256) なのはこちらのアルゴリズムロールオーバーとは無関係で、.jp 自体はこれまでどおり RSA 鍵で署名されてるからなので問題ない。

DNSViz で見た直後の鍵の状態。ロールオーバーはじめる前からキャプチャ撮っておけばよかった。

_ ふつーならここで DS 鍵登録終わったよー、自動作業に戻ってねー、と指示するんだけど、前述のようにそれをしなくても勝手に検知する設定を入れてるので待つだけ。

_ ということで待ちました。

Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DS check, outgoing, remote 203.119.1.1@53, KSK submission attempt: positive
Sep 19 10:55:24 <daemon.notice> sakura knot[39674]: notice: [chigumaya.jp.] DNSSEC, KSK submission, confirmed
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing zone
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 55776, algorithm ECDSAP256SHA256, KSK, public, active
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 15948, algorithm ECDSAP256SHA256, public, active
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 65044, algorithm RSASHA256, KSK, public, active+
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 10774, algorithm RSASHA256, public, active+
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing started
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, successfully signed
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, next signing at 2019-09-19T12:55:24
Sep 19 10:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] zone file updated, serial 1568800523 -> 1568858124
外から見える変化はないが、内部的には新しい KSK が上位ゾーン(.jp)に登録されたことを確認したので、旧 KSK をリタイアさせるためのフラグが立った。
# keymgr chigumaya.jp list
6fcf6d0bd8190bae0b6444d00424f287cbebbdac ksk=no  zsk=yes tag=15948 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=0 active=1568800523 retire-active=0 retire=0 post-active=0 remove=0
a5ae4c186045c36d19014a8e7b2f110fe439b5a3 ksk=yes zsk=no  tag=65044 algorithm=8  size=2048 public-only=no  pre-active=0 publish=1538445746 ready=1538449346 active=1538485347 retire-active=1568858124 retire=0 post-active=1568865324 remove=0
c0c889cd7b9016269bd31587c611e75108eb1c9d ksk=yes zsk=no  tag=55776 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=1568800523 active=1568858124 retire-active=0 retire=0 post-active=0 remove=0
cdf6b2aef9df6420dc5bd0cad1e8aee263ee0eb7 ksk=no  zsk=yes tag=10774 algorithm=8  size=1024 public-only=no  pre-active=0 publish=1567645351 ready=0 active=1567735351 retire-active=1568800523 retire=0 post-active=1568865324 remove=0
外から見える変化はないというのは厳密にはウソで、DS の登録が完了したので不要になった CDS/CDNSKEY がゾーンから取り除かれている(それにともなうゾーン再署名が実行されている)。

_ 2時間(DS TTL)経過。旧 DS がキャッシュから消えたので、旧 DNSKEY が新たに参照されることはなくなる。よって消す(alg=13 の鍵だけになる)。ただし、キャッシュが残ってる旧 DNSKEY をもとに署名検証される可能性はあるので、旧 DNSKEY による署名は残す。

Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing zone
Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 55776, algorithm ECDSAP256SHA256, KSK, public, active
Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 15948, algorithm ECDSAP256SHA256, public, active
Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 65044, algorithm RSASHA256, KSK
Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 10774, algorithm RSASHA256, active+
Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing started
Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, successfully signed
Sep 19 12:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, next signing at 2019-09-20T13:55:24
Sep 19 12:55:25 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] zone file updated, serial 1568858124 -> 1568865324
RSA 鍵のステータスから public が消えている(= 鍵を公開しない)が、ZSK はいまだ active で署名はされる。dig ってみてもたしかにそのとおりになっている。
% dig +noall +ans +dnssec chigumaya.jp dnskey
chigumaya.jp.           3260    IN      DNSKEY  257 3 13 RGNT++goDbzeT9tiPTo7cgooSJR5aprAsGHtr6zfPt4zqAT/2iq9bhnN mb59jeTe4K3Zei+myOPADRvvgh0tcw==
chigumaya.jp.           3260    IN      DNSKEY  256 3 13 361vuxUWp5cUtlwayVHl7TXqdOWjEM0xBjKmVu3iWhoGDty75cMXckTI gvHsMbx6rbjRagB8fSGEhDvtzM0kGQ==
chigumaya.jp.           3260    IN      RRSIG   DNSKEY 13 2 86400 20191003035524 20190919022524 55776 chigumaya.jp. /NFpFVc9wegekLxeXeii0SwDd5RIa+uTYKFV2aBllm0GZhyXPrQULyYH ICg9+qjOxMfqpX+OSVANIQDGQj1WlQ==
% dig +noall +ans +dnssec chigumaya.jp
chigumaya.jp.           3147    IN      A       160.16.73.77
chigumaya.jp.           3147    IN      RRSIG   A 8 2 86400 20191002005647 20190917232647 10774 chigumaya.jp. Q6COWx1FlZKiAHz58n6tmK3BEMIcvVWhvKcJqo3C9i3QZu6XlPXDMPX/ jezc44jBFDwcUb26sEE62vSeuyyZLHF5uUrZ+BKu9FtdqN0aln2bh+T9 ZSlQHcel4V4zi1WhFf0trSMAuWW/wEivxITyWETyOaV9GDBU4Y0ERx0S khk=
chigumaya.jp.           3147    IN      RRSIG   A 13 2 86400 20191002005647 20190917232647 15948 chigumaya.jp. eC3RJcKyAjyGgzBFhxB7wtshDULohi4dLLNtdmzyh/X9zrv1YpHpYbra JbqkToUxzTXcVplhdfUkv8c11VsiBw==
鍵のステータス。RSA 鍵に post-active のフラグが立った。
# keymgr chigumaya.jp list
6fcf6d0bd8190bae0b6444d00424f287cbebbdac ksk=no  zsk=yes tag=15948 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=0 active=1568800523 retire-active=0 retire=0 post-active=0 remove=0
a5ae4c186045c36d19014a8e7b2f110fe439b5a3 ksk=yes zsk=no  tag=65044 algorithm=8  size=2048 public-only=no  pre-active=0 publish=1538445746 ready=1538449346 active=1538485347 retire-active=1568858124 retire=0 post-active=1568865324 remove=0
c0c889cd7b9016269bd31587c611e75108eb1c9d ksk=yes zsk=no  tag=55776 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=1568800523 active=1568858124 retire-active=0 retire=0 post-active=0 remove=0
cdf6b2aef9df6420dc5bd0cad1e8aee263ee0eb7 ksk=no  zsk=yes tag=10774 algorithm=8  size=1024 public-only=no  pre-active=0 publish=1567645351 ready=0 active=1567735351 retire-active=1568800523 retire=0 post-active=1568865324 remove=0

_ 25時間後。古い DNSKEY による署名が削除される。ログからついに RSA 鍵の記述が消えた。

Sep 20 13:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing zone
Sep 20 13:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 55776, algorithm ECDSAP256SHA256, KSK, public, active
Sep 20 13:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, key, tag 15948, algorithm ECDSAP256SHA256, public, active
Sep 20 13:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, signing started
Sep 20 13:55:24 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, successfully signed
Sep 20 13:55:25 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] DNSSEC, next signing at 2019-09-25T09:56:47
Sep 20 13:55:25 <daemon.info> sakura knot[39674]: info: [chigumaya.jp.] zone file updated, serial 1568865324 -> 1568955324
keymgr が管理する鍵も ECDSA 鍵だけに。
# keymgr chigumaya.jp list
6fcf6d0bd8190bae0b6444d00424f287cbebbdac ksk=no  zsk=yes tag=15948 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=0 active=1568800523 retire-active=0 retire=0 post-active=0 remove=0
c0c889cd7b9016269bd31587c611e75108eb1c9d ksk=yes zsk=no  tag=55776 algorithm=13 size=256  public-only=no  pre-active=1568706923 publish=1568710523 ready=1568800523 active=1568858124 retire-active=0 retire=0 post-active=0 remove=0
dig っても ECDSA な RRSIG だけ。
% dig +noall +ans +dnssec chigumaya.jp
chigumaya.jp.           86400   IN      A       160.16.73.77
chigumaya.jp.           86400   IN      RRSIG   A 13 2 86400 20191002005647 20190917232647 15948 chigumaya.jp. eC3RJcKyAjyGgzBFhxB7wtshDULohi4dLLNtdmzyh/X9zrv1YpHpYbra JbqkToUxzTXcVplhdfUkv8c11VsiBw==
これにてアルゴリズムロールオーバー終了であります。

_ 長々と過程を記録してきたけど、基本的には変化していく状況を見守ってるだけで、実際に手を動かすのは最初の設定変更と DS 鍵登録の2回だけ。それ以外はすべて Knot が勝手にやってくれる。むちゃくちゃ楽ちん。定期的な KSK ロールオーバーももうやらないことにしたので(ルートゾーンの KSK だって8年使ったんだし、こんな泡沫サイトなんて鍵が漏洩した可能性が高い場合やアルゴリズムが危殆化しないかぎり放置してたって問題にならん)、今後必要な作業は ZSK のロールオーバーと定期的/ゾーン更新時の再署名だけ。これはどちらも完全自動化されてるので、つまり人間はもう何もしなくていいということ。DNSSEC がめんどくさいとかいうのはとっくに過去のものになっており、今は設定を書いたら以後放置プレイでいけるぐらい気楽にできるようになってる。

_ 宗教的な理由で DNSSEC が禁じられてるとか、改竄されても困らないドメインだから必要ないという人にまでやれというつもりはないけど、自動化できる環境がここまで揃ってるのに手間がかかるからとか複雑すぎるからとかいう理由で DNSSEC をやらないのは、もはや時代遅れの言い訳にすぎない。

_ 参考


2019年9月1日(日)

bash の危険な算術式

_ 使ってる人がいちばん多いだろうからタイトルでは bash としてるけど、ここで取り上げることは zsh および ksh 一族(本家 ksh、pdksh、mksh)にも該当する。ash、dash などでは該当しない。

_ 以下のシェルスクリプトには脆弱性がある。わかるだろうか。

#!/bin/bash
# "品目,単価,個数" の形式の CSV を読んで、"品目,合計金額" の形式で出力する
csv="foo.csv"
while IFS=, read item price num; do
    echo "$item,$((price*num))"
done < "$csv"
これ、細工された CSV ファイルを食わせることで、任意コードの実行ができてしまう。数ある脆弱性の中でもとくにヤバいやつだ。どこが穴なのかというと、タイトルにもあるとおり算術式なのだが、しかしこのスクリプトは $((price*num)) という単純な掛け算をしているにすぎない。いったいどこがマズいのだろうか。

_ 算術式の中では、変数の値は $ なしで参照することができる。

$ a=5
$ echo $((a))
5
これは POSIX で規定された動作。個人的にはこれだけでも十分以上に気持ち悪い動作なのだが、bash、zsh、ksh 一族では POSIX 仕様からの拡張で、さらに以下のようなことができる。
$ a=5
$ b=a
$ echo $((b))
5
算術式内にあらわれた $ なしの b は文字列ではなく変数名として扱われる。そして、$b の値が a であるから、それがまた変数名とみなされるのである。これは bash の独自拡張である間接展開とはまた異なる。

_ 間接展開(indirect expansion)とは以下のようなもの。

$ a=5
$ b=a
$ echo ${!b}
5
変数 $b の値が a なので、${!b} として $a の値すなわち 5 を返す、というもの。上の算術式とよく似ているが、もう1段増やすと違いが明瞭になる。
$ a=5
$ b=a
$ c=b
$ echo ${!c} $((c))
a 5
$c の値が b であるから、${!c} は $b の値である "a" を返す。しかし $((c)) は $b ⇒ $a ⇒ 5 のように参照される。算術式内に算術式として解釈される文字列が含まれている場合、再帰的に展開されるのだ。bash、zsh、ksh 一族の算術式は、再帰展開という拡張によって算術式だけでチューリング完全性を獲得している(再帰回数に制限があるので厳密にチューリング完全ではないが)。

_ ここまでの説明で、算術式が危険な罠だということがわかっただろうか。まだわからんか。

_ 以下のようなシェルスクリプト(hoge.sh)を考える。

#!/bin/bash
typeset -i n	# 変数 n を整数型に宣言(typeset は declare と同じ)
a=5
n="$1"
echo "$a"
スクリプトの第1引数を $n に代入してるだけ。$a は最初に代入された値をいじらずそのまま echo している、つまり 5 が出力されるはず。しかし、以下のように実行するとその予想と異なる結果になる。
$ ./hoge.sh a=10
10
変数 n は整数型に宣言されているため、n="$1" は「$1 を n に代入する」ではなく、「$1 を算術式として再帰評価した上でその結果を n に代入する」という動作になる。そして $1 の中身である "a=10" は算術式として正しいのでこの代入が実行されて、意図せず $a の値が破壊されてしまう。この例では $1 で値を受けてるけれど、read n のように標準入力から値を受けたり、n=$(hoge) のようにコマンドの実行結果を代入したりする場合でも、typeset -i (declare -i) で変数が整数型宣言されていればその値が算術式として再帰評価されることには変わりない。

_ あまり知られていないが、算術式内部から任意のコマンドを呼び出すことができる。上の hoge.sh を以下のように実行してみる。

$ ./hoge.sh 'x[$(whoami>&2)]'
yamaya
5
whoami が実行されてしまっている。このわけわかんないコマンド実行については こちらの解説を参照。この例では whoami はカレントシェルで実行されて、その標準出力(空文字列)が hoge.sh に渡されたわけ*ではない*ことに注意。これは sudo すれば明らか。
$ sudo ./hoge.sh 'x[$(whoami>&2)]'
root
5
whoami がカレントシェルで実行されてから sudo hoge.sh にその結果が渡されるのであれば、whoami の出力は root ではなく sudo する前のユーザ名(yamaya)になるはずである。sudo により hoge.sh が root 権限で実行され、その中で whoami が実行されるから root という結果になるのだ。仮に /etc/sudoers により sudo で hoge.sh 以外のコマンドを実行できないよう制限してあった場合でも、sudo で実行してるのはあくまで hoge.sh であって whoami を直接実行してるわけではないから制限をすり抜けてしまう。権限上昇の脆弱性ということだ(sudoers で制限してないならどうせどんなコマンドでも実行できちゃうので関係ない)。

_ 冒頭の CSV を処理するスクリプトでは、CSV ファイルに含まれる文字列を $((price*num)) のように算術式評価してしまっている。よって、foo.csv に

hoge,100,x[$(whoami>&2)]
のような行が含まれていると、そのコマンドが実行されてしまう。その他シェルスクリプトの用途としてログ処理に使うケースも多いかと思うが、外部からのログに含まれる文字列をうかつに算術式評価される文脈で扱うと脆弱性になりうるので十分に注意しなければならない。

_ $(( ... )) という算術式展開や typeset -i という整数型宣言だけではない。非常にわかりづらいが、以下も同じ脆弱性がある。

#!/bin/bash
if [[ $1 -eq 0 ]]; then
    a=0
else
    a=1
fi
[[ ... ]] という条件式構文で -eq や -le などの比較演算子が使われる場合、比較される値は暗黙に文字列ではなく算術式として評価される。よって、上のスクリプトの第1引数に算術式を食わせるとそれが評価されてコード実行につながる。bash や zsh では [[ ... ]] ではなく [ ... ] なら -eq や -le などを使っても算術式としては扱われず、数値以外の文字列ならエラーになるので、どうしても [[ でなければならない理由がなければ [ を使ったほうがよい。ksh 一族では [ ... ] や test を使う場合でも算術式展開されてしまうので注意。

_ そのほか、for(( expr1 ; expr2 ; expr3 )) というループ構文の各パラメータや(for i in ... という文なら算術式評価されない)、配列のインデックス(${a[x]} における x)、文字列の部分切り出しに使われる ${var:offset:length} の offset と length も暗黙的に算術式として評価される。

_ zsh の挙動が謎。

% declare -i n
% n='a=10'				# a=10 が実行される
% n=$(echo a=10)			# 実行される
% echo a=10 | read n			# 実行される
% n='x[$(whoami>&2)]'			# whoami は実行されない
% n=$(echo 'x[$(whoami>&2)]')		# 実行されない
% echo 'x[$(whoami >&2)]' | read n	# 実行されない
% n='n[$(whoami>&2)]'			# 整数型宣言した変数と配列変数名が一致した場合は実行される
算術式評価が実行される場合とされない場合があってよくわからん。bash はすべてのケースで実行される。

_ ash や dash などでは、算術式内に数値でなく文字列があらわれても再帰展開されずエラーになるので、外部からこういった文字列が入力されてコード実行されることはない。安全。

_ 外部から来た値をそのまま算術式評価してはならない。typeset -i していない変数にいったん文字列として代入し、その値が数字だけで構成されているかチェックし、問題ない場合だけ算術式評価するという手順を踏むように書かなければならない。

#!/bin/bash
typeset -i n
a="$1"
[[ $a =~ ^[0-9]*$ ]] && n=$a
念のため、ここで [[ ... ]] を使っているが、=~ (正規表現マッチ)は文字列として扱われ算術式評価はされない。

_ これ、極めて非直感的な挙動で、こういう問題があるということを知らなければ回避するコードを書くという発想にすら至らないのではないかと思うけど、いちおう bash などのシェルでは仕様どおりの動作。いくら仕様どおりの動作でも、仕様が脆弱なら脆弱性なんじゃねーの、ということで実は4月に IPA に報告してみた (*1)。が、「スクリプトを書く人が対処すべき問題であってシェルそのものの問題じゃないねー」ということで脆弱性扱いはしないという回答が先週になって返ってきた (*2)。うん、まあ、そう言われちゃうとそのとおりなんだよねぇ。しかたないねぇ。ということでスクリプトを書くみなさんが各自対処してください。

_ なお、IPA への報告後に気付いたが、この件は mksh では man でしっかり 警告されていた。警告するけど動作は修正しないってのも、IPA の回答と同じくスクリプトを書く側の問題であってシェルの問題ではないって立場だよね。

Warning: This also affects implicit conversion to integer, for example as done by the let command. Never use unchecked user input, e.g. from the environment, in an arithmetic context!
まあ、mksh なんて、使ってる人以前に知ってる人がそもそもいないよね。警告されても誰も気付かん。OpenBSD から folk した MirBSD という OS で /bin/sh として使われているシェル。MirBSD 以外でもコンパイルすれば動くけど、わざわざそれを使う気にはならんよなぁ。

_ 20190905追記: ksh 一族(ksh93, pdksh, mksh)では [[ ... ]] だけでなく [ ... ] や test を使う場合でも、-eq などの数値比較演算子では算術式展開がおこなわれることがわかったのでその旨修正した。また、zsh の謎の挙動について例を追加した。


(*1): 報告先に各シェル実装の開発元ではなく IPA を選んだのは、複数実装に同じ問題があって個別に連絡するのがクソめんどくさい(しかも pdksh のように public domain でどこに報告したらいいのかすら不明なものもある)から。
(*2): IPA に報告した時点では /etc/sudoers の制限を回避できる可能性があることに気づいておらず、IPA 側も権限上昇はできないという前提で判断している。が、「シェルが悪いんじゃなくてスクリプトが悪い」という判断に権限上昇は関係ないだろう。

2019年8月25日(日)

マンデルブロ集合

_ ひきつづきシェルスクリプトでお絵かきするよ。今度はシェルピンスキーのギャスケット以外のフラクタル図形を。

_ フラクタルの定番中の定番、マンデルブロ集合でございます。こんな画像。

_ 数学的な性質の詳細はともかく、ただお絵かきするだけなら wikipedia の説明だけで十分。アルゴリズムなんて高尚なものはなく、ひたすら式どおり地道に計算してドットを打つだけ。

_ ということで、上の画像を実際に出力するのに使ったワンライナーがこちら。つーか実質的に dc コマンドを一発叩くだけ(うしろにくっついてる convert は画像フォーマット変換のためのもので、PGM 形式を直接扱える画像ビューワがあるなら不要)。

dc -e'_2 _1.5 3 512 16 sDsSsWsYsXlD1-lSd[P2]f[lxd*lyd*-la+2lxly**lb+sysxlj1-dsj0!=tlj]sz[lxd*lyd*+4>z]st[0klilS~16klW*lS1-/lX+salW*lS1-/lY+sb0dsxsylDsjlzxpli1+dsilSd*!=m]sm0silmx'|convert - mandelbrot.png
残念ながら一部の Linux distro では dc という超絶ハイパーウルトラ便利なコマンドがデフォでインストールされないという暴挙としか言えない事態になっているので、全人類はいますぐインストールしなさい。

_ 念のため、dc の引数部分を読みやすく整形してコメントを付加したものを載せておく。

_2 _1.5 3 512 16 sDsSsWsYsX	# X=-2, Y=-1.5, W=3, S=512, D=16
lD1-lSd[P2]f			# PGM ヘッダ
# z: z^2+c
[
  lxd*lyd*-la+			# x=x^2-y^2+a
  2lxly**lb+			# y=2*x*y+b
  sysx
  lj1-dsj 0!=t			# --j != 0 ならマクロ t を実行
  lj				# push j
]sz
[
  lxd*lyd*+4>z			# 発散 (|z|<2) してなければマクロ z を実行
]st
# m: main loop
[
  0klilS~16k                    # i/512, i%512
  lW*lS1-/lX+sa                 # a=(i%512)*3/511-2
  lW*lS1-/lY+sb                 # b=(i/512)*3/511-1.5
  0dsxsylDsj lzx p		# x=y=0, j=16, exec "z", 結果出力
  li1+dsi lSd*!=m		# ++i != 512^2 && exec "m"
]sm
# run
0si lmx				# i=0, exec "m"
先頭の5つのパラメータを変更すると生成される画像が変わる。最初の _2, -1.5 は画像左上の複素座標で、その次の 3 という値を実軸、虚軸に加えたのが画像右下の座標。つまり、(-2-1.5i) - (1+1.5i) の範囲を描画するということ。次の 512 は生成する画像のサイズ、16 は収束したと判断して繰り返しを打ち切る回数で、これは生成されるグレースケール画像の depth としても使われる。

_ もうひとつ別バージョンのマンデルブロ集合描画スクリプト。

#!/bin/zsh
z='p=x*x-y*y-2+i/66.3,q=2*x*y+1.5-j/66.3,x=p,y=q,--d&&x*x+y*y<4&&z'
f(){ g;((i=0,++j<200))&&f;}
g(){ ((x=0.0,y=0.0,d=16,z));<<<$d;((++i<200))&&g;}
(<<<"P2 200 200 15";f)|convert - mandelbrot-zsh.png
PGM 形式画像の生成を zsh でおこなうシェル(だけ)スクリプト。それを PNG に変換する convert 以外は一切コマンドを呼んでない(zsh のビルトインすら使わない)。整数演算しかできない bash にこんな計算は無理だが、zsh は小数を扱えるのでこんなこともできちゃう。再帰の深さに制限があってデカい画像を作ろうとするとコケるが。

_ 昔書いた awk 版、Lua 版もどうぞ。

L-system

_ シェルピンスキーでも使った L-system はもっといろんな画像を作れるのでもうすこしいじってみる。

_ まずは うぃきぺにあるコッホ曲線の例

#!/bin/bash
L=$(m4<<'_END_'|tail -n1
define(`Lsystem', ``$1'
ifelse($2,0,,`Lsystem($1,decr($2))')')
define(`F', ``F + F - F - F + F'')
Lsystem(`F', 4)dnl
_END_
)
dir=(10,0 0,-10 -10,0 0,10)
path=$(eval $(echo $L | sed 's/[-+]/((&&i));/g;s/F/echo ${dir[i%4]};/g'))
convert -size 900x500 xc: -draw "fill none stroke black path 'm50,450 $path'"  koch.png
結果。

_ うーん、でも、コッホ曲線って、ふつーは直線を3等分してその真ん中を正三角形の2辺に置き替える、ってものじゃね? なんか俺が知ってるコッホ曲線と違う。つーことで、見慣れたコッホ曲線を描いてみる。せっかくなので直線ではなく三角形からスタートさせることでコッホ雪片に。

スクリプトのほうは m4 を sed に置き替えてる。やってることは同じ。
p=F--F--F--
for i in 1 2 3 4 5; do
  p=$(echo $p | sed 's/F/F+F--F+F/g')
done
dir=(2,0 1,-2 -1,-2 -2,0 -1,2 1,2)
path=$(eval $(echo $p | sed 's/[-+]/((&&i));/g;s/F/echo ${dir[i%6]};/g'))
convert -size 600x650 xc:white -draw "fill none stroke black path 'm300,0 $path'" koch-snowflake.png

_ 調子にのってもっとやってみる。

このルールを繰り返し適用すると以下の文字列が得られる。
A
AB
ABA
ABAAB
ABAABABA
ABAABABAABAAB
ABAABABAABAABABAABABA
ABAABABAABAABABAABABAABAABABAABAAB
前2つの文字列を連結したものが次の文字列になっていて、各文字列の長さは 1, 2, 3, 5, 8, 13, 21, 34, ... すなわちフィボナッチ数列になっている。こういう文字列を Fibonacci word (フィボナッチ列)と呼ぶらしい。

_ このフィボナッチ列を絵にしてみよう。AB はいずれも直進を示すものとする。 ただし、A の方には追加で以下のルールを適用する。

つまり ABAAB なら (直進左折)(直進)(直進左折)(直進右折)(直進) である。

_ スクリプトはこちら。

p=A
for j in {1..18}; do
  p=$(echo $p | sed 's/A/ab/g;y/B/a/;y/ab/AB/')
done
l=(3,0 0,-3 -3,0 0,3)
A="i+=++n%2?1:-1"	# A なら位置をインクリメントして奇数なら左折、偶数なら右折
B="++n"			# B ならインクリメントだけ
path=$(eval $(echo $p | sed 's/./echo ${l[i%4]};((&));/g'))
convert -size 800x800 xc: -draw "fill none stroke black path 'm50,650 $path'" fibonacci.png
実行すると以下の画像が得られる。fibonacci word fractal と呼ばれ、フィボナッチ数列の特徴が画像中にも見られるらしい。詳細は うぃきぺで。

_ その他 L-system によって生成される画像たち。クリプトは最適化されてだいぶ短かくなってるが、パラメータが異なるだけで、初期状態から置換ルールを数回適用し、得られた文字列を convert の描画コマンドに置き替えるという流れに変わりない。

_ ドラゴン曲線

l=(2,2 2,-2 -2,-2 -2,2)
p=FX
eval 'p=$(sed "s/X/x+yF+/g;s/Y/-Fx-y/g;y/xy/XY/"<<<$p);'{,,,,,,,,,,,}
convert -size 550x450 xc: -draw "fill none stroke black path 'm350,350 $(eval $(sed 's/[-+]/((&&i));/g;s/[FXY]/echo ${l[i%4]};/g'<<<$p))'" dragon.png

_ ヒルベルト曲線

l=(9,0 0,9 -9,0 0,-9)
p=A
eval 'p=$(sed "s/A/+bF-aFa-Fb+/g;s/B/-aF+bFb+Fa-/g;y/ab/AB/"<<<$p);'{,,,,,}
convert -size 600x600 xc: -draw "fill none stroke black path 'm15,15 $(eval $(sed 's/[-+]/((&&i));/g;s/F/echo ${l[i%4]};/g;s/[AB]//g'<<<$p))'" hilbert.png

_ ゴスペル曲線

l=(8,0 4,-7 -4,-7 -8,0 -4,7 4,7)
p=A
eval 'p=`sed "s/A/a-b--b+a++aa+b-/g;s/B/+a-bb--b-a++a+b/g;y/ab/AB/"<<<$p`;'{,,,}
convert -size 500x450 xc: -draw "fill none stroke black path 'm300,10 $(eval `sed 's/[-+]/((&&i));/g;s/[AB]/echo ${l[i%6]};/g'<<<$p`)'" gosper.png

_ ここまでは「直進」と「方向転換」だけで描画したのですべて一筆書き。一筆書き以外の画像を生成するには、「筆を離して別の位置に移動する」という描画ルールが必要になる。

_ ちうことで、以下のルールで絵を描いてみる。 出典はこちら。

[ は現在の位置と方向をスタックに push、] はスタックからの pop をあらわす。通過した場所を覚えておいて(push)、筆を離してその場所に戻ってくる(pop)ってこと。

_ このルールで次数ごとに異なる画像として描画し、さらにそれらを連結して GIF アニメにしてみるスクリプトが以下。実装上の理由により、スクリプト中で push/pop は [] ではなく <> になっている。

d=(-9 -10 -9 -7 -4 0 4 7 9 10 9 7 4 0 -4 -7)
p=X
for j in {1..5};{
  X=100;Y=750
  p=$(sed "s/F/FF/g;s/X/F+<<X>-X>-F<-FX>+X/g"<<<$p)
  convert -size 800x800 xc: -draw "stroke green $(eval $(sed 's/X//g;s/[-+]/((i&&));/g;s/F/echo line $X,$Y $[X-=d[(i+4)%16]],$[Y+=d[i%16]];/g;s/</S[++s]=\"X=$X;Y=$Y;i=$i\";/g;s/>/eval ${S[s--]};/g'<<<$p))" $j.gif
}
convert -delay 100 ?.gif fractalplant.gif
rm ?.gif

_ 結果。

草生えるwwwwwwwww

_ ペンローズタイルも L-system で記述できる。一連のお絵かきでこれがいちばんスクリプトのサイズがデカいが、それでも550バイトほど。描画する線の色をてきとーに変えてみた。

x=(21 34 34 21 0 -21 -34 -34 -21 0)
y=(29 11 -11 -29 -36 -29 -11 11 29 36)
M=red;N=blue;O=green;P=purple
X=300;Y=300
p='<N>++<N>++<N>++<N>++<N>'
eval 'p=$(sed "s/M/oA++pA----nA<-oA----mA>++/g;s/N/+oA--pA<---mA--nA>+/g;s/O/-mA++nA<+++oA++pA>-/g;s/P/--oA++++mA<+pA++++nA>--nA/g;s/A//g;y/mnop/MNOP/"<<<$p);'{,,,}
convert -size 600x600 xc: -draw "fill none $(eval $(sed 's/[-+]/((i&&));/g;s/[MNOP]/echo stroke $& line $X,$Y $[X+=x[i%10]],$[Y+=y[i%10]];/g;s/</S[++s]=\"X=$X;Y=$Y;i=$i\";/g;s/>/eval ${S[s--]};/g'<<<$p))" penrosetile.png
結果。

こんな複雑な非周期平面充填図形がたったこれだけのスクリプトで描けるとは。

カオスゲーム

_ カオスゲームでシェルピンスキーのギャスケットを描画するには、「点 P とランダムに選んだ三角形の頂点のひとつの中点を新たな P とする」という作業を何度も繰り返すというものだった。

_ これを三角形ではなく正方形にするとどうなるか。こうなる。

x=100;y=100
for i in {0..9999};do
  echo $[x=(x+RANDOM%2*200)/2] $[y=(y+RANDOM%2*200)/2]
done | awk '{t[$2*200+$1]=1} END{print "P1",200,200;for(;i++<200^2;)print t[i]?1:0}' | convert - chaos-sq.png

むっちゃランダム!

_ が、「同じ頂点を2回続けて選ばない」というルールを追加すると、こうなる。

x=250;y=250
for i in {0..29999};do
  while :; do t=$[RANDOM%4]; [ "$t" = "$r" ]||break; done; r=$t
  echo $[x=(x+r%2*500)/2] $[y=(y+r/2*500)/2]
done | awk '{t[$1+$2*500]=1} END{print "P1",500,500;for(;i++<500^2;)print t[i]?1:0}' | convert - chaos-sq2.png

むっちゃフラクタル!

_ この手順は

x(n+1) = a*x(n) + b*y(n) + e
y(n+1) = c*x(n) + d*y(n) + f
という関数を何種類か用意し、その関数のうちひとつをランダムに選択して適用する、と一般化できる。シェルピンスキーのギャスケットを描画するための「ある点と三角形の頂点の中点」なら a=1/2, b=0, c=0, d=1/2 で、e と f が (頂点の座標)/2 という関数を3セット分用意したものに相当する。

_ では、このパラメータを変えるとどうなるか。こうなる。 Bernsley fernと呼ぶらしい。

むっちゃシダ!

_ これを描画するのに使ったワンライナー。

dc -e'30000[0sa0sb0sc.16sd0sf]s1[.85sa.04sb_.04sc.85sd1.6sf]s2[.02sa_.26sb.23sc.22sd1.6sf]s3[_.15sa.28sb.26sc.24sd.44sf]s4[0k48271lr*2147483647%dsr8/100%9kl1xd1<2d87<394<4lalx*lbly*+dn32Plclx*ldly*lf++psysx1-d0<m]sm0dsxsy12345srlmx'|awk '{p[int($1*50)+int($2*50)*400+3e3]=1}END{print"P1",400,525;for(;i++<21e4;)print p[i]+0}'|convert - +level-colors green,black -flip fern.png
整数しか扱えない bash で小数の計算をさせるのはめんどくさいのでまた dc で。dc 部分をコメントつきで読みやすくしたもの。
30000				# ループ回数
[ 0sa 0sb 0sc .16sd 0sf ]s1	# 関数 f1-f4 のパラメータ(e は常に 0 なので略)
[ .85sa .04sb _.04sc .85sd 1.6sf ]s2
[ .02sa _.26sb .23sc .22sd 1.6sf ]s3
[ _.15sa .28sb .26sc .24sd .44sf ]s4
# メインループ
[
  0k 48271 lr* 2147483647 %dsr	# 疑似乱数列 (r*48271)%(2^31-1)
  8/ 100% 9k			# 得られた乱数を2桁に
  l1x				# f1
  d1<2				# 乱数が 1 より大きければ f2
  d87<3				# 87 より大きければ f3
  94<4				# 94 よろ大きければ f4
  lalx*lbly*+ dn 32P		# ax+by を計算して出力
  lclx*ldly*lf++ p		# cx+dy+f を計算して出力
  sysx				# 計算結果を新たな x, y に
  1-d0<m			# ループカウンタを減らして0より大きければはじめから
]sm
0dsxsy				# x=0, y=0
12345sr				# 乱数のシード
lmx				# マクロ m を実行


9月中旬
やまや