Vagrant上でubuntu/xenial32, ubuntu/xenial64が動作しない(続)

前回の記事の続き.trustyと同レベルには解決した.

環境(再掲)

Host:

Guest:

症状(再掲)

Vagrantubuntu/xenial64(あるいはubuntu/xenial32)を起動すると

  • 起動後まもなく,root filesystemがread-onlyになる
  • 動いている間も動作が遅い

ログファイルを見ると,次のようなメッセージが得られた.

  • sd 2:0:0:0: [sda] tag#7 Medium access timeout failure. Offlining disk!
  • sd 2:0:0:0: rejecting I/O to offline device
  • Buffer I/O error on device
  • Buffer I/O error on device sda1, logical block 249088

ubuntu/trusty64などではこの症状は発生しない.

原因

ディスクコントローラの「ホストのIOキャッシュを使う」が無効になっているためである.

  • ubuntu/trusty64に対して,この設定を無効化した所,症状が再現した.
  • 逆にubuntu/xenial64に対して,この設定を有効化した所,症状が発生しなくなった.

ホストのIOキャッシュを無効にするとストレージとの通信が高確率で失敗するということになるため,やはりVirtualBoxにはバグがあると考えられるが,vagrant上でubuntu/xenial64を安定して利用するという目的はとりあえずこれで達成できる.

解決策

起動時の設定でhostiocacheを有効にする.Vagrantfileに以下の設定を追加する.

  config.vm.provider "virtualbox" do |vb|
    vb.customize ["storagectl", :id, "--name", "SCSI Controller", "--hostiocache", "on"]
  end

Vagrant上でubuntu/xenial32, ubuntu/xenial64が動作しない

追記: 原因と解決策は次の記事にある.

環境

Host:

Guest:

症状

Vagrantubuntu/xenial64(あるいはubuntu/xenial32)を起動した所,

  • 起動後まもなく,root filesystemがread-onlyになる
  • 動いている間も動作が遅い

という症状に遭遇した.

ログファイルを見ると,

[  105.513000] sd 2:0:0:0: [sda] tag#7 Medium access timeout failure. Offlining disk!
[  108.734234] sd 2:0:0:0: rejecting I/O to offline device
[  108.793265] sd 2:0:0:0: rejecting I/O to offline device
[  108.793318] blk_update_request: I/O error, dev sda, sector 1994752
[  108.793323] Buffer I/O error on device sda1, logical block 249088
[  108.793326] Buffer I/O error on device sda1, logical block 249089
[  108.793327] Buffer I/O error on device sda1, logical block 249090
...

となり,sdaへのアクセスがタイムアウトしたことによりディスクを切り離してしまい,その後一切のアクセスができなくなっている.

ubuntu/trusty64などやVitualBoxに直接Ubuntu Serverをインストールした場合は発生しない症状である.

Workaround 1

I/Oがタイムアウトする,ということでVMの起動直後に,sdaのタイムアウトの調整を試みたところ,タイムアウトからread-onlyになる症状は発生しなくなった.

sudo sh -c 'echo 120 > /sys/block/sda/device/timeout'

しかし,ディスクI/Oが時々,極めて時間がかかる.次の記録は/dev/urandomから256MB読んでファイルに書き込む操作を繰り返した際のものであるが,2回目のみ長時間かかっている.そもそもddとtimeの報告している時間が一致していない.

ubuntu@ubuntu-xenial:~$ time dd if=/dev/urandom of=./file bs=1M count=256
256+0 records in
256+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 29.5976 s, 9.1 MB/s

real	0m29.623s
user	0m0.000s
sys	0m17.756s
ubuntu@ubuntu-xenial:~$ time dd if=/dev/urandom of=./file bs=1M count=256
256+0 records in
256+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 174.663 s, 1.5 MB/s

real	6m26.321s
user	0m0.004s
sys	0m17.716s
ubuntu@ubuntu-xenial:~$ time dd if=/dev/urandom of=./file bs=1M count=256
256+0 records in
256+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 33.1649 s, 8.1 MB/s

real	0m33.195s
user	0m0.000s
sys	0m17.620s

Workaround 2

ubuntu/trusty64と異なりubuntu/xenial64では,SATAコントローラではなくSCSIコントローラが用いられていることに気づいた.

ubuntu/trusty64

ubuntu/xenial64

