id0-rsa.pubのメモ【Insufficient Key Size】

Insufficient Key Size

以下問題文。

An incompetent systems administrator accidentally configured the company's encryption system to use very small keys. This RSA key modulus is only 119 bits.

-----BEGIN RSA PUBLIC KEY-----
MBYCD3AY9xf8ZmUVDBSIVPZMSQIDAQAB
-----END RSA PUBLIC KEY-----

Recover the decryption exponent (in lowercase hex). 

とりあえず問題文の公開鍵の中身を確認してみる。公開鍵をpub.keyで保存して以下のコマンドを実行。

$ openssl rsa -RSAPublicKey_in -in pub.key -text
Public-Key: (119 bit)
Modulus:
    70:18:f7:17:fc:66:65:15:0c:14:88:54:f6:4c:49
Exponent: 65537 (0x10001)

ここでNとeがそれぞれわかる。また、Nが119bitで極端に短いことに気づく。（以前聞いた話だと512bitくらいまでならお手持ちのパソコンで簡単に素因数分解可能だったはず）
計算しやすいようにNをintに直して素因数分解する。（:を取り除いたものを10進数に直す）

$ python
>>> modulus = int("70:18:f7:17:fc:66:65:15:0c:14:88:54:f6:4c:49".replace(":", ""), 16)
>>> modulus
582043602765817436229812959722228809

素因数分解の方法については以下のようなものがある。
* 自分でプログラムを書く
* factordbにブチ込む
* WolframAlphaにブチ込む
今回はとりあえずfactordbにブチ込んで素因数分解をした。
素因数分解できたら秘密鍵を導出して終了。

from Crypto.Util.number import inverse

p = 662700133751480051
q = 878291059745115859
N = p * q
e = 65537

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
print(hex(d))

id0-rsa.pubのメモ【Ps and Qs】

Ps and Qs

以下問題文。

Here is an RSA public key and a message that's been encrypted with it.

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAKzl5VggSXb/Jm2oqkPeRQwtpmGlLnJT
Nre4LKx3VUljtLzYWj4xoG+aHBouwJT7DyeibpasCH8Yderr4zIGTNUCAwEAAQ==
-----END PUBLIC KEY-----

message:
0xf5ed9da29d8d260f22657e091f34eb930bc42f26f1e023f863ba13bee39071d1ea988ca62b9ad59d4f234fa7d682e22ce3194bbe5b801df3bd976db06b944da


Luckily the recipient was using their random number generator incorrectly resulting in low entropy prime number generation. Here is another public key the recipient generated around the same time.

-----BEGIN PUBLIC KEY-----
MF0wDQYJKoZIhvcNAQEBBQADTAAwSQJCAPsrpwx56OTlKtGAWn24bo5HUg3xYtnz
nTj1X/8Hq7pLYNIVE57Yxoyr3zTOOBJufgTNzdKS0Rc5Ti4zZUkCkQvpAgMBAAE=
-----END PUBLIC KEY-----

Submit the secret message in lowercase hex. Some light reading material

大きな数の素因数分解は難しいが、2つの大きな数の最大公約数を求めることは容易であることを利用した問題。
2つのRSAの公開鍵に同じ素数が含まれていた場合、最大公約数を求めることで簡単にその素数がわかり、素因数分解をして秘密鍵を導出することができる。
割とCTFの問題として出題されるイメージがあり、公開鍵が2つあった場合は疑ってみると良いかもしれない。

公開鍵のパース

まず、opensslで表示した公開鍵の中身を計算に使えるようにパースする。

def parse_rsa_public_key(key):
    """Key is an RSA public-key, return the RSA modulus and exponent as ints."""
    out = subprocess.run("echo '%s' | openssl rsa -pubin -text -noout" % key, shell=True, stdout=subprocess.PIPE).stdout
    out = out.decode("utf-8")
    a = out.find("Modulus:") + len("Modulus:")
    b = out.find("Exponent")
    modulus = out[a:b]
    modulus = modulus.replace(' ', '').replace('\n', '').replace(':', '')
    N = int(modulus, 16)
    c = b + len("Exponent: ")
    d = out.find(" (0x")
    e = int(out[c:d])
    return N, e

