picoCTF 2018 – Cryptography

題目: Crypto Warmup 1

題目給了你一串訊息 llkjmlmpadkkc跟key thisisalilkey
要你利用table的方式加密

Table打開內容如下

看一下訊息跟key長度一樣
llkjmlmpadkkc
thisisalilkey

明顯是要利用查表的方式
譬如l對上t等於E

當然可以一個一個check
不過盡量試試用好一點的方法
網路上有個網站
https://planetcalc.com/2468/

可以利用此種加密方法
ROT0 (“a” transforms to “a”)

所以輸入後我們得到密文
essbudmaiouoa
答案就是picoCTF{essbudmaiouoa}

第一次輸入答案錯誤嚇了一跳?!

發現只是題目很無聊的要求你要轉大寫
https://www.ifreesite.com/abc/
隨便找個網站把英文轉大寫
再輸入
picoCTF{ESSBUDMAIOUOA}

發現又不對啦XD

結果是要求解密啦
回網站改成解密

輸入答案
picoCTF{SECRETMESSAGE}

正確過關

題目: Crypto Warmup 2

這題直接告訴你了加密的方式稱為rot13

有沒有覺得有點眼熟? 剛剛那個網站就有類似東西~

ROT1 就是讓a變成b，顧名思義，ROT13就是轉移13個位置

詳細參考wiki
https://zh.wikipedia.org/wiki/ROT13

一樣很好找到線上工具
https://rot13.com/

直接去解密題目給的cvpbPGS{guvf_vf_pelcgb!}

得到解答
picoCTF{this_is_crypto!}

題目: HEEEEEEERE’S Johnny!

下載下來有兩個檔案
passwd跟shadow
內容看起來就是Linux中etc的passwd跟shadow

#passwd
root:x:0:0:root:/root:/bin/bash
#shadow
root:$6$IGI9prWh$ZHToiAnzeD1Swp.zQzJ/Gv.iViy39EmjVsg3nsZlfejvrAjhmp5jY.1N6aRbjFJVQX8hHmTh7Oly3NzogaH8c1:17770:0:99999:7:::Code language: PHP (php)

nc 2018shell.picoctf.com 40157
連線過去
的確是問你帳號跟密碼而已

用john破解看看shadow的hash

john --wordlist=/usr/share/wordlists/rockyou.txt shadow Code language: JavaScript (javascript)

秒破!

得到密碼password1 (root)
再連線過去輸入帳密
拿到flag

picoCTF{J0hn_1$_R1pp3d_1b25af80}Code language: PHP (php)

題目: caesar cipher 1

有一個message檔案名為ciphertext

內容是picoCTF{domnuaiixifxwuymulwcjbylnivlpglc}

當然這個不是解答

題目要你decrypt這個message

這個內容也可以透過網站的shell去找到

Hint告訴我們這是一個caesar cipher

先看看wiki
https://zh.wikipedia.org/wiki/%E5%87%B1%E6%92%92%E5%AF%86%E7%A2%BC

看是不是發現跟之前ROT13根本原理一樣?!

wiki有提到
:::info
特定愷撒密碼名稱
根據偏移量的不同，還存在若干特定的愷撒密碼名稱：

偏移量為10：Avocat(A→K)
偏移量為13：ROT13
偏移量為-5：Cassis (K 6)
偏移量為-6：Cassette (K 7)
:::

題目hint有給了一個線上網站工具

想不到更聰明的方法…反正最多就試26次

一個一個試試看

試到20發現一個看起來很像答案的東西

丟去答案 過關~
picoCTF{justagoodoldcaesarciphertobrvmri}

題目: hertz

先連線過去看看
nc 2018shell.picoctf.com 48186

一大串看不懂的文字

先用caesar cipher嘗試了一下
https://rot13.com/
看起來不是

題目中提到了 substitutions. (替換)
https://zh.wikipedia.org/wiki/%E6%9B%BF%E6%8D%A2%E5%BC%8F%E5%AF%86%E7%A0%81

不過這樣還是不知道密文阿
結果找到一個網站 substitution cipher solver
可以暴力破解這種類型的加密
https://www.guballa.de/substitution-solver
把內容貼上就得到答案了

Flag如下
substitution_ciphers_are_solvable_vdascrwiam

題目: blaise’s cipher

查到blaise就是Vigenère Cipher
https://www.mygeocachingprofile.com/codebreaker.vigenerecipher.aspx
找到線上工具
利用暴力破解方式
把全文貼上去 讓它去try
破出來會有很多結果
我是根據查詢這個flagflagflagflagflag找到的

記得picoctf要改成大寫picoCTF