VirtualBoxの設定画面からSCSIコントローラを削除し,SATAコントローラに変更した所,タイムアウトからread-onlyになる症状は発生しなくなった.

ワークアラウンドとして,vagrant boxのbox.ovfを書き換えてSATAコントローラを利用する方法も検討した.

--- .vagrant.d/boxes/ubuntu-VAGRANTSLASH-xenial64/20160429.0.0/virtualbox/box.ovf.orig	2016-05-02 22:24:42.490411586 +0900
+++ .vagrant.d/boxes/ubuntu-VAGRANTSLASH-xenial64/20160429.0.0/virtualbox/box.ovf	2016-05-02 22:33:01.721795537 +0900
@@ -79,11 +79,12 @@
       </Item>
       <Item>
         <rasd:Address>0</rasd:Address>
-        <rasd:Description>SCSI Controller</rasd:Description>
-        <rasd:ElementName>SCSI Controller 0</rasd:ElementName>
+        <rasd:Caption>sataController0</rasd:Caption>
+        <rasd:Description>SATA Controller</rasd:Description>
+        <rasd:ElementName>SATA Controller 0</rasd:ElementName>
         <rasd:InstanceID>3</rasd:InstanceID>
-        <rasd:ResourceSubType>VirtualSCSI</rasd:ResourceSubType>
-        <rasd:ResourceType>6</rasd:ResourceType>
+        <rasd:ResourceSubType>AHCI</rasd:ResourceSubType>
+        <rasd:ResourceType>20</rasd:ResourceType>
       </Item>
       <Item>
         <rasd:Address>1</rasd:Address>

しばらく動作させると停止する事こそ無いものの次のようなエラーメッセージがdmesgに出力されていた.

[  138.725547] ata3.00: exception Emask 0x0 SAct 0x7f00013c SErr 0x0 action 0x6 frozen
[  138.767307] ata3.00: failed command: WRITE FPDMA QUEUED
[  138.767783] ata3.00: cmd 61/00:10:00:d0:1f/08:00:00:00:00/40 tag 2 ncq 1048576 out
                        res 40/00:00:00:00:00/00:00:00:00:00/00 Emask 0x4 (timeout)
[  138.769023] ata3.00: status: { DRDY }
...
[  141.449344] ata3: hard resetting link
[  141.773423] ata3: SATA link up 3.0 Gbps (SStatus 123 SControl 300)
[  141.773579] ata3.00: configured for UDMA/133
[  141.773583] ata3.00: device reported invalid CHS sector 0
[  141.773584] ata3.00: device reported invalid CHS sector 0
...
[  141.773604] sd 2:0:0:0: [sda] tag#1 FAILED Result: hostbyte=DID_OK driverbyte=DRIVER_TIMEOUT
[  141.773606] sd 2:0:0:0: [sda] tag#1 CDB: Write(10) 2a 00 00 1f 80 00 00 08 00 00
[  141.773608] blk_update_request: I/O error, dev sda, sector 2064384
[  142.050589] EXT4-fs warning (device sda1): ext4_end_bio:329: I/O error -5 writing to inode 56795 (offset 0 size 8388608 starting block 258304)
[  142.050592] Buffer I/O error on device sda1, logical block 257792
...

Workaround 1と同様,ディスクI/Oが時々,極めて時間がかかる.次の記録は/dev/urandomから256MB読んでファイルに書き込む操作を繰り返した際のものである.Workaround 1と比較すると,時間がかかる処理の割合は増えているようだ.

ubuntu@ubuntu-xenial:~$ time dd if=/dev/urandom of=./file bs=1M count=256
256+0 records in
256+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 281.666 s, 953 kB/s

real	5m45.765s
user	0m0.000s
sys	0m17.744s
ubuntu@ubuntu-xenial:~$ time dd if=/dev/urandom of=./file bs=1M count=256
256+0 records in
256+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 170.685 s, 1.6 MB/s

real	4m21.259s
user	0m0.000s
sys	0m18.000s
ubuntu@ubuntu-xenial:~$ time dd if=/dev/urandom of=./file bs=1M count=256
256+0 records in
256+0 records out
268435456 bytes (268 MB, 256 MiB) copied, 48.634 s, 5.5 MB/s

real	2m57.844s
user	0m0.000s
sys	0m17.620s

まとめ

タイムアウトや速度低下が発生する症状から,ゲストOSとVirtualBoxの間のHDDの通信が消失するなどしている可能性が考えられる.

