InCTF 2014 - Crypto 200

This challenge had made me mad, Some how I finally I managed to solve the challenge. This is a RSA Crypto, given a cipher and public key. This is RSA low public exponent attack, e=3. 
root@Vijay:# openssl rsa -pubin -in pub.pem -text -noout -modulus
Public-Key: (4096 bit)
Modulus:
    00:d1:0b:a0:e9:cd:6d:d6:c3:89:5f:cd:f4:17:db:
    21:e5:81:22:60:89:c6:c7:58:7f:c4:1b:3d:78:df:
    f5:2c:0f:8c:29:dc:6b:e9:fc:cf:31:68:32:e6:ff:
    6f:f0:49:6e:9e:56:6e:cb:c1:31:06:4e:b8:47:5d:
    6c:1b:c8:28:be:4a:f4:54:ad:62:cb:f0:d1:d2:cd:
    5a:59:8a:24:1c:52:b1:6d:8e:e1:da:0c:a9:cc:56:
    30:3c:d0:70:71:0e:6c:18:1f:2a:31:c6:88:7e:52:
    cf:14:bd:76:f6:25:80:a8:46:92:f8:81:98:a9:38:
    49:0f:b2:de:19:41:b1:10:85:83:3d:ed:ca:16:67:
    3f:4a:e5:4b:e6:0f:e0:da:66:24:a5:3d:b2:32:dc:
    a6:c5:88:7d:72:3c:77:39:c4:76:ef:30:60:19:a0:
    57:f1:c6:be:37:a5:b8:20:d0:91:9a:cf:fd:18:63:
    d2:2c:6f:a7:30:fe:12:e8:15:35:9d:68:a4:ec:e1:
    c0:1e:f7:b0:ec:d9:59:91:b3:d9:71:d0:09:27:99:
    5e:d6:6e:d6:c9:93:36:44:c4:f9:9e:c7:52:80:9e:
    af:73:1e:69:c5:c0:f9:b0:34:e1:b8:33:0f:ef:d4:
    05:90:c4:6f:a1:79:61:4f:7a:d2:8c:d1:8b:99:73:
    69:18:2f:46:f9:e9:ba:25:48:c6:53:80:e5:3e:22:
    c9:9b:ea:a6:9b:f6:f8:63:87:45:30:bd:ce:9a:68:
    ee:6a:fb:a4:e9:ae:07:81:be:5b:3d:f1:a5:17:c5:
    7e:c1:b5:2b:4b:84:b7:18:63:a8:8a:35:f1:c0:df:
    0a:1f:8e:e3:6c:91:61:d2:ef:60:47:2a:12:9d:b8:
    16:66:22:3e:dd:07:f3:e9:d1:da:4b:fd:d2:17:1d:
    be:58:a0:36:80:4d:ef:fd:8f:d5:8e:b5:7a:2a:45:
    4b:25:c5:de:92:5a:16:54:d5:fe:67:02:04:b8:40:
    12:9b:8b:c5:a2:d3:97:fa:f2:15:7a:8b:b2:09:a2:
    7a:ff:89:b2:f8:bf:18:ab:da:53:71:e0:c1:cf:3d:
    68:c2:0b:5e:3e:19:5f:6f:63:12:a3:f8:ef:97:88:
    ca:fb:76:61:b7:9a:f7:52:15:9f:88:50:17:bd:e8:
    6c:7a:2e:b3:4e:27:7d:ac:36:7d:9f:56:33:c5:90:
    0a:d1:15:ef:4c:8f:ae:53:28:da:21:5c:b2:20:b8:
    ae:fb:09:e3:02:62:8a:2b:e0:56:9e:e7:dc:17:1e:
    f3:14:7c:6a:ce:61:02:71:e0:6d:5b:a7:14:03:d3:
    2e:2a:b5:30:76:5f:06:a1:f1:02:4c:d6:42:c4:97:
    88:f1:df

Exponent: 3 (0x3)

