Description

Category: Misc/Coding

Source: ASIS CTF 2019 Quals

Points: 67

Description:

Warm-up your fingers to capture next flags!

nc 37.139.9.232 19199 ## Write-up

주어진 사이트에 접속해보면 먼저 PoW(Proof Of Work)을 요구한다. PoW는 sha1, sha2, md5의 다양한 hash 알고리즘에 대해서 나오는데, PoW를 풀고 나면 본격적인 문제가 나온다.

주어진 길이에 따라 두 개의 ASIS CTF flag 형식의 문자열을 생성하면 되는데, 두 문자열의 CRC32 값이 같아야 한다고 한다.

CRC32 collision generator를 찾아보다가 이 사이트에서 forcecrc32.py를 찾았는데, 이 라이브러리는 특정 파일에서 주어진 위치의 4 바이트를 수정하여 원하는 CRC32 값을 갖도록 해주는 기능을 갖고 있다.

해당 파일을 받아서 아래와 같이 변경하였다.(code)

  • 파일명 입력 --> 데이터 입력
  • 길이를 입력받아 ASIS CTF flag 형태의 임의의 문자열 s1, s2 생성 후, crc32(s2)가 crc32(s1)과 동일해지도록 s2를 수정

조건에 맞는 s1, s2를 구해서 서버로 전송하면 동일한 형태의 길이만 다른 다음 문제가 나온다.

loop을 이용하여 계속 문제를 풀어나가다 보면 flag를 얻을 수 있다.(code)

Flag : ASIS{3asy_c0din9_fOr_W4rM_UP}

'writeups > Coding|misc.' 카테고리의 다른 글

REDACTED-PUZZLE  (0) 2019.11.26
KNOW_YOUR_MEM  (0) 2019.11.26
Project Eulernt  (0) 2019.11.26
Who do I trust?  (0) 2019.11.25
SQL  (0) 2019.11.25

Description

Category: Misc

Source: PlaidCTF 2019

Points: 200

Description:

Guys, guys, don’t fight. I’m sure we’ll be able to come up with something roughly equal.

source

eulernt.pwni.ng:5555

Write-up

[...]

N = int(gmpy2.fac(333))
#N = 10334465434588059156093965538297516550622260[...]
sN = int(gmpy2.isqrt(N))
#sN = 3214726338988757399964463840205273148284735[...]

k = int(input("Enter number: "))

goodness = Decimal(abs(k - sN)) / sN 

if k and N % k == 0 and goodness < 1e-8:
    print(open('/home/eulernt/flag.txt').read())
elif k and N % k == 0 and goodness < 1e-4:
  print("Good work! You're getting there.")
else:
    print("Nope!")

N = 333!이고, sN = sqrt(N)이다. 아래쪽의 if문을 살펴보면, N의 약수 중에 sN과 거의 유사한(10-8 정확도) 어떤 수 k를 찾아야 하는 것을 알 수 있다.

N은 333!이니, 1부터 333까지의 숫자를 최대 한번씩만 사용해서 k를 만들어야 조건을 만족할 수 있을 것이다.

문제 제목이 오일러(euler)와 유사하길래 도움이 될만한 수학 공식이 있는지 살펴 보았으나 찾지는 못했다. 그래도 미련을 못버리고 한참을 찾아보다가, 문제 분류가 Misc인 것을 보고 찾는 것을 포기했다.

알고리즘을 생각해보자. a * b == N일 때, a와 b가 비슷한 크기를 가진다면 a와 b는 sN에 가까운 수가 될것이다.

일단 N을 대충이나마 엇비슷하게 반으로 쪼갤 수 있는 알고리즘을 생각해 보았다.

a = 1
b = 1

#1. init
for i in range(2, 333, 2):
  c = abs(a * i - b * (i + 1))
  d = abs(a * (i + 1) - b * i)

  if (c < d):
    #c is better
    a *= i
    b *= i + 1
  else:
    a *= i + 1
    b *= i

(2, 3), (4, 5), (6, 7)... 을 번갈아가면서 a와 b에 각각 곱해가는데, a와 b의 차이가 적어지는 방향으로 곱하도록 하였다. 이렇게 해서 a와 b를 구한 후 sN과 비교해 보면 대충 아래와 같은 것을 확인할 수 있다.

sN / a = 1.00150466738
sN / b = 0.998497593247

