daily pastebin goal
25%
SHARE
TWEET

ebCTF CRY300 writeup by Dirt#3478

a guest Aug 4th, 2013 360 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. EBCTF CRY300 writeup - By team Dirt#3478
  2.  
  3. The CRY300 challenge involved breaking an authentication system which employed elliptic curve signatures (ECDSA). Normally, elliptic curve cryptography is hard to break, so there was a particular weakness which was introduced through a weak random number generator.
  4.  
  5. When signing a message with a private ECDSA key, an ephemeral key is generated as well. The signing occurs with the combination of the private key and the ephemeral key. A reference to the ephemeral key which was used, together with the signature, makes up the security token. If two distinct messages are both signed with the same private and ephemeral keys, the security of the signature scheme falls apart: anyone who intercepts these two security tokens can generate other security tokens with this private and ephemeral key.
  6.  
  7. To solve the challenge, we need 1. to generate the proof-of-work, 2. to reverse some of the hashes, 3. to find out the (public) parameters of the elliptic curve, 4. to extract the ephemeral key from the eavesdropped communications and 5. to generate a new security token based on this ephemeral key.
  8.  
  9. == 1. Generate proof-of-work ==
  10.  
  11. First things first: in order to authenticate, we need to generate a proof-of-work: a 64-byte plaintext that starts with a given (random) substring and the MD5-hash of which starts with '0000'. The following code works:
  12.  
  13. ===== CODE START ================
  14. #!/usr/bin/python
  15.  
  16. import hashlib
  17.  
  18. pos = "********" # The requested substring
  19. solution = ""
  20. iterator = 0
  21. while hashlib.md5(solution).hexdigest()[0:4] != "0000":
  22.         solution = str(iterator)
  23.         while len(solution) < 56:
  24.                 solution = "0" + solution
  25.         solution = pos + solution
  26.         iterator = iterator + 1
  27.  
  28. print iterator-1
  29. print solution
  30. print hashlib.md5(solution).hexdigest()
  31. ===== CODE END ==================
  32.  
  33. == 2. Reverse the MD5 hashes ==
  34.  
  35. We need a couple of plaintexts for the hashes: googling the hash value gives us:
  36.  
  37. Hotz f56334fbe02eaa05218c31b01a80f2f6
  38. Bushing 00b37cb56bb57705348610253b1b82e4
  39. Butler 98c131f9fb31f732b136f87e64ff686a
  40.  
  41. Hotz and Bushing have access level 0, Butler has access level 1. Our attack will consist of generating a valid security token for the password 'Butler'.
  42.  
  43. == 3. Public parameters of elliptic curve ==
  44.  
  45. Normally in ECDSA, the underlying field and the curve upon which calculations are performed are public. In this case however, we had to find these out as well.
  46.  
  47. We know the following:
  48. - The elliptic curve is taken over a finite field of order p (with p a prime number)
  49. - The elliptic curve has, by definition, the form y^2 = x^3 + a*x + b
  50. - a = p - 3 (line 27 of service.py)
  51. - The points G, P and Q are on the curve (line 40-45 of service.py, coordinates at lines 30-37)
  52.  
  53. If we denote G=(Gx,Gy), P=(Px,Py) and Q=(Qx,Qy), we have the following equations:
  54. Gy^2 = Gx^3 + (p - 3)*Gx + b mod p
  55. Py^2 = Px^3 + (p - 3)*Px + b mod p
  56. Qy^2 = Qx^3 + (p - 3)*Qx + b mod p
  57.  
  58. Substracting the second equation from the first and the third equation from the second, we get:
  59. Gy^2 - Py^2 = Gx^3 - Px^3 + (p - 3)*(Gx - Px) mod p
  60. Py^2 - Qy^2 = Px^3 - Qx^3 + (p - 3)*(Px - Qx) mod p
  61.  
  62. Moving all terms without unknowns to the left, we get:
  63. Gy^2 - Py^2 - Gx^3 + Px^3 - 3*(Gx - Px) = p*(Gx - Px) mod p
  64. Py^2 - Qy^2 - Px^3 + Qx^3 - 3*(Px - Qx) = p*(Px - Qx) mod p
  65.  
  66. Since p = 0 mod p, we know that the right-hand side is 0 in both equations. In both equations, the left-hand side should therefore be a multiple of p if interpreted as integers. Putting them in a computer algebra system (we used Sage), we find that the greatest common divisor of the two is 89953523493328636138979614835438769105803101293517644103178299545319142490503, which is prime and therefore equal to p.
  67.  
  68. Since a = p - 3, we can now calculate a and b to get the unknown values:
  69.  
  70. a = 89953523493328636138979614835438769105803101293517644103178299545319142490500
  71. b = 28285296545714903834902884467158189217354728250629470479032309603102942404639
  72. p = 89953523493328636138979614835438769105803101293517644103178299545319142490503
  73.  
  74. We also need to find the order of G on the elliptic curve. Our computer algebra system tells us the order of the point G on the given elliptic curve is 89953523493328636138979614835438769106005948670998555217484157791369906305783.
  75.  
  76. == 4. Extract the ephemeral key ==
  77.  
  78. An ECDSA signature, in general, is generated in the following way:
  79.  
  80. G: generator point on the curve
  81. hash: value to be signed
  82. sm: secret multiplier (part of private key)
  83. n: order of G on the curve
  84.  
  85. 1. Generate an ephemeral key k, calculate p1 = kG (scalar multiplication of points on curve) and let r be the x-coordinate of p1.
  86. 2. Calculate s = k^-1 * (hash + (r * sm)) mod n
  87. 3. The secret token is r,s
  88.  
  89. Now, if two distinct messages hash and hash' are both signed with the same ephemeral key k, we get:
  90.  
  91. s = k^-1 * (hash + (r * sm)) mod n
  92. s' = k^-1 * (hash' + (r * sm)) mod n
  93.  
  94. (remember that r is calculated from k)
  95.  
  96. Solving for k^-1, we get
  97.  
  98. k^-1 = (s - s')/(hash - hash') mod n
  99.  
  100. Searching through the captured sessions, we look for lines with the same ephemeral key (first bytes of security token):
  101.  
  102. $ cat captured-sessions.txt | cut -d" " -f2 | sort | cut -c -30 | uniq -d
  103. g8IwXPGZdVhLTVQsc4NxjbQdys2/5q
  104. KVKN3KKUwmAMMDUC9QrKvBmPyu2h5t
  105. wNpp5moxL1+Z0I40PJQCC/LegcOQoc
  106.  
  107. $ cat captured-sessions.txt | grep g8IwXPGZdVh
  108. Hotz g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w==
  109. Bushing g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w==
  110.  
  111. The first attempt works: we have found two distinct messages, MD5(Hotz) and MD5(Bushing), which are signed with the same ephemeral key. We find k^-1 with the following code:
  112.  
  113. ===== CODE START ================
  114. hashHotz = "f56334fbe02eaa05218c31b01a80f2f6"
  115. hashBushing = "00b37cb56bb57705348610253b1b82e4"
  116. hashButler = "98c131f9fb31f732b136f87e64ff686a"
  117.  
  118. secTokenHotz = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlW9NTSxduU5nPoqdQt4Cn58GL17cq37J1SrbrK1/b67w=="
  119. secTokenBushing = "g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHmOCiSFewnBx/EQ3Ij7ZX+iE+dPiDSBMezXcwzWWeVm1w=="
  120.  
  121. hash1 = int(hashHotz,16)
  122. hash2 = int(hashBushing,16)
  123. hash3 = int(hashButler,16)
  124.  
  125. tmpHotz = base64.b64decode(secTokenHotz).encode('hex')
  126. tmpBushing = base64.b64decode(secTokenBushing).encode('hex')
  127.  
  128. sigHotz = ecdsa.Signature(int(tmpHotz[:64],16),int(tmpHotz[64:],16))
  129. sigBushing = ecdsa.Signature(int(tmpBushing[:64],16),int(tmpBushing[64:],16))
  130.  
  131. kinv = (sigHotz.s-sigBushing.s)*inverse_mod(hash1-hash2,n) % n
  132.  
  133. print kinv
  134. ===== CODE END ==================
  135.  
  136. The value of k^-1 is 64177781991311767079417471012576014125644196091350459505499548533470939053671.
  137.  
  138. == 5. Generate a new signature ==
  139.  
  140. Now that we have the value of k^-1, we can calculate the signature for Butler. We reuse the previously found formula for k^-1:
  141.  
  142. k^-1 = (s - s')/(hash - hash') mod n
  143.  
  144. We denote the hash of Butler with hash' and the signature of butler with s'. Isolating s', we get:
  145.  
  146. s' = k^-1*(hash' - hash) + s mod n
  147.  
  148. Adding to the previous code block, this code yields the signature and security token for Butler:
  149.  
  150. ===== CODE START ================
  151. sButler = (kinv*(hash3-hash1)+sigHotz.s) % n
  152.  
  153. print sButler
  154.  
  155. sigButler = ecdsa.Signature(sigHotz.r,sButler)
  156. output = encode_signature(sigButler)
  157.  
  158. print output
  159. ===== CODE END ==================
  160.  
  161. == 6. Finally ==
  162.  
  163. We connect to the server using netcat (telnet under Ubuntu sends a CRLF, while we need only an LF). We resolve the proof-of-work requirement, enter password 'Butler' and the security token we generated (g8IwXPGZdVhLTVQsc4NxjbQdys2/5q2EzHvGo4lLxHlfB7uuzOhxzGGWeEKY0tGJ8bgH441xVCkDcfdIUhJREA==).
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top