RSAの危ない運用(弊研究室の某課題について考える21日目)

はじめに

この記事は弊研究室の某課題について考える21日目の記事です。

前回RSAの暗号についてやったので今回はRSAの危ない運用に関して話します

公開鍵Nのビット数が短いとまずい

公開鍵Nのビット数が短いと普通に計算して素数を求められます。そうするとpとqがわかってしまうのでまずいということで今回は短いビット数の鍵を復号します。

Pollard-Rhoアルゴリズム + Miller-Rabin素数判定法を用いて素数を見つけます。素数となる数でどんどん割っていく方法だと時間がかかるのでしょっぱなからこれでいきます。

import sys
from random import randint
from fractions import gcd
from Crypto.PublicKey import RSA

def miller_rabin(n,k=20):
    s, d = 0 , n-1
    while d % 2 == 0:
        s+=1
        d/=2
    for i in range(k):
        a = randint(2,n-1)
        y = pow(a,d,n)
        if y == 1:
            continue
        for j in range(s):
            if y == n-1:
                break
            y = (y*y) %n
        else:
            return False

    return True

def pollard_rho(n, c=1):
    x, y, d = 2, 2, 1
    while d == 1:
        x = (x*x + c) % n
        y = (y*y + c) % n
        y = (y*y + c) % n
        d = gcd(abs(x-y),n)
    if d != n:
        return d

#N = 821 * 953

key = RSA.importKey(open("96key.pem").read())
print key.n

print pollard_rho(key.n)
$ time python pollard_rho.py
67347099272184651187705110721
239973115325831

real    2m25.078s
user    2m25.004s
sys     0m0.017s

こんな感じで素因数分解の答えを出してきます。意外と時間がかかるので自分の計算機でどこまでの鍵なら計算できるのか知っておくと便利かも。自分は128の鍵は30分以上かかりました。

素数pとqの値が近いとまずい

選んだ素数pとqの値が近いとフェルマー法によって求められます。

Fermat法は素数同士の積からなる合成数において、二つの素数の差が小さい場合に有効なアルゴリズムである。 具体的には、合成数nの平方根周辺のある値をxとしたとき、(x-k)*(x+k) == nとなるkを小さいものから求める。

p*qの積のNがあった際にNより大きいa^2を考え N = a^2 - b^2とあらわすことができれば、a+ba-b素因数分解の結果となるということです。

まぁ書きます。手順としてはNに近い平方根を計算すること。そしてそれに近いbを試していくことって感じ。まぁbを試すためにはxを増やしたりyを増やしたりって感じで試していく

