Cracking Zeppelin

A few days ago Brian Krebs published a piece about Zeppelin key cracking, so … since I was also involved in recovering files for some of the ransomware gang victims I though I will add a few cents…

Back in 2020, I was approached by one of my clients to have a quick look at this particular piece of Zeppelin ransomware sample; and as you can imagine, I was immediately skeptical — it’s really unlikely to crack crypto of modern ransomware so I pretty much threw a towel, immediately, kinda by default.

BUT…

I was also aware of work of Lance Jones, and his UNIT221B on this particular malware strain and… that offered some hope…

I decided to try to factor these keys myself and what followed was a VERY intense week where I had to very quickly learn how to use and pay for AWS, how to allocate its resources, how to fix lots of other peoples’ bugs in a software that was — by that time — full of legacy assumptions, and – for the lack of a better word — in a need of a lot of troubleshooting and ‘code massaging’.

But the rewards were there, waiting…

The morning I saw the first cracked key I became ecstatic. I didn’t care about money this was earning me, I didn’t care what a bill I had to pay to AWS, here I was, breaking the damn ransomware! We were able to recover files for the client. Just like that!

Working in a cybersecurity space can be quite daunting, we often see ‘bad’ things, we live ‘failure’ every day. Yet, that moment I managed to crack the first key was a moment of triumph. Not all is lost. We are actually helping. We matter. it’s cheesy as hell, but there is no better satisfaction than disrupting the bad, for good.

And … it did happen again, I’ve spent a lot of time cracking other keys, but we did beat them. For a cost of a few hundred dollars on AWS, each time, we did beat them, every single time.

Multi-prime RSA

Today for a change I will talk about a topic that is completely abstract to me. I got interested in it as a side-effect of a project I was working on and here’s a code that some may find useful.

Researching RSA crypto internals you will surely come across a lot of information and practical examples talking about calculation of a private key / decryption if you can only factor ‘n = p & q’. For example this great example.

I was curious how to do it not only for p & q, but also for multi-prime RSA setups, that is – these where ‘n = r[1] x r[2] x … x r[n]’. There is not that much published about it online and the best example I could find was this article on StackExchange.

While I don’t read mathematical symbols very well, I decided to implement it in python to learn something new. In order to keep it flexible, the whole code works based on the content of the ‘r’ array (or list really), that specifies all multipliers of ‘n’. The Modular multiplicative inverse function is stolen from this article on StackOverflow.

Here’s the code:

import math
def egcd(a, b):
   if a == 0:
      return (b, 0, 1)
   else:
      g, y, x = egcd(b % a, a)
   return (g, x - (b // a) * y, y)

def cmi(a, m):
   g, x, y = egcd(a, m)
   if g != 1:
      return None
   else:
      return x % m

r = [931164518537359, 944727352543879, 982273258722607]
y = 529481440313141057262802385309623737292746309
lr = len(r)
e = 5
N = 1
d = [None] * lr
t = [None] * lr
x = [None] * lr
for i in range(lr):
   N = N * r[i]
   d[i] = cmi (e, r[i]-1)
   print ("r[", i , "] = ", r[i])
   print ("N = ", N)

print ()

for i in range(lr):
   print ("d[", i , "] = ", d[i])

print ()

m=r[0]
for i in range(1,lr):
   t[i] = cmi (m, r[i])
   m = m * r[i]
   print ("t[", i , "] = ", t[i])

print ()

for i in range(lr):
   x[i] = pow(y, d[i] ,r[i]) % r[i]
   print ("x[", i , "] = ", x[i])

print ()

X = x[0]
m = r[0]
for i in range(1,lr):
   X = X + m * ( ( (x[i] - (X % r[i]) ) * t[i] ) % r[i] )
   m = m * r[i]
   print ("x = ", X)

Here are the numbers from the StackExchange post:

e=5
r1=931164518537359 r2=944727352543879 r3=982273258722607
N=864102436520313334659779717201860718296307527
d1=558698711122415 d2=566836411526327 d3=785818606978085
t2=360227672914825 t3=882117903741868
y=529481440313141057262802385309623737292746309
x1=436496882968258 x2=903092574358267 x3=806961802724
x=710532117316769399313215266414 (when i=2)
x=111222333444555666777888999000000000000000042

And here is the output of the script:

r[ 0 ] = 931164518537359
r[ 1 ] = 944727352543879
r[ 2 ] = 982273258722607
N = 864102436520313334659779717201860718296307527

d[ 0 ] = 558698711122415
d[ 1 ] = 566836411526327
d[ 2 ] = 785818606978085

t[ 1 ] = 360227672914825
t[ 2 ] = 882117903741868

x[ 0 ] = 436496882968258
x[ 1 ] = 903092574358267
x[ 2 ] = 806961802724

x = 710532117316769399313215266414
x = 111222333444555666777888999000000000000000042

And what about the article I mentioned earlier?

e = 113
p = 338924256021210389725168429375903627261
q = 338924256021210389725168429375903627349
ct = 102692755691755898230412269602025019920938225158332080093559205660414585058354

For which the expected result is:

t :535645912235879621902477379288244888293287927881054157873533

If I plug it in to the code I pasted above, I will get the following:

r = [338924256021210389725168429375903627261, 338924256021210389725168429375903627349]
y = 102692755691755898230412269602025019920938225158332080093559205660414585058354
lr = len(r)
e = 113

And the output is:

r[ 0 ] = 338924256021210389725168429375903627261
r[ 1 ] = 338924256021210389725168429375903627349
N = 114869651319530967114595389434126892905129957446815070167640244711056341561089
d[ 0 ] = 155965144363742834209812020597760961217
d[ 1 ] = 329926266923302149289986966649109725737
t[ 1 ] = 234936132014702656514037206726478650776
x[ 0 ] = 22808800254162271774126722746602450507
x[ 1 ] = 22808800254162132696325593613158654299
x = 535645912235879621902477379288244888293287927881054157873533