PlaidCTF 2015 - Strength in Difference (crypto 110) Writeup

Hint:

Strength in Difference

We've captured the flag encrypted several times... do you think you can recover it?

Alice's Other Birthday Suit

by Javantea April 18, 2015

How to do this quickly?

There are many ways of doing this, the main thing is that we need to efficiently come up with pt ** N where N starts at min(e) and goes down to 1. The first step is to find the smallest exponent we can make using two ciphertexts.

It turns out that e8 and e17 do this.

See this:

best_a = 10000
for i in range(len(es)):
      for j in range(len(es)):
              if i == j: continue
              if es[i] % es[j] > 0 and es[i] % es[j] < best_a:
              best_a = es[i] % es[j]
              print(i, j)
      #next j
#next i

This produces best_a == 1775 and i = 8, j = 17.

This allows us to use the inverse of c17 repeatedly to create pt ** 1775.

Once you have pt ** 1775, you need to check for the next step down. [e % 1775 for e in es] [1491, 1349, 994, 1704, 994, 1349, 639, 639, 426, 284, 639, 1349, 1136, 639, 1491, 71, 994, 1136, 309, 1704]

As you can see you can produce 71 but it's a slower solution because it takes 30 minutes to compute. Instead, I found that 309 produced 14 in the next step which makes it possible for me to crack in one minute fourteen seconds. Not bad.

real    1m14.278s
user    1m14.228s
sys     0m0.006s

How does this work at all?

How does this work at all? Inverse numbers are a consequence of RSA modular exponentiation. Think for a moment about RSA's system.

Our ciphertext is generated using: pt ^ e mod N

In Python, that is: pow(pt, e, N)

When someone encrypts the same plaintext twice with two different e and the same N, they are making a mistake known as Alice's Birthday. The first step to cryptanalysis of this problem is to understand inverse numbers.

N = 1777515163382723970373940383272808481655635386178766060349515720868487653330
89060790975724925254690253115039605976618801961586375738876768312663570453872422
39670056994997890314957563718692456908808241405556785438717235135398736785240289
7584121327597709142354218771564925957009027121275680622544508517589219713
pow(1234, 65537, N) = 8128206764887588592803344687472673906283845270537718229072
99742290889689503074097648238837529922917688091270550885108573661729290590639685
72749155102672159754878928872471404942773680915279208060650397269487853036954557
34573555394731297070065410768330619191503306069996810062631909406787918549746451
7907093433

Let's call this cv1.

pow(1234, 32768, N) = 8433382499942535200453485969430959424326350773016047478852
59535709652825684216595862468993682546342507356888357425768135935781117605679059
66427921808278741033227004179549246417812714008944738108748509428941409405586729
13905211106957809578217163079328781701444730824115693799242555067546824357212324
0793157842

Let's call this cv2.

Note that 32768*2 = 65536

cv2_inv = Crypto.Util.number.inverse(cv2, N)

This gives us the inverse of that number in N, just like 1/cv2 except in modular arithmetic.

so if cv1 is pt ** 65537 and cv2 is pt ** 32768, what is cv1 * cv2_inv % N ?

It should be pt ** 32769 % N Let's call this intermediate1.

What is intermediate1 * cv2_inv % N ?

It should be pt ** 1 % N, which is simply pt. This is the end of the decryption. To see it work, run this Python code:

cv2_inv = Crypto.Util.number.inverse(cv2, N)
intermediate1 = (cv1 * cv2_inv) % N
pt = (intermediate1 * cv2_inv) % N
print(pt)

As you can see, you get the plaintext back. This doesn't work on normal RSA because valid RSA systems never encrypt with two different e, e is part of the public key, so it doesn't make sense to change it. This attack only works when you find someone encrypting the same plaintext with two different e and two same N.

So why is this solution so complex when the explanation is easy? When the exponents do not easily give you pt ** 1, you have to reduce the exponent to a number which you can then use to divide another number with. With a large number of ciphertexts and exponents, we end up with a lot of choices for which direction to go. The most obvious direction for example, required a ton of unnecessary computation to get to 1. In this solution, I take an alternative route which only takes 1 minute 14 seconds on my system.

import Crypto.Util.number
import binascii

import gmpy2

"""
START FROM strength_is_weakness1.py
"""