def isqrt(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n//x) //2
    return x

def fermat(n):
    x = isqrt(n) + 1
    y = isqrt(x * x - n)

    while True:
        w = x * x - n - y * y
        if w == 0:
            break
        elif w > 0:
            y += 1
        else:
            x += 1

    return x+y, x-y

n = 0x86E996013E77C41699000E0941D480C046B2F71A4F95B350AC1A4D426372923D8A4561D96FBFB0240595907201AD3225CF6EDED7DE02D91C386FFAC280B72D0F95CAE71F42EBE0D3EDAEACE7CEA3195FA32C1C6080D90EF853D06DD4572C92B9F8310BBC0C635A5E26952511751030A6590816554E763031BCBB31E3F119C65F

p,q = fermat(n)

print p
print q

実行結果は下のように

$ time python fermat.py
9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769
9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987245583

real    0m0.015s
user    0m0.007s
sys     0m0.008s

複数のRSA暗号があるとき同じ素数を使っているとまずい

つい最近のCTF問題でもありましたね。Common's factors attackと言われるものです。

これですが複数のRSA公開鍵のNから最大公約数を求めればいいです。問題を用意するのが大変なので今回はとある問題から素数合成数をいただきます

用意する問題は当然ps and qsです。

今年のsecconの問題ですね。私も解いたんですがその時にはBKPのやつを借りました。今回は時間に余裕があったので一からコード組みますっていっても公約数求めるだけなのでたいしたことはない

from Crypto.PublicKey import RSA
from fractions import gcd
import gmpy

E = 65537

def common_factor(N1, N2):
    p = gcd(N1,N2)
    return (p, N1/p), (p,N2,p)

def form_priv_key(n,p,q):
    phi = (p-1) * (q-1)
    d = gmpy.invert(E,phi)
    key = RSA.construct((long(n),long(E),long(d),long(p),long(q)))
    return key

key1 = RSA.importKey(open("pub1.pub").read())
key2 = RSA.importKey(open("pub2.pub").read())

print key1.n
print key2.n

privkey1, privkey2 = common_factor(key1.n,key2.n)

privkey = form_priv_key(key1.n, privkey1[0], privkey1[1])
print privkey.decrypt(open("cipher").read())

privkey = form_priv_key(key2.n, privkey2[0], privkey2[1])
print privkey.decrypt(open("cipher").read())

結果はこんな感じ。

$ python2 common_factor.py
847796795638781450678718708664542960446354226336422534142899480441478781747168340722544245493739168125415291376063352480076469305992008517388366298914970810765149321160596112226917023146371080685458239747986992197343482255681414590678694753885521068656675164266739274608505094927725285868801825144058835115051061857233824816176186349372737400492228548130718029270482313906040935333159681273527671359469173939861889228505791626525994180917670701909816457560622922219797109618405842358250940062127841301193206255543580550667149741357342408703680375118252445296600962244008043713708516004025217199954286478272550961283413053789743740774140439284662596273452124779590753836094450154459078034659421366584354005421566290862244000178569163732971816333961711759000171156293724203334889496589376907683142167883476184246287660764821622298961378903818077158234683927321823293466245584486980446609569799420950073036635602004293246754252079757527610246223280774592566063422181158810677919909523144033543195999214800559998598003329294711989868113423468536273984117507008756542731210465222475943122324672467669623079721727526348599823126409108190030551584092950358235465140166515452377475799157617227362838246912839086733412861436353117994501342653
763718912475160487902804749669814117361530270298225094625871588939939773892509348006077810445741086683427253000695920011673348476297973798322806091336777405584801442639626925406721932533140226556519019440300864340670199686368307155860493615065198319490060598587202051942638792919648596288576294804549738135969737494734307362891313864027749187674251692407867312885251279302785352318725391842117065840058358065676707016006124478822206302825992616559261930620693061673348139416033418864269248381876692676529410115745518353146254670349865568255213560376368953292931958006941630719304442332912813624543600126197554727832190226632919876204677667384620275620336951964833888599634720101911051166398907898747710391394105753614253527704990658698844796442515669670816004761855554187277637871343595647487793209271354240148469085627742503649786300484610102224828274384484809539697728008552925590472129497180290668277790132130824141651399551803499770513576176720509094833332201946177880267399933460994496277590932311628302240154240967341858152145815276163397709272690500041597393678630136932574450837982593210399370333578887450410911663220219423601973078501237709613593311133945501455828164291429228495931943107997137587307522565029820756690578833
▒H4؋ѝ2l▒r
▒puF`u▒܎▒▒3▒4CT▒R
  ▒▒V▒Z[]▒▒▒▒%▒▒)() _▒d▒
                        |▒o▒h▒o▒V▒▒s{t_▒vӫ▒1ۧ▒[:▒X▒Y▒▒%▒%▒▒r▒9dJ▒|▒▒▒▒▒▒▒7▒▒M▒▒
                                                                              g▒B▒▒▒▒݁t^Scq▒`H▒0▒c▒f▒▒▒▒Ŏ\▒
                                                                                                          6▒a ▒▒"5`▒_▒et:
▒▒a▒C   =▒L▒X▒  UmL▒b▒'▒▒▒\▒X▒▒▒3▒▒l>▒▒(W!▒▒T▒▒▒▒e▒DǷ.▒▒?f▒L.▒U▒▒▒▒▒▒nR~J▒.▒'▒&/▒▒w▒▒▒▒!A▒wS"U▒▒Z▒*▒    ▒▒▒E▒T▒d▒w▒@▒J!▒=▒▒▒▒"▒▒,▒▒▒▒Dh▒▒▒▒▒▒      ▒▒▒▒(▒l▒▒▒4UayXg4Ї4Z▒Z▒▒Ma▒▒5▒▒▒|▒ۻ▒;Z▒-S▒@▒▒]> \n6>▒g▒MBK▒▒E▒@▒a▒VYԹB▒p▒▒▒`▒[▒53▒1▒],▒GA".▒
         ▒▒5▒摨SECCON{1234567890ABCDEF}

▒▒C@▒▒&▒▒▒▒▒▒?▒w▒▒▒9▒y▒N>▒g▒▒▒A▒n▒<Sy▒▒▒▒▒▒▒ڍ▒▒E▒T▒8T▒▒X▒ލ▒O>ƾ▒H▒▒▒`▒=▒
                                                                       ▒▒R▒▒▒▒0
                                                                               ƞ▒R▒8Η▒\o"▒▒Kf+8▒▒5o▒V▒=
                                                                                                        ▒E▒▒▒▒yv▒▒C▒>▒▒Όme[▒▒e
           ▒螉\MNu4z▒▒▒}▒▒▒4 ▒Gf▒Ȯ▒▒▒▒▒P▒▒▒"K▒▒Ќ>▒aW▒▒▒)4▒C▒ϿK▒▒▒T▒0▒/▒B▒T▒]YL@-▒▒▒▒ ▒e▒*▒Ҟ▒ӥ▒▒▒▒▒▒}▒֫▒DŢ<R%Ƙ▒Z▒<▒y[▒PI▒▒T▒e1▒▒▒l▒T▒p.▒▒▒t[▒ko▒$▒G▒▒▒~i▒▒▒▒▒▒▒▒$▒▒▒:Z|▒▒u▒c▒▒▒0▒k▒OBO▒kZ▒CV▒▒6▒▒▒▒▒ $>▒ԃBf▒V▒f▒▒▒.<o▒▒▒▒Q~▒j▒▒`j

終わり

まだまだ危ない運用はあるのですがひとまずはこんな感じでよいでしょう。私の勉強のためにもここらへんはまとめておきたいものですね

参考文献

RSA暗号(弊研究室の某課題について考える20日目)

はじめに

失踪は許さない弊研究室の某課題について考えるの20日目の記事です。

他の記事も徐々に書いていますが完結は年明けになりそうです。

RSA暗号

RSA暗号は桁数の大きい合成数素因数分解は難しいという理論の元で構成された公開鍵暗号です。

共通鍵暗号公開鍵暗号

暗号方式には共通鍵暗号公開鍵暗号があります。共通鍵暗号は暗号化と復号に同じ鍵を用います。公開鍵暗号では公開鍵と秘密鍵の2種を用意し、片方の鍵で暗号化したものはもう片方の鍵でしか復号できないといったものとなります。

共通鍵暗号では暗号化と復号に要する鍵が同じであるため鍵を安全に相手に渡す必要があります。

一方で公開鍵暗号では秘密鍵は自身でもっておくものであるため、共通鍵等の情報を用いて秘密鍵を推測、生成されないようなアルゴリズムである必要があります。

RSA暗号の仕組み

  1. 素数pとqを選びます。
  2. n=p*q, φ(n)=(p-1)*(q-1)とする
  3. φ(n)と互いに素となるeを選ぶ
  4. d * e ≡ 1 (mod φ(n))となる最小のdを選ぶ
  5. neを公開鍵、p,q,d秘密鍵とする

RSA暗号鍵を使った暗号化と復号

2つの方法で暗号化・復号を行いたいと思います。

  1. opensslコマンドを利用してRSAの公開鍵と復号鍵を作成して暗号化・復号する
  2. 素数pとqを作成し、自力でRSA暗号鍵を作成して文書を暗号化・復号する

opensslコマンドを利用する

まずは暗号鍵を作ります

$ openssl genrsa > server.key # 秘密鍵の作成
$  openssl rsa -in server.key -pubout -out publick-key.pem # 公開鍵の作成

opensslコマンドの秘密鍵には素数pとqが含まれているので公開鍵を作成することが可能です。 openssl rsa -text -in server.keyで確認できます。

ではこの鍵を用いて暗号化していきます

暗号化にはopenssl rsautl -encryptを用います

$ echo "This is a plain text" > plain
$  openssl rsautl -encrypt -pubin -inkey public-key.pem -in plain -out encrypt
]$ cat encrypt
N▒-9U▒
▒▒%`▒;▒▒▒1▒▒=%2u'm▒▒
                    ▒▒֡▒L7▒돆▒▒▒m▒▒W▒▒@T▒
▒L
V▒rU▒▒▒@we▒▒▒-@<▒▒^▒▒▒H▒v▒|^Й▒▒1▒▒{&j*▒GFZ|t▒Q▒▒W{▒▒Q.▒%▒▒▒
                                                           ▒
V▒▒4▒|u▒▒▒Q▒V
▒5▒i▒viyk▒▒![M▒▒,▒ȥh▒▒Ȉ6묛▒▒ң▒l\d▒#▒Dt.▒D̃)sdZ%o}tS`▒▒0▒▒q

