2018-06-08

ROCAと離散対数問題

Security

ROCA

原論文はhttps://acmccs.github.io/papers/p1631-nemecA.pdfです。

RSALibで生成された素数を利用したRSA暗号に関する脆弱性です。

RSALibで生成される素数の特徴

本記事では512bitの例を扱います。RSALibで生成される素数は次のような形をしています。

$p = kM + \mathrm{pow}(65537, a, M)$

$\mathrm{pow}(e, a, M)$ は $M$ を法とした $e$ の $a$ 乗を表します。ここで、 $M = P_{39}\#$ は素数を小さい順に39個かけ合わせた数です。

$p$ を決定するパラメータは37bitの $k$ および62bitの $a$ だけで、99bitの空間しかなく、512bitの素数全体の空間にくらべ非常に小さいです。

さて、この特徴をもつ素数から生成される公開鍵 $n = p \cdot q$ は次の特徴をもちます。

（特徴）合同式 $n \equiv 65537 ^ x (\mathrm{mod} M)$ が解 $x$ をもつ

$n \equiv 65537 ^ x (\mathrm{mod} M)$ を解く

本来離散対数問題を解くのはとてもむずかしいのですが、この場合は手元のPythonでも数秒もかからず解けてしまいます。

方針はシンプルで、まず $M = P_{39}\# = \prod p_i$ となる各 $p_i$ に対しもとの方程式を分解して

$n \equiv 65537^{x_i} (\mathrm{mod} p_i)$

の形の連立合同式にします。

それぞれの合同式は全探索することに簡単に解けます。 $p_i$ は非常に小さいですから、 $x_i$ を0から $p_i - 1$ まで動かしてみて、 $n$ と合同になるものを調べていきます。なお、そのような $x_i$ が見つからなかった場合、もとの方程式にも解がないことになりますので、その場合 $n$ はRSALibによって生成された素数からなる公開鍵ではありません。

$x_i$ が見つかったとします（ $a_i$ と置きましょう）。次に、65537の位数を調べます。つまり、 $65537^{q_i} \equiv 1 (\mathrm{mod} p_i)$ となるような最小の $q_i$ を探します。 $q_i$ は巡回群の性質より必ず存在し、合同式の解は $x_i = a_i + m \cdot q_i$ の形で一般化されます。

$q_i$ を探す作業もたかだか $p_i$ 回の探索で見つかるので十分高速です。

これらの合同式をそれぞれ解き、最後に中国剰余定理により連立合同式の解が一般に求められます。 $q_i$ が合成数のとき、中国剰余定理が使えないと思うかもしれませんが、 $q_i$ の各素因数について、 $x_i = a_i + m \cdot q_i$ の $q_i$ をそれぞれの素因数に置き換えた合同式が成り立つので、これらで代用すれば中国剰余定理が使えます。

$x = a + m \cdot q$

という形になったとします。しかしこの $x$ はすべてが

$n \equiv 65537 ^ x (\mathrm{mod} M)$

を満たすとは限りません。なぜなら $q$ が $M$ に比べて小さいからです。しかし、 $m \sim 1000$ ぐらいまでにはもとの合同式を満たす $x$ にヒットするので順番に $m$ を変えていくことでもとの方程式の解を簡単に調べることができます。

混乱しやすいポイント

連立合同式

$n \equiv 65537^{x_i} (\mathrm{mod} p_i)$

を解くとき、法 $p_i$ について中国剰余定理を使うと思いがちですが、 $x_i$ は法 $q_i$ に関して決まるので、ここに注意してください。また、 $q_i$ どうしは一般に互いに素とは限りませんから、中国剰余定理の結果得られる解 $x$ は $M = P_{39}\#$ よりずっと小さい法に関して決まります。

より大きな入力での離散対数問題

ROCAでは、それぞれの合同式を解く際に全探索でも十分高速ですが、全探索が難しくなってくると、Baby-step Giant-stepアルゴリズムや、Pohlig-Hellmanアルゴリズムが活躍するようになってきます。

参考文献

