Multiplicative

Multiplicative

Problem

• JavaCrackMe.jar

Tools

• IDA 7.0

Background Knowledge

• Integer overflow - Wikipedia

Explanation

• JavaCrackMe.jar를 IDA 7.0으로 열어 분석해보았다.
  • 
    • java -jar JavaCrackMe.jar <target>으로 실행하여 입력값을 넣어준다.
    • 입력값을 long 타입의 값(signed 8-byte integer)으로 변환한다.
    • 해당 값을 26729와 곱해준다.
    • 위 연산의 결과값이 -1536092243306511225
      • 와 같다면 Correct! 출력한다.
      • 와 다르면 Wrong! 출력한다.
  • 바라는 결과값인 -1536092243306511225이 26729로 나뉘어 떨어지지 않기 때문에, 해당 문제는 정수 오버플로우를 이용하여 원하는 값을 구해야 함을 알 수 있다.
  • signed 8-byte integer인 target일 때, 정수 오버플로우가 적용되는 target * 26729 = -1536092243306511225를 만족하는 target을 찾아야 한다.
• 정수 오버플로우를 생각하여 target를 찾는 방정식을 세우면 다음과 같다.
  • (not-overflowed-target) * 26729 = (k * 2**64) + (-1536092243306511225)
  • k = k if (((k * 2**64) + (-1536092243306511225)) % 26729 == 0)
  • target = ((k * 2**64) + (-1536092243306511225)) // 26729 > 0x7fffffffffffffff ?
    • ((k * 2**64) + (-1536092243306511225)) // 26729 - 2**64 :
    • ((k * 2**64) + (-1536092243306511225)) // 26729
• 이를 파이썬 스크립트로 작성하여 문제를 풀 수 있다.
  • multiplicative.py

Review

• 정수 오버플로우의 결과값을 구하는 방정식을 세울 생각을 하자...
• 이를 단순 무차별 대입으로 찾으려 하면 최소 245287194656008047번의 연산을 거쳐야 한다. 이는 하루이틀 돌린다고 되는 게 아니다...