次に復号です。復号にはopenssl rsautl -decryptを使います

$  openssl rsautl -decrypt -inkey server.key -in encrypt
This is a plain text

さてでは作った鍵をpythonを用いて暗号化・復号していきます。CTFではよくpythonスクリプト書きますからね

pythonでopensslで作成した鍵を取り扱う

pycryptoライブラリを使用します。

$ sudo pip install pycrypto

こんな感じで暗号化・復号ができます

from Crypto.PublicKey import RSA

with open("encryptpy.txt","w") as f:
    f.write(RSA.importKey(open("public-key.pem").read()).encrypt(open("plain").read(),"")[0])

with open("decrypt.txt","w") as f:
    f.write(RSA.importKey(open("server.key").read()).decrypt(open("encryptpy.txt").read()))

ちなみにopensslコマンドで作成したencryptファイルの復号もできます。

>>> from Crypto.PublicKey import RSA
>>> privkey = RSA.importKey(open("server.key").read())
>>> privkey.decrypt(open("encrypt").read())
'\x02\xb9\x9c\x19\xef~\'\xd9\x93\xa6}2#"\xf0oMH\x86\x9d\x83\x98\xf2M\xda\x97\xdbT\xa9WW_\xb7y\xb8\x03\x1a\xf7P\xc5\xbe\x92\n\xf9^aOA\xae\xe4\xea{\x03?\xaf\x8dX\xe2\xc1Oe\xf8\xa0Z\x96\x87[\x87\xfc\xe2F\x13\xf7u\xd1\xd5sDO\xf7\x11\xef\xc3\x0c\x17\xd3\xa8\x03\xa4t\xd0\xa4O\xdezA?\x04\x01cM\xb8\xb7\xa3y6\xbd\xab\xb6\xf6j\x13\xef\n/\rR\x956\xeffD\x1e01M\x13{\x16\x11\xde\xad\xc5\x18\xbcN\x99\x99F\x85\x99(\x0f\x0byE\xb0\x91\xa0\xd2V_\x90\xc2\x97xG\x05\xc8\xacd\x0e&\x996\x8fl\xbe\xb7\xde\xfb\xc1\x1c\xea,\r\xf7\xa7\x86\x87`\x8fD:\xd0\xd4\x9e\xb1\xd4*Q\xc6\xf7\x1d\x14\xeb?\xccA\xee\xbd\xb1\x82>\x08\ry\xde\xe4\xa2\xd2\xc8\xb3\x7f\xb6e\xc1\xf1\xa3\xbcDa\xae_e)\x19P\x94\xf7\xdep@\x00This is a plain text\n'