RSA鍵生成脆弱性ROCAの紹介

2018-05-26

sudo時にユーザ環境のファイルを実行する

Infrastructure

まあ要はsudo時のパスをどうにかしたいという話。 PythonとかRubyを使う人は多分一度は経験するんじゃないでしょうか。

$ sudo visudo

secure_pathに参照したいパスを追加します。

2018-05-26

EC2でユーザ権限でのrbenvインストール

Application Programming Infrastructure

$ sudo yum update -y
$ sudo yum groupinstall "Development Tools" -y

言語を変えておきます（rbenvのインストールに直接影響はないですが、日本語とか文字化けするので）。

$ sudo vim /etc/environment
LANG=en_US.utf-8
LC_ALL=en_US.utf-8

$ git clone https://github.com/sstephenson/rbenv.git ~/.rbenv
$ echo 'export PATH="$HOME/.rbenv/bin:$PATH"' >> ~/.bash_profile
$ echo 'eval "$(rbenv init -)"' >> ~/.bash_profile
$ source ~/.bash_profile
$ git clone git://github.com/sstephenson/ruby-build.git ~/.rbenv/plugins/ruby-build
$ cd ~/.rbenv/plugins/ruby-build
$ sudo ./install.sh
$ sudo yum install -y openssl-devel readline-devel
$ rbenv install 2.4.2
$ rbenv global 2.4.2

2018-05-26

CircleCIで自動デプロイ

Application Programming

circle.ymlを用意します。

machine:
  ruby:
    version: 2.4.2

test:
  override:
    - /bin/true

deployment:
  production:
    branch: master
    commands:
      - ruby deploy.rb

デプロイに使うだけなので、テストを/bin/trueに置き換えます。ruby deploy.rbに相当する部分はシェルスクリプトでいいんですが、現代っ子なのでRubyで書きます。

仕組みを説明すると、CircleCIのコンテナから上記コマンドが実行されるので、コンテナからリモートサーバへSSHでログインして、プログラムを最新に置き換えてあげるといったことをすればいいです。なので、リモートサーバのpemをCircleCIに登録してあげる必要があります。

CircleCIのプロジェクトのSettingsからSSH Settingsみたいなのがあった気がするので、そこにいって鍵を登録します。ホスト名はIPアドレスにしました。

deploy.rbを以下のように書きます。EC2にログインすることを想定して、ユーザー名はec2-userにしておきます（各自のものにしてください）。

IP = 'xxx.xxx.xxx.xxx'
KEY = "id_#{IP}"

puts "ssh -i ~/.ssh/#{KEY} ec2-user@#{IP} 'bash -s' < commands.sh"
res = `ssh -i ~/.ssh/#{KEY} ec2-user@#{IP} 'bash -s' < commands.sh`
if res['exit=0'].nil?
  exit(1)
end

commands.shはリモートで実行するコマンドです。

source ~/.bash_profile && \
cd プロジェクトのディレクトリ && \
git fetch && git reset --hard origin/master && \
必要があればサーバの停止など && \
必要があればdependencyのインストールなど && \
必要があればビルドなど && \
必要があればサーバの再起動など ; \
echo exit=$?

&&と;の違いに注意してください。;はexit statusが0にならなくても次に進む場合の連結です。最後にすべての操作成功時にexit=0を出力するようにし、Ruby側からこれを確認し、デプロイの成功判定をCircleCI側に伝えます。

2018-05-24

LMTの理論をわかりやすく

Machine/Deep Learning

はじめにリンクを載せておきます。

要は、うまくネットワークを学習させることで、ある閾値未満の摂動に対してロバストにできることを理論的に示した、ということです。

この手法はLipschitz Margin Trainingといわれ、略してLMTです。

以下、説明に際してモデルはClassifierを考えます。つまり、入力ベクトルを、いくつかのクラスに分類するような問題を考えます。

どれだけ出力がずれても正しく分類されるか

