23 Apr 2025
---
layout: post
title: "Textbook-DSA2"
categories: [Algorithm]
tags: [dsa, signature, security, python, cryptography]
last_modified_at: 2025-04-23
---
```python
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
from random import randrange, choices
from hashlib import sha1
import string
class DSA(object):
def __init__(self):
print('generating parameters...')
while True:
self.q = getPrime(160)
r = randrange(1 << 863, 1 << 864)
self.p = self.q * r + 1
if self.p.bit_length() != 1024 or isPrime(self.p) != True:
continue
h = randrange(2, self.p - 1)
self.g = pow(h, r, self.p)
if self.g == 1:
continue
self.x = randrange(1, self.q)
self.y = pow(self.g, self.x, self.p)
self.k = randrange(1, self.q)
break
def update(self):
self.k = randrange(1, self.q)
def sign(self, msg):
r = pow(self.g, self.k, self.p) % self.q
h = bytes_to_long(msg) % self.q
s = inverse(self.k, self.q) * (h + self.x * r) % self.q
self.update()
return (r, s)
def verify(self, msg, sig):
r, s = sig
if s == 0:
return False
s_inv = inverse(s, self.q)
h = bytes_to_long(msg) % self.q
e1 = h * s_inv % self.q
e2 = r * s_inv % self.q
r_ = pow(self.g, e1, self.p) * pow(self.y, e2, self.p) % self.p % self.q
if r_ == r:
return True
else:
return False
dsa = DSA()
token = "".join(choices(string.ascii_letters + string.digits, k=32)).encode()
print("Welcome to dream's DSA server")
while True:
print("[1] Sign")
print("[2] Verify")
print("[3] Get Info")
choice = input()
if choice == "1":
print("Input message (hex): ", end="")
msg = bytes.fromhex(input())
if msg == token:
print("Do not cheat !")
else:
print(dsa.sign(msg))
elif choice == "2":
print("Input message (hex): ", end="")
msg = bytes.fromhex(input())
if len(msg) > 100:
print("Too long message")
else:
print("Input signagure (r, s as decimal integer): ", end="")
sig = map(int, input().split(", "))
if dsa.verify(msg, sig) == True:
print("Signature verification success")
if msg == token:
print(open("flag", "rb").read())
else:
print("Signature verification failed")
elif choice == "3":
print(f"p = {dsa.p}")
print(f"q = {dsa.q}")
print(f"g = {dsa.g}")
print(f"y = {dsa.y}")
print(f"token = {token}")
else:
print("Nope")
전자 서명 알고리즘은 DSA라고 함
플래그 획득 조건: 2번 메뉴에서/ r,s 값을 받고 / msg, sig를 verify해서 True / 그리고 msg==token이면/ flag 프린트
h값이 생성되는 방법:
from pwn import *
from Crypto.Util.number import *
io = remote("host3.dreamhack.games",20726)
io.sendline(b"3")
def recv():
io.recvuntil(f"= ".encode())
return eval(io.recvline())
p, q, g, y, token = [recv() for _ in range(5)]
token_int = bytes_to_long(token)
forge_token = long_to_bytes(token_int + q)
io.sendline(b"1")
io.sendlineafter(b": ", bytes.hex(forge_token).encode())
r, s = eval(io.recvline())
io.sendline(b"2")
io.sendline(bytes.hex(token).encode())
io.sendline(f"{r}, {s}".encode())
io.recvuntil(b"success\n")
flag = eval(io.recvline()).decode()
io.close()
print(flag)
-
수동탐색 : 직접 써보기
MTSM..
-
구글해킹 :
site
inurl
intitle
link
filetype
Wildcard(*) 해킹 * 배우는 법이라고 하면 해킹과 배우는 법 사이 모든 문자가 옴
큰따옴표 공백 포함해서 검색하고 싶을 때
admin site:target.com 이런 식으로 검색
inurl로 알지 못했던 도메인도 발견 가능
intitle 디렉토링 리스팅 취약점
link 특정 링크를 포함한..
실제 버그헌팅 할 때) targetSystem.com을 헌팅할 때
site:.targetSystem.com ->
site:.targetSystem.com inurl: admin
site:s3.amazonaws.com
site:*.targetSystem.com ext:txt password
inurl:/etc/passwd root
0:0:root:/root:/bin/bash -> LFI 취약점 검색
intitle: index of
GHDB 사이트 활용
- 스파이더링
ZAP (OWASP Zed Attack Proxy)
버프 스위트랑 비슷한 툴
Web Spidering/Web Crawling -> 사이트에서 확인할 수 있는 모든 페이지들을 식별하는 것
api 다 보여줌
- S3 bucket
숨겨진 서버, 로그, 크리덴셜, 사용자 정보, 소스코드
DB 구축 대신 쓰거나 백업용서버로 사용
site: s3.amazonaws.com [Target]
site:amazonaws.com [Target]
GrayhatWarfare이란 툴 -> 웹으로 실행 가능
Bucket Stream -> CT로 도메인 이름 찾아냄 (CT: 인증서를 감시/관리하는 시스템)
- github recon
타겟 회사 이름, 프로젝트 이름, 개발자 이름(닉네임) 조사 후 검사
Issues / Code commits 현황 조사
Code History 및 Blame 내역 활용
-> API key, 암호화 key, DB 비밀번호 등 찾을 수 있음
키워드는 key, secret, password, cred 등등…
Gitrob
TruffieHog
- Domain Enumeration
인증서의 SAN(subject Alternative name) 조사
SAN: 1개의 인증서에 여러 도메인 등록
리눅스에 amass 툴 사용으로 도메인 enumeration 가능
Mobile App Hacking
- 모바일 앱 공격
- 모바일 앱 서버 공격
Mobile App Attack
-> 모바일 앱의 흐름을 조작해서 악용하는 것
로그인 흐름인 것을 우회하거나
유료인 것을 무료로 우회하거나
Mobile App Server Attack
모바일 앱 서버 공격 -> 앱 서버 DB 데이터 추출
Web App: web view를 이용하여 만든 앱
Hybrid App, Native App
- Mobile App 취약점 분석 환경
Rooting / Jailbreak
단말기에서 root 획득하는 과정
안드로이드에서..
- Boot loader unlocked
- custom recovery
- custom ROM install
*Bootloader: 안드로이드 OS 부팅 초기에 실행, kernel을 RAM에 로드
-> 사용자가 펌웨어를 수정할 수 없도록 Bootloader locked를 건다
-> unlocked은 보통 fastboot mode에 들어가서.. fastboot oem unlock
Recovery & Custom Recovery
Recovery: android OS 유지 관리 기능 제공 (백업이나 기기 초기화 등..)
Custom Recovery에서는 제한 기능을 우회하기 위한 AOSP에서 제공하는 Recovery+몇가지 추가
fastboot mode 이용하여 설치 -> 안되면 Odin
Android ROM -> Android 기기 펌웨어
Custom ROM -> setuid 권한을 가진 su binary 추가한 버전 -> custom recovery를 이용하여 설치
Jailbreak -> iOS에서 root 권한 획득
해당 버전의 취약점이 있어야 Jailbreak 가능
checkra1n, Unc0ver, Taurine, Unc0ver 등…
서치는 “Programs used to jailbreak 14.x cve” 등..
jailbreak 종류는 아래와 같음
- untethered jailbreak
- tethered jailbreak
- semi tethered jailbreak
3utools 이용
만약 탈옥이 되면 Cydia나 Sileo라는 앱 사용 가능
tweak?
Proxy 세팅
단말기 app과 app 서버 사이 프록시 연결
일단 이거 관련한 실습은 노션에 자료 올려둠
같은 와이파이에 연결되어 있어야 함
https 통신을 하기 때문에 버프 인증서 설치가 필요함
일단 루팅을 해야함!!!!!!!!!!!!!!
Nox 앱 플레이어로 실습해볼 수도 있음
Android App
Android Runtime으로는 세 가지가 있다
1) JVM
Java에서 bytecode로…
이 bytecode를 JVM에서 실행
2) Dalvik VM
bytecode 실행 전 네이티브 코드로 -> JIT 컴파일
3) ART
OAT file 실행
앱 설치 시 완전 네이티브 코드로 변환 -> AOT 컴파일
DEX -> android 실행 파일
Smali -> Dalvik code를 위한 어셈블리 언어
java code를 dalvik을 위해 smali라는 어셈블리로 변환
Android App 위변조 방지
코드 서명: 개발자 본인의 코드 서명 인증서로 서명 -> 공격자의 악성 패치 앱 배포를 막기 위해
APK 구조
cpu에 따른 lib가 다름
Activity, Activity 생명 주기
activity: 사용자와 상호작용/ 화면/ 하나의 클래스
리버싱할 때 위 그림 기준으로 확인하기
Broadcast receiver
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from flag import FLAG
def getSafePrime(n):
while True:
p1 = getPrime(n)
p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653
p2 = 2*p1 + 1
if isPrime(p2):
return p1, p2
while True:
p1, p2 = getSafePrime(1024)
q1 = getPrime(1024)
q2 = getPrime(1024)
e = 0x10001
if (p1 - 1) * (q1 - 1) % e == 0:
continue
if (p2 - 1) * (q2 - 1) % e == 0:
continue
N1 = p1 * q1
N2 = p2 * q2
break
FLAG1 = bytes_to_long(FLAG[ : len(FLAG)//2])
FLAG2 = bytes_to_long(FLAG[len(FLAG)//2 : ])
# RSA encryption 1
FLAG1_enc = pow(FLAG1, e, N1)
print(f"{N1 = }")
print(f"{e = }")
print(f"{FLAG1_enc = }")
# RSA encryption 2
FLAG2_enc = pow(FLAG2, e, N2)
print(f"{N2 = }")
print(f"{e = }")
print(f"{FLAG2_enc = }")
일단 p1을 아니까 N1도 아니까 q1도 구할 수 있음
N1/p1=q1
d=pow(e,-1,(q1-1)*(p1-1))
long_to_bytes(pow(enc,d,N1))
걍 코드를 짜보겠다
from Crypto.Util.number import long_to_bytes
p1 = 122925338396977892377812264658939951801210314312238212067059595148447406166769716855936119104014353481162826500622396956338370238037713303129667973570418205129792800094492802512333202767609745542480301632710243676880179931490273979269048908687034938065216226244568368994455058377505090061149006930577060428653
N1 = 19327201401631091708078119279128692380925436148753032544895352594739110282713758787694579835391781210402243077561190953131900323053423046549084383867230010218276408621326328657011461469470863807292770977339969966619084182213730972103570599543306681902985938663544751982304914890625033249271730565010591288864800205047761519021424394075419080844544837213852439849121802683213686553168522746043462188813484812435077464939031324951004504043502401170179833768423690231004598616247184121591410659261674988936191040818361630775820141493597159203856838814572719736836706893107415465623258821901349346519326330233623214728221
FLAG1_enc = 13004466492825661714373794815483060213694105615136425500989349693819961897670052449133543120631375577093758006042616662397161828589759021109123036143679110213645273703495254751289251984825741644206592407373383229795977571891490892303010088149447806230252355167293296067357472058390377966149510304189768318019106010038464918342981779040801334805493934402083256202515878968471566745346269521478477710514882908808895056775440776187428798107877812935170817655999121652544951651932298324706467047940709230959842386229472100688721362825588490871211182464995770751546581073841668835160521366577198069608693267099763820863798
N2 = 27450043483315478797311762404726094577043502998132803099792119462966972085300899948161891817110329463991628866797190656347290669289715965306807327781311775199098217243334803546897391127316534191753025750966088057417220995637276594988237432346097632955067112307495374843098339005553306641285945162968651827001664879318348061935910034735641200929274386097426194176189548233606952782529875735520470196679662317949279351304878856061765216511421722100868900219446793017053639756452344855640565216220821535719191238236595833273152962271929229104781027974482540785947824462470111459855576434011643733382300240759662671745043
e = 65537
FLAG2_enc = 17463642564205701432307028203763062907371381377693194828300595918415046220812120475428225071119982138749111622652127381786090687125183190277170778539362877193467937714016137568118933014547356440506555629558154283687808070558309970344505816619533040961898974711852132964742029858929057461119543575535330375800427250608222111417772757317328946180150624934340736646008296127968384530576375036996310505498939822504071130031960700949736356441252292463128173777657044615516176593682581668414273678552105485641336500940770941508284916043004595128850506708764616933566005759493826241800383490202557574106404650701685720400402
flag=b""
# RSA decryption 1
q1 = N1 // p1
oil1 = (q1 - 1) * (p1 - 1)
d1 = pow(e, -1, oil1)
FLAG1_dec = pow(FLAG1_enc, d1, N1)
flag+=long_to_bytes(FLAG1_dec)
# RSA decryption 2
p2 = 2*p1 + 1
q2 = N2 // p2
oil2 = (q2 - 1) * (p2 - 1)
d2 = pow(e, -1, oil2)
FLAG2_dec = pow(FLAG2_enc, d2, N2)
flag+=long_to_bytes(FLAG2_dec)
print(flag)