しっかり復号できていることが確認できます

pythonで自分で鍵を作成する

RSAアルゴリズムに従ってpythonで鍵を作成します。今回素数p,qは簡単なものを利用します。

from Crypto.PublicKey import RSA
from fractions import gcd

p = 661
q = 821
e = 65537

N = p*q
L = (p-1)*(q-1)

for i in range(2,L):
    if (e*i) % L == 1:
        D = i

key = RSA.construct(map(long,(N,e,D)))
print key.exportKey()
$ python makersa.py
---BEGIN RSA PRIVATE KEY-----
MCUCAQACAwhH2QIDAQABAgMD6qECAgKVAgIDNQICAlECAQ0CAgGZ
-----END RSA PRIVATE KEY-----

ということで秘密鍵が作成できました。鍵サイズが1024bitないのでpycryptoで暗号化・復号はできません。CTFの問題なら1024は超えるはずなのであとは上の時と同じように復号してください。

終わりに

次はplain RSAに対する攻撃という題でRSAのいけない運用に対して話していこうかなと思います。

研究室内等のネットワーク系統の障害対応(弊研究室の某課題について考える16日目)

はじめに

この記事は3年間私が研究室で生活してきて、その際に起きた障害、それに対する対応を私なりにまとめたものです。

そのため今回の障害対応は基本的には小規模(要は研究室等の障害)であり第三者への不利益等は考えていないものです。