Classifierでは、それぞれのクラスのconfidenceを求め、それがもっとも高くなるようなクラスに入力を分類します。入力を $x$ とし、真のラベルに対応するconfidenceを $C_t(x)$ 真のラベル以外のラベルでもっともconfidenceが高いものに対応するconfidenceを $C_{t'}(x)$ と書くことにすると、正しく分類される条件は

$M(x) = C_t(x) - C_{t'}(x) > 0$

です。 $M$ はmarginの頭文字です。ある程度入力を摂動させたとしてもネットワークが正しく分類するというのは、 $M$ が摂動に対して正の符号を保ったままように変化することです。このためには、ある程度 $M$ がデフォルトで大きな値をとっておく必要がありますよね。

LMTで一番大事な式

ネットワークのリプシッツ定数 $L$ を次の式を満たすような実数とします。以下、ベクトルのノルムはL2 norm, 行列ノルムはL2 normから誘導されるノルムであるspectral normを考えます。

$|F(x+\varepsilon) - F(x)| \le L|\varepsilon|$

ここで $F$ はネットワークの関数、 $x$ は入力です。このとき、次の式が成り立ちます。

$M(x) > \sqrt{2} L |\varepsilon| \Rightarrow M(x + \varepsilon) > 0$

証明は元論文にあるのでここでは省略します。

つまり、入力 $x$ に対して $M(x)$ が常に、 $\sqrt{2}cL$ （ $c$ は定数）より大きくなるように学習させることができれば、 $|\varepsilon| \le c$ を満たすような摂動に関しては、結果を変えません。

Lipschitz Margin Training

LMTでは、classifierが正しく分類したときに限り、 $C_t(x)$ の値を $C_t(x) - \sqrt{2}cL$ に補正して誤差を計算します。これで学習がうまくいけば、このネットワークは正しく分類するときに、2番目の候補に対して $\sqrt{2}cL$ より大きなconfidenceの差をつけて判別するわけですから、上述したことから摂動に強くなることがわかります。

LMTの気持ち

と、ここまででLMTの説明としては十分なわけですが、最後にLMTがどんな場合でもうまくいくわけではない、ということを説明しておきます。

まず、上の説明でも出てきた定数 $c$ の意味をよく考えてみましょう。実は $c$ にはinvariant radii（不変半径）という名前がついており、名前の通り、この範囲内の摂動なら結果が変わらないように要請するものです。 $c = \infty$ の極限を考えると明らかに失敗する（すべての入力が同じクラスに分類される）ように、分類に対して適切な $c$ の値を見積もることが重要です。 $c=\infty$ ではネットワークが定値関数になってしまうように、 $c$ はネットワークが表現する関数のなめらかさに関する制約だとみなすこともできます。

また、それとは別に、ネットワークが表現できる関数のクラスというものがあります。20層のネットワークは4層のネットワークに比べ、ずっと複雑なモデルを扱うことができます。複雑なモデルだと、途中のパラメータをいくらでも調整できるため、かなり大きな $c$ を指定しても、うまくそのなめらかさの要請を満たしつつ、適切な関数を学習してくれます。しかし、Shallow Networkの場合、 $c$ の要請を満たすようななめらかな関数がそもそもそのネットワークで表現不可能、ということがしばしばあります。こういった場合、 $c$ の値がかなり小さく制限されてしまいます。

また、Adversarial Exampleの生成手法であるFGSM: Fast Gradient Sign Methodに対して、LMTはそれほど強くないということが知られています。 FGSMは、入力の各要素を摂動させたときの誤差の変化をもとに、誤差を増大する方向を調べ、その方向に入力を摂動させるというアルゴリズムです。 LMTで学習されたモデルの場合だと、ネットワークの関数があまりになめらかなため、FGSMの攻撃に弱いです。関数がなめらかだと数値微分の精度が上がってしまうので、誤差が増大する方向を的確に突き止められてしまいます。FGSMに強いネットワークというのは、LMTとは真逆で、ネットワークの関数が極めてギザギザしているような関数になっているネットワークです（こうすると数値微分の値がほとんどランダムになります）。

とはいってもぼくの実験では、4層のShallow Networkでも、入力の各要素で5%程度のスケールまでの摂動なら通常の学習をした場合に比べて、Advesarial Exampleでの攻撃成功率を半分程度に抑えることができました。

2018-05-21

AGC024 D: Isomorphism Freak

Sport Programming

入力例ですこし試してみると、頂点を追加していってグラフをできるだけ対称的にする、という問題であることに気づきます。

対称中心は、ノードになることもありますし、辺の中心にになることもあるので、インプット時にダミーの頂点を各辺の間に追加しておきます。

long tmp = 100;
REP(i,n-1) {
    long a, b;
    cin >> a >> b;
    a--; b--;
    long mid = tmp;
    tmp++;
    adj[a].push_back(mid);
    adj[mid].push_back(a);
    adj[mid].push_back(b);
    adj[b].push_back(mid);
}

あとは、ダミーを含め、どの頂点を中心にするかを決め打ちして調べます。中心は明らかに次数2以上なので、葉は飛ばします。

次のコードは、頂点iを中心としたときの、（カラフルさ、葉の数）のペアを返します。

対称となるようにノードを追加したあと、木がどうなっているかというと、木を頂点iを根とした根付き木とみなしたときに、葉でない任意のノードについて、それらの子がすべて同型となっています。

このときカラフルさは、木の深さに等しく、葉の数は、頂点から葉に向かうパス上で発生する分岐の数の積に等しいです。木の深さは、2で割ってやることで、ダミーを除いた深さを考えます。

実装では、根を中心とし、BFSで頂点を見ていき、一つのパスにまとめています（上述したことからわかりますが、ノードを追加したのちのグラフにおいて、根から葉に向かうパスはすべて同じ長さとなるので一つにまとめることができます）。

// pair of (color, leaves)
P cnt(int i) {
    reset(); // set false to visited
    long div = adj[i].size();
    long depth = 0;
    VI cur;
    visited[i] = true;
    cur.push_back(i);
    while (1) {
        VI nex;
        long maxdeg = 1;
        for (auto j: cur) {
            maxdeg = max(maxdeg, long(adj[j].size() - 1));
            for (auto k: adj[j]) {
                if (!visited[k]) {
                    nex.push_back(k);
                    visited[k] = true;
                }
            }
        }
        
        if (nex.size() == 0) {
            return P(depth / 2 + 1, div);
        }
        cur = VI(nex);
        
        div *= maxdeg;
        depth++;
    }
    exit(1);
}

2018-05-20

How to restore the Edit Response URL of a Google Form?

Misc

It seems you cannot restore the URL without the help of the administrator.

The Edit Response URL is of the following format:

https://docs.google.com/forms/d/e/{form_id}/viewform?edit2={response_id}

where you can get form_id by directly accessing the form, but you cannot get your response_id once you close your browser. You can visit the page with Edit Response URL as long as your browser remembers your submission. (If it does, It alerts Confirm Form Resubmission when you visit the page.)

Technically, since Google Forms don't require user login, response_id is probably a hashed string initialized only by some info of your answer, which may not contain your account data of Google. It means you cannot extrapolate the hashed string. (If you can, then other people also can, which means other user could edit your response.)

If you can contact your administrator

The administrator may know your Edit Response URL. Even when s/he doesn't know it, s/he can obtain it by running GAS on the spreadsheet. You can google the process.

d0tfi1e’s blog

趣味と日記

ROCAと離散対数問題

ROCA

RSALibで生成される素数の特徴

$n \equiv 65537 ^ x (\mathrm{mod} M)$ を解く

混乱しやすいポイント

より大きな入力での離散対数問題

参考文献

sudo時にユーザ環境のファイルを実行する

EC2でユーザ権限でのrbenvインストール

CircleCIで自動デプロイ

LMTの理論をわかりやすく

どれだけ出力がずれても正しく分類されるか

LMTで一番大事な式

Lipschitz Margin Training

LMTの気持ち

AGC024 D: Isomorphism Freak

How to restore the Edit Response URL of a Google Form?

If you can contact your administrator