'Cryptography' 카테고리의 다른 글

Elliptic Curve Pairings  (0) 2022.11.25 2022.11.04 2022.10.14 2022.09.21 2022.08.24

'Blockchain Security' 카테고리의 다른 글

DFX Finance Attack Overview  (0) 2022.11.16 2022.11.05 2022.10.20 2022.08.30 2022.03.14

'Blockchain Security' 카테고리의 다른 글

DFX Finance Attack Overview  (0) 2022.11.16 2022.11.05 2022.10.21 2022.08.30 2022.03.14

https://www.secmem.org/blog/2022/09/12/DarkPCS/

'Cryptography' 카테고리의 다른 글

New Lookup Argument  (0) 2022.11.04 2022.10.24 2022.09.21 2022.08.24 2022.08.12

'Cryptography' 카테고리의 다른 글

Sum-Check Protocol and Applications  (0) 2022.10.24 2022.10.14 2022.08.24 2022.08.12 2022.08.04

Problem Description

We are given a 2000-bit RSA modulus $n$, with public exponent $e$.

Here, we have $d_p, d_q < 2^{105}$ where $d_p, d_q$ are inverses of $e$ modulo $p-1, q-1$.

We are given $d_p \pmod{2^{55}}, d_q \pmod{2^{55}}$ as a hint. We need to factor $n$.

Solution

In the paper "Twenty Years of Attacks on the RSA Cryptosystem", there's a note that there is a $\tilde{\mathcal{O}}(\sqrt{d_p})$ attack against CRT-RSA. Since we don't know only 50 bits of $d_p$, it's worth thinking about whether the same attack works here. It turns out that it does!

I explained the attack in my blog a few years ago (Korean), and I turned it into a challenge in picoCTF 2021.

For completeness, I'll explain the full solution here. The idea is meet in the middle. We see that $$\prod_{j=0}^{2^{25} - 1} \prod_{i=0}^{2^{25} - 1} \left( m^{e (hint_p + (i \cdot 2^{25} + j) \cdot 2^{55})} - m \right)$$ will be a multiple of $p$. This is because when we hit the pair $(i, j)$ such that $$hint_p + i \cdot 2^{80} + j \cdot 2^{55} = d_p$$ we'll multiply $$m^{ed_p} - m \equiv 0 \pmod{p}$$ into the product. To compute this, we write $$G(x) = \prod_{i=0}^{2^{25} - 1} \left( m^{e (hint_p + i \cdot 2^{80})} \cdot x - m \right)$$ Denoting $$z = m^{e \cdot 2^{55}} \pmod{n}$$ we see that it now suffices to compute $$G(z^0), G(z^1), \cdots G(z^{2^{25} - 1})$$ which is now a polynomial computation problem. To this, there are two methods.

In the picoCTF, the challenge size was not too large - therefore, less optimal methods worked. At the time, the model solution was divide & conquer + FFT to compute $G$ in $\mathcal{O}(\sqrt{d_p} \log^2 \sqrt{d_p})$ time, and then using multipoint evaluation algorithm to evaluate it over the needed points. This method requires polynomial division, and overall has a quite large overhead. This is implemented in the github link above.

Here, the size of the challenge is $2^{25}$ with 2000 bit modulus, so we need to be faster. To do so, we compute $G$ using the same method i.e. divider & conquer + FFT, but instead of using generic multipoint evaluation algorithms we note that the points we need to evaluate $G$ is geometric. Therefore, we may utilize the awesome Chirp-Z transform to our advantage. This will enable us to compute all evaluations with a single logarithm factor. This is what we implemented. For more information on Chirp-Z transform, check cp-algorithms.

However, there are quite a lot of obstacles due to large problem size - it took us over 24 hours to actually get the flag.

• first, the FFT size in sagemath is apparently capped, so it can't multiply two polynomials of degree $2^{24}$
• therefore, to multiply large polynomials, we have to split the polynomial and multiply in pieces ourselves
• it turns out that this solution requires at least 128GB of RAM, and even this requires some memory optimizations
•  on a good computing environment, our solution takes about 4~5 hours.