picoCTF{v1gn3r3_c1ph3rs_ar3n7_bad_cdf08bf0}

題目: hertz 2

nc 2018shell.picoctf.com 12521
連線過去得到以下內容

Let's decode this now!
Sdk egyub fxaoc waj mghvi atkx sdk rqzl pan. Y uqc's fkryktk sdyi yi igud qc kqil vxafrkh yc Vyua. Ys'i qrhais qi yw Y iartkp q vxafrkh qrxkqpl! Abql, wyck. Dkxk'i sdk wrqn: vyuaUSW{igfisysgsyac_uyvdkxi_qxk_saa_kqil_nhcyfyxsct}Code language: PHP (php)

總之是要decode
根據題目說是有規律的
找了個線上工具試試看
其中看得出格式picoCTF{}
所以clues中設定ytblBVN=picoCTF
(要注意 每次連線過去拿到的密文會不一樣)
然後成功得到flag

picoCTF{substitution_ciphers_are_too_easy_gmnibirtnv}

題目: Safe RSA

了解RAS之後 要我們幫助他解開一個密文
沒有金鑰 但是有一些有趣的東西可以參考

下載下來的內容裡面有ciphertext, e, n
也就是公式當中的c 跟 N
而d必須要從e跟r算出 而r需要p跟q

hint的部分
https://en.wikipedia.org/wiki/RSA_(cryptosystem)

e看起來很小?

e = 3

當e 太小時 可能就存在低加密指數攻擊
可參考 RSA的攻擊方式
https://www.anquanke.com/post/id/84632

對密文進行 square root of 3

去暴力破解k
如果c-kn 可以開根三次 則可以得到明文

拿別人的code
https://www.rootnetsec.com/picoctf-2018-safe-rsa/

#!/bin/python 
import gmpy
n = 0x2F6C2F0F6266F297F890F9246C0B189A702DB378D4B021339D995E0C0F03507477CF5AB319206AC6B8141BF3C32071EF0A822018D12F307C9222DFF07C0F3556F89327B87E843B29C4567FAAEA1E6253CD6A647D2AB6679B322A6B32F4BDBB3523C325E027707F6728DEACA6914B6CF2456ACE3BF848014A511DE272C9145F1E042DB27380E6DFB823D9EB6A635C885F073AE83B3D19AB7EB4A545CC4E05E336CF8E3D3811D0D501B3FD622A366B52649D66265BB097735E66AC5EEF7F1E77AEEDF70C58B6F3D1DDCDBC0560177464D8A7750D3F535250E500C3CD7EE03DA6851EAEE27D5911EC16FC7742B8E15D7F32B137A208FFD05BB9F5275C0F4E64443
cipher_str = 0x15ACBD1C515CB91085F155A56AEF8AF99CEF3C2B32C24BEED9B72E1B4BFBE80EC571BCA18961B2BF68A769EBAEA8B3F75A25D55203C79A7A9A44E29F1A5798152F5E52A598B4C898EA965F62B534864A1BC723C3F98D489B0A22C9DCEC577189F14965

gs = gmpy.mpz(cipher_str)
gm = gmpy.mpz(n)
g3 = gmpy.mpz(3)
mask = gmpy.mpz(0x8080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808000)
test = 0
while True:
  if test == 0:
   gs = gs
  else:
   gs += gm
  root,exact = gs.root(g3)
  if (root & mask).bit_length() < 8:
    print root
    break
print '\n',hex(int(root))[2:-1].decode('hex')Code language: PHP (php)

小小的注意點gmpy.mpz(n)
這個n必須是int type
今天如果a=10 b=0x25 都會是int type
但是如果是c=hex(10) 會是str type 無法代入到n

13016382529449106065839070830454998857466392684017754632233929110204433151964285

picoCTF{e_w4y_t00_sm411_9f5d2464}

題目: caesar cipher 2

這題也是一個caesar cipher

密文在shell的路徑
/problems/caesar-cipher-2_0_372a62ea0204b948793a2b1b3aeacaaa

也是可以直接下載來看
打開後內容如下

^WQ]1B4iQ/SaO@M1W>V3`AMXcABMO@3\BMa3QC`3kCode language: JavaScript (javascript)

提示有提到ascii
可以看ascii table看看有甚麼線索
http://www.asciitable.com/
因為flag形式都是picoCTF開頭
觀察編碼
^=94 W=87
p=112 i=105
是不是有發現其實有規律了

到下列網站輸入密文 得到flag
picoCTF{cAesaR_CiPhErS_juST_aREnT_sEcUrE}

題目: rsa-madlibs