二つのワークアラウンドにより最低限動作させることは出来るようになったが,未だ根本的な解決はできていない.

追記: 原因が判明したため,解決策を次の記事に掲載した.

Firefox 34に更新してからタブやセッションの復元機能などが壊れた

先日,Firefox 34に更新してからというもの,複数あるマシンで次の症状が生じた。

  • 「最近閉じたタブ」や「以前のセッションを復元」がグレイアウト
  • FireGestureからタブの複製を行おうとすると次のエラーを得る
([Exception... "Default view is not tracked" nsresult: "0x80070057 (NS_ERROR_ILLEGAL_VALUE)" location: "JS frame :: resource:///modules/sessionstore/SessionStore.jsm :: ssi_duplicateTab :: line 1547" data: no])

プロファイルのディレクトリの中のファイルを消しては起動を繰り返して壊れているファイルの特定を試みた。その結果prefs.jsにある browser.startup.homepage の設定を削除することで回復することが分かった。

検証が終わってから再度調査したところ http://forums.mozillazine.jp/viewtopic.php?f=2&t=15133 にも browser.startup.* を削除したところ回復したという報告が見つかった。一度回復すると browser.startup.homepage を設定しなおしても再現しないので,この設定が存在しない状態で起動した際にどこかのデータが再生成されることによって回復するのではないかと推測される。

ぷららIPv6へGNU/Linuxから接続

家の回線は長らく光ネクストではなくBフレッツだったためにネイティブなIPv6サービスが受けられなかった*1が,ついにBフレッツが廃止され光ネクストに移行された*2のでISPIPv6サービスを利用してみることにした。

環境

ファイアウォール

手始めに,忘れずIPv6用のファイアウォールを整備しておく。IPv4と違ってNAPTが間に入らないため設定を忘れると危険である。
/etc/iptables/rules.v6 *3:

*filter
:INPUT-SERVICES - 
-A INPUT -i lo -j ACCEPT
-A INPUT -p ipv6-icmp -j ACCEPT
-A INPUT -p udp --dport 546 --sport 547 -s fe80::/10 -d fe80::/10 -j ACCEPT
-A INPUT -m state --state ESTABLISHED,RELATED -j ACCEPT
-A INPUT -j INPUT-SERVICES
-A INPUT -j DROP
...

UDP 546はDHCPv6でIPアドレスを取得するために必要になる。ipv6-icmpを無条件に受け入れて良いかは要検討。

PlalaIPv6接続サービス

さて,PlalaのIPv6接続サービスのページを見ると利用のためにIPv6トンネル対応アダプタなる専用機器が必要だと書いてあるが,今回の目的はこの専用機器を利用せずにGNU/Linux上で構成することである。NetBSDにおける設定例をHachulog: NetBSDでぷららのIPv6を利用するで見つけることができたので,ありがたくこれを参考にさせて頂いて設定を行った。

記事によれば,PPPoEセッションをもうひとつ張って,DHCPv6でPrefixを取得するとのことである。順に設定していく。

PPPoEセッション

pppoeconfコマンドで設定を行った。
ログインIDはhttp://www.plala.or.jp/ipv6/access/flow/にあるように,ユーザIDの後に契約コースによって@v6h.plala.or.jpか@v6m.plala.or.jpを加えたものとなる。

pppoeconfコマンドによって設定が生成されると,/etc/network/interfacesにインターフェイスが追加される。

iface dsl-provider inet ppp
pre-up /sbin/ifconfig br0 up # line maintained by pppoeconf
provider dsl-provider

br0となっているのは仮想マシン用のブリッジを用意しているためなので,通常の環境ではeth0と読み替えてよい。
また,/etc/ppp/peers/dsl-providerにPPPの設定が配置される。

名前が気に入らないので各種リネームをした。

  • mv /etc/ppp/peers/dsl-provider /etc/ppp/peers/plala-ipv6
  • /etc/ppp/pppoe_on_boot の内容修正
  • /etc/network/interfacesの修正
    • iface ppp0 inet ppp
      • 名前をppp0に合わせるとifup/ifdownで
    • provider plala-ipv6

このままではppp0上でIPv6通信ができないので,/etc/ppp/peers/plala-ipv6に次の行を追加した。

+ipv6

これによりppp0にリンクローカルアドレスが割り当てられて,PPPoEの相手とIPv6で通信できるようになる。