아직 갈 길이 멀다. 여기서 어떻게 더 개선을 할 수 있을까 고민하다가, sN에 더 가까워 지기 위해 양쪽에 곱해준 수들을 트레이드 하는 방법을 생각해 보았다. 예를 들면, sN/a = 1.0015이니, a에 곱했던 어떤 수 k1와 b에 곱했던 어떤 수 k2가 k2/k1 = 1.0015를 만족한다면 a에서 k1을 빼고 k2를 곱하면 a == sN이 될 것이다.

먼저, a와 b가 어떤 수들의 곱인지 알 수 있도록 a와 b를 계산할 때 list를 만들었다. 그리고는 2차원 loop을 돌면서 sN/a와 가장 가까운 (k2/k1)의 조합을 찾아서 트레이드를 하도록 하였다.

... 전혀 개선되지 않았다. 역시나 이렇게 쉽게 풀리진 않을 것 같았다.

선수 풀이 너무 작은 것 같아서, 1:1이 아닌 1:2, 2:1, 2:2 트레이드도 가능하도록 알고리즘을 개선해 보았다. 각 리스트 내에서 1개 또는 2개 원소의 곱으로 만들 수 있는 숫자들을 모두 모아서 새로운 리스트를 만들어 최적의 트레이드 조건을 찾아보았다.

약간의 시간이 걸리긴 했지만, 괄목할만한 결과를 만들어 내었다. a팀에서 241, 273을 보내고 b팀에서 204, 323을 받아오는 트레이드로, 무려 10-7의 정확도로 a, b를 찾아낼 수 있었다.

이번엔 최대 3명의 트레이드가 가능하도록 변경하고, 너무 오랜 시간이 걸릴 것이 예상되었기 때문에 종료 조건도 추가해서 다시 실행하였다.(code)

다행히 생각보다 오래 걸리지는 않아서(반나절 이상은 걸릴 줄 알았으나) 몇십분 정도 후에 10-9 이상의 정확도를 갖는 a, b를 찾을 수 있었고, 이를 이용해서 flag를 얻었으나 이미 대회는 종료된 뒤였다(...)

Flag : PCTF{R3fr3sh1ngly_Sm00th}

이후에 암호천재님의 조언을 받아 알고리즘을 개선하였다.

  • N = 1 * 2 * 3 * ... * 332 * 333 = 2238 * 3165 * 581 * ... * 313 * 317 * 331

이므로, sN = sqrt(N)은 아래와 같이 쓸 수 있다.

  • sqrt(N) = 2119 * 382 * 540 * ... * sqrt(3 * 5 * ... * 313 * 317 * 331) = x * sqrt(y)

그러므로, 위의 문제 k | N, k ≈ sN을 만족하는 k 찾기는 k' | y, k' ≈ sN/x를 만족하는 k'을 찾는 문제로 다시 쓸 수 있다.

생긴건 동일하지만 찾아야 하는 수의 범위가 훨씬 줄어들었다.

기존의 코드에서 크게 변경할 것 없이, 알고리즘의 전단계에서 N을 y로 바꿔주고 sN을 sN/x로 바꾸기만 하면 된다. 다만, 범위가 줄어든 만큼 조합을 찾는 것도 어려워 졌기 때문에 5개의 순서쌍까지 후보에 넣어야 solution을 찾을 수 있었으나, 소요 시간은 훨씬 줄어 1분 내에 알고리즘이 종료되었다.(code) 3초짜리 알고리즘은 대체....


'writeups > Coding|misc.' 카테고리의 다른 글

KNOW_YOUR_MEM  (0) 2019.11.26
Flag collision  (0) 2019.11.26
Who do I trust?  (0) 2019.11.25
SQL  (0) 2019.11.25
plz variable  (0) 2019.11.25
rop

Description

Category: Pwnable

Source: pwnable.kr

Points: 7

Author: Jisoon Park(js00n.park)

Description:

Voldemort concealed his splitted soul inside 7 horcruxes.
Find all horcruxes, and ROP it!
author: jiwon choi

ssh horcruxes@pwnable.kr -p2222 (pw:guest)

Write-up

서버에 접속하여 바이너리를 실행시켜보면 7개의 horcruxes를 찾으라고 하면서 메뉴를 선택하라고 한다.

main() 함수부터 decompile 하여 차근차근 살펴보자.

