background

[CryptoHack | DreamHack] Chinese Remainder Theorem (중국인의 나머지 정리)

크립토핵 설명보다 드림핵 설명이 이해하기 쉬웠다. 연습문제는 다음과 같다.x ≡ 2 mod 5 x ≡ 3 mod 11 x ≡ 5 mod 17 # Find the integer a such that x ≡ a mod 935 다음과 같이 풀 수 있다.from Crypto.Util.number import inverse p1 = 5 p2 = 11 p3 = 17 c1 = 2 c2 = 3 c3 = 5 m = p1*p2*p3 m1 = m // p1 m2 = m // p2 m3 = m // p3 n1 = inverse(m1, p1) n2 = inverse(m2, p2) n3 = inverse(m3, p3) x = pow(c1*m1*n1 + c2*m2*n2 + c3*m3*n3, 1, m) print(x) 또 다른 문제..

[CryptoHack] Modular Square Root (Tonelli-Shanks algorithm)

Legendre Symbol에서 우리는 숫자가 제곱근 모듈로 소수인지 여부를 확인하는 빠른 방법을 배웠다. 더 나아가서 이러한 근을 효율적으로 계산하는 알고리즘이 있다. 실제로 가장 좋은 것은 Tonelli-Shanks라고 불리며, 19세기에 이탈리아인에 의해 처음 기술되었고 1970년대에 Daniel Shanks에 의해 독립적으로 재발견되었다는 사실에서 이러한 이름을 얻었다. 2가 아닌 모든 소수는 p ≡ 1 mod 4 또는 p ≡ 3 mod 4 형식이다. p ≡ 3 mod 4의 경우 제곱근을 계산하기 위한 정말 간단한 공식은 페르마의 소정리에서 직접 도출할 수 있다. 여전히 p ≡ 1 mod 4 경우가 남아 있으므로 보다 일반적인 알고리즘이 필요하다. Tonelli-Shanks 알고리즘은 r^2 ≡ ..

stack pivoting

stack pivoting 가젯을 활용해 스택의 흐름을 변경해서 익스플로잇을 수행하는 공격 기법이다. 쓰기 가능한 영역(.bss 영역 등)을 활용해서 fake stack을 구성한 뒤 ROP 체이닝에 활용하는 식으로 공격을 수행할 수 있다. 일반적으로 사용하는 gadget은 다음과 같다. gadget 종류 add esp, offset; ret; sub esp, offset; ret; call register; push register; pop esp; ret; xchg register, esp; ret; mov esp, register; ret; leave; ret; mov register,[ebp+0c]; call register; mov reg, dword ptr fs:[0]; …; ret; 여기서 주..

[CryptoHack] Legendre Symbol (르장드르 기호)

이전 강의(Quadratic Residues, 제곱 잉여)에서는 모듈로 체계에서 이차 잉여가 존재하지만 모든 수가 그렇진 않다는 것을 배웠다. 이번 강의에서는 Legendre Symbol(르장드르 기호)에 대해 설명한다. 르장드르 기호는 어떤 수가 제곱 잉여인지 여부를 판단할 때 사용한다. 위키의 설명은 다음과 같다. 또 다음과 같은 식도 성립한다고 한다. 제곱 잉여(1) * 제곱 잉여(1) = 제곱 잉여(1) 제곱 잉여(1) * 제곱 비잉여(-1) = 제곱 비잉여(-1) 제곱 비잉여(-1) * 제곱 비잉여(-1) = 제곱 잉여(1) 크립토핵에선 르장드르 기호를 다음과 같이 정리해준다. [정의] (a / p) = 1 (모듈러 p에서 a가 제곱 잉여이고, a ≢ 0 mod p) (a / p) = -1 (모..

[how2heap] House of Lore (glibc 2.35)

how2heap의 예제를 활용한 house of lore 공격 분석 bins bins은 사용이 끝난 청크들이 저장되는 객체이다. 메모리의 낭비를 막고, 해제된 청크를 빠르게 재사용할 수 있게 한다. bin에는 unsorted bin, small bin, large bin이 있으며 small bin에서 특정 크기 이하 청크는 fast bin으로 관리된다. malloc 요청이 들어오면 먼저 tcache를 검색하고 없으면, unsorted bin을 찾으며 unsorted bin에도 없으면 fast, small, large bin순으로 크기 범위에 맞는 bin을 찾아 탐색한다. 이는 해제된 free 상태의 청크가 저장되는 순서와도 동일한데, free 함수로 할당 받은 청크를 해제하면 청크는 tcache에 우선적..