Modulus=D10BA0E9CD6DD6C3895FCDF417DB21E581226089C6C7587FC41B3D78DFF52C0F8C29DC6BE9FCCF316832E6FF6FF0496E9E566ECBC131064EB8475D6C1BC828BE4AF454AD62CBF0D1D2CD5A598A241C52B16D8EE1DA0CA9CC56303CD070710E6C181F2A31C6887E52CF14BD76F62580A84692F88198A938490FB2DE1941B11085833DEDCA16673F4AE54BE60FE0DA6624A53DB232DCA6C5887D723C7739C476EF306019A057F1C6BE37A5B820D0919ACFFD1863D22C6FA730FE12E815359D68A4ECE1C01EF7B0ECD95991B3D971D00927995ED66ED6C9933644C4F99EC752809EAF731E69C5C0F9B034E1B8330FEFD40590C46FA179614F7AD28CD18B997369182F46F9E9BA2548C65380E53E22C99BEAA69BF6F863874530BDCE9A68EE6AFBA4E9AE0781BE5B3DF1A517C57EC1B52B4B84B71863A88A35F1C0DF0A1F8EE36C9161D2EF60472A129DB81666223EDD07F3E9D1DA4BFDD2171DBE58A036804DEFFD8FD58EB57A2A454B25C5DE925A1654D5FE670204B840129B8BC5A2D397FAF2157A8BB209A27AFF89B2F8BF18ABDA5371E0C1CF3D68C20B5E3E195F6F6312A3F8EF9788CAFB7661B79AF752159F885017BDE86C7A2EB34E277DAC367D9F5633C5900AD115EF4C8FAE5328DA215CB220B8AEFB09E302628A2BE0569EE7DC171EF3147C6ACE610271E06D5BA71403D32E2AB530765F06A1F1024CD642C49788F1DF

root@Vijay:# openssl rsa -noout -text -pubin -in pub.pem | grep '^ ' | tr -dc '[0-9a-f]'

00d10ba0e9cd6dd6c3895fcdf417db21e581226089c6c7587fc41b3d78dff52c0f8c29dc6be9fccf316832e6ff6ff0496e9e566ecbc131064eb8475
d6c1bc828be4af454ad62cbf0d1d2cd5a598a241c52b16d8ee1da0ca9cc56303cd070710e6c181f2a31c6887e52cf14bd76f62580a84692f88198a9
38490fb2de1941b11085833dedca16673f4ae54be60fe0da6624a53db232dca6c5887d723c7739c476ef306019a057f1c6be37a5b820d0919acffd1
863d22c6fa730fe12e815359d68a4ece1c01ef7b0ecd95991b3d971d00927995ed66ed6c9933644c4f99ec752809eaf731e69c5c0f9b034e1b8330f
efd40590c46fa179614f7ad28cd18b997369182f46f9e9ba2548c65380e53e22c99beaa69bf6f863874530bdce9a68ee6afba4e9ae0781be5b3df1a
517c57ec1b52b4b84b71863a88a35f1c0df0a1f8ee36c9161d2ef60472a129db81666223edd07f3e9d1da4bfdd2171dbe58a036804deffd8fd58eb5
7a2a454b25c5de925a1654d5fe670204b840129b8bc5a2d397faf2157a8bb209a27aff89b2f8bf18abda5371e0c1cf3d68c20b5e3e195f6f6312a3f
8ef9788cafb7661b79af752159f885017bde86c7a2eb34e277dac367d9f5633c5900ad115ef4c8fae5328da215cb220b8aefb09e302628a2be0569e
e7dc171ef3147c6ace610271e06d5ba71403d32e2ab530765f06a1f1024cd642c49788f1df