int __cdecl main(int argc, const char **argv, const char **envp)
{
  int v3; // ST1C_4

  setvbuf(stdout, 0, 2, 0);
  setvbuf(stdin, 0, 2, 0);
  alarm(0x3Cu);
  hint();
  init_ABCDEFG();
  v3 = seccomp_init(0);
  seccomp_rule_add(v3, 0x7FFF0000, 173, 0);
  seccomp_rule_add(v3, 0x7FFF0000, 5, 0);
  seccomp_rule_add(v3, 0x7FFF0000, 3, 0);
  seccomp_rule_add(v3, 0x7FFF0000, 4, 0);
  seccomp_rule_add(v3, 0x7FFF0000, 252, 0);
  seccomp_load(v3);
  return ropme();
}

alarm() 까지는 별로 볼것 없고, hint는 화면에 welcome message를 출력해주는 함수이다. seccomp를 이용해서 system call들을 필터링 하는 부분도 대충 제외하고 나면 init_ABCDEFG() 함수와 ropme() 함수가 남는다.

unsigned int init_ABCDEFG()
{
  int v0; // eax
  unsigned int result; // eax
  unsigned int buf; // [esp+8h] [ebp-10h]
  int fd; // [esp+Ch] [ebp-Ch]

  fd = open("/dev/urandom", 0);
  if ( read(fd, &buf, 4u) != 4 )
  {
    puts("/dev/urandom error");
    exit(0);
  }
  close(fd);
  srand(buf);
  a = 0xDEADBEEF * rand() % 0xCAFEBABE;
  b = 0xDEADBEEF * rand() % 0xCAFEBABE;
  c = 0xDEADBEEF * rand() % 0xCAFEBABE;
  d = 0xDEADBEEF * rand() % 0xCAFEBABE;
  e = 0xDEADBEEF * rand() % 0xCAFEBABE;
  f = 0xDEADBEEF * rand() % 0xCAFEBABE;
  v0 = rand();
  g = 0xDEADBEEF * v0 % 0xCAFEBABE;
  result = f + e + d + c + b + a + 0xDEADBEEF * v0 % 0xCAFEBABE;
  sum = result;
  return result;
}

init_ABCDEFG 함수는 urandom에서 읽어온 값을 seed로 설정해주고 a, b, c, d, e, f, g 값을 설정 후 이들을 더해서 sum을 만드는 함수이다. 이 변수들은 모두 전역변수로 선언되어 있다.

int ropme()
{
  char s[100]; // [esp+4h] [ebp-74h]
  int v2; // [esp+68h] [ebp-10h]
  int fd; // [esp+6Ch] [ebp-Ch]

  printf("Select Menu:");
  __isoc99_scanf("%d", &v2);
  getchar();
  if ( v2 == a )
  {
    A();
  }
  else if ( v2 == b )
  {
    B();
  }

  [...]

  else if ( v2 == g )
  {
    G();
  }
  else
  {
    printf("How many EXP did you earned? : ");
    gets(s);
    if ( atoi(s) == sum )
    {
      fd = open("flag", 0);
      s[read(fd, s, 0x64u)] = 0;
      puts(s);
      close(fd);
      exit(0);
    }
    puts("You'd better get more experience to kill Voldemort");
  }
  return 0;
}

ropme() 함수는 int 타입의 menu 값을 입력받아서 a, b, c, d, e, f, g 중 하나의 값과 동일하다면 각각 A(), B(), C(), D(), E(), F(), G() 함수를 호출하여 a, b, c, d, e,f, g의 값을 다시 출력해주고 있다.

입력한 값이 a부터 g까지의 변수들과 모두 다르다면 획득한 exp를 물어보는데, 이 값이 sum과 동일한 경우에 flag를 출력해준다.

프로그램의 동작을 찾았으니, 취약점과 공략 방법을 생각해 보자. 다행히 프로그램이 복잡하지 않아 확인할 부분이 많지는 않다.

어렵지 않게 지역변수 s에 대해 gets() 함수가 사용되어 bufffer overflow가 발생하는 것을 알 수 있다.

바이너리의 정보를 확인해 보면 canary와 PIE 모두 사용되지 않는 것으로 보이니 flag를 보여주는 부분으로 return address를 덮어써서 간단하게 해결할 수 있을 것 같다.