hint是要你去了解一下RSA
https://simple.wikipedia.org/wiki/RSA_algorithm
https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

先連線過去看看
nc 2018shell.picoctf.com 40440

Hello, Welcome to RSA Madlibs
Keeping young children entertained, since, well, nev3r
Tell us how to fill in the blanks, or if it's even possible to do so
Everything, input and output, is decimal, not hex
#### NEW MADLIB ####
q : 93187
p : 94603
##### WE'RE GONNA NEED THE FOLLOWING ####
n
IS THIS POSSIBLE and FEASIBLE? (Y/N):Code language: PHP (php)

內容其實就是問一些rsa的數學問題

這篇值得研究一下
https://findneo.github.io/180727rsa-attack/

egcd輾轉相除法

公私鑰的產生

歐拉函數與計算方式

模反元素

幾個點
p,q為質數
N=pq
r=(p-1)(q-1)
r>e, 且e跟r互質
模反元素 ed = 1 (mod r)

public key是(N,e)
private key是(N,d)

第一個問題問說p,q是否合理
我們可以寫程式來確認 是否兩個數字互質

第二個給你p,n
所以用q=n/p
在計算p,q是否互質就可

第三題給e,n
問是否可行 還要計算q,p
看了一下 想了一下 這樣資訊好像不夠

第四題又是p,q
計算totient(n) 也就是n的歐拉 (p-1)(q-1)

第五題
要加密
有明文, e, n

對明文加密是這樣的

其中c就是密文
小n是明文

這邊我們可以利用python的一個函數pow
https://www.runoob.com/python/func-number-pow.html

pow(x, y[, z]) 會變成 x^y ( mod z )

所以我們需要就是塞入 pow(plaintext, e, n)
就可以得到密文ciphertext

第六題是要解密
不過給的是密文,e,n
資訊不夠沒辦法解

再下一題是給q,p,e
要找出d
模反元素 ed = 1 (mod r)
是可以計算出來的

第八題
給了p,e,n,密文
要得出明文 跟前面有題有點像
不過這次多了p
所以我們其實是可以解的
因為c(ciphertext)有了 n有了
d是可以從n,p,e所得到

:::info
https://github.com/Dvd848/CTFs/blob/master/2018_picoCTF/rsa-madlibs.md
https://github.com/sefi-roee/CTFs-Writeups/blob/master/picoCTF-2018/Crypto/10-rsa_madlibs-250/solution.md
https://tcode2k16.github.io/blog/posts/picoctf-2018-writeup/cryptography/#rsa-madlibs
https://baotdvi.wordpress.com/2018/11/11/rsa-madlibs-picoctf-2018/
http://heell07.blogspot.com/2018/10/picoctf-2018-rsa-madlibs-write-up.html
:::

寫程式來讓以上流程自動
首先要可以連過去

利用pwn這個lib

send(payload) 發送payload
sendline(payload) 發送payload，並且進行換行（最後會加上\n）
sendafter(some_string, payload) 收到 some_string 之後,發送你的 payload
recvn(N) 接受 N個字元
recvline() 接受一行輸出
recvlines(N) 接收 N行輸出
recvuntil(some_string) 收到 some_string 為止

第一步連接過去

#!/usr/bin/python3      
import sys
import time
import socket
from pwn import *
hostname = '2018shell.picoctf.com'
port = 40440
r = remote(hostname, port)
print(r)Code language: JavaScript (javascript)

確認有連線過去

注意一點
比較麻煩的是使用pwn tools的時候
python3會自bytes python是strings
所以我這邊使用python3方式 利用decode才能work
https://mks.tw/2976/%E8%B3%87%E8%A8%8A%E5%AE%89%E5%85%A8-%E5%BE%9E%E6%AF%AB%E7%84%A1%E5%9F%BA%E7%A4%8E%E9%96%8B%E5%A7%8B-pwn-buffer-overflow

#!/usr/bin/python3      
import sys
import time
import socket
import binascii
from pwn import *
hostname = '2018shell.picoctf.com'
port = 40440
r = remote(hostname, port)
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while(a!=0):
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y
def inverse(q, p, e):
    phi = (q-1)*(p-1)
    gcd, a, b = egcd(e, phi)
    d = a%phi
    return d
# question 1
q1 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
q = int(q1[-5].split(' : ')[1])
p = int(q1[-4].split(' : ')[1])
r.sendline('y')
r.sendlineafter('n: ', str(p*q))
print('Question 1 Done!')

# question 2
q2 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
p = int(q2[-5].split(' : ')[1])
n = int(q2[-4].split(' : ')[1])
r.sendline('y')
r.sendlineafter('q: ', str(n/p))
print('Question 2 Done!')

