Contrast Labs is our security research team, writing the rules that power Contrast's suite of tools. A lot of our research starts with vulnerability analysis, reading and understanding how different exploits work at an API level and how we can detect that: during code analysis with Contrast Scan or as the application runs with Contrast Assess.
To fully understand these exploits, our team frequently participates in Capture the Flag competitions to learn new styles of attacking applications. While we place well in many of the competitions, the real benefit is the team working together to play a game and the ability for new team members early in their career to rapidly improve their skills while having fun. We hire across a range of skills, but a common characteristic of every team member is the ability to work well together and help each-other.
We recently participated in the Cybrics CTF and performed a write-up of how our team solved one of the challenges to find a vulnerability in a message commit system. Here is the solution to the "Too Secure" problem:
Challenge Description#
Find a vulnerability in our novel message commitment system. Read the paper here: too_secure.pdf
Enter decimal r2 value as the flag. Flag format here is NOT cybrics{...}
Maths#
Let H(x) be the function that generates â given x
Let x1, x2 be the integer representations of M1 and M2, respectively.
We're given
c = G * h r
Where G = gx mod p and h = g ^ H(x) mod p
We can combine and simplify:
c = gx + H(x)*r mod p
To break the system, we want to find r2 such that
c1 = c2 mod p
gx1 + H(x1)*r1 = gx2 + H(x2)*r2mod p
Since g is known, and we're given that the Op(g) = q, we could solve the above by solving:
x1 + H(x1)*r1 = x2 + H(x2)*r2 mod q
r2 = (x1 - x2 + H(x1)*r1) * H(x2)-1 mod q
Where H(x2)-1 is the multiplicative inverse of H(x2) modulo q ### Finding q
We were given q | (p-1), gq = 1 mod p. Luckily, factoring p-1 was pretty quick via some online factorization calculators
https://www.dcode.fr/prime-factors-decomposition
We test each prime factor against g and p.
g = 10729072579307052184848302322451332192456229619044181105063011741516558110216720725qs = [2, 3, 7, 3671, 10733, 1039300813886545966418005631983853921163721828798787466771912919828750891]p = 12039102490128509125925019010000012423515617235219127649182470182570195018265927223q = 0for q_ in qs: v = pow(g, q_, p) if v == 1: q = q_
print("q", q)
>>> q 1039300813886545966418005631983853921163721828798787466771912919828750891Finding H(x)#
Computing H(x) (called HAT(x) in the code below) was a little convoluted given the instructions:
Note: since p is prime, totient(p) = p-1
def str2val(message): val = 0 mult = 1 for let in message: val += ord(let) * mult mult *= 256 return val
def chunkstring(string, length): return (string[0+i:length+i] for i in range(0, len(string), length))
def bitstring_to_bytes(s): b = bytearray() chunks = chunkstring(s, 8) for chunk in chunks: num = int(chunk, 2) b.append(num & 0xff) return bytes(b)
def HAT(x): G = pow(g, x, p) numStr = "{0:b}".format(G) if len(numStr) < 1024: numStr = "0" * (1024 - len(numStr)) + numStr
Gp = bitstring_to_bytes(numStr) a = hashlib.sha512(Gp).hexdigest() ap = int(a, 16) app = pow(ap, ap, p-1) return app
r1 = 31245182471M1 = "Hi! I am Vadim Davydov from ITMO University"x1 = str2val(M1)M2 = "Transfer the points for easy task to this team"x2 = str2val(M2)
hat_x1 = HAT(x1)hat_x2 = HAT(x2)Finding H(x2)-1#
Since q is prime, H(x2) and q are coprime, so we can use the Extended Euclidean Algorithm to find H(x2)-1:
def modulo_multiplicative_inverse(A, M): """ Assumes that A and M are co-prime Returns multiplicative modulo inverse of A under M """ # Find gcd using Extended Euclid's Algorithm gcd, x, y = extended_euclid_gcd(A, M)
# In case x is negative, we handle it by adding extra M # Because we know that multiplicative inverse of A in range M lies # in the range [0, M-1] if x < 0: x += M
return x
def extended_euclid_gcd(a, b): """ Returns a list `result` of size 3 where: Referring to the equation ax + by = gcd(a, b) result[0] is gcd(a, b) result[1] is x result[2] is y """ s = 0; old_s = 1 t = 1; old_t = 0 r = b; old_r = a
while r != 0: quotient = old_r // r # In Python, // operator performs integer or floored division # This is a pythonic way to swap numbers # See the same part in C++ implementation below to know more old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t return [old_r, old_s, old_t]
inv = modulo_multiplicative_inverse(hat_x2, q)Putting it all together#
r2 = (x1 - x2 + H(x1)*r1) * H(x2)-1 mod q
print ( ((x1 - x2 + hat_x1 * r1) * inv ) % q )
>>> 299610740605778098196154877327490870095375317123548563579894088319476495