IDA에서 flag를 출력해주는 부분의 주소(0x80A010B)를 확인해서 return address에 덮어쓰도록 gets()에 입력값을 넣고 실행해보자.

정상적으로 실행되지 않고 그냥 프로세스가 종료되어 버린다. 왜이런가 하고 자세히 봤더니, 입력으로 넣어준 주소에 0x0A가 들어있어서 gets에 입력이 들어가다가 만 것 같다.

함수들의 주소를 잘 보면 main 함수의 끄트머리부터 0x080A0000 영역에 들어가게 된다. 역시 문제에서 주어진대로 rop를 해서 sum의 값을 알아내야 할 것 같다.

sum을 위해서는 a의 값을 알아내야 하고, a의 값을 알아내기 위해서는 A() 함수를 호출시켜야 하는데, A() 함수는 a의 값을 알아야 호출할 수 있다.

뭐 이건 정상적인 경우의 얘기고, A()부터 G() 함수의 주소들을 보면 사용하지 않아야 하는 값들이 없으므로 ropme 함수의 return address를 변조해서 A() 부터 G() 함수까지 호출되도록 해보자.

일단 return address에는 A() 함수의 값을 써주면 된다. 그럼 ropme 함수의 ret instruction이 A() 함수의 주소를 pop 하여 eip에 넣어서 A() 함수에 진입하게 해줄거고, 마찬가지로 A() 함수의 에필로그에 있는 ret instruction이 스택에서 그 다음에 있는 값을 pop 하여 eip에 넣어줄 것이다.

보통 ROP를 할 때는 호출하는 함수의 argument를 구성하기 위해 stack 구성이 좀 더 복잡해지고 pop-pop-ret 등의 가젯이 필요한데, 이 문제에서 호출할 함수들은 argument가 필요하지 않아서 그냥 A() 부터 G() 함수의 값을 스택에 순서대로 넣어주면 된다.

그렇게 하면 함수들이 순서대로 수행되면서 a부터 g의 값을 알게 되어 sum을 계산할 수 있다.

마지막으로 G() 함수의 주소 다음에 ropme()가 한번 더 실행되도록 ropme의 주소(0x0809fffc)를 넣어주면 sum을 입력한 후 flag를 확인할 수 있게 된다. (ropme()의 주소에 0x0a가 있어서, main() 함수의 마지막에 ropme를 호출하는 call instruction의 주소를 넣었다.) (code)

Flag : Magic_spell_1s_4vad4_K3daVr4!

'writeups > Pwnable' 카테고리의 다른 글

2 small 2 Pwn  (0) 2019.11.26
speedrun-002  (0) 2019.11.26
shellql  (0) 2019.11.26
two targets  (0) 2019.11.26
Welcome  (0) 2019.11.26
RSA

Description

Category: Crypto

Source: PlaidCTF 2019

Points: 150

Author: Jisoon Park(js00n.park)

Description:

Tears dripped from my face as I stood over the bathroom sink. Exposed again! The tears melted into thoughts, and an idea formed in my head. This will surely keep my secrets safe, once and for all. I crept back to my computer and began to type.

Write-up

주어진 텍스트 압축 파일을 풀어보면 CRT를 이용하는 RSA en/decryption 코드가 있다.

[...]

class Key:
  PRIVATE_INFO = ['P', 'Q', 'D', 'DmP1', 'DmQ1']
  def __init__(self, **kwargs):
    for k, v in kwargs.items():
      setattr(self, k, v)
    assert self.bits % 8 == 0

  def ispub(self):
    return all(not hasattr(self, key) for key in self.PRIVATE_INFO)

  def ispriv(self):
    return all(hasattr(self, key) for key in self.PRIVATE_INFO)

  def pub(self):
    p = deepcopy(self)
    for key in self.PRIVATE_INFO:
      if hasattr(p, key):
        delattr(p, key)
    return p