# question 3
q3 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
r.sendline('n')
print('Question 3 Done!')

# question 4
q4 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
q = int(q4[-5].split(' : ')[1])
p = int(q4[-4].split(' : ')[1])
r.sendline('y')
r.sendlineafter('totient(n): ', str((p-1)*(q-1)))
print('Question 4 Done!')

# question 5
q5 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
plaintext = int(q5[-6].split(' : ')[1])
e = int(q5[-5].split(' : ')[1])
n = int(q5[-4].split(' : ')[1])
r.sendline('y')
r.sendlineafter('ciphertext: ', str(pow(plaintext, e, n)))
print('Question 5 Done!')

# question 6
q6 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
r.sendline('n')
print('Question 6 Done!')

# question 7
q7 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
q = int(q7[-6].split(' : ')[1])
p = int(q7[-5].split(' : ')[1])
e = int(q7[-4].split(' : ')[1])
r.sendline('y')
r.sendlineafter('d: ', str(inverse(q, p, e)))
print('Question 7 Done!')
# question 8
q8 = r.recvuntil('IS THIS POSSIBLE and FEASIBLE? (Y/N):').decode("utf-8").split('\n')
p = int(q8[-7].split(' : ')[1])
ciphertext = int(q8[-6].split(' : ')[1])
e = int(q8[-5].split(' : ')[1])
n = int(q8[-4].split(' : ')[1])
q = n/p
d = inverse(p, q, e)
r.sendline('y')
r.sendlineafter('plaintext: ', str(pow(ciphertext, d, n)))
print('Question 8 Done!')
# flag

lines = r.recvall()
print(lines)
ans = pow(ciphertext, d, n)
flag = hex(ans)
flag = flag[2:]
flag = flag[:len(flag)]
print(flag,'\n')
print(bytearray.fromhex(flag).decode())Code language: PHP (php)

(‘7069636f4354467b64305f755f6b6e30775f7468335f7740795f325f5253405f35643338336531307d’, ‘\n’)
picoCTF{d0_u_kn0w_th3_w@y_2_RS@_5d383e10}

題目: SpyFi

其實連題目都看不太懂

但是有給一段程式碼

#!/usr/bin/python2 -u
from Crypto.Cipher import AES
agent_code = """flag"""
def pad(message):
    if len(message) % 16 != 0:
        message = message + '0'*(16 - len(message)%16 )
    return message
def encrypt(key, plain):
    cipher = AES.new( key.decode('hex'), AES.MODE_ECB )
    return cipher.encrypt(plain).encode('hex')
welcome = "Welcome, Agent 006!"
print welcome
sitrep = raw_input("Please enter your situation report: ")
message = """Agent,
Greetings. My situation report is as follows:
{0}
My agent identifying code is: {1}.
Down with the Soviets,
006
""".format( sitrep, agent_code )
message = pad(message)
print encrypt( """key""", message )Code language: PHP (php)

可以連過去看看
nc 2018shell.picoctf.com 34490

hint問說使用甚麼mode

看一下code
可以看出使用AES加密
ECB Mode 長度不足16的會用0做padding

先看看ECB的方式https://zh.wikipedia.org/wiki/%E5%88%86%E7%BB%84%E5%AF%86%E7%A0%81%E5%B7%A5%E4%BD%9C%E6%A8%A1%E5%BC%8F

非常單純 就是明文分成幾個區塊做獨立的加密

所以兩個一樣的區塊
加密出來的內容會一樣的
可以參考這篇的解說
https://xz.aliyun.com/t/3099

唯一成功的payload
https://tcode2k16.github.io/blog/posts/picoctf-2018-writeup/cryptography/

from pwn import *
import string
context.log_level = 'error'
def serverTest(p):
  sh = remote('2018shell.picoctf.com', 34490)
  # sh = process('./spy_terminal_no_flag.py')
  payload = p
  print payload
  sh.sendlineafter(': ', payload)
  data = sh.recvall()
  blocks = []
  for i in range(0, len(data), 32):
    blocks.append(data[i:i+32])
  return blocks
output = ''
n = 30-15 + len(output)
while True:
  sample = serverTest('a'*10+'a'*(128-n))[12]
  for e in 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_/{/}!@#$%^&*()!':
    if e != '\n':
      pass
    if len(output) < 15:
      payload = 'a'*11+'My agent identifying code is: '[-15-15+n:]+output+e
    else:
      payload = 'a'*11+output[-15:]+e
    if serverTest(payload)[4] == sample:
      output += e
      n += 1
      print outputCode language: PHP (php)