利益あたりが絡むのであればサービスの持続性等や対応等があるのでこの通りではありません。参考にしないでください。

アウトライン

  • サンプルのネットワーク構図
  • 日頃やること
  • 障害が発生した時の対応
  • 原因究明
  • 再発防止

サンプルのネットワーク構図

この構図を元に説明していこうと思います

f:id:kataware8136:20171227134701p:plain

障害の定義

この記事での障害とは

  • 計算機が利用できなくなる
  • 計算機の動作が重い
  • 特定のサービスが利用できない

といったことを指します

日頃やること

サーバで動いているサービスの把握はしておいてください。あるサービスを動かしているときにそのサービスが複数のデーモンで動いていないか等を確認しておくことは対応で役に立ちます。

障害発生した際にすぐやってはいけないこと

再起動する

再起動して解決する問題もあるかもしれませんが、「障害が発生した」⇒「再起動しよう」は何も解決してないのでやめましょう

障害が発生した時

障害がどこまでの範囲で発生しているのかを把握します。

例えばサンプルの構図では島の中の計算機だけなのか、それともサーバのスイッチ周りなのか、おおもとのスイッチ周りがダメでサンプル構図の全体で発生しているのかを確認しましょう。

例えば島の中の計算機だけが同じ障害を発生しており別の島で発生していなければ、その島だけの問題なので「スイッチの故障」「大本のスイッチから島のスイッチまでのLANケーブルの破損」等が考えられます。

小さいところから大きいところに確認していくのがいいと思います。「自分の島」⇒「ほかの島」⇒「サーバのデーモン確認」⇒「大本のスイッチ」⇒「建物全体」みたいな感じです。建物全体になるともう一研究室の一人としては何もできないのでスルー

切り分けた障害における対応

小さい範囲から大きい範囲まで順に対応方法を説明します。

個人の端末のみ

考えられる原因

  • 大量のパケット処理による遅延
  • 島のスイッチから計算機のLANケーブルの破損
  • スイッチの端末とつながってるところだけが壊れてる(ほぼない)
  • NICの破損(まずない)

大体上の2つが原因として考えられそう

島の中の障害

考えられる原因

  • スイッチ本体の障害
  • 大本のスイッチから島のスイッチまでのLANケーブルの破損

サーバの周りの障害

考えられる原因

  • サービスのデーモンが死んでる
  • サービスを動かすサーバの負荷が大きい

全体

大本のスイッチ、まぁ要は研究室内の障害ですね。

考えられる原因

  • どこかでループを起こしている
  • さらに上のほうで障害(例えば研究室であれば大学のネットワークの障害とか)

正直2つ目に関してはどうしようもありません。

障害対応

LANケーブルの破損とスイッチの破損は取り換えてくださいってことでスルー、ループに関してはやらかしたら即座に止まるのでなにかネットワーク周りをいじってた人の配線を確認しておしまい。ということで下の2点の対応について書く

  • サービスのデーモン死亡
  • サーバの負荷が大きい

サービスのデーモン死亡

まずはサービスの状況を確認します

systemctl status <サービス名>です。サービスで異常が発生している際はこれで確認することができます。

このためにサービスの名前を確認しておく必要があるんですよね。デーモンの再起動にはsystemctl restart <サービス名>なのですがエラーにそもそも解決策が載ってたりします。

デーモンの再起動やエラーメッセージから根本の原因を特定できます。

サーバの負荷が大きい

正直研究室という小さい枠組みで負荷が大きくなるなんてめったにないのですが一応解決策を

tcpdumpもしくはwiresharkトラフィック監視してください。で飛んできているパケットのipアドレスを探して端末所有者に原因を聞きましょう。

おわり

この記事書いてた時に研究室に障害起きたんだが何か悪いことしたのか?

ちなみに原因はサーバの電源がなぜか落ちていました。普通に電源ボタンを押して再起動して解決です。