以上の設定でPPPoE接続を行った。

$ sudo ifup plala-ipv6

DHCPv6

続いて,wide-dhcpv6-clientパッケージをインストールした。ppp0インターフェイスに限って動作するように/etc/default/wide-dhcpv6-clientに

INTERFACES="ppp0"

を設定した。
/etc/wide-dhcpv6/dhcp6c.confに次の設定を行った。

interface ppp0 {
  send ia-pd 0;
  request domain-name-servers;
  script "/etc/wide-dhcpv6/dhcp6c-script";
};

id-assoc pd 0 {
  prefix-interface br0 {
    # xxxx:xxxx:xxxx:xx00::/64
    sla-id 0;
    sla-len 8;
  };
};

ルーティング

IPv6のデフォルトルートが設定されていないため,ppp0をデフォルトルートに設定した。

$ sudo ip -6 route add default dev ppp0

とりあえずはこれで通信できるようになる。

自動でデフォルトルートを設定するために,https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=477245を参考にPPPoEの接続が終わったタイミングで上記コマンドを実行するようにした。
/etc/ppp/ipv6-up.d/routing:

#!/bin/sh
if [ -z "${CONNECT_TIME}" ]; then
	if [ "${PPP_IPPARAM}" = "ipv6default" ]; then
		ip -6 route add default dev ${PPP_IFACE}
	fi
fi

/etc/ppp/peers/plala-ipv6 には次の行を追加した。

ipparam ipv6default

なお,pppd側ではなく/etc/network/interfacesのpost-upでデフォルトルートの追加を行うと,タイミングによってPPPoE接続が終わる前のまだppp0インターフェイスが存在しない状態でpost-upが実行されることがある。

DNSサーバ

dhcp6cがresolvconfに対応しており接続時に自動でresolv.confに追加されるが,ifdownした時には削除されないため修正した。
/etc/wide-dhcpv6/dhcp6c-ifupdown:

--- dhcp6c-ifupdown.orig	2014-08-04 08:15:08.875772378 +0900
+++ dhcp6c-ifupdown	2014-08-04 08:15:11.771745142 +0900
@@ -12,6 +12,7 @@
 
 case $MODE in
     start|stop)
+        [ "$MODE" = "stop" ] && /sbin/resolvconf -d $IFACE
         for i in $INTERFACES ; do
             if [ "$IFACE" = "$i" ] ; then
                 /usr/sbin/dhcp6ctl $MODE interface $IFACE

備考

今回は内部ネットワークへの広告やフォワーディングは行わなかった。

GNU/Linux(CUPS)からWindows 7経由でLinuxに対応していないプリンタに印刷する

以前設定したLinux対応していないプリンタであるが,どうにも用紙サイズエラーで止まってしまうケースが多く使い物にならない。

一台,サーバになるWindows 7機があったので,これに中継させることにした。
参考にしたのは

あたりである。

Mac OSに対応していない(ドライバがない)プリンタを、Windows機を経由して利用する方法 - joker8phoenix's diaryを参考に途中まで設定していたのであるが,なんということだろうか,Windows XP時代には搭載されていたと思しきLPDサーバ機能がクライアント用OSであるWindows 7からは削除されたという。

仕方ないのでここはsmb経由で印刷することに妥協して設定を行った。
Ghostscript, RedMon, Acrobat Distiller 5.0J用 プリンタ定義ファイル, Adobe PS Printer DriverをインストールするところはMac OSに対応していない(ドライバがない)プリンタを、Windows機を経由して利用する方法 - joker8phoenix's diaryとほぼ同じである。ただし,作成した"Acrobat Distiller J"プリンタにRPT1:ポートを追加し構成する際に管理者権限を要することに注意する必要がある。管理者権限でプリンタのプロパティを開いていないと,

ポートの構成中にエラーが発生しました。 操作を完了できませんでした (エラー 0x00000001)。

というエラーメッセージで失敗することになる。プリンタのプロパティを管理者権限で開くためには,コマンドプロンプト管理者として実行し

rundll32 printui.dll,PrintUIEntry /p /n "Acrobat Distiller J"

を実行した。(他に方法はないのだろうか)

そして,"TCP/IP Print Server"をインストールして起動する代わりにプリンタの共有を行っい,クライアント側もsmb経由でアクセスするように構成した。クライアント側(Ubuntu 14.04)ではドライバとしてGeneric > Generic PostScript Printer [en]を選択した。以上の設定により,実際に印刷できることを確認した。