picoCTF{@g3nt6_1$_th3_c00l3$t_4635097}

題目: Super Safe RSA

連線過去
nc 2018shell.picoctf.com 59208

有以下的
c: 11908610272529694976839346145506718134424483325162427330827923979426596022535046
n: 21925898401461883830470394420359456865403082378342545381878535990401366139324883
e: 65537

要你解開密文
跟Safe RSA那題一樣給了c,n,e
但是這題的e不是3了
所以沒辦法用同樣方法去解

反而是n並不是非常大
而我們知道n=q * p
所以可以嘗試利用暴力破解方式去解出p跟q
如果成功 這樣我們解密的參數就都有了

利用線上工具
https://www.alpertron.com.ar/ECM.HTM

解出p跟q

19 881243 129296 313418 497231 519706 301581 275544 862665 577507 337928 344685 407936 475693 (80 digits) = 153 438124 862853 157064 138420 841334 176127 (39 digits) × 129571 728975 876542 947066 098862 041423 704659 (42 digits)

p: 153438124862853157064138420841334176127
q: 129571728975876542947066098862041423704659
c: 500841937419866240176360707812663643310328691046177338067474122450639436050850
n: 19881243129296313418497231519706301581275544862665577507337928344685407936475693
e: 65537

plaintext: 13992908697345007896469122886569173422764307521738516337074498079782891381842704L
解出來的明文怪怪的

利用另一個code成功解出

from Crypto.Util.number import inverse
p = 153438124862853157064138420841334176127
q = 129571728975876542947066098862041423704659
c = 500841937419866240176360707812663643310328691046177338067474122450639436050850
e = 65537
n = 19881243129296313418497231519706301581275544862665577507337928344685407936475693
phi = (q-1)*(p-1)
d = inverse(e, phi)
print (hex(pow(c,d,n))[2:-1]).decode('hex')Code language: JavaScript (javascript)

picoCTF{us3_l@rg3r_pr1m3$_3432}Code language: PHP (php)

題目: eleCTRic

先連過去看看
nc 2018shell.picoctf.com 61333

重點還是有source code 所以就看看code吧

首先可以從題目與內容知道
這題考的就是AES的CTR mode
可以看一下文章來先做基本的認識CTR mode
https://zh.wikipedia.org/wiki/%E5%88%86%E7%BB%84%E5%AF%86%E7%A0%81%E5%B7%A5%E4%BD%9C%E6%A8%A1%E5%BC%8F
https://wumansgy.github.io/2018/11/03/AES%E7%9A%84CTR%E6%A8%A1%E5%BC%8F%E5%8A%A0%E5%AF%86%E8%A7%A3%E5%AF%86%E8%AF%A6%E8%A7%A3/

CTR mode為串流加密法（Stream cipher）
16 bytes = 128 bits

仔細看source code
發現一個有趣的點

class AESCipher(object):
    def __init__(self):
        self.bs = 32
        random = Random.new()
        self.key = random.read(AES.block_size)
        self.ctr = random.read(AES.block_size)
    def encrypt(self, raw):
        cipher = AES.new(self.key, AES.MODE_CTR, counter=lambda: self.ctr)
        return cipher.encrypt(raw).encode('base64').replace('\n', '')

nonoce + counter當中的counter是一個constant
所以每一個key加密出來的內容會是一樣的

https://blog.srikavin.me/posts/5bc15a23b7c5001b74f57e51-picoctf-2018-electric

C密文 P明文 F=(key,nonce)
所以第一個密文C1
C1 = P1 XOR F1
而我們如果有C1與P1的話
因為F1 = C1 XOR P1

那另一個密文C2
C2 = P2 XOR F2
因為F1等於F2
所以 C2 = P2 XOR C1 XOR P1

code裡面確認到裡面有get flag function

https://github.com/ashutosh1206/Crypton/tree/master/Block-Cipher/Attack-CTR-Bit-Flipping

這篇的概念說的滿好
https://blog.srikavin.me/posts/5bc15a23b7c5001b74f57e51-picoctf-2018-electric
但我這邊的code解開
https://github.com/sefi-roee/CTFs-Writeups/blob/master/picoCTF-2018/Crypto/13-eleCTRic-400/solution.md

整個流程是這樣
我們先取得flag檔案的名稱 就是P2
然後我們加密一個檔案 檔名為P1 會得到密文C1
並且因為F皆為相同的
所以我們可以得到C2 = P1 XOR C1 XOR P2

picoCTF{alw4ys_4lways_Always_check_int3grity_6c094576}