root@Vijay:# xxd -p cipher 
075a1ec729bc48da7edd3b5820f7b1112c2da1d61398b9ff8c52d47132a1
85e18fec092789a1f0706551d529182f27c086b882dfbd38fa494110c669
57c49bceebad7074cc163017c294709f59ab0efb793b95a44c388f6afeda
ba16c85813b6127f99b8b44496c90d44cb1c70b8a5185997e1c023a28f81
66b584d85aa4fbce9ab5936c006ad63786351eea286e0d5639fef4255727
fc77fff0c4b7df42ac4f7e3b2601767a0b3be82a69f024063fc580c1ca05
075cf21b394970f4c07b1dd194d8b3dac66da1603b31a0ef9f02345c6c88
5d4c60661534c89d46e9535bd81c1cb8ff1f6a7212bb0dfddb410800949a
84206680e043a6b57ed95099e01d6230149544e856879f74907cc460ac75
3e856c67aaa565d6792343e1ecfc858445901cc1d3afd8c272dced8ff815
9a95f2bdac213c2c95aeba689365b34275e6126ddb49d324735de3240678
3fa92c3b23acb677a13cb895bb31b511216cc3b84178c6d99fe838
It's a 4096 bit key and its difficult to break it. But we got a low public exponent value, e=3. While googling I got a nice writeup from the blog http://eindbazen.net/2012/05/plaidctf-2012-rsa/ 

""" 
ciphertext = pow(plaintext, 3) % modulus
 
# 'ciphertext' is the remainder, so all we need to know to take the cubic root is the quotient 'k'

ciphertext + modulus * k = pow(plaintext, 3) 

"""
I used this idea to solve the challenge but I got failed, after so many tries I found that the program does checks the condition at test = 0. 
#!/bin/python 
import gmpy

n = 0x00d10ba0e9cd6dd6c3895fcdf417db21e581226089c6c7587fc41b3d78dff52c0f8c29dc6be9fccf316832e6ff6ff0496e9e566ecbc131064eb8475d6c1bc828be4af454ad62cbf0d1d2cd5a598a241c52b16d8ee1da0ca9cc56303cd070710e6c181f2a31c6887e52cf14bd76f62580a84692f88198a938490fb2de1941b11085833dedca16673f4ae54be60fe0da6624a53db232dca6c5887d723c7739c476ef306019a057f1c6be37a5b820d0919acffd1863d22c6fa730fe12e815359d68a4ece1c01ef7b0ecd95991b3d971d00927995ed66ed6c9933644c4f99ec752809eaf731e69c5c0f9b034e1b8330fefd40590c46fa179614f7ad28cd18b997369182f46f9e9ba2548c65380e53e22c99beaa69bf6f863874530bdce9a68ee6afba4e9ae0781be5b3df1a517c57ec1b52b4b84b71863a88a35f1c0df0a1f8ee36c9161d2ef60472a129db81666223edd07f3e9d1da4bfdd2171dbe58a036804deffd8fd58eb57a2a454b25c5de925a1654d5fe670204b840129b8bc5a2d397faf2157a8bb209a27aff89b2f8bf18abda5371e0c1cf3d68c20b5e3e195f6f6312a3f8ef9788cafb7661b79af752159f885017bde86c7a2eb34e277dac367d9f5633c5900ad115ef4c8fae5328da215cb220b8aefb09e302628a2be0569ee7dc171ef3147c6ace610271e06d5ba71403d32e2ab530765f06a1f1024cd642c49788f1df
e = 0x3
cipher_str = 0x075a1ec729bc48da7edd3b5820f7b1112c2da1d61398b9ff8c52d47132a185e18fec092789a1f0706551d529182f27c086b882dfbd38fa494110c66957c49bceebad7074cc163017c294709f59ab0efb793b95a44c388f6afedaba16c85813b6127f99b8b44496c90d44cb1c70b8a5185997e1c023a28f8166b584d85aa4fbce9ab5936c006ad63786351eea286e0d5639fef4255727fc77fff0c4b7df42ac4f7e3b2601767a0b3be82a69f024063fc580c1ca05075cf21b394970f4c07b1dd194d8b3dac66da1603b31a0ef9f02345c6c885d4c60661534c89d46e9535bd81c1cb8ff1f6a7212bb0dfddb410800949a84206680e043a6b57ed95099e01d6230149544e856879f74907cc460ac753e856c67aaa565d6792343e1ecfc858445901cc1d3afd8c272dced8ff8159a95f2bdac213c2c95aeba689365b34275e6126ddb49d324735de32406783fa92c3b23acb677a13cb895bb31b511216cc3b84178c6d99fe838

 
gs = gmpy.mpz(cipher_str)
gm = gmpy.mpz(n)
g3 = gmpy.mpz(3)
 