あとはそれぞれの公開鍵をパースし、最大公約数を求め、秘密鍵を導出する。秘密鍵ができたら復号しておわり。

from math import gcd
from Crypto.Util.number import inverse
import subprocess

N1, e = parse_rsa_public_key(key1)
N2, e = parse_rsa_public_key(key2)
p = gcd(N1, N2)
q1 = N1 // p
q2 = N2 // p

phi = (p - 1) * (q1 - 1)
d = inverse(e, phi)

m = pow(message, d, N1)
solution = hex(m)[2:]
print(solution)

補足 : pycryptoは便利。

pip install pycrypto

参考

• SECCON2017 writeup - 生き恥

• http://www2.nict.go.jp/csri/plan/H26-symposium/files/3-2.pdf

• https://factorable.net/weakkeys12.extended.pdf

id0-rsa.pubのメモ【Cut and Paste Attack On AES-ECB】

Cut and Paste Attack On AES-ECB

ブロック暗号のモードの話。以下問題文。

ECB is the most basic mode of operation for block ciphers. When used with AES, any block of 16 bytes (the block size of AES) will encrypt to the same ciphertext when encrypted via AES-ECB with the same key. Below are 3 pairs of messages and their corresponding ciphertexts:

m1 = Deposit amount: 5 dollars
c1 = 0x5797791557579e322e619f12b0ccdee8802015ee0467c419e7a38bd0a254da54
m2 = One million dolls is quite the collection
c2 = 0xb1e952572d6b8e00b626be86552376e2d529a1b9cafaeb3ba7533d2699636323e7e433c10a9dcdab2ed4bee54da684ca
m3 = Hey nice binoculars
c3 = 0x35d0c02036354fdf6082285e0f7bd6d2fdf526bd557b045bce65a3b3e300b55e

Let's suppose there is a (very very bad) protocol to communicate with your bank out there that works as follows: All correspondence is encrypted via AES-ECB and everyone shares a unique key with the bank. The bank will assume all messages are from you provided they decrypt under your key. Suppose you observed the above three ciphertexts being sent to the bank and know their corresponding messages. What ciphertext would you send the bank to forge the message "Deposit amount: One million dollars"? Submit your solution in lowercase hex, no leading 0x.

ブロック暗号は平文を固定のブロック長に分割して暗号化する。しかし、そのままだとブロック長より長い平文を暗号化できない。そこで、暗号化モードという仕組みにより任意の長さの平文を暗号化している。ECBモードは最も単純な仕組みの暗号化モードで、同一の平文ブロックをECBモードで暗号化すると、同一の暗号文ブロックが出力されるという問題がある。
まず入力となる平文を16バイトずつに区切ってみる。
m1はDeposit amount:+5 dollars。
m2はOne million doll+s is quite the c+ollection。
m3はHey nice binocu+lars。
すると、今回作るDeposit amount: One million dollarsという文字は、m1（Deposit amount:）、m2（One million doll）、m3（ars）にそれぞれ存在していることがわかる。
あとはそれに対応する暗号文をくっつけてsubmitして終了。 5797791557579e322e619f12b0ccdee8b1e952572d6b8e00b626be86552376e2fdf526bd557b045bce65a3b3e300b55e

id0-rsa.pubのメモ【Caesar】

Caesar

シーザー暗号の話。以下問題文。

Should probably stick to the salad 

ZNKIGKYGXIOVNKXOYGXKGRREURJIOVNKXCNOINOYXKGRRECKGQOSTUZYAXKNUCURJHKIGAYKOSZUURGFEZURUUQGZZNKCOQOVGMKGZZNKSUSKTZHAZOLOMAXKOZYMUZZUHKGZRKGYZROQKLOLZEEKGXYURJUXCNGZKBKXBGPJADLIVBAYKZNUYKRGYZZKTINGXGIZKXYGYZNKYURAZOUT

Test Vector
PT: HELLOWORLD
KEY: B
CT: IFMMPXPSME