def genkey(bits):
  assert bits % 2 == 0
  while True:
    p = genprime(bits // 2)
    q = genprime(bits // 2)
    e = 65537
    d, _, g = egcd(e, (p-1) * (q-1))
    if g != 1: continue
    iQmP, iPmQ, _ = egcd(q, p)
    return Key(
      N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
      iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
    )

[...]

RSA CRT를 위해 다양한 파라미터들을 생성하는데, public key를 export 할때는 P, Q, D, DmP1, DmQ1을 제외하고 N, E, iQmP, iPmQ, bits만 포함된 class instance를 pickle로 serialize 하도록 되어있다.

문제에서 주어진 key.sad.pub 파일이 이렇게 만들어진 파일이다.

일반적인 RSA 공개키 정보에 iPmQ = p-1 mod qiQmP = q-1 mod p가 추가로 주어진 셈인데, 이 정보를 이용해서 비밀키 정보를 알아내면 될것 같다.

암호천재님께서 하사하신 메모

위와 같이 정리하면 p에 대한 2차 방정식을 구할 수 있다.

ap + bq = 1 (mod q)이므로, 원래 ap + bq = 1 + kn이 되어야 하지만, 0 <= a < q, 0 <= b < p이기 때문에 ap + bq < 2n이라서 k = 1로 확정할 수 있다.

위의 2차 방정식에서 p를 제외한 모든 값을 알고 있으므로 근의 공식을 이용하면 양의 정수 p를 유일하게 얻을 수 있다.

그로부터 q, d, DmP1, DmQ1을 계산하면 주어진 코드의 decryption 함수를 사용하여 flag를 얻을 수 있다.(code)

Flag : PCTF{Rub_your_hands_palm_to_palm_vigorously_for_at_least_20_seconds_to_remove_any_private_information}

'writeups > Crypto' 카테고리의 다른 글

Noki  (0) 2019.11.26
Ez Pz  (0) 2019.11.26
Ezdsa  (0) 2019.11.26
Open-gyckel-krypto  (0) 2019.11.26
baby RSA  (0) 2019.11.26

Description

Category: Reversing

Source: PlaidCTF 2019

Points: 50

Author: Jisoon Park(js00n.park)

Description:

Let's do this together. You do know how to count, don't you?

Write-up

main() 함수를 보면 decimal string 형태의 flag를 1씩 증가시키면서 입력받은 값이 flag와 동일한지 확인 후 check_flag()로 원했던 flag 값 까지 도달했는지를 확인하고 있다.

[...]

  while ( 1 )
  {
    incr_flag();
    printf("> ");
    fflush(stdout);
    fgets(s, 30, stdin);
    if ( s[0] && s[strlen(s) - 1] <= 31 )
      s[strlen(s) - 1] = 0;
    if ( strcmp(s, flag_buf) )
    {
      printf("No, the correct number is %s.\n", flag_buf);
      puts("But I believe in you. Let's try again sometime!");
      exit(1);
    }
    v4 = get_compliment();
    puts(v4);
    check_flag();

[...]

check_flag() 함수가 핵심인 것 같다. 좀 더 들여다 보자.

[...]

  for ( i = 0; ; ++i )
  {
    if ( i > 19 )
    {
      printf("PCTF{% raw %}{%s}{% endraw %}\n", flag_buf);
      exit(0);
    }
    v0 = flag_buf[i];
    v1 = v0 & 3;
    v2 = (v0 >> 2) & 3;
    v3 = (v0 >> 4) & 0xF;
    LODWORD(v4) = rol(v1 + 0xA55AA55AA559LL, 2);
    v5 = v4;
    LODWORD(v6) = rol(v2 - v4 + 0xA55AA55AA559LL, 13);
    v7 = v6;
    LODWORD(v8) = rol(v3 - v6 + 0xA55AA55AA559LL, 17);
    v9 = v8;
    v10 = v7 ^ v8 ^ v5;
    LODWORD(v11) = rol((v7 & ~(v7 ^ v8 ^ v5) | v8 & (v7 ^ v8 ^ v5)) + v5 + v3 + 68453106630LL, 3);
    v12 = v11;
    LODWORD(v13) = rol((v9 & ~v11 | v10 & v11) + v7 + v1 + 68453106630LL, 11);
    v14 = v13;
    LODWORD(v15) = rol((v12 & ~v9 | v13 & v9) + v10 + v2 + 68453106630LL, 19);
    v16 = v15;
    LODWORD(v17) = rol((v14 ^ v9 ^ v15) + v12 + v2 + 201504941903014LL, 5);
    v18 = v17;
    LODWORD(v19) = rol((v16 ^ v17 ^ v14) + v9 + v1 + 201504941903014LL, 7);
    v20 = v19;
    LODWORD(v21) = rol((v18 ^ v14 ^ v19) + v16 + v3 + 201504941903014LL, 23);
    v22 = (unsigned int)((unsigned __int64)(v20 + v21 + v18 + v14) >> 32) ^ (unsigned __int64)(v20 + v21 + v18 + v14);
    v23 = (v22 >> 16) ^ v22;
    result = (unsigned __int8)(BYTE1(v23) ^ v23);
    if ( *((_BYTE *)check_buf + i) != (BYTE1(v23) ^ (unsigned __int8)v23) )
      break;
  }

[...]

대부분의 변수가 64bit 정수로 구성되어 있고, rol()을 이용한 계산을 거친 결과가 마지막 if문의 조건을 만족해야 한다.

unsigned __int64 __cdecl rol(unsigned __int64 a1, char sh)
{
  int high; // edx
  int low; // eax
  int v4; // ebx
  __int16 v5; // si
  unsigned __int64 v6; // rax
  unsigned __int64 result; // rax

  high = a1 << sh >> 32;
  low = (_DWORD)a1 << sh;
  if ( sh & 0x20 )
  {
    high = (_DWORD)a1 << sh;
    low = 0;
  }
  v4 = low;
  v5 = high;
  v6 = a1 >> ((48 - sh) & 0x1F);
  if ( (48 - sh) & 0x20 )
  {
    LODWORD(v6) = HIDWORD(v6);
    WORD2(v6) = 0;
  }
  LODWORD(v6) = v6 | v4;
  HIDWORD(result) = (unsigned __int16)(WORD2(v6) | v5);
  return result;
}

rol() 함수는 rotate left 동작을 하는데, rotate left를 임의로 구현했더니 동작 결과가 조금 달라서 주어진 rol() 함수를 그대로 이용해야 했다.

IDA가 decompile 해준 check_flag() 함수와 rol() 함수를 그대로 python으로 옮겼더니 제대로 동작하지 않았다. 64bit 연산이 적용된 경우에 IDA의 decompile이 부정확한 경우가 있어서, assembly 코드를 보고 python 함수를 구현했다.(code)

Flag : PCTF{2052419606511006177}

이렇게 해서 풀긴 풀었는데, 풀고 나서 다시 생각해보니 flag_buf에 들어있는 값들이 복잡해 보이지만 사실 딱 10종류이다.

check_flag() 함수를 자세히 보면 flag의 각 자리수를 검사하는데, 자리수 간에 의존성이 없으니 flag_buf에 있는 10가지 숫자가 0부터 9까지의 숫자에 1:1로 대응된다.

그냥 gdb에서 1부터 10까지 넣어가면서 if문의 비교 값들을 확인해봤으면 금방 풀 수 있었을텐데 assembly 코드를 한땀한땀 보느라 너무 많은 시간을 허비했다. 다른팀들 풀이 시간을 보니 20분 정도만에 풀었던데 아마도 그렇게 푼 것 같다.

'writeups > Reversing' 카테고리의 다른 글

Easy Crack Me  (0) 2019.11.26
Elementary  (0) 2019.11.26
ELF Crumble  (0) 2019.11.26
Super Secure Vault  (0) 2019.11.26
Feed_me  (0) 2019.11.25

Description

Category: Crypto

Source: WPICTF 2019

Points: 500

Author: Jisoon Park(js00n.park)

Description:

We caught two WPI students sending illegal secrets on our network... can you find out what they said?

made by rm -k and acurless
capture_final.pcapng

Write-up

주어진 pcapng 파일을 열어보면 TCP 통신 내역을 볼 수 있다. follow를 이용해서 내용을 살펴보자.

g, mod, pub 값이 있는 걸로 봐서는 대수 기반의 key exchange 알고리즘인 것 같다. DH(diffie-hellman) 아니면 elgamal일 것 같았는데, enc_key가 mod 보다 작은 값 하나로 구성된 것을 보니 elgamal은 아닌 것 같다. (elgamal은 암호문이 두 개의 값으로 구성된다.)

DH 프로토콜이라고 가정하고, 공격 방법을 생각해 보자. 사실 떠오르는 방법이 없었는데, DH의 wiki에 아래와 같은 말이 있었다.

The order of G should have a large prime factor to prevent use of the Pohlig–Hellman algorithm to obtain a or b.

order of G가 뭔지는 모르겠지만, Pohlig–Hellman algorithm이라는 것을 찾아봤다.

a = bx mod p로 정의된 식에서, a, b, p로부터 x를 찾아내는 계산법이었다. 여기를 보니 p - 1이 작은 소수들의 곱으로 표현되면 Pohlig–Hellman algorithm을 사용할 수 있다고 한다. 당장 p - 1을 인수분해 해보자.

yafu를 이용해서 인수분해를 시도해 보았더니, 0.0004초만에 아래와 같은 결과를 확인할 수 있었다.

p - 1 = 2^5 * 3^13 * 5^12 * 7^14 * 11^2 * 13^13 * 17^10 * 19^4 * 23^14 * 29^12

Pohlig–Hellman algorithm 자체를 이해할 수는 없어서, 구현체를 찾아보았다.

python 구현체를 찾아서 이용해 봤지만, 한참을 기다려도 연산이 끝나지 않았다.

다른 좋은게 없을까 고민하다가 sage가 생각나서 sage 구현체를 찾아서 시도해봤더니 바로 x를 찾을 수 있었다.

DH 알고리즘에서 x는 private key이고, 상대방의 public key pub에 대해 pubx mod p를 계산한 값이 shared_secret이다.

private key를 찾았으니 shared secret은 쉽게 계산할 수 있다.

다음에 온 메세지는 enc_key인데, 길이가 8로 나누어 떨어지지 않는 것을 보니 당연히 암호화 키 자체는 아니고, shared secret으로 암호화 해서 보낸 어떤 값인 것 같다.

어떤 식으로 암호화 한 것일까 고민해 보다가, shared secret과 데이터의 곱이 아닐까 싶어서 shared secret의 p에 대한 역수를 구해서 곱해주었더니 16바이트 길이의 값을 얻을 수 있었다.)

enc_key 다음에 오는 데이터가 32 바이트이니, 아마도 AES를 이용한 암호문이 아닐까 싶어서 위에서 얻은 16바이트 데이터를 key로 하여 AES-ECB 복호화를 시도하였더니 flag를 얻을 수 있었다.(code)

Flag : WPI{sTRuk_byA_$m0otH_cR!mIn@1}

'writeups > Crypto' 카테고리의 다른 글

Ez Pz  (0) 2019.11.26
R u SAd  (0) 2019.11.26
Ezdsa  (0) 2019.11.26
Open-gyckel-krypto  (0) 2019.11.26
baby RSA  (0) 2019.11.26

Description

Category: Crypto

Source: AceBear Security Contest 2019

Points: 831

Author: Jisoon Park(js00n.park)

Description:

Let's warm-up

link

Write-up

문제 설정은 매우 간단하다. n, e, c와 함께 (p + q)2019 mod n, (p + 2019)q mod n의 값이 주어진다. (각각 a, b라고 해두자)

여기서 private exponent를 찾아서 c를 복호화 하면 되는 문제이다.

[...]

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537

c = pow(m, e, n)

print(n)
# 13299187269178832408213486199795357[...]

print(c)
# 51298575439582965784709335152059190[...]

print(pow(p+q, 2019, n))
# 11662295269650372444446581690681292[...]

print(pow(p+2019, q, n))
# 46935581819524717607675319301313485[...]

우선 (p + 2019)q mod n = b을 살펴보자. q승을 한다는데서 페르마의 소정리를 이용할 생각을 쉽게 해볼 수 있다.

  • (p + 2019)q mod n = (p + 2019)(q - 1) + 1 mod n mod q = p + 2019 mod q = b mod q
  • p = b - 2019 (mod q)

다음으로 (p + q)2019 mod n = a을 풀어보자.

(a + c)b mod c = ab mod c 인 것을 활용하면 된다. (증명은 b가 0, 1일때는 자명하고, 2일때 부터는 귀납법을 이용하면 된다.)

  • (p + q)2019 mod n = p2019 mod n mod q = (b - 2019)2019 mod q = a mod q
  • (b - 2019)2019 - a = 0 (mod q)

그러므로, (b - 2019)2019 - a는 q의 배수이다. n 또한 q의 배수이니, 두 수의 GCD를 구하면 q의 값을 알 수 있다.

이제 순서대로 p, phi(n), d, m을 구하면 flag를 얻을 수 있다. (code)

Flag : AceBear{1_Hop3_1t_w4s_n0t_t00_34sy_f0r_U}

'writeups > Crypto' 카테고리의 다른 글

R u SAd  (0) 2019.11.26
backtalk  (0) 2019.11.26
Ezdsa  (0) 2019.11.26
Open-gyckel-krypto  (0) 2019.11.26
Blind  (0) 2019.11.26
RSA

Description

Category: Crypto

Source: Midnightsun CTF 2019

Points: 226

Author: Jisoon Park(js00n.park)

Description:

Primes are fun, don't google translate me bro

Download: gyckel.tar.gz

Author: grocid is available for questions in #midnightsun @ freenode
Status: Online

Write-up

(uphack 팀의 writeup을 참조하였습니다.)

주어진 텍스트 파일을 열어보면 간단한 python 코드와 RSA 공개키, 그리고 암호문을 찾을 수 있다.

while True:
    p = next_prime(random.randint(0, 10**500))
    if len(str(p)) != 500:
        continue
    q = Integer(int(str(p)[250:] + str(p)[:250]))
    if q.is_prime():
        break

>> p * q
61460246439415037572177153632567252974745825[...]
>> pow(m, 65537, p * q)
35720309045280131806911840318258750185600188[...]

500자리 10진수 소수인 p를 생성하고, 상위 250자리와 하위 250자리를 바꾼 값이 q라고 한다. 상위와 하위를 각각 250 자리의 십진수 a, b라고 하고 식으로 쓰면 아래와 같다.

  • p = a * 10250 + b
  • q = b * 10250 + a

문제에서 n = pq 값이 주어지는데, 이 값을 a, b로 써보면 아래와 같다. * n = pq = (a * 10250 + b)(b * 10250 + a) = ab * 10500 + (a2 + b2) * 10250 + ab

a와 b가 각각 250 자리의 수이니, a2는 최대 500 자리이고, a2 + b2는 500자리 수이거나 1로 시작하는 501자리 수가 될 것이다.

x = ab, y = a2 + b2라고 하면, 1000자리 십진수인 pq는 위의 식에 따라 아래와 같이 구성될 것이다.

xxxxxxxxxxxxxxxxxxxx
         cyyyyyyyyyyyyyyyyyyyy
                    xxxxxxxxxxxxxxxxxxxx

 where carry c is 0 or 1

위의 pq를 x와 y에 대해 다시 쓰면 pq = x * 10500 + y * 10250 + x가 된다. 500 자리의 x에서 상위 250자리와 하위 250자리를 (carry를 고려하면) 50% 확률로 알아낼 수 있다. x를 알아내고 나면 pq, x, y에 대한 식을 정리해서 y의 값도 알아낼 수 있다.

RSA 비밀키를 얻기 위해서는 phi(N) = (p - 1)(q - 1)의 값을 알아내야 한다.

  • phi(N) = (p - 1)(q - 1) = pq + 1 - (p + q)
  • p + q = (a + b) * 10250 + (a + b)

위와 같이 정리해보면 최종적으로 알아내야 하는 값은 a + b인 것을 알 수 있다.

x = ab, y = a2 + b2의 값을 알고 있으므로, sqrt(y + 2x)를 계산하면 a + b를 알아낼 수 있다.(a + b는 정수이므로, y + 2x가 제곱수인지 확인해보면 x, y를 제대로 찾았는지 확인할 수 있다.)

  • sqrt(y + 2x) = sqrt(a2 + b2 + 2ab) = sqrt((a + b)2)

a + b를 알아내고 나면 phi(N), d, m을 순서대로 계산하여 flag를 얻을 수 있다.(code)

Flag : midnight{w3ll_wh47_d0_y0u_kn0w_7h15_15_4c7u4lly_7h3_w0rld5_l0n6357_fl46_4nd_y0u_f0und_17_50_y0u_5h0uld_b3_pr0ud_0f_y0ur53lf_50_uhmm_60_pr1n7_7h15_0n_4_75h1r7_0r_50m37h1n6_4nd_4m4z3_7h3_p30pl3_4r0und_y0u}

'writeups > Crypto' 카테고리의 다른 글

backtalk  (0) 2019.11.26
baby RSA  (0) 2019.11.26
Ezdsa  (0) 2019.11.26
Blind  (0) 2019.11.26
LG  (0) 2019.11.26

+ Recent posts