mask = gmpy.mpz(0x8080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808080808000)
test = 0
while True:
  if test == 0:
   gs = gs
  else:
   gs += gm
  root,exact = gs.root(g3)
  if (root & mask).bit_length() < 8:
    print root
    break

print '\n',hex(int(root))[2:-1].decode('hex')
The output is 
11657667992152384389168970007935564620544078223989911116124095315088239681126594015781938080477630692915497593321366093615015306163688656393156198882654127506116466608834490674480387607410167266362059980939450825093071957288196553216860521023077321644076523737128658172831409622651074862


Never use a small public exponent in RSA keys. The recommended exponent is 65537. The key for this level is weakrsakey.
GMpy is the nice package for solving the large numbers in python. Masking is the nice idea, I learnt from his blog. Printable characters are always from the ascii value 32 - 128 which are lesser than 2**7. In 8 bit representation, the printable's 8th bit is always 0. So we used masking to find the exact number we want.

Comments

Post a Comment

Popular posts from this blog

Python Speech recognition for Mac OS X

Hi Folks, I have been been searching for the    Python Speech recognition package especially for Mac OS.  I am not happy with the search results. Finally I got  https://pypi.python.org/pypi/SpeechRecognition/ (SpeechRecognition works only for the Linux distributions and Windows.) But I made it working for the Mac OS X by using flac.  Following are the instructions to make it run and modified code,  Prerequisite: Install Xcode in Unix Development mode Install Xcode - Command Line tools (Type ' xcode-select —install' in the terminal ) Install Port or Brew ( port    [or]   Brew   ) sudo brew install portaudio  [or]  sudo port install portaudio (for loading mic drivers) sudo pip install pyaudio [or] sudo easy_install install pyaudio (Mic Sources) sudo pip install SpeechRecognition [or] sudo easy_install install SpeechRecognition sudo port install flac Once you have finished w...
Read more

Baby Step Giant Step Algorithm Python Code

#Baby Step Giant Step DLP problem y = a**x mod n #Example 70 = 2**x mod 131 y = 70 a = 2 n = 131 s = floor(sqrt(n)) A = [] B = [] for r in range(0,s): value = y*(a^r) % n A.append(value) for t in range(1,s+1): value = a^(t*s) % n B.append(value) print A print B x1,x2 =0,0 for r in A: for t in B: if r == t: x1 = A.index(r) x2 = B.index(t) print x1,x2 break print 'the value of x is ', ((x2+1)*s - x1) % n # Answer
Read more

Simple Automation using Python - Atomac in Mac OS X

Image
The Product Automation in MAC OS X is quite easy if we have enough knowledge in the following languages and tools  Bash Scripts  Apple Scripts  Python especially ATOMac Knowledge in Accessibility. For more understanding of the LDTP: http://download.freedesktop.org/ldtp/doc/ldtp-tutorial.pdf LDTP - Tutorial is written by  Nagappan Alagappan. He has given the clear idea and architecture of the LDTP and its working. I have used the contents from the tutorial for knowledge sharing. Following are the few information and contents from  the LDTP - Tutorial. Few interesting key points, Linux Desktop Testing Project (LDTP) i s aimed at producing high quality test automation framework and cutting-edge tools that can be used to test GNU/Linux Desktop and improve it.  It uses the Accessibility libraries to poke through the application's user interface.  This idea has been extended to Microsoft Windows as Cobra , Mac OS X as ATOMa...
Read more