a = open('captured_827a1815859149337d928a8a2c88f89f','r').read().split('\n')

a.pop(0)
a.pop(-1)

b = [v.replace('{','').replace('}','').replace('L','').split(' : ') for v in a]

c = []
for v in b:
    r = [int(w,16) for w in v]
    c.append(r)

cts = [v[2] for v in c]

allcts = 1
for q in cts:
    allcts *= q

n = c[0][0]
sqrtn = gmpy2.iroot(n, 2)[0]

es = [v[1] for v in c]

"""
END OF FROM strength_is_weakness1.py
START FROM alicebirthday2.py

let's assume that we can subtract off whatever we want. What do we want to subtract off?
[1517356884191, 6173920479630499, 521222775331469, 52322651179, 1731619,
736938749, 44003349641539, 146189, 1804229351, 3714908233709, 263758484593339,
122944949, 5409989577508180636511, 1224741217939, 42232455791,
1073197694407494671, 156889697747737238458819, 59711, 17249876309,
438348354053765429]

# This was too slow:
so we start with 1775.
then we get to 75.
then we get to 4.
then we get to 1.

# I actually did:
We start with 1775.
then we get to 309.
then we get to 14.
then we get to 1.

>>> [e % 1775 for e in es]
[1491, 1349, 994, 1704, 994, 1349, 639, 639, 426, 284, 639, 1349, 1136, 639, 1491, 71, 994, 1136, 309, 1704]
...

Now we just have to make said thing happen.
"""
print("First round:")
e8  = es[8]
e17 = es[17]

c8  = cts[8]
c17 = cts[17]

# e2 is big
# e1 is small
# e8 is big
# e17 is small

N=n

c17_inv = Crypto.Util.number.inverse(c17, N)

x = c8
for i in range(e8 // e17):
  reduced = (x*c17_inv) % N
  x = reduced
#next i

print("pt**%i == " % (e8 % e17), x)

print("Second round:")
ev1775 = 1775
cv1775 = x

#>>> [e % 1775 for e in es].index(71)
#15

e18 = es[18]
c18 = cts[18]
# e2 is big
# e1 is small
# e1775 is small
# e18 is big

cv1775_inv = Crypto.Util.number.inverse(cv1775, N)
x = None
x = c18
for i in range(e18 // ev1775):
  reduced = (x*cv1775_inv) % N
  x = reduced
  if i & 0xfffff == 0: print(i)
#next i

print("pt**%i == " % (e18 % ev1775), x)
# pt**309 ==  77812143691613137859642574159751661524059656531077281832519514607166612396443019877291279228946029262208452737727357399060260572705324856415477500890491548105139173030286296654630429582478615912190130048364100883562180845460100956750790149256651343993188760510224743760002627483741121653831578520450860678971

print("Fourth round:")
e5 = es[5]
c5 = cts[5]
ev309 = 309
cv309 = x
cv309_inv = Crypto.Util.number.inverse(cv309, N)
x = None
x = c5
for i in range(e5 // ev309):
  reduced = (x*cv309_inv) % N
  x = reduced
  if i & 0xfffff == 0: print(i)
#next i

print("pt**%i == " % (e5 % ev309), x)
# pt**14 ==  27886551985375180119142257698198169680785819745800876267667334683899150260379015867328461457168129787983685908863283637175608702914017729024858236190216068123162447684806625206823427949151063725365869097301347014506928254536158313067042819454111737574973705118098896158360196887284334117004352987400844142343

print("Fifth round:")

e17 = es[17]
c17 = cts[17]
ev14 = 14
cv14 = x
cv14_inv = Crypto.Util.number.inverse(cv14, N)
x = None
x = c17
for i in range(e17 // ev14):
  reduced = (x*cv14_inv) % N
  x = reduced
  if i & 0xfffff == 0: print(i)
#next i

print("pt**%i == " % (e17 % ev14), x)
# pt**1 ==  11859814987468385682904193929732856121563109146807186957694593421160017639466355

#x_inv = Crypto.Util.number.inverse(x, N)
#reduced = (c1*x_inv) % N

#pt = reduced

pt = x

print("pt == ", pt)

print("solution == ", binascii.unhexlify(hex(pt)[2:]))
# solution ==  b'flag_Strength_Lies_In_Differences'

Posted on April 24, 2015, 12:34 p.m. by Javantea