Writeup: EBCTF 2013 - Challenge CRY300 “Curves”(時間内に解けなかった)

時間内に通せなかったが、最後のわからなかった部分が後でわかったのでとりあえず書いておく。

アクセスすると最初に指定された8bytesで始まる64bytesの16進文字列で、md5が0000で始まるものを要求される。なお、この値はこれ以降使っていないので、サーバの負荷を調整するためのものだろうか。

import sys
import hashlib
def hashcash(cash):
    i = 0
    while True:
        resp = "%s%056x" % (cash, i)
        if hashlib.md5(resp).hexdigest().startswith('0000'):
            break
        i += 1
    return resp

print hashcash(sys.argv[1])

続いてパスワードを聞かれる。service.py中にハッシュ化されたパスワードがあるが、検索すれば簡単に元のパスワードがわかる。括弧内はアクセスレベルである。

  • f56334fbe02eaa05218c31b01a80f2f6 (0): Hotz
  • 00b37cb56bb57705348610253b1b82e4 (0): Bushing
  • 6fa95b1427af77b3d769ae9cb853382f (0): Peter
  • 58cd57027cf126fcc9bd93dea9d74c1a (0): Segher
  • f1cd318e412b5f7226e5f377a9544ff7 (1): Kevin
  • 98c131f9fb31f732b136f87e64ff686a (1): Butler
  • 6f3249aa304055d63828af3bfab778f6 (2): 31337

アクセスレベル2のユーザはそのままフラグが表示され、アクセスレベル1のユーザはECDSAで追加の認証が必要となる。しかし、パスワードに数字は許されていないためLevel 2のところへはアクセスできない。その認証トークンをLevel 0のものについて1000個集めたものが captured-sessions.txt である。

認証トークンは全体が一つのECDSA署名である。base64でデコードした後、16進文字列に変換して、先頭64文字がr、後半64文字がsとなる。 これがtoken(パスワードのmd5)の署名となっていれば良い。

さて、Level 0用の認証トークンを作るために用いられたget_ephemeral_keyを見ると、ランダムでなければならないkの空間がやけに小さい。

def get_ephemeral_key():
        k = ""
        while len(k) < 32:
                k += hashlib.md5(seed + str(random.randint(0,255))).digest()
        return int(k.encode('hex'),16)

md5は16bytesなので、kの空間は65536通りしか無い。1000個も集めれば十分に衝突していることが期待される。これはDSA/ECDSAの有名な誤用である。

ECDSAの仕様から、kの値が同じなら、rの値が等しくなるので、そのような認証トークンをcaptured-sessions.txtから探した。二つkが同じ認証トークンの組があることが分かる。

$ awk '{print $2}' captured-sessions.txt | perl -MMIME::Base64 -lpe '$_ = encode_base64(substr(decode_base64($_),0, 32)); s/\n//g' | sort | uniq -c | awk '$1 != 1 {print}'
      2 KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdOg=
      2 g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHk=
      2 wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5w=

$ grep -F KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdO captured-sessions.txt 
Bushing KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdOiU66IYqtYejrnlwpfYdr4079fFeLM4RC5ni4P9JF+4Tw==
Bushing KVKN3KKUwmAMMDUC9QrKvBmPyu2h5tkqCqRG7NTjdOiU66IYqtYejrnlwpfYdr4079fFeLM4RC5ni4P9JF+4Tw==

$ grep g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxH captured-sessions.txt 
Hotz g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w==
Bushing g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w==

$ grep -F wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv captured-sessions.txt 
Hotz wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xCxqlIuZkMQDSpRWffZGG4NdkaOvAfttTtQuCaJZonxA==
Bushing wNpp5moxL1+Z0I40PJQCC/LegcOQocP+8Y9GV7Mv+5xiKYZxm648bajMuJ9Dy1SyHEpu/MBHkViuCM4P9Fd78Q==

Wikipediaに書かれている式からプログラムを書いたが、この問題、公開鍵が与えられていないのでまだ群の位数(n)がわかっていない。

import hashlib
import ecdsa
import base64

n = 0 # Unknown

z  = int(hashlib.md5("Kevin").hexdigest(), 16)
z1 = int(hashlib.md5("Hotz").hexdigest(), 16)
z2 = int(hashlib.md5("Bushing").hexdigest(), 16)
t1 = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w=="
t2 = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w=="