The computation of $G$ took about 2 hours, and the remaining parts also took around 2 hours.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 from sage.all import *  import random as rand from tqdm import tqdm  import time  from Crypto.Util.number import inverse, getPrime    p_size = 1000 d_size = 105 l_size = 55   enc = 35558284230663313298312684064040643811204702946900174110911295087662938676356112802781671547473910691476600838877279843972105403072929243674403244286458898562457747942651643439624568905004454158744508429126554955023110569348839934098381885098523538078300248638407684468503519326866276798222721018258242443186786917829878515320321445508466038372324063139762003962072922393974710763356236627711414307859950011736526834586028087922704589199885845050751932885698053938070734392371814246294798366452078193195538346218718588887085179856336533576097324041969786125752304133487678308830354729347735644474025828   pk = (44774502335951608354043148360684114092901940301155357314508676399067538307546121753785009844275454594381602690061553832466871574728524408152400619047820736137949166290404514747591817206669966103047443912935755873432503095952914080827536130899968275165557303493867755627520568588808534411526058896791373252974606364861105086430729757064078675811147972536205086402752245214343186536177015741922559575575911278873118556603923689408629477875537332177644886701517140711134017511229202430437068095342526435886609381176269251580339549071944830141516001532825295594908434587285225415103472279090325281062442217, 29624366183227462965645558392954094074485353876807451497147549927093025197118051280445930543762170853769573962200247669305286333212410439624262142109295839433584663989554419810341266820063074908743295553517790354149623873028162282751352613333181218478850463012413786673509078012976454604598813805735677104174112776060905225493357010861225261560490401501912259585922988353328944884443953564154752191932500561561256069872534626325000901099904014035414792860997025614313564862063784602254606240743545483125618939111639728114664995759380293512809125885893543730614962375399353971677980309835647540883700977)   hint = (5013415024346389, 4333469053087705)     (n, e) = pk (hint_p, hint_q) = hint   SIZE = 1 << ((d_size - l_size) // 2) m = Zmod(n)(rand.randint(2, 1 << 128)) print("m", int(m))   RR = Zmod(n)   chirp = m ** (e << l_size) Fix1 = m ** (e * hint_p) Fix2 = m ** (e << ((l_size + d_size) // 2))   sys.setrecursionlimit(10 ** 6)   P = PolynomialRing(RR, 'x') x = P.gen()   T = time.time()   cnt = 0    DEG_BOUND = (1 << 24)   def getMul(f1, f2):     if f1.degree() < DEG_BOUND and f2.degree() < DEG_BOUND:         return f1 * f2     arr = [RR(0)] * (f1.degree() + f2.degree() + 1)     temp1 = f1.coefficients(sparse = False)     temp2 = f2.coefficients(sparse = False)     idx1 = 0     U1s = []     while idx1 <= f1.degree():         U1s.append(P(temp1[idx1: idx1 + DEG_BOUND]))         idx1 += DEG_BOUND      idx2 = 0     U2s = []     while idx2 <= f2.degree():         U2s.append(P(temp2[idx2: idx2 + DEG_BOUND]))         idx2 += DEG_BOUND     idx1, idx2 = 0, 0     while idx1 * DEG_BOUND <= f1.degree():         idx2 = 0         while idx2 * DEG_BOUND <= f2.degree():             temp = (U1s[idx1] * U2s[idx2]).coefficients(sparse = False)             for v in range(len(temp)):                 arr[(idx1 + idx2) * DEG_BOUND + v] += temp[v]             idx2 += 1         idx1 += 1     return P(arr)   def compute(L, R):     global cnt     if R - L == (1 << 16):         print("HEY", cnt)         cnt += 1     if L >= R:         return 1      if L + 1 == R:         return ((Fix2 ** L) * Fix1) * x - m     f1 = compute(L, (L + R) // 2)     f2 = compute((L + R) // 2, R)     return getMul(f1, f2)   G = compute(0, SIZE)   print(time.time() - T)   # now compute all  print("computed G(x), now multipoint eval via chirp-z")   coefG = G.coefficients(sparse = False)   del G    A1 = [RR(1), RR(1)] cur = RR(1) for i in tqdm(range(2, SIZE * 2)):     cur = cur * chirpwa     A1.append(A1[i-1] * cur)   A0 = [] for i in tqdm(range(SIZE + 1)):     A0.append(coefG[SIZE - i] / A1[SIZE - i])   del coefG     idx1 = 0 U1s = [] while idx1 <= SIZE:     U1s.append(P(A0[idx1: idx1 + DEG_BOUND]))     idx1 += DEG_BOUND  del A0    print("A0")   idx2 = 0 U2s = [] while idx2 <= SIZE * 2 - 1:     U2s.append(P(A1[idx2: idx2 + DEG_BOUND]))     idx2 += DEG_BOUND   print("A1")   arr = [RR(0)] * (SIZE) idx1, idx2 = 0, 0 while idx1 * DEG_BOUND <= SIZE:     idx2 = 0     while idx2 * DEG_BOUND <= SIZE * 2 - 1:         temp = (U1s[idx1] * U2s[idx2]).coefficients(sparse = False)         for v in range(len(temp)):             if SIZE <= (idx1 + idx2) * DEG_BOUND + v < 2 * SIZE:                 arr[(idx1 + idx2) * DEG_BOUND + v - SIZE] += temp[v]         del temp          idx2 += 1     idx1 += 1   print("now let's calculate it!")   for i in tqdm(range(0, SIZE)):     val = arr[i] / A1[i]     t = GCD(int(val), n)     if t != 1 and t != n:         print("Found!!!!", t)   print(time.time() - T)   Colored by Color Scripter cs

'CTF' 카테고리의 다른 글

BlackHat MEA Finals  (0) 2022.11.21 2022.11.09 2022.09.19 2022.06.27 2022.02.28

Problem Summary

The goal here is to emit the event SendFlag(). To do so, we need to gain control of all three NFTs.

In the contract file, there is an ERC721 called "TctfNFT" and ERC20 called "TctfToken". We also see that during the initialization the marketplace contract gets 1337 TctfTokens. In the market's constructor, three NFTs are minted, the first to the NFT contract and the other to the market contract. These three NFTs are put on sale on a price of 1, 1337, and some insanely large price. We'll have to get all these NFTs.

Looking at the contract's methods, we see that

• We may get an airdrop of 5 tokens but only once.
• We can create a sell order of NFT under the condition that we have control (approval or owner) over it.
• We can cancel a sell order of NFT under the condition that we have control over it.
• We can purchase an order of NFT with enough tokens.
• We can purchase an order of NFT with a coupon, but only once. The issuer of the coupon should be the NFT owner, and we have to supply the signature of the issuer for the coupon. For this problem, we pretty much have to know the private key of the issuer.
• We can use purchaseTest() function only once. Here, the market creates one order and purchases it on its own.

Approach

The constraint gives us some hints on how to approach the problem.

The first NFT is very cheap, so we can purchase without any trickery. The two functions purchaseTest() and purchaseWithCoupon() are very suspicious, and we can use these only once each. Therefore, each suspicious functions will have us stealing one NFT. Since purchaseWithCoupon() function gives us power to change a price of an order, we should use it to buy the third NFT. The second NFT costs 1337 tokens, and it just happens that the market contract holds 1337 tokens. Therefore, we should use purchaseTest function to steal those tokens.

Part 1: The purchaseTest()

There are multiple ways to solve this part of the problem. I'll show my solution and sqrtrev's solution.

The dangerous thing about many of the market's methods is that it takes the order ID as input. If we simply used a mapping for these orders, it would probably not be a problem. However, we use a variable length array to handle our orders. To keep our array length the same as the number of valid orders, we use a nice algorithm which can be seen in _deleteOrder(). When an element of the array is deleted, the element at the back is put at the location of the deleted element. This is also a strategy used in OpenZeppelin's EnumerableSet contracts to keep index of the elements. Now we see the problem - the value at a specific index may change due to element addition and deletion.

Now let's take a look at the purchaseTest() function again. It creates order, then purchases the order.

If we look at the createOrder() function again, we see that the only external calls are done to simply check the approval or ownership, but those are done with staticcalls. Therefore, we can't use that to attack. We also see that we can't perform the attack in purchaseOrder(). Thankfully for us, there is an approve call to the NFT address. This can definitely be used to our advantage.

Basically, we create a dumb NFT and send it to the TctfMarket. We call purchaseTest() with the NFT.

Inside the approve() call, we will create another order, which sells a dumb NFT that we own at 1337 tokens. Then, we will remove the order that we just created. This will make the order at the order ID equal to the "sell dumb NFT at 1337 token" order. Now the market will happily purchase this new order, sending us 1337 tokens. This gives us enough funds to buy the second NFT anytime we want.

sqrtrev's solution is much simple, it simply sends the NFT that is being sold at purchaseTest() to our EOA at the approve() call. Inside the purchaseOrder() function, we see that the funds are sent to the owner of the token, so it'll be sent to us. Looking back, I overcomplicated this part of the problem. Part of it is because I took a look at EnumerableSet recently, I guess. It's all very cool ideas, so it's good.

Part 2: The purchaseWithCoupon()

The first thing we have to notice is that verifyCoupon() is practically a view function. The getOrder() function inside is  view, so it'll be done with staticcall. The ownerOf() function is also view, so staticcall will be used. Therefore, we can't use the same idea to re-enter with a different order at coupon's order ID. Therefore, we can't do anything malicious until the token transfers come in.

We initially thought that the ideas from Part 1 still work, so I wrote all scripts and then realized that it doesn't work.

I believed that a compiler bug must be the way to go, and began searching on solidity's list of known bugs.

Literally everything matched the challenge -

• This solidity bug was patched in 0.8.16. The challenge uses 0.8.15.
• It's stated that the last component must be static-sized array. It is bytes32[2].
• It's stated that one dynamic component is needed. There is a bytes value.
• The bug clears the first 32 bytes of the first dynamic tuple. That happens to be order ID.
• In the blog, it is stated that "Plausible attacks against affected contracts can only occur in situations where the contract accepts a static calldata array as a part of its input and forwards it to another external call without modifying the content." This is exactly what happens in purchaseWithCoupon() and verifyCoupon(). The SignedCoupon struct is sent in as a calldata, and it's directly forwarded.

Some testing shows that if we send a SignedCoupon with order ID 1, it's forwarded to verifyCoupon with order ID 0.

This means that if we have some order that we control at order 0 and the order for the third NFT at some other place, we can use the coupon. This is because the order used to verify the coupon is the order 0, which we own the NFT of. This means that we can sign our own coupon, but use it on the order for the third NFT with the solidity bug. All that's left is to combine these.

Part 3: Combining Everything

We'll denote the order for the NFTs that we need to get as order #1, #2, #3. We note that for the bug at Part 2, we need a order that we control at the order ID 0. With this in mind, we will set up our attack as follows. We'll use sqrtrev's approach on Part 1.

• Get the TctfToken airdrop. Currently, the orders on the market is [#1, #2, #3].
• Perform sqrtrev's attack. We'll get 1337 tokens, and the orders on the market is still [#1, #2, #3].
• We'll buy NFT #2 with our 1337 tokens, and the orders on the market is [#1, #3]
• We'll mint a dumb NFT to ourself, and create an order. The orders on the market is [#1, #3, us].
• Now we'll buy NFT #1 with 1 token. The orders on the market is [us, #3].
• Now the order ID 0 is an order we control - so the attack from Part 2 works. We buy NFT #3 with 1 token.

This will give us the flag. Foundry testing is very easy to do, but hardhat scripting was a bit painful. It can be done though.