pastebin - collaborative debugging

pastebin is a collaborative debugging tool allowing you to share and modify code snippets while chatting on IRC, IM or a message board.

This site is developed to XHTML and CSS2 W3C standards. If you see this paragraph, your browser does not support those standards and you need to upgrade. Visit WaSP for a variety of options.

pastebin private pastebin - collaborative debugging tool What's a private pastebin?

Posted by Paranoia on Mon 15th Mar 19:48
View followups from Paranoia | download | new post

  1. from __future__ import division
  2. import sys
  3. import os
  4. import subprocess
  5. import math
  6. import sha
  7.  
  8.  
  9. #error 1 is returned when integer-to-octets conversion fails
  10. greaterB = 1
  11.  
  12. #error 2 occurs because the integrity checking mechanism fails
  13. lessB = 2
  14.  
  15. if ( len(sys.argv) != 3 ):
  16.   print 'Usage: python attack.py ORACLE CHALLENGE'
  17.   sys.exit()
  18.  
  19. #read in N,e,c from text file
  20. f = open(sys.argv[2], 'r')
  21. N = f.readline()
  22. E = f.readline()
  23. C = f.readline()
  24.  
  25. #convert hex to integer for future use
  26. n = int(N,16)
  27. e = int(E,16)
  28. c = int(C,16)
  29.  
  30. #set oracle to be ./oracle specified by command line
  31. oracle = './' + sys.argv[1]
  32.  
  33. #calculate k and B, as deinfed in attack paper
  34. k = int(math.ceil(math.log(n,256)))
  35. B = 2**( 8*(k-1) )
  36.  
  37. #STEP 1
  38. f1 = 2
  39. error = 0
  40. while 1 :
  41.  
  42.   #calculate ((f1^e) * c) % n
  43.   num = ((pow(f1,e,n))*c) % n
  44.   num_i = num
  45.  
  46.   #format and query oracle
  47.   num = hex(num)[2:]
  48.   if num[len(num)-1] == 'L':
  49.     num = num[:len(num)-1]
  50.    
  51.   #verify hex to int conversion
  52.   if int(num,16) != num_i:
  53.     print "hex to int conversion fail"
  54.     sys.exit()
  55.  
  56.   #open oracle and send query
  57.   sp = subprocess.Popen(oracle,shell=True,stdin=subprocess.PIPE)
  58.   sp.communicate(N+E+(num.zfill(256)))
  59.  
  60.   #examine error code
  61.   error = sp.returncode
  62.  
  63.   if( error == lessB ):
  64.     f1 = f1*2
  65.    
  66.   elif( error == greaterB ):
  67.     break
  68.    
  69.   else:
  70.     print "error code not 1 or 2"
  71.     sys.exit()
  72.  
  73. print "f1 equals " + str(f1)
  74.  
  75.  
  76. #STEP 2
  77. f2 = int(math.floor( (n + B) / B ) * (f1/2))
  78. error = 0
  79.  
  80. while 1 :
  81.  
  82.   #calculate ((f2^e) * c) % n
  83.   num = ((pow(f2,e,n))*c) % n
  84.   num_i = num
  85.  
  86.   #format num as hex
  87.   num = hex(num)[2:]
  88.   if num[len(num)-1] == 'L':
  89.     num = num[:len(num)-1]
  90.    
  91.   #verify hex to int conversion
  92.   if int(num,16) != num_i:
  93.     print "hex to int conversion fail"
  94.     sys.exit()
  95.  
  96.   #open oracle and send query
  97.   sp = subprocess.Popen(oracle,shell=True,stdin=subprocess.PIPE)
  98.   sp.communicate(N+E+(num.zfill(256)))
  99.  
  100.   #examine error code
  101.   error = sp.returncode
  102.  
  103.   if(error == greaterB):
  104.     f2 = int(f2 + (f1/2))
  105.    
  106.   elif(error == lessB):
  107.     break
  108.   else:
  109.     print "error code not 1 or 2"
  110.     sys.exit()
  111.  
  112. print "f2 equals " + str(f2)
  113.  
  114.  
  115. #STEP 3
  116. #calculate m_min and m_max
  117. m_min = int(math.ceil(n/f2))
  118. m_max = int(math.floor((n+B)/f2))
  119. m_min_p = m_min
  120. m_max_p = m_max
  121. i = 0
  122.  
  123. while m_max != m_min :
  124.  
  125.   #calculate intermediate values
  126.   f_tmp = int(math.floor( (2*B) / (m_max - m_min) ))
  127.   I = int(math.floor((f_tmp * m_min) / n))
  128.   f3 = int(math.ceil( (I * n) / m_min ))
  129.  
  130.   #debugging only
  131.   if(i == 0):
  132.     print "m_min: " + str(m_min)
  133.     print "m_max: " + str(m_max)
  134.     print "f_tmp: " + str(f_tmp)
  135.     print "I: " + str(I)
  136.     print "f3: " + str(f3)
  137.  
  138.   #calculate ((f3^e) * c) % n
  139.   num = ((pow(f3,e,n))*c) % n
  140.   num_i = num
  141.  
  142.   #format num as hex
  143.   num = hex(num)[2:]
  144.   if num[len(num)-1] == 'L':
  145.     num = num[:len(num)-1]
  146.  
  147.   #verify hex to int conversion
  148.   if int(num,16) != num_i:
  149.     print "hex to int conversion fail"
  150.     sys.exit()
  151.  
  152.   #open oracle and send query
  153.   sp = subprocess.Popen(oracle,shell=True,stdin=subprocess.PIPE)
  154.   sp.communicate(N+E+(num.zfill(256)))
  155.  
  156.   #examine error code
  157.   error = sp.returncode
  158.   if error == greaterB:
  159.     m_min = int(math.ceil( ( (I*n) + B) / f3))
  160.   elif error == lessB:
  161.     m_max = int(math.floor( ( (I*n) + B) / f3))
  162.   else:
  163.     print "error code not 1 or 2"
  164.     sys.exit()
  165.   if ( (m_min_p == m_min) and (m_max_p == m_max) ):
  166.     print "infinte looping"
  167.     sys.exit()
  168.   m_min_p = m_min
  169.   m_max_p = m_max
  170.   i = i + 1
  171.  
  172.  
  173. print "Step 3 iterates " + str(i) + " times"
  174.  
  175. print "diff = " + str(m_max - m_min)
  176. print "f_tmp = " + str(f_tmp)
  177. print "I = " + str(I)
  178. print "f3 = " + str(f3)
  179. print "m_min = " + str(m_min)
  180. print "m_max = " + str(m_max)
  181.  
  182. sys.exit()
  183.  
  184.  
  185. m = m_min
  186. m_i = m
  187.  
  188. m = hex(m)[2:]
  189. if m[len(m)-1] == 'L':
  190.    m = m[:len(m)-1]
  191.    
  192. m = m.zfill(256)
  193.  
  194. #verify hex to int conversion
  195. if int(m,16) != m_i:
  196.   print "hex to int conversion fail"
  197.   sys.exit()
  198.  
  199. print m
  200. print len(m)
  201. print f3
  202. print B
  203. print 2*B
  204.  
  205.  
  206. hLen = sha.digest_size
  207.  
  208. Y = m[0:2]
  209. maskedSeed = m[2:2+(2*hLen)]
  210. maskedDB = m[2+(2*hLen):]
  211.  
  212. def mgf1_sha1(mgfSeed, maskLen):
  213.  
  214.   result = ""
  215.  
  216.   if maskLen > (2**32)*sha.digest_size:
  217.     return "mask too long"
  218.  
  219.   print int(math.ceil(maskLen / sha.digest_size))
  220.  
  221.   for i in range(int(math.ceil(maskLen / sha.digest_size))):
  222.     counter = hex(i)[2:].zfill(8)
  223.     if counter[len(counter)-1] == 'L':
  224.       counter = counter[:len(counter)-1]
  225.     hash = sha.new(mgfSeed+counter)
  226.     result = result + hash.hexdigest()
  227.  
  228.   return result[:(maskLen*2)]
  229.  
  230. seedMask = mgf1_sha1(maskedDB, hLen)
  231.  
  232. seed = hex(int(maskedSeed,16) ^ int(seedMask,16))[2:]
  233. if seed[len(seed)-1] == 'L':
  234.   seed = seed[:len(seed)-1]
  235.  
  236. dbMask = mgf1_sha1(seed,k-hLen-1)
  237.  
  238. DB = hex(int(maskedDB,16) ^ int(dbMask,16))[2:]
  239. if DB[len(DB)-1] == 'L':
  240.   DB = DB[:len(DB)-1]
  241.  
  242. print DB
  243.  
  244. lHash_ = DB[:hLen*2]
  245.  
  246. print lHash_
  247.  
  248. #######################################################################
  249. ##
  250. ##You can find the three relevant pdfs here:
  251. ##
  252. ##http://dl.dropbox.com/u/4326/question.pdf <-- assignment
  253. ##http://dl.dropbox.com/u/4326/pkcs-1v2-1d3.pdf <-- crypto scheme details
  254. ##http://dl.dropbox.com/u/4326/Manger.%20A%20Chosen%20Ciphertext%20Attack%20on%20RSA%20Optimal%20Asymmetric%20Encryption%20.pdf <-- attack
  255. ##
  256. ##You can also find the relevant USERNAME files here:
  257. ##
  258. ##http://dl.dropbox.com/u/4326/sc6517
  259. ##http://dl.dropbox.com/u/4326/sc6517.challenge
  260. ##
  261. ##Please only take the time to read the above etc if you're interested - don't feel obligated or anything like that.
  262. ##
  263. ##My problem:
  264. ##
  265. ##I have had my f1 and f2 values confirmed to be correct by my lecturer. However, the output from the 'Step 3' loop is infeasible. The output (m_min) from Step 3 (line 115-173) is an encoded message EM. ##This message is formed before encryption, using randomisation, to prevent tricks like ENC(m+m') = c + c'. The form of an EM is described in PKCS specification pdf, in section 7.1.1. See that the right ##hand part of the EM is 'maskedDB' which is generated by hashing a random string. The output from my attack results in a maskedDB = 0, which is clearly (all but) impossible.
  266. ##
  267. ##I've looked hard at my implementation of the pseudocode presented in the attack pdf, and at my understanding of the cryptoscheme, the assignment and the attack, and I can't find anything wrong.
  268. ##
  269. ##Any kind of discussion about this would probably be useful to me, even if it's just me explaining all of the above, as I often find having to form these thoughts coherently to explain them helps to find ##a solution.
  270. ##
  271. ##No worries if the above is a bit too involved for you.
  272. ##
  273. ##Much love, Para
  274. ##
  275. ###############################################################################

Submit a correction or amendment below. (click here to make a fresh posting)
After submitting an amendment, you'll be able to view the differences between the old and new posts easily.

Use syntax highlighting

To highlight particular lines, prefix each line with @@


Remember my settings