def parse_security_token(sig):
    tmp = base64.b64decode(sig).encode('hex')
    return (int(tmp[:64],16), int(tmp[64:],16))

def sig_security_token(r, s):
        rhex = "%064x" % r
        shex = "%064x" % s
        return base64.b64encode(rhex.decode('hex') + shex.decode('hex')) 

(r1, s1) = parse_security_token(t1)
(r2, s2) = parse_security_token(t2)
assert r1 == r2
r = r1
k = ((z1 - z2) * ecdsa.inverse_mod(s1 - s2, n)) % n
dA = ((s1 * k - z1) * ecdsa.inverse_mod(r, n)) % n
s = (ecdsa.inverse_mod(k, n) * (z + r * dA)) % n
print sig_security_token(r, s)

さらに言えば楕円曲線もまだ決定できていないので、まず楕円曲線を決定することにした。
ecdsa.pyとservice.pyよりy^2 \equiv x^3 - 3x + b \;\pmod{p}で表される楕円曲線であることがわかる。bとpの値が未知である。
service.pyの先頭で楕円曲線上の点が3つ与えられていることに注目した。

#some points that really should be on the curve we're going to use
_Gx = 0x337ef2115b4595fbd60e2ffb5ee6409463609e0e5a6611b105443e02cb82edd8L
_Gy = 0x1879b8d7a68a550f58166f0d6b4e86a0873d7b709e28ee318ddadd4ccf505e1aL

_Qx = 0x2a40fd522f73dc9f7c40b2420e39e62c5742ff2f11805a1577ed7f60153a0be1L
_Qy = 0x3085e99246006b71b4211eff47ff3efc0f93103ee7379dc3bcc6decdc46073a3L

_Rx = 0xbd0a442367bdc24cb09c49404e3d307ba99122e7b78e14f0d84870d0df97aa59L
_Ry = 0x22c88612db6b6af6f196cd815fc5f57fe871d3b6588b0c7a59e06cc759d736b2L

C_i = y_i^2 - x_i^3 + 3x_iとおき、\gcd(c_1 - c_2,\, c_2 - c_3)からpの値を決定した。

b = 28285296545714903834902884467158189217354728250629470479032309603102942404639
p = 89953523493328636138979614835438769105803101293517644103178299545319142490503

これでbとpを決定することができたが、まだ必要な位数がわかっていない。結局、この計算を行うプログラムを探しまわっている途中でタイムアップとなった。



終了後、PARI/GPで計算できることに気づいた。

$ gp
? b = 28285296545714903834902884467158189217354728250629470479032309603102942404639
? p = 89953523493328636138979614835438769105803101293517644103178299545319142490503
? E = ellinit([0, 0, 0, -3, b])
? allocatemem(1000000000)
? n = ellgroup(E, p)
%4 = [89953523493328636138979614835438769106005948670998555217484157791369906305783]

サーバはもう停止してるので通るか確認できない……

Writeup: EBCTF 2013 - Challenge CRY200 “One to many”

タイトルは"1対多"でいかにもRSAの同一平文だし、実際に中国人の剰余定理からも計算できたそうですが、別の解法を。

\gcd(n_k,\, (\prod n_i)/n_k)を計算するとn_763, n_3821が互いに素ではないことがわかる。よって共通の素数pをgcd(n_763, n_3821)から求めることができてnの素因数分解ができた。

eの値がまだ不明だが、id:k_operafanさんにとりあえず65537を試してみよと言われて、試したら当たってしまった。怖い。あとは普通にRSAの鍵を作って計算するだけである。

import Crypto.PublicKey.RSA as RSA
from Crypto.Util.number import *

e = long(65537)

def read_message(filename):
    with open(filename) as f:
        n = int(f.readline()[2:-1])
        c = int(f.readline()[14:-1])
    return n, c

n, c = read_message("files/message%d.txt" % 763)
n2, c2 = read_message("files/message%d.txt" % 3821)
p = GCD(n, n2)
q = n/p
d = inverse(e, (p-1)*(q-1))
m = RSA.construct((n, e, d)).decrypt(c)
print long_to_bytes(m)
This is a secret message, for your eyes only: ebCTF{b517aba29f132c52c9426a177952a2d8}

複数の解法を用意してるのだろうか。