1
$\begingroup$

I'm a student who learning cryptography, refer to this book "Applied Cryptanalysis - Breaking Ciphers in the Real World" (page 133). It helped me know about time-memory trade off. Then I had a homework CTF things which must use time trade off attack to deal with it. I gave up from first start because I don't know where should I start. This is the answer exercise!

import base36

p=0x113b7d158a909efadc7216ca15fd51c419eb41ab108e0aa1d45da70c78185593d44bdb402476181c008ef36bc5378b0ad4c868ca4ed4f754c3c1b1f0891bcd8ad7d3db07251de90f4362cb5895f836eec8851d3fe3d68083db8a63053ec4078a55df017f1d43393f3aa2a453bb334417671731731e1e7687c77d104ff76aed523b6980831a4c4b55d74c4de77462d9a596ce7fcb3090d0abb8f94989c1b3701e533ebd722c855fba9ff17d64ce9b3306841157ee49b1c1fb3a38c93b9faaa84efcfdceba923b73b8682835ca322a1350bcc322d7eb34259d8302f55157c2c5d72c8aebb7b57f9f08809ee034258cf2e3c8e0982a155b72fdc79432eceb83b49d9
g=0xa9074b6e6d5bba3d024b90eeaee1f5b969fee32c5c25b91698755450509a8beb4100b046c9c6601981e208bc6e505aa67fdd224eff829a8cd8ebc1267c2cb4192b18ab1bcf5dba908e2cd849be038b5d52d5cf836eed63ee54fab1838a7152361a298bbeab3cc2d6f2b84097622fa5493dca99b4b6a648dcc886b607a8dc9590d995cf2e1f24ac5f277a2260d34410dc3b832ed6dc4928e92dfa8a807ddbdf77574d7bb34a45ca08bb7c8b89aa1fd1380abcbd75f99d3e819da9617356b650f9cc21ccffe913b09ca547967bb12feedbdb97730ccff09cc63aab6f6fc7b33392211da29bf32538b38a514cad4ea271e97618e39b0ab7cb152499093b7afbae2f
A=0x18776a5cf81fc30572aa9682dfb2f7d606e8073de536853dd9be8a391261dcca6cebea2a2b1337f2a057d238152729cea6983a8ef2b111d8096f212db771229830e2e6d4839a37355d4efb265183f199cd573fa99a38183e7ee3cc7fdac7c92078b6c1535b142965379f1c7e73d5a95725dfb75749529a687bf9b7e01a0b4511a05d96999608c2527a0308f2360d26706233d451f62edc8f2e76fde85c631b601d12a828657efe65aba78fccd46d79a84bc3380da71fad6472d9e666fd99fbd7c154555501b608d4cef875099e037eef3712a5e3108f95c1e01b2a8f0961569c77738a459b65b0ac39109b30ab3226d7b92a1db080a99bbb86f6e96266b13df7
B=0xbecd8332380e8c0f3969602e4924473ade119dad5fe6f2d9582dc8196ae85dfa80fab3c001f8bea1ca6c63b9f8f264742beaede2bd11c86bf4d6a0fa7df1dd84da318a7142f2228dbb8dd37a5a3c5a772dd2c744184a41743f4286ba2ccfa431c1571cd63a9ee1bb398b4dd09ccaa426b37f72f4452c2f37a96634e8d6604362e2836891818e9744f00323ade93e10aa1785cc1865fff57ec5caacf74b11ebed16384613145a2e33141a9523252b952cf0eb9c33914d067b66a2a03133f044f336efee054eec905dfa14af970f556b44c52e3814e0914a2393bb56da5aca7b88c45fcaf02f76fc9718746c15901b8ea86801f0b07eca7385dd1cb6991e65e421

table = {}
S = 0

print '[-] Generating table...'

for i in range(0, 2**33, 2**20): # sufficient bounds
   table[pow(g, i, p)] = i

print '[-] Performing look-up in table...'

for i in range(0, 2**18):
   B = (B * g) % p
   if B in table:
       print  ' >> B = g ^', table[B] - i
       S = pow(A, table[B] - i, p)
       break

print '[+] Key found:\n\n', base36.dumps(S), '\n'

Could anyone help me understand time-memory trade off? Maybe with an example building upon my homework

$\endgroup$
  • $\begingroup$ What are you trying to attack? (ECC? DLog? PW-Hashes? Symmetric Keys?) TMTOs are known in a variety of settings. $\endgroup$ – SEJPM Nov 9 '16 at 23:42
  • $\begingroup$ @SEJPM I'm trying to solve a CTF challenge. It's kind of RSA ( Asymmetric Keys ) $\endgroup$ – Mr2uang Nov 10 '16 at 6:48
1
$\begingroup$

Time trade off, or in your case, time-memory tradeoff, works by having massive "rainbow tables" that show you ALL hashes in a hashing algorithm (probably MD5, or other low security algorithm). A "Rainbow Table" saves you time and processor power, rather than having a hash cracker eat up your ROM, but are probably many gigabytes large. The trade-off then becomes size vs. time & power. If this doesn't satisfy you, or this seems like it's missing something, there is PLENTY of research being done on hash cracking, and even a youtube channel called "Computerphile" that has a better explanation on this than me.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.