とりあえず何文字ずらしたら良いかよくわからなかったので総当たりしてみる。

def caesar_decrypt(c, n):
  if ord('A') <= ord(c) and ord(c) <= ord('Z'):
    return chr((ord(c) - ord('A') - int(n)) % 26 + ord('A'))

def main():
  s = 'ZNKIGKYGXIOVNKXOYGXKGRREURJIOVNKXCNOINOYXKGRRECKGQOSTUZYAXKNUCURJHKIGAYKOSZUURGFEZURUUQGZZNKCOQOVGMKGZZNKSUSKTZHAZOLOMAXKOZYMUZZUHKGZRKGYZROQKLOLZEEKGXYURJUXCNGZKBKXBGPJADLIVBAYKZNUYKRGYZZKTINGXGIZKXYGYZNKYURAZOUT'
  for n in range(26):
    p = ''.join((caesar_decrypt(c, n) for c in s))
    print(n, ': ', p)

if __name__ == '__main__':
    main()

なんか読めそうな文章が出てきたでのsubmitしてみたが通らない。キレそう。 THECAESARCIPHERISAREALLYOLDCIPHERWHICHISREALLYWEAKIMNOTSUREHOWOLDBECAUSEIMTOOLAZYTOLOOKATTHEWIKIPAGEATTHEMOMENTBUTIFIGUREITSGOTTOBEATLEASTLIKEFIFTYYEARSOLDORWHATEVERVAJDUXFCPVUSETHOSELASTTENCHARACTERSASTHESOLUTION Discuss The Problemをみると、テキストを読めみたいなことが書いったので読んで指示通りsubmitすれば終了。（めんどくさい）

Read the text that your decryption yields and follow the instructions, that will lead you to the solution we're looking for.

id0-rsa.pubのメモ【Intro to RSA】

Intro to RSA

RSAが何かという話。
以下問題文。

Given the following public key, private key, and encrypted message (c=me mod N), compute the original message (m). Submit your answer as a hex integer (no lead 0x, all lower case characters).

(e, N) = (0x3, 0x64ac4671cb4401e906cd273a2ecbc679f55b879f0ecb25eefcb377ac724ee3b1)
d = 0x431d844bdcd801460488c4d17487d9a5ccc95698301d6ab2e218e4b575d52ea3
c = 0x599f55a1b0520a19233c169b8c339f10695f9e61c92bd8fd3c17c8bba0d5677e

cを復号すれば良い。dが与えられているのであとは計算するだけ。

$ python
>>> hex(pow(c, d, N))
'0x4d801868d894740b2be29309fcd3edcd51bd2c2a685028b89290f9268c727581L'

今日は夜遅いのでこれだけでおしまい。

id0-rsa.pubのメモ【Intro to Hashing】

crypto強くなりたいということでid0-rsaをちまちまやっていき、その記録を残していくお気持ち。

Intro to Hashing

ハッシュ関数とはなんぞやという話。
Introなので記載されている方法に沿ってやればOK。
id0-rsa.pubのsha256ハッシュの値をさらにmd5ハッシュしてsubmitして終了。

$ printf "id0-rsa.pub" | sha256sum
4b4c17690546df5edf6dd8c5a6c399a02e07367810c95f3d2776b730b4a326c8
$ printf "4b4c17690546df5edf6dd8c5a6c399a02e07367810c95f3d2776b730b4a326c8" | md5sum
b25d449d86aa07981d358d3b71b891de

echoじゃなくてprintfコマンドを使う理由としては改行コードが入らないようにするためっぽい。

Notice the use of the command printf as opposed to echo, this prevents a new line from being appended to our data, so the string is piped to the md5sum exactly as is.

AMD-Action:authenticate:SP の対処法メモ

App Storeからアプリケーションをインストールしようとした時に AMD-Action:authenticate:SP というエラーがででいた。 ここを参考に以下のコマンドを実行。

$ sudo -s
# cd /Users
# mkdir Shared
# chown root Shared
# chgrp staff Shared
# chmod 775 Shared
# exit

自分の場合は上記の手順で解決しました。

参考

